mlsanityData to 7 Oct 2026

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

arXiv 2302.03421 ↗First posted 7 Feb 2023stat.ML cs.IT cs.LGcited by 25

Not on the map. Why?

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.

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

24 of 78 references.

References · 24

  1. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  2. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  3. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  4. 2020Estimating means of bounded random variables by bettingcited by 164
  5. 2022Game-theoretic statistics and safe anytime-valid inferencecited by 145
  6. 2019A Primer on PAC-Bayesian Learningcited by 130
  7. 2015On the properties of variational approximations of Gibbs posteriorscited by 121
  8. 2020Tighter risk certificates for neural networkscited by 112
  9. 2019Safe Testingcited by 98
  10. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  11. 2016A Strongly Quasiconvex PAC-Bayesian Boundcited by 54
  12. 2015Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithmcited by 50
12 more
  1. 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 45
  2. 2020PAC-Bayes unleashed: generalisation bounds with unbounded lossescited by 43
  3. 2020Admissible anytime-valid sequential inference must rely on nonnegative martingalescited by 43
  4. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  5. 2022Anytime-valid off-policy inference for contextual banditscited by 37
  6. 2020A Limitation of the PAC-Bayes Frameworkcited by 24
  7. 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
  8. 2022Integral Probability Metrics PAC-Bayes Boundscited by 19
  9. 2021Martingale Methods for Sequential Estimation of Convex Functionals and Divergencescited by 17
  10. 2022Catoni-style confidence sequences for heavy-tailed mean estimationcited by 17
  11. 2023Huber-Robust Confidence Sequencescited by 7
  12. 2015PAC-Bayes Iterated Logarithm Bounds for Martingale Mixturescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 8; 2024: 10; 2025: 5; 2026: 2.

25 papers.

Sort:

  1. 2023MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splittingcited by 33
  2. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
  3. 2024Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Modelscited by 25
  4. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  5. 2024A PAC-Bayesian Link Between Generalisation and Flat Minimacited by 13
  6. 2023Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixturescited by 12
  7. 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 11
  8. 2024PAC-Bayes-Chernoff bounds for unbounded lossescited by 9
  9. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  10. 2024Generalization bounds for mixing processes via delayed online-to-PAC conversionscited by 7
  11. 2025Anytime-valid, Bayes-assisted, Prediction-Powered Inferencecited by 7
  12. 2023Time-Uniform Confidence Spheres for Means of Random Vectorscited by 6
13 more
  1. 2026Self-Evolving Agents with Anytime-Valid Certificatescited by 6
  2. 2025Compute-Optimal LLMs Provably Generalize Better With Scalecited by 5
  3. 2023Adaptive Principal Component Regression with Applications to Panel Datacited by 4
  4. 2024Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Losscited by 4
  5. 2023The extended Ville's inequality for nonintegrable nonnegative supermartingalescited by 3
  6. 2024Data-dependent and Oracle Bounds on Forgetting in Continual Learningcited by 3
  7. 2023Federated Learning with Nonvacuous Generalisation Boundscited by 2
  8. 2024Tighter Generalisation Bounds via Interpolationcited by 2
  9. 2025A variational approach to dimension-free self-normalized concentrationcited by 2
  10. 2026Are Flat Minima an Illusion?cited by 1
  11. 2024A note on generalization bounds for losses with finite momentscited by 0
  12. 2025Sequential Off-Policy Learning with Logarithmic Smoothingcited by 0
  13. 2025PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classificationcited by 0