Non-Vacuous Generalization Bounds for Neural Networks

This direction is merged into another direction: vacuous generalization bounds. Its last version stays readable and citable here.

Version 1 of 139 papers39 conceptsfrozen 2026-10-04

The central paradox of modern machine learning is that our most successful models—massive neural networks with millions of parameters—should, according to classical theory, be failing miserably. Traditional statistical learning theory suggests that a model with more parameters than data points should simply memorize the training set and fail to generalize to new examples. Yet, in practice, these models generalize remarkably well.

When theorists try to prove why this happens using standard tools like VC-dimension or Rademacher complexity, they often run into the "vacuous bound" problem. A generalization bound is a mathematical guarantee that the test error won't exceed the training error by more than a certain amount. However, as Behnam Neyshabur and Nati Srebro observed in Exploring Generalization in Deep Learning, these bounds often produce values greater than 1.0. Telling an engineer that their model's error is "guaranteed to be less than 150%" is mathematically true but practically useless.

A growing body of research is dedicated to finding "non-vacuous" bounds—guarantees that are tight enough to actually track and predict real-world performance.

The PAC-Bayes Framework

The most promising tool for creating these tight guarantees is PAC-Bayes theory. Unlike classical methods that look at a single "best" hypothesis, PAC-Bayes looks at a distribution over hypotheses.

The intuition is simple: if you have a large "volume" of models that all perform well on your training data, it is highly likely that the average model in that group will perform well on unseen data. Arnaud Doucet and colleagues demonstrate in Wide stochastic networks: Gaussian limit and PAC-Bayesian training that by treating neural network weights as random variables, we can directly optimize these bounds to achieve both better accuracy and rigorous performance guarantees.

Building Tighter Bounds with Data-Dependent Priors

The "tightness" of a PAC-Bayes bound depends heavily on the "prior"—our initial guess about which models are good before seeing the data. If the prior is too broad, the bound becomes loose (vacuous).

To fix this, researchers like Omar Rivasplata and Csaba Szepesvari have proposed using instance-dependent priors in PAC-Bayes bounds for stable algorithms with instance-dependent priors. By combining PAC-Bayes with algorithmic stability—the idea that a small change in the training data shouldn't wildly change the model—they can build priors that are informed by the data distribution itself without "cheating" the math. This results in bounds that actually mean something in the real world.

Compression and Effective Dimensionality

Another way to explain why huge models generalize is through the lens of compression. Even if a network has millions of parameters, it might only be using a tiny fraction of them to actually solve the task.

  • Structural Sparsity: Tomer Galanti and Tomaso Poggio show in Norm-based Generalization Bounds for Sparse Neural Networks that the specific architecture of a network (like the sparsity in CNNs) acts as a natural constraint that keeps the "effective" complexity low.
  • Sloppy Data: Jialin Mao and Pratik Chaudhari argue in Does the Data Induce Capacity Control in Deep Learning? that real-world data is "sloppy"—most dimensions are noise, and only a few are informative. They found that the internal geometry of deep networks inherits this sloppiness, meaning their "effective dimensionality" is often less than 0.5% of their actual parameter count.
  • Explicit Compression: Algorithms like Pick-to-Learn (P2L), introduced by Dario Paccagnan in The Pick-to-Learn Algorithm, treat the learning process itself as a compression scheme. By finding the smallest subset of data needed to represent the model, they can calculate extremely tight bounds without needing a separate test set.

From Theory to Engineering Guarantees

The shift toward non-vacuous bounds isn't just a theoretical exercise; it's an engineering necessity for high-stakes applications.

In robotics, Maxwell Goldstein uses these tools in PAC-Bayes Control to synthesize controllers that are provably safe in novel environments. Similarly, Paul Viallard and Emilie Morvant apply these frameworks to adversarial robustness in A PAC-Bayes Analysis of Adversarial Robustness, moving away from "worst-case" scenarios that lead to vacuous results and toward "averaged" risks that provide actionable security guarantees.

By moving beyond the "crisis of confidence" in classical bounds, this research direction is finally providing the mathematical language needed to explain—and certify—the success of modern machine learning.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_vacuous_generalization_bounds_for_ne_e1413244,
  title = {Non-Vacuous Generalization Bounds for Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-vacuous-generalization-bounds-for-neural-networks/rdr_e14132443b2d4ddd84c448ead6555de2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_vacuous_generalization_bounds_for_ne_e1413244_v1,
  title = {Non-Vacuous Generalization Bounds for Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-vacuous-generalization-bounds-for-neural-networks/rdr_e14132443b2d4ddd84c448ead6555de2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}