CoChat
Sign Up
PreprintCited by 118Stochastic Gradient Optimization TechniquesMachine Learning and AlgorithmsDomain Adaptation and Few-Shot Learning

Uniform convergence may be unable to explain generalization in deep learning

Open access
Nagarajan, Vaishnavh, Kolter, J. Zico·2019·arXiv
DOI 10.48550/arxiv.1902.04742arXiv 1902.04742
Open this paper in CoChat — free accountOpen PDF

Abstract

Aimed at explaining the surprisingly good generalization behavior of overparameterized deep networks, recent works have developed a variety of generalization bounds for deep learning, all based on the fundamental learning-theoretic technique of uniform convergence. While it is well-known that many of these existing bounds are numerically large, through numerous experiments, we bring to light a more concerning aspect of these bounds: in practice, these bounds can {\em increase} with the training dataset size. Guided by our observations, we then present examples of overparameterized linear classifiers and neural networks trained by gradient descent (GD) where uniform convergence provably cannot "explain generalization" -- even if we take into account the implicit bias of GD {\em to the fullest extent possible}. More precisely, even if we consider only the set of classifiers output by GD, which have test errors less than some small $ε$ in our settings, we show that applying (two-sided) uniform convergence on this set of classifiers will yield only a vacuous generalization guarantee larger than $1-ε$. Through these findings, we cast doubt on the power of uniform convergence-based generalization bounds to provide a complete picture of why overparameterized deep networks generalize well.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1902.04742

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Models with the same architecture will often converge to the same basin of weights, even with different initializations, up to permutations over weight space.

    “While models with different architectures might not have compatible weight spaces, there exists ample evidence that models with the same architecture will often converge to the same basin of weights (Nagarajan & Kolter, 2019;Garipov et al., 2018;Lubana et al., 2023).This holds even for models with different initializations, up to permutations over weight space (Srinivasan et al., 2021).”

    From The Platonic Representation Hypothesis (2024) · cites this paper as Nagarajan & Kolter, 2019

    In B More Experiments (p. 13), the paper says SGD explores the same test-loss basin across different training sets when starting from a fixed initialization. That supports a narrower version of the first sentence, but not its broader suggestion that sharing an architecture is generally enough. The different-initializations statement is separately cited to Srinivasan et al.; this paper distinguishes that setting from its own observation. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 39

  1. [1][1] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. abs/1811.04918, 2018. URL http://arxiv.org/abs/1811.04918 . - · arXiv
  2. [2][2] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In The 35th International Conference on Machine Learning, ICML , 2018. -
  3. [3][3] Peter L. Bartlett, Dylan J. Foster, and Matus J. Telgarsky. Spectrally-normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 , 2017. -
  4. [4][4] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 , 2018. -
  5. [5][5] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research , 2, 2002. -
  6. [6][6] Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns overparameterized networks that provably generalize on linearly separable data. International Conference on Learning Representations (ICLR) , 2018. -
  7. [7][7] Felix Dräxler, Kambis Veschgini, Manfred Salmhofer, and Fred A. Hamprecht. Essentially no barriers in neural network energy landscape. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 , 2018. -
  8. [8][8] Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, UAI 2017 , 2017. -
  9. [9][9] Vitaly Feldman and Jan Vondrák. Generalization bounds for uniformly stable algorithms. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018 , 2018. -
  10. [10][10] Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P. Vetrov, and Andrew G. Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018 , 2018. -
  11. [11][11] Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian J. Goodfellow. Adversarial spheres. In 6th International Conference on Learning Representations, ICLR 2018 , 2018. -
  12. [12][12] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Computational Learning Theory, COLT 2018 , 2018. -
  13. [13][13] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33nd International Conference on Machine Learning, ICML , 2016. -
  14. [14][14] Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension bounds for piecewise linear neural networks. In Proceedings of the 30th Conference on Learning Theory, COLT 2017 , 2017. -
  15. [15][15] Geoffrey E. Hinton and Drew van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, COLT , 1993. -
  16. [16][16] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation , 9(1), 1997. -
  17. [17][17] Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. Advances in Neural Information Processing Systems ( to appear ) , 2017. -
  18. [18][18] Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018 , 2018. -
  19. [19][19] Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos J. Storkey. Width of minima reached by stochastic gradient descent is influenced by learning rate to batch size ratio. In Artificial Neural Networks and Machine Learning - ICANN 2018 - 27th International Conference on Artificial Neural Networks , 2018. -
  20. [20][20] Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. 2017. URL http://arxiv.org/abs/1710.05468 . - · arXiv
  21. [21][21] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. International Conference on Learning Representations (ICLR) , 2017. -
  22. [22][22] John Langford and Rich Caruana. (not) bounding the true error. In Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001] , 2001. -
  23. [23][23] John Langford and John Shawe-Taylor. Pac-bayes & margins. In Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, NIPS 2002 , 2002. -
  24. [24][24] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018 , 2018. -
  25. [25][25] David McAllester. Simplified pac-bayesian margin bounds. In Learning Theory and Kernel Machines . Springer Berlin Heidelberg, 2003. -
  26. [26][26] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning . Adaptive computation and machine learning. MIT Press, 2012. -
  27. [27][27] Vaishnavh Nagarajan and J. Zico Kolter. Generalization in deep networks: The role of distance from initialization. Deep Learning: Bridging Theory and Practice Workshop in Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 , 2017. -
  28. [28][28] Vaishnavh Nagarajan and Zico Kolter. Deterministic PAC-bayesian generalization bounds for deep networks via generalizing noise-resilience. In International Conference on Learning Representations (ICLR) , 2019. -
  29. [29][29] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. International Conference on Learning Representations Workshop Track , 2015. -
  30. [30][30] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of The 28th Conference on Learning Theory, COLT , 2015. -
  31. [31][31] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring generalization in deep learning. Advances in Neural Information Processing Systems to appear, 2017. -
  32. [32][32] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. A pacbayesian approach to spectrally-normalized margin bounds for neural networks. International Conference on Learning Representations (ICLR) , 2018. -
  33. [33][33] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrization in generalization of neural networks. In International Conference on Learning Representations (ICLR) , 2019. -
  34. [34][34] W. H. Rogers and T. J. Wagner. A finite sample distribution-free performance bound for local discrimination rules. The Annals of Statistics , 6(3), 1978. -
  35. [35][35] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research , 11, 2010. -
  36. [36][36] Daniel Soudry, Elad Hoffer, and Nathan Srebro. The implicit bias of gradient descent on separable data. International Conference on Learning Representations (ICLR) , 2018. -
  37. [38][38] Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. -
  38. [39][39] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Representations (ICLR) , 2017. -
  39. [40][40] Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Nonvacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach. In International Conference on Learning Representations (ICLR) , 2019.

Cited by

Sorted by citations

Authors
Nagarajan, V., & Kolter, J. Z.
Affiliations
Carnegie Mellon University (US)
ORCID
Kolter, J. Zico
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
32
Pages
11611-11622
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1902.04742
arXiv
1902.04742
OpenAlex
W2970290137
Cited by
118
References
0
Citations by year
2025: 4 · 2024: 10 · 2023: 13 · 2022: 11 · 2021: 37 · 2020: 35 · 2019: 8
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • neural information processing systems
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Domain Adaptation and Few-Shot Learning
Keywords
uniform convergence, generalization bounds, overparameterized neural networks, implicit bias, gradient descent

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review