頂會最佳論文覆滅科學家們30多年期待：復雜度遠超預期

雷西 發(fā)自 凹非寺

量子位 | 公眾號 QbitAI

三十多年來，在線算法一直被科學家寄予厚望，但一篇論文的誕生讓它走下了神壇。

它的目標，簡單來說就是在沒有完整數(shù)據(jù)的情況下，通過有限的信息提前找到最佳策略。

在我們的生活中，例如股票市場的即時交易分析，還有導航路徑的實時規(guī)劃，都有在線算法的身影。

不過沒有完整數(shù)據(jù)，就意味著性能將受到限制；因此科學家們一直期待它能突破數(shù)據(jù)的桎梏，達到更高的效率。

然而就在最近，來自微軟研究院、牛津大學等機構(gòu)的研究人員在進行了一場實驗之后發(fā)現(xiàn)，這種算法的復雜度遠遠超過了人們的期待。

他們也憑借著這篇論文，在今年的計算理論頂會STOC上獲得了最佳論文獎。

那么，他們獲獎的這項研究，具體說了些什么呢？

科學家們的“30年期待”

這里我們需要先來了解一些背景知識。

和在線算法相對的，還有離線算法，它在開始處理之前需要先接收到所有的輸入數(shù)據(jù)。

由于預先掌握了完整數(shù)據(jù)，在同等的數(shù)據(jù)規(guī)模下離線算法顯著快過在線算法

想象一下，現(xiàn)在要從一系列數(shù)字中找出最大值，第一種情況是直接知道所有數(shù)字，另一種是比較完前面的數(shù)才知道后面的數(shù)字是多少，顯然第一種情況的速度更快。

于是離線算法的性能被看作是一個標桿，并衍生出了“競爭比”的概念。

而在過去的30多年里，在線算法曾一度被寄予競爭比接近1的厚望。

具體的體現(xiàn)是，關(guān)于在線算法，學界有一個經(jīng)典問題，叫做k-server問題。

k-server問題可以這樣來描述：

給定一個度量空間和位于該空間指定位置的k個服務器，在該空間的不同位置中會出現(xiàn)一系列請求。

對于每個請求，都必須選擇一個服務器來響應該請求。

如果服務器已經(jīng)在請求的位置，它可以立即響應；否則，它必須移動到請求的位置。

而k-server問題的最終目標，是將所有服務器移動距離的總和最小化。

舉個例子，在一公路旁有若干家餐館，路上有k個空閑的外賣員，這些餐館可能隨時需要外賣員上門取餐，此時外賣員的調(diào)度就可以看做是一個k-server問題。

而在這個過程當中，無論是系統(tǒng)還是外賣員在真的接到訂單之前都不知道訂單出現(xiàn)的時間和位置，此時的問題是如何將所有外賣員取餐所走的路程之和最小化。

直到這篇論文發(fā)表為止，長達30多年的時間里，在線算法一直被期待在解決所有k-server問題時，復雜度都不超過Θ(log k)。

（其中Θ表示漸進緊確界，可簡單理解為數(shù)量級相同）

但這篇論文的出現(xiàn)，讓這個期待被打破。

那么，作者又是如何把這個期待證偽的呢？

復雜度遠超預期

注：本節(jié)中的對數(shù)符號log，如無特別說明，底數(shù)為2

遞歸構(gòu)建圖度量空間

為了探究k-server問題的復雜度，作者構(gòu)建了一個遞歸定義的圖度量空間（本質(zhì)上也是k-server問題）。

作者首先構(gòu)造一個簡單的度量空間M(0)，然后把多個M(0)按照循環(huán)的方式連成一個環(huán)M(1)，然后把多個M(1)連接成M(2)……以此類推，最終形成了一個可以分割成對稱的子結(jié)構(gòu)的空間。

在這個度量空間上作者設(shè)計了一個隨機請求序列ρ，它會在對稱子結(jié)構(gòu)之間交替選擇請求點，迫使在線算法在子結(jié)構(gòu)間頻繁移動，而最優(yōu)算法是固定在一個子結(jié)構(gòu)。

之后，作者證明了在這個特殊構(gòu)造的度量空間和請求序列上,任何確定性在線算法的預期消耗最低也要達到Ω(log2)。

而具體的證明，則采用了數(shù)學歸納法。

數(shù)學歸納法

數(shù)學歸納法雖然名字里有個歸納，實質(zhì)上卻是一種嚴謹?shù)难堇[推理。

它首先驗證結(jié)論針對序列中的第一項是否成立，然后假設(shè)對第k項也成立，接著，只要能證明對第k+1項也成立，結(jié)論就可以得到證明。

這個過程就像多米諾骨牌，只要推倒（k+1）一塊，其他的牌自然也會隨之倒下，這時同時確保第一塊有同樣的效果，整個體系就完備了。

舉個例子，我們知道數(shù)列{a(n)=n}的前n項和S(n)=n(n+1)/2，用數(shù)學歸納法證明過程如下：

首先n=1時，a(n)=1，S(n)=1(1+1)/2=1，結(jié)論成立

然后假設(shè)n=k時結(jié)論也成立，此時S(k)=k(k+1)/2

那么，當n=k+1時，S(k+1)=S(k)+(k+1)
即S(k+1)=k(k+1)/2+2(k+1)/2
提取公因子(k+1)，這個式子又可以寫成(k+2)(K+1)/2
此時n=k+1，n+1=k+2，結(jié)論依然成立
所以S(n)=n(n+1)/2得證

任意度量空間消耗下限

而具體到這項研究，作者利用隨機性和對稱性定義了一個新的序列ρ(w)，并假設(shè)在度量空間M(w)中，對隨機的ρ(w)，確定性算法的消耗下限為Ω(w2)。

首先對于M(0)，確定性算法的消耗下限為1，此時結(jié)論成立。

然后試著將w推廣到w+1，構(gòu)建出M(w+1)的度量空間，它包含兩條由多個M(w)組成的對稱路徑。

在請求ρ(w+1)上，假設(shè)此時位于左路徑，下一段位于左右路徑的概率各為1/2。

如果下階段位于右路徑，算法復雜度將會因為路徑切換而升高，不是低消耗。

而如果位于左路徑，由于路徑上都是一個個M(w)，所以新增部分的消耗下限就是Ω(w2)（此為歸納法假設(shè)）。

于是對于w+1段路徑，可以將每一段的消耗Ω(w2)累加，即為(w+1)Ω(w2)，結(jié)合Ω的定義，最終可以證明M(w+1)的最低消耗為Ω((w+1)2)，進而證明假設(shè)成立。

回到最初的度量空間

而作者構(gòu)建的M(w+1)都是由6個M(w)組成，則M(w)的大小n=|M(w)|=O(6^w)，取對數(shù)得log|M(w)|=w·log6。

代入Ω(w2)中，得到在n點度量空間中，消耗下限為Ω((logn/log6)2)，而當n=k時，消耗下限則為Ω((logk/log6)2)。

而log6為一個2到3之間的常數(shù)，除以這樣一個數(shù)不會帶來結(jié)果的顯著改變，也就證明了k-server問題中消耗不低于Ω(log2k)的結(jié)論。

當k足夠大時，log2k顯然大于logk，因此在這樣的k-server問題中，實現(xiàn)O(logk)級別的低消耗是不可能的。

而此前人們一直認為可以用這樣的消耗解決所有的k-server問題，因此反例的出現(xiàn)便宣告了這一設(shè)想的終結(jié)。

論文地址：
https://dl.acm.org/doi/pdf/10.1145/3564246.3585132
參考鏈接：
https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/