{"id":"arxiv/2606.29593","url":"https://arxiv.org/abs/2606.29593","tags":["cs.LG","cs.AI","math.NA","math.OC","stat.ML"],"score":0,"title":"How AI settled the complexity of the oldest SGD algorithm","domain":"cs.LG","source":"arxiv","authors":["Michał Dereziński","Xiaoyu Dong"],"reviews":0,"subject":"cs.LG","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-28","reactions":{}}