Acceleration and its Limits in Gaussian Variational Inference

arXiv:2610.21020v1 Announce Type: cross Abstract: 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. However, when only pointwise derivatives are available, we construct a family of strongly log-concave targets for which any randomized algorithm requires kappa^{1-o(1)} queries to achieve a fixed objective accuracy, even when the initial objective gap is bounded independently of kappa. 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.

Source: arXiv cs.LG | 2026-10-16