在機器學習的世界中，最優化問題非常重要，它們能使世界變得更好。最優化問題旨在尋求完成某件事情的最佳方式，比如手機 GPS 計算達到目的地的最短路線，旅游網站搜索與行程相匹配的最便宜的航班。同時，機器學習應用通過分析數據模式進行學習，并試圖為任何給定的最優化問題提供最準確和最人性化的答案。

對于簡單的最優化問題，找到最佳解決方案只是一個算術問題。1847 年，法國數學家奧古斯丁 - 路易?柯西（Augustin-Louis Cauchy）研究了一個相當復雜的例子 —— 天文計算。在那時他開創了一種常見的優化方法，也就是現在的梯度下降，它是優化方法中最經典和最簡單的一階方法之一。

如今，得益于其較低復雜度和簡單操作，大多數機器學習程序都極其依賴梯度下降方法，其他領域也用它分析數據和解決工程問題。一百多年來，數學家們一直在完善梯度下降方法。然而上個月的一篇論文表明，關于梯度下降方法的基本假設可能是錯誤的。

這篇論文為《Provably Faster Gradient Descent via Long Steps》，唯一作者為約翰霍普金斯大學應用數學與統計學助理教授 Benjamin Grimmer。他對于自己的發現感到非常驚訝，就像直覺被打破一樣。

他的反直覺結果表明，如果長期以來被認可的、找到給定問題最佳答案的規則被打破，則梯度下降的速度可以實現近 3 倍提升。再具體一點：他認為梯度下降算法可以通過包含意想不到的大步長（large step size）來更快地工作，這與研究人員長期以來所認為的相反。

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

雖然這一理論上的進展可能不適用于機器學習解決更棘手的問題，但可以促使研究人員重新考慮對梯度下降的理解。

MIT 的一名優化研究員 Shuvomoy Das Gupta 對此表示，「事實證明，我們并沒有完全理解梯度下降背后的理論。現在，這項研究讓我們更接近理解梯度下降的作用了?！?/span>

Benjamin Grimmer

我們接下來看一看這項工作的具體內容。

研究概覽

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

結果表明，更大的步長在短期內增加了目標值，但長期內實現了可證明的、更快的收斂。此外通過簡單的數值驗證，作者還提出了證明更快 O (1/T log T) 梯度下降率的一個猜想。

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

在具體操作中，設計可證明的更快非恒定步長梯度下降方法相當于尋找具有很大平均步長值的直接（straightforward）步長模式。證明給定的模式很簡單，可以利用半定規劃來完成，參見定理 3.1。

下表 1 展示了越來越快的收斂保證的直接步長模式，其中每個模式都使用計算機生成的、精確算術半定規劃解決方案進行了驗證。未來的工作將確定更大步長的直接模式和其他可處理的非恒定、周期性大步長策略。

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

作者表示，其方法與賓夕法尼亞大學優化研究員 Jason Altschuler 首次提出的方法非常相似，后者建立了長度為 2 或 3 的重復步長模式，并向最小化器更快收縮，實現平滑、強凸的最小化。

更細節的內容請參閱原論文。

從小步長到大步長，突破長度限制

我們知道，盡管沒人能證明步長越小越好，但幾十年來該領域的傳統觀點一直是采用小步長。這意味著在梯度下降方程中，步長不大于 2。

隨著計算機輔助技術的進步，優化理論家已經開始測試更極限的技術。比如最近發表在《數學編程》期刊上的一項工作，Das Gupta 和其他研究者要求計算機為僅限 50 步的算法找到最佳步長，這是一種元優化問題。他們發現，最佳 50 步的長度變化很大，序列中一個步驟的長度幾乎達到了 37，遠高于長度 2 的典型上限。

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

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

Grimmer 發現，最快的序列總是有一個共同點，即中間的一步總是很大，其大小取決于重復序列中的步驟數。對于 3 步序列，大步的長度為 4.9；對于 15 步序列，算法建議步長為 29.7；對于測試中最長的 127 步序列，中間的最大步長為 370。最終的結果表明，序列達到最佳點的速度是連續小步長速度的近三倍。

理論雖新穎，但無法改變當前使用方式

法國帕萊索理工學院優化研究員 Aymeric Dieuleveut 表示，這種循環方法代表了一種不同的梯度下降思維方式。他說道，「直覺告訴我，我不應該一步一步地思考問題，而是應該連續思考多個步驟。我認為很多人都忽略了這一點?！?/span>

不過，雖然這些見解可能會改變研究人員對梯度下降的看法，但可能不會改變這項技術目前的使用方式。畢竟，Grimmer 的論文只關注光滑函數和凸函數，光滑函數沒有尖銳彎曲，凸函數的形狀像一個碗，底部只有一個最優值。這些函數在理論上是最基礎的，但在實踐中卻不那么重要。機器學習研究人員使用的優化程序通常要復雜得多。

蒙特利爾大學優化與機器學習研究員 Gauthier Gidel 表示，一些經過改進的技術可以使 Grimmer 的大步長方法更快，但這些技術需要付出額外的運行成本。因此人們一直希望常規梯度下降法能在步長的正確組合下勝出。遺憾的是，這項新研究的三倍提速還遠遠不夠。

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

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

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