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

arXiv: https://arxiv.org/abs/2302.03421 · HTML: https://mlsanity.com/paper/2302.03421/

## Key facts

- Cited by 25 papers in the map (data through 7 Oct 2026).
- Builds on 24 of its 78 references that are in the map.
- First posted on arXiv 7 Feb 2023.

## Builds on (most cited first, 24 of 24)

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Safe Testing](https://mlsanity.com/paper/1906.07801/) (2019)
- [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020)
- [A Strongly Quasiconvex PAC-Bayesian Bound](https://mlsanity.com/paper/1608.05610/) (2016)
- [Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm](https://mlsanity.com/paper/1503.08329/) (2015)
- [Simpler PAC-Bayesian Bounds for Hostile Data](https://mlsanity.com/paper/1610.07193/) (2016)
- [PAC-Bayes unleashed: generalisation bounds with unbounded losses](https://mlsanity.com/paper/2006.07279/) (2020)
- [Admissible anytime-valid sequential inference must rely on nonnegative martingales](https://mlsanity.com/paper/2009.03167/) (2020)
- [Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks](https://mlsanity.com/paper/1905.10259/) (2019)
- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [A Limitation of the PAC-Bayes Framework](https://mlsanity.com/paper/2006.13508/) (2020)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [Integral Probability Metrics PAC-Bayes Bounds](https://mlsanity.com/paper/2207.00614/) (2022)
- [Martingale Methods for Sequential Estimation of Convex Functionals and Divergences](https://mlsanity.com/paper/2103.09267/) (2021)
- [Catoni-style confidence sequences for heavy-tailed mean estimation](https://mlsanity.com/paper/2202.01250/) (2022)
- [Huber-Robust Confidence Sequences](https://mlsanity.com/paper/2301.09573/) (2023)
- [PAC-Bayes Iterated Logarithm Bounds for Martingale Mixtures](https://mlsanity.com/paper/1506.06573/) (2015)

## Built on by (most cited first, 25 of 25)

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models](https://mlsanity.com/paper/2407.18158/) (2024)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [A PAC-Bayesian Link Between Generalisation and Flat Minima](https://mlsanity.com/paper/2402.08508/) (2024)
- [Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures](https://mlsanity.com/paper/2309.14298/) (2023)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)
- [Anytime-valid, Bayes-assisted, Prediction-Powered Inference](https://mlsanity.com/paper/2505.18000/) (2025)
- [Time-Uniform Confidence Spheres for Means of Random Vectors](https://mlsanity.com/paper/2311.08168/) (2023)
- [Self-Evolving Agents with Anytime-Valid Certificates](https://mlsanity.com/paper/2607.00871/) (2026)
- [Compute-Optimal LLMs Provably Generalize Better With Scale](https://mlsanity.com/paper/2504.15208/) (2025)
- [Adaptive Principal Component Regression with Applications to Panel Data](https://mlsanity.com/paper/2307.01357/) (2023)
- [Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss](https://mlsanity.com/paper/2405.14681/) (2024)
- [The extended Ville's inequality for nonintegrable nonnegative supermartingales](https://mlsanity.com/paper/2304.01163/) (2023)
- [Data-dependent and Oracle Bounds on Forgetting in Continual Learning](https://mlsanity.com/paper/2406.09370/) (2024)
- [Federated Learning with Nonvacuous Generalisation Bounds](https://mlsanity.com/paper/2310.11203/) (2023)
- [Tighter Generalisation Bounds via Interpolation](https://mlsanity.com/paper/2402.05101/) (2024)
- [A variational approach to dimension-free self-normalized concentration](https://mlsanity.com/paper/2508.06483/) (2025)
- [Are Flat Minima an Illusion?](https://mlsanity.com/paper/2605.05209/) (2026)
- [A note on generalization bounds for losses with finite moments](https://mlsanity.com/paper/2403.16681/) (2024)
- [Sequential Off-Policy Learning with Logarithmic Smoothing](https://mlsanity.com/paper/2506.10664/) (2025)
- [PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification](https://mlsanity.com/paper/2509.06600/) (2025)

## Abstract (arXiv)

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.