CoChat
Sign Up
PreprintCited by 44Stochastic Gradient Optimization TechniquesNeural Networks and ApplicationsDomain Adaptation and Few-Shot Learning

The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian

Open access
Oymak, Samet, Fabian, Zalan, Li, Mingchen, Soltanolkotabi, Mahdi·2019·arXiv
DOI 10.48550/arxiv.1906.05392arXiv 1906.05392
Open this paper in CoChat — free accountOpen PDF

Abstract

Modern neural network architectures often generalize well despite containing many more parameters than the size of the training dataset. This paper explores the generalization capabilities of neural networks trained via gradient descent. We develop a data-dependent optimization and generalization theory which leverages the low-rank structure of the Jacobian matrix associated with the network. Our results help demystify why training and generalization is easier on clean and structured datasets and harder on noisy and unstructured datasets as well as how the network size affects the evolution of the train and test errors during training. Specifically, we use a control knob to split the Jacobian spectum into "information" and "nuisance" spaces associated with the large and small singular values. We show that over the information space learning is fast and one can quickly train a model with zero training loss that can also generalize well. Over the nuisance space training is slower and early stopping can help with generalization at the expense of some bias. We also show that the overall generalization capability of the network is controlled by how well the label vector is aligned with the information space. A key feature of our results is that even constant width neural nets can provably generalize for sufficiently nice datasets. We conduct various numerical experiments on deep networks that corroborate our theoretical findings and demonstrate that: (i) the Jacobian of typical neural networks exhibit low-rank structure with a few large singular values and many small ones leading to a low-dimensional information space, (ii) over the information space learning is fast and most of the label vector falls on this space, and (iii) label noise falls on the nuisance space and impedes optimization/generalization.

Overview

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.1906.05392

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Verification

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?

  • For many deep learning tasks, especially those with a heavily over-parametrized neural network, the learned neural network will enjoy low-rank properties after training.

    “Moreover, it is known that for many deep learning tasks, especially those with a heavily over-parametrized neural network, the learned neural network will enjoy low-rank properties after training (Oymak et al., 2019).”

    From LoRA: Low-Rank Adaptation of Large Language Models (2021) · cites this paper as Oymak et al., 2019

    The Abstract (p. 1) reports low-rank structure in the Jacobian of typical neural networks, and Numerical experiments (p. 13) examine the Jacobian after training. The source does not establish that the learned network itself becomes low-rank, or that training produces this property across many deep-learning tasks. (LLM, conf=0.85)

    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.

Citations

Cites

Flagged first, then by citations

Research works printed but not linked: 51

  1. [1][1] Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint arXiv:1811.04918 (2018). - · arXiv
  2. [2][2] Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via over-parameterization. arXiv preprint arXiv:1811.03962 (2018). - · arXiv
  3. [3][3] Anthony, M., and Bartlett, P. L. Neural network learning: Theoretical foundations . cambridge university press, 2009. -
  4. [4][4] Arora, S., Du, S. S., Hu, W., Li, Z., and Wang, R. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584 (2019). - · arXiv
  5. [5][5] Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. Stronger generalization bounds for deep nets via a compression approach. arXiv preprint arXiv:1802.05296 (2018). - · arXiv
  6. [7][7] Bartlett, P. L. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions on Information Theory 44 , 2 (1998), 525-536. -
  7. [8][8] Bartlett, P. L., Maiorov, V., and Meir, R. Almost linear vc dimension bounds for piecewise polynomial networks. In Advances in Neural Information Processing Systems (1999), pp. 190-196. -
  8. [9][9] Bartlett, P. L., and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research 3 , Nov (2002), 463-482. -
  9. [12][12] Belkin, M., Hsu, D., and Xu, J. Two models of double descent for weak features. arXiv preprint arXiv:1903.07571 (2019). - · arXiv
  10. [14][14] Brutzkus, A., Globerson, A., Malach, E., and Shalev-Shwartz, S. Sgd learns overparameterized networks that provably generalize on linearly separable data. arXiv preprint arXiv:1710.10174 (2017). - · arXiv
  11. [15][15] Cao, Y., and Gu, Q. A generalization theory of gradient descent for learning over-parameterized deep relu networks. arXiv preprint arXiv:1902.01384 (2019). - · arXiv
  12. [16][16] Chaudhari, P., Choromanska, A., Soatto, S., LeCun, Y., Baldassi, C., Borgs, C., Chayes, J., Sagun, L., and Zecchina, R. Entropy-sgd: Biasing gradient descent into wide valleys. arXiv preprint arXiv:1611.01838 (2016). - · arXiv
  13. [17][17] Chizat, L., and Bach, F. A note on lazy training in supervised differentiable programming. arXiv preprint arXiv:1812.07956 (2018). - · arXiv
  14. [18][18] Chizat, L., and Bach, F. On the global convergence of gradient descent for over-parameterized models using optimal transport. arXiv preprint arXiv:1805.09545 (2018). - · arXiv
  15. [19][19] Dou, X., and Liang, T. Training neural networks as learning data-adaptive kernels: Provable representation and approximation benefits. arXiv preprint arXiv:1901.07114 (2019). - · arXiv
  16. [20][20] Du, S. S., Lee, J. D., Li, H., Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv:1811.03804 (2018). - · arXiv
  17. [21][21] Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes overparameterized neural networks. arXiv preprint arXiv:1810.02054 (2018). - · arXiv
  18. [22][22] Dziugaite, G. K., and Roy, D. M. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008 (2017). - · arXiv
  19. [23][23] Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. Linearized two-layers neural networks in high dimension. arXiv preprint arXiv:1904.12191 (2019). - · arXiv
  20. [24][24] Goel, S., and Klivans, A. Learning neural networks with two nonlinear layers in polynomial time. arXiv preprint arXiv:1709.06010 (2017). - · arXiv
  21. [25][25] Goel, S., Klivans, A., and Meka, R. Learning one convolutional layer with overlapping patches. arXiv preprint arXiv:1802.02547 (2018). - · arXiv
  22. [26][26] Golowich, N., Rakhlin, A., and Shamir, O. Size-independent sample complexity of neural networks. arXiv preprint arXiv:1712.06541 (2017). - · arXiv
  23. [27][27] Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems (2018), pp. 9461-9471. -
  24. [28][28] Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv:1509.01240 (2015). - · arXiv
  25. [29][29] Hoffer, E., Hubara, I., and Soudry, D. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In Advances in Neural Information Processing Systems (2017), pp. 1731-1741. -
  26. [31][31] Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems (2018), pp. 8571-8580. -
  27. [32][32] Ji, Z., and Telgarsky, M. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv:1810.02032 (2018). - · arXiv
  28. [33][33] Ji, Z., and Telgarsky, M. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300 (2018). - · arXiv
  29. [34][34] Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. T. P. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.04836 (2016). - · arXiv
  30. [36][36] Li, H., Xu, Z., Taylor, G., Studer, C., and Goldstein, T. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems (2018), pp. 6389-6399. -
  31. [37][37] Li, M., Soltanolkotabi, M., and Oymak, S. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. arXiv preprint arXiv:1903.11680 (2019). - · arXiv
  32. [39][39] Long, P. M., and Sedghi, H. Size-free generalization bounds for convolutional neural networks. arXiv preprint arXiv:1905.12600 (2019). - · arXiv
  33. [40][40] Ma, C., Wu, L., et al. A comparative analysis of the optimization and generalization property of two-layer neural network and random feature models under gradient descent dynamics. arXiv preprint arXiv:1904.04326 (2019). - · arXiv
  34. [41][41] Maurer, A. A vector-contraction inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory (2016), Springer, pp. 3-17. -
  35. [42][42] Mei, S., Montanari, A., and Nguyen, P.-M. A mean field view of the landscape of two-layers neural networks. arXiv preprint arXiv:1804.06561 (2018). - · arXiv
  36. [43][43] Nagarajan, V., and Kolter, J. Z. Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. arXiv preprint arXiv:1905.13344 (2019). - · arXiv
  37. [44][44] Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. Exploring generalization in deep learning. In Advances in Neural Information Processing Systems (2017), pp. 5947-5956. -
  38. [45][45] Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. A pac-bayesian approach to spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564 (2017). - · arXiv
  39. [46][46] Nitanda, A., and Suzuki, T. Refined generalization analysis of gradient descent for overparameterized two-layer neural networks with smooth activations on classification problems. arXiv preprint arXiv:1905.09870 (2019). - · arXiv
  40. [48][48] Oymak, S., and Soltanolkotabi, M. Towards moderate overparameterization: global convergence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.04674 (2019). - · arXiv
  41. [50][50] Sagun, L., Evci, U., Guney, V. U., Dauphin, Y., and Bottou, L. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv:1706.04454 (2017). - · arXiv
  42. [51][51] Schmitt, B. A. Perturbation bounds for matrix square roots and pythagorean sums. Linear algebra and its applications 174 (1992), 215-227. -
  43. [52][52] Schur, J. Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen veränderlichen. Journal für die reine und angewandte Mathematik 140 (1911), 1-28. -
  44. [54][54] Song, M., Montanari, A., and Nguyen, P. A mean field view of the landscape of two-layers neural networks. In Proceedings of the National Academy of Sciences (2018), vol. 115, pp. E7665-E7671. -
  45. [55][55] Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research 19 , 1 (2018), 2822-2878. -
  46. [56][56] Yehudai, G., and Shamir, O. On the power and limitations of random features for understanding neural networks. arXiv preprint arXiv:1904.00687 (2019). - · arXiv
  47. [57][57] Yin, D., Ramchandran, K., and Bartlett, P. Rademacher complexity for adversarially robust generalization. arXiv preprint arXiv:1810.11914 (2018). - · arXiv
  48. [58][58] Yu, Y., Wang, T., and Samworth, R. J. A useful variant of the davis-kahan theorem for statisticians. Biometrika 102 , 2 (2014), 315-323. -
  49. [59][59] Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 (2016). - · arXiv
  50. [60][60] Zhang, H., Yu, D., Chen, W., and Liu, T.-Y. Training over-parameterized deep resnet is almost as easy as training a two-layer network. arXiv preprint arXiv:1903.07120 (2019). - · arXiv
  51. [61][61] Zou, D., Cao, Y., Zhou, D., and Gu, Q. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888 (2018). · arXiv

Cited by

Sorted by citations

Metadata

Authors
Oymak, S., Fabian, Z., Li, M., & Soltanolkotabi, M.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1906.05392
arXiv
1906.05392
OpenAlex
W2949960976
Cited by
44
References
1
Citations by year
2025: 5 · 2024: 1 · 2023: 2 · 2022: 2 · 2021: 14 · 2020: 14 · 2019: 6
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Domain Adaptation and Few-Shot Learning
Keywords
neural network generalization, singular values, label noise, early stopping, label alignment, 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