A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetry
This provides theoretical guarantees for sampling algorithms in machine learning and statistics, particularly for non-log-concave densities, but is incremental as it builds on prior work to refine mixing bounds.
The paper tackles the problem of analyzing the mixing time of the Metropolis-Adjusted Langevin Algorithm (MALA) for sampling from target densities in high-dimensional spaces, establishing a mixing time bound of O(((LΥ)^(1/2) / ψ_μ^2) log(1/ε)) under smoothness and isoperimetry assumptions, which extends beyond log-concave settings and depends on Υ rather than Ld.
We study the mixing time of Metropolis-Adjusted Langevin algorithm (MALA) for sampling a target density on $\mathbb{R}^d$. We assume that the target density satisfies $ψ_μ$-isoperimetry and that the operator norm and trace of its Hessian are bounded by $L$ and $Υ$ respectively. Our main result establishes that, from a warm start, to achieve $ε$-total variation distance to the target density, MALA mixes in $O\left(\frac{(LΥ)^{\frac12}}{ψ_μ^2} \log\left(\frac{1}ε\right)\right)$ iterations. Notably, this result holds beyond the log-concave sampling setting and the mixing time depends on only $Υ$ rather than its upper bound $L d$. In the $m$-strongly logconcave and $L$-log-smooth sampling setting, our bound recovers the previous minimax mixing bound of MALA~\cite{wu2021minimax}.