Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
We present a unified framework to analyze the global convergence of Langevin dynamics based algorithms for nonconvex finite-sum optimization with n component functions. At the core of our analysis is a direct analysis of the ergodicity of the numerical approximations to Langevin dynamics, which leads to faster convergence rates. Specifically, we show that gradient Langevin dynamics (GLD) and stochastic gradient Langevin dynamics (SGLD) converge to the almost minimizer 2 within e O nd/( ✏) and e O d 7 /( 5 ✏ 5 ) stochastic gradient evaluations respectively 3 , where d is the problem dimension, and is the spectral gap of the Markov chain generated by GLD. Both results improve upon the best known gradient complexity 4 results [45]. Furthermore, for the first time we prove the global convergence guarantee for variance reduced stochastic gradient Langevin dynamics (SVRG-LD) to the almost minimizer within e O p nd 5 /( 4 ✏ 5/2 ) stochastic gradient evaluations, which outperforms the gradient complexities of GLD and SGLD in a wide regime. Our theoretical analyses shed some light on using Langevin dynamics based algorithms for nonconvex optimization with provable guarantees.
, where d is the problem dimension, and is the spectral gap of the Markov chain generated by GLD. Both results improve upon the best known gradient complexity 4 results [45]. Furthermore, for the first time we prove the global convergence guarantee for variance reduced stochastic gradient Langevin dynamics (SVRG-LD) to the almost minimizer within e O p nd 5 /( 4 ✏ 5/2 ) stochastic gradient evaluations, which outperforms the gradient complexities of GLD and SGLD in a wide regime. Our theoretical analyses shed some light on using Langevin dynamics based algorithms for nonconvex optimization with provable guarantees. question in nonconvex optimization and machine learning: is there an efficient algorithm that is guaranteed to converge to the global minimum of (1.1)?
Recent studies [17,16] showed that sampling from a distribution which concentrates around the global minimum of F n (x) is a similar task as minimizing F n via certain optimization algorithms. This justifies the use of Langevin dynamics based algorithms for optimization. In detail, the first order Langevin dynamics is defined by the following stochastic differential equation (SDE) dX(t) = rF n (X(t))dt + p 2 1 dB(t),
2) where > 0 is the inverse temperature parameter that is treated as a constant throughout the analysis of this paper, and {B(t)} t 0 is the standard Brownian motion in R d . Under certain assumptions on the drift coefficient rF n , it was showed that the distribution of diffusion X(t) in (1.2) converges to its stationary distribution [14], a.k.a., the Gibbs measure ⇡(dx) / exp( F n (x)), which concentrates on the global minimum of F n [29,26,47]. Note that the above convergence result holds even when F n (x) is nonconvex. This motivates the use of Langevin dynamics based algorithms for nonconvex optimization [45,53,50,49]. However, unlike first order optimization algorithms [42,27,46,3], which have been extensively studied, the non-asymptotic theoretical guarantee of applying Langevin dynamics based algorithms for nonconvex optimization, is still under studied. In a seminal work, Raginsky et al. [45] provided a non-asymptotic analysis of stochastic gradient Langevin dynamics (SGLD) [52] for nonconvex optimization, which is a stochastic gradient based discretization of (1.2). They proved that SGLD converges to an almost minimizer up to d . In a concurrent work, Zhang et al. [53] analyzed the hitting time of SGLD and proved its convergence to an approximate local minimum. More recently, Tzen et al. [50] studied the local optimality and generalization performance of Langevin algorithm for nonconvex functions through the lens of metastability and Simsekli et al. [49] developed an asynchronous-parallel stochastic L-BFGS algorithm for non-convex optimization based on variants of SGLD. Erdogdu et al. [23] further developed non-asymptotic analysis of global optimization based on a broader class of diffusions.
In this paper, we establish the global convergence for a family of Langevin dynamics based algorithms, including Gradient Langevin Dynamics (GLD) [17,20,16], Stochastic Gradient Langevin Dynamics (SGLD) [52] and Stochastic Variance Reduced Gradient Langevin Dynamics (SVRG-LD) [19] for solving the finite sum nonconvex optimization problem in (1.1). Our analysis is built upon the direct analysis of the discrete-time Markov chain rather than the continuous-time Langevin diffusion, and therefore avoid the discretization error.
After the author rebuttal: Thank you for your detailed and satisfying responses to all of my comments. I keep my overall score and congratulate you for a very nice paper that I enjoyed reading.  The authors propose a new framework to analyze the global convergence of Langevin dynamics based algorithms in a nonconvex optimization context. Three type of algorithms are considered, including gradient Langevin Dynamics, its stochastic version and, finally, a stochastic version that incorporates variance reduction. The key idea is a novel decomposition of the optimization error that directly analyses the ergodicity of the numerical approximation of the Langevin diffusion, rather than measuring the error of the true dynamics and its discretization, which is a slowly converging term. Moreover, focusing on the numerical approximation bypasses the analysis of the convergence of the true dynamics to its stationary distribution. Bypassing these two steps, the authors are able to show improved convergence rates compared to previous work for gradient Langevin dynamics and its stochastic version. In addition, the authors provide a first global convergence guarantee for the variance reduced version in this nonconvex setting. They show that, under certain conditions, the variance reduced version is superior to the other two.  My comments: 1. line 51: I understand this as you mean that you take the discrete-time diffusion to be the "ground truth" and do subsequent analysis based on this? If so there should be no discretization error, i.e. you bypass it by construction? What do you mean with "get around to a large extent"?  2. You refer to sigma2 as the "variance of the stochastic gradient". The variance of the gradient should formally be a matrix (variance-covariance) matrix since the gradient is a vector. Or is it another variance metric you have in mind?  3. In general, how does sigma2 (however you define it) scale with d and n?  4. Does the rate d^7 (or d^5 after variance reduction) mean that the stochastic versions are basically non-feasible for high-dimensional datasets? I am not an expert in optimization methods, but the consensus seem to be that optimization methods scale much better with respect to the dimension of the problem compared to say simulation methods. These rates with respect to d seem to suggest otherwise.  5. Do you have any empirical results to validate your mathematical derivations? Note that this is the reason that I responded "Not confident" on the reproducibility question.  6. You have assumed that eta is a constant "step-size". You could probably improve your rates a lot by clever step-size choices, for example, using second order methods. I suppose that you would have to make more assumptions and your results would be less general, but it would be interesting to hear your thoughts on how to extend this work beyond a constant step-size.  7. Should there be dependence on n in the rates for gradient Langevin dynamics in Section 1.1?  Other comments: This paper is very well written, in particular considering that it is purely theoretical. The authors have done an excellent job in presenting the work in a comprehensible way (using 8 pages only!).