# The Sample Complexity of One-Hidden-Layer Neural Networks

arXiv: https://arxiv.org/abs/2202.06233 · HTML: https://mlsanity.com/paper/2202.06233/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Generalization bounds for deep convolutional neural networks](https://mlsanity.com/paper/1905.12600/) (2019)
- [Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin](https://mlsanity.com/paper/1910.04284/) (2019)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors](https://mlsanity.com/paper/1912.04265/) (2019)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [On Tighter Generalization Bound for Deep Neural Networks: CNNs, ResNets, and Beyond](https://mlsanity.com/paper/1806.05159/) (2018)
- [How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?](https://mlsanity.com/paper/1805.07883/) (2018)
- [Generalization Bounds for Neural Networks via Approximate Description Length](https://mlsanity.com/paper/1910.05697/) (2019)
- [Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networks](https://mlsanity.com/paper/1911.05059/) (2019)

## Built on by (most cited first, 10 of 10)

- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [A PAC-Bayesian Generalization Bound for Equivariant Networks](https://mlsanity.com/paper/2210.13150/) (2022)
- [Generalization Bound and New Algorithm for Clean-Label Backdoor Attack](https://mlsanity.com/paper/2406.00588/) (2024)
- [Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks](https://mlsanity.com/paper/2404.18769/) (2024)
- [Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNs](https://mlsanity.com/paper/2403.15707/) (2024)
- [On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation](https://mlsanity.com/paper/2211.09634/) (2022)
- [Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks](https://mlsanity.com/paper/2305.16475/) (2023)
- [Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization](https://mlsanity.com/paper/2412.04274/) (2024)
- [Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Ability](https://mlsanity.com/paper/2503.04111/) (2025)

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