清華新聞網(wǎng)7月9日電 近日，清華大學(xué)交叉信息院博士生陳樂(lè)偲和助理教授張景昭的科研成果“求解二階Oracle復(fù)雜度的凹凸問(wèn)題”（Solving Convex-Concave Problems with 
Second-Order Oracle Complexity）在機(jī)器學(xué)習(xí)理論的國(guó)際頂級(jí)會(huì)議Conference on Learning Theory（COLT）2025上獲得最佳學(xué)生論文獎(jiǎng)。
陳樂(lè)偲在會(huì)上宣讀論文
該工作聚焦數(shù)值優(yōu)化領(lǐng)域的經(jīng)典問(wèn)題極小極大優(yōu)化問(wèn)題進(jìn)行探索。該問(wèn)題考慮計(jì)算一個(gè)凸-凹函數(shù)的鞍點(diǎn)，其源自于博弈論中尋找雙玩家零和博弈的Nash均衡點(diǎn)問(wèn)題，并且在帶約束優(yōu)化的拉格朗日（Lagrange）函數(shù)求解問(wèn)題、分布魯棒優(yōu)化問(wèn)題以及機(jī)器學(xué)習(xí)中的對(duì)抗訓(xùn)練問(wèn)題等場(chǎng)景中都具有重要應(yīng)用。
作為數(shù)值優(yōu)化的經(jīng)典問(wèn)題，極小極大優(yōu)化問(wèn)題的研究具有悠久的歷史。早在1976年俄國(guó)數(shù)學(xué)家Korpelevich就提出了被沿用至今的外梯度法，并且證明該算法可以在
梯度查詢(xún)內(nèi)找到一個(gè)?-鞍點(diǎn)。該算法也被后續(xù)工作證明在所有一階算法類(lèi)（也即利用梯度信息的算法類(lèi)）中是最優(yōu)的。2012年，Monteiro和Svaiter將Korpelevich的外梯度法推廣到了二階算法，即同時(shí)利用梯度和Hessian矩陣信息的算法類(lèi)（也被稱(chēng)為牛頓類(lèi)算法），并且得到了
的迭代復(fù)雜度上界。從2012年以后，研究者們提出了大量類(lèi)似的算法，并且也將算法推廣到使用P階導(dǎo)數(shù)信息的設(shè)定，但是對(duì)于p=2的情況都只能得到相同的的保證。由于該問(wèn)題超過(guò)十年沒(méi)有突破，機(jī)器學(xué)習(xí)領(lǐng)域泰斗Michael I. Jordan以及優(yōu)化領(lǐng)域泰斗Yurii Nesterov都分別在他們2022-2023年的文章中推斷該問(wèn)題的最優(yōu)二階復(fù)雜度就是。
然而，該研究打破了領(lǐng)域中人們的普遍認(rèn)知，提出了一個(gè)新的算法，并證明其可以在的二階復(fù)雜度內(nèi)尋找到任意光滑凸-凹函數(shù)的?-鞍點(diǎn)，其中
符號(hào)隱藏了復(fù)雜度中可忽略不計(jì)的對(duì)數(shù)因子。該算法巧妙地對(duì)于極小化變量以及極大化變量同時(shí)使用Monteiro和Svaiter在2013年所提出的高階動(dòng)量加速技術(shù)，將原問(wèn)題歸約為求解個(gè)條件數(shù)為常數(shù)的極小極大優(yōu)化子問(wèn)題，最終調(diào)用任意一個(gè)已知的收斂算法求解上述子問(wèn)題都可以達(dá)到該研究的新結(jié)果。
盡管外梯度法很早就被證明是最優(yōu)的一階算法，但張景昭研究團(tuán)隊(duì)的本突破性成果證明了在更高階（p≥2）的設(shè)定下，實(shí)際上存在著比外梯度法更優(yōu)的算法。該結(jié)果刷新了人們對(duì)該經(jīng)典問(wèn)題復(fù)雜度的認(rèn)知，對(duì)于啟發(fā)更快速的算法設(shè)計(jì)具有重大意義。
論文第一作者為清華大學(xué)交叉信息院2023級(jí)博士生陳樂(lè)偲，論文通訊作者為交叉信息院助理教授張景昭，其他作者為香港中文大學(xué)2022級(jí)博士生劉程暢以及復(fù)旦大學(xué)副研究員羅珞。
論文鏈接：
https://arxiv.org/abs/2506.08362
供稿：交叉信息院
編輯：李華山
審核：郭玲
