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) \| \pi) \leq e^{-\sqrt{\sigma} t}\operatorname{KL}(\operatorname{Law}(Q_{0}, P_{0})\, \|\, \Pi_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) \| \pi) \leq \frac{\tau^2}{t^2}\operatorname{KL}(\operatorname{Law}(Q_{\tau}, P_{\tau})\, \|\, \Pi_{\tau}) \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.