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

CREATORWaïss Azizian c,∗, Franck Iutzeler ♯, Jérôme Malick ∗, Panayotis Mertikopoulos ⋄
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE233 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-16398

Browse the full library · About the Tower of Babel