Gaussian variational inference (GVI) approximates a target distribution by fitting a Gaussian, and practitioners often hope that momentum-based acceleration—which improves gradient descent's condition-number dependence from κ to √κ—will carry over. The new paper shows this transfer is subtle. When exact Gaussian expectations are available, a convex composite formulation of GVI indeed achieves the classical accelerated √κ rate. But that ideal setting is rarely what happens in practice.
The authors then consider the realistic case where only pointwise derivatives of the log-density are available. They construct a family of strongly log-concave, log-smooth targets for which any randomized algorithm requires κ^{1-o(1)} queries to reach a fixed objective accuracy, even when the initial objective gap is bounded independently of κ. This means curvature bounds alone cannot guarantee a uniform accelerated total-query complexity; the classical acceleration story breaks down.
The paper does not stop at the negative result. It asks what additional structure can restore acceleration, and finds a positive answer: under a Hessian-Lipschitz assumption, variance-reduced stochastic methods provide accelerated guarantees when the Hessian variation is sufficiently small. Finally, experiments on real datasets show that acceleration still gives substantial empirical speedups across a broad range of methods, suggesting that the theoretical barrier, while real, does not always bind in practice.