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:
- Bias: Does the discrete-time algorithm settle into the exact target distribution $\pi$, or is its stationary distribution $\pi_h$ inherently biased?
- 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