For linear classifiers, the relationship between (normalized) output margin
and generalization is captured in a clear and simple bound -- a large output
margin implies good generalization. Unfortunately, for deep models, this
relationship is less clear: existing analyses of the output margin give
complicated bounds which sometimes depend exponentially on depth. In this work,
we propose to instead analyze a new notion of margin, which we call the
äll-layer margin." Our analysis reveals that the all-layer margin has a clear
and direct relationship with generalization for deep models. This enables the
following concrete applications of the all-layer margin: 1) by analyzing the
all-layer margin, we obtain tighter generalization bounds for neural nets which
depend on Jacobian and hidden layer norms and remove the exponential dependency
on depth 2) our neural net results easily translate to the adversarially robust
setting, giving the first direct analysis of robust test error for deep
networks, and 3) we present a theoretically inspired training algorithm for
increasing the all-layer margin and demonstrate that our algorithm improves
test performance over strong baselines in practice.
Description
[1910.04284] Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
%0 Journal Article
%1 wei2019improved
%A Wei, Colin
%A Ma, Tengyu
%D 2019
%K bounds complexity generalization readings sampling
%T Improved Sample Complexities for Deep Networks and Robust Classification
via an All-Layer Margin
%U http://arxiv.org/abs/1910.04284
%X For linear classifiers, the relationship between (normalized) output margin
and generalization is captured in a clear and simple bound -- a large output
margin implies good generalization. Unfortunately, for deep models, this
relationship is less clear: existing analyses of the output margin give
complicated bounds which sometimes depend exponentially on depth. In this work,
we propose to instead analyze a new notion of margin, which we call the
äll-layer margin." Our analysis reveals that the all-layer margin has a clear
and direct relationship with generalization for deep models. This enables the
following concrete applications of the all-layer margin: 1) by analyzing the
all-layer margin, we obtain tighter generalization bounds for neural nets which
depend on Jacobian and hidden layer norms and remove the exponential dependency
on depth 2) our neural net results easily translate to the adversarially robust
setting, giving the first direct analysis of robust test error for deep
networks, and 3) we present a theoretically inspired training algorithm for
increasing the all-layer margin and demonstrate that our algorithm improves
test performance over strong baselines in practice.
@article{wei2019improved,
abstract = {For linear classifiers, the relationship between (normalized) output margin
and generalization is captured in a clear and simple bound -- a large output
margin implies good generalization. Unfortunately, for deep models, this
relationship is less clear: existing analyses of the output margin give
complicated bounds which sometimes depend exponentially on depth. In this work,
we propose to instead analyze a new notion of margin, which we call the
"all-layer margin." Our analysis reveals that the all-layer margin has a clear
and direct relationship with generalization for deep models. This enables the
following concrete applications of the all-layer margin: 1) by analyzing the
all-layer margin, we obtain tighter generalization bounds for neural nets which
depend on Jacobian and hidden layer norms and remove the exponential dependency
on depth 2) our neural net results easily translate to the adversarially robust
setting, giving the first direct analysis of robust test error for deep
networks, and 3) we present a theoretically inspired training algorithm for
increasing the all-layer margin and demonstrate that our algorithm improves
test performance over strong baselines in practice.},
added-at = {2019-10-22T03:21:27.000+0200},
author = {Wei, Colin and Ma, Tengyu},
biburl = {https://www.bibsonomy.org/bibtex/25fb4266f0377d48ee3ca46387fa065b7/kirk86},
description = {[1910.04284] Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin},
interhash = {9a1d3f7b37e1ef29ba25c764d0a7e51a},
intrahash = {5fb4266f0377d48ee3ca46387fa065b7},
keywords = {bounds complexity generalization readings sampling},
note = {cite arxiv:1910.04284},
timestamp = {2019-10-22T03:21:27.000+0200},
title = {Improved Sample Complexities for Deep Networks and Robust Classification
via an All-Layer Margin},
url = {http://arxiv.org/abs/1910.04284},
year = 2019
}