← All papers

Curvature Coupling Makes Langevin Bias Condition-Number Sharp

Abstract

The unadjusted Langevin algorithm (ULA) has stationary Wasserstein bias at most $6h\sqrt{\kappa\beta d}$ for a potential with strong convexity $\alpha$, smoothness $\beta$, and condition number $\kappa=\beta/\alpha$. Gaussian examples show that the step-size and dimension dependences are necessary, but their first-order bias is only $\sqrt{\operatorname{tr}H}/4$. They do not explain whether the remaining condition-number factor is real. We prove that it is. For every $d\geq4$ and $\kappa\geq8$, we construct an explicit $C^\infty$ potential whose best Hessian bounds are exactly $\alpha$ and $\beta$ and whose stationary bias satisfies $\liminf_{h\downarrow0}\frac{W_2(\widehat\pi_h,\pi)}h \geq c\sqrt{\kappa\beta d}.$ The mechanism is a bounded curvature coupling between one soft and one stiff coordinate. It converts an $O(h)$ perturbation of stiff-coordinate curvature into an $O(h\sqrt\kappa)$ soft-coordinate mean shift. Independent copies give the dimension factor. Thus the worst-case first-order bias is $\Theta(\sqrt{\kappa\beta d})$ under only strong convexity and gradient smoothness. The same family gives a high-accuracy iteration lower bound. For one fixed, bounded scale-free initialization, every constant-step ULA sequence attaining error $\epsilon\downarrow0$ requires $\Omega(\kappa\sqrt d \epsilon^{-1}\log(1/\epsilon))$ iterations. This matches the corresponding upper guarantee, including its initialization logarithm.

Keywords: Langevin algorithm, log-concave sampling, asymptotic bias, condition number, discretization error, strong convexity

Full text (PDF) · source repository · doi:10.5281/zenodo.21802801