# Size-Independent Sample Complexity of Neural Networks

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

## Key facts

- Cited by 290 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2017.

## Built on by (most cited first, 30 of 290)

- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Combined Scaling for Zero-shot Transfer Learning](https://mlsanity.com/paper/2111.10050/) (2021)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [On the Role of Neural Collapse in Transfer Learning](https://mlsanity.com/paper/2112.15121/) (2021)
- [Neural Collapse: A Review on Modelling Principles and Generalization](https://mlsanity.com/paper/2206.04041/) (2022)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction](https://mlsanity.com/paper/2105.10446/) (2021)
- [When Do Extended Physics-Informed Neural Networks (XPINNs) Improve Generalization?](https://mlsanity.com/paper/2109.09444/) (2021)
- [Causally motivated Shortcut Removal Using Auxiliary Labels](https://mlsanity.com/paper/2105.06422/) (2021)
- [Towards Label-free Scene Understanding by Vision Foundation Models](https://mlsanity.com/paper/2306.03899/) (2023)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Understanding the role of importance weighting for deep learning](https://mlsanity.com/paper/2103.15209/) (2021)
- [Learning to Augment Distributions for Out-of-Distribution Detection](https://mlsanity.com/paper/2311.01796/) (2023)
- [Learning with Multiclass AUC: Theory and Algorithms](https://mlsanity.com/paper/2107.13171/) (2021)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [Reverse Engineering Self-Supervised Learning](https://mlsanity.com/paper/2305.15614/) (2023)
- [Combining Observational and Randomized Data for Estimating Heterogeneous Treatment Effects](https://mlsanity.com/paper/2202.12891/) (2022)
- [Sequence Length Independent Norm-Based Generalization Bounds for Transformers](https://mlsanity.com/paper/2310.13088/) (2023)
- [Defending Against Image Corruptions Through Adversarial Augmentations](https://mlsanity.com/paper/2104.01086/) (2021)
- [A Primer on Bayesian Neural Networks: Review and Debates](https://mlsanity.com/paper/2309.16314/) (2023)
- [Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel](https://mlsanity.com/paper/2107.12723/) (2021)
- [On the statistical complexity of quantum circuits](https://mlsanity.com/paper/2101.06154/) (2021)
- [Measuring Generalization with Optimal Transport](https://mlsanity.com/paper/2106.03314/) (2021)
- [On the Generalization Mystery in Deep Learning](https://mlsanity.com/paper/2203.10036/) (2022)
- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [An Information-Theoretic Perspective on Variance-Invariance-Covariance Regularization](https://mlsanity.com/paper/2303.00633/) (2023)
- [Nonparametric regression using over-parameterized shallow ReLU neural networks](https://mlsanity.com/paper/2306.08321/) (2023)
- [Formalizing Generalization and Robustness of Neural Networks to Weight Perturbations](https://mlsanity.com/paper/2103.02200/) (2021)

## Abstract (arXiv)

We study the sample complexity of learning neural networks, by providing new bounds on their Rademacher complexity assuming norm constraints on the parameter matrix of each layer. Compared to previous work, these complexity bounds have improved dependence on the network depth, and under some additional assumptions, are fully independent of the network size (both depth and width). These results are derived using some novel techniques, which may be of independent interest.