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

Source 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 $σ$-strongly log-concave target $π(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 $Π_0$ denotes an appropriately selected reference measure. When $π$ 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 $Π_τ$ denotes another correspondingly chosen reference measure at time $τ> 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.