Derandomizing PAC-Bayesian Theory for Deterministic Models

This direction is split into other directions: stochastic-to-deterministic conversion gap. Its last version stays readable and citable here.

Version 1 of 129 papers42 conceptsfrozen 2026-10-04

PAC-Bayesian theory is one of the most powerful tools in statistical learning theory for providing "non-vacuous" generalization bounds—mathematical guarantees that a model's error on unseen data will be low. However, there is a fundamental mismatch between the theory and its application. PAC-Bayesian bounds are inherently designed for randomized predictors (where we sample a model from a distribution), while modern machine learning relies almost exclusively on deterministic models (where we use a single, fixed set of weights).

To bridge this gap, researchers have developed "derandomization" techniques. These methods allow us to transfer the tight guarantees of stochastic ensembles to the specific, deterministic neural networks and classifiers used in production.

The Stochastic Mismatch

As Tim van Erven explains in PAC-Bayes Mini-tutorial: A Continuous Union Bound, PAC-Bayes can be viewed as a continuous version of the union bound. It measures the complexity of a hypothesis space using the Kullback-Leibler (KL) divergence between a "prior" distribution and a "posterior" distribution learned from data.

The problem arises when we try to apply this to a single deterministic model, like a trained ResNet. In the PAC-Bayesian world, a deterministic model is represented as a "Dirac delta" distribution—a distribution with all its mass on a single point. If we try to calculate the KL divergence between a smooth prior and a Dirac posterior, the value explodes to infinity. This makes the resulting generalization bound "vacuous" (useless), as it essentially predicts the error could be anything.

The Margin as a Bridge

The most common way to solve this is to use the margin of the predictor. The intuition is simple: if a deterministic model classifies a point correctly with a large margin, it should still classify it correctly even if we add a small amount of random noise to its weights.

In On Margins and Derandomisation in PAC-Bayes, Felix Biggs and Benjamin Guedj provide a unified "recipe" for this. By establishing that a large margin provides robustness against weight noise, they show that the deterministic mean of a distribution can be guaranteed to generalize as well as the randomized ensemble itself. This allows for dimension-independent guarantees for linear models and deep ReLU networks.

This same logic applies to ensemble methods like Random Forests. In On Margins and Generalisation for Voting Classifiers, Felix Biggs and colleagues use concentration-of-measure results to relate the risk of a random proxy (sampling one tree) to the actual performance of the deterministic majority vote.

Neural Networks as Expectations

A surprising insight in this field is that many deterministic architectures can be mathematically reframed as the "expected output" of a randomized ensemble. For example, a single-hidden-layer neural network can be viewed as the majority vote of an infinite ensemble of simpler features.

In Non-Vacuous Generalisation Bounds for Shallow Neural Networks, Felix Biggs and Benjamin Guedj leverage this equivalence to derive the first non-vacuous bounds for deterministic shallow networks trained with standard SGD. They show that because the deterministic output is effectively an average, it inherits the stability and generalization properties of the underlying distribution, allowing for error bounds below 1.0 on datasets like MNIST.

Disintegration and Flat Minima

Other researchers have looked for ways to "disintegrate" the bounds entirely, moving away from the need to average over distributions. Paul Viallard and Pascal Germain introduced a framework in A General Framework for the Derandomization of PAC-Bayesian Bounds that uses the Rényi divergence instead of KL. This approach provides certificates for a single set of weights that are more stable to optimize during training.

This direction also explains the empirical success of "flat minima." In A PAC-Bayesian Link Between Generalisation and Flat Minima, Maxime Haddouche and co-authors prove that finding a region where the loss is "flat" (low gradient variance) is theoretically equivalent to having a PAC-Bayesian posterior that is robust to perturbations.

Why Derandomization Matters

Without derandomization, PAC-Bayes remains a beautiful theory for a type of machine learning we rarely use (stochastic predictors). By developing these bridges—whether through margins, optimal transport as suggested by Kohei Miyaguchi in PAC-Bayesian Transportation Bound, or stability analysis—researchers are finally providing the formal performance certificates required for deploying deterministic models in high-stakes production environments.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_derandomizing_pac_bayesian_theory_for_de_db7af4e8,
  title = {Derandomizing PAC-Bayesian Theory for Deterministic Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/derandomizing-pac-bayesian-theory-for-deterministic-models/rdr_db7af4e8267a4e419f0e0b6f685e9bc6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_derandomizing_pac_bayesian_theory_for_de_db7af4e8_v1,
  title = {Derandomizing PAC-Bayesian Theory for Deterministic Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/derandomizing-pac-bayesian-theory-for-deterministic-models/rdr_db7af4e8267a4e419f0e0b6f685e9bc6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}