How AI settled the complexity of the oldest SGD algorithm
Michał Dereziński, Xiaoyu Dong
cs.LG, cs.AI, math.NA, math.OC, stat.ML
Submitted: 2026-06-28
License: http://creativecommons.org/licenses/by/4.0/
The gist: In 1937, Stefan Kaczmarz proposed a simple algorithm for solving systems of linear equations.
Terminology
Abstract
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.
Sources
- First Proof
- Remarks on the disproof of the unit distance conjecture
- DeepSeek LLM: Scaling Open-Source Language Models with Longtermism
- Handbook of Convergence Theorems for (Stochastic) Gradient Methods
- Point Convergence of Nesterov's Accelerated Gradient Method: An AI-Assisted Proof
- Accelerating Scientific Research with Gemini: Case Studies and Common Techniques
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks