Stochastic Gradient
Stochastic Gradient Markov Chain Monte Carlo (SG-MCMC) algorithms have become increasingly popular for Bayesian inference in large-scale applications. Even though these methods have proved useful in several scenarios, their performance is often limited by their bias. In this study, we propose a novel sampling algorithm that aims to reduce the bias of SG-MCMC while keeping the variance at a reasonable level. Our approach is based on a numerical sequence acceleration method, namely the Richardson-Romberg extrapolation, which simply boils down to running almost the same SG-MCMC algorithm twice in parallel with different step sizes. We illustrate our framework on the popular Stochastic Gradient Langevin Dynamics (SGLD) algorithm and propose a novel SG-MCMC algorithm referred to as Stochastic Gradient Richardson-Romberg Langevin Dynamics (SGRRLD). We provide formal theoretical analysis and show that SGRRLD is asymptotically consistent, satisfies a central limit theorem, and its non-asymptotic bias and the mean squared-error can be bounded. Our results show that SGRRLD attains higher rates of convergence than SGLD in both finite-time and asymptotically, and it achieves the theoretical accuracy of the methods that are based on higher-order integrators. We support our findings using both synthetic and real data experiments.
Stochastic Gradient MCMC (SG-MCMC) methods provide an easy way to perform Bayesian posterior inference in large datasets, and have received a lot of interest from the research community in the last few years. One drawback of these methods is that they are asymptotically biased, meaning they do not converge exactly to the posterior distribution.  This paper shows that the bias can be reduced by a technique called Richardson-Romberg extrapolation.   The basic idea is very simple: Two SG-MCMC chains are run in parallel, with Chain 2 having half the step size of Chain 1. Also chain 2 is run for twice the number of steps as Chain 1. The injected Gaussian noise in the chains are correlated, with alpha_k = (beta_{2*k-1) + beta_{2*k})/sqrt(2) where alpha_k and beta_k are the injected Gaussian noise at time step k in Chains 1 and 2 respectively. Then, to compute the expectation of a function f w.r.t. the target distribution of the chains, one simply subtracts the estimate computed using samples from Chain 1 from the estimate computed using Chain 2. The resulting estimate is shown to have lower bias O(gamma^2) compared to O(gamma) obtained from Chain 1 or 2 alone (where gamma is the step size). They also prove a similar reduction in MSE of the estimates.
I like the fact that the method is very simple to understand and implement (see my summary), and does not require any major changes to the base SG-MCMC algorithm. Also, this seems very general and applies to a large class of SG-MCMC algorithms, and is therefore potentially very impactful to the Stochastic Gradient MCMC community.  Novelty: Although Richardson-Romberg extrapolation is well known in numerical analysis, it is not widely known in the machine learning / stochastic gradient MCMC community.   Clarity: The paper is well written and the presentation is clear.   Comments/questions:  - Can this technique be directly applied to all SG-MCMC methods? If not, are there specific conditions other than that the SG MCMC algorithm satisfies the bound in section 2.2: pi_gamma(f) = pi(f) + C * gamma + O(gamma^2)?  - Can this method be applied to other non-stochastic gradient, but approximate MCMC schemes, e.g. sub-sampling based Metropolis-Hastings tests? What about Distributed SGLD? - Since one chain has to run for twice as long as the other, there is a lot of wasted computation where the chain with the bigger step size stays idle. Instead, is it possible to use 3 chains, one chain with a step size of gamma, and two chains with step sizes gamma/2 each, and run all of them for the same number of steps? Does this increase the variance of the estimate? - Is there an extension of this method to more than 2 step sizes? - The injected noise in the chains have to be correlated, but I didnt quite understand the effect of correlation between mini-batches . Is the variance lowest when using the same batch for the k^th iteration of chain 1, and the 2k-1^th and the 2k^th iteration of chain 2? Or is the effect of this correlation negligible? - I think the matrix factorization experiment (figure 5) should be run until convergence, and you should also compare to SGD. The current plot shows that your method works better than SGLD, but it would be nice to show that your method works better than SGLD in a setting where being Bayesian is advantageous (i.e. better than SGD). Bayesian matrix factorization is not widely used in practice, so showing some numbers will convince more people to adopt your method. Also having an SGD plot as control will put the final errors of SGRRLD and SGLD in better perspective. - Although the method is easy and clearly presented, an algorithm box could make the paper more accessible to a wider audience. I believe many practitioners will not read through the more theoretical parts, so pseudo code presented early on in the paper will enable readers who are not very familiar with this area to try out your method without understanding the more challenging parts.