Acceleration and its Limits in Gaussian Variational Inference

We study whether the classical momentum-based acceleration that improves the condition-number dependence of gradient descent from $\kappa$ to $\sqrt{\kappa }$ 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{\kappa }$ convergence rate. Under pointwise derivative access, however, we construct a family of targets for which any randomized algorithm requires ${\kappa }^{1-o(1)}$ 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.