Fast rates in Bayesian online learning with approximate posteriors

Bayesian online learning promises uncertainty-aware prediction on data streams, but its performance hinges on inferential choices, including learning rates, prior distributions and variational families, which are usually fixed before seeing the stream. We address this by treating Bayesian update rules as experts and aggregating the Bayesian experts according to sequential predictive losses. We prove that the resulting aggregate competes with the best expert in hindsight at an aggregation cost determined by how each expert's per-round performance is evaluated. We instantiate the framework in online conformal inference and Gaussian process regression. The conformal inference application yields a smoothed Bayesian counterpart of adaptive conformal inference with long-run randomized coverage, while the Gaussian process application gives an oracle inequality in cumulative predictive Kullback-Leibler risk and adaptation to unknown Hölder smoothness up to logarithmic factors. Experiments show that the aggregate tracks strong experts without oracle expert selection.

We derive explicit non-asymptotic PAC-Bayes generalization bounds for Gibbs posteriors, that is, data-dependent distributions over model parameters obtained by exponentially tilting a prior with the empirical risk. Unlike classical worst-case complexity bounds based on uniform laws of large numbers, which require explicit control of the model space in terms of metric entropy (integrals), our analysis yields posterior-averaged risk bounds that can be applied to overparameterized models and adapt to the data structure and the intrinsic model complexity. The bound involves a marginal-type integral over the parameter space, which we analyze using tools from singular learning theory to obtain explicit and practically meaningful characterizations of the posterior risk. Applications to low-rank matrix completion and ReLU neural network regression and classification show that the resulting bounds are analytically tractable and substantially tighter than classical complexity-based bounds. Our results highlight the potential of PAC-Bayes analysis for precise finite-sample generalization guarantees in modern overparameterized and singular models.

Online learning in non-stationary streams is often formulated as tracking a point estimate, although many applications require predicting the full data-generating distribution. We study online distributional prediction under drift and bounded causal adversarial corruption. Candidate laws are represented by variable-size latent cluster configurations that induce predictive distributions. A Gibbs quasi-posterior over configurations yields an online predictor by posterior averaging and can be sampled using reversible-jump MCMC. The method uses no stream likelihood but specifies a kernel-mixture predictive family. We evaluate cumulative Wasserstein-1 regret against the time-varying true law and study periodic restart, sliding-window, and exponential-discounting memory against full history. The bounds separate PAC-Bayesian complexity, corruption-sensitive posterior perturbation, and drift through $A_T^{\mathrm{OT}}=\sum_{t=2}^T W_2^2(p_{t-1}^*,p_t^*)$. Under bounded support, latent quadratic growth, predictive-map regularity, and localized-comparator assumptions, restart has sublinear high-probability cumulative regret when $0\le a<1$, $q,ζ,b<1$, $0\leγ<β<1$, and $0<h<(1-a)/2$. Here $a,q,ζ,b$ control the polynomial growth of drift, predictive-family approximation error, off-order posterior mass, and oracle-order switch cost; $λ_s\asymp s^{-β}$ and $H\asymp T^h$. Corruptions satisfy the segment-local condition $Λ_{r,s}=O(s^γ)$, so a sublinear global budget alone is insufficient. The regime requires oracle-informed tuning, $\varepsilon_T=o(1)$, and fixed confidence or $\log(1/δ_0)=T^{o(1)}$. Sliding-window and discounted guarantees additionally require the stated localized-memory condition.