0
| 本文作者： 我在思考中 | 2021-08-19 10:34 |
作者 | Nick Thieme
編譯 | 陳彩嫻
許多現(xiàn)代應(yīng)用研究都對梯度下降算法有很強(qiáng)的依賴。梯度下降過程通常用于尋找特定數(shù)學(xué)函數(shù)中的最大值或最小值，這個(gè)過程也被稱為“優(yōu)化”該函數(shù)。它的計(jì)算應(yīng)用十分廣泛，上至研究利潤最大化的產(chǎn)品制造方式，下至制定日常工廠工人分配輪班的最佳方式。
然而，盡管梯度下降算法的用途十分廣泛，但研究人員從來沒有想明白，梯度下降在什么情況下會(huì)遇到“攔路虎”？
針對這個(gè)問題，來自英國牛津大學(xué)與利物浦大學(xué)的研究團(tuán)隊(duì)展開了合作研究工作。他們肯定了梯度下降從本質(zhì)上解決了一個(gè)十分困難的計(jì)算問題，但也指出，在某些特殊應(yīng)用中，梯度下降算法的表現(xiàn)受到了限制。他們的工作“The Complexity of Gradient Descent: CLS = PPAD ∩ PLS”發(fā)表在理論計(jì)算機(jī)頂會(huì) STOC 上，并獲得了 STOC 最佳論文獎(jiǎng)。
論文地址：https://arxiv.org/abs/2011.01929
梯度下降有多難
梯度下降是現(xiàn)代應(yīng)用研究的重要工具，但在許多常見的問題上，它的表現(xiàn)并不好。在這項(xiàng)研究之前，研究人員并不清楚梯度下降在何時(shí)、出于何種原因而變得不再有效。針對梯度下降的局限性，計(jì)算復(fù)雜性理論的知識有利于尋找這些問題的答案。
據(jù)麻省理工學(xué)院的副教授 Costis Daskalakis 介紹，此前，許多梯度下降的研究工作都沒有談到復(fù)雜性理論。
簡單來說，計(jì)算復(fù)雜性主要是研究解決或驗(yàn)證不同計(jì)算問題的解決方案所需要的資源（通常是計(jì)算時(shí)間）。研究人員將問題分為不同的類別，其中，同一個(gè)類別的所有問題具備同樣的基本計(jì)算特征。
舉一個(gè)例子：想象一個(gè)城鎮(zhèn)，在這個(gè)城鎮(zhèn)上，人的數(shù)量多于房子的數(shù)量，且每個(gè)人都住在一個(gè)房子里。給你一本電話簿，上面寫著鎮(zhèn)上每個(gè)人的姓名和地址，你需要找到住在同一所房子里的兩個(gè)人。你知道你是可以找到答案的，因?yàn)槿吮确孔佣?，但可能要查找好一?huì)（尤其是當(dāng)他們的姓氏不一樣時(shí)）。
這個(gè)問題屬于一個(gè)叫做“TFNP”的復(fù)雜性分類，是所有確保有解決方案、且可以快速驗(yàn)證解決方案是否正確的計(jì)算問題的集合。研究人員專注于研究 TFNP 中兩個(gè)問題子集的交集。
第一個(gè)子集叫做“PLS”（polynomial local search，“多項(xiàng)式局部搜索”）。PLS問題主要是為了找到函數(shù)在特定區(qū)域中的最小值或最大值。這些問題的答案必須確保可以通過相對直接的推理找到。
路徑規(guī)劃任務(wù)也屬于PLS分類的一個(gè)問題：假設(shè)你在旅行中只可以通過切換相鄰城市對的訪問順序來改變行程，你要如何制定一條路線，使得自己可以用最短的旅行距離訪問固定數(shù)量的城市。要計(jì)算所有設(shè)想路線的長度并不難；而且，由于你調(diào)整旅行線路的條件受到了限制，所以很容易看出哪些改變可以縮短旅行的距離。也就是說，你最終一定可以找到一條不需要再做出任何改進(jìn)的最優(yōu)路線，也就是所謂的“局部極小值”。
問題的第二個(gè)子集叫做“PPAD”（polynomial parity arguments on directed graphs，“有向圖的多項(xiàng)式校驗(yàn)參數(shù)”）。這些問題的解決方案源于更復(fù)雜的解題過程，即知名的“布勞威爾不動(dòng)點(diǎn)定理”（Brouwer’s fixed point theorem）。所謂“布勞威爾不動(dòng)點(diǎn)定理”，就是對于任何連續(xù)函數(shù)的變換，都保證有一個(gè)點(diǎn)保持不變?，F(xiàn)實(shí)中也是一樣的：如果你攪拌一杯水，那么該定理保證必然會(huì)有一個(gè)水粒子的位置是不變的。
PLS 和 PPAD 分類的交集本身就形成了一類稱為“PLS int PPAD”的問題。PLS int PPAD 包含了許多復(fù)雜性研究人員所關(guān)注的自然問題。然而，直到現(xiàn)在，研究人員也無法找到一個(gè)對 PLS int PPAD 來說是完全的自然問題——“完全”也意味著，它可能是該類中難度最高的問題。
在這篇論文發(fā)表之前，唯一已知的 PLS int PPAD 完全問題是相當(dāng)人為的構(gòu)造問題，有時(shí)候被稱為“Either-Solution”。這個(gè)問題將來自 PLS 的一個(gè)完全問題和來自 PPAD 的一個(gè)完全問題結(jié)合，形成了極少在 PLS int PPAD 之外遇到的問題。在這篇新論文中，研究人員證明了：梯度下降與 Either-Solution 問題一樣難，使梯度下降本身變成了 PLS int PPAD完全問題。
魚與熊掌不可兼得
發(fā)現(xiàn)梯度下降的這一特點(diǎn)，并不代表梯度下降的表現(xiàn)會(huì)一直不佳。事實(shí)上，它在許多用途上都與以往一樣快速、高效。
論文的二作 Paul Goldberg 談道：“關(guān)于計(jì)算復(fù)雜性，有一個(gè)略帶幽默色彩的刻板印象，就是我們經(jīng)常會(huì)拎一個(gè)很久以前在實(shí)踐中已經(jīng)被解決的問題出來，然后證明這個(gè)問題是非常困難的?！?/span>
但這個(gè)結(jié)果確實(shí)表明，應(yīng)用研究人員不應(yīng)該期望梯度下降算法能夠?yàn)槟承纫蠛芨叩膯栴}提供十分精確的解決方案。
精度問題涉及到了計(jì)算復(fù)雜性的核心，即資源需求的評估。在許多復(fù)雜問題中，精度和速度之間存在基本聯(lián)系。如果要使算法被認(rèn)為是有效的，那么你必須能夠在無需高成本的情況下提高解決方案的精度。新的結(jié)果也顯示了，對于需要非常精確的解決方案的應(yīng)用，梯度下降也許不是一種可行的方法。
例如，梯度下降通常在不要求高精度的情況下應(yīng)用于機(jī)器學(xué)習(xí)，但機(jī)器學(xué)習(xí)的研究人員又可能希望將實(shí)驗(yàn)的精度翻倍。在這種情況下，新的研究結(jié)果表明，他們可能不得不將梯度下降算法的運(yùn)行時(shí)間延長為原來的四倍。這個(gè)結(jié)果并不理想，但也不會(huì)導(dǎo)致梯度下降不能用。但對于其他應(yīng)用，比如數(shù)值分析，由于精度要求很高，這又使得計(jì)算變得十分棘手。
就像現(xiàn)實(shí)落地一樣，他們必須在一些地方上作出妥協(xié)，要么接受一個(gè)精度較低的解決方案，做一些比較簡單的問題，要么找到有效管理冗長運(yùn)行時(shí)間的方法。
但這并不是說梯度下降的快速算法不存在。相反，快速算法可能是存在的。但研究結(jié)果確實(shí)表明，如果這類快速算法存在，那么就暗示著，PLS int PPAD 的所有問題都存在快速算法——這比僅僅為梯度下降找到快速算法的難度要高得多。
Constantinos Daskalakis 總結(jié)：“許多問題可能都是基于數(shù)學(xué)進(jìn)步就能解決。這也是為什么我們希望得到一個(gè)非常自然的問題，就像梯度下降一樣，能夠捕捉整個(gè)交叉領(lǐng)域的復(fù)雜性。”
雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)
雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
