Paper ID: 2410.02979

From Optimization to Sampling via Lyapunov Potentials

August Y. Chen, Karthik Sridharan

We study the problem of sampling from high-dimensional distributions using Langevin Dynamics, a natural and popular variant of Gradient Descent where at each step, appropriately scaled Gaussian noise is added. The similarities between Langevin Dynamics and Gradient Flow and Gradient Descent leads to the natural question: if the distribution's log-density can be optimized from all initializations via Gradient Flow and Gradient Descent, given oracle access to the gradients, can we efficiently sample from the distribution using discrete-time Langevin Dynamics? We answer this question in the affirmative for distributions that are unimodal in a particular sense, at low but appropriate temperature levels natural in the context of both optimization and real-world applications, under mild regularity assumptions on the measure and the convergence rate of Gradient Flow. We do so by using the results of De Sa, Kale, Lee, Sekhari, and Sridharan (2022) that the success of optimization implies particular geometric properties involving a \textit{Lyapunov Potential}. These geometric properties from optimization in turn give us strong quantitative control over isoperimetric constants of the measure. As a corollary, we show we can efficiently sample from several new natural and interesting classes of non-log-concave densities, an important setting where we have relatively few examples. Another corollary is efficient discrete-time sampling results for log-concave measures satisfying milder regularity conditions than smoothness, results similar to the work of Lehec (2023).

Submitted: Oct 3, 2024