Research map / Optimization / Implicit bias and generalization

The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations

ICML 2025 · Optimization › Implicit bias and generalization · approach: SGD noise and flat minima · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes the expected global convergence time of SGD on general non-convex losses via Freidlin–Wentzell large deviations, giving matching exponential upper/lower bounds governed by a pruned "energy" of spurious minima.

Problem

How long SGD with constant step-size takes to reach the global minimum of a general non-convex loss, given that it can be trapped in spurious local minima.

Approach

Uses large deviations (Freidlin–Wentzell theory adapted to discrete-time SGD) to build a transition graph over critical components; the expected hitting time of the global minimizers is exp(energy/step), where energy is the maximal relative depth of spurious minima the iterates must climb, yielding sandwich bounds.

Key results

• Upper and lower bounds on E[hitting time] of form exp((energy ± tol)/step), with energy given by the pruned energy of the target set relative to the initialization.
• On the three-hump camel example, the mean convergence time scales as exp(2(f(x2)-f(x5))/(step*sigma^2)); empirical fit with R^2 of 0.99 (data) and 0.97 (theory).
• Energy vanishes when no spurious minima exist, making convergence time subexponential; the energy is bounded by the maximal depth of spurious minima encountered.

Measured effects reported in the paper

Surprising findings

• Convergence time is governed by the most costly indirect chain of obstacles, not the least costly direct path to the global minimum.
• Escape times from individual local minima alone do not characterize global convergence time.

Limitations

• Lower bound requires attracting strength of the target to be large enough; the paper calls this technical.
• Bounds are stated for small step-size and margin; upper bound on transition costs needs extra noise assumption (Lagrangian bound).

Experimental setup

Metrics: expected global convergence time (hitting time)

Builds on: Freidlin-Wentzell theory subsampled SGD large deviation principle (Azizian et al.) quasi-potential / least action principle

Closest papers by meaning

• From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent (NeurIPS 2022 · similarity 0.93)
• Asymptotic theory of SGD with a general learning-rate (NeurIPS 2025 · similarity 0.92)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems (NeurIPS 2020 · similarity 0.92)
• Global Convergence and Stability of Stochastic Gradient Descent (NeurIPS 2022 · similarity 0.91)
• Taming Stochastic Gradient Descent: Almost Sure Convergence and Saddle-Point Avoidance under $(L_{0},L_{1})$-Smoothness (ICML 2026 · similarity 0.91)
• What is the Long-Run Distribution of Stochastic Gradient Descent? A Large Deviations Analysis (ICML 2024 · similarity 0.91)