Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
arXiv:2010.09597
Abstract
We provide a new convergence analysis of stochastic gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain. Under certain conditions on the target distribution, we prove that stochastic gradient evaluations suffice to guarantee -sampling error in terms of the total variation distance, where is the problem dimension. This improves existing results on the convergence rate of SGLD (Raginsky et al., 2017; Xu et al., 2018). We further show that provided an additional Hessian Lipschitz condition on the log-density function, SGLD is guaranteed to achieve -sampling error within stochastic gradient evaluations. Our proof technique provides a new way to study the convergence of Langevin-based algorithms and sheds some light on the design of fast stochastic gradient-based sampling algorithms.
arXiv comment44 pages, 1 figure
References in corpus (21)
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
- Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
- Sampling Can Be Faster Than Optimization
- On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
- Log-concave sampling: Metropolis-Hastings algorithms are fast
- Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
- A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
- On the convergence of Hamiltonian Monte Carlo
- Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
- On stochastic gradient Langevin dynamics with dependent data streams: the fully non-convex case
- Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
- Non-convex Learning via Replica Exchange Stochastic Gradient MCMC
- Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
- A Variant of Azuma's Inequality for Martingales with Subgaussian Tails
- Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion
- Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
- Nonasymptotic estimates for Stochastic Gradient Langevin Dynamics under local conditions in nonconvex optimization
- Couplings and quantitative contraction rates for Langevin dynamics
- A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
- Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
- Laplacian Smoothing Stochastic Gradient Markov Chain Monte Carlo