acceptodds
Under review as a conference paper at ICLR 2027

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. Under pointwise derivative access, however, we construct a family of targets for which any randomized algorithm requires queries to attain a fixed accuracy from a uniformly bounded initial objective gap. 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 Lipschitz-Hessian 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Gaussian variational inference, accelerated optimization, variance reduction

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_BaKhOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses Gaussian variance inference (GVI) which aims to approximate the given target by Gaussian distribution. There are 3 main contributions. First, a deterministic acceleration for GVI is designed, which is based on the well-studied accelerated proximal gradient algorithm and treats the mean/factor coordinates of Gaussian as optimization variables. It requires the exact Gaussian expectation to compute the gradient for each update step. Second, the authors show the impossibility of acceleration when an algorithm may only evaluate the gradient at chosen sampled points. Third, with an Lipschitz Hessian assumption, the authors analyze 4 control-variate estimators inside one stochastic accelerated framework. Experiments show the acceleration of proposed methods.

Critical strengths
  • The paper provides an upper bound with exact expectations, and a lower bound showing that point wise access loses the acceleration, and an upper bound identifying small Hessian variation that can restore it.
  • The main novelty of this paper from my perspective is the query-complexity Lower bound for GVI.
Critical weaknesses
  • The algorithms presented are pretty standard. In particular, Theorem 2 is accelerated proximal gradient descent applied to a convex composite formulation, while Theorem 7 is accelerated proximal gradient descent with stochastic gradients. Lemma 17 and 28 are standard estimate-sequence techniques used for analyzing the convergence of accelerated gradient descent algorithms. The new technical content is in the variance bounds (Prop. 15, 19, 30 and Lemma 26), and the lower bound in Section 3.
  • The lower bound in Section 3 does not depend on lambda_H, but Section 4 shows that the acceleration can be recovered by it. Is showing some dependence on Hessian variation necessary?
Questions for authors

See the weaknesses.

2 comments

We thank the reviewer for the thoughtful assessment and for recognizing the lower bound as the main novelty of the paper.

Standard acceleration techniques. We agree with the reviewer that the accelerated updates and estimate-sequence arguments are standard, and we thank the reviewer for identifying the variance bounds and the lower bound as the main contribution. The variance bounds are what make the standard arguments work in our setting: they control the error along the accelerated iterates, since bounding the variance only at the optimum is not enough.

Hessian variation in the lower bound. Since Section 4 establishes acceleration under sufficiently small Hessian variation, we agree that it is natural to ask how much Hessian variation can be allowed while the near-linear lower bound holds. The potential VvV_v in Theorem 3 can be taken to have a finite Hessian-Lipschitz constant with an explicit lower (and upper) bounds. With α=1\alpha=1, the potential is Vv(x)=∥x∥2/2+(κ−1)(eKv∗ρτ)(x)V_v(x)=\Vert x\Vert^2/2+(\kappa-1)(e_{K_v}\ast\rho_\tau)(x), where eKve_{K_v} is half the squared distance to the truncated ball KvK_v and τ=(κ−1)−2\tau=(\kappa-1)^{-2}. By calculating the Hessian variation along the direction vv near the boundary of the hidden cap, we obtain the lower bound λH≥κ−1τgρ(0)\lambda_H\ge \frac{\kappa-1}{\tau}g_\rho(0) where gρg_\rho is the one-dimensional marginal density of ρ\rho. We have some freedom in choosing the mollifier ρ\rho. By choosing a suitable mollifier, we can ensure that $\lambda_H =\Theta(\kappa^3\sqrt d) =\Theta(\kappa^3\log\kappa)$ while preserving all the properties required for Theorem 3. Consequently, the near-linear lower bound continues to hold even under the additional restriction λH≤Cκ3log⁡κ\lambda_H \le C\kappa^3\log\kappa for some C>0C>0. We have added this argument at the end of Section 3, with a detailed derivation in the appendix. It does not, however, identify a sharp threshold in λH\lambda_H.

Acceleration in sequential rounds. We also have a new result: under curvature bounds alone, an accelerated variant with large batches needs only O(κ)O(\sqrt{\kappa}) sequential rounds, while the total number of queries remains linear in κ\kappa, consistent with our lower bound. This may resonate with the view that VI is efficient because many evaluations can run in parallel. As in Section 4, the key technical step to prove this is the variance analysis. We would be happy to add it to the paper if the reviewer finds it valuable.

We hope these responses address the reviewer's concerns. If so, we would be grateful if the reviewer would consider updating the score, and we would be glad to clarify anything further. Thank you again for your time and thoughtful feedback.

Thank you for your clarification. I think it is a good work. I'd like to update my score as "accept". Good luck.

Reviewer_ZBwwOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the benefits and limitations of Nesterov-type acceleration in full-covariance Gaussian variational inference. The authors first establish an accelerated benchmark when exact Gaussian expectations are available. They then prove a query-complexity lower bound showing that strong log-concavity and log-smoothness alone are insufficient to guarantee uniform acceleration under pointwise derivative access. To address this limitation, they combine accelerated proximal and projected methods with variance-reduced gradient estimators, whose variance is controlled by Hessian variation. These methods achieve accelerated total-query guarantees when Hessian variation is sufficiently small relative to the other problem parameters. Experiments on Gaussian targets and graph-probit posteriors illustrate the predicted condition-number scaling and the practical benefits of the proposed methods.

Critical strengths
  1. I find the topic interesting, with potential relevance beyond Gaussian variational inference. In stochastic optimization, the gradient variance can depend on the current iterate and the algorithm’s trajectory. When the variance-dependent term dominates the computational cost, Nesterov-type acceleration may not provide a substantial improvement in total query complexity. Designing and analyzing variance-reduction methods that enable effective acceleration is therefore an interesting and challenging problem. This paper provides useful insight into this issue by connecting Hessian variation with gradient variance and accelerated convergence.

  2. The query-complexity lower bound is a valuable theoretical contribution. The authors construct a family of strongly log-concave and log-smooth targets for which any randomized algorithm using pointwise derivatives of fixed finite order requires κ1−o(1)\kappa^{1-o(1)} queries to achieve a fixed accuracy. This establishes a limitation that extends beyond a particular gradient estimator or momentum scheme and helps explain why additional structure is needed to guarantee acceleration.

  3. The work is comprehensive, combining a lower bound, algorithm design, convergence analysis, and numerical experiments. The comparisons between accelerated and nonaccelerated methods using the same gradient estimator are particularly useful for assessing the contribution of momentum. Together, the theoretical results and experiments provide a well-developed investigation of both the possibilities and limitations of acceleration in this setting.

Critical weaknesses

One minor concern is that the practical relevance of the accelerated regime could be discussed more concretely. For the main first-order bounds, the accelerated term dominates when λH2d2≲ϵκ\lambda_H^2d^2\lesssim\epsilon\sqrt{\kappa}. This condition may become restrictive in higher-dimensional problems or when higher accuracy is required, where the variance-dependent term can dominate the total query complexity. The paper acknowledges this limitation and provides sharper bounds for Price–STL in Appendix C.4. Still, it would be helpful to explain which practical settings satisfy these favorable conditions and whether they explain the improvements observed in the experiments.

Questions for authors

The paper explains that controlled Hessian variation enables effective variance reduction, making acceleration useful. While the experiments show that momentum can help, it remains unclear how this benefit changes as Hessian variation increases. Could the authors provide controlled experiments with different levels of Hessian variation, and compare accelerated and non-accelerated updates using the same gradient estimator?

2 comments

We thank the reviewer for the positive assessment and for the helpful suggestion of a controlled experiment, which we have now carried out.

Practical relevance of the favorable regime. We agree with the reviewer that the condition λH2d2≲εκ\lambda_H^2d^2\lesssim\varepsilon\sqrt{\kappa} can be restrictive at large dimension or high accuracy. However, we note that even for the same estimator, a different variance bound can give a different regime. For example, in the graph-probit problem, strengthening the quadratic prior can increase κ\kappa without increasing the Hessian oscillation. Also, as the reviewer pointed out, Appendix C.4 of the submitted manuscript uses ωH\omega_H to bound the total complexity without using Hessian Lipschitzness. This illustrates that the suggested condition can be conservative, and could be applicable to wider range of problems in practice.

Controlled experiment. We thank the reviewer for pointing this out. Following the reviewer's suggestion, we compared the accelerated and nonaccelerated projected updates with the same STL estimator and batch size b=128b=128. We varied the amplitude of a nonquadratic perturbation in dimension 88, keeping the curvature bounds (with ratio 100100), the optimal Gaussian, and the initialization fixed.

LHL_HGradient queries to gap 10−610^{-6} (acc. / nonacc.)Final mean gap (acc. / nonacc.)
0025,344 / 529,920<10−13<10^{-13} / <10−13<10^{-13}
2.56×10−52.56\times10^{-5}25,344 / 529,920<10−13<10^{-13} / <10−13<10^{-13}
2.56×10−42.56\times10^{-4}25,344 / 529,9203.8×10−133.8\times10^{-13} / <10−13<10^{-13}
2.56×10−22.56\times10^{-2}25,344 / 529,9203.8×10−93.8\times10^{-9} / 2.7×10−102.7\times10^{-10}
2.562.56NR / NR3.8×10−53.8\times10^{-5} / 2.7×10−62.7\times10^{-6}
25.625.6NR / NR3.6×10−33.6\times10^{-3} / 2.6×10−42.6\times10^{-4}

Table R3. Query counts correspond to the first crossing of the five-seed mean objective gap below 10−610^{-6}. NR denotes no crossing within 12,000 updates.

For the four smallest amplitudes, acceleration reduced the number of gradients needed to reach the target by a factor of about 21. At the two largest amplitudes, neither method reached it, and the nonaccelerated update had a smaller final gap. Thus, even with the estimator and batch size fixed, the benefit of momentum diminished as the Hessian variation increased. We added these results to Appendix D.7. in the revised manuscript.

Acceleration in sequential rounds. Related to this comment, we have a new result that does not require small Hessian variation: under curvature bounds alone, an accelerated variant with large batches needs only O(κ)O(\sqrt{\kappa}) sequential rounds, compared with order κ\kappa for nonaccelerated methods, while the total number of queries remains linear in κ\kappa. This may resonate with the view that VI is efficient because many evaluations can run in parallel. We would be happy to add it to the paper if the reviewer finds it valuable.

We hope these responses address the reviewer's concerns. If so, we would be grateful if the reviewer would consider updating the score, and we would be glad to clarify anything further. Thank you again for your time and thoughtful feedback.

Dear Authors,

Thank you for the explanation and the added experiment. They address my questions. I'd like to update my score on this paper to 4.

Reviewer_48k6OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper sets out to analysis accelerated proximal stochastic gradient methods for GVI (gaussian variational inferences). Their first result shows how it is impossible to have an accelerated stochastic method under standard smoothness + strong convexity results with using O(\kappa) samples per iteration. This is interesting. They show that they can escape this lower bound by assuming the Hessian's are also Lipschitz, and using enough samples per iteration to guarantee that the stochastic gradient variance is bounded.

Critical strengths

Their proposed method +analysis could be the fastest known convergence rate for GVI, though for a rather restricted class of problem (more below). The lower bound on the impossibility of acceleration is also a strength. Finally, the paper is genuinely well written and clear.

Critical weaknesses

My main issue is this: From reading your paper, it is not crystal clear to me that the total complexity of your accelerated variants of proximal gradient do have a lower complexity than the unaccelerated version. Indeed, it's quite common that accelerated sgd variants can have worst complexity than sgd, and I want to ascertain that is not the case here.

Questions for authors

Specifically, to be accelerated in your sense O(κlog⁡ϵ−1)O(\sqrt{\kappa}\log \epsilon^{-1}) you require:

λK2d2≤ϵκ\lambda_K^2 d^2 \leq \epsilon \sqrt{\kappa} ⇒\Rightarrow LH2d2α5/2≤β\frac{L_H^2d^2}{\alpha^{5/2}} \leq \sqrt{\beta} That is, for sufficiently well conditioned, low dimensional, low accuracy problems with respect to the Lipschitz constant of the Hessian, you can acheive acceleration. To make it clearer that your total complexity is faster than the unaccelerated version, you should also add the total complexity of vanilla prox gradient descent in say Table 1. I think your complexity will appear favorably to vanillia prox gradient, but it's not totally clear a prior because your accelerated variants require large batch sizes where as the proof of vanilla prox gradient works with batch size 1.

One question I have been considering, is the value of having accelerated rates for black-box Gaussian variational inference. The reason I ask this, is because that Gaussian VI is such a well structured problem that it admits other fast and bespoke algorithms, that could be faster in practice as compared to your accelerated proximal gradient method. For instance the Batch-and-match method [Cai2024] which gives a stochastic proximal point method for GVI. Indeed, in practice it is difficult to beat a proximal point method. Though ultimately, I do understand your contribution either way from the perspective of developing the fastest known convergence rates for GVI. And moreover, how this could pave the way for other accelerated methods in black box VI.

[Cai2024] D. Cai et al, Batch and match: Black-box variational inference with a score-based divergence, ICML 2024

minor points or type-Os:

Line 143 : "Coresponding to a postive domain", I think positive definite domain is clearer, postive domain might mean elementwise positive

Line 144: "as additive constant" this is incredibly minor, but you also dropped a 1/2 multiplicative constant. 

Theorem 3. Using v∈Sd−1v\in \mathbb{S}^{d-1} to denote the d-dimensional sphere  conflicts with your Sd\mathbb{S}^{d} notation for summetric matrices. I thought for vv was a symmetric matrix until I read the proof.

Line 286: You should state right away the L is a matrix. I thought at first it was a constant. Only by line 297 is it clearely a matrix.

Line 318: I don't thikn you have defined N∇VN_{\nabla V} though I guess it's the total number of ∇V\nabla V gradient queires. Also in Theorem 5 you are missing the number of HVP queries (even though it's in the table, it also should be in the theorem).

3 comments

We thank the reviewer for the careful reading and the kind remarks on the clarity of the paper.

Regime of acceleration. We agree that our total-complexity acceleration guarantees require a favorable regime. We highlight this in the abstract and the introduction, and the reviewer also explains it clearly in the review. We also want to mention that our methods use variance-reduced gradient estimators, e.g., STL, which is widely used in practice, and our proposed FD estimator, whereas most guarantees in the literature are for the standard reparameterization gradient. For completeness, we derived complexity bounds with the same variance-reduced estimators for nonaccelerated methods such as stochastic proximal gradient (Table R1). For the upper bounds obtained with our current estimates, the accelerated bound is smaller in every case: momentum reduces the optimization term from order κ\kappa to order κ\sqrt{\kappa}, while the variance-dependent term keeps the same order. The gain is a factor of order κ\sqrt{\kappa} when the optimization term dominates, i.e., when λH2d2≲εκ\lambda_H^2d^2\lesssim\varepsilon\sqrt{\kappa}, which is the regime discussed above.

MethodNonacceleratedAcceleratedHVP cost
FD-proxdκ+λH2d3εd\kappa+\frac{\lambda_H^2 d^3}{\varepsilon}dκ+λH2d3εd\sqrt{\kappa}+\frac{\lambda_H^2 d^3}{\varepsilon}00
STL-projdκ+λH2d3εd\kappa+\frac{\lambda_H^2 d^3}{\varepsilon}dκ+λH2d3εd\sqrt{\kappa}+\frac{\lambda_H^2 d^3}{\varepsilon}00
Paired-proxκ+λH2d2ε\kappa+\frac{\lambda_H^2 d^2}{\varepsilon}κ+λH2d2ε\sqrt{\kappa}+\frac{\lambda_H^2 d^2}{\varepsilon}dN∇Vd N_{\nabla V}
Price–STL-projκ+λH2d2ε\kappa+\frac{\lambda_H^2 d^2}{\varepsilon}κ+λH2d2ε\sqrt{\kappa}+\frac{\lambda_H^2 d^2}{\varepsilon}dN∇Vd N_{\nabla V}

Table R1. Upper bounds on total gradient queries for expected excess KL ≤ε\le\varepsilon from our current estimates, omitting constants and log⁡(2Δ0/ε)\log(2\Delta_0/\varepsilon); λH=LH/α3/2\lambda_H=L_H/\alpha^{3/2}. Counts include all batch samples and FD calibration, and batch sizes are tuned separately for each method.

Batch size. As the reviewer pointed out, our stochastic accelerated guarantees require a sufficient batch size that depends on the estimator. However, we note that using Hessian queries removes the dimension dependence of batch sizes in the favorable regime. In our new experiments, we find that batch size of one is already sufficient for second-order methods. At b=1b=1, all accelerated Paired and Price–STL variants reach the target on all five graph-probit datasets within 110 gradient queries, earlier than their matched nonaccelerated counterparts (Table R2).

DatasetPaired-proxPaired-projPrice–STL-proj
Sonar21 / 5140 / 240100 / NR
Ionosphere31 / 11150 / 530110 / NR
WDBC31 / 10160 / 460110 / NR
Diabetes21 / 10150 / 480100 / NR
Banknote31 / 14150 / NR100 / NR

Table R2. Gradient queries needed to reduce the five-seed mean objective gap to 10−510^{-5} of its initial value at b=1b=1. Each cell reports accelerated / nonaccelerated results. Gaps are checked every ten updates. NR denotes no crossing within 600 updates.

Value of understanding acceleration. We agree that there are many existing algorithms for GVI, which is a relatively simple setting, and that some of them, such as batch-and-match (Cai et al., 2024), may be faster in practice. We will cite and discuss these works in the Related Work section. Many well-performing methods in VI combine momentum and variance reduction, and our paper studies the influence of these two components in the GVI setting. As the reviewer kindly described, we hope this provides a starting point for understanding accelerated methods in black-box VI more broadly.

Acceleration in sequential rounds. In addition to the Lipschitz-Hessian results, we have a new result: under curvature bounds alone, an accelerated variant with large batches needs only O(κ)O(\sqrt{\kappa}) sequential rounds, compared with order κ\kappa for nonaccelerated methods. The total number of queries remains linear in κ\kappa, consistent with our lower bound. This may resonate with the view that VI is efficient because many evaluations can run in parallel. We would be happy to add the details to the paper if the reviewer finds it valuable.

Minor points. Thank you for the careful reading.

  • We agree that “positive definite domain” is clearer and have revised the wording accordingly.
  • Thank you for pointing this out. Since Σ=AA⊤\Sigma=AA^\top and det⁡A>0\det A>0, the Gaussian entropy satisfies
H(q) = \frac12\log\det(2\pi e\,\Sigma) = \frac d2\log(2\pi e)+\frac12\log\det(AA^\top) = \frac d2\log(2\pi e)+\log\det A. \end{aligned}$$ Thus, the factor $1/2$ is canceled by the identity $\det(AA^\top)=(\det A)^2$. - Thank you very much for catching this ambiguity. We have revised the notation $S$ to clearly distinguish the two. - Thank you for the suggestion. We have clarified that $L$ is a matrix. - The notation $N_{\nabla V}$, denoting the total number of target-gradient evaluations, is defined at the end of Section 1, together with $T_\varepsilon$ and $N_{\mathrm{HVP}}$. Regarding Theorem 5, its statement concerns the first-order STL estimator, which requires only gradient evaluations and no HVPs. The HVP counts arise only for the corresponding second-order estimator, Price–STL, whose full guarantees are provided in the appendix. We hope these responses address the reviewer's concerns. If so, we would be grateful if the reviewer would consider updating the score, and we would be glad to clarify anything further. Thank you again for your time and thoughtful feedback.
Reviewer_48k6OpenReview ↗

Very satisfied with answers

Dear Authors,

thank you for addressing all of my questions, I am very satisfied with your answers, which increases my confidence in the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.