The Fenchel Game of Underdamped Langevin Dynamics: Insights into Accelerated Convergence

Abstract

For $(Q_t,P_t)$ governed by suitably damped underdamped Langevin dynamics, we quantify the convergence in KL divergence of the positional marginal to a $\sigma$-strongly log-concave target $\pi (dq)=\frac{1}{Z}{e}^{-V(q)}dq$ as \begin{align*} \operatorname{KL}(\operatorname{Law}(Q_t) \| π) \leq e^{-\sqrtσ t}\operatorname{KL}(\operatorname{Law}(Q_{0}, P_{0})\, \|\, Π_0), \end{align*} where ${\Pi }_0$ denotes an appropriately selected reference measure. When $\pi$ is merely log-concave, the estimate \begin{align*} \operatorname{KL}(\operatorname{Law}(Q_t) \| π) \leq \frac{τ^2}{t^2}\operatorname{KL}(\operatorname{Law}(Q_τ, P_τ)\, \|\, Π_τ) \end{align*} is derived, where ${\Pi }_{\tau }$ denotes another correspondingly chosen reference measure at time $\tau >0$. Both rates match precisely the canonical rates of the corresponding accelerated gradient flows in ${\mathbb{R}}^d$. They are achieved by the novel interpretation of the underdamped Langevin dynamics as a combination of strategies in an online sampling game and by estimating the KL divergence using a cost function informed by fictitious competitors.