# Fast rates in Bayesian online learning with approximate posteriors

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 47 references that are in the map.
- First posted on arXiv 26 Aug 2026.

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

- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [The Bayesian Learning Rule](https://mlsanity.com/paper/2107.04562/) (2021)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [Concentration of tempered posteriors and of their variational approximations](https://mlsanity.com/paper/1706.09293/) (2017)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [On Sparse variational methods and the Kullback-Leibler divergence between stochastic processes](https://mlsanity.com/paper/1504.07027/) (2015)
- [Convergence of Sparse Variational Inference in Gaussian Processes Regression](https://mlsanity.com/paper/2008.00323/) (2020)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Streaming Variational Bayes](https://mlsanity.com/paper/1307.6769/) (2013)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Convergence Rates of Variational Posterior Distributions](https://mlsanity.com/paper/1712.02519/) (2017)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [Streaming Sparse Gaussian Process Approximations](https://mlsanity.com/paper/1705.07131/) (2017)
- [Provable Bayesian Inference via Particle Mirror Descent](https://mlsanity.com/paper/1506.03101/) (2015)
- [Optimal low-rank approximations of Bayesian linear inverse problems](https://mlsanity.com/paper/1407.3463/) (2014)
- [Non-exponentially weighted aggregation: regret bounds for unbounded loss functions](https://mlsanity.com/paper/2009.03017/) (2020)
- [A Generalization Bound for Online Variational Inference](https://mlsanity.com/paper/1904.03920/) (2019)
- [Adaptive variational Bayes: Optimality, computation and applications](https://mlsanity.com/paper/2109.03204/) (2021)
- [Bayesian Online Natural Gradient (BONG)](https://mlsanity.com/paper/2405.19681/) (2024)
- [Particle-based Online Bayesian Sampling](https://mlsanity.com/paper/2302.14796/) (2023)
- [Adaptive sparse variational approximations for Gaussian process regression](https://mlsanity.com/paper/2504.03321/) (2025)
- [Online Sampling from Log-Concave Distributions](https://mlsanity.com/paper/1902.08179/) (2019)
- [Bayesian online learning in the one-pass regime: Frequentist validity and uncertainty quantification](https://mlsanity.com/paper/2604.27442/) (2026)
- [Adaptive Bayesian Online Learning via Expert Aggregation](https://mlsanity.com/paper/2607.20239/) (2026)

## Abstract (arXiv)

Exact Bayes prediction enjoys fast predictive regret guarantees, but exact posterior updating or representation may be too costly for online use. We study when these statistical guarantees are preserved by computational approximations. We show that the cumulative price of posterior approximation can be governed by the interaction between the contraction radius of the exact Gibbs posterior and the Wasserstein distance between the approximate and exact posteriors. Our general theorem shows that whenever exact Bayes prediction achieves a fast regret bound, any approximate posterior method that tracks the exact posterior with sufficient accuracy inherits the same fast regret, up to an additive term determined by the approximation error. Three online learning examples are developed. For linear models with strongly convex regularized losses, a projected Langevin algorithm yields an approximate posterior that achieves logarithmic regret. For an infinite-dimensional canonical exponential family sequence model over a Sobolev ellipsoid, a prior-preserving truncation method attains the minimax predictive regret rate with sublinear memory and constant update cost per observation. For random-design Gaussian process (GP) regression, a sparse variational posterior with inducing variables achieves the same predictive regret rate as the exact GP, but at substantially lower computational cost.