Faster high-accuracy log-concave sampling via algorithmic warm starts

It is a fundamental problem to understand the complexity of high-accuracy sampling from a strongly log-concave density π on ℝ 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 article improves the dimension dependence of this sampling problem to \ (O (d^1/2) \). The previous best result for MALA was \ (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 \ (O (d^1/2) \), but only under a warm start (an initialization with constant Rényi divergence w. r. t. π). 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 \ (O (d^1/2) \) 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.