Acceleration and its Limits in Gaussian Variational Inference
Abstract
We study whether the classical momentum-based acceleration that improves the condition-number dependence of gradient descent from κ to √κ for strongly convex, smooth objectives extends to Gaussian variational inference (GVI) for strongly log-concave, log-smooth target distributions. With exact Gaussian expectations, a convex composite formulation of GVI yields the classical accelerated √κ convergence rate. However, when only pointwise derivatives are available, we construct a family of strongly log-concave targets for which any randomized algorithm requires κ1−o(1) queries to achieve a fixed objective accuracy, even when the initial objective gap is bounded independently of κ. Thus curvature bounds alone cannot guarantee uniform accelerated total-query complexity. We then ask which additional structure permits acceleration and give positive examples: under a Hessian-Lipschitz assumption, variance-reduced stochastic methods yield accelerated guarantees when the Hessian variation is sufficiently small. Finally, experiments on real datasets show substantial empirical speedups from acceleration across a broad range of methods.
Related
- Scalable Sparse Autoregressive Variational Inference for Non-Gaussian Spatial Fields
- Amortized Structured Stochastic Variational Inference for Gaussian Process Latent Variable Models
- Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference
- A Projection Anderson Acceleration Algorithm for Non-quasi-monotone Variational Inequalities with Hölder Continuous Terms
- Chebyshev-Exact Acceleration under Hessian Variation, II: Computer-Assisted Variational Lower Bound
BibTeX
@misc{park2026acceleration,
title = {{Acceleration and its Limits in Gaussian Variational Inference}},
author = {Jaesung R. Park and Uijeong Jang and Yifan Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21020},
eprint = {2610.21020},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21020},
}
RIS
TY - UNPB
TI - Acceleration and its Limits in Gaussian Variational Inference
AU - Jaesung R. Park
AU - Uijeong Jang
AU - Yifan Chen
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.21020
UR - https://arxiv.org/abs/2610.21020
AB - We study whether the classical momentum-based acceleration that improves the condition-number dependence of gradient descent from κ to √κ for strongly convex, smooth objectives extends to Gaussian variational inference (GVI) for strongly log-concave, log-smooth target distributions. With exact Gaussian expectations, a convex composite formulation of GVI yields the classical accelerated √κ convergence rate. However, when only pointwise derivatives are available, we construct a family of strongly log-concave targets for which any randomized algorithm requires κ^1−o(1) queries to achieve a fixed objective accuracy, even when the initial objective gap is bounded independently of κ. Thus curvature bounds alone cannot guarantee uniform accelerated total-query complexity. We then ask which additional structure permits acceleration and give positive examples: under a Hessian-Lipschitz assumption, variance-reduced stochastic methods yield accelerated guarantees when the Hessian variation is sufficiently small. Finally, experiments on real datasets show substantial empirical speedups from acceleration across a broad range of methods.
ER -