清华大学交叉信息院张景昭团队科研成果获得COLT 2025学生论文奖
2025/07/10
近日,清华大学交叉信息院博士生陈乐偲和助理教授张景昭的科研成果“求解二阶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级博士生刘程畅以及复旦大学副研究员罗珞。
文章来源清华大学,分享只为学术交流,如涉及侵权问题请联系我们,我们将及时修改或删除。
-
第五届传感、测量、通信与物联网技术国 42
-
2026年9月优质国际学术会议推荐 263
-
2026年第15届计算与模式识别国际 212
-
2026年第二届计算机视觉与机器学习 2124
-
2026年无人机遥感与人工智能国际会 472
-
2026资源、化学化工与应用材料国际 3740
-
2026年图像处理与数字创意设计国际 3525
-
2026年机械工程,新能源与电气技术 8084
-
2026年材料科学、低碳技术与动力工 3712
-
第三届国际会议语言学、心理学与创意教 08-07
-
2026年建筑科学、材料工程与可持续 08-07
-
2026年国际会议金融科技、市场营销 08-07
-
第三届国际社会科学与文化研究会议平行 08-07
-
ICSSCS 2026 - 子论坛: 08-07
-
第三届社会科学与文化研究国际会议平行 08-07
-
2026 JCR影响因子正式发布1135
-
中国科协发布2025年《重要学术1583
-
2026年新锐分区(原中科院期刊8243
-
2025年两院院士增选有效候选人6001
-
好学术:科研网址导航|学术头条分7917
-
2025年国际期刊预警名单发布!8062
-
2025年中科院期刊分区表重磅发28351
-
吉林大学校长张希:学术会议中的提9122
-
清华大学计算机系高性能所获得IE07-31
-
北京大学生命科学学院伊成器课题组07-31
-
北京大学罗欢、李阿明、方方课题组07-31
-
北京大学生命科学学院郭强团队与合07-31
-
清华大学集成电路学院任天令团队合07-31
-
清华大学5位清华人当选“202607-31
-
研究揭示热带雨林优势树种望天树幼07-31
-
北京联佳业广告有限公司 2510

-
上海拜尔德科技有限公司 24499

-
西安华线石油科技有限公司 21539

-
阜阳师范学院 2466

-
南京邮电大学 21604

-
武汉工程大学 21533

-
成长在北京-线下网站北京发展网 18863

-
中国仪器仪表学会 中国系统仿真学 21717

-
上海大学材料学院 21726

-
中国医师协会胸外科医师分会 24732

-
贵州德捷会晤服务有限公司 18850

-
上海交通大学 8598

-
潇湘行商务服务(北京)有限公司 21746

-
武汉理工大学 2602

-
郑州轻工业学院 23452

-
上海浦融会展服务有限公司 18336

-
郑州大学 8936

-
中国水利教育协会 2589

-
名校通(北京)教育科技有限公司 8604

-
云南欧亿骏机电设备有限公司 18625





















623








































