靠「猜」答案獲得頂會最佳論文，華人IOI金牌獲得者找到復(fù)雜「雞兔同籠」最簡解法
打破線性方程求解速度極限
魚羊 蕭簫 發(fā)自 凹非寺
量子位 報道 | 公眾號 QbitAI
還記得小時候被“雞兔同籠”支配的恐懼嗎？
其實，當(dāng)我們學(xué)習(xí)了二元一次方程，就知道這個問題并不復(fù)雜：
不過，可別小看了這樣的線性方程，試想一下，如果動物的種類不止2種，特征也不只頭和腳呢？
比如……
這個時候，我們就只能求助矩陣乘法了。
那么，問題來了，采用高斯消元法，求解的復(fù)雜度就是O(n3)。
也就是說，如果n從2增加到4，求解復(fù)雜度就會增加23即8倍。
n越來越大，計算的步驟就會以3次方的速度快速增加……
想想機器學(xué)習(xí)、工程項目里極其復(fù)雜的矩陣乘法，是不是有點頭皮發(fā)麻的感覺。
好消息是，現(xiàn)在，這個困擾工程師們已久的基礎(chǔ)問題，有了突破性進展。
計算機理論頂會SODA 2021的最佳論文，用“猜”答案的方式，一口氣把算法復(fù)雜度減小到了O(n2.3316)！
論文作者，是來自佐治亞理工學(xué)院的兩位數(shù)學(xué)家：彭泱和Santosh Vempala。
這項研究具體是怎么一回事？快來一起研究研究。
IOI金牌獲得者，靠“猜”推動研究
IOI金牌獲得者、來自佐治亞理工學(xué)院的助理教授彭泱，和他的合作者Santosh Vempala共同提出了一種全新的思路。
相比于此前，數(shù)學(xué)家們不停地改進矩陣乘法的算法，他們別出心裁，想到能否靠“猜”，來重新設(shè)計一種算法。
這種方法就是：猜測每個未知數(shù)的值，把它們代入方程后，查看結(jié)果與實際值相差有多大。
然后，修正未知數(shù)的值，再猜一次。
這種方法，在計算機方向上被稱為迭代法。
彭泱的這種迭代算法，在方程的數(shù)量變得極多、且每個方程涉及的未知數(shù)較少時，顯示出了巨大的優(yōu)勢。
也就是說，如果在一個系數(shù)矩陣屬于“稀疏矩陣”——矩陣本身特別大，但相對地，系數(shù)為0的數(shù)量又非常多的時候，迭代法就會出現(xiàn)神奇的結(jié)果。
此前，沒有人能夠證明，“迭代法”對于稀疏矩陣而言，是否會比“矩陣乘法”更快。
當(dāng)然，這種算法并不只靠“猜”。
彭泱設(shè)計的算法中，他們還會在給出多組隨機數(shù)的同時，將這些隨機數(shù)組并行計算。
這就像是數(shù)百個人同時在山林中搜索寶藏，肯定比一個人反復(fù)搜索要更快。
但這種算法的設(shè)計，還面臨兩個難點：
如何保證設(shè)計出來的數(shù)，足夠隨機、不偏向問題的任何一部分？
如何保證設(shè)計出來的這些隨機數(shù)組，全面覆蓋每一種可能性？
他們發(fā)現(xiàn)，正因為由隨機數(shù)構(gòu)造出的矩陣中，項數(shù)是隨機的、且彼此之間有著某種關(guān)聯(lián)，因此，這一矩陣本身就具有某種對稱性。
這就意味著，如果知道矩陣中某些具體的數(shù)值，就能推斷出一整個矩陣的形狀。
這一發(fā)現(xiàn)，使得他們設(shè)計的算法，比未考慮矩陣對稱性的那些算法，找到解的速度更快。
事實證明，這種算法確實能夠保證在O(n2.3316)復(fù)雜度以內(nèi)，完成任何計算。
這比之前的O(n2.37286)，復(fù)雜度降低了不少，可以說是一個巨大的進步。
這一新發(fā)現(xiàn)，讓彭泱和他的合作者獲得了ACM-SIAM離散算法研討會SODA 2021的最佳論文獎。
為什么要降低計算復(fù)雜度？
解一個二元一次方程，也就是2×2的矩陣，靠中學(xué)知識就能輕松搞定。
然而當(dāng)n變得越來越大，求解方程的計算量就會以3次方的速度迅速增加。
這是什么概念？
意味著如果線性問題中，要求解的未知數(shù)達到100甚至10000，那么計算量復(fù)雜度就會增加1000000、甚至1012倍。
目前，機器學(xué)習(xí)、動力學(xué)模擬等問題，都會遇到超大規(guī)模線性方程組，如何降低計算復(fù)雜度，一直是學(xué)者們致力于解決的問題。
要是計算復(fù)雜度居高不下，對于計算機而言，將會是一個巨大而沉重的負(fù)擔(dān)。
因此，數(shù)學(xué)家們一直在想方設(shè)法將線性問題的復(fù)雜度弄得更小一點，也就是讓O(nω)中的ω變小。
哪怕ω減小的量只有0.00001，對于上百萬未知數(shù)的方程組來說也是一個巨大的進步。
通過不斷改善矩陣乘法，ω先是從3降低到2.81，歷經(jīng)多次研究后，被MIT和哈佛的數(shù)學(xué)家們降低到2.37286。
然而，到這個階段，數(shù)學(xué)家們傾盡全力所設(shè)計的新算法，也只是將ω降低了0.00001而已。
有數(shù)學(xué)家進行過預(yù)測，ω可以無限接近于2，也就意味著這種線性問題的計算復(fù)雜度還能盡力向O(n2)靠攏。
因此，彭泱他們的新算法，可以說是將這一研究向前推動了一大步。
關(guān)于作者
論文作者彭泱，江蘇南京人，現(xiàn)為佐治亞理工學(xué)院計算機科學(xué)系助理教授。
他本科畢業(yè)于滑鐵盧大學(xué)數(shù)學(xué)專業(yè)，其后在CMU拿下計算機科學(xué)博士學(xué)位。2013-2015年在MIT擔(dān)任應(yīng)用數(shù)學(xué)博士后。
目前，他主要關(guān)注的研究方向是高效算法的設(shè)計、分析和實現(xiàn)。
根據(jù)Google Scholar，彭泱的論文引用數(shù)為2788，h指數(shù)為28。
他的名字，也頻頻見于FOCS、STOC、SODA等計算機理論頂會論文當(dāng)中。
彭泱與數(shù)學(xué)和計算機結(jié)緣很早，據(jù)中國僑網(wǎng)報道，他8年級時就曾參加10年級水平的美國數(shù)學(xué)比賽，并獲得滿分的成績。還在2004年和2005年參加加拿大計算機競賽，摘下金牌。
2005年和2006年，彭泱代表加拿大隊參加國際奧林匹克數(shù)學(xué)競賽（IMO），分別獲得銀牌和銅牌。
而在此期間，他還參與了2004、2005和2006年的國際奧林匹克信息學(xué)競賽（IOI），并在2005年獲得金牌。
論文的另一位作者Santosh Vempala是著名計算機科學(xué)家，佐治亞理工學(xué)院計算機科學(xué)杰出教授。2015年，他入選“因?qū)ν辜透怕史植妓惴ǖ呢暙I”入選ACM Fellow。
他的主要研究方向是算法理論，用于抽樣、學(xué)習(xí)、優(yōu)化和數(shù)據(jù)分析的算法工具，高維幾何，隨機線性代數(shù)等。
Santosh Vempala還是古根海姆獎、斯隆獎獲得者。
論文地址：
https://arxiv.org/abs/2007.10254
參考鏈接：
[1]https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/
[2]https://www.cc.gatech.edu/~rpeng/
[3]http://www.arc.gatech.edu/
[4]https://www.chinaqw.com/node2/node2796/node2882/node3156/userobject6ai253919.html
[5]https://www.siam.org/conferences/cm/conference/soda21
相關(guān)閱讀
