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 \(\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}(d^{1/2}) \) . 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}(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 \(\widetilde{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.