Fast rates in Bayesian online learning with approximate posteriors

Technical Summary: Fast Rates in Bayesian Online Learning with Approximate Posteriors

Problem Statement
Bayesian online prediction offers strong statistical guarantees, specifically fast predictive regret bounds (e.g., logarithmic in parametric models and minimax optimal in nonparametric ones), derived from the telescoping structure of cumulative log-loss. However, these guarantees traditionally assume the exact posterior distribution is available at every round. In modern applications, exact posterior updating is often computationally intractable, necessitating approximate inference methods (e.g., variational inference, sampling algorithms, or truncation).

The central problem addressed is whether the fast statistical regret rates of exact Bayesian prediction survive when the posterior is replaced by a computationally feasible approximation. Existing literature often provides only slow regret bounds ($O(\sqrt{T})$) for approximate methods or focuses on the asymptotic fidelity of the terminal posterior, failing to account for the cumulative error introduced by approximation at every intermediate step of the online sequence.

Methodology and Theoretical Framework
The paper establishes a general theoretical framework to decompose the predictive regret of an approximate posterior into the regret of the exact Gibbs posterior and an additive penalty determined by the approximation error.

1. Statistical Setup: The author considers a filtered probability space where, at each round $t$, an approximate posterior $Q_t$ is generated by a computational algorithm, while $\Pi_t$ denotes the exact Gibbs posterior. The goal is to bound the expected cumulative predictive regret of the sequence $(Q_t)$.
2. Key Quantities:
   • $\epsilon_t$: The statistical contraction radius of the exact posterior, defined as $E[W_2^2(\Pi_t, \delta_{\theta^\star})]$, where $\theta^\star$ is a stochastic target.
   • $\alpha_t$: The computational tracking error, defined as $E[W_2^2(Q_t, \Pi_t)]$, measuring the Wasserstein distance between the approximate and exact posteriors.
3. Main Theorem (Predictive Regret under Approximation): The core result (Theorem 2.3) states that under a second-order predictive stability condition (Assumption 2.2), the excess regret of the approximate method is bounded by:
   $$\sum_{t=1}^T (\epsilon_t \alpha_t + \alpha_t^2)$$
   This result relies on the insight that posterior concentration ($\epsilon_t \to 0$) naturally attenuates the impact of approximation errors. Unlike first-order Lipschitz conditions which would require $\alpha_t$ to vanish uniformly, second-order stability allows the cumulative penalty to remain small even if $\alpha_t$ decays at a rate compatible with $\epsilon_t$.
4. Sufficient Conditions: The paper derives conditions on the loss function (smoothness, bounded gradients, and conditional stationarity) that ensure the second-order stability assumption holds.

Three Application Regimes
The framework is instantiated in three distinct computational regimes, demonstrating that fast rates can be preserved with specific algorithmic choices:

1. Finite-Dimensional Linear Models (Strongly Convex):

   • Context: Regularized losses with strongly convex regularizers and bounded covariates.
   • Method: A projected Moreau–Yosida Langevin algorithm (MYULA) is used to sample from the constrained Gibbs posterior.
   • Result: The exact posterior contracts at rate $O(t^{-1/2})$. The algorithm achieves a squared Wasserstein tracking error of $O(t^{-1})$. Consequently, the cumulative approximation penalty is $O(\log T)$, preserving the logarithmic regret of the exact method.

2. Infinite-Dimensional Exponential Family Sequences:

   • Context: Sequence models over a Sobolev ellipsoid where the exact posterior is a product of conjugate coordinates.
   • Method: A prior-preserving truncation method. The algorithm updates only the first $m$ coordinates (sufficient statistics) and retains the original prior for the unresolved tail, rather than replacing the model with a sequence of truncated priors.
   • Result: By choosing the truncation level $m$ at the effective dimension scale ($m \asymp T^{1/\zeta}$), the method achieves the minimax predictive regret rate with sublinear memory ($O(m)$) and constant update cost per observation.

3. Random-Design Gaussian Process (GP) Regression:

   • Context: Nonparametric regression with a GP prior.
   • Method: An online sparse variational GP using population-spectral inducing variables.
   • Result: The paper shows that a sparse variational posterior with $J \asymp T^{d/(d+2s)}$ inducing variables achieves the same nonparametric regret rate as the exact GP. Crucially, the analysis demonstrates that vanishing variational KL divergence is not necessary; rather, the relevant metric is the displacement of the approximation relative to the shrinking geometry of the exact posterior (controlled by the operator norm of the posterior covariance).

Key Contributions

1. General Comparison Theorem: The paper provides the first general result converting posterior approximation error into a cumulative predictive regret penalty while retaining fast rates. It separates the statistical radius ($\epsilon_t$) from the computational distance ($\alpha_t$).
2. Second-Order Stability: It introduces a second-order predictive stability condition, showing that posterior contraction reduces sensitivity to computational perturbations, allowing for "coarser" approximations as time progresses.
3. Algorithmic Realizations: It constructs three implementable online learners (Langevin-based, truncation-based, and sparse variational) that achieve optimal or near-optimal regret rates with significantly reduced computational or memory costs compared to exact inference.
4. Computational-Statistical Trade-off: The work formalizes the principle that computational accuracy need only be sufficient to keep the induced predictive perturbation below the statistical resolution of the exact posterior.

Significance and Claims
The paper claims to resolve the question of whether fast rates in Bayesian online prediction survive computation. It argues that computational approximations need not be uniformly negligible; instead, their accuracy must simply improve at a rate compatible with the statistical contraction of the exact posterior.

The author emphasizes that their framework makes the required computational accuracy explicit, exposing where model-specific work is unavoidable. They note that their results turn posterior approximation from an external numerical concern into an explicit component of sequential regret analysis.

Limitations
The paper acknowledges several limitations and directions for future work:

• The finite-dimensional result assumes compact support, smooth loss, and strong convexity, with a conservative cold-start mixing schedule.
• The sequence model assumes known smoothness, a horizon-dependent rank, and tractable one-dimensional predictive normalizers.
• The sparse GP result assumes known population spectral features, fixed kernel hyperparameters, and a known horizon.
• Extending these direct comparisons to adaptive ranks, moving inducing sets, or online hyperparameter learning requires new arguments.