mlsanityData to 7 Oct 2026

Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approach

arXiv 2605.14663 ↗First posted 14 May 2026math.OC math.PR stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) has been studied extensively over the past decades due to its simplicity and broad applicability in machine learning. In this work, we analyze the local behavior of gradient descent and stochastic gradient descent for minimizing C2-functions that satisfy the Polyak-Lojasiewicz (PL) inequality and under a multiplicative gradient noise model motivated by overparameterized neural networks. Using a geometric interpretation of the PL-condition, we prove a simple yet surprising fact: in this possibly non-convex setting, the asymptotic convergence rate of (S)GD matches the rate obtained for strongly convex quadratics.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 16 of its 31 references that are in the map. First posted on arXiv 14 May 2026.

Builds on

16 of 31 references.

References · 16

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  3. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  4. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  5. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  6. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  7. 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 79
  8. 2019Convergence rates for the stochastic gradient descent method for non-convex objective functionscited by 66
  9. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
  10. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  11. 2016Local Convergence of the Heavy-ball Method and iPiano for Non-convex Optimizationcited by 9
  12. 2023Exponential convergence rates for momentum stochastic gradient descent in the overparametrized settingcited by 7
4 more
  1. 2024Nesterov acceleration in benignly non-convex landscapescited by 6
  2. 2024Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequalitycited by 2
  3. 2025Polyak-Lojasiewicz inequality is essentially no more general than strong convexity for C2 functionscited by 2
  4. 2026Optimal local linear convergence of Nesterov's accelerated gradient method for C2 functions under the Polyak--Lojasiewicz inequalitycited by 1

Built on by

Not cited yet.