The promises and pitfalls of Stochastic Gradient Langevin Dynamics
Stochastic Gradient Langevin Dynamics (SGLD) has emerged as a key MCMC algorithm for Bayesian learning from large scale datasets. While SGLD with decreasing step sizes converges weakly to the posterior distribution, the algorithm is often used with a constant step size in practice and has demonstrated successes in machine learning tasks. The current practice is to set the step size inversely proportional to N where N is the number of training samples. As N becomes large, we show that the SGLD algorithm has an invariant probability measure which significantly departs from the target posterior and behaves like Stochastic Gradient Descent (SGD). This difference is inherently due to the high variance of the stochastic gradients. Several strategies have been suggested to reduce this effect; among them, SGLD Fixed Point (SGLDFP) uses carefully designed control variates to reduce the variance of the stochastic gradients. We show that SGLDFP gives approximate samples from the posterior distribution, with an accuracy comparable to the Langevin Monte Carlo (LMC) algorithm for a computational cost sublinear in the number of data points. We provide a detailed analysis of the Wasserstein distances between LMC, SGLD, SGLDFP and SGD and explicit expressions of the means and covariance matrices of their invariant distributions. Our findings are supported by limited numerical experiments.
Review after rebuttal:  I thank the author(s) for their response. While I still believe that this paper is a minor increment beyond what has already been done on SGLD, I agree that the message might be useful for some.  I also appreciate the effort the authors have made in improving the manuscript based on reviews' suggestions, particularly their efforts to include relevant numerical experiments to ML scenarios, and recommendations beyond the CV approach which has been studied to exhaustion and rarely applicable in practice.  Based on this, I've adjusted my decision to marginally above threshold.  Original review: In the paper "The promises and pitfalls of Stochastic Gradient Langevin Dynamics" the authors revisit the Stochastic Langevin Gradient Dynamics (SGLD) approach to approximately sampling from a probability distribution using stochastic gradients (specifically subsampling).   The authors compare a number of different classes of approximate inference method, including SGLD, LMC (known by some as Unadjusted Langevin Algorithm or ULA) and Stochastic Gradient Langevin Dynamics Fixed Point (SGLDFP) -- the latter being a variant of SGLD with a control variate exploiting the unimodality of the distribution, similar to what has been presented in [3, 25 and others].  In the usual context of strong log-concave models, geometric convergence can be readily shown for all these algorithms via synchronous coupling arguments (Lemma 1)  The authors investigate the asymptotic and non-asymptotic behaviour of these processes in the big-data setting (N = data size), under the frequently adopted assumption that the step size is proportional to 1/N and the mini-batch size is fixed independently of N.  T  They show that while the invariant measures for LMC and SGLDFP will converge to each other and the target distribution in Wasserstein-2 with rate O(N^{-1/2}),   SGLD and SGD will converge to each other O(N^{-1/2}).  They demonstrate an example (Bayesian linear regression) in which the distance to the invariant measure remains strictly bounded above from 0 as N -> infinity.    To further understand the behaviour, the authors then obtain asymptotic formula for the first two moments of each respective invariant distribution -- this makes evident the bias with respect to the correct moments for SGD and SGLD.  Finally, toy numerical experiments demonstrate the theory they have just described.  Firstly, I commend the authors for being so precise. I found to be very clearly written.  In my opinion, the main novelty in this paper is the demonstration that the equilibrium behaviour of (1) SGLD and SGD are so similar as N -> infinity and (2) LMC/ULA approaches the correct distribution as N->\infty (albeit this could have already been seen from other works).  While the analysis is illuminating, the scope of applicability is quite limited, the assumption of strongly log-concave models does not put us too far from the Gaussian case, and has already been studied very well following the familiar lines of  [A. Durmus and E.Moulines. High-dimensional Bayesian inference via the Unadjusted Langevin]  [Dalalyan, Arnak S., and Avetik G. Karagulyan. "User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient." arXiv preprint arXiv:1710.00095 (2017).] [Dalalyan, Arnak S. "Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent." arXiv preprint arXiv:1704.04752 (2017).] and various other papers.  Indeed, the proofs in the supplementary material follow almost identically similar proofs in these papers.    The conclusion of this paper is that SGLD diverges from the correct distribution in the large N limit and to use control variates with SGLD.  While the precise results differ, very similar observations using different approaches have been made in other papers, as the authors have mentioned themselves.  My strongest criticism is that I feel that other avenues could have been addressed beyond introducing control variates which is now well established and which are unlikely to work beyond unimodal distributions, and thus strongly limited their usage in the ML community.  For example, would another scaling of step size with N have fixed this asymptotic bias, or perhaps scaling the mini-batch size p with N -- indeed it appears that perhaps choosing p \propto N^{alpha} for some alpha > 0 would also be a solution?  A negative or positive statement along these lines could have been easily considered in this work and provided additional useful recommendations to a practitioner.  Moreover, given the typical style of NIPs papers I also believe the numerical experiments would have provided an opportunity to demonstrate the theory presented in a more realistic context outside the assumptions given.   Perhaps demonstrating examples where the strong log-concavity assumption does not hold, or the model has multiple modes.  In conclusion, while I believe this paper is clearly and precisely written,  given the plethora of previous works investigating very similar ideas using very similar methods, and given the limited applicability of the conclusions for typical problems in ML, I would recommend that perhaps this work is not appropriate for NIPs in its current form, but would strongly recommend it be submitted to a more appropriate journal/conference.    Finally, as a general comment that has no bearing on my decision on this paper,  I find it curious that the authors claim that "SGLD has demonstrated spectacular successes in machine learning tasks".  I am curious evidence this is based on -- I stand to be corrected but I have yet to see SGLD being used or applied in practice.