Approximate Bayesian updates can preserve the fast prediction rates of exact updating, according to a theoretical arXiv preprint, when their error is matched to the way the exact posterior narrows over time. In the paper’s framework, cumulative predictive regret is the running gap in prediction performance that an online method accumulates against its benchmark. The main comparison theorem bounds approximate regret by exact-posterior regret plus an accumulated penalty tied to posterior contraction, approximation-tracking error and a quadratic tracking term.
The work develops three theoretical online-learning examples: strongly convex regularized linear models; an infinite-dimensional exponential-family sequence model over a Sobolev ellipsoid, a mathematical smoothness class; and random-design Gaussian-process regression.
A relative target for approximation
Rather than setting one universal numerical accuracy target, the paper compares approximation with the exact posterior’s contraction radius. It measures the remaining mismatch with Wasserstein tracking error, a distance between probability distributions, and accumulates terms proportional to the contraction radius times tracking error and to the square of tracking error. The authors frame this as a design principle: computational accuracy should follow posterior contraction and predictive geometry.
Three model regimes
In the regularized linear setting, the exact Gibbs posterior—the full update used as the benchmark—has expected squared-Wasserstein contraction of order 1/t and expected cumulative regret of order log T + 1. Online MYULA, a sampling-based approximate update, reaches the same orders for posterior tracking and cumulative regret under the stated assumptions.
The sequence example uses a prior-preserving truncation: it updates only the first m coordinates while retaining the original prior on the unresolved tail. It therefore needs O(m) memory and O(1) state-update work per observation.
The exact sequence-model posterior contracts at order t^(-(ζ-1)/ζ) and has cumulative regret of order T^(1/ζ), with ζ = a + 2s + 1. The exponent depends on the model’s smoothness and prior scaling. The truncated method adds a tail-dependent tracking term, but choosing m at least of order T^(1/ζ) gives regret of the same order. A matching lower bound of order T^(1/ζ) makes that rate minimax within the specified sequence-model class.
In the random-design Gaussian-process example, exact GP prediction has contraction of order t^(-2s/(d+2s)) and cumulative regret of order T^(d/(d+2s)) under the stated Sobolev-regression and GP-prior assumptions. The sparse variational version uses fixed inducing variables—the approximation’s fixed summary variables—and computes its sparse posterior at O(J^2) cost per round.
At the paper’s inducing-rank threshold, J at least of order T^(d/(d+2s)), sparse-GP tracking has the same order as exact-GP contraction and regret retains the exact-GP order. The reported total sparse cost is O(TJ^2), compared with O(T^3) for exact GP. The guarantee does not require the Kullback–Leibler (KL) divergence, a separate measure of mismatch between distributions, to vanish.
The assumptions set the boundary
No empirical trials or benchmark datasets are reported; the paper’s evidence consists of theoretical upper and lower bounds and complexity statements under explicit assumptions. Those assumptions are substantial: the linear case uses compact support, smooth loss and regularization that supplies strong convexity; the sequence case assumes known smoothness, a horizon-dependent rank, coordinatewise conjugacy and tractable one-dimensional predictive normalizers; and the sparse-GP case assumes known population spectral features, fixed kernel hyperparameters and inducing variables, polynomial spectral decay and a known horizon.
Whether the framework extends to moving or point-inducing schemes, adaptive ranks or online hyperparameter learning remains open. The analysis also leaves open whether warm starts or stochastic-gradient samplers can reduce the conservative finite-dimensional schedule, or whether the methods can work without known smoothness and horizon information.
Paper data and sources
Original title: Fast rates in Bayesian online learning with approximate posteriors
Authors: Ilsang Ohn
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text