研究了一辈子「遗憾」的人，说自己零遗憾：一个 AI 核心方法的二十年

机器之心编译

二十年前，在线凸优化（Online Convex Optimization，OCO）还是理论计算机、机器学习与优化交界处的一个年轻方向。今天再看，它所形成的 regret minimization、自适应更新和在线决策框架，已经深刻影响现代机器学习。从 Online Newton Step、AdaGrad，到 bandit optimization、在线控制和序列建模，OCO 的许多思想逐步进入 AI 的核心方法体系。

如今，AI 与数学的关系也走到了一个新的节点。9 月，陶哲轩与另外 24 位菲尔兹奖得主联名发表《A Severe Misalignment of AI in Mathematics》，引发数学界对 AI、数学研究价值和学术生态的广泛讨论。随着 AI 在搜索、推导和证明上的能力迅速提升，一个越来越现实的问题浮现出来：当机器能够解决更多数学问题，数学家的核心价值将体现在哪里？

普林斯顿大学教授 Elad Hazan 最近写了一篇回顾在线凸优化二十年发展的文章。从 universal portfolio、Online Newton Step 和 AdaGrad，到在线控制、spectral filtering 与新的神经网络架构，他以自己的研究经历串起了 OCO 与现代 AI 之间的一条重要技术脉络。

• https://www.minregret.com/2026/09/15/two-decades-of-online-convex-optimization.html

文章最后，Hazan 也把视线投向 AI 对数学研究的影响。他认为，随着 AI 越来越擅长定理证明，选择有意思的问题、创造新的框架将变得更加重要。这恰好触及当下数学界正在讨论的一个核心问题：当搜索、推导和证明能力不断被 AI 放大，提出什么问题、创造什么概念、建立什么框架，可能变得更加重要。

以下是 Elad Hazan 的原文：

在线凸优化二十年：一段个人回忆

我第一次开始研究在线凸优化（Online Convex Optimization，OCO），是在读博第三年。当时，Zinkevich 的论文刚刚发表。与此同时，我和几位同学正在一起读 Cover 关于 universal portfolios（通用投资组合）的论文——后面还会讲到我和 Satyen Kale 的友谊。

那时候，我研究这个方向，其实有一个非常现实的目的：万一以后找不到教职，我得给自己留条后路。我刚进研究生院时，想做的是计算复杂性理论。可那时候，我身边经常围着一群数学天才：Ryan O’Donnell、Irit Dinur、Scott Aaronson、Dana Moshkovitz、Robert Krauthgamer、Muli Safra，当然还有我的导师 Sanjeev Arora。那个环境让人压力巨大。当年的 STOC/FOCS 和今天一样严苛，甚至可能更严，最重要的评价标准就是数学能力。现在回头看，这件事尤其有意思：AI 如今恰恰特别擅长 STOC/FOCS 所偏爱的那类能力，而在发明全新框架这件事上，相对没那么强。这一点我会在文章最后再回来谈。当时我的想法很简单：如果要和这些天才竞争理论方向的教职，我恐怕一点希望都没有。

现在想来，这种担心还挺好笑的。因为今天，这些人都成了我的好朋友。我可以请 Scott 和 Dana 来家里吃饭；下一周去和 Noga Alon 喝咖啡；也可以跟 Avi Wigderson 聊聊我的小儿子 Oded。读博时的我，完全无法想象，后来自己竟然能和这些人如此亲近。

所以，先把谦虚暂时扔到一边：当年组织一个学生小组、一起研究金融，好让大家万一学术道路走不通还能去金融行业找工作——这事完全是我的主意……

我们跑去 Bendheim Center 上了一门金融课——如果我没记错的话，Satyen 大概是我们当中唯一真正把课上完的人。与此同时，我们也在研究 Cover 的投资组合理论。我们一开始的目标，是把 Cover 的方法改进成一个真正高效的算法，同时还要保留他所得到的最优 regret bound（遗憾界）。长话短说，我们后来发现了一个非常漂亮的联系：Newton 方法、regret minimization（遗憾最小化）和在线凸优化，其实可以被放进同一个框架中理解。这最终变成了我一生最喜欢的论文之一，也就是提出 Online Newton Step（ONS）算法的那篇论文。当时我就觉得，这是一项很重要的结果，尽管论文被 FOCS/STOC 拒掉了。而且我隐约感觉，这里面真正重要的东西，比表面看到的还要多。现在回头看，算法本身反而是次要的。更重要的发现是，「无论使用什么方法，都要高效地追上事后看来最好的那个固定决策」，可以成为一个统一视角。在这个视角下，投资组合选择、梯度下降和 Newton 方法，突然都变成了同一件事的不同形式。

这里稍微补充一点技术背景。Cover 的论文研究的是一种叫做 universal portfolios 的投资策略。它有一个非常特别的保证：即便你对市场不做任何假设，它的表现仍然可以与事后看来最优的、固定比例并持续再平衡的股票投资组合进行比较。Zinkevich 的论文研究了一个类似的量，这个概念来自博弈论，也就是 regret（遗憾）。Regret 衡量的是：我们的累计损失，与事后看来最好的那个固定决策相比，到底差了多少。Zinkevich 证明，一种很自然的梯度下降方法，就能够得到接近最优的 regret bound。于是我们的想法是：如果 Newton 方法能够得到比梯度下降更好的 regret bound 呢？进一步说，如果这能导出一种高效的投资组合选择算法呢？

真正最吸引我的，是数学优化与学习之间的联系。但在当时，这种联系几乎还没有被探索过。我记得自己曾经去问 ORFE 的一位优化领域专家——这里就不说名字了——一个非常基础的问题：「带约束凸优化的最坏情况计算复杂度到底是多少？」结果我始终没能得到一个清晰的答案。

于是，我转而去读 Nesterov 和 Nemirovski 那本奠基性的著作。后来，Yuri Nesterov 和 Arkadi Nemirovski 都成了我心目中的科研偶像。我还有幸和 Arkadi 本人有过交流，他是我认识过最伟大的科学家之一。但我必须承认：那本书几乎读不下去。

从一个理论计算机博士生的角度看，这就是当时优化领域一种很奇怪的状态。这是一个极其深厚、极其成熟的领域，但它还缺少一种简洁、统一的算法语言，来把优化、学习和序列决策连接起来。而后来，这个连接逐渐变成了我们今天所说的在线凸优化（Online Convex Optimization）。

从 ONS 到自适应梯度方法

这个领域影响最大的成果之一，可能就是 adaptive gradient methods（自适应梯度方法）的发展。它们后来成了现代深度学习和 AI 的主力工具之一，而故事的起点，就是 AdaGrad。这背后的故事其实挺有意思。最近，我还分别在两位同事的 60 岁生日庆祝活动上讲过：一位是 Yoram Singer——我和他以及 John Duchi 一起发明了这套方法；另一位是 Peter Bartlett。

博士毕业后，我去了著名的 IBM Almaden「Theory Group」做博士后，接待我的是非常优秀的数学家 Nimrod Megiddo。从一开始，我的目标就是回自己的祖国以色列当教授。但问题在于，我在以色列学术圈基本没什么人脉，而我的导师又是一位印裔美国人……

所以，为了和以色列资深教授建立联系，我决定去找著名的优化专家 Yoram Singer。这事倒不难。Yoram 早就知道我，因为他看过我们 2006 年那篇 ONS 论文。他是最早真正理解并认可那项工作的人之一。后来，他还和我的朋友 Shai Shalev-Shwartz、Nati Srebro 一起，把其中的一些思想用在了 Pegasos 上。

必须称赞 Yoram 一句：他在科研合作上开放到了极致。他非常热情地欢迎我去 Google Mountain View 的办公室。然后，我、Yoram 和 John Duchi 一起，开始尝试改进优化方法。那时 John 还是 Berkeley 的学生，每天都会骑车，在 Berkeley 和 Google Mountain View 园区之间来回，大概要骑一个小时。我特别喜欢 Google MTV 园区：免费的食物，加上一种极其浓厚的 nerd 氛围，简直是做研究的理想环境。

我们当时最核心的问题是：我们能不能和「事后看来最好的正则化方法」竞争？！

这其实相当于把 regret 的思想，用到了优化器家族本身。此前，regret 这个视角已经把不同的学习算法统一起来。现在，我们把视角再往上抬了一层，开始对准 optimizer 本身。今天，这种想法在优化领域已经非常常见，但在当时，它是全新的。

Yoram 的动力来自优化本身——他想改善机器学习实践。John 则痴迷于其中的矩阵数学——那部分确实非常漂亮 :-) 至于我，我还在努力寻找一个以色列的教职……结果，这个三人组合相当成功，自适应梯度方法就这样诞生了！

自适应、计算与友谊

从博士后到我拿到第一份教职的那几年，是在线凸优化的黄金时代。Satyen 和我状态火热，我们就像一台运转良好的科研机器。无论看到什么问题，我们几乎总能发现：以前的人似乎都没有从 regret、optimization，或者两者结合的角度真正看过它。我们反复问的其实都是同一个问题：如果什么假设都不做，只要求 no regret，这个问题会变成什么样？那真的是我们人生中非常快乐的一段时间。短短几年，我们一起写了差不多 20 篇论文，涉及：

1. Projection-free methods（无投影方法）
2. Regret 中的 variational bounds
3. Bandit algorithms
4. 博弈论、均衡与不动点
5. 最优随机强凸优化
6. Online submodular minimization
7. Online matrix prediction，与 Shai Shalev-Shwartz 合作
8. Multiplicative weights 及其应用，与我们的导师 Sanjeev Arora 合作

而所有这些研究背后，都伴随着一种非常强烈的伙伴感。我们甚至不需要把对方的话补完，更像是两个人一直处在同一个频率上。连喜欢吃的东西、喜欢去的地方都差不多。

图：读博期间，Satyen 和我站在写满公式的白板前。

图：读博期间的 Satyen 和我。

我尤其记得某一届 NeurIPS，应该是 2008 年，在加拿大温哥华举办。当时我需要续签美国签证。结果申请基本等于被拒了，或者说，我被告知处理可能要花几个月时间，而在这期间，我必须一直待在美国境外。我在领事馆解释说，我家里还有一个小宝宝，正在加州等我，但完全没用。我就这么被困在了加拿大，也不知道下一步该怎么办。

所谓患难见真情。Satyen 就留在了温哥华陪我。他在我旁边开了一间酒店房——也可能直接和我住一起了，我已经记不清。总之，在我想清楚接下来怎么办之前，我们就一起工作、一起闲逛。最后，我的解决办法居然是跑去了一趟 Patagonia…… :-) 更离谱的是，就在那段时间里，我们又一起写出了三篇新论文！

初为教授的日子

梦想终于实现了。我在以色列拿到了教职，去了 Technion。那是一所顶尖大学，虽然我所在的是工业工程学院——说实话，这并不是我的第一选择。更巧的是，我还赶上了 Arkadi Nemirovski 在那里任教的最后一段时间。简直不能更完美。

但其实，还可以更完美。因为此前根本没人告诉我：指导研究生竟然可以这么快乐。那是一种完全不同于其他关系的体验，你投入多少，最后得到的回报往往是十倍。我一共指导了四位研究生：Tomer Koren、Dan Garber、Kfir Levy 和 Oren Anava。其中三位后来都成了非常优秀的教授。那几年，OCO 还在快速发展，世界各地不断涌现出新结果，我这块「小小的天堂」里也一样。很多朋友来访问过我们，包括 Jake Abernethy、Manfred Warmuth、Sham Kakade、Alexander Madry，当然也包括 Satyen，还有很多很多人。那段时期，我自己最喜欢的一些结果包括：

1. Playing non-linear games with linear oracles，与 Dan Garber 合作
2. The equivalence of Blackwell approachability and no-regret learning，与 Jake Abernethy、Peter Bartlett 合作
3. Beating SGD: learning SVMs in sublinear time，与 Tomer Koren、Nati Srebro 合作
4. Tight bounds for stochastic and online logistic regression，与 Tomer Koren、Kfir Levy 合作

图：Jake Abernethy 和我，在 Technion 的办公室里。

图：Technion 时期，我和学生 Tomer Koren、Kfir Levy、Oren Anava，在一家叫 Alabama 的烟熏肉餐厅外面。Dan Garber 没来——因为他是素食主义者 :-)

动力系统、控制与 Spectral Transformer

随着深度学习崛起，自适应梯度方法也逐渐被认为是这场革命中的重要组成部分。后来，我同时收到了 Stanford 和 Princeton 的 offer，最终选择回到自己的母校 Princeton。成为 Princeton 教授以后，我又做了几年优化研究，但慢慢地，我对 OCO 的兴趣开始减弱。根本原因，是 AI 正在变得越来越强大。其实早在那个时候，我就已经开始和 Scott Aaronson 讨论 AI alignment 问题了——Scott 可以给我作证，对吧？！

真正让我转向另一个方向的触发点，是 Tengyu Ma 的一次报告。Tengyu 以前也是 Sanjeev 在 Princeton 的学生。那场报告讲的是他和 Benjamin Recht、Moritz Hardt 一起做的一项工作：在统计设定下学习线性动力系统。但我一听见 statistical models 就会「过敏」…… :-) 所以我跟我的学生 Cyril 和 Karan 说：肯定还有别的做法，我们给这个问题来一次 regret treatment 吧……

结果，我这两个聪明得不得了的学生发明出了一套新技术，后来带我们走得比最初想象中远得多：spectral filtering（谱滤波）。它背后的技术其实非常 OCO，从 improper learning，到快速在线优化，再到 regret minimization，都是 OCO 的味道。核心思想是：我们不必真的把那个隐藏的动力系统识别出来。相反，我们可以使用一个不同的、规模更大的预测器类别，直接去和它竞争。这已经是我们第 N 次使用同一种套路了，只不过这一次，目标变成了动力系统。框架仍然是通过 regret 实现 improper learning，而 spectral filtering 则是这个框架的第一个具体实例。具体来说，我们会用一小组从 Hankel 矩阵中构造出来的固定 filter，对历史序列进行卷积，然后学习应该怎样组合这些 filter。这样一来，原本的预测问题，在新的参数化之下居然变成了一个凸问题。最初的结果只能处理 symmetric systems，但后来，这套方法被大幅扩展。最近，我还和博士后 Annie Marsden——顺带一提，她是 John Duchi 的学生——一起把它推进到了 universal sequence preconditioning。

控制问题又带来了另一层复杂性，因为一个 action 不仅会改变当前的 loss，还会改变未来的 state。在 nonstochastic control 中，我们比较的是：在完全相同的 disturbance 之下，如果换成另一个 controller，并且让它沿着自己的 trajectory 演化，它最终能够取得怎样的表现？再一次，真正关键的是找到一个正确的 controller 参数化方法。一旦参数化选对，我们就能够把在线凸优化塞进一个动力学问题里面。后来，我和 Karan 还专门写了一本关于这套方法的书。所以，也许我其实从来没有真正离开过 OCO……

接下来，事情又出现了一个转折。这些想法最后居然把我们重新带回了深度学习。我和 Naman Agarwal、Daniel Suo、Xinyi Chen 一起，用 spectral filtering 构建出了 spectral state space models，后来又发展出了 Flash STU。就这样，一个最初为了证明 regret theorem 而设计出来的 representation，最后竟然成为了神经网络架构的一部分。当年我们开始读 Cover 的论文时，可完全没想过事情最后会变成这样 :-)

图：我早期在 Princeton 的实验室成员。从左到右是 Xinyi、Karan、Brian、我和 Naman。

图：与 Princeton 的学生们聚餐。桌边依次有 Cyril、我、Zhou、Udaya、Nataly、Wenhan、Naman、Jennifer 和 Xinyi。

最后想说的话

现在回头看，我觉得这一切从「害怕找不到教职」开始，并不是偶然。这种恐惧，把我从一条主要依靠定理证明能力的道路上推开了。毕竟，那是一条竞争极其激烈的道路。我转而开始做另一件事：构建框架。如果是在今天这个 AI 时代，我会更加主动地做出同样的选择。随着 AI 越来越擅长证明定理，选择有意思的问题，以及创造新的框架，会变得更加重要。至少对我来说，这部分一直都是更有价值的工作。

我对 OCO 这门科学非常、非常满意。无论从数学上的优雅程度，还是现实中的实际价值来看，它都远远超过了我当初的期待。但毫无疑问，我真正最重要的收获，是在这条路上建立起来的那些关系——和我的学生，和我的合作者。所以到头来，我可以说：我完全没有 regret :-)

最后，还是要为遗漏掉许多合作和交流表示歉意。尤其是我与 Jake Abernethy、Sasha Rakhlin 围绕 bandit optimization 的合作，完全值得单独写一个故事。还有我与 Adam Kalai、Sham Kakade、Shay Moran、Paula Gradu、Xinyi Chen、Jennifer Sun、Annie Marsden，以及许许多多其他人的交流，也都没有来得及展开。