On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
Recent advances in Bayesian learning with large-scale data have witnessed emergence of stochastic gradient MCMC algorithms (SG-MCMC), such as stochastic gradient Langevin dynamics (SGLD), stochastic gradient Hamiltonian MCMC (SGHMC), and the stochastic gradient thermostat. While finite-time convergence properties of the SGLD with a 1st-order Euler integrator have recently been studied, corresponding theory for general SG-MCMCs has not been explored. In this paper we consider general SG-MCMCs with high-order integrators, and develop theory to analyze finite-time convergence properties and their asymptotic invariant measures. Our theoretical results show faster convergence rates and more accurate invariant measures for SG-MCMCs with higher-order integrators. For example, with the proposed efficient 2nd-order symmetric splitting integrator, the mean square error (MSE) of the posterior average for the SGHMC achieves an optimal convergence rate of L −4/5 at L iterations, compared to L −2/3 for the SGHMC and SGLD with 1st-order Euler integrators. Furthermore, convergence results of decreasing-step-size SG-MCMCs are also developed, with the same convergence rates as their fixed-step-size counterparts for a specific decreasing sequence. Experiments on both synthetic and real datasets verify our theory, and show advantages of the proposed method in two large-scale real applications.
The paper presents a convergence analysis for stochastic gradient Langevin algorithms. The results are very encouraging, since they show that it is possible to improve the rate of convergence by using high-order integrators. Indeed, previous convergence analysis for the SGLD algorithm have been rather discouraging, since the best possible rate in MSE has been shown to be L^{-2/3} (compared to the standard L^{-1} Monte Carlo rate). Guided by the new results, the authors also propose a 2nd order slitting integrator which attains a rate of L^{-4/5}, i.e. much closer to the standard Monte Carlo rate than SGLD (but still not quite there).I admit to not having checked the proofs in the supplementary material in detail, but the theory looks solid. I have a few questions and suggestions for improvement:1. You state in the introduction that you carry out the analysis for general SG-MCMC algorithms, but I do not understand what you mean by this. Is not the analysis in fact rather tailored to numerically integrated stochastic versions of the second order Langevin system? In particular, the way you define $\tilde L_l$ and $\Delta V_l$ seems to be specific to the 2nd order Langevin system. For instance, in the SG-HMC algorithm by Chen et al. 2014 [1] they use different scaling matrices for the drift and the noise terms, and it thus seems to me that this algorithm does not quite fit into the framework that you consider. Does your analysis apply to this algorithm? Likewise, the SG-NHT algorithm by Ding et al. 2014 [2] is based on a different, extended, system and it is not completely obvious that this fits into your framework. I think that you should be more specific about the precise requirements that you have on the diffusion (1) for your results to hold.2. In the proposed integrator, systems B and O_l together define an Ornstein-Uhlenbeck process for p (\theta is kept fixed). Why do you propose to split this into B and O_l, rather than integrating exactly the OU process? (This would also lead to a symmetric integrator, ACA, where C=B+O_l.)3. I found Section 5 "large-scale machine learning applications" too brief to provide any valuable insights. I would suggest that you focus on one of the two applications in the main paper, and move the second application completely to the supplementary material.4. Can you comment on the possibility of using other (i.e., not splitting-based) high-order integrators for SG-HMC and SGLD? Are there any standard integrators that could be used to obtain a L^{-4/5} rate for SGLD?*** Minor points/typos:5. Line 121. Are you missing a minus sign in the definition of V_l (since \grad_\theta U comes with a negative sign in the definition of F)?6. Line 261. The condition should be $\sum_{l=1}^L h_l^2 / S_L^2 \rightarrow 0$, no?7. What is L for the fixed step-size results presented in Figure 2? Is it still 10^6 (as in Figure 1) or do you use a smaller value here?8. Line 397: Should be $L = 100$K and not $L = 100K$ (or even better, $L = 10^5$).