# Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin

arXiv: https://arxiv.org/abs/1910.04284 · HTML: https://mlsanity.com/paper/1910.04284/

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2019.

## Built on by (most cited first, 30 of 56)

- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path](https://mlsanity.com/paper/2106.02073/) (2021)
- [Label Noise SGD Provably Prefers Flat Global Minimizers](https://mlsanity.com/paper/2106.06530/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models](https://mlsanity.com/paper/2210.14199/) (2022)
- [On the effectiveness of adversarial training against common corruptions](https://mlsanity.com/paper/2103.02325/) (2021)
- [How Does Sharpness-Aware Minimization Minimize Sharpness?](https://mlsanity.com/paper/2211.05729/) (2022)
- [A Theory of Label Propagation for Subpopulation Shift](https://mlsanity.com/paper/2102.11203/) (2021)
- [Theoretical Analysis of Weak-to-Strong Generalization](https://mlsanity.com/paper/2405.16043/) (2024)
- [Aug-NeRF: Training Stronger Neural Radiance Fields with Triple-Level Physically-Grounded Augmentations](https://mlsanity.com/paper/2207.01164/) (2022)
- [Improved Regularization and Robustness for Fine-tuning in Neural Networks](https://mlsanity.com/paper/2111.04578/) (2021)
- [A Theoretical Study of Inductive Biases in Contrastive Learning](https://mlsanity.com/paper/2211.14699/) (2022)
- [Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalization](https://mlsanity.com/paper/2307.11007/) (2023)
- [Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guarantees](https://mlsanity.com/paper/2206.02659/) (2022)
- [Noisy Feature Mixup](https://mlsanity.com/paper/2110.02180/) (2021)
- [Data-Efficient GAN Training Beyond (Just) Augmentations: A Lottery Ticket Perspective](https://mlsanity.com/paper/2103.00397/) (2021)
- [Measuring Generalization with Optimal Transport](https://mlsanity.com/paper/2106.03314/) (2021)
- [Evaluating natural language processing models with generalization metrics that do not need access to any training or testing data](https://mlsanity.com/paper/2202.02842/) (2022)
- [A PAC-Bayesian Generalization Bound for Equivariant Networks](https://mlsanity.com/paper/2210.13150/) (2022)
- [What is a Good Metric to Study Generalization of Minimax Learners?](https://mlsanity.com/paper/2206.04502/) (2022)
- [A Scaling Law for Synthetic-to-Real Transfer: How Much Is Your Pre-training Effective?](https://mlsanity.com/paper/2108.11018/) (2021)
- [The activity-weight duality in feed forward neural networks: The geometric determinants of generalization](https://mlsanity.com/paper/2203.10736/) (2022)
- [Adversarial Feature Augmentation and Normalization for Visual Recognition](https://mlsanity.com/paper/2103.12171/) (2021)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [The Sample Complexity of One-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.06233/) (2022)
- [A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning](https://mlsanity.com/paper/2206.01132/) (2022)
- [On the Role of Generalization in Transferability of Adversarial Examples](https://mlsanity.com/paper/2206.09238/) (2022)
- [Koopman-based generalization bound: New aspect for full-rank weights](https://mlsanity.com/paper/2302.05825/) (2023)
- [Sparsity-aware generalization theory for deep neural networks](https://mlsanity.com/paper/2307.00426/) (2023)
- [Recent Advances in Large Margin Learning](https://mlsanity.com/paper/2103.13598/) (2021)

## Abstract (arXiv)

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.