Acceleration and its Limits in Gaussian Variational Inference

Jaesung R. Park; Uijeong Jang; Yifan Chen

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

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)}$ 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

Panel of Figure 1 — Figure 1: A hidden cap in direction $v$ inside the ball $B$ .

Method	Batch size	Gradient queries	HVP queries
FD + Alg. 2	$1+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon\sqrt{\kappa}}$	$d\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon}$	$0$
STL + Alg. 3	$d+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon\sqrt{\kappa}}$	$d\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon}$	$0$
Paired + Alg. 2	$1+\dfrac{\lambda_{H}^{2}d^{2}}{\varepsilon\sqrt{\kappa}}$	$\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{2}}{\varepsilon}$	$d\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{3}}{\varepsilon}$
Price–STL + Alg. 3	$1+\dfrac{\lambda_{H}^{2}d^{2}}{\varepsilon\sqrt{\kappa}}$	$\sqrt{\kappa}+\dfrac{\lambda_{H}^{2}d^{2}}{\varepsilon}$	$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

T_{\varepsilon}=O\left(\sqrt{\kappa}\log(2\Delta_{0}/\varepsilon)\right)

iterations. Entries give orders in

O(\cdot)

notation; the two oracle-count columns omit the common factor

\log(2\Delta_{0}/\varepsilon)

Figure 2: Stochastic acceleration on Gaussian targets. STL-proj with $b=64$ : (a) mean KL gap at $\kappa=300$ with $20$ – $80$ percentile bands over five seeds; (b) updates to mean KL $\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

64

. Curves are five-seed mean objective gaps from

\mathcal{N}(0,I_{d})

, with

20

–

80

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

\kappa=300

; (b) updates to KL

\leq 10^{-6}

, with

\sqrt{\kappa}

and

\kappa

reference lines.

Figure 5: Gaussian comparisons at $\kappa=300$ . Rows show first- and second-order methods; columns show $b=1,8,64$ . Curves are exact KL gaps, averaged over five seeds with $20$ – $80$ 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^{-6}$ ; gaps below $10^{-9}$ leave the displayed range.

Dataset	OpenML ID	$d=n$	$\kappa$
Sonar	40	208	69.47
Ionosphere	59	351	75.64
WDBC	1510	569	69.68
Diabetes	37	768	70.20
Banknote	1462	1372	69.43

Appendix

Table 2: Graph-probit dimensions and conditioning. Each observation has one latent score. All targets use

\alpha=1

, so

\kappa=\beta

Method	Oracle	Coord.	Entropy treatment / domain	Step $\eta$
FD-prox (Alg. 2 )	1st	$L$	Entropy and factor-ball prox	$1/(\alpha s_{p}^{2})$
FD-proj (Alg. 4 )	1st	$L$	Entropy extension, $K_{L}$	$1/(\alpha s_{e}^{2})$
STL-proj (Alg. 3 )	1st	$C$	Full gradient, $K_{C}$	$1/(15\beta)$
Paired-prox (Alg. 2 )	2nd	$L$	Entropy and factor-ball prox	$1/(\alpha s_{p}^{2})$
Paired-proj (Alg. 4 )	2nd	$L$	Entropy extension, $K_{L}$	$1/(\alpha s_{e}^{2})$
Price-STL-proj (Alg. 3 )	2nd	$C$	Full gradient, $K_{C}$	$1/(15\beta)$

Appendix

Table 3: Methods and fixed steps. Each of the first six rows includes accelerated and nonaccelerated variants.

L

is a positive-diagonal Cholesky factor and

C

is symmetric positive definite. Oracle order refers to target derivatives.

Matched pair	$10^{-2}$	$10^{-3}$	$10^{-4}$	$10^{-5}$
FD-prox	0/0/5/0	3/0/2/0	4/0/1/0	5/0/0/0
FD-proj	5/0/0/0	4/0/1/0	5/0/0/0	5/0/0/0
STL-proj	2/3/0/0	2/2/0/1	2/0/0/3	1/0/0/4
Paired-prox	0/0/5/0	3/0/2/0	4/0/1/0	5/0/0/0
Paired-proj	5/0/0/0	4/0/1/0	5/0/0/0	5/0/0/0
Price-STL-proj	5/0/0/0	5/0/0/0	5/0/0/0	5/0/0/0

Appendix

Table 4: Graph-probit hitting-time comparisons at

b=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=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,\ldots,600

, including calibration and setup queries. First-order methods use no HVPs. For second-order methods,

N_{\mathrm{HVP}}=d[N_{\nabla V}-N_{\nabla V}(0)]

, where the setup count

N_{\nabla V}(0)

1

for Paired-prox and

0

otherwise.

	$b=8$		$b=64$		$b=256$
Dataset	Acc.	Nonacc.	Acc.	Nonacc.	Acc.	Nonacc.
Sonar	$1.01\times 10^{3}$	$5.66\times 10^{-2}$	$2.70\times 10^{-5}$	$5.24\times 10^{-2}$	$2.84\times 10^{-6}$	$5.24\times 10^{-2}$
Ionosphere	$3.00\times 10^{3}$	$9.27\times 10^{1}$	$2.84\times 10^{-1}$	$1.46\times 10^{0}$	$1.09\times 10^{-5}$	$1.46\times 10^{0}$
WDBC	$9.61\times 10^{3}$	$1.28\times 10^{3}$	$1.09\times 10^{1}$	$2.56\times 10^{0}$	$3.34\times 10^{-5}$	$2.55\times 10^{0}$
Diabetes	$1.90\times 10^{4}$	$9.95\times 10^{3}$	$7.03\times 10^{2}$	$2.33\times 10^{0}$	$7.35\times 10^{-5}$	$2.32\times 10^{0}$
Banknote	$4.93\times 10^{4}$	$3.71\times 10^{4}$	$4.78\times 10^{3}$	$3.61\times 10^{1}$	$1.09\times 10^{0}$	$3.57\times 10^{1}$

Appendix

Table 5: STL batch sensitivity. Five-seed mean gaps

F(q_{600})-F_{\mathrm{ref}}

, with identical stepsizes and initialization across batches.

Figure 7: Graph-probit comparisons at

b=256

. Rows show first- and second-order methods on all five datasets. Plotting conventions follow Appendix D.4 ; other settings match Figure 3 .

Matched pair	Acc. earlier	Nonacc. earlier	Same checkpoint	Neither reached
FD-prox	7	7	1	0
FD-proj	10	1	2	2
STL-proj	12	1	0	2
Paired-prox	9	3	3	0
Paired-proj	12	0	3	0
Price-STL-proj	15	0	0	0

Appendix

Table 6: Logistic-regression hitting-time comparisons. Each row covers five datasets and three batches, using a hitting threshold of

1\%

of the initial mean gap.

Figure 8: First-order methods on logistic-regression posteriors. Rows show

b=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,64

; columns show the five datasets. Plotting conventions follow Appendix D.4 .

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

Stochastic Gradient Variational Inference with Price's Gradient Estimator from Bures-Wasserstein to Parameter Space
Feb 21, 2026Kyurae Kim, Qiang Fu, Yi-An Ma +2Variational Inference
University of Pennsylvania, Philadelphia, U.S. · Yale University, New Haven, U.S. · University of California San Diego, San Diego, U.S. +1
Variational inference via radial transport
Feb 19, 2026Luca Ghafourpour, Sinho Chewi, Alessio Figalli +1Variational Inference
ETH Zürich · Cambridge · Yale University
Wasserstein Contraction of Coordinate Ascent Variational Inference
May 28, 2026Rocco Caprio, Adrien Corenflos, Sam PowerBayesian Inference Variational Inference
University of Warwick and Bocconi University. · University of Warwick. · University of Bristol.

Feb 21, 2026J/K move · Enter open · S save

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

Kyurae Kim, Qiang Fu, Yi-An Ma, Jacob R. Gardner+1

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

Variational Inference

Open paper AskPDF arXiv

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.

Abstract

Oracle Complexity

Explore similar work

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

Variational inference via radial transport

Wasserstein Contraction of Coordinate Ascent Variational Inference