Faster high-accuracy log-concave sampling via algorithmic warm starts
Jason M. Altschuler, Sinho Chewi · 2023
It is a fundamental problem to understand the complexity of high-accuracy sampling from a strongly log-concave density $\pi$ on $\mathbb{R}^{d}$. Indeed, in practice, high-accuracy samplers such as the Metropolis-adjusted Langevin algorithm (MALA) remain the de facto gold standard; and in theory, via the proximal sampler reduction, it is understood that such samplers are key for sampling even beyond log-concavity (in particular, for sampling under isoperimetric assumptions).This paper improves the dimension dependence of this sampling problem to $\widetilde{O}\left(d^{1 / 2}\right)$, whereas the previous best result for MALA was $\widetilde{O}(d)$. This closes the long line of work on the complexity of MALA, and moreover leads to state-of-the-art guarantees for high-accuracy sampling under strong log-concavity and beyond (thanks to the aforementioned reduction).Our starting point is that the complexity of MALA improves to $\widetilde{O}\left(d^{1 / 2}\right)$, but only under a warm start (an initialization with constant Rényi divergence w.r.t. $\pi$). Previous algorithms for finding a warm start took $O(d)$ time and thus dominated the computational effort of sampling. Our main technical contribution resolves this gap by establishing the first $\widetilde{O}\left(d^{1 / 2}\right)$ Rényi mixing rates for the discretized underdamped Langevin diffusion. For this, we develop new differential-privacy-inspired techniques based on Rényi divergences with Orlicz-Wasserstein shifts, which allow us to sidestep longstanding challenges for proving fast convergence of hypocoercive differential equations.