stat.MLOct 14, 2026

Acceleration and its Limits in Gaussian Variational Inference

Authors: Jaesung R. Park, Uijeong Jang, Yifan Chen

Organizations: Department of Mathematics, University of California, Los Angeles

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study whether the classical momentum-based acceleration that improves the condition-number dependence of gradient descent from κκ to κ\sqrtκ 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 κ\sqrtκ 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)κ^{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.

Figures & tables

Figure 1: A hidden cap in direction vv inside the ball BB .
MethodBatch sizeGradient queriesHVP queries
FD + Alg. 21+λH2d3εκ1+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon\sqrt{\kappa}}dκ+λH2d3εd\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon}00
STL + Alg. 3d+λH2d3εκd+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon\sqrt{\kappa}}dκ+λH2d3εd\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon}00
Paired + Alg. 21+λH2d2εκ1+\dfrac{\lambda_{H}^{2}d^{2}}{\varepsilon\sqrt{\kappa}}κ+λH2d2ε\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{2}}{\varepsilon}dκ+λH2d3εd\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon}
Price–STL + Alg. 31+λH2d2εκ1+\dfrac{\lambda_{H}^{2}d^{2}}{\varepsilon\sqrt{\kappa}}κ+λH2d2ε\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{2}}{\varepsilon}dκ+λH2d3εd\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon}
Table 1: Fixed-batch guarantees. All four methods (estimator, algorithm) attain expected objective gap at most ε\varepsilon in Tε=O(κlog⁡(2Δ0/ε))T_{\varepsilon}=O\left(\sqrt{\kappa}\log(2\Delta_{0}/\varepsilon)\right) iterations. Entries give orders in O(⋅)O(\cdot) notation; the two oracle-count columns omit the common factor log⁡(2Δ0/ε)\log(2\Delta_{0}/\varepsilon) .
Figure 2: Stochastic acceleration on Gaussian targets. STL-proj with b=64b=64 : (a) mean KL gap at κ=300\kappa=300 with 2020 – 8080 percentile bands over five seeds; (b) updates to mean KL ≤10−6\leq 10^{-6} , with κ\sqrt{\kappa} and κ\kappa reference lines.
Figure 3: Convergence on graph-probit posteriors. The top row compares first-order methods and the bottom row compares second-order methods, all with batch size 6464 . Curves are five-seed mean objective gaps from N(0,Id)\mathcal{N}(0,I_{d}) , with 2020 – 8080 percentile bands. Solid and dashed lines distinguish accelerated and nonaccelerated variants within each matched pair. Appendix D.5 reports comparisons across all five datasets.
Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Paired benchmark on Gaussian targets. Accelerated and nonaccelerated Paired-prox with a samplewise-exact estimator: (a) KL gap at κ=300\kappa=300 ; (b) updates to KL ≤10−6\leq 10^{-6} , with κ\sqrt{\kappa} and κ\kappa reference lines.
Figure 5: Gaussian comparisons at κ=300\kappa=300 . Rows show first- and second-order methods; columns show b=1,8,64b=1,8,64 . Curves are exact KL gaps, averaged over five seeds with 2020 – 8080 percentile bands for stochastic methods. FD and paired methods use one seed. Solid and dashed lines distinguish accelerated and nonaccelerated variants. The dotted line marks 10−610^{-6} ; gaps below 10−910^{-9} leave the displayed range.
DatasetOpenML IDd=nd=nκ\kappa
Sonar4020869.47
Ionosphere5935175.64
WDBC151056969.68
Diabetes3776870.20
Banknote1462137269.43
Appendix
Table 2: Graph-probit dimensions and conditioning. Each observation has one latent score. All targets use α=1\alpha=1 , so κ=β\kappa=\beta .
MethodOracleCoord.Entropy treatment / domainStep η\eta
FD-prox (Alg. 2 )1stLLEntropy and factor-ball prox1/(αsp2)1/(\alpha s_{p}^{2})
FD-proj (Alg. 4 )1stLLEntropy extension, KLK_{L}1/(αse2)1/(\alpha s_{e}^{2})
STL-proj (Alg. 3 )1stCCFull gradient, KCK_{C}1/(15β)1/(15\beta)
Paired-prox (Alg. 2 )2ndLLEntropy and factor-ball prox1/(αsp2)1/(\alpha s_{p}^{2})
Paired-proj (Alg. 4 )2ndLLEntropy extension, KLK_{L}1/(αse2)1/(\alpha s_{e}^{2})
Price-STL-proj (Alg. 3 )2ndCCFull gradient, KCK_{C}1/(15β)1/(15\beta)
Appendix
Table 3: Methods and fixed steps. Each of the first six rows includes accelerated and nonaccelerated variants. LL is a positive-diagonal Cholesky factor and CC is symmetric positive definite. Oracle order refers to target derivatives.
Matched pair10−210^{-2}10−310^{-3}10−410^{-4}10−510^{-5}
FD-prox0/0/5/03/0/2/04/0/1/05/0/0/0
FD-proj5/0/0/04/0/1/05/0/0/05/0/0/0
STL-proj2/3/0/02/2/0/12/0/0/31/0/0/4
Paired-prox0/0/5/03/0/2/04/0/1/05/0/0/0
Paired-proj5/0/0/04/0/1/05/0/0/05/0/0/0
Price-STL-proj5/0/0/05/0/0/05/0/0/05/0/0/0
Appendix
Table 4: Graph-probit hitting-time comparisons at b=64b=64 . Thresholds are fractions of the initial mean gap. Entries count datasets with an earlier accelerated crossing / earlier nonaccelerated crossing / equal recorded crossing / no crossing by either variant. Matched-pair rankings are identical under derivative-query budgets.
Figure 6: Graph-probit convergence by gradient-query cost at b=64b=64 . Rows show first- and second-order methods on all five datasets. Means and bands follow Figure 3 ; the logarithmic horizontal axis uses cumulative gradient counts at k=10,20,…,600k=10,20,\ldots,600 , including calibration and setup queries. First-order methods use no HVPs. For second-order methods, NHVP=d[N∇V−N∇V(0)]N_{\mathrm{HVP}}=d[N_{\nabla V}-N_{\nabla V}(0)] , where the setup count N∇V(0)N_{\nabla V}(0) is 11 for Paired-prox and 00 otherwise.
 b=8b=8b=64b=64b=256b=256
DatasetAcc.Nonacc.Acc.Nonacc.Acc.Nonacc.
Sonar1.01×1031.01\times 10^{3}5.66×10−25.66\times 10^{-2}2.70×10−52.70\times 10^{-5}5.24×10−25.24\times 10^{-2}2.84×10−62.84\times 10^{-6}5.24×10−25.24\times 10^{-2}
Ionosphere3.00×1033.00\times 10^{3}9.27×1019.27\times 10^{1}2.84×10−12.84\times 10^{-1}1.46×1001.46\times 10^{0}1.09×10−51.09\times 10^{-5}1.46×1001.46\times 10^{0}
WDBC9.61×1039.61\times 10^{3}1.28×1031.28\times 10^{3}1.09×1011.09\times 10^{1}2.56×1002.56\times 10^{0}3.34×10−53.34\times 10^{-5}2.55×1002.55\times 10^{0}
Diabetes1.90×1041.90\times 10^{4}9.95×1039.95\times 10^{3}7.03×1027.03\times 10^{2}2.33×1002.33\times 10^{0}7.35×10−57.35\times 10^{-5}2.32×1002.32\times 10^{0}
Banknote4.93×1044.93\times 10^{4}3.71×1043.71\times 10^{4}4.78×1034.78\times 10^{3}3.61×1013.61\times 10^{1}1.09×1001.09\times 10^{0}3.57×1013.57\times 10^{1}
Appendix
Table 5: STL batch sensitivity. Five-seed mean gaps F(q600)−FrefF(q_{600})-F_{\mathrm{ref}} , with identical stepsizes and initialization across batches.
Figure 7: Graph-probit comparisons at b=256b=256 . Rows show first- and second-order methods on all five datasets. Plotting conventions follow Appendix D.4 ; other settings match Figure 3 .
Matched pairAcc. earlierNonacc. earlierSame checkpointNeither reached
FD-prox7710
FD-proj10122
STL-proj12102
Paired-prox9330
Paired-proj12030
Price-STL-proj15000
Appendix
Table 6: Logistic-regression hitting-time comparisons. Each row covers five datasets and three batches, using a hitting threshold of 1%1\% of the initial mean gap.
Figure 8: First-order methods on logistic-regression posteriors. Rows show b=1,8,64b=1,8,64 ; columns show the five datasets. Plotting conventions follow Appendix D.4 .
Figure 9: Second-order methods on logistic-regression posteriors. Rows show b=1,8,64b=1,8,64 ; columns show the five datasets. Plotting conventions follow Appendix D.4 .
More in this topic

Oracle Complexity

Oracle complexity studies how many queries to limited-information procedures algorithms need to solve optimization, learning, sampling, and related problems.

See all 30 papers

Explore similar work

CardsList
Feb 21, 2026

Stochastic Gradient Variational Inference with Price's Gradient Estimator from Bures-Wasserstein to Parameter Space

For approximating a target distribution given only its unnormalized log-density, stochastic gradient-based variational inference (VI) algorithms are a popular approach. For example, Wasserstein VI (WVI) and black-box VI (BBVI) perform gradient descent in measure space (Bures-Wasserstein space) and parameter space, respectively. Previously, for the Gaussian variational family, convergence guarantees for WVI have shown superiority over existing results for black-box VI with the reparametrization gradient, suggesting the measure space approach might provide some unique benefits. In this work, however, we close this gap by obtaining identical state-of-the-art iteration complexity guarantees for both. In particular, we identify that WVI's superiority stems from the specific gradient estimator it uses, which BBVI can also leverage with minor modifications. The estimator in question is usually associated with Price's theorem and utilizes second-order information (Hessians) of the target log-density. We will refer to this as Price's gradient. On the flip side, WVI can be made more widely applicable by using the reparametrization gradient, which requires only gradients of the log-density. We empirically demonstrate that the use of Price's gradient is the major source of performance improvement.

Kyurae Kim, Qiang Fu, Yi-An Ma +2

University of Pennsylvania, Philadelphia, U.S. · Yale University, New Haven, U.S. · University of California San Diego, San Diego, U.S. +1

Variational Inference
AskPDF
Feb 19, 2026

Variational inference via radial transport

In variational inference (VI), the practitioner approximates a high-dimensional distribution ππ with a simple surrogate one, often a (product) Gaussian distribution. However, in many cases of practical interest, Gaussian distributions might not capture the correct radial profile of ππ, resulting in poor coverage. In this work, we approach the VI problem from the perspective of optimizing over these radial profiles. Our algorithm radVI is a cheap, effective add-on to many existing VI schemes, such as Gaussian (mean-field) VI and Laplace approximation. We provide theoretical convergence guarantees for our algorithm, owing to recent developments in optimization over the Wasserstein space--the space of probability distributions endowed with the Wasserstein distance--and new regularity properties of radial transport maps in the style of Caffarelli (2000).

Luca Ghafourpour, Sinho Chewi, Alessio Figalli +1

ETH Zürich · Cambridge · Yale University

Variational Inference
AskPDF
May 28, 2026

Wasserstein Contraction of Coordinate Ascent Variational Inference

We study the non-asymptotic contraction in Wasserstein distance of the sequential, parallel, and random-scan coordinate ascent variational inference algorithms. This is shown to hold under a functional smoothness condition of the optimality maps and a transportation-information inequality at their fixed points. Our results are sharp and general, and as opposed to those based on global strong log-concavity assumptions, they allow for local convergence on smooth, non-smooth, and discrete manifolds, including within the context of data augmentation. We consider many applications in statistical physics and Bayesian statistics. These include pairwise Markov Random field models such as Ising and Curie-Weiss, unbalanced Bayesian Gaussian Mixture Models, high-dimensional Bayesian Probit Regression, and high-dimensional Logistic Regression with Pólya--Gamma random variables (i.e. Jaakkola-Jordan's algorithm). In many of these models, these represent the first available convergence results of their kind.

Rocco Caprio, Adrien Corenflos, Sam Power

University of Warwick and Bocconi University. · University of Warwick. · University of Bristol.

Bayesian InferenceVariational InferenceWasserstein Distance
AskPDF