One of the most profound mysteries in modern machine learning is why massive neural networks generalize so well. Classical statistical learning theory suggests that a model with more parameters than data points should overfit catastrophically, memorizing the training data instead of learning underlying patterns. Yet, in practice, overparameterized networks achieve remarkable accuracy on unseen data.
When theorists attempt to prove mathematical guarantees for these models using traditional frameworks (like Vapnik-Chervonenkis dimension or Rademacher complexity), they run into a wall. The resulting mathematical limits are frequently vacuous—meaning the calculated upper bound on the test error exceeds 100% (or even the total number of training samples). As noted by Yuan Cao et al. in Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks, this lack of tightness prevents classical frameworks from offering practical guidance or explaining empirical success.
To bridge this gap, a major research direction focuses on deriving non-vacuous generalization bounds—theoretical guarantees that are numerically tight enough to be meaningful in the real world.
The Problem with Worst-Case Complexity
To understand why traditional bounds fail, consider how they measure a model's capacity. Classical bounds are typically uniform: they calculate the worst-case complexity across the entire hypothesis space of all possible parameter configurations.
If a network has 100 million parameters, the space of possible functions it can represent is unimaginably vast. Traditional theory assumes the learning algorithm could pick the absolute worst function that happens to fit the training data. Therefore, the complexity term explodes.
However, as Behnam Neyshabur et al. demonstrated in Exploring Generalization in Deep Learning, while these worst-case bounds can sometimes track relative performance trends across different architectures, their absolute numerical values are practically useless for predicting real-world error rates. Real optimization algorithms do not pick a worst-case function; they navigate a highly specific path.
The PAC-Bayesian Shift: Bounding Distributions, Not Models
The breakthrough strategy for creating non-vacuous bounds shifts the question from "How complex is the entire model space?" to "How much did our optimization algorithm narrow down our choices?" This is the core intuition behind PAC-Bayesian theory.
Instead of bounding a single, deterministic neural network, PAC-Bayes analyzes a distribution over networks.
- Before seeing the data, we define a prior distribution $P$ over the weights.
- After training on the data, the learning algorithm returns a posterior distribution $Q$ centered around the learned weights.
The complexity of the model is then measured by the Kullback-Leibler (KL) divergence between $Q$ and $P$, denoted as $KL(Q \parallel P)$. The KL divergence quantifies how much information the algorithm gained from the training data. If the posterior distribution doesn't deviate wildly from the prior, the complexity term remains small, yielding a tight bound.
As John Langford et al. showed in PAC-Bayes & Margins, this framing allows for data-dependent guarantees that adapt to the specific problem. Felix Biggs et al. in On Margins and Derandomisation in PAC-Bayes emphasize that because these bounds are "non-uniform," the mathematical guarantee adapts dynamically to the specific model learned, bypassing the global parameter-counting trap.
Harnessing Algorithmic Stability and Flat Minima
How do we ensure that the posterior distribution $Q$ stays close to the prior $P$ in a high-dimensional space? The answer lies in the geometry of the loss landscape and the nature of Stochastic Gradient Descent (SGD).
SGD has an implicit bias toward finding flat minima—broad valleys in the loss landscape where perturbing the network's weights has little to no effect on its performance. Vaishnavh Nagarajan leveraged this property in Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience, proving that this "noise-resilience" allows researchers to construct a wide posterior distribution $Q$ around the trained weights. Because the valley is flat, $Q$ can have a large variance without sacrificing accuracy. A wider posterior distribution overlaps more significantly with a simple prior, keeping $KL(Q \parallel P)$ remarkably low and eliminating the exponential dependence on network depth.
Loss Landscape
▲
│ █ █
│ █ █ ◄── Sharp Minimum (Poor Generalization, Narrow Posterior)
│ █ █
│ ──█──────█──
│ █ █ █▀▀▀▀▀▀▀▀▀▀█
│█ █ █ █ ◄── Flat Minimum (Good Generalization, Wide Posterior)
└────────────────────────────────────────► Weights
This connection means that certain optimization algorithms are implicitly minimizing generalization bounds. For example, Gintare Karolina Dziugaite et al. demonstrated in Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors that Entropy-SGD—an algorithm designed to force models into flat minima—is mathematically optimizing the prior of a PAC-Bayes bound.
By combining PAC-Bayes with algorithmic stability (the property that a model's output changes minimally when a single training instance is modified), the authors and others, such as Omar Rivasplata et al. in PAC-Bayes bounds for stable algorithms with instance-dependent priors, have successfully computed valid, non-vacuous bounds. In fact, Felix Biggs delivered the first strictly non-vacuous generalization guarantees for shallow networks trained with standard SGD on datasets like MNIST in Non-Vacuous Generalisation Bounds for Shallow Neural Networks.
Learning as Compression
A complementary perspective for building tight bounds views machine learning through the lens of information theory and compression. If a massive network can be compressed into a much simpler representation without losing its predictive power, its true operational capacity is far lower than its parameter count implies.
The authors of The Pick-to-Learn Algorithm: Empowering Compression for Tight Generalization Bounds and Improved Post-training Performance, Dario Paccagnan et al., formalized this by designing a meta-algorithm that explicitly transforms a model into a compression scheme. By bounding the generalization error based on the size of the compressed representation rather than the original hypothesis space, they achieved exceptionally tight theoretical limits.
This compression dynamic also helps explain complex training phenomena like grokking—where a network suddenly transitions from perfect training accuracy to perfect test accuracy long after over-fitting seemed inevitable. As Branton DeMoss et al. showed in The Complexity Dynamics of Grokking, this sudden leap in generalization is marked by a sharp phase transition where the model sheds its complex, uncompressed memorization of noise in favor of simple, highly compressed, and elegant algorithmic patterns.