mlsanityData to 7 Oct 2026

Lower Bounds on the Generalization Error of Nonlinear Learning Models

arXiv 2103.14723 ↗First posted 26 Mar 2021stat.ML cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

We study in this paper lower bounds for the generalization error of models derived from multi-layer neural networks, in the regime where the size of the layers is commensurate with the number of samples in the training data. We show that unbiased estimators have unacceptable performance for such nonlinear networks in this regime. We derive explicit generalization lower bounds for general biased estimators, in the cases of linear regression and of two-layered networks. In the linear case the bound is asymptotically tight. In the nonlinear case, we provide a comparison of our bounds with an empirical study of the stochastic gradient descent algorithm. The analysis uses elements from the theory of large random matrices.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 22 of its 58 references that are in the map. First posted on arXiv 26 Mar 2021.

Builds on

22 of 58 references.

References · 22

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  3. 2014Deep Learning in Neural Networks: An Overviewcited by 765
  4. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  5. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
  6. 2017Exploring Generalization in Deep Learningcited by 595
  7. 2019Benign Overfitting in Linear Regressioncited by 544
  8. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  9. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  10. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  11. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  12. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
10 more
  1. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  2. 2019Two models of double descent for weak featurescited by 194
  3. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  4. 2019Linearized two-layers neural networks in high dimensioncited by 155
  5. 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 146
  6. 2019Harmless interpolation of noisy data in regressioncited by 121
  7. 2017Fisher-Rao Metric, Geometry, and Complexity of Neural Networkscited by 99
  8. 2018Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approachcited by 89
  9. 2017A Random Matrix Approach to Neural Networkscited by 80
  10. 2020Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networkscited by 76

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 1; 2023: 0; 2024: 1; 2025: 1; 2026: 1.

6 papers.

  1. 2021Separation of Scales and a Thermodynamic Description of Feature Learning in Some CNNscited by 53
  2. 2021Analytic Insights into Structure and Rank of Neural Network Hessian Mapscited by 52
  3. 2022Homogenization of SGD in high-dimensions: Exact dynamics and generalization propertiescited by 26
  4. 2024A Differential Geometric View and Explainability of GNN on Evolving Graphscited by 4
  5. 2025Path Regularization: A Near-Complete and Optimal Nonasymptotic Generalization Theory for Multilayer Neural Networks and Double Descent Phenomenoncited by 0
  6. 2026When Stronger Triggers Backfire: A High-Dimensional Theory of Backdoor Attackscited by 0