在機(jī)器學(xué)習(xí)的世界中，最優(yōu)化問(wèn)題非常重要，它們能使世界變得更好。最優(yōu)化問(wèn)題旨在尋求完成某件事情的最佳方式，比如手機(jī) GPS 計(jì)算達(dá)到目的地的最短路線，旅游網(wǎng)站搜索與行程相匹配的最便宜的航班。同時(shí)，機(jī)器學(xué)習(xí)應(yīng)用通過(guò)分析數(shù)據(jù)模式進(jìn)行學(xué)習(xí)，并試圖為任何給定的最優(yōu)化問(wèn)題提供最準(zhǔn)確和最人性化的答案。

對(duì)于簡(jiǎn)單的最優(yōu)化問(wèn)題，找到最佳解決方案只是一個(gè)算術(shù)問(wèn)題。1847 年，法國(guó)數(shù)學(xué)家?jiàn)W古斯丁 - 路易?柯西（Augustin-Louis Cauchy）研究了一個(gè)相當(dāng)復(fù)雜的例子 —— 天文計(jì)算。在那時(shí)他開(kāi)創(chuàng)了一種常見(jiàn)的優(yōu)化方法，也就是現(xiàn)在的梯度下降，它是優(yōu)化方法中最經(jīng)典和最簡(jiǎn)單的一階方法之一。

如今，得益于其較低復(fù)雜度和簡(jiǎn)單操作，大多數(shù)機(jī)器學(xué)習(xí)程序都極其依賴梯度下降方法，其他領(lǐng)域也用它分析數(shù)據(jù)和解決工程問(wèn)題。一百多年來(lái)，數(shù)學(xué)家們一直在完善梯度下降方法。然而上個(gè)月的一篇論文表明，關(guān)于梯度下降方法的基本假設(shè)可能是錯(cuò)誤的。

這篇論文為《Provably Faster Gradient Descent via Long Steps》，唯一作者為約翰霍普金斯大學(xué)應(yīng)用數(shù)學(xué)與統(tǒng)計(jì)學(xué)助理教授 Benjamin Grimmer。他對(duì)于自己的發(fā)現(xiàn)感到非常驚訝，就像直覺(jué)被打破一樣。

他的反直覺(jué)結(jié)果表明，如果長(zhǎng)期以來(lái)被認(rèn)可的、找到給定問(wèn)題最佳答案的規(guī)則被打破，則梯度下降的速度可以實(shí)現(xiàn)近 3 倍提升。再具體一點(diǎn)：他認(rèn)為梯度下降算法可以通過(guò)包含意想不到的大步長(zhǎng)（large step size）來(lái)更快地工作，這與研究人員長(zhǎng)期以來(lái)所認(rèn)為的相反。

論文地址：https://arxiv.org/pdf/2307.06324.pdf

雖然這一理論上的進(jìn)展可能不適用于機(jī)器學(xué)習(xí)解決更棘手的問(wèn)題，但可以促使研究人員重新考慮對(duì)梯度下降的理解。

MIT 的一名優(yōu)化研究員 Shuvomoy Das Gupta 對(duì)此表示，「事實(shí)證明，我們并沒(méi)有完全理解梯度下降背后的理論。現(xiàn)在，這項(xiàng)研究讓我們更接近理解梯度下降的作用了?！?/span>

Benjamin Grimmer

我們接下來(lái)看一看這項(xiàng)工作的具體內(nèi)容。

研究概覽

本文通過(guò)一種計(jì)算機(jī)輔助分析技術(shù)，在平滑凸優(yōu)化中建立了可以證明更快的梯度下降收斂速度。其中，作者分析了一次多次迭代的整體效果而非大多數(shù)一階方法分析中使用的典型單次迭代歸納，從而允許非恒定步長(zhǎng)策略。

結(jié)果表明，更大的步長(zhǎng)在短期內(nèi)增加了目標(biāo)值，但長(zhǎng)期內(nèi)實(shí)現(xiàn)了可證明的、更快的收斂。此外通過(guò)簡(jiǎn)單的數(shù)值驗(yàn)證，作者還提出了證明更快 O (1/T log T) 梯度下降率的一個(gè)猜想。

具體地講，作者的證明基于性能估計(jì)問(wèn)題（PEP）思路，它將計(jì)算或限制給定算法的最壞情況問(wèn)題實(shí)例作為半定規(guī)劃（Semidefinite Program, SDP）來(lái)處理。通過(guò)相關(guān) SDP 可行解的存在，作者證明了應(yīng)用非恒定步長(zhǎng)模式后的下降保證，從而獲得更快收斂保證。

在具體操作中，設(shè)計(jì)可證明的更快非恒定步長(zhǎng)梯度下降方法相當(dāng)于尋找具有很大平均步長(zhǎng)值的直接（straightforward）步長(zhǎng)模式。證明給定的模式很簡(jiǎn)單，可以利用半定規(guī)劃來(lái)完成，參見(jiàn)定理 3.1。

下表 1 展示了越來(lái)越快的收斂保證的直接步長(zhǎng)模式，其中每個(gè)模式都使用計(jì)算機(jī)生成的、精確算術(shù)半定規(guī)劃解決方案進(jìn)行了驗(yàn)證。未來(lái)的工作將確定更大步長(zhǎng)的直接模式和其他可處理的非恒定、周期性大步長(zhǎng)策略。

但是，尋找長(zhǎng)的、直接步長(zhǎng)模式 h 很困難，所有直接模式的集合都是非凸的，導(dǎo)致局部搜索常常沒(méi)有結(jié)果。如表 1 所示，長(zhǎng)度 t = 2^m ? 1 的模式是通過(guò)重復(fù) t = 2^m?1 ? 1 兩次而創(chuàng)建的，中間添加了一個(gè)新的長(zhǎng)步，并手動(dòng)縮短長(zhǎng)度 2^m?1 ? 1 子模式中的長(zhǎng)步。作者表示，這種遞歸模式與以往研究中的二次極小化的循環(huán)和分形切比雪夫模式具有強(qiáng)相似性，還沒(méi)有證明它們之間的聯(lián)系。

作者表示，其方法與賓夕法尼亞大學(xué)優(yōu)化研究員 Jason Altschuler 首次提出的方法非常相似，后者建立了長(zhǎng)度為 2 或 3 的重復(fù)步長(zhǎng)模式，并向最小化器更快收縮，實(shí)現(xiàn)平滑、強(qiáng)凸的最小化。

更細(xì)節(jié)的內(nèi)容請(qǐng)參閱原論文。

從小步長(zhǎng)到大步長(zhǎng)，突破長(zhǎng)度限制

我們知道，盡管沒(méi)人能證明步長(zhǎng)越小越好，但幾十年來(lái)該領(lǐng)域的傳統(tǒng)觀點(diǎn)一直是采用小步長(zhǎng)。這意味著在梯度下降方程中，步長(zhǎng)不大于 2。

隨著計(jì)算機(jī)輔助技術(shù)的進(jìn)步，優(yōu)化理論家已經(jīng)開(kāi)始測(cè)試更極限的技術(shù)。比如最近發(fā)表在《數(shù)學(xué)編程》期刊上的一項(xiàng)工作，Das Gupta 和其他研究者要求計(jì)算機(jī)為僅限 50 步的算法找到最佳步長(zhǎng)，這是一種元優(yōu)化問(wèn)題。他們發(fā)現(xiàn)，最佳 50 步的長(zhǎng)度變化很大，序列中一個(gè)步驟的長(zhǎng)度幾乎達(dá)到了 37，遠(yuǎn)高于長(zhǎng)度 2 的典型上限。

論文地址：https://link.springer.com/article/10.1007/s10107-023-01973-1

這一結(jié)果表明，優(yōu)化研究人員遺漏了一些東西。因此，出于好奇，Grimmer 將 Das Gupta 的數(shù)值結(jié)果轉(zhuǎn)化為了更普遍的定理。為了突破 50 步的任意上限，他探索了可重復(fù)序列的最佳步長(zhǎng)，每次重復(fù)都更接近最佳答案。Grimmer 讓計(jì)算機(jī)進(jìn)行了數(shù)百萬(wàn)次步長(zhǎng)序列的排列，從而找到那些最快收斂到答案的序列。

Grimmer 發(fā)現(xiàn)，最快的序列總是有一個(gè)共同點(diǎn)，即中間的一步總是很大，其大小取決于重復(fù)序列中的步驟數(shù)。對(duì)于 3 步序列，大步的長(zhǎng)度為 4.9；對(duì)于 15 步序列，算法建議步長(zhǎng)為 29.7；對(duì)于測(cè)試中最長(zhǎng)的 127 步序列，中間的最大步長(zhǎng)為 370。最終的結(jié)果表明，序列達(dá)到最佳點(diǎn)的速度是連續(xù)小步長(zhǎng)速度的近三倍。

理論雖新穎，但無(wú)法改變當(dāng)前使用方式

法國(guó)帕萊索理工學(xué)院優(yōu)化研究員 Aymeric Dieuleveut 表示，這種循環(huán)方法代表了一種不同的梯度下降思維方式。他說(shuō)道，「直覺(jué)告訴我，我不應(yīng)該一步一步地思考問(wèn)題，而是應(yīng)該連續(xù)思考多個(gè)步驟。我認(rèn)為很多人都忽略了這一點(diǎn)?！?/span>

不過(guò)，雖然這些見(jiàn)解可能會(huì)改變研究人員對(duì)梯度下降的看法，但可能不會(huì)改變這項(xiàng)技術(shù)目前的使用方式。畢竟，Grimmer 的論文只關(guān)注光滑函數(shù)和凸函數(shù)，光滑函數(shù)沒(méi)有尖銳彎曲，凸函數(shù)的形狀像一個(gè)碗，底部只有一個(gè)最優(yōu)值。這些函數(shù)在理論上是最基礎(chǔ)的，但在實(shí)踐中卻不那么重要。機(jī)器學(xué)習(xí)研究人員使用的優(yōu)化程序通常要復(fù)雜得多。

蒙特利爾大學(xué)優(yōu)化與機(jī)器學(xué)習(xí)研究員 Gauthier Gidel 表示，一些經(jīng)過(guò)改進(jìn)的技術(shù)可以使 Grimmer 的大步長(zhǎng)方法更快，但這些技術(shù)需要付出額外的運(yùn)行成本。因此人們一直希望常規(guī)梯度下降法能在步長(zhǎng)的正確組合下勝出。遺憾的是，這項(xiàng)新研究的三倍提速還遠(yuǎn)遠(yuǎn)不夠。

Gidel 提出自己的疑問(wèn)，「雖然表明情況略有改善，但我想真正的問(wèn)題是：我們真的能縮小這個(gè)差距嗎？」

這些結(jié)果還提出了另一個(gè)令本文作者徹夜難眠的理論之謎。為什么步長(zhǎng)的理想模式都具有如此對(duì)稱的形狀？不僅最大的一步總是恰好在中間，而且它的兩邊也會(huì)出現(xiàn)同樣的模式：繼續(xù)放大并細(xì)分序列，會(huì)得到一個(gè)「幾乎分形的模式」，大的步長(zhǎng)被小的步長(zhǎng)包圍。這種重復(fù)暗示著，一種潛在的結(jié)構(gòu)正在支配最佳解決方案，目前還沒(méi)有人能夠解釋這種結(jié)構(gòu)。

但本文作者至少還抱有希望，「這個(gè)謎題，如果我破除不了，別人也會(huì)破除的?！?/span>