📊 statistics

How AI settled the complexity of the oldest SGD algorithm

本文叙述了现代人工智能模型如何被用于最终确定卡茨马尔算法（Kaczmarz algorithm）的最坏情况复杂度，该算法是由斯特凡·卡茨马尔（Stefan Kaczmarz）于1937年提出的一种基础随机梯度下降方法。

原作者： Michał Dereziński, Xiaoyu Dong

发布于 2026-06-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Michał Dereziński, Xiaoyu Dong

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

故事背景：AI 如何破解一个 90 年之久的数学难题

想象一下，有一个数学问题自 1937 年以来就一直静静地躺在书架上，落满了灰尘。这是一个关于如何求解巨大方程组（一种寻找复杂问题完美答案的方法）的谜题。这种特定的方法被称为 Kaczmarz 算法，它实际上是驱动现代 AI（如 ChatGPT 和 Gemini）的技术的“曾祖父”。

几十年来，数学家们知道这个算法是有效的，但他们无法准确证明在最坏的情况下它的运行速度究竟有多快。这就像你明知道一辆车可以从纽约开到洛杉矶，但你却无法计算出如果遇到所有的红灯和交通拥堵时，最长需要多少时间。

这篇论文讲述了两个不同的 AI 模型——Gemini 和 ChatGPT——是如何联手解决这个谜团，并最终证明了该算法收敛速度的过程。

角色与使命

算法（Kaczmarz 方法）： 想象你正在试图在一张地图上寻找隐藏的宝藏。你不知道确切的位置，但你有一份线索清单（方程）。Kaczmarz 算法就像一个徒步旅行者，在每一步中，他会随机选择一个线索，朝着满足该线索的位置前进，然后再次随机选择另一个线索。随着时间的推移，徒步旅行者会越来越接近宝藏。
谜团： 徒步旅行者最终会找到宝藏，但数学家们一直在争论速度问题。徒步旅行者会不会在原地兜圈子徘徊很久？还是说存在一个保证的速度限制？
人类研究员： 两位科学家（Michał 和 Xiaoyu）尝试用传统的数学方法来解决这个问题。他们已经非常接近了，但撞到了墙。他们意识到自己需要一个新的视角。
AI 团队： 研究人员转向了 AI。他们并没有只是简单地要求 AI “解决它”，而是扮演了指挥家的角色，让不同的 AI 模型进行对话。

“顿悟”时刻：思想的接力赛

解决方案并非来自一个 AI 的独立工作，而是发生在一场接力赛中，接力棒在两个不同的跑步者之间传递：

Gemini 的洞察（函数分析学家）： 当被要求解决这个问题时，Gemini 并没有给出完整的证明。相反，它建立了一个奇特而精妙的联系。它观察了这个数学问题并说道：“这不仅仅是关于方程；它看起来像是来自泛函分析（具体来说是‘量子马尔可夫半群’）的一个概念。”
- 类比： 想象一名技工试图修理一台坏掉的发动机。Gemini 没有去观察齿轮，而是说：“这台发动机实际上是基于与核反应堆相同的物理原理运行的。”这是一个极其高层且奇特的联系，是人类研究人员之前从未见过的。
- 缺陷： Gemini 虽然找对了联系，但无法给出证明。它引用了一些数学论文，但这些论文其实并不包含它所需的证明。这就像是指向一本图书馆里的书并说：“答案就在里面”，但那本书其实是空的。
ChatGPT 的证明（基础解法专家）： 人类研究人员将 Gemini 的“奇特联系”交给了 ChatGPT。他们问道：“好吧，如果这个联系是真的，你能用基础数学来证明它吗？”
- ChatGPT 审视了问题并回答道：“我可以做到。”它没有使用 Gemini 提到的那些复杂、令人困惑的术语。相反，它使用了一个涉及复数（一种通常用于高级物理和工程学的数学类型）的巧妙基础技巧，从而证明了速度限制。
- 类比： 如果说 Gemini 是那个指着远处的山峰并说“宝藏就在那个山峰之下”的人，那么 ChatGPT 就是那个真正爬上山、挖开坑并找到黄金的人。

结果：最后一步非常迅速

论文证明了一个特定的结论：Kaczmarz 算法正如我们所期望的那样快。

在这些算法的世界里，有两种检查答案的方法：

平均值： 你记录下徒步旅行者采取的所有步骤，取其平均值，这会得到一个很好的答案。（我们已知这是很快的）。
最后一步： 你只看他在最后结束时的位置。（这正是谜团所在）。

论文证明了：最后一步和平均值一样快。 徒步旅行者不需要在最后阶段为了“稳定下来”而徘徊。最终的位置本身就是一个完美的解。

为什么这很重要（根据论文所述）

一个圆满的轮回： 训练现代 AI 的最古老的已知版本的算法（SGD），最终被现代 AI 所解决。
一种新的研究方式： 这篇论文不仅关于数学，它也是一个关于人类与 AI 如何协作的案例研究。人类并没有写出证明，AI 写出了证明。人类只是促进了两个不同 AI 之间的对话。
解决了一个更大的问题： 通过解决这个特定的谜题，他们同时也解决了一个关于 AI 训练算法整体运行速度的长期悬而未决的问题。

核心结论

这篇论文讲述了一个 90 年前的数学难题，它过于顽固，以至于仅靠人类无法攻克。通过让两个不同的 AI 模型进行协作——一个负责寻找一个奇特的、高层级的联系，另一个负责构建实际的证明——这个谜团终于被解开了。结果证实，这个经典算法的“最后一步”是非常高效的，同时也让我们窥见了未来科学研究的模样：一种人类引导 AI，而 AI 完成繁重工作的伙伴关系。

技术摘要：解决最古老 SGD 算法的复杂度问题

问题陈述
本文探讨了关于 Kaczmarz 算法（由 Stefan Kaczar 在 1937 年提出）最坏情况计算复杂度的长期开放问题。该算法是已知最早的随机梯度下降（SGD）实例，而 SGD 是训练现代大语言模型（LLM）的基础范式。Kaczmarz 算法通过迭代地将当前估计值投影到随机选择的一个方程上，来求解线性方程组 $Ax = b$。

虽然随机 Kaczmarz 的平均迭代（averaged iterate）的收敛速度已知为 $O(1/\epsilon)$ （与矩阵条件数无关），但最后一次迭代（last iterate，实际应用中的标准输出）的收敛速度仍未得到解决。此前，应用数学家和计算机科学家的尝试仅取得了局部结果或次优界限（例如 $O(1/\epsilon^{1/\alpha})$ ，其中 $\alpha < 1$ ）。核心问题在于：随机 Kaczmarz 算法的最后一次迭代是否能达到最优的 $O(1/\epsilon)$ 收敛速率，从而匹配平均迭代的性能以及无噪声最小二乘回归的理论下界。

方法论：AI 引导的研究
本文展示了一个“AI 引导研究”的新颖案例研究，其中人类研究人员促进了两个 AI 模型——Gemini Deep Think 和 ChatGPT Pro 之间的协作，以推导出一个数学证明。该方法遵循以下轨迹：

初步的人机交互： 作者首先利用人类推理将问题简化为一个离散不等式，然后要求 ChatGPT 求解。这产生了一个次优界限（ $\alpha = 3/4$ ）。
自主尝试： 作者提示两个模型进行自主解决。ChatGPT 正确识别出该问题是一个开放性问题；而 Gemini 声称找到了肯定解，但未能提供严谨的证明，并引用了不存在的定理和错误的参考文献。
综合与验证： 尽管 Gemini 的证明存在缺陷，但它识别出了一个关键联系，即与泛函分析、特别是对称量子马尔可夫半群（symmetric quantum Markov semigroups）和 Ritt 算子（Ritt operators）理论的联系。作者将 Gemini 的见解综合成一个关于算子界的正式猜想。
最终推导： 该猜想被提交给 ChatGPT，后者利用复分析技术（特别是解析函数导数的 Cauchy 估计）和算子理论成功推导出了一个初等证明，从而解决了这一开放性问题。

主要贡献与结果
其主要贡献是证明了随机 Kaczmarz 算法的最后一次迭代达到了最优收敛速率。

主定理 (Theorem 3.1)： 作者为线性算子 $\Phi(X) = \mathbb{E}[BXB]$ （其中 $B$ 是一个随机正收缩算子）建立了一个通用的界限。他们证明了 $T$ 与 $T+1$ 次复合之间的算子范数差满足：
$\|\Phi^T - \Phi^{T+1}\|_{op \to op} \leq \frac{3}{T+1}$
应用于 Kaczmarz (Corollary 3.2)： 通过将 Kaczmarz 更新映射到此算子框架中，本文证明了对于矩阵 $A$ 和向量 $b$ ，最后一次迭代 $x^{(T)}$ 的期望平方误差满足：
$\mathbb{E} \|A(x^{(T)} - x^*)\|^2 \leq \frac{C}{T} \|A\|_F^2 \|x^*\|^2$
这证实了最后一次迭代具有 $O(1/\epsilon)$ 的收敛速率，解决了先前文献 [39, 6] 中提出的问题。
更广泛的影响 (Corollary 3.3)： 该结果扩展到了无噪声最小二乘回归中 SGD 的最后一次迭代分析，解决了关于 LLM 训练背景下 SGD 收敛动态的一个长期开放问题 [8, 41]。

意义与主张
本文在两个层面上声称其重要性：

数学层面的解决： 它解决了一个在随机优化领域存在数十年之久的根本性开放问题，弥合了理论分析（通常依赖于平均化）与实际应用（使用最后一次迭代）之间的鸿沟。其证明采用了一种涉及泛函分析和复分析的不同方法，区别于以往的 SGD 收敛证明。
方法论层面的案例研究： 本文记录了一种特定形式的人机协作。作者强调，虽然数学证明是由 AI 生成的，但研究过程需要人类的促进作用，以实现模型间见解的传递并验证输出的有效性。他们认为这代表了“AI 引导研究”的一种“中间地带”，即 AI 作为分析的主要驱动力，但仍处于人类的监督之下，这凸显了当前 AI 在数学发现中的能力与局限性。

作者对结果本身的原创性保持谦逊，指出鉴于该论证的初等性质，人类研究人员在投入足够的时间和精力后最终也可能解决该问题。然而，他们断言，这种特定的路径——利用 AI 桥接不同数学领域（SGD 与泛函分析）——展示了科学发现的新潜力。