?作者?|?機(jī)器之心編輯部

來(lái)源?|?機(jī)器之心

梯度下降算法具有廣泛的用途，但是關(guān)于它的計(jì)算復(fù)雜度的理論研究卻非常少。最近，來(lái)自利物浦大學(xué)、牛津大學(xué)的研究者從數(shù)學(xué)的角度證明了梯度下降的計(jì)算復(fù)雜度，這項(xiàng)研究也入選 STOC 2021 的最佳論文獎(jiǎng) 。

當(dāng)前應(yīng)用研究的很多方面都依賴于一種名為梯度下降的算法。這是一個(gè)求解某個(gè)數(shù)學(xué)函數(shù)最大 / 最小值的過(guò)程（函數(shù)優(yōu)化），從計(jì)算產(chǎn)品的最佳生產(chǎn)方式，到工人輪班的最佳安排方法，這一算法都能派上用場(chǎng)。

盡管梯度下降算法具有廣泛的用途，但是關(guān)于它計(jì)算復(fù)雜度的理論研究卻非常少?，F(xiàn)在，來(lái)自利物浦大學(xué)、牛津大學(xué)等機(jī)構(gòu)的研究者在論文《 The Complexity of Gradient Descent: CLS = PPAD ∩ PLS 》中給出了答案，梯度下降從本質(zhì)上解決了一個(gè)非常困難的計(jì)算問(wèn)題。這篇文章也入選了 STOC 2021 的最佳論文。

論文地址：

https://arxiv.org/pdf/2011.01929.pdf

本文作者由牛津大學(xué)的 Paul Goldberg 、Alexandros Hollender 與利物浦大學(xué)的 John Fearnley 、 Rahul Savani 共同撰寫。

梯度下降計(jì)算復(fù)雜性

梯度下降是現(xiàn)代應(yīng)用研究的重要工具，但它在許多常見問(wèn)題上效果不佳。在這項(xiàng)研究之前，并沒(méi)有學(xué)者進(jìn)行全面研究究竟是什么讓梯度下降陷入困境，現(xiàn)在計(jì)算復(fù)雜性理論有助于回答這個(gè)問(wèn)題。

「梯度下降的很多工作都沒(méi)有涉及復(fù)雜性理論，」麻省理工學(xué)院的副教授 Costis Daskalakis 說(shuō)。

計(jì)算復(fù)雜性是對(duì)解決或驗(yàn)證不同計(jì)算問(wèn)題的解決方案所需資源（通常是計(jì)算時(shí)間）的研究。研究人員將問(wèn)題分為不同的類別，同一類別中的所有問(wèn)題共享一些基本的計(jì)算特征。

舉例來(lái)說(shuō)，想象一個(gè)城鎮(zhèn)，人多于房子，每個(gè)人都住在房子里。給你一本電話簿，上面寫著鎮(zhèn)上每個(gè)人的姓名和地址，你需要找到住在同一所房子里的兩個(gè)人。你可以完成這個(gè)任務(wù)，不過(guò)因?yàn)槿硕嘤诜孔?#xff0c;這可能需要一些時(shí)間進(jìn)行查找（特別是如果他們不共享姓氏）。

上述問(wèn)題屬于 TFNP（total function nondeterministic polynomial） 復(fù)雜類問(wèn)題。它是所有計(jì)算問(wèn)題的集合，能夠保證存在解決方案，并且可以快速檢查解決方案的正確性。?

研究人員專注于 TFNP 中兩個(gè)子集問(wèn)題的交集：

第一個(gè)子集稱為 PLS（polynomial local search）。這是一系列問(wèn)題的集合，涉及在特定區(qū)域中尋找函數(shù)的最小值或最大值， 這些問(wèn)題的答案必須確保可以通過(guò)相對(duì)直接的推理找到。

PLS 類別中的一個(gè)典型問(wèn)題是路徑規(guī)劃：假如要求你以盡可能短的旅行距離訪問(wèn)固定數(shù)量的城市，且只能通過(guò)切換相鄰城市對(duì)的順序來(lái)改變行程。要計(jì)算所有設(shè)想路線的長(zhǎng)度并不難，并且由于可以調(diào)整行程的方式受到限制，因此很容易看出哪些更改會(huì)縮短行程。

也就是說(shuō)，最終你會(huì)找到一條路線，這條路線不能再進(jìn)一步縮短路程了，那么這條路線就是你要找到的最小值，就是所謂的局部極小值。

TFNP 問(wèn)題的第二個(gè)子集是 PPAD。這些問(wèn)題的解來(lái)自更復(fù)雜的過(guò)程，稱為布勞威爾不動(dòng)點(diǎn)定理，即對(duì)于任何連續(xù)函數(shù)，存在一個(gè)點(diǎn)保持不變。在日常生活中也是如此，比如你攪拌一杯水，該定理保證一定有一個(gè)水分子最終會(huì)回到它開始的地方。

PLS 和 PPAD 類的交集本身形成了一類稱為「 PLS ∩ PPAD」 的問(wèn)題。這類問(wèn)題包含許多復(fù)雜性研究人員所關(guān)注的自然問(wèn)題。然而，直到現(xiàn)在，研究人員都無(wú)法找到一個(gè)對(duì) 「 PLS ∩ PPAD」來(lái)說(shuō)是完全的自然問(wèn)題，所謂「完全」意味著它可能是這類問(wèn)題中最難的問(wèn)題。

而 PLS 與 PPAD 的交集，被他們證明等價(jià)于 CLS （連續(xù)局域搜索問(wèn)題）。

在這篇論文之前，唯一已知的「 PLS ∩ PPAD 」完全問(wèn)題可以說(shuō)是一個(gè)人工構(gòu)造的問(wèn)題，這個(gè)問(wèn)題有時(shí)被稱為「Either-Solution」。它將來(lái)自 PLS 的一個(gè)完全問(wèn)題和來(lái)自 PPAD 的一個(gè)完全問(wèn)題聯(lián)合，形成了研究人員極少在「 PLS ∩ PPAD 」之外遇到的問(wèn)題。在這篇論文中，研究人員證明了梯度下降與「Either-Solution」一樣難，梯度下降本身就是「 PLS ∩ PPAD 」完全問(wèn)題。

速度與精度不能平衡

哥倫比亞大學(xué)數(shù)據(jù)科學(xué)中心教授 Tim Roughgarden 說(shuō)道：「我們?nèi)祟惐緛?lái)就應(yīng)該努力去深入了解計(jì)算本質(zhì)的各個(gè)方面。所以我對(duì)這項(xiàng)研究結(jié)果的發(fā)現(xiàn)感到十分興奮?！?/p>

這一發(fā)現(xiàn)并不意味著梯度下降會(huì)一直表現(xiàn)不佳。事實(shí)上，對(duì)于大多數(shù)任務(wù)來(lái)說(shuō)，梯度下降與以往一樣快速和高效。

「關(guān)于計(jì)算復(fù)雜性有一種略帶幽默的刻板印象，即我們經(jīng)常會(huì)拿以前在實(shí)踐中已經(jīng)被解決的問(wèn)題出來(lái)，然后在證明它是非常難的，」論文二作 Goldberg 說(shuō)。

但這一結(jié)果確實(shí)意味著，應(yīng)用研究人員不應(yīng)該期望梯度下降法為一些精度很重要的問(wèn)題提供精確的解決方案。

精度問(wèn)題涉及計(jì)算復(fù)雜性的核心——資源需求的評(píng)估。在許多復(fù)雜問(wèn)題中，精度和速度之間存在基本聯(lián)系。要使算法被認(rèn)為是有效的，你必須有能夠提高解決方案的精度，而無(wú)需為找到該解決方案所花費(fèi)的時(shí)間付出相應(yīng)的高昂代價(jià)。新的結(jié)果也顯示了，對(duì)于那些需要非常精確的解決方案的應(yīng)用，梯度下降也許不是一種可行的方法。

例如，梯度下降在機(jī)器學(xué)習(xí)中經(jīng)常以不需要極端精確的方式使用。但機(jī)器學(xué)習(xí)研究人員想要將實(shí)驗(yàn)的精度提高一倍。在這種情況下，新的結(jié)果意味著他們可能需要將梯度下降算法的運(yùn)行時(shí)間增加四倍。這種做法并不理想，但梯度下降還能起作用。

但對(duì)于其他應(yīng)用，比如在數(shù)值分析中，研究人員可能需要將精度進(jìn)行成倍提升，為了實(shí)現(xiàn)這樣的改進(jìn)，他們可能必須將梯度下降的運(yùn)行時(shí)間進(jìn)行更多倍的提升，這樣一來(lái)，計(jì)算更加難以處理。

如果想要使用梯度下降，研究者必須做出妥協(xié)，要么接受精度較低的解，做一些比較簡(jiǎn)單的問(wèn)題，要么找到管理冗長(zhǎng)運(yùn)行時(shí)間的方法。

但這并意味著快速梯度下降算法不存在，相反，快速算法有可能存在。但這一結(jié)果暗示著「 PLS ∩ PPAD 」 的所有問(wèn)題都存在快速算法，這比僅僅為梯度下降找到快速算法的難度要高得多。

「數(shù)學(xué)上的進(jìn)步可以解決許多現(xiàn)有問(wèn)題，這也是為什么我們希望得到一個(gè)非常自然的問(wèn)題，比如梯度下降，能夠捕捉整個(gè)交叉領(lǐng)域的復(fù)雜性。」Daskalakis 說(shuō)道。

參考鏈接：

https://www.quantamagazine.org/computer-scientists-discover-limits-of-major-research-algorithm-20210817/

https://www.youtube.com/watch?v=as720_SRpY0

????

現(xiàn)在，在「知乎」也能找到我們了

進(jìn)入知乎首頁(yè)搜索「PaperWeekly」

點(diǎn)擊「關(guān)注」訂閱我們的專欄吧

·

總結(jié)

以上是生活随笔為你收集整理的不能兼顾速度与精度，STOC 2021最佳论文揭示梯度下降复杂度理论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。