Markov Chain Monte Carlo (MCMC) methods are fundamental for sampling from complex probability distributions, but many widely used algorithms either rely on gradients (like NUTS) and/or struggle with high-dimensional, multi-scale distributions. The No-Underrun Sampler (NURS) is a new approach that offers gradient-free, locally adaptive sampling, combining elements of Hit-and-Run and NUTS while remaining straightforward to implement and inherently parallelizable.
What is NURS?
NURS is an implementable approximation of Hit-and-Run, a coordinate-free Gibbs sampler that is theoretically powerful but often computationally infeasible. Like Hit-and-Run, NURS selects random directions uniformly from the unit sphere. However, to make the method implementable, NURS introduces additional structure in its “run” step:
- Locally Adaptive Exploration: NURS generates a discrete orbit in the chosen direction and dynamically adjusts its length to match the local scale of the target distribution.
- Precise State Selection: State selection is guided by exact density evaluations along the orbit using categorical sampling, ensuring that updates align closely with the target’s local geometry.
Why Does NURS Matter?
Many MCMC methods struggle with multi-scale distributions, where different regions require vastly different tuning parameters for efficient exploration. A classic example is Neal’s funnel, a well-known benchmark in Bayesian hierarchical inference. Most samplers fail to efficiently traverse both its narrow neck and broad mouth region effectively.
Empirical tests on Neal’s funnel show that while NURS is diffusive in narrow regions, its ballistic movement in broader regions offsets this, enabling efficient sampling across the distribution’s different scales. This behavior enables efficient sampling where many other gradient-free methods fail.
Mathematical Insights
Our recent paper provides a rigorous theoretical foundation for NURS, including:
- Quantitative Tuning Guidelines: NURS comes with clear, principled guidelines for tuning its parameters.
- Connections to Hit-and-Run: We formalize how NURS approximates Hit-and-Run while remaining implementable.
- Coupling Results: We extend known coupling results from Hit-and-Run to NURS in the Gaussian case, revealing that NURS inherits Hit-and-Run’s potential for fast convergence.
Looking Ahead
By providing an implementable approximation to Hit-and-Run, locally adapting to the different scales of the target, offering strong theoretical foundations, and demonstrating practical effectiveness in challenging multi-scale settings, NURS expands the toolkit for gradient-free MCMC methods. Despite the wide applicability and potential of gradient-free methods — this area remains relatively underexplored.
If you’re interested in learning more, feel free to check out the paper linked here—and stay tuned for further developments! We welcome your thoughts and ideas!