mlsanityData to 7 Oct 2026

How AI settled the complexity of the oldest SGD algorithm

arXiv 2606.29593 ↗First posted 28 Jun 2026cs.LG cs.AI cs.NAcited by 0

Not on the map. Why?

Abstract (arXiv)

In 1937, Stefan Kaczmarz proposed a simple algorithm for solving systems of linear equations. This algorithm turned out to be the earliest known example of stochastic gradient descent, a ubiquitous computing paradigm that drives the training of modern AI models such as ChatGPT and Gemini. Now, those AI models have joined forces to discover the worst-case complexity of the Kaczmarz algorithm. This paper tells the story of how it happened.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 25 of its 45 references that are in the map. First posted on arXiv 28 Jun 2026.

Builds on

25 of 45 references.

References · 25

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2024DeepSeek LLM: Scaling Open-Source Language Models with Longtermismcited by 621
  4. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  5. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  6. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  7. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  8. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  9. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 67
  10. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 41
  11. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  12. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
13 more
  1. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 35
  2. 2019The importance of better models in stochastic optimizationcited by 32
  3. 2026First Proofcited by 26
  4. 2023Exact convergence rate of the last iterate in subgradient methodscited by 24
  5. 2026Accelerating Scientific Research with Gemini: Case Studies and Common Techniquescited by 24
  6. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  7. 2013Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systemscited by 14
  8. 2013An Accelerated Randomized Kaczmarz Algorithmcited by 12
  9. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 10
  10. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 10
  11. 2025Point Convergence of Nesterov's Accelerated Gradient Method: An AI-Assisted Proofcited by 10
  12. 2025Randomized Kaczmarz Methods with Beyond-Krylov Convergencecited by 7
  13. 2026Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Sizecited by 2

Built on by

Not cited yet.