AI发现最早随机梯度算法的最坏情况复杂度
How AI settled the complexity of the oldest SGD algorithm
- 用AI模型协作分析算法最坏情况复杂度
- 确认了Kaczmarz算法在最差情况下的收敛速度
- 适合对优化理论感兴趣的学者阅读
1937年，斯蒂芬·卡茨马尔兹提出了求解线性方程组的简单算法。该算法被证实是最早的随机梯度下降（SGD）实例之一，而现代人工智能模型（如ChatGPT和Gemini）的训练正是基于这一计算范式。如今，这些人工智能模型协同工作，揭示了卡茨马尔兹算法在最坏情况下的复杂度。本文讲述了这一发现的过程。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。