# Online PAC-Bayes Learning

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 66 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [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)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Adding Gradient Noise Improves Learning for Very Deep Networks](https://mlsanity.com/paper/1511.06807/) (2015)
- [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)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [PAC-Bayesian Theory Meets Bayesian Inference](https://mlsanity.com/paper/1605.08636/) (2016)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [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)
- [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)
- [Spiking Neural Networks and Online Learning: An Overview and Perspectives](https://mlsanity.com/paper/1908.08019/) (2019)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [PAC-Bayes with Backprop](https://mlsanity.com/paper/1908.07380/) (2019)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [Generalization Bounds via Convex Analysis](https://mlsanity.com/paper/2202.04985/) (2022)
- [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015)
- [Learning PAC-Bayes Priors for Probabilistic Neural Networks](https://mlsanity.com/paper/2109.10304/) (2021)
- [A Generalization Bound for Online Variational Inference](https://mlsanity.com/paper/1904.03920/) (2019)
- [PAC-Bayes under potentially heavy tails](https://mlsanity.com/paper/1905.07900/) (2019)
- [Still no free lunches: the price to pay for tighter PAC-Bayes bounds](https://mlsanity.com/paper/1910.04460/) (2019)
- [Progress in Self-Certified Neural Networks](https://mlsanity.com/paper/2111.07737/) (2021)
- [Stochastic Online Convex Optimization. Application to probabilistic time series forecasting](https://mlsanity.com/paper/2102.00729/) (2021)

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

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theory](https://mlsanity.com/paper/2310.04935/) (2023)
- [PAC-Bayesian Generalization Bounds for Adversarial Generative Models](https://mlsanity.com/paper/2302.08942/) (2023)
- [A PAC-Bayesian Link Between Generalisation and Flat Minima](https://mlsanity.com/paper/2402.08508/) (2024)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures](https://mlsanity.com/paper/2309.14298/) (2023)
- [Forgetting, Ignorance or Myopia: Revisiting Key Challenges in Online Continual Learning](https://mlsanity.com/paper/2409.19245/) (2024)
- [Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!](https://mlsanity.com/paper/2306.05862/) (2023)
- [Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation](https://mlsanity.com/paper/2304.07048/) (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)
- [Length independent generalization bounds for deep SSM architectures via Rademacher contraction and stability constraints](https://mlsanity.com/paper/2405.20278/) (2024)
- [Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier](https://mlsanity.com/paper/2509.25979/) (2025)
- [Adaptive Bayesian Online Learning via Expert Aggregation](https://mlsanity.com/paper/2607.20239/) (2026)
- [Streaming PAC-Bayes Gaussian process regression with a performance guarantee for online decision making](https://mlsanity.com/paper/2210.08486/) (2022)
- [Sequential Off-Policy Learning with Logarithmic Smoothing](https://mlsanity.com/paper/2506.10664/) (2025)
- [Block-Sample MAC-Bayes Generalization Bounds](https://mlsanity.com/paper/2602.12605/) (2026)
- [Personalized Federated Learning for Gradient Alignment](https://mlsanity.com/paper/2605.02143/) (2026)
- [Information-Theoretic Generalization Bounds for Sequential Decision Making](https://mlsanity.com/paper/2605.12190/) (2026)
- [Certified Policy Optimisation for Nested Causal Bandits via PAC-Bayes Risk](https://mlsanity.com/paper/2605.29788/) (2026)

## Abstract (arXiv)

Most PAC-Bayesian bounds hold in the batch learning setting where data is collected at once, prior to inference or prediction. This somewhat departs from many contemporary learning problems where data streams are collected and the algorithms must dynamically adjust. We prove new PAC-Bayesian bounds in this online learning framework, leveraging an updated definition of regret, and we revisit classical PAC-Bayesian results with a batch-to-online conversion, extending their remit to the case of dependent data. Our results hold for bounded losses, potentially non-convex, paving the way to promising developments in online learning.