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