# A Theoretical-Empirical Approach to Estimating Sample Complexity of DNNs arXiv: https://arxiv.org/abs/2105.01867 · HTML: https://mlsanity.com/paper/2105.01867/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Builds on 28 of its 66 references that are in the map. - First posted on arXiv 5 May 2021. ## Builds on (most cited first, 28 of 28) - [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015) - [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018) - [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014) - [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014) - [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014) - [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014) - [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015) - [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016) - [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017) - [Speech Recognition with Deep Recurrent Neural Networks](https://mlsanity.com/paper/1303.5778/) (2013) - [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017) - [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017) - [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017) - [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019) - [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014) - [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) - [Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation](https://mlsanity.com/paper/1404.0736/) (2014) - [Intrinsic dimension of data representations in deep neural networks](https://mlsanity.com/paper/1905.12784/) (2019) - [Estimating the intrinsic dimension of datasets by a minimal neighborhood information](https://mlsanity.com/paper/1803.06992/) (2018) - [Joint Unsupervised Learning of Deep Representations and Image Clusters](https://mlsanity.com/paper/1604.03628/) (2016) - [State-of-the-art Speech Recognition With Sequence-to-Sequence Models](https://mlsanity.com/paper/1712.01769/) (2017) - [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018) - [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018) - [Learning Representations for Neural Network-Based Classification Using the Information Bottleneck Principle](https://mlsanity.com/paper/1802.09766/) (2018) - [Dimensionality compression and expansion in Deep Neural Networks](https://mlsanity.com/paper/1906.00443/) (2019) - [Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm](https://mlsanity.com/paper/1905.10843/) (2019) - [Learning Curves for Deep Neural Networks: A Gaussian Field Theory Perspective](https://mlsanity.com/paper/1906.05301/) (2019) ## Built on by (most cited first, 6 of 6) - [Scaling Laws Under the Microscope: Predicting Transformer Performance from Small Scale Experiments](https://mlsanity.com/paper/2202.06387/) (2022) - [How Much More Data Do I Need? Estimating Requirements for Downstream Tasks](https://mlsanity.com/paper/2207.01725/) (2022) - [Optimizing Data Collection for Machine Learning](https://mlsanity.com/paper/2210.01234/) (2022) - [Data Scaling Laws for End-to-End Autonomous Driving](https://mlsanity.com/paper/2504.04338/) (2025) - [Delegated Classification](https://mlsanity.com/paper/2306.11475/) (2023) - [A Step Toward Interpretability: Smearing the Likelihood](https://mlsanity.com/paper/2501.07643/) (2025) ## Abstract (arXiv) This paper focuses on understanding how the generalization error scales with the amount of the training data for deep neural networks (DNNs). Existing techniques in statistical learning require computation of capacity measures, such as VC dimension, to provably bound this error. It is however unclear how to extend these measures to DNNs and therefore the existing analyses are applicable to simple neural networks, which are not used in practice, e.g., linear or shallow ones or otherwise multi-layer perceptrons. Moreover, many theoretical error bounds are not empirically verifiable. We derive estimates of the generalization error that hold for deep networks and do not rely on unattainable capacity measures. The enabling technique in our approach hinges on two major assumptions: i) the network achieves zero training error, ii) the probability of making an error on a test point is proportional to the distance between this point and its nearest training point in the feature space and at a certain maximal distance (that we call radius) it saturates. Based on these assumptions we estimate the generalization error of DNNs. The obtained estimate scales as O(1/(δ N1/d)), where N is the size of the training data and is parameterized by two quantities, the effective dimensionality of the data as perceived by the network (d) and the aforementioned radius (δ), both of which we find empirically. We show that our estimates match with the experimentally obtained behavior of the error on multiple learning tasks using benchmark data-sets and realistic models. Estimating training data requirements is essential for deployment of safety critical applications such as autonomous driving etc. Furthermore, collecting and annotating training data requires a huge amount of financial, computational and human resources. Our empirical estimates will help to efficiently allocate resources.