Generalization bounds for deep learning

Guillermo Valle Pérez, Ard A. LouisarXiv 2020 · arXiv

Introduction

The remarkable success of deep learning presents a fundamental challenge to classical statistical learning theory. Traditional frameworks often link a model's "capacity" to its number of parameters—suggesting that overparameterized models, which possess far more parameters than training examples, should simply memorize the data and fail to generalize. However, modern neural networks defy this expectation, learning general patterns even when they have the capacity to fit random noise.

Existing theoretical tools, such as VC dimension or Rademacher complexity, frequently produce "vacuous" bounds. In practice, these bounds might guarantee an error rate of over 100%, providing no actionable insight for researchers. Furthermore, they often fail to capture qualitative trends observed in the field, such as the performance gains associated with increased depth or larger datasets. This paper addresses these discrepancies by establishing a rigorous framework of seven "desiderata" for generalization bounds and introducing a novel marginal-likelihood PAC-Bayesian bound derived from a function-space perspective.

The Seven Desiderata for Generalization Theory

To evaluate the utility of theoretical bounds, the authors propose seven criteria (D.1–D.7) that a "good" theory should satisfy:

  1. Data Complexity (D.1): The bound must scale correctly with the inherent difficulty of the dataset.
  2. Training Set Size (D.2): It should scale correctly with the number of examples ($m$).
  3. Architectural Sensitivity (D.3): It must capture performance differences between architectures (e.g., CNNs vs. Fully Connected Networks).
  4. Optimization Sensitivity (D.4): It should reflect differences caused by the choice of algorithm (e.g., SGD vs. Adam).
  5. Non-Vacuity (D.5): The bound must provide values significantly below 100% error to be meaningful.
  6. Computational Efficiency (D.6): It should be efficiently computable.
  7. Theoretical Rigor (D.7): It must be based on proven mathematical theorems.

Methodology: A Function-Space Approach

The core contribution of this work is the marginal-likelihood PAC-Bayesian bound. While traditional PAC-Bayesian bounds typically operate in the parameter space (the weights of the network), this approach shifts the focus to the function space.

The authors argue that parameter space is inherently redundant; many distinct weight configurations can represent the same mathematical function. By bounding error in function space, the theory avoids the "overparameterization trap" that renders other bounds vacuous. To implement this, the authors leverage the Neural Network Gaussian Process (NNGP) to approximate the marginal likelihood—the probability of the data given the model architecture. By using Expectation Propagation (EP) to compute this likelihood, they derive a bound that is directly proportional to the Bayesian evidence.

A significant theoretical insight is the connection to power-law learning curves. Empirical evidence suggests that deep learning error often follows a power law ($error \propto m^{-\alpha}$). The authors prove that their marginal-likelihood bound is asymptotically optimal (up to a constant) if the learning curve follows such a power law, providing a strong theoretical link between Bayesian evidence and generalization.

Empirical Evaluation

The framework was tested through over 1,000 experiments using binarized versions of standard computer vision benchmarks, including MNIST, Fashion-MNIST, EMNIST, KMNIST, and CIFAR-10. To test the bound's sensitivity to data complexity (D.1), the authors employed label corruption, systematically flipping labels to increase the difficulty of the learning task.

Key Results

The proposed bound successfully met several of the established desiderata:

  • Non-Vacuity: Unlike many predecessors, this bound is non-vacuous across a wide range of tasks, offering tight quantitative guides to actual performance.
  • Trend Tracking: The bound correctly predicted that error increases with label corruption and decreases with training set size according to the correct exponent.
  • Architectural Insights: In tests across 19 different architectures, including ResNets and DenseNets, the bound showed a strong correlation with true test error. It effectively "ranked" architectures, correctly identifying that certain choices (like average pooling over max pooling) lead to better generalization.

Limitations and Future Work

While the marginal-likelihood PAC-Bayesian bound represents a significant step forward, several challenges remain. Currently, the bound does not fully satisfy D.4 (Optimization Sensitivity), as it assumes a Bayesian posterior and does not account for the specific nuances of optimizers like SGD or hyperparameters like batch size.

Additionally, the computational cost of calculating the NNGP kernel and marginal likelihood is $O(m^3)$, posing scalability issues for massive datasets like ImageNet. Future research directions include extending the derivation from binary classification to multi-class problems, incorporating finite-width corrections to the NNGP approximation, and improving computational efficiency to handle larger-scale applications.

Summary updated

Abstract

Generalization in deep learning has been the topic of much recent theoretical and empirical research. Here we introduce desiderata for techniques that predict generalization errors for deep learning models in supervised learning. Such predictions should 1) scale correctly with data complexity; 2) scale correctly with training set size; 3) capture differences between architectures; 4) capture differences between optimization algorithms; 5) be quantitatively not too far from the true error (in particular, be non-vacuous); 6) be efficiently computable; and 7) be rigorous. We focus on generalization error upper bounds, and introduce a categorisation of bounds depending on assumptions on the algorithm and data. We review a wide range of existing approaches, from classical VC dimension to recent PAC-Bayesian bounds, commenting on how well they perform against the desiderata. We next use a function-based picture to derive a marginal-likelihood PAC-Bayesian bound. This bound is, by one definition, optimal up to a multiplicative constant in the asymptotic limit of large training sets, as long as the learning curve follows a power law, which is typically found in practice for deep learning problems. Extensive empirical analysis demonstrates that our marginal-likelihood PAC-Bayes bound fulfills desiderata 1-3 and 5. The results for 6 and 7 are promising, but not yet fully conclusive, while only desideratum 4 is currently beyond the scope of our bound. Finally, we comment on why this function-based bound performs significantly better than current parameter-based PAC-Bayes bounds.
BibTeX
@misc{perez2020generalization,
  author = {Guillermo Valle Pérez and Ard A. Louis},
  title = {{Generalization bounds for deep learning}},
  year = {2020},
  eprint = {2012.04115},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.04115},
}
Figure