The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations
Waïss Azizian c,∗, Franck Iutzeler ♯, Jérôme Malick ∗, Panayotis Mertikopoulos ⋄ · 2025
Read The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations by Waïss Azizian c,∗, Franck Iutzeler ♯, Jérôme Malick ∗, Panayotis Mertikopoulos ⋄ (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-2503-16398.txt.
Introduction
Waïss Azizian, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos ask how long stochastic gradient descent needs to find the best valley in a bumpy landscape, in a 2025 paper. The algorithm trains most neural networks, wandering with noisy steps. Local dips can trap it for ages. Viewing the wander as a randomly perturbed dynamical system, the team apply large deviations theory, which prices rare escapes.
They give matching upper and lower bounds on the time to reach the global minimum, so the answer is tight. The time is set by the costliest set of obstacles on the way, tying the landscape's global shape to the noise's statistics. For the shallow local minima common in deep learning, they refine the picture further. The results explain, in principle, why some training runs escape bad dips quickly and others crawl.
Catalog record
| CREATOR | Waïss Azizian c,∗, Franck Iutzeler ♯, Jérôme Malick ∗, Panayotis Mertikopoulos ⋄ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 233 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-16398