Introduction
Hamiltonian Monte Carlo (HMC) is widely regarded as the "gold standard" for sampling from complex, high-dimensional distributions. By leveraging Hamiltonian dynamics, it can take large steps through the state space with high acceptance rates. However, HMC suffers from a significant "Big Data" bottleneck: it requires calculating the gradient of the log-posterior over the entire dataset at every single step.
To scale HMC, researchers often turn to stochastic gradients (mini-batches). Unfortunately, this introduces a major theoretical hurdle. Standard HMC relies on a Metropolis-Hastings (MH) correction step to remain exact. With stochastic gradients, the MH step becomes computationally intractable and breaks the algorithm's mathematical reversibility. Consequently, most existing HMC theory applies only to full-gradient versions.
This paper bridges that gap by providing the first general theoretical framework for proving the convergence of stochastic gradient HMC (SG-HMC) without the MH step, specifically for strongly log-concave and log-smooth distributions.
A General Framework for Convergence
The authors propose a comprehensive framework to analyze convergence using the 2-Wasserstein distance. Their core theoretical contribution proves that an SG-HMC algorithm will converge to the target distribution with a predictable error, provided two conditions are met:
- The stochastic gradient estimator is unbiased.
- Its variance is bounded along the algorithm's trajectory.
Using this framework, the paper analyzes four specific stochastic gradient estimators:
- Mini-batch Stochastic Gradient (SG): The standard approach using a random subset of data.
- Stochastic Variance Reduced Gradient (SVRG): Uses a periodically updated reference point to reduce variance.
- Stochastic Average Gradient (SAGA): Maintains a table of previous gradients to achieve variance reduction.
- Control Variate Gradient (CVG): Uses a fixed reference point (typically the MAP estimate) to stabilize gradients.
Key Insights: The Variance-Precision Trade-off
The theoretical analysis reveals that sampling error is directly governed by the variance of the gradient estimator. Smaller variance allows for larger step sizes, accelerating the mixing of the Markov chain.
This leads to several critical insights regarding algorithm selection:
- SG-HMC’s Inefficiency: Standard mini-batch SG-HMC often performs poorly because its gradient complexity scales linearly with the dataset size ($n$) to maintain a specific error level.
- The Power of Control Variates (CVG): CVG-HMC is highly effective for massive datasets because its gradient complexity is independent of the dataset size ($O(1/\epsilon^2)$) for a fixed error $\epsilon$.
- SVRG/SAGA for High Precision: For tasks requiring extremely high precision (small $\epsilon$), SVRG and SAGA outperform CVG. Their complexity scales better with respect to the error term ($O(\epsilon^{-2/3})$ vs $O(\epsilon^{-2})$).
Theoretical Complexity Bounds
The paper provides a comprehensive comparison of the number of gradient evaluations needed to reach a target accuracy:
| Algorithm | Gradient Complexity |
|---|---|
| SG-HMC | $\tilde{O}(n/\epsilon^2)$ |
| SVRG-HMC | $\tilde{O}(n^{2/3}/\epsilon^{2/3} + 1/\epsilon)$ |
| SAGA-HMC | $\tilde{O}(n^{2/3}/\epsilon^{2/3} + 1/\epsilon)$ |
| CVG-HMC | $\tilde{O}(1/\epsilon^2)$ |
Experimental Validation
The authors evaluated these theoretical findings using both synthetic data (Multivariate Gaussian) and real-world data (Bayesian Logistic Regression on the Covtype dataset).
The experimental results strongly confirm the theoretical bounds. As shown in the convergence plots above, SG-HMC exhibits a significantly higher bias and struggles to converge tightly compared to the other three methods. SVRG-HMC performs exceptionally well on smaller subsets, while CVG-HMC becomes increasingly efficient and competitive as the dataset size grows, validating its $O(1)$ dependence on $n$.
Limitations and Future Directions
The primary limitation of this work is the assumption of strong log-concavity. While this is a standard and necessary starting point for rigorous convergence theory, many real-world posterior distributions—especially those in deep neural networks—are non-convex and multi-modal.
A promising future direction suggested by the authors is exploring how to incorporate a "stochastic" version of the Metropolis-Hastings correction. While theoretically and practically challenging, this could potentially mitigate the bias introduced by stochastic gradients even further, extending the reliability of HMC in large-scale machine learning applications.
Summary updated