Large-Time Analysis of the Langevin Dynamics for Energies Fulfilling Polyak-Łojasiewicz Conditions
Massimo Fornasier, Lukang Sun, Rachel Ward · 2025
Read Large-Time Analysis of the Langevin Dynamics for Energies Fulfilling Polyak-Łojasiewicz Conditions by Massimo Fornasier, Lukang Sun, Rachel Ward (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24925.txt.
Introduction
Massimo Fornasier, Lukang Sun, and Rachel Ward track the long run acts of a noise driven search for low points of a cost. Such Langevin moves are used to find best fits in hard land shapes. They set firm ground for the search: its law is well set and smooth, with fresh prior bounds.
When the end state can be pooled, the law tends to that pooled state over time. When it can not, the law spreads out, at a rate they pin down. Under a named slope rule, they show sharp fast pull toward the set of best points. Both phases are joined in one read for a class not worked this way before.
Catalog record
| CREATOR | Massimo Fornasier, Lukang Sun, Rachel Ward |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24925
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Large-Time Analysis of the Langevin Dynamics for Energies Fulfilling Polyak-Łojasiewicz Conditions Massimo Fornasier, Lukang Sun, Rachel Ward Abstract In this work, we take a step towards understanding overdamped Langevin dynamics for the minimization of a general class of objective functions ℒ \mathcal{L} . We establish well-posedness and regularity of the law ρ t \rho_{t} of the process through novel a priori estimates, and, very importantly, we characterize the large-time behavior of ρ t \rho_{t} under truly minimal assumptions on ℒ \mathcal{L} . In the case of integrable Gibbs density, the law converges to the normalized Gibbs measure. In the non-integrable case, we prove that the law diffuses. The rate of convergence is 𝒪 ( 1 / t ) \mathcal{O}(1/t) . Under a Polyak–Łojasiewicz (PL) condition on ℒ \mathcal{L} , we also derive sharp exponential contractivity results toward the set of global minimizers. Combining these results we provide the first systematic convergence analysis of Langevin dynamics under PL conditions in non-integrable Gibbs settings: a first phase of exponential in time contraction toward the set of minimizers and then a large-time exploration over it with rate 𝒪 ( 1 / t ) \mathcal{O}(1/t) . 1 Introduction Stochastic Gradient–based algorithms are the workhorses of modern machine learning. Recall the general set-up: the aim is to minimize a loss function of the form \mathcal{L}(w)=\frac{1}{N}\sum_{i=1}^{N}\ell_{i}(w) , and the Stochastic Gradient update rule is \displaystyle w^{(k+1)} \displaystyle=w^{(k)}-\eta_{k}\nabla{\cal L}(w^{(k)})+\eta_{k}\xi^{(k)}, (1) where \eta_{k}>0 is the step-size at iteration k , and \xi^{(k)} is a stochastic noise vector, independent of previous \xi^{(h)} h<k , but possibly depending on w^{(k)} . One source of noise, which is almost unavoidable in large-scale machine learning applications, is due to applying mini-batch gradient descent en leiu of full gradient descent, in which case \xi^{(k)}=\frac{1}{|B_{k}|}\sum_{i\in B_{k}}\nabla\ell_{i}(w^{(k)})-\nabla{\cal L}(w^{(k)}) , where B_{k}\subset[N] are the indices in the mini-batch used at iteration k , modeled as drawn independently of previous mini-batches. A second or alternative source of noise is injected Gaussian noise \xi^{(k)} with bounded variance \mathbb{E}\|\xi^{(k)}\|^{2}\leq M or affine variance \mathbb{E}\|\xi^{(k)}\|^{2}\leq M_{1}+M_{2}\|\nabla{\cal L}(w^{(k)})\|^{2} . Gaussian noise can be purposefully injected to render the algorithm privacy-preserving (so-called ‘DP SGD’) [ Abadi et al., 2016 ] , to enable exploration of possibly non-convex loss landscapes [ Bassily et al., 2018 , Cooper, 2021 , Liu et al., 2020 , Liu et al., 2022 ] and because doing so can cause an implicit regularization effect that often improves generalization [ Li et al., 2022 , Neyshabur et al., 2015 , Razin and Cohen, 2020 ] . Focusing on the Gaussian noise setting, when the variance term is bounded \mathbb{E}\|\xi^{(k)}\|^{2}\leq M , or even increases inversely with a decreasing stepsize \eta_{k} , it makes more sense to consider the Stochastic Gradient update rule w^{(k+1)}=w^{(k)}-\eta_{k}(\nabla{\cal L}(w^{(k)})+\xi^{(k)}) as acting on a random variable W^{(k)} rather than a point w^{(k)} , and to analyze convergence in terms of the law of W^{(k)} toward an equilibrium distribution, instead of analyzing convergence of a point estimate w^{(k)} to a critical point w^{*} (or better to a global minimizer) of the loss function. One would hope that convergence results from the “optimization” setting find natural analogues in the “sampling” setting, and vice versa. 1.1 The strongly convex regime In the most classical regime, the translation between optimization and sampling results is seamless. The most classical assumption in gradient descent convergence theory is that the loss function {\mathcal{L}} is \mu - strongly convex and L -Lipschitz smooth, in which case a direct proof shows that for a range of constant step-size \eta_{k}=\eta , w^{(k)} converges to the unique global minimizer of {\cal L} at a linear rate proportional to the condition number L/\mu . When noise with bounded variance \mathbb{E}\|\xi^{(k)}\|_{2}^{2}\leq M is added, the expected convergence \mathbb{E}[\mathcal{L}(w^{(k)})-\mathcal{L}(w^{*})] is again linear with rate L/\mu , but the iterations reach up to a radius of around the global minimizer of size proportional to M\eta\frac{L}{\mu} , see [ Bottou et al., 2018 , Theorem 4.6 ] for details. This suggests that in the strongly convex regime, and in the limit of small constant step-size \eta where the discrete-time Stochastic Gradient update converges to a continuous-time stochastic differential equation , the dynamics should be such that the initial probability distribution of points is pushed towards a distribution centered at the global minimizer w^{*} and having a variance proportional to cM, where c=\frac{L}{\mu}\eta\in(0,1) . And indeed, this is the case. Consider the formal limit of this process, the Langevin dynamics: dw_{t}=-\nabla\mathcal{L}(w_{t})dt+\sqrt{2\sigma}dB_{t}. (2) where t\to B_{t} is a d -dimensional Brownian motion, \sigma>0 , and w_{t=0}=w_{0}\in\mathbb{R}^{d} is given or drawn at random according to an initial probability measure \rho_{0}\in\mathcal{P}(\mathbb{R}^{d}) . The Langevin dynamics ( 2 ) converge classically to near global minimizers under the so-called log-Sobolev inequality (LSI). The LSI holds for \rho_{\infty} if, for any \lambda>0 , \begin{array}[]{c}\int_{\mathbb{R}^{d}}\log\mathopen{}\mathclose{{\left(\frac{d\rho}{d\rho_{\infty}}}}\right)d\rho(x)=:\underbrace{H(\rho|\rho_{\infty})}_{\begin{subarray}{c}\text{relative}\\ \text{entropy}\end{subarray}}\leq\frac{1}{2\lambda}\underbrace{I(\rho|\rho_{\infty})}_{\begin{subarray}{c}\text{Fisher}\\ \text{information}\end{subarray}}:=\frac{1}{2\lambda}\int_{\mathbb{R}^{d}}\mathopen{}\mathclose{{\left|\nabla\log\mathopen{}\mathclose{{\left(\frac{d\rho}{d\rho_{\infty}}}}\right)}}\right|^{2}d\rho(x)\\ \mbox{ for all }\rho\in\mathcal{P}(\mathbb{R}^{d}).\end{array} (3) (As in this paper we do not actually make use of LSI, we do not introduce the relative entropy nor the Fischer information in full glory, and we refer to [ Villani, 2003 , Section 9.2] for details.) For the noisy evolution ( 2 ), an LSI with constant \lambda>0 ensures exponential convergence of the law \rho_{t}:=\operatorname{Law}(w_{t}) in terms of Wasserstein distance or relative entropy toward the normalized Gibbs density \rho_{\infty}\propto\pi:=e^{-\mathcal{L}/\sigma} . Indeed, a typical \mathcal{L} for which ( 3 ) holds is a strictly convex function, or an L^{\infty} perturbation of a strictly convex function , see [ Holley and Stroock, 1987 ] . Note that in the case \mathcal{L}(w)=\|Aw-y\|^{2} where A is invertible, then the Gibbs density \pi=e^{-\mathcal{L}/\sigma} is a Gaussian density centered at the minimizer w^{*} , and this density has variance \sigma^{2} , aligning with the discrete SGD results about fast convergence within a radius of the variance. Note that the discrete-time theory for SGD allows for a general range of noise distributions including Gaussian noise as a special case. The continuous-time Langevin dynamics theory, while specific to Gaussian noise, nevertheless provides a finer-grained picture of how the dynamics are evolving in a distributional sense: any initial distribution converges in the Wasserstein distance towards the Gibbs density e^{-\mathcal{L}/\sigma} . 1.2 The PL inequality regime The strong convexity regime is classical, and the discrete-time Stochastic Gradient Descent (SGD) theory and the continuous-time Langevin dynamics theory are well-understood and related. However, practical implementations of SGD in training, e.g., deep neural networks, are aiming at optimizing highly nonconvex landscapes. A better assumption than strong convexity for overparameterized neural networks is a local version of the Polyak–Łojasiewicz (PL) inequality [ Bassily et al., 2018 , Liu et al., 2020 , Liu et al., 2022 ] . First, let us recall the PL inequality. When the deterministic gradient flow \dot{w}_{t}=-\nabla\mathcal{L}(w_{t}) or the Gradient Descent w^{(k+1)}=w^{(k)}-\eta\nabla\mathcal{L}(w^{(k)}) are analyzed under the PL inequality \frac{1}{2}\|\nabla\mathcal{L}(w)\|^{2}\geq\mu\mathopen{}\mathclose{{\left(\mathcal{L}(w)-\min\mathcal{L}}}\right),\qquad\mu>0,\quad\forall w\in\mathbb{R}^{d}, (4) one obtains exponential convergence to the minimizer set \mathcal{W}^{*}:=\operatorname*{arg\,min}\mathcal{L}, matching the fast convergence rate one achieves under strong convexity assumptions on the loss function convergence {\mathcal{L}}(w^{(k)})\to\min\mathcal{L} (as opposed to the pointwise convergence w^{(k)}\to w^{*} which is more difficult in the PL inequality setting as w^{*} is not a necessarily a point, but possibly a set of points). In the Stochastic Gradient regime, fast convergence to within a radius of the minimizing set