Abstract
The randomized midpoint method, proposed by Shen and Lee (2019), has emerged as an optimal discretization procedure for simulating continuous-time Langevin diffusions. Focusing on the case of strongly convex and smooth potentials, this paper analyzes several probabilistic properties of the randomized midpoint discretization method for both overdamped and underdamped Langevin diffusions. 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, requiring the step-size to vanish for asymptotic unbiasedness. Next, we establish the asymptotic normality for 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 the ability to obtain confidence intervals for numerical integrations.
Introduction
In fields ranging from Bayesian statistics to molecular dynamics, a fundamental challenge is the computation of expectations: the average value of a function $\phi(x)$ over a target probability distribution $\pi$. Because these integrals are rarely analytically tractable, researchers rely on Markov Chain Monte Carlo (MCMC) methods to simulate particles moving according to Langevin diffusion.
Recently, the "randomized midpoint method" was introduced as a discretization technique superior to the standard Euler-Maruyama approach. While previous literature established this method as information-theoretically optimal for sampling—meaning it reaches the target distribution in fewer iterations—its performance regarding numerical integration remained uncharacterized. This paper fills that gap by analyzing the ergodicity, bias, and asymptotic normality of the method.
The Randomized Midpoint Discretization
The authors evaluate two primary variants of the algorithm:
- Randomized Langevin Monte Carlo (RLMC): Based on first-order, overdamped Langevin dynamics.
- Randomized Underdamped Langevin Monte Carlo (RULMC): Based on second-order dynamics that incorporate momentum, often leading to faster convergence in practice.
The core innovation of these methods lies in their gradient handling. Unlike standard schemes that evaluate the gradient only at the current state, the randomized midpoint method selects a random time point within the discretization interval, estimates the position at that point, and uses the resulting gradient to update the state. This analysis utilizes Lyapunov conditions to ensure the chain remains stable and Stein’s method (Poisson equations) to characterize the fluctuations of integration errors.
Ergodicity and Bias Analysis
A critical finding of this research is the characterization of the stationary distribution. The authors prove that for both RLMC and RULMC, the discrete chain converges to a unique stationary distribution under constant step sizes. However, this stationary distribution is inherently biased away from the true target distribution $\pi$.
To achieve asymptotic unbiasedness, the step-size $h$ must approach zero. The degree of bias differs significantly between the two methods:
- RLMC (Overdamped) Bias: Scales at $O(\sqrt{h})$.
- RULMC (Underdamped) Bias: Scales at $O(h^{1.5})$.
This suggests that the underdamped version is significantly more accurate for a fixed step size, as the inclusion of momentum allows the chain to stay much closer to the target distribution.
Asymptotic Normality and Integration
The paper establishes a Central Limit Theorem (CLT) for the randomized midpoint integrator. It proves that as the number of steps $n$ goes to infinity, the error of the integrator follows a normal distribution. This is a vital result for practitioners, as it provides the theoretical justification needed to construct reliable confidence intervals for MCMC estimates.
Furthermore, the authors identify a specific convergence advantage for RULMC. For certain classes of test functions, the underdamped method achieves a convergence rate of $O(n^{-5/8})$. This is a notable improvement over the $O(n^{-1/3})$ rate typically associated with standard overdamped Langevin schemes. However, the authors note a trade-off: while the method is optimal for sampling the distribution, the variance of the integrator can still be a bottleneck for general, "black-box" test functions.
Conclusion and Limitations
This study provides a rigorous theoretical foundation for using randomized midpoint methods in numerical integration. While the results are promising, they are currently bounded by several constraints:
- Strong Convexity: The proofs assume the potential function is strongly convex and smooth, which may not apply to the multi-modal or non-convex landscapes found in deep learning.
- Function Specificity: The accelerated $O(n^{-5/8})$ rate is not universal and depends on the properties of the test function $\phi$.
- Dimensionality: While the convergence rates are established, the constants involved are dimension-dependent, leaving the "many-particle" limit as a subject for future research.
By establishing ergodicity and asymptotic normality, this work moves the randomized midpoint method from a theoretical sampling curiosity to a practical tool for robust statistical inference.
Summary updated