梯度下降是機(jī)器學(xué)習(xí)中求最小值最常用的一種算法。盡管這種算法應(yīng)用廣泛，但是人們關(guān)于它計(jì)算復(fù)雜度的理論研究卻寥寥無(wú)幾。
在今年 ACM 舉辦的計(jì)算機(jī)理論頂會(huì) STOC 上，牛津大學(xué)和利物浦大學(xué)的學(xué)者們，給我們證明了這個(gè)理論問(wèn)題的答案。
他們得到了梯度下降算法的計(jì)算復(fù)雜度，等于兩類(lèi)計(jì)算機(jī)問(wèn)題的交集。
這篇文章也成為了 STOC 2021 的最佳論文。
梯度下降的復(fù)雜度
四位作者研究人員將目光放在了 TFNP 中兩個(gè)子集問(wèn)題的交集。
第一個(gè)子集稱為 PLS （多項(xiàng)式局部搜索）。
這是一系列問(wèn)題，涉及在特定區(qū)域中尋找函數(shù)的最小值或最大值。
屬于 PLS 的一個(gè)典型例子是規(guī)劃一條路線的任務(wù)，以最短的路線經(jīng)過(guò)一些城市，且只能通過(guò)切換城市的順序來(lái)改變行程。
通過(guò)調(diào)整順序可以很容易看出哪些路線縮短了行程，最終你會(huì)找到某一條路線，無(wú)法進(jìn)一步縮短路程，這條路線 x 就是你要找到的最小值。
用數(shù)學(xué)公式來(lái)表示就是：（p 是求路線總長(zhǎng)度的函數(shù)，g (x) 表示改變 x 得到的新路線）
TFNP 問(wèn)題的第二個(gè)子集是 PPAD （有向圖上的多項(xiàng)式奇偶校驗(yàn)參數(shù)）。
這個(gè)問(wèn)題的解來(lái)自更復(fù)雜的過(guò)程，比如 Brouwer 不動(dòng)點(diǎn)定理，即對(duì)于滿足一定條件的連續(xù)函數(shù)，存在一個(gè)點(diǎn)保持不變。
例如，如果你攪動(dòng)一杯水，Brouwer 不動(dòng)點(diǎn)定理保證絕對(duì)會(huì)有一個(gè)水分子會(huì)回到它最初的位置。
用數(shù)學(xué)公式來(lái)表示就是：
實(shí)際應(yīng)用中，我們不可能要求找到以上兩個(gè)問(wèn)題絕對(duì)精確的解，只要誤差小于規(guī)定的值 ε 即可，也就是：
PLS 和 PPAD 這兩類(lèi)問(wèn)題的交集本身形成了一類(lèi)稱為 PLS∩PPAD 的問(wèn)題。
然而，直到現(xiàn)在，研究人員都無(wú)法找到 PLS∩PPAD 完全問(wèn)題的一個(gè)天然的例子。所謂的完全問(wèn)題，就是某類(lèi)問(wèn)題中最典型、最難的問(wèn)題。
現(xiàn)在，來(lái)自牛津大學(xué)和利物浦大學(xué)的學(xué)者們終于找到了，梯度下降問(wèn)題（GD）就是，它等價(jià)于 PLS 與 PPAD 的交集。
PPAD∩PLS 是可以通過(guò)在有界域上執(zhí)行梯度下降來(lái)解決的所有問(wèn)題的類(lèi)別。
而 PLS 與 PPAD 的交集，被他們證明等價(jià)于 CLS （連續(xù)局域搜索問(wèn)題）
PLS 與 PPAD 的任意解（either-solution）就是 PLS∩PPAD 完全問(wèn)題的解。
到了這里，梯度下降算法與這兩個(gè)問(wèn)題有什么聯(lián)系呢？
請(qǐng)看梯度下降算法的迭代公式：
在求解實(shí)際問(wèn)題，我們也是在尋找局部最小值的近似解。我們可以設(shè)置兩種計(jì)算終止條件：
1、如果 x’與 x 這兩個(gè)點(diǎn)的損失函數(shù)小于精度 ε：
那么計(jì)算終止，這與前面 PLS 中的 Real-Local-Opt 問(wèn)題類(lèi)似。
2、如果 x’與 x 這兩個(gè)點(diǎn)的空間距離小于精度 ε：
那么計(jì)算終止，這與前面 PPAD 中的 Brouwer 不動(dòng)點(diǎn)問(wèn)題類(lèi)似。
第一種相當(dāng)于是 PLS，第二種相當(dāng)于是 PPAD。
該結(jié)果意味著，梯度下降算法精度和速度之間存在基本聯(lián)系，為獲得更高精度，計(jì)算時(shí)間將會(huì)不成比例地迅速增長(zhǎng)。
精度與時(shí)間的平衡點(diǎn)
實(shí)際上，吳恩達(dá)在自己的機(jī)器學(xué)習(xí)課程中已經(jīng)指出，梯度下降算法的運(yùn)算復(fù)雜度和步數(shù) n 的平方成正比。
若對(duì)精度要求高，需要將學(xué)習(xí)率 η 設(shè)置得更小。
如果機(jī)器學(xué)習(xí)研究者可能希望將實(shí)驗(yàn)的精度提高到 2 倍，那么可能不得不將梯度下降算法的運(yùn)行時(shí)間增加到 4 倍。
這表明，梯度下降在實(shí)踐中必須做出某種妥協(xié)。要么接受不太高的精度，要么花費(fèi)更長(zhǎng)的運(yùn)行時(shí)間來(lái)?yè)Q取。
例如，一些對(duì) SGD 進(jìn)行加速的優(yōu)化算法，雖然收斂速度更快，但很有可能陷入局部最小值。要想獲得精度更高的結(jié)果，往往必須回歸到 SGD。
對(duì)于某些精度很重要的問(wèn)題，運(yùn)行時(shí)長(zhǎng)會(huì)讓梯度下降算法變得不可行。
但這并不是說(shuō)梯度下降的快速算法不存在，但如果存在著這樣的算法，將意味著 PLS∩PPAD 也存在快速算法，但尋找后者的快速算法要比前者難得多。
最后，這一問(wèn)題的計(jì)算機(jī)自動(dòng)證明代碼已經(jīng)開(kāi)源，有興趣的朋友可以前去觀摩嘗試。
參考鏈接：
https://www.quantamagazine.org/how-big-data-carried-graph-theory-into-new-dimensions-20210819/
https://www.youtube.com/watch?v=as720_SRpY0&ab_channel=SIGACTEC
https://arxiv.org/abs/2011.01929
https://github.com/jfearnley/PPADPLS/
廣告聲明：文內(nèi)含有的對(duì)外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。