arxivcs.LGcs.AImath.NAmath.OCstat.ML2026-06-28
How AI settled the complexity of the oldest SGD algorithm
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 an…