Hessian-Free High-Resolution Nesterov Acceleration for Sampling
arXiv:2006.09230
Abstract
Nesterov's Accelerated Gradient (NAG) for optimization has better performance than its continuous time limit (noiseless kinetic Langevin) when a finite step-size is employed \citep{shi2021understanding}. This work explores the sampling counterpart of this phenonemon and proposes a diffusion process, whose discretizations can yield accelerated gradient-based MCMC methods. More precisely, we reformulate the optimizer of NAG for strongly convex functions (NAG-SC) as a Hessian-Free High-Resolution ODE, change its high-resolution coefficient to a hyperparameter, inject appropriate noise, and discretize the resulting diffusion process. The acceleration effect of the new hyperparameter is quantified and it is not an artificial one created by time-rescaling. Instead, acceleration beyond underdamped Langevin in distance is quantitatively established for log-strongly-concave-and-smooth targets, at both the continuous dynamics level and the discrete algorithm level. Empirical experiments in both log-strongly-concave and multi-modal cases also numerically demonstrate this acceleration.
References in corpus (25)
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- A Variational Perspective on Accelerated Methods in Optimization
- -divergence Inequalities
- Sampling Can Be Faster Than Optimization
- A Lyapunov Analysis of Momentum Methods in Optimization
- Optimal non-reversible linear drift for the convergence to equilibrium of a diffusion
- On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
- Variance Reduction using Nonreversible Langevin Samplers
- Accelerating diffusions
- Underdamped Langevin MCMC: A non-asymptotic analysis
- Convergence of Langevin MCMC in KL-divergence
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- The Case for Bayesian Deep Learning
- Direct Runge-Kutta Discretization Achieves Acceleration
- A Unified Particle-Optimization Framework for Scalable Bayesian Sampling
- Understanding and Accelerating Particle-Based Variational Inference
- Is There an Analog of Nesterov Acceleration for MCMC?
- Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
- Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
- The Randomized Midpoint Method for Log-Concave Sampling
- Policy Optimization as Wasserstein Gradient Flows
- On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
- Approximate inference with Wasserstein gradient flows
- Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
- The strong convergence of operator-splitting methods for the Langevin dynamics model