mlsanityData to 7 Oct 2026

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

arXiv 2206.07892 ↗First posted 16 Jun 2022cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

46 of 55 references.

References · 46

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  3. 2017Exploring Generalization in Deep Learningcited by 595
  4. 2019Benign Overfitting in Linear Regressioncited by 544
  5. 2017Implicit Regularization in Matrix Factorizationcited by 318
  6. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  7. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  8. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  9. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  10. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  11. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  12. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
34 more
  1. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  2. 2018To understand deep learning we need to understand kernel learningcited by 186
  3. 2019Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networkscited by 162
  4. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
  5. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  6. 2019Harmless interpolation of noisy data in regressioncited by 121
  7. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  8. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  9. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  10. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  11. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  12. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  13. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  14. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  15. 2019Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentationcited by 71
  16. 2020The Implicit and Explicit Regularization Effects of Dropoutcited by 71
  17. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 63
  18. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  19. 2019Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margincited by 56
  20. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  21. 2019Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resiliencecited by 51
  22. 2021Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixturescited by 48
  23. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  24. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 41
  25. 2022The Implicit Bias of Benign Overfittingcited by 38
  26. 2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 33
  27. 2020On the proliferation of support vectors in high dimensionscited by 32
  28. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  29. 2020Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularizationcited by 27
  30. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  31. 2022On the Generalization Mystery in Deep Learningcited by 25
  32. 2020On Uniform Convergence and Low-Norm Interpolation Learningcited by 24
  33. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  34. 2021Exact Gap between Generalization Error and Uniform Convergence in Random Feature Modelscited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 0; 2025: 0; 2026: 1.

6 papers.

  1. 2023The Benefits of Mixup for Feature Learningcited by 19
  2. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  3. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  4. 2023What do larger image classifiers memorise?cited by 6
  5. 2023Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networkscited by 4
  6. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0