Delocalization of bias in unadjusted Hamiltonian Monte Carlo and underdamped Langevin
Merged summary
TL;DR - This paper proves that unadjusted Hamiltonian Monte Carlo and underdamped Langevin samplers exhibit "delocalization of bias," meaning their sampling error can be controlled cheaply for low-dimensional marginals of high-dimensional distributions—reducing the need for costly Metropolis–Hastings correction.
- Extends the delocalization-of-bias phenomenon (previously shown for overdamped Langevin) to unadjusted HMC and underdamped Langevin, avoiding the small step sizes and iteration-complexity blowup that Metropolis–Hastings adjustment imposes.
- Main result: controlling the $W_2$ (Wasserstein-2) bias of any $K$-dimensional marginal of a high-dimensional target needs only $O(\sqrt{K})$ integration steps, up to $\log d$ factors, assuming weak or sparse interactions among variables.
- Handles the technical difficulty of discrete-time integrators via a broadly applicable matrix-polynomial framework characterizing their propagators.
- The underdamped result holds for all large friction parameters, implying the Leimkuhler–Matthews integrator for overdamped Langevin dynamics also shows delocalization of bias.
Sources (1)
Delocalization of bias in unadjusted Hamiltonian Monte Carlo and underdamped Langevin
TL;DR - This paper proves that unadjusted Hamiltonian Monte Carlo and underdamped Langevin samplers exhibit "delocalization of bias," meaning their sampling error can be controlled cheaply for low-dimensional marginals of high-dimensional distributions—reducing the need for costly Metropolis–Hastings correction.
- Extends the delocalization-of-bias phenomenon (previously shown for overdamped Langevin) to unadjusted HMC and underdamped Langevin, avoiding the small step sizes and iteration-complexity blowup that Metropolis–Hastings adjustment imposes.
- Main result: controlling the $W_2$ (Wasserstein-2) bias of any $K$-dimensional marginal of a high-dimensional target needs only $O(\sqrt{K})$ integration steps, up to $\log d$ factors, assuming weak or sparse interactions among variables.
- Handles the technical difficulty of discrete-time integrators via a broadly applicable matrix-polynomial framework characterizing their propagators.
- The underdamped result holds for all large friction parameters, implying the Leimkuhler–Matthews integrator for overdamped Langevin dynamics also shows delocalization of bias.