mlsanityData to 7 Oct 2026

The Sample Complexity of One-Hidden-Layer Neural Networks

arXiv 2202.06233 ↗First posted 13 Feb 2022cs.LG stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

We study norm-based uniform convergence bounds for neural networks, aiming at a tight understanding of how these are affected by the architecture and type of norm constraint, for the simple class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We begin by proving that in general, controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees (independent of the network width), while a stronger Frobenius norm control is sufficient, extending and improving on previous work. Motivated by the proof constructions, we identify and analyze two important settings where (perhaps surprisingly) a mere spectral norm control turns out to be sufficient: First, when the network's activation functions are sufficiently smooth (with the result extending to deeper networks); and second, for certain types of convolutional networks. In the latter setting, we study how the sample complexity is additionally affected by parameters such as the amount of overlap between patches and the overall number of patches.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 20 of its 33 references that are in the map. First posted on arXiv 13 Feb 2022.

Builds on

20 of 33 references.

References · 20

  1. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  2. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  3. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  4. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  5. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  6. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  7. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  8. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  9. 2020Directional convergence and alignment in deep learningcited by 172
  10. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  11. 2019Generalization bounds for deep convolutional neural networkscited by 58
  12. 2019Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margincited by 56
8 more
  1. 2020A law of robustness for two-layers neural networkscited by 54
  2. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  3. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  4. 2021Generalization bounds via distillationcited by 33
  5. 2018On Tighter Generalization Bound for Deep Neural Networks: CNNs, ResNets, and Beyondcited by 24
  6. 2018How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?cited by 19
  7. 2019Generalization Bounds for Neural Networks via Approximate Description Lengthcited by 15
  8. 2019Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networkscited by 4

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 2; 2024: 4; 2025: 1.

10 papers.

  1. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 84
  2. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  3. 2022A PAC-Bayesian Generalization Bound for Equivariant Networkscited by 17
  4. 2024Generalization Bound and New Algorithm for Clean-Label Backdoor Attackcited by 11
  5. 2024Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networkscited by 8
  6. 2024Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNscited by 5
  7. 2022On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activationcited by 4
  8. 2023Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networkscited by 4
  9. 2024Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimizationcited by 1
  10. 2025Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Abilitycited by 0