Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
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. Our algorithm improves both clean and adversarially robust test performance over strong baselines in practice.
Code (1)
Tasks
AllGeneral ClassificationGeneralization BoundsRobust classificationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Improved Sample Complexities for Deep Neural Networks and Robust Classification via an All-Layer Margin
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, …
AllGeneralization BoundsRobust classificationCollaborative Layer-wise Discriminative Learning in Deep Neural Networks
Intermediate features at different layers of a deep neural network are known to be discriminative for visual patterns of different complexities. However, most existing works ignore such cross-layer heterogeneities when c…
ClassificationGeneral ClassificationScene ClassificationSample-efficient actor-critic algorithms with an etiquette for zero-sum Markov games
We introduce algorithms based on natural policy gradient and two time-scale natural actor-critic, and analyze their sample complexity for solving two player zero-sum Markov games in the tabular case. Our results improve …
Policy Gradient MethodsLarge Margin Deep Networks for Classification
We present a formulation of deep learning that aims at producing a large margin classifier. The notion of margin, minimum distance to a decision boundary, has served as the foundation of several theoretically profound an…
ClassificationData AugmentationGeneral ClassificationPareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck
In modern deep learning, algorithmic choices (such as width, depth, and learning rate) are known to modulate nuanced resource tradeoffs. This work investigates how these complexities necessarily arise for feature learnin…
tabular-classification