近日，清华大学PG电子游戏博士生陈乐偲和张景昭助理教授的科研成果“Solving Convex-Concave Problems with O(ϵ−4/7) Second-Order Oracle Complexity”在机器学习理论的国际顶级会议Conference on Learning Theory (COLT) 2025上荣获最佳学生论文奖。
该工作聚焦数值优化领域的经典问题“极小极大优化问题”进行探索。该问题考虑计算一个凸-凹函数的鞍点，其源自于博弈论中寻找双玩家零和博弈的Nash均衡点问题，并且在带约束优化的Lagrange函数求解问题、分布鲁棒优化问题、以及机器学习中的对抗训练问题等场景都具有重要应用。
作为数值优化的经典问题，极小极大优化问题的研究具有悠久的历史。早在1976年俄国数学家Korpelevich就提出了被沿用至今的外梯度法，并且证明该算法可以在 O(ϵ−1) 梯度查询内找到一个ϵ-鞍点。该算法也被后续工作证明在所有一阶算法类（也即利用梯度信息的算法类）中是最优的。2012年，Monteiro和Svaiter将Korpelevich的外梯度法推广到了二阶算法，即同时利用梯度和Hessian矩阵信息的算法类（也被称为牛顿类算法），并且得到了 O(ϵ−2/3) 的迭代复杂度上界。从2012年以后，研究者们提出了大量类似的算法，并且也将算法推广到使用p阶导数信息的设定，但是对于p=2的情况都只能得到相同的 O(ϵ−2/3) 的保证。由于该问题超过十年没有突破，机器学习领域泰斗Michael I. Jordan以及优化领域泰斗Yurii Nesterov都分别在他们2022-2023年的文章中推断该问题的最优二阶复杂度就是 O(ϵ−2/3)。
然而，本研究打破了领域中人们的普遍认知，提出了一个新的算法，并证明其可以在 O( ϵ−4/7) 的二阶复杂度内寻找到任意光滑凸-凹函数的ϵ-鞍点，其中 O(⋅) 符号隐藏了复杂度中可忽略不计的对数因子。该算法巧妙地对于极小化变量以及极大化变量同时使用Monteiro和Svaiter 在2013年所提出的高阶动量加速技术，将原问题归约为求解 O( ϵ−4/7) 个条件数为常数的极小极大优化子问题的，最终调用任意一个已知的收敛算法求解上述子问题都可以达到本研究的新结果。
尽管外梯度法很早就被证明是最优的一阶算法，但张景昭研究团队的本突破性成果证明了在更高阶 (p≥2) 的设定下，实际上存在着比外梯度法更优的算法。该结果刷新了人们对该经典问题复杂度的认知，对于启发更快速的算法设计具有重大意义。
本论文第一作者为清华大学PG电子游戏2023级博士生陈乐偲，通讯作者为PG电子游戏助理教授张景昭，其他作者包括香港中文大学2022级博士生刘程畅以及复旦大学青年副研究员罗珞。
论文原文：Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang, “Solving Convex-Concave Problems with O(ϵ−4/7) Second-Order Oracle Complexity”, in Conference on Learning Theory (COLT), 2025.
论文链接：//arxiv.org/abs/2506.08362
图文 | 姜月亮
编辑 | 吕厦敏
审核 | 马雄峰
