PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast rates in Bayesian online learning with approximate posteriors

Ilsang Ohn

arXiv:2608.25706v1stat.MLcs.LG

TL;DR

The paper studies whether fast predictive-regret guarantees of exact Bayes survive computationally approximate posterior updating and representation. It develops a contraction-aware comparison theorem based on Wasserstein tracking error, then demonstrates rate preservation with Langevin, truncation, and sparse-GP methods. The results cover logarithmic regret in strongly convex linear models and minimax predictive-regret rates in sequence and GP settings, subject to explicit assumptions.

  • Problem

    Exact Bayesian prediction can be computationally costly online, while existing regret analyses generally do not separately quantify the cumulative effect of approximate posterior computation.

  • Method

    The paper compares approximate and exact Bayesian predictors using the exact posterior’s contraction radius and their Wasserstein tracking distance under second-order predictive stability.

  • Results

    The framework preserves exact-Bayes rates: projected Langevin achieves logarithmic regret, prior-preserving truncation achieves minimax sequence-model regret with sublinear memory, and sparse variational GP achieves exact-GP predictive-regret order.

  • Takeaways & Limitations

    Approximate posterior accuracy need only improve at a rate compatible with posterior contraction, rather than being uniformly negligible or having vanishing variational KL divergence.

  • Takeaways & Limitations

    The results rely on setting-specific assumptions, including compact support and strong convexity, known smoothness and horizon-dependent rank, or known spectral features, hyperparameters, inducing variables, and horizon.

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether fast predictive-regret guarantees survive computationally approximate Bayesian updating and answers affirmatively through a contraction-aware comparison framework. Three implementations preserve exact-Bayes rates across parametric and nonparametric settings while reducing computational burdens.

  • Motivation: Fast-rate analyses of exact Bayesian or exponential-weighting predictors generally assume the predictive distribution is available at every round, leaving computational approximation error unpriced.Terminal contraction of an approximate posterior does not by itself control cumulative predictive loss along the online posterior path.
  • General framework: The framework bounds approximate-posterior regret by exact Gibbs regret plus a penalty governed by contraction radius ε_t and Wasserstein tracking error α_t.Under second-order predictive stability, the cumulative approximation cost scales with ε_tα_t rather than α_t alone.
  • Finite-dimensional models: O(log T) cumulative approximation penalty preserves logarithmic exact-Gibbs regret for projected Moreau–Yosida Langevin updates in strongly convex finite-dimensional models.The exact posterior contracts at O(t−1/2), while the squared Wasserstein tracking error is of order t−1 on the compact parameter space.
  • Infinite-dimensional sequence models: The prior-preserving sequence-model truncation attains minimax cumulative predictive regret with sublinear memory and constant state-update work per observation.It updates only the first m coordinates while retaining the original prior on the unresolved tail, with m chosen at the effective-dimension scale.
  • Gaussian-process regression: An effective-dimension sparse variational GP representation preserves the nonparametric predictive-regret order of exact Bayes when J exceeds a sublinear threshold in T.The approximate posterior uses the first J population covariance-operator eigenfunctions as interdomain inducing variables and can be updated recursively.
  • Cross-application perspective: The three applications use incomplete sampling, infinite-representation truncation, and variational sparse compression, but share the same contraction-and-distance analysis.The paper also connects these methods to related literatures on streaming approximate inference, sequential posterior accuracy, and constrained log-concave sampling.

2 Main results

The paper separates exact-posterior statistical contraction from computational tracking error and shows that second-order predictive stability makes approximation progressively less costly as the exact posterior contracts.

  • Exact Bayes benchmark: Exact Bayesian predictive losses telescope through Gibbs recursion, enabling cumulative regret analysis via a single marginal-likelihood expression.This telescoping identity underlies fast regret bounds for exact prediction.
  • Approximation penalty: Second-order predictive stability couples approximation error with posterior contraction, whereas first-order Lipschitz control would accumulate the approximation distances directly.Under second-order stability, concentration reduces sensitivity to computational error; the residual cost is quadratic in α_t.
  • General framework: The framework compares an exact Gibbs posterior Π_t with a computationally feasible approximate posterior Q_t using contraction radius ε_t and Wasserstein distance α_t.The resulting regret bound decomposes approximate regret into exact-posterior regret plus an approximation penalty.
  • Verification: The stability condition can be verified from smoothness, exponential envelopes, and conditional stationarity of the underlying loss.The sufficient conditions apply to probability measures supported on a compact convex parameter space.

3 Moreau–Yosida Langevin online Bayes

For strongly convex finite-dimensional Gibbs models, the paper uses projected Moreau–Yosida Langevin sampling to track the exact posterior accurately enough to preserve logarithmic regret.

  • Statistical-computational threshold: Strong convexity yields exact-posterior contraction ε_t ≍ t^-1/2, so approximation accuracy α_t ≲ t^-1/2 gives an O(log T) cumulative penalty.The sampling analysis targets precisely this computational threshold.
  • Algorithm: Projected Moreau–Yosida unadjusted Langevin sampling approximates each constrained Gibbs posterior on the compact parameter space.The method smooths the hard constraint, runs Langevin transitions, and projects the final state back onto the parameter space.
  • Regret guarantee: The resulting online MYULA learner preserves logarithmic cumulative regret under the stated predictable-design, loss, prior, and stationarity assumptions.The guarantee is established through the statistical Gibbs-posterior result and the approximation analysis.

4 Truncated online posteriors for exponential family sequences

For an infinite-dimensional exponential-family sequence model, the paper replaces costly full posterior representation with prior-preserving coordinate truncation while retaining minimax predictive regret.

  • Computational regime: Exact posterior representation can require linear worst-case memory, so the approximation updates only the first m coordinates and preserves the prior on the unresolved tail.This is computational truncation of one fixed infinite-dimensional Bayesian model, not replacement by changing truncated-prior models.
  • Statistical analysis: The exact posterior and truncation analyses provide explicit contraction, regret, and truncation terms over a Sobolev ellipsoid.The sequence model uses coordinatewise conjugate posteriors under the stated smoothness and prior assumptions.
  • Implementation: Algorithm 2 uses O(m) memory and O(1) state-update work per observation, apart from a one-dimensional conjugate normalizer ratio.It stores and updates sufficient statistics only for coordinates j ≤ m.
  • Rate and trade-off: Choosing m at the effective-dimension scale yields minimax cumulative predictive regret with sublinear memory.The balanced choice reduces expected memory from T^(1/a) to T^(1/(a+2s+1)).

5 Online sparse variational Gaussian processes

The GP section develops predictive-stability guarantees for exact and sparse variational posteriors, then applies them to an online population-spectral inducing-variable algorithm. With a sublinear inducing budget, the sparse method preserves the exact GP's fast regret while reducing computation.

  • 5.1 Gaussian process regression: Gaussian-process predictive stability relates predictive KL risk to Wasserstein displacement between GP laws, with an additional remainder for unbounded Gaussian responses.Theorem 5.1 supplies the stability result used because the responses are unbounded.
  • 5.1 Gaussian process regression: Under bounded basis functions, Sobolev truth, and suitably scaled polynomial-decay GP priors, the exact GP posterior satisfies fast regret guarantees.The assumptions include λj ≍ j−1−2s/d.
  • 5.1 Gaussian process regression: The analysis asks whether sparse variational compression preserves the predictive performance of the full GP posterior under random-design Gaussian regression.The sparse posterior uses the first J population covariance eigenfunctions as fixed interdomain inducing variables and admits recursive finite-dimensional updates.
  • 5.2 Sparse variational Gaussian processes: O(J^2) computation per round contrasts with O(t^2) exact-posterior updates and O(T^3) exact total cost through horizon T.The sparse method's total cost is evaluated using the oracle inducing-variable choice J ≍ T^d/(d+2s).
  • 5.2 Sparse variational Gaussian processes: J ≳ T^d/(d+2s) inducing variables provide the sparse variational GP approximation accuracy required by the theorem.The inducing variables are fixed across the horizon and the posterior can be updated recursively using finite-dimensional sufficient statistics.
  • 5.2 Sparse variational Gaussian processes: The sparse variational GP with J ≳ T^d/(d+2s) achieves fast cumulative predictive regret, even though its KL divergence from the exact posterior need not vanish.Shrinking exact-posterior covariance converts variational discrepancy into smaller Wasserstein displacement as concentration increases.

6 Conclusion

The conclusion presents a comparison principle in which approximation penalties depend on exact-posterior contraction and computational tracking error. It proposes matching computational accuracy to statistical resolution, while identifying assumptions that limit the current applications.

  • 6 Conclusion: The main theorem decomposes computed-predictor regret into an exact Gibbs benchmark and an approximation penalty governed by contraction radius εt and Wasserstein tracking error αt.The penalty quantifies the interaction between statistical concentration and posterior approximation.
  • 6 Conclusion: Posterior approximation need not be uniformly negligible; its accuracy only needs to improve at a rate compatible with exact-posterior contraction.Statistical concentration reduces sensitivity to computational error.
  • 6 Conclusion: The proposed design principle is to identify contraction and predictive geometry first, then allocate enough accuracy to keep predictive perturbations below statistical resolution.This makes approximation an explicit component of sequential regret analysis.
  • 6 Conclusion: The finite-dimensional result assumes compact support, smooth loss, and regularization-provided strong convexity, while its cold-start mixing schedule is conservative.Warm starts or stochastic-gradient samplers may reduce computational cost.
  • 6 Conclusion: The sequence and sparse-GP results assume known smoothness or spectral features, fixed hyperparameters and inducing variables, polynomial spectral decay, and a known horizon.Extensions to adaptive ranks, moving inducing sets, or online hyperparameter learning require new tracking arguments.

A.1 Proof of Theorem 2.3

This proof establishes the general approximation-penalty bound by coupling approximate and exact posteriors, controlling loss derivatives, and applying integrability and variational arguments. The resulting estimates are then specialized under the stated regularity conditions.

  • A.1 Proof of Theorem 2.3: Conditional stationarity and the mean-value theorem control the directional derivative appearing in the predictive comparison.The proof separates the loss-gradient fluctuation from the change in exponential weights.
  • A.1 Proof of Theorem 2.3: An optimal coupling of P and Q provides the Wasserstein representation used to compare their posterior-dependent quantities.The proof introduces interpolated laws and coordinate variables under the coupling.
  • A.1 Proof of Theorem 2.3: Differentiating the interpolated log integral and applying Cauchy–Schwarz bounds the change in predictive quantities by posterior displacement and moment terms.The argument uses expectations under the interpolating probability measure and the stated envelope bound.
  • A.1 Proof of Theorem 2.3: Jensen's inequality converts the posterior's mean distance from the target into a Wasserstein distance, completing the stability estimate.The final combination uses Cauchy–Schwarz under the coupling.
  • A.1 Proof of Theorem 2.3: The application verifies the required loss smoothness, curvature, envelope, and stationarity conditions before invoking the general theorem.The proof concludes by applying Theorem 2.3 after establishing those assumptions.

B.2 Proof of Theorem 3.7

The appendix proves sequence-model regret and approximation bounds by combining coordinatewise posterior analysis, product-measure Wasserstein identities, localized comparators, and truncation. Summation over coordinates yields the stated rates and truncation choice.

  • B.2 Proof of Theorem 3.7: Strong convexity of coordinatewise posterior potentials supplies second-moment control around the target parameter.Lemma B.1 bounds the second moment using curvature and the gradient at the reference point.
  • B.2 Proof of Theorem 3.7: For product posteriors, squared Wasserstein distances add coordinatewise, enabling separate control of variance and Sobolev bias terms.The coordinatewise coupling identity is applied to the posterior and prior products.
  • B.2 Proof of Theorem 3.7: Coordinatewise exponential-family moment bounds and binomial resolvents control posterior predictive risk across observations.The proof uses conditional sufficient-statistic moments and bounds involving κj and expected counts.
  • B.2 Proof of Theorem 3.7: A localized conjugate-prior comparator controls the finite-coordinate risk and KL contributions, while the prior is retained beyond the truncation level.Choosing m ≍ T^1/ζ makes the combined terms O(T^1/ζ).
  • B.2 Proof of Theorem 3.7: The Sobolev constraint bounds the truncation bias through spectral decay, producing a rate of t−(ζ−1)/ζ for the relevant Wasserstein term.The proof separates coordinates below and above a data-dependent threshold jt.
  • B.2 Proof of Theorem 3.7: Combining the approximation and comparator bounds with the general theorem and setting mT = ⌈T^1/ζ⌉ yields the claimed sequence-model guarantees.The final step invokes Theorems 4.5 and 4.6 before applying Theorem 2.3.

C.6 Proof of Theorem 4.8

The proof lower-bounds minimax regret by constructing a prior over active coordinates and relating predictive log-loss to conditional mutual information. Coordinate-wise information contributions remain non-negligible, yielding a T^(1/ζ) lower bound.

  • The Bayes-average log-loss regret is at least the conditional mutual information I(ω; Y1:T | X1:T).
  • For active coordinates, observations depend on disjoint independent bits, allowing the mutual-information lower bound to be decomposed across coordinates.
  • The active-coordinate counts satisfy Pr(Nj ≥ μj/2) ≳ 1 uniformly for sufficiently large T.
  • Each active coordinate contributes a positive constant to the mutual-information lower bound on the high-probability event.
  • T^(1/ζ) is the resulting lower-bound scale for Bayes-average regret and minimax regret, up to a multiplicative constant.

D.2 Proof of Theorem 5.1

The proof bounds predictive excess risk for Gaussian laws and then controls the discrepancy between exact and approximate Gaussian posteriors using mean and covariance geometry. A Wasserstein bound yields the theorem's comparison inequality.

  • Gaussian predictive excess risk is bounded by the squared mean error plus predictive variance error, scaled by 1/(2σξ^2).
  • The proof compares exact and approximate Gaussian laws through their mean functions and covariance operators.
  • The Gaussian Wasserstein formula bounds the mean difference by the Wasserstein distance and the covariance discrepancy through Bures–Wasserstein geometry.
  • When the Wasserstein distance is at most α and the exact posterior contraction radius is at most ε, the mean-related difference is controlled using Cauchy–Schwarz.
  • Combining the mean and variance bounds proves the stated comparison inequality.

D.3 Proof of Theorem 5.4

The proof establishes exact GP posterior contraction by controlling its mean and covariance under regular spectral design. Kernel-ridge risk bounds and covariance decomposition provide the required predictive-error rate.

  • The spectral truncation and covariance bounds combine to give the target cumulative predictive-error rate T^(d/(d+2s)).
  • The posterior covariance is decomposed into the first N coefficient directions and the orthogonal complement.
  • On the regular-design event, the covariance operator satisfies an operator-norm bound of order t^-1.
  • The exact GP posterior mean is the kernel-ridge regression estimator.
  • Under the spectral assumptions, the posterior-mean risk is bounded using eigenvalue decay, source conditions, and uniform eigenfunction control.

D.4 Proof of Theorem 5.5

The proof controls sparse variational GP approximation through Gaussian transportation and KL bounds, then combines these with predictive-variance control. This establishes the approximation estimates needed for the theorem.

  • Finite reverse KL from the variational posterior to the exact Gaussian posterior enables a Wasserstein control through Gaussian transportation.
  • On the posterior covariance event, the operator-norm control combines with sparse-GP KL bounds to establish the approximation estimate.
  • Finite-dimensional projections converge in Wasserstein distance, allowing the transportation argument to extend to the infinite-dimensional Gaussian setting.
  • The sparse GP approximation error is bounded when the number of inducing variables satisfies J ≥ J†.
  • Uniformly bounded predictive variance supplies the remaining control needed to combine the theorem bounds.
Loading 2608.25706v1…