arXiv preprint ·
Acceleration and its Limits in Gaussian Variational Inference
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning (Statistics)
Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
When is a better LLM worth paying for? Stochastic Optimization with Switching Mixed-Fidelity Oracles
On the Optimisation Landscape of Overparameterised Weighted MMD
Honesty is the Best Policy ... or is it? Demand Management for Probabilistic Service Options
An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
Get the few papers worth your time in Machine Learning (Statistics) every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.