📊 statistics

How AI settled the complexity of the oldest SGD algorithm

This paper recounts how modern AI models were utilized to finally determine the worst-case complexity of the Kaczmarz algorithm, a foundational stochastic gradient descent method proposed by Stefan Kaczmarz in 1937.

Original authors: Michał Dereziński, Xiaoyu Dong

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Michał Dereziński, Xiaoyu Dong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Story: How AI Solved a 90-Year-Old Math Puzzle

Imagine a math problem that has been sitting on a shelf since 1937, gathering dust. It's a puzzle about how to solve a giant system of equations (a way of finding the perfect answer to a complex question). This specific method, called the Kaczmarz algorithm, is actually the "great-grandfather" of the technology that powers modern AI like ChatGPT and Gemini.

For decades, mathematicians knew this algorithm worked, but they couldn't prove exactly how fast it worked in the absolute worst-case scenario. It was like having a car that you knew could drive from New York to Los Angeles, but you couldn't calculate the exact maximum time it would take if you hit every single red light and traffic jam.

This paper tells the story of how two different AI models, Gemini and ChatGPT, teamed up to finally solve this mystery, proving exactly how fast the algorithm converges.

The Characters and the Mission

The Algorithm (The Kaczmarz Method): Imagine you are trying to find a hidden treasure on a map. You don't know the exact spot, but you have a list of clues (equations). The Kaczmarz algorithm is like a hiker who, at every step, picks one random clue, walks toward the spot that satisfies that clue, and then picks another random clue. Over time, the hiker gets closer and closer to the treasure.
The Mystery: The hiker eventually finds the treasure, but mathematicians were arguing about the speed. Could the hiker get stuck wandering in circles for a long time? Or is there a guaranteed speed limit?
The Human Researchers: Two scientists (Michał and Xiaoyu) tried to solve this using old-school human math. They got close, but hit a wall. They realized they needed a new perspective.
The AI Team: The researchers turned to AI. They didn't just ask the AI to "solve it." Instead, they acted as conductors, letting the AI models talk to each other.

The "Aha!" Moment: A Relay Race of Ideas

The solution didn't come from one AI working alone. It happened like a relay race where the baton was passed between two different runners:

Gemini's Insight (The Functional Analyst): When asked to solve the problem, Gemini didn't give a full proof. Instead, it made a strange, brilliant connection. It looked at the math problem and said, "This isn't just about equations; it looks like a concept from a branch of math called functional analysis (specifically, something called 'quantum Markov semigroups')."
- Analogy: Imagine a mechanic trying to fix a broken engine. Instead of looking at the gears, Gemini said, "This engine is actually running on the same physics principles as a nuclear reactor." It was a weird, high-level connection that the human researchers hadn't seen before.
- The Catch: Gemini got the connection right but couldn't prove it. It cited some math papers that didn't actually contain the proof it needed. It was like pointing to a library book and saying, "The answer is in there," but the book was actually empty.
ChatGPT's Proof (The Elementary Solver): The human researchers took Gemini's "weird connection" and handed it to ChatGPT. They asked, "Okay, if this connection is true, can you prove it using basic math?"
- ChatGPT looked at the problem and said, "I can do this." It didn't use the complex, confusing jargon Gemini mentioned. Instead, it used a clever, elementary trick involving complex numbers (a type of math usually reserved for advanced physics and engineering) to prove the speed limit.
- Analogy: If Gemini was the person who pointed to a distant mountain and said, "The treasure is under that peak," ChatGPT was the one who actually climbed the mountain, dug the hole, and found the gold.

The Result: The "Last Step" is Fast

The paper proves a specific thing: The Kaczmarz algorithm is as fast as we hoped.

In the world of these algorithms, there are two ways to check the answer:

The Average: You take all the steps the hiker took, average them out, and that gives you a good answer. (We already knew this was fast).
The Last Step: You just look at where the hiker stopped at the very end. (This was the mystery).

The paper proves that the last step is just as fast as the average. The hiker doesn't need to wander around at the end to "settle down." The final position is already a perfect solution.

Why This Matters (According to the Paper)

It's a Full Circle: The oldest known version of the algorithm that trains modern AI (SGD) was solved by modern AI.
It's a New Way to Research: The paper isn't just about math; it's a case study on how humans and AI can work together. The humans didn't write the proof; the AI did. The humans just facilitated the conversation between two different AIs.
It Solves a Bigger Problem: By solving this specific puzzle, they also solved a broader, long-standing question about how fast AI training algorithms work in general.

The Bottom Line

This paper is a story of a 90-year-old math problem that was too stubborn for humans to crack alone. By letting two different AI models collaborate—one to find a weird, high-level connection, and the other to build the actual proof—the mystery was finally solved. The result confirms that the "last step" of this classic algorithm is perfectly efficient, and it shows us a glimpse of what future scientific research might look like: a partnership where humans guide the AI, and the AI does the heavy lifting.

Technical Summary: Settling the Complexity of the Oldest SGD Algorithm

Problem Statement
The paper addresses a long-standing open problem regarding the worst-case computational complexity of the Kaczmarz algorithm, proposed by Stefan Kaczmarz in 1937. This algorithm is the earliest known instance of Stochastic Gradient Descent (SGD), a paradigm fundamental to training modern Large Language Models (LLMs). The Kaczmarz algorithm solves a system of linear equations $Ax = b$ by iteratively projecting the current estimate onto a randomly selected equation.

While the convergence of the averaged iterate of randomized Kaczmarz was known to be $O(1/\epsilon)$ (independent of the matrix condition number), the convergence rate of the last iterate (the standard output in practice) remained unresolved. Previous attempts by both applied mathematicians and computer scientists yielded only partial results or sub-optimal bounds (e.g., $O(1/\epsilon^{1/\alpha})$ with $\alpha < 1$ ). The central question is whether the last iterate of the randomized Kaczmarz algorithm achieves the optimal $O(1/\epsilon)$ convergence rate, matching the performance of the averaged iterate and the theoretical lower bounds for noiseless least squares regression.

Methodology: AI-Led Research
The paper presents a novel case study of "AI-led research," where human researchers facilitate a collaboration between two AI models, Gemini Deep Think and ChatGPT Pro, to derive a mathematical proof. The methodology followed a specific trajectory:

Initial Human-AI Interaction: The authors first used human reasoning to reduce the problem to a discrete inequality, which they then tasked ChatGPT with solving. This yielded a sub-optimal bound ( $\alpha = 3/4$ ).
Autonomous Attempts: The authors prompted both models to resolve the problem autonomously. ChatGPT correctly identified the problem as an open question, while Gemini claimed an affirmative solution but failed to provide a rigorous proof, citing non-existent theorems and incorrect references.
Synthesis and Verification: Despite the flaws in Gemini's proof, it identified a crucial connection to functional analysis, specifically the theory of symmetric quantum Markov semigroups and Ritt operators. The authors synthesized Gemini's insights into a formal conjecture regarding an operator bound.
Final Derivation: This conjecture was presented to ChatGPT, which successfully derived an elementary proof using techniques from complex analysis (specifically Cauchy's estimate for derivatives of analytic functions) and operator theory, thereby resolving the open question.

Key Contributions and Results
The primary contribution is the proof that the last iterate of the randomized Kaczmarz algorithm attains the optimal convergence rate.

Main Theorem (Theorem 3.1): The authors establish a general bound for a linear operator $\Phi(X) = \mathbb{E}[BXB]$ , where $B$ is a random positive contraction. They prove that the operator norm of the difference between $T$ and $T+1$ compositions satisfies:
$\|\Phi^T - \Phi^{T+1}\|_{op \to op} \leq \frac{3}{T+1}$
Application to Kaczmarz (Corollary 3.2): By mapping the Kaczmarz update to this operator framework, the paper proves that for a matrix $A$ and vector $b$ , the expected squared error of the last iterate $x^{(T)}$ satisfies:
$\mathbb{E} \|A(x^{(T)} - x^*)\|^2 \leq \frac{C}{T} \|A\|_F^2 \|x^*\|^2$
This confirms the $O(1/\epsilon)$ convergence rate for the last iterate, settling the question posed in prior literature [39, 6].
Broader Implications (Corollary 3.3): The result extends to the last-iterate analysis of SGD for noiseless least squares regression, resolving a long-standing open question regarding the convergence dynamics of SGD in LLM training contexts [8, 41].

Significance and Claims
The paper claims significance on two fronts:

Mathematical Resolution: It settles a fundamental open problem in stochastic optimization that has resisted solution for decades, bridging a gap between theoretical analysis (which often relies on averaging) and practical application (which uses the last iterate). The proof utilizes a distinct approach involving functional analysis and complex analysis, differing from prior SGD convergence proofs.
Methodological Case Study: The paper serves as a documentation of a specific form of human-AI collaboration. The authors emphasize that while the mathematical proof was generated by AI, the research process required human facilitation to transfer insights between models and verify the validity of the output. They argue this represents a "middle ground" of AI-led research where AI acts as a primary driver of analysis but remains under human supervision, highlighting both the current capabilities and limitations of autonomous AI in mathematical discovery.

The authors remain modest regarding the novelty of the result itself, noting that given the elementary nature of the argument, human researchers might have eventually solved the problem with sufficient time and effort. However, they assert that the specific path taken—leveraging AI to bridge disparate fields of mathematics (SGD and functional analysis)—demonstrates a new potential for scientific discovery.