On the Convergence of Hamiltonian Monte Carlo with Stochastic Gradients

Difan Zou, Quanquan GuICML 2021 · OpenReview

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:

  1. The stochastic gradient estimator is unbiased.
  2. 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).

Convergence of different HMC algorithms measured by L2 distance for dataset sizes n=500 and n=5000. SG-HMC exhibits significantly higher error compared to variance-reduced methods.

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

Abstract

Hamiltonian Monte Carlo (HMC), built based on the Hamilton’s equation, has been witnessed great success in sampling from high-dimensional posterior distributions. However, it also suffers from computational inefficiency, especially for large training datasets. One common idea to overcome this computational bottleneck is using stochastic gradients, which only queries a mini-batch of training data in each iteration. However, unlike the extensive studies on the convergence analysis of HMC using full gradients, few works focus on establishing the convergence guarantees of stochastic gradient HMC algorithms. In this paper, we propose a general framework for proving the convergence rate of HMC with stochastic gradient estimators, for sampling from strongly log-concave and log-smooth target distributions. We show that the convergence to the target distribution in $2$-Wasserstein distance can be guaranteed as long as the stochastic gradient estimator is unbiased and its variance is upper bounded along the algorithm trajectory. We further apply the proposed framework to analyze the convergence rates of HMC with four standard stochastic gradient estimators: mini-batch stochastic gradient (SG), stochastic variance reduced gradient (SVRG), stochastic average gradient (SAGA), and control variate gradient (CVG). Theoretical results explain the inefficiency of mini-batch SG, and suggest that SVRG and SAGA perform better in the tasks with high-precision requirements, while CVG performs better for large dataset. Experiment results verify our theoretical findings.
BibTeX
@inproceedings{zou2021convergence,
  author = {Difan Zou and Quanquan Gu},
  title = {{On the Convergence of Hamiltonian Monte Carlo with Stochastic Gradients}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=gc0ylnIN3J},
}
Figure