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