2606.29593

Total: 1

#1 How AI settled the complexity of the oldest SGD algorithm [PDF] [Copy] [Kimi] [REL]

Authors: Michał Dereziński, Xiaoyu Dong

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.

Subjects: Machine Learning , Artificial Intelligence , Numerical Analysis , Optimization and Control , Machine Learning

Publish: 2026-06-28 20:27:52 UTC