清华新闻网7月9日电 近日，清华大学交叉信息院博士生陈乐偲和助理教授张景昭的科研成果“求解二阶Oracle复杂度的凹凸问题”（Solving Convex-Concave Problems with Second-Order Oracle Complexity）在机器学习理论的国际顶级会议Conference on Learning Theory（COLT）2025上获得最佳学生论文奖。

陈乐偲在会上宣读论文

该工作聚焦数值优化领域的经典问题极小极大优化问题进行探索。该问题考虑计算一个凸-凹函数的鞍点，其源自于博弈论中寻找双玩家零和博弈的Nash均衡点问题，并且在带约束优化的拉格朗日（Lagrange）函数求解问题、分布鲁棒优化问题以及机器学习中的对抗训练问题等场景中都具有重要应用。

作为数值优化的经典问题，极小极大优化问题的研究具有悠久的历史。早在1976年俄国数学家Korpelevich就提出了被沿用至今的外梯度法，并且证明该算法可以在梯度查询内找到一个ϵ-鞍点。该算法也被后续工作证明在所有一阶算法类（也即利用梯度信息的算法类）中是最优的。2012年，Monteiro和Svaiter将Korpelevich的外梯度法推广到了二阶算法，即同时利用梯度和Hessian矩阵信息的算法类（也被称为牛顿类算法），并且得到了 的迭代复杂度上界。从2012年以后，研究者们提出了大量类似的算法，并且也将算法推广到使用P阶导数信息的设定，但是对于p=2的情况都只能得到相同的的保证。由于该问题超过十年没有突破，机器学习领域泰斗Michael I. Jordan以及优化领域泰斗Yurii Nesterov都分别在他们2022-2023年的文章中推断该问题的最优二阶复杂度就是。

然而，该研究打破了领域中人们的普遍认知，提出了一个新的算法，并证明其可以在的二阶复杂度内寻找到任意光滑凸-凹函数的ϵ-鞍点，其中符号隐藏了复杂度中可忽略不计的对数因子。该算法巧妙地对于极小化变量以及极大化变量同时使用Monteiro和Svaiter在2013年所提出的高阶动量加速技术，将原问题归约为求解个条件数为常数的极小极大优化子问题，最终调用任意一个已知的收敛算法求解上述子问题都可以达到该研究的新结果。

尽管外梯度法很早就被证明是最优的一阶算法，但张景昭研究团队的本突破性成果证明了在更高阶（p≥2）的设定下，实际上存在着比外梯度法更优的算法。该结果刷新了人们对该经典问题复杂度的认知，对于启发更快速的算法设计具有重大意义。

论文第一作者为清华大学交叉信息院2023级博士生陈乐偲，论文通讯作者为交叉信息院助理教授张景昭，其他作者为香港中文大学2022级博士生刘程畅以及复旦大学副研究员罗珞。

论文链接：

https://arxiv.org/abs/2506.08362

供稿：交叉信息院

编辑：李华山

审核：郭玲