This research, published in late 2017, addresses one of the most persistent "holy grails" in machine learning: establishing a rigorous theoretical foundation for the success of Deep Learning (DL). While practitioners have seen DL models achieve state-of-the-art results in computer vision and natural language processing, theorists have struggled to explain whether these models are truly "learning" generalizable patterns or simply performing high-dimensional memorization.
The Generalization Gap
A central tension exists between achieving low training error (empirical risk) and ensuring performance on unseen data. Massive models can easily fit random noise, leading to the suspicion that they might be "brute-force memorizers." Statistical Learning Theory (SLT), pioneered by Vapnik, provides a framework for generalization bounds, but calculating these for complex, multi-layer Convolutional Neural Networks (CNNs) is notoriously difficult. This paper seeks to bridge that gap by quantifying the complexity, or "bias," of specific DL architectures.
Methodology: Estimating the Shattering Coefficient
The authors introduce a practical method to measure the Shattering coefficient $\mathcal{N}(\mathcal{F}, n)$, which represents the number of distinct ways an algorithm can classify $n$ points. Since exact calculation for deep networks is analytically impossible, they propose a numerical estimator (Algorithm 1).
By simulating a single neuron through the generation of random hyperplanes in $\mathbb{R}$-dimensional space, they count the unique classification patterns produced for various sample sizes. Their findings indicate that the shattering coefficient of a single neuron follows a second-order polynomial ($an^2 + bn + c$).
To model entire networks, the authors treat the total complexity as the product of the shattering coefficients of individual neurons across all convolutional layers. This compositional approach allows them to estimate the complexity of architectures like AlexNet and VGG16.
Convergence and Data Requirements
Using Vapnik’s Generalization Bound, the authors calculate the "divergence factor"—the gap between training error and real-world error. This analysis determines how many samples $n$ are required for a model to provide a theoretical guarantee of learning.
Key Insights
- Complexity Explosion: AlexNet’s shattering coefficient is estimated at $O(n^{2752})$, while VGG16 reaches $O(n^{8960})$, highlighting the immense flexibility of these models.
- Data Volume Thresholds: For AlexNet to achieve a strong theoretical guarantee, it requires approximately 4.1 million training examples. This explains why DL required the "Big Data" era (and datasets like ImageNet) to move beyond empirical luck to theoretical stability.
- MNIST vs. ImageNet: On the MNIST dataset (70k images), the theoretical guarantee for AlexNet is weak. High accuracy on such small datasets suggests reliance on empirical risk minimization rather than rock-solid generalization guarantees.
Results and Implications
The authors calculated a divergence factor ($\epsilon$) of approximately $0.00076$ for AlexNet on ImageNet. This implies a 95% certainty that the real-world error is within 0.07% of the training error. Interestingly, despite VGG16 using smaller $3 \times 3$ filters to reduce complexity, the sheer volume of neurons results in a higher overall shattering coefficient than AlexNet.
Ultimately, the paper demonstrates that training error alone is insufficient for evaluating models; a model with a lower shattering coefficient is theoretically superior due to its tighter generalization bounds. While the current estimator serves as a lower bound and focuses primarily on convolutional layers, it provides a vital step toward a formal theory of Deep Learning capacity and optimization.
Summary updated