cs.LG · 2606.29593 Copy arXiv ID · Jun 28, 2026 Save How AI settled the complexity of the oldest SGD algorithm Authors: Michał Dereziński , Xiaoyu Dong
Organizations: University of Michigan · National University of Singapore
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.
Explore similar work May 14, 2026 · Juho Kim, Tuomas Sandholm Imperfect-Information Games Parallel
May 2, 2025 · Henry Shugart, Jason M. Altschuler Large Step Sizes Flat Minima
Jun 16, 2026 · Aditya Devarakonda, Irene Simó Muñoz, Giulia Guidi Stochastic Gradient Descent Multi-Gpu Systems
May 14, 2026 · cs.AI J/K move · Enter open · S save
Juho Kim, Tuomas Sandholm
Parallelization has played an instrumental role in the field of artificial intelligence (AI), drastically reducing the time taken to train and evaluate large AI models. In contrast to its impact in the broader field of AI, applying parallelization to computational game solving is relatively unexplored, despite its great potential. In this paper, we parallelize the family of counterfactual regret minimization (CFR) algorithms, which were central to important breakthroughs for solving large imperfect-information games. We present a generalized parallelization framework, reframing CFR as a series of linear algebra operations. Then, existing techniques for parallelizing linear algebra operations can be applied to accelerate CFR. We also describe how our technique can be applied to other tabular members of the CFR family of algorithms, including the state-of-the-art, such as CFR+, discounted CFR, and predictive variants of CFR. Experimentally, we show that our CFR implementation on a GPU is up to four orders of magnitude faster than Google DeepMind OpenSpiel's CFR implementations on a CPU.