Accelerating MCMC for Ill Conditioned Geometries

26 concepts22 papers2 proposals

When drawing samples from a high-dimensional probability distribution, the shape of the distribution dictates the speed of the sampler. The ideal distribution is isotropic—perfectly spherical, changing at the same rate in every direction. In reality, real-world target distributions are often ill-conditioned. They feature extreme differences in scale across different dimensions, resembling highly elongated valleys or thin needles.

In these anisotropic landscapes, standard Markov Chain Monte Carlo (MCMC) algorithms like Langevin Monte Carlo (LMC) and Hamiltonian Monte Carlo (HMC) slow down dramatically. To understand why, we must look at how the geometry of a distribution constrains the step size of a sampler, and how a new wave of algorithmic strategies aims to break this bottleneck.

The Tyranny of the Condition Number

To navigate a probability landscape safely, a gradient-based sampler must choose a step size $\eta$ that respects the steepest direction of the distribution. If the step size is too large, the algorithm will overshoot the narrow walls of the valley, causing numerical instability and wild divergence. Consequently, the step size is restricted by the maximum smoothness parameter $L$ (the worst-case curvature), typically requiring $\eta \propto 1/L$.

However, the sampler's goal is to explore the entire distribution, including its longest, flattest dimensions, which are governed by the strong concavity parameter $m$ (the minimum curvature). If the sampler takes uniform steps of size $1/L$ across all dimensions, it will require an agonizingly large number of iterations to traverse the length of the distribution.

This geometric disparity is quantified by the condition number $\kappa = L/m$. As the condition number grows, the distribution becomes more ill-conditioned, and standard samplers stall.

Isotropic (Low κ):          Ill-Conditioned (High κ):
      ◯                      (=================================)
Step size matches scale      Step size restricted by narrow width;
in all directions.           exploring the length takes too long.

This sensitivity is not just an empirical nuisance; it is a fundamental theoretical barrier. Santosh S. Vempala et al. demonstrated in Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions that even for well-behaved, strongly log-concave distributions, the relaxation time of HMC scales linearly with $\kappa$. For other continuous-time frameworks like the zigzag sampler, Jianfeng Lu 0001 et al. showed in Complexity of zigzag sampling algorithm for strongly log-concave distributions that the computational complexity can scale quadratically ($O(\kappa^2 \sqrt{d})$). Even when leveraging modern parallel computing architectures, Huanjian Zhou et al. note in Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models that parallel iterations still suffer from a linear dependence on $\kappa$, making highly skewed distributions an open challenge for parallelization.

To overcome this scaling bottleneck, researchers have developed several distinct strategies to decouple the sampler's step size from the global worst-case curvature.

Strategy 1: Coordinate-Wise Adaptation

If a uniform step size across all dimensions forces the sampler to obey the strictest global limit, why not update dimensions independently?

This is the intuition behind coordinate-wise sampling. Instead of computing a full gradient update that is instantly bottlenecked by the steepest direction, we can select a single coordinate at random and update it. If that coordinate corresponds to a flat, wide dimension of the distribution, the algorithm can safely take a massive step without risking instability.

Zhiyan Ding et al. formalized this mechanism in Random Coordinate Langevin Monte Carlo (RC-LMC) and its momentum-based counterpart, Random Coordinate Underdamped Langevin Monte Carlo (RC-ULMC). By updating only one randomly selected coordinate at a time, these algorithms adaptively match the step size to the local coordinate-wise curvature. This coordinate-wise freedom allows the sampler to traverse less sensitive dimensions rapidly, yielding significant speedups for highly skewed target distributions.

Strategy 2: Advanced Path Discretization

Another approach targets the mathematical errors introduced when we translate continuous physical diffusions (like Langevin or Hamiltonian dynamics) into discrete computer steps. Standard discretization schemes assume that the gradient of the distribution remains relatively constant over a single step. In an ill-conditioned landscape, this assumption fails catastrophically because the gradient changes rapidly across the narrow dimensions.

To fix this, the authors of The Randomized Midpoint Method for Log-Concave Sampling replaced deterministic discretization steps with a randomized, unbiased integral estimator. By evaluating the gradient at a randomly sampled intermediate point along the path, the algorithm cancels out systematic discretization errors. This simple change dramatically improves the sampler's sensitivity to the condition number, reducing the dependence to nearly linear ($\tilde{O}(\kappa^{7/6})$) without requiring higher-order smoothness assumptions.

Alternatively, one can vary the duration of the simulation itself. In standard HMC, the algorithm simulates physical trajectories for a fixed "integration time." If the distribution is highly stretched, a fixed integration time can cause the sampler to get caught in periodic, redundant orbits. Jun-Kun Wang et al. solved this in Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time by varying the integration time according to the roots of Chebyshev polynomials. This variation ensures that the sampler probes multiple frequencies of the target landscape, achieving an acceleration effect analogous to momentum methods in convex optimization.

Strategy 3: Reshaping Space via Non-Euclidean Geometry

Instead of modifying how the sampler moves through flat Euclidean space, we can warp the space itself to make the distribution appear more isotropic.

One way to achieve this is through Bregman divergences. By replacing standard Euclidean distances with a distance metric derived from a strictly convex function, the sampler adapts to the underlying geometry of the target density. Han Liu et al. utilized this in Bregman Proximal Langevin Monte Carlo via Bregman-Moreau Envelopes, creating a framework where the sampler inherently accommodates non-smooth and highly anisotropic variances across dimensions.

When the distribution is confined by complex boundaries or extreme scaling, we can map the problem onto a Riemannian manifold. Yin Tat Lee et al. demonstrated in Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space that by incorporating constraints directly into the manifold's metric tensor, the sampler can seamlessly navigate spaces where variables span multiple orders of magnitude.

A complementary approach introduces Hessian-driven damping. In underdamped Langevin dynamics, momentum helps the sampler glide through flat regions. However, momentum can cause the sampler to oscillate wildly when it hits a steep wall. To counteract this, Stanley Osher et al. proposed Gradient-Adjusted Underdamped Langevin (GAUL) dynamics in Gradient-adjusted underdamped Langevin dynamics for sampling. GAUL incorporates the Hessian of the distribution directly into the damping term, dynamically increasing friction in steep directions to suppress oscillations while preserving momentum along the flat, elongated paths.

Standard Momentum:              Hessian-Driven Damping (GAUL):
     \      /                        \              /
      \    /                          \____________/
       \  /                           
  Wild oscillations              Friction increases near walls;
  against steep walls.           smooth transit along the floor.

Strategy 4: Learning the Geometry

When a distribution's geometry is too intricate or non-linear to be resolved by analytical transformations, we can use machine learning to discover the optimal sampling coordinates.

In Generalizing Hamiltonian Monte Carlo with Neural Networks, Daniel Levy et al. replaced the fixed, physics-inspired updates of traditional HMC with trainable neural networks. By optimizing these networks to maximize the expected squared jump distance, the algorithm automatically learns a custom, non-linear warping of the space. The resulting sampler learns to take large steps along the unconstrained, flat dimensions of ill-conditioned distributions while automatically slowing down to safely negotiate highly sensitive regions.

Key Foundational Work

Underdamped Langevin MCMC: A non-asymptotic analysis (2018) — contributed 1 concept elements to this direction.
Generalizing Hamiltonian Monte Carlo with Neural Networks (2018) — contributed 1 concept elements to this direction.
Magnetic Hamiltonian Monte Carlo (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_ill_conditioned_distribution_sampling_b51ebc65,
  title = {ill-conditioned distribution sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ill-conditioned-distribution-sampling/rdr_b51ebc6547ec4e178f680ad51d434d4d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_ill_conditioned_distribution_sampling_b51ebc65_v1,
  title = {ill-conditioned distribution sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ill-conditioned-distribution-sampling/rdr_b51ebc6547ec4e178f680ad51d434d4d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake