English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the mixing time of the Metropolis-adjusted Langevin algorithm (MALA)for sampling from a log-smooth and strongly log-concave distribution. Weestablish its optimal minimax mixing time under a warm start. Our maincontribution is two-fold. First, for a $d$-dimensional log-concave density withcondition number $\kappa$, we show that MALA with a warm start mixes in $\tildeO(\kappa \sqrt{d})$ iterations up to logarithmic factors. This improves uponthe previous work on the dependency of either the condition number $\kappa$ orthe dimension $d$. Our proof relies on comparing the leapfrog integrator withthe continuous Hamiltonian dynamics, where we establish a new concentrationbound for the acceptance rate. Second, we prove a spectral gap based mixingtime lower bound for reversible MCMC algorithms on general state spaces. Weapply this lower bound result to construct a hard distribution for which MALArequires at least $\tilde \Omega (\kappa \sqrt{d})$ steps to mix. The lowerbound for MALA matches our upper bound in terms of condition number anddimension. Finally, numerical experiments are included to validate ourtheoretical results.

Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling