On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method

Ye He, Krishnakumar Balasubramanian, Murat A Erdogdu

Introduction

In machine learning and statistics, computing expectations of the form $\mathbb{E}_\pi[\phi(x)]$ is a foundational task, where $\pi$ represents a target probability distribution such as a posterior in Bayesian inference. Because analytical calculation of this integral is rarely possible, practitioners rely on Markov Chain Monte Carlo (MCMC) methods based on Langevin diffusions.

Recently, the Randomized Midpoint Method (RMM) has emerged as a highly regarded algorithm, achieving the theoretical lower bound for sampling complexity in strongly log-concave densities. However, generating a sample from $\pi$ is fundamentally different from calculating the average of a function over $\pi$ (numerical integration). This paper provides the first rigorous theoretical analysis bridging this gap, addressing two primary questions:

  1. Bias: Does the discrete-time algorithm settle into the exact target distribution $\pi$, or is its stationary distribution $\pi_h$ inherently biased?
  2. Inference: When using these samples to estimate an average, how can we quantify the fluctuation of that estimate? Establishing a Central Limit Theorem (CLT) is necessary to provide valid confidence intervals.

Methodology

This work is purely theoretical, focusing on proving mathematical properties—such as convergence rates, bias bounds, and limit theorems—rather than empirical benchmarking on specific datasets. The authors analyze two variants of the RMM algorithm:

  • RLMC (Randomized Langevin Monte Carlo): Based on overdamped Langevin dynamics, representing a simpler, first-order approach.
  • RULMC (Randomized Underdamped Langevin Monte Carlo): Based on underdamped dynamics, which incorporates a "momentum" term and is often faster in practice.

The core "Randomized Midpoint" trick approximates the integral of the diffusion by evaluating the gradient at a random point within each time step, rather than strictly at the beginning (as in the standard Euler method). To characterize the long-term behavior of these discrete Markov chains, the authors employ rigorous probabilistic tools, including ergodicity theory and the study of Poisson equations.

Key Findings

Ergodicity and the Constant Step-Size Bias

The authors prove that both RLMC and RULMC possess a unique stationary distribution and are geometrically ergodic under standard assumptions (specifically, a strongly log-concave potential and Lipschitz gradients).

Crucially, they demonstrate that maintaining a constant step-size ($h$) results in a permanent bias. The algorithm converges to a unique stationary distribution $\pi_h$, but $\pi_h$ is strictly not the target $\pi$. To achieve an unbiased result, the step-size must asymptotically decrease toward zero over time.

Underdamped Dynamics Yield Higher Accuracy

The theoretical bounds reveal that the underdamped method is significantly more accurate. The bias in the underdamped case is bounded by $W_2(\pi, \pi_h) \leq O(h^{1.5})$, compared to the overdamped bias of $W_2(\pi, \pi_h) \leq O(\sqrt{h})$. This confirms that the added complexity of simulating momentum pays substantial dividends in integration accuracy.

Asymptotic Normality and the CLT Trade-off

The paper successfully establishes Central Limit Theorems for both methods, allowing researchers to place formal "error bars" on expectations calculated via RMM.

However, this introduces a bias-variance trade-off governed by the step-size schedule. If the step-size decreases too slowly, the resulting normal distribution is shifted (biased). Conversely, if it decreases too quickly, the convergence rate of the estimator slows down. Interestingly, for the underdamped case, the authors identify a specific class of "constant" test functions where the convergence rate improves to $O(n^{5/8})$, outpacing the standard $O(n^{1/2})$ or $O(n^{1/3})$ rates typical of other discretizations.

Limitations and Future Directions

While the theoretical guarantees are robust, they rely on strong assumptions: the potential function $f$ must be $m$-strongly convex and possess $M$-Lipschitz gradients. In practice, many real-world energy landscapes—particularly in deep learning—do not satisfy these conditions globally.

Furthermore, the superior $O(n^{5/8})$ convergence rate for the underdamped CLT applies only to a restricted class of test functions; for general functions, the rate remains comparable to simpler Euler-based methods.

Looking forward, the authors suggest that exploring higher-order discretization schemes or alternative randomization strategies could further mitigate bias without sacrificing the optimal sampling complexity that makes the Randomized Midpoint Method so attractive.

Summary updated

Abstract

The randomized midpoint method, proposed by (Shen and Lee, 2019), has emerged as an optimal discretization procedure for simulating the continuous time underdamped Langevin diffusion. In this paper, we analyze several probabilistic properties of the randomized midpoint discretization method, considering both overdamped and underdamped Langevin dynamics. We first characterize the stationary distribution of the discrete chain obtained with constant step-size discretization and show that it is biased away from the target distribution. Notably, the step-size needs to go to zero to obtain asymptotic unbiasedness. Next, we establish the asymptotic normality of numerical integration using the randomized midpoint method and highlight the relative advantages and disadvantages over other discretizations. Our results collectively provide several insights into the behavior of the randomized midpoint discretization method, including obtaining confidence intervals for numerical integrations.
BibTeX
@inproceedings{he2020ergodicity,
  author = {Ye He and Krishnakumar Balasubramanian and Murat A Erdogdu},
  title = {{On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=VyUUqCjOEuY},
}
Figure