In high-dimensional Bayesian inference, Markov Chain Monte Carlo (MCMC) samplers face a "Goldilocks" problem. If the proposal step size is too large, the algorithm frequently explores regions of low probability, leading to rejected moves and a stagnant chain. If the step size is too small, the chain accepts almost every move but explores the space with the agonizing slowness of a random walk.
Optimal scaling research provides the mathematical "instruction manual" for finding the perfect middle ground. By analyzing how the dimensionality ($d$) of a problem affects the behavior of the Metropolis-Hastings correction, researchers have derived specific scaling laws and target acceptance rates that maximize the speed of exploration.
The Fundamental Trade-off
The efficiency of an MCMC algorithm is typically measured by its "mixing time"—how many steps it takes to forget its starting position and accurately represent the target distribution. As Alexandros Beskos, Andrew M. Stuart, and Gareth O. Roberts demonstrate in Optimal scalings for local Metropolis–Hastings chains on nonproduct targets in high dimensions, this efficiency is a direct function of the proposal variance.
In high dimensions, the volume of the "shell" where most of the probability mass resides becomes increasingly thin. To stay within this shell, the proposal variance must be scaled inversely with the dimension. If we don't scale the step size down as $d$ increases, the discretization error of our proposal grows, and the probability of acceptance vanishes.
The 0.234 Rule for Random Walks
The most famous result in this field is the "0.234 rule." For a standard Random Walk Metropolis (RWM) algorithm, the optimal strategy is to scale the proposal variance as $O(d^{-1})$. YF Liu, Andrew M. Stuart, and Natesh S. Pillai showed in SPDE limits of the random walk Metropolis algorithm in high dimensions that under this scaling, the discrete chain converges to a continuous Langevin diffusion.
The "speed" of this diffusion is maximized when the algorithm targets an acceptance rate of approximately 23.4%. This specific number represents the point where the benefit of taking larger steps is exactly cancelled out by the cost of more frequent rejections.
Scaling Gradient-Informed Samplers
When we use gradients to "push" the proposal toward regions of higher probability, we can afford to take much larger steps.
- MALA: The Metropolis-Adjusted Langevin Algorithm (MALA) uses first-order gradients. Alain Durmus and Gareth O. Roberts found in Fast Langevin based algorithm for MCMC in high dimensions that MALA's step size scales as $d^{-1/3}$, with an optimal acceptance rate of 0.574 (or 0.704 for higher-order proposals).
- HMC: Hybrid (or Hamiltonian) Monte Carlo uses physics-inspired trajectories to make even bolder moves. In Optimal tuning of the Hybrid Monte-Carlo Algorithm, Alexandros Beskos and colleagues proved that HMC's leapfrog step size should scale as $d^{-1/4}$, leading to an optimal acceptance rate of 0.651.
These results show a clear trend: the more information the sampler uses about the target's geometry, the more slowly the step size must shrink as dimensions grow, and the higher the optimal acceptance rate becomes.
The Impact of Non-Smoothness
The "rules of thumb" change when the target distribution is not smooth. For example, Vu C. Dinh and Lam S. Ho point out in Hamiltonian Monte Carlo on ReLU Neural Networks is Inefficient that the non-differentiability of ReLU activations breaks the standard $d^{-1/4}$ scaling of HMC. Because the "energy" of the system jumps at the ReLU boundaries, the integrator error becomes much larger, forcing the step size to scale more aggressively at $d^{-1/2}$.
Similarly, for non-smooth targets like the Laplace distribution (common in Lasso regression), Francesca Crucinio and Alain Durmus discovered in Optimal Scaling Results for Moreau-Yosida Metropolis-adjusted Langevin Algorithms a unique $d^{-2/3}$ scaling regime.
Scaling Out of Stationarity
Most scaling results assume the chain has already reached its target distribution (stationarity). However, the "warm-up" phase—where the chain is still traveling toward the high-probability region—requires different tuning.
Juan Kuntz and Michela Ottobre showed in Non-stationary phase of the MALA algorithm that when a sampler is far from the target, it is much more sensitive to discretization errors. In this phase, MALA requires a more restrictive $d^{-1/2}$ scaling to avoid rejection, making the journey to the "target" significantly slower than the exploration of the target itself.
Why It Works: The Diffusion Limit
The intuition behind these specific numbers (0.234, 0.651) comes from the Diffusion Limit. When we scale the step size correctly, the discrete MCMC moves begin to look like a continuous stochastic process. By maximizing the "speed" (the diffusion coefficient) of this limiting process, we find the acceptance rate that allows the chain to travel the furthest distance in the shortest amount of time.
Essentially, optimal scaling transforms the discrete, high-dimensional sampling problem into a continuous optimization problem, providing a rigorous way to bypass the curse of dimensionality.