# Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 55 references that are in the map.
- First posted on arXiv 16 Jun 2022.

## Builds on (most cited first, 30 of 46)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks](https://mlsanity.com/paper/1907.04595/) (2019)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [Label Noise SGD Provably Prefers Flat Global Minimizers](https://mlsanity.com/paper/2106.06530/) (2021)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Shape Matters: Understanding the Implicit Bias of the Noise Covariance](https://mlsanity.com/paper/2006.08680/) (2020)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation](https://mlsanity.com/paper/1905.03684/) (2019)
- [The Implicit and Explicit Regularization Effects of Dropout](https://mlsanity.com/paper/2002.12915/) (2020)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)

## Built on by (most cited first, 6 of 6)

- [The Benefits of Mixup for Feature Learning](https://mlsanity.com/paper/2303.08433/) (2023)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [What do larger image classifiers memorise?](https://mlsanity.com/paper/2310.05337/) (2023)
- [Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks](https://mlsanity.com/paper/2305.16475/) (2023)
- [Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2602.22936/) (2026)

## Abstract (arXiv)

A major challenge in modern machine learning is theoretically understanding the generalization properties of overparameterized models. Many existing tools rely on uniform convergence (UC), a property that, when it holds, guarantees that the test loss will be close to the training loss, uniformly over a class of candidate models. Nagarajan and Kolter (2019) show that in certain simple linear and neural-network settings, any uniform convergence bound will be vacuous, leaving open the question of how to prove generalization in settings where UC fails. Our main contribution is proving novel generalization bounds in two such settings, one linear, and one non-linear. We study the linear classification setting of Nagarajan and Kolter, and a quadratic ground truth function learned via a two-layer neural network in the non-linear regime. We prove a new type of margin bound showing that above a certain signal-to-noise threshold, any near-max-margin classifier will achieve almost no test loss in these two settings. Our results show that near-max-margin is important: while any model that achieves at least a (1 - ε)-fraction of the max-margin generalizes well, a classifier achieving half of the max-margin may fail terribly. Building on the impossibility results of Nagarajan and Kolter, under slightly stronger assumptions, we show that one-sided UC bounds and classical margin bounds will fail on near-max-margin classifiers. Our analysis provides insight on why memorization can coexist with generalization: we show that in this challenging regime where generalization occurs but UC fails, near-max-margin classifiers simultaneously contain some generalizable components and some overfitting components that memorize the data. The presence of the overfitting components is enough to preclude UC, but the near-extremal margin guarantees that sufficient generalizable components are present.