# On Size-Independent Sample Complexity of ReLU Networks

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 16 references that are in the map.
- First posted on arXiv 3 Jun 2023.

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

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (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)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation](https://mlsanity.com/paper/1905.03684/) (2019)
- [Generalization bounds for deep convolutional neural networks](https://mlsanity.com/paper/1905.12600/) (2019)
- [On Generalization Bounds of a Family of Recurrent Neural Networks](https://mlsanity.com/paper/1910.12947/) (2019)

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

- [Improved Sample Complexity Bounds for Diffusion Model Training](https://mlsanity.com/paper/2311.13745/) (2023)
- [Size Lowerbounds for Deep Operator Networks](https://mlsanity.com/paper/2308.06338/) (2023)
- [Public-data Assisted Private Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2403.03856/) (2024)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [DFNN: A Deep Fr'echet Neural Network Framework for Learning Metric-Space-Valued Responses](https://mlsanity.com/paper/2510.17072/) (2025)
- [Dimension-invariant uniform consistency of the empirical spatial distribution function and its associated spatial depth estimator](https://mlsanity.com/paper/2607.16092/) (2026)

## Abstract (arXiv)

We study the sample complexity of learning ReLU neural networks from the point of view of generalization. Given norm constraints on the weight matrices, a common approach is to estimate the Rademacher complexity of the associated function class. Previously Golowich-Rakhlin-Shamir (2020) obtained a bound independent of the network size (scaling with a product of Frobenius norms) except for a factor of the square-root depth. We give a refinement which often has no explicit depth-dependence at all.