betaFeedback

WorksMathematics

Stochastic counterpart of Nesterov's method for sampling and provable non-acceleration of samplers with heavy-ball structure

Abstract

Polyak's heavy-ball method and Nesterov's method are two momentum-based methods that have inspired many optimization techniques used in applied fields, including machine learning. Momentum also provides a connection with sampling, and interestingly, many kinetic Langevin samplers reduce to the heavy-ball recurrence when velocity is eliminated and noise is removed. This observation motivates a natural question: what is the corresponding sampler for Nesterov's method? We propose a sampler whose deterministic part is exactly Nesterov's recurrence, driven by temporally correlated Gaussian noise and requires one new gradient evaluation per step. Noise correlation provides O(h2)\mathcal{O}(h^2) bias for smooth observables. We establish geometric ergodicity for possibly non-convex potentials. For strongly convex potentials with Lipschitz continuous gradients, we obtain contraction rates and show that, up to an additive constant, the energy decays at a rate of order κ−1/2κ^{-1/2}, where κκ is the condition number. For Gaussian targets, we show that relaxation has square-root dependence on κκ. We further prove that any sampler based on heavy-ball dynamics with additive noise cannot achieve accelerated convergence uniformly over the class of strongly convex functions. Finally, we compare the proposed sampler with OBABO, BAOAB, HMC, MALA, BPS, and NUTS in numerical experiments and demonstrate the better performance of proposed sampler.

Paper details

vlnc:W_7ypgx5kf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s ChatGPT

View statement
Looking for related papers…