Providing theoretical learning guarantees to Deep Learning Networks

Rodrigo Fernandes de Mello, Martha Dais Ferreira, Moacir Antonelli PontiarXiv 2017 · arXiv

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$).

Shattering coefficient growth across different dimensions (R2 to R20) as a function of sample size.

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.

Convergence curves showing the relationship between sample size and the theoretical generalization bound.

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

BibTeX
@misc{mello2017providing,
  author = {Rodrigo Fernandes de Mello and Martha Dais Ferreira and Moacir Antonelli Ponti},
  title = {{Providing theoretical learning guarantees to Deep Learning Networks}},
  year = {2017},
  eprint = {1711.10292},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.10292},
}
Figure