A unified recipe for deriving (time-uniform) PAC-Bayes bounds

Ben Chugg, Hongjian Wang, Aaditya Ramdas

Abstract

We present a unified framework for deriving PAC-Bayesian generalization bounds. Unlike most previous literature on this topic, our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times, not only for a fixed sample size. Our approach combines four tools in the following order: (a) nonnegative supermartingales or reverse submartingales, (b) the method of mixtures, (c) the Donsker-Varadhan formula (or other convex duality principles), and (d) Ville's inequality. Our main result is a PAC-Bayes theorem which holds for a wide class of discrete stochastic processes. We show how this result implies time-uniform versions of well-known classical PAC-Bayes bounds, such as those of Seeger, McAllester, Maurer, and Catoni, in addition to many recent bounds. We also present several novel bounds. Our framework also enables us to relax traditional assumptions; in particular, we consider nonstationary loss functions and non-i.i.d. data. In sum, we unify the derivation of past bounds and ease the search for future bounds: one may simply check if our supermartingale or submartingale conditions are met and, if so, be guaranteed a (time-uniform) PAC-Bayes bound.

Introduction: The "Fixed-Time" Trap

In machine learning theory, PAC-Bayes bounds provide a powerful mechanism for guaranteeing that a model's empirical risk on training data will generalize to unseen data. However, traditional PAC-Bayes literature has largely been constrained by the "fixed-time" assumption, where the sample size $n$ must be determined before observing any data. If a researcher monitors a bound continuously or stops data collection based on observed performance—a common practice known as "peeking"—the mathematical validity of these classical guarantees collapses.

This work addresses this limitation by introducing a framework for anytime-valid (time-uniform) bounds. These guarantees hold simultaneously across all time steps $t=1, 2, 3, \dots$, allowing for adaptive stopping and continuous monitoring without compromising statistical integrity.

The Unified Recipe

The core contribution of this paper is a four-step "recipe" that systematizes the derivation of PAC-Bayes bounds. By identifying the underlying martingale structures that have been implicitly present in disparate proofs for decades, the authors provide a clear path to time-uniformity.

The unified recipe for deriving time-uniform PAC-Bayes bounds by combining four key mathematical tools.
  1. Identify a Martingale Structure (A): The process must be identified as either a nonnegative forward supermartingale or a reverse submartingale. This choice determines whether the resulting bound is "lossless" when moving from fixed-time to anytime-validity.
  2. The Method of Mixtures (B): A mixture is applied over the parameter space, allowing the bound to hold for any data-dependent distribution $\rho$ (the "posterior").
  3. Change of Measure (C): Using convex duality principles like the Donsker-Varadhan formula, the expectation of the process is related to the Kullback-Leibler (KL) divergence between the prior and posterior distributions.
  4. Ville’s Inequality (D): Finally, Ville’s inequality—a time-uniform generalization of Markov’s inequality—is applied to ensure the bound holds with high probability across all time steps.

Unifying the PAC-Bayes Landscape

One of the most significant impacts of this framework is its ability to recover and extend a vast array of existing literature. The authors demonstrate that classical results from McAllester, Catoni, Maurer, and Seeger are actually specific instances of this unified recipe.

A mapping of classical fixed-time PAC-Bayes results to the anytime-valid corollaries derived in this work.

As shown in the table above, the framework bifurcates into two main categories:

  • Forward Supermartingales: These typically yield bounds that are as tight as their fixed-time counterparts. Because they do not strictly require i.i.d. data, they are particularly useful for non-stationary environments and online learning.
  • Reverse Submartingales: These are used for bounds involving convex functions of risk (like Seeger’s bound). While they require an exchangeability assumption, they can be made anytime-valid through a "stitching" argument, albeit with a minor iterated logarithm penalty.

Key Insights and Future Directions

Beyond unification, the paper introduces novel bounds, including a Bernstein-type anytime bound and guarantees for losses with only bounded second moments. A key takeaway is that for many supermartingale-based bounds, anytime-validity comes "for free"—the bounds are just as tight at any given $n$ as the traditional fixed-time versions.

While the framework significantly relaxes the i.i.d. assumption, challenges remain. Reverse submartingale bounds still rely on exchangeability, and deriving closed-form anytime-valid bounds for losses with only $p$-th moments ($1 < p \le 2$) remains an open problem. Nonetheless, this unified recipe provides a robust foundation for the next generation of generalization theory, moving from static estimates to dynamic, anytime-valid guarantees.

Summary updated

Abstract

We present a unified framework for deriving PAC-Bayesian generalization bounds. Unlike most previous literature on this topic, our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times, not only for a fixed sample size. Our approach combines four tools in the following order: (a) nonnegative supermartingales or reverse submartingales, (b) the method of mixtures, (c) the Donsker-Varadhan formula (or other convex duality principles), and (d) Ville's inequality. Our main result is a PAC-Bayes theorem which holds for a wide class of discrete stochastic processes. We show how this result implies time-uniform versions of well-known classical PAC-Bayes bounds, such as those of Seeger, McAllester, Maurer, and Catoni, in addition to many recent bounds. We also present several novel bounds. Our framework also enables us to relax traditional assumptions; in particular, we consider nonstationary loss functions and non-i.i.d. data. In sum, we unify the derivation of past bounds and ease the search for future bounds: one may simply check if our supermartingale or submartingale conditions are met and, if so, be guaranteed a (time-uniform) PAC-Bayes bound.
BibTeX
@article{chugg2023unified,
  author = {Ben Chugg and Hongjian Wang and Aaditya Ramdas},
  title = {{A unified recipe for deriving (time-uniform) PAC-Bayes bounds}},
  journal = {J. Mach. Learn. Res.},
  year = {2023},
}
Figure