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