Stochastic Gradient MCMC with Stale Gradients
Stochastic gradient MCMC (SG-MCMC) has played an important role in largescale Bayesian learning, with well-developed theoretical convergence properties. In such applications of SG-MCMC, it is becoming increasingly popular to employ distributed systems, where stochastic gradients are computed based on some outdated parameters, yielding what are termed stale gradients. While stale gradients could be directly used in SG-MCMC, their impact on convergence properties has not been well studied. In this paper we develop theory to show that while the bias and MSE of an SG-MCMC algorithm depend on the staleness of stochastic gradients, its estimation variance (relative to the expected estimate, based on a prescribed number of samples) is independent of it. In a simple Bayesian distributed system with SG-MCMC, where stale gradients are computed asynchronously by a set of workers, our theory indicates a linear speedup on the decrease of estimation variance w.r.t. the number of workers. Experiments on synthetic data and deep neural networks validate our theory, demonstrating the effectiveness and scalability of SG-MCMC with stale gradients.
This paper presents theoretical analysis for Stochastic-Gradient MCMC methods using stale (outdated) gradients, which often appear in asynchronous settings. In a nutshell, the paper extends the results of Chen, Ding, Carin, NIPS 2015 to the stale gradient settings. The bias, MSE, and the variance of the SG-MCMC estimator is rigorously analyzed under certain and rather standard assumptions. It has been shown that the bias and the MSE of the estimator depend on the "staleness" of the gradients whereas the variance does not. These results indicate that in a distributed setting where multiple chains are run in parallel, the SG-MCMC estimator would be able to attain lower MSE even if stale gradients are being used. The theory is supported by several experiments (both synthetic and real-data).  
Overall, in my opinion this is an excellent paper. The paper is very well written, the objectives and the contributions are stated very clearly. I really enjoyed reading the paper.   Even though SG-MCMC methods have enabled scaling up MCMC to very large-scale settings, distributed and/or asynchronous variants of SG-MCMC have not been rigorously explored yet. In this sense, this paper has very important contributions and would be of great interest to the community. The results of the paper, in a sense, demystify asynchronous SG-MCMC, where for the first time, we obtain a clear understanding of the behaviors of the bias, variance, and the MSE of the SG-MCMC estimator. Besides, certain trade-offs become theoretically more grounded, such as the one explained in line 291 (page 7). Another take-home message is that using an higher-order integrator would not be useful in the stale-gradient settings.   The results presented in the paper can also be used for developing and analyzing new distributed/asynchronous SG-MCMC methods, or even new stochastic optimization methods based on simulated annealing.    I only have some minor comments/corrections.  -- Main Document --   * Line 13: I think it is better to write "with respect to" instead of "w.r.t." since there is enough space.   * It is quite trivial but it might be good to remind the reader about MSE = Bias^2 + Var. I would suggest the authors to check Section D of the supplementary document of (Li et al. 2016). ([28] in the paper)  * Line 168: "M" should be "S".  * Line 241: "indicates" should be "indicated"  * Line 249: I would prefer saying "we average" since all the rest of the paragraph is in the present tense.   * Theorem 6: Should the step length be "h_m" instead of "h"?  * Line 291: I am not very happy with the usage of PSGLD as the baseline SG-MCMC method in the deep learning experiments. Due to the negligence of the "correction term" in PSGLD, the bounds given in Lemma 1 no longer hold for PSGLD: there are additional terms appearing in the bounds of both bias and MSE due to this negligence. Therefore, the theory presented in this paper is not completely appropriate for PSGLD. I would suggest the authors to use another SG-MCMC method which would obey the bounds given in Lemma 1. If this is not possible I would recommend providing a discussion/explanation on this subject.    * Lines 322-325: The full list of authors should be given in [7,8,9].  -- Supplementary Document --   * Line 427, Line 448, Line 455: $X$ should be $x$ (lower-case).   * The first equation after line 458: There should not be an absolute value operator on the right hand side. If there is, then it should be \leq (after applying a triangle inequality)  * The last equation after line 458: I do not really understand how ||E \nabla \psi|| becomes ||\nabla \psi||. \nabla \psi is not deterministic, how come it is equal to its expectation?  * Eq 19: (and the equation after that) h should be h_s. Eq 20: h should be h_m. The same problem appears in the equations after Line 511. This should be also corrected in all the relevant parts of the main text.