他們得到梯度下降算法的計算復雜度等于兩類計算機問題的交集

梯度下降是機器學習中最常用的求最小值的算法之一雖然該算法被廣泛使用，但對其計算復雜度的理論研究卻很少

在今年由ACM舉辦的STOC計算機理論峰會上，來自牛津大學和利物浦大學的學者證明了這個理論問題的答案。

他們得到梯度下降算法的計算復雜度等于兩類計算機問題的交集。

這篇文章也成為了STOC 2021的最佳論文。

梯度下降的復雜性

第一個子集叫做PLS。

這是一系列問題，涉及到在特定區域內尋找函數的最小值或最大值。

PLS的一個典型例子就是規劃一條路線的任務，途經一些路線最短的城市，只有切換城市的順序才能改變行程。

通過調整順序，很容易看出哪些路線縮短了行程，最終會找到某一條路線，無法進一步縮短行程這條路線X是你需要找到的最小值

用數學公式表示:表示改變X得到的新路線)

TFNP問題的第二個子集是PPAD(有向圖上的多項式奇偶校驗參數)。

這個問題的解來自一個更復雜的過程，比如Brouwer不動點定理，即對于滿足一定條件的連續函數，有一個點保持不變。

比如你攪拌一杯水，布勞威爾不動點定理保證水分子一定會回到原來的位置。

用數學公式來表達就是:

在實際應用中，我們不可能找到上述兩個問題的絕對精確解，只要誤差小于規定值，即:

PLS和PPAD的交集本身就形成了一種叫PLSPPAD的問題。

可是，直到現在，研究人員還沒有找到PLSPPAD完全問題的自然例子所謂完全問題，是某種問題中最典型，最困難的問題

現在，牛津大學和利物浦大學的學者終于發現梯度下降問題(GD)相當于PLS和PPAD的交集。

PPADPLS是一類可以通過對有界區域進行梯度下降來解決的問題。

PLS和PPAD的交集被證明等價于CLS(連續局部搜索問題)

PLS和PPAD的非此即彼解就是PLSPPAD完全問題的解。

這里，梯度下降算法和這兩個問題有什么聯系。

請看梯度下降算法的迭代公式:

在解決實際問題時，我們也在尋找局部最小值的近似解。我們可以設置兩個計算終止條件:

1.如果x’和x的損失函數小于精度:

然后終止計算，這類似于PLS中的真實—局部—最優選擇問題。

2.如果x’和x之間的空間距離小于精度:

然后終止計算，這類似于PPAD的Brouwer不動點問題。

第一個相當于PLS，第二個相當于PPAD。

這一結果意味著梯度下降算法的精度和速度之間存在基本關系為了獲得更高的精度，計算時間會不成比例地快速增加

精度和時間的平衡點

事實上，吳恩達在自己的機器學習課程中已經指出，梯度下降算法的計算復雜度與步數n的平方成正比。

如果精度高，需要將學習速率設置得更小。

如果機器學習研究人員可能想要將實驗的準確率提高2倍，那么他們可能需要將梯度下降算法的運行時間提高4倍。

這表明在實踐中必須做出一些妥協要么接受不太高的精度，要么花更長的運行時間作為交換

例如，一些加速SGD的優化算法收斂速度較快，但很可能陷入局部極小為了得到更高精度的結果，往往需要返回到SGD

對于一些具有重要精度的問題，運行時間會使梯度下降算法不可行。

但這并不是說梯度下降沒有快速算法，但如果有這樣的算法，那就意味著PLSPPAD也有快速算法，但找到后者的快速算法要比前者困難得多。

最后電腦自動證明這個問題的代碼已經開源，感興趣的朋友可以去觀察試試。

參考鏈接: