PAC-Bayesian Generalization Bounds for Deterministic Classifiers

19 concepts11 papers1 proposal

Imagine you want a mathematical guarantee that your machine learning model will perform well on unseen test data. To get this, you might turn to PAC-Bayesian theory, one of the most powerful frameworks for deriving tight, data-dependent generalization bounds.

But if you try to apply standard PAC-Bayes theory to a standard neural network or a Support Vector Machine (SVM), you will immediately hit a fundamental mathematical mismatch. PAC-Bayes theory naturally computes guarantees for stochastic classifiers—distributions over hypotheses (often called Gibbs classifiers) that randomly sample a new set of weights every time they make a prediction. In practice, however, we almost exclusively deploy deterministic classifiers—a single, fixed weight vector or a concrete voting ensemble.

This discrepancy creates what theorists call the stochastic-to-deterministic conversion gap. Bridging this gap is essential for making generalization theory relevant to real-world deployment.

The Cost of Derandomization

Why can't we just plug a deterministic model into a PAC-Bayesian bound? A single deterministic model can be thought of as a "Dirac delta" distribution—a probability distribution concentrated entirely on one point. Unfortunately, PAC-Bayes bounds depend heavily on the Kullback-Leibler (KL) divergence between the learned distribution and a prior distribution. If your learned distribution is a single point, this KL divergence often becomes infinitely large, rendering the bound useless (or "vacuous").

To circumvent this, early statistical learning theory relied on "derandomization" techniques. As explained by Langford et al. (2002) and Shawe-Taylor et al. (2009), these techniques use mathematical inequalities to relate the risk of a deterministic majority-vote classifier to the average risk of its randomized components.

However, this conversion comes at a steep price. Jin et al. (2012) point out that converting performance bounds from stochastic to deterministic voting classifiers invariably introduces a loose multiplicative penalty factor greater than one. Marchand et al. (2004) and Biggs et al. (2022) emphasize that this lack of tight, direct bounds leaves a persistent gap between theory and practice.

The issue is further compounded when analyzing optimization algorithms. As Kaban et al. (2023) demonstrate, PAC-Bayes bounds for randomized algorithms can be looser by a factor of $\sqrt{n}$ (where $n$ is the sample size) compared to the stability bounds available for deterministic algorithms, creating a theoretical inefficiency that contradicts empirical reality.

To fix this, researchers have developed three main intuitions to bridge the gap: viewing single models as ensembles, leveraging the geometry of flat minima, and directly "disintegrating" the bounds.

Strategy 1: Deterministic Models as Ensembles

One elegant way to close the gap is to find an exact mathematical equivalence between a single deterministic architecture and a randomized ensemble.

Consider a shallow neural network. Instead of treating it as a single point in parameter space, we can mathematically interpret its deterministic output as the expected output—or the majority vote—of a randomized ensemble of predictors.

By exploiting this equivalence, Biggs et al. (2022) successfully bypassed the lossy derandomization step. This allowed the authors to derive the first "non-vacuous" (meaningful, less than 1.0) generalization bounds for deterministic shallow neural networks trained with standard Stochastic Gradient Descent (SGD) on datasets like MNIST, without requiring any stochasticity during inference.

Strategy 2: Flat Minima and Noise Resilience

A second, highly popular intuition connects the stochastic-to-deterministic gap to the geometry of the loss landscape.

Suppose your trained, deterministic model sits in a flat minimum—a region where perturbing the weights slightly does not significantly increase the training loss. If the loss landscape is flat, then a cloud of noisy parameters centered around your model will perform almost identically to the single deterministic point at the center.

Loss
 ^
 |       _..---.._          <- Flat Minimum: The average loss of the 
 |     .'         '.           noisy neighborhood (stochastic) matches
 |    /     *       \          the loss of the center point (deterministic).
 |   |  (stochastic) |
 +---'-------^-------'-----> Parameters
       deterministic

Nagarajan et al. (2019) formalized this by linking a deterministic network's performance to the average performance of its noisy parameter neighbors. By proving that this "noise-resilience" generalizes from training data to test data, the authors derived deterministic bounds that avoid an exponential dependence on network depth.

To make this framework practical, Tsuzuku et al. (2020) used PAC-Bayesian analysis to develop a scale-invariant definition of flatness, ensuring that simple weight rescaling cannot artificially break the guarantee. More recently, Haddouche et al. (2024) provided a rigorous mathematical link between generalization and flatness by incorporating gradient variance terms via Poincaré inequalities. However, the authors note that establishing fast generalization rates for single-point weight estimates remains an active open question.

Strategy 3: Disintegration of Bounds

Instead of trying to force a deterministic model to look like a distribution or an ensemble, can we rewrite PAC-Bayes theory to apply to individual hypotheses directly? This approach is known as disintegration.

The core idea behind disintegration is to mathematically "unpack" the expectation over the distribution found in standard PAC-Bayes theorems. As developed by Viallard et al. (2024), this framework allows for the direct derivation of generalization guarantees on individual, single hypotheses rather than averaged risks.

By eliminating the complex and loose derandomization steps entirely, disintegration provides a cleaner, more practical path to evaluating the true generalization capacity of deep networks exactly as they are deployed.

Key Foundational Work

PAC-Bayes & Margins (2002) — contributed 1 concept elements to this direction.
PAC-Bayes Learning of Conjunctions and Classification of Gene-Expression Data (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_to_deterministic_conversion_g_ecdd7d86,
  title = {stochastic-to-deterministic conversion gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-to-deterministic-conversion-gap/rdr_ecdd7d8616084f7e89840aebffb4d5eb},
  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_stochastic_to_deterministic_conversion_g_ecdd7d86_v1,
  title = {stochastic-to-deterministic conversion gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-to-deterministic-conversion-gap/rdr_ecdd7d8616084f7e89840aebffb4d5eb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake