Abstract
The problem of posterior inference is central to Bayesian statistics and a wealth of Markov Chain Monte Carlo (MCMC) methods have been proposed to obtain asymptotically correct samples from the posterior. As datasets in applications grow larger and larger, scalability has emerged as a central problem for MCMC methods. Stochastic Gradient Langevin Dynamics (SGLD) and related stochastic gradient Markov Chain Monte Carlo methods offer scalability by using stochastic gradients in each step of the simulated dynamics. While these methods are asymptotically unbiased if the stepsizes are reduced in an appropriate fashion, in practice constant stepsizes are used. This introduces a bias that is often ignored. In this paper we study the mean squared error of Lipschitz functionals in strongly log-concave models with i.i.d. data of growing data set size and show that, given a batchsize, to control the bias of SGLD the stepsize has to be chosen so small that the computational cost of reaching a target accuracy is roughly the same for all batchsizes. Using a control variate approach, the cost can be reduced dramatically. The analysis is performed by considering the algorithms as noisy discretisations of the Langevin SDE which correspond to the Euler method if the full data set is used. An important observation is that the scale of the step size is determined by the stability criterion if the accuracy is required for consistent credible intervals. Experimental results confirm our theoretical findings.
Introduction
In the era of "Big Data," Bayesian inference faces a significant scalability challenge. Traditional Markov Chain Monte Carlo (MCMC) methods, while asymptotically exact, require a full pass over the dataset of size $N$ at every iteration. This $O(N)$ per-step cost becomes prohibitive as $N$ grows. Stochastic Gradient Langevin Dynamics (SGLD) emerged as a promising alternative, utilizing mini-batches of size $n$ to estimate gradients, thereby reducing the per-step cost to $O(n)$.
However, this efficiency comes at a price. Unlike standard MCMC, SGLD with a constant stepsize is inherently biased—it doesn't sample from the exact posterior. While practitioners often assume that the computational gains of subsampling outweigh this bias, this paper rigorously quantifies the "true cost" of reaching a target accuracy. We demonstrate that for naive SGLD, the total computational complexity required to achieve a specific error level actually scales similarly to full-gradient methods, effectively negating the benefits of subsampling unless variance reduction techniques are employed.
Methodology: SGLD as a Noisy Discretization
The authors analyze SGLD through the lens of numerical analysis, treating it as a noisy Euler-Maruyama discretization of a Langevin Stochastic Differential Equation (SDE): $$dX_t = \nabla \log \pi(X_t) dt + \sqrt{2} dW_t$$ where $\pi$ is the target posterior. In the SGLD framework, the true gradient $\nabla \log \pi$ is replaced by a stochastic estimate $g(x)$.
The analysis focuses on strongly log-concave models, where the log-posterior is a smooth, bowl-shaped function. The performance metric used is the Mean Squared Error (MSE) of Lipschitz functionals, which accounts for both the discretization bias (from the stepsize $h$) and the variance introduced by the stochastic gradients (from the batch size $n$).
The "No Free Lunch" Theorem
The central theoretical contribution of this work is the analysis of how the stepsize $h$ must scale with the dataset size $N$ to maintain a target accuracy $\epsilon$. For a fixed batch size $n$, the authors show that to control the bias introduced by the stochastic gradient noise, the stepsize must be reduced as $O(N^{-2})$.
When calculating the total computational work (number of steps $\times$ cost per step), this leads to a surprising result: the total cost to reach an accuracy $\epsilon \approx 1/\sqrt{N}$ (the natural scale of posterior uncertainty) is $O(N \log N)$. This is essentially the same scaling as the Full-Gradient Euler method. In other words, for naive SGLD, you can choose to do many cheap steps or a few expensive ones, but the total "computational bill" remains the same. Furthermore, in the "big data" limit, the constraint on the stepsize is often dictated by numerical stability rather than just accuracy.
Breaking the Barrier with Control Variates
To overcome this limitation, the authors propose the use of Control Variates (CV). By centering the stochastic gradient estimate around the posterior mode (the MAP estimate) $\hat{\theta}$, the variance of the estimate can be significantly reduced. The modified gradient estimator takes the form: $$g_{cv}(x) = \nabla \log p(\hat{\theta}) + \frac{N}{n} \sum_{i \in \mathcal{S}} (\nabla \log p(x_i | x) - \nabla \log p(x_i | \hat{\theta}))$$ As the sampler approaches the mode, the variance of this estimator vanishes. This allows for much larger stepsizes $h$ that do not need to shrink aggressively as $N$ increases. Consequently, the computational cost to reach the target accuracy drops from $O(N \log N)$ to $O(\log N)$, assuming the mode has been pre-calculated. While finding the mode requires an initial $O(N)$ optimization, this is a one-time cost that pays off exponentially in the sampling phase.
Experimental Validation
The theoretical findings were validated using two primary experimental setups:
- Gaussian Toy Model: A 1D linear Gaussian model where the posterior is known analytically. Results confirmed that for a fixed computational budget, the Root Mean Squared Error (RMSE) is nearly identical regardless of whether small batch sizes with many steps or large batch sizes with fewer steps were used.
- Synthetic Logistic Regression: A multi-dimensional model ($d=3$) with dataset sizes $N$ ranging from $1,000$ to $100,000$. Despite logistic regression being only strictly (not necessarily strongly) log-concave, the $O(N)$ scaling of the naive method and the efficiency of the CV approach were clearly observed.
Conclusion
This research highlights a critical catch in the application of SGLD to large-scale Bayesian inference: without variance reduction, the perceived speedup of subsampling is often an illusion when high accuracy is required. The authors suggest that the perceived success of SGLD in machine learning might not be because it is a superior sampler, but because it acts as a form of stochastic optimization that averages over models. For true Bayesian inference, however, SGLD with control variates is essential to achieve genuine scalability.
Summary updated