Jordan：AI 時代變革，源於應用場景中的優化算法

雷鋒網 AI 科技評論按：8 月 9 日，為期兩周的 2018 國際數學家大會（ICM）在裡約熱內盧完美謝幕，來自全球一百多個國家的 3000 多位數學家出席了本次盛會。

ICM 是國際數學聯盟主辦的、每四年一次的全球最高標準的數學科學學術會議。其中，在 ICM 2018 最後一次全體講座中，UCB 教授 Michael I. Jordan 提出了屬於 AI 時代的新問題：「How should scientists efficiently compute the world's data in a way that addresses real-world problems.」

近年來，運籌優化與決策算法作為數學在現實中的應用領域，一直受到數學界的廣泛關注。而在此次面對 ICM 全體參會數學家的講座中，Jordan 教授發表了聚焦「是否存在最佳的優化方法」問題的，主題為「Dynamical，symplectic and stochastic perspectives on Gradient-Based optimization」的講座。人工智能領域中運籌優化和算法決策的重要性，再一次成為了全場的焦點。

Michael I.Jordan 是加州大學伯克利分校 UCB 電氣工程與電腦科學系、統計系傑出教授，美國科學院、美國工程院、美國藝術與科學院三院院士，機器學習領域目前唯一獲此成就的科學家，是機器學習的奠基者、人工智能領域的泰鬥之一。

Michael I.Jordan已確認參加由雷鋒網、乂學教育·松鼠AI和IEEE LTSC主辦的『全球AI+智適應教育峰會』，免費門票、VIP門票開放申請中，訪問大會官網即刻申請：https://gair.leiphone.com/gair/aiedu2018

以下是 Michael I.Jordan 教授演講的主要內容：

今天演講的主題是動態的、保辛的隨機視角下的梯度優化方法。內容圍繞動態系統（dynamical systems）和優化之間的關係展開。這在數學中是一個古老而寬泛的領域。動態系統研究涉及數學的眾多分支，主要基於對梯度流與力學變分觀點。「數據工程」通常被稱為「機器學習」或「人工智能」，是跨越統計學、物理學、電腦科學和數學的跨領域學科。

對我們來說，將計算與實際問題相結合是一項艱巨的任務。我們的目標是在這個領域中建立一些新的聯繫，從基於梯度優化的連續時間、變分角度研究等各個方面著手。我們超越了經典的梯度流理論，專注於二階動態，旨在展示這種動力學與快速收斂 (converge) 的優化算法之間的相關性。

雖然我們關注理論研究，但實際的應用背景對我們來說也同樣重要。現代統計數據分析通常涉及非常大的數據集和參數太空，因此計算效率在實際應用中至關重要。

在這樣的前提下，效率的概念比傳統的計算複雜性理論中「算法複雜度」的概念更加嚴格。我們接下來討論多項式複雜性和指數複雜性之間的區別，這是一個非常有意義的關注點。在大規模數據分析中，一個可以實際應用的算法不僅需要多項式的複雜度階，而且需要在相關問題參數中線性或者近似線性的複雜度。優化理論為提升算法的效率提供了實踐和理論的支持。它提供了計算效率高的算法，並提供了允許將收斂速度確定為問題參數的顯式函數的分析工具。鑒於基於 Hessian 的優化方法在參數太空的維度上會產生二次或三次的複雜度，在討論非一階方法的時候，效率可能是一個有意義的討論點。

更廣泛地說，統計推斷（statistical inference）和計算思想的融合，是當前世紀的主要趨勢之一——目前以諸如「數據科學」和「機器學習」這樣的術語來出現。這是一種尋求將計算和統計推斷需求共同研究的新的數學概念的趨勢。例如，人們希望將數據分析算法的運行時間的計算化成關於統計風險、數據樣本數量、模型複雜度等統計量的函數，同時考慮計算資源限制，如處理器數量、通信帶寬和異步程度。對這種權衡的基本理解似乎可以通過更低的下界的發展而出現——通過建立「最優」概念，可以消除冗余的概念並揭示必然的聯繫。在這裡，優化理論也很重要。

經典統計理論沒有考慮時間維度，它的方程在數據複雜性、風險和變量維度之間進行權衡，但在這些方程中並不包含運行時間。而在電腦科學的另一方面，你會發現算法設計需要在運行時間、運行資源等複雜性度量之間進行權衡，但統計風險不在其中。所以要如何將這兩種方式放在一起是我們這個時代的一大挑戰。優化起到了將這兩個領域結合在一起的作用，它提供了算法和對問題更深層次的理解，特別是當我們開始考慮通過優化去達到更優的下界。

在 20 世紀 70 年代開始的一項開創性研究中，Nemirovski、Nesterov 和其他人開發了一種優化的複雜性理論，建立了收斂速度的下界，並發現實現這些下界限的算法。此外，複雜性模型是相對的——指定了「oracle」，那麽算法只能使用 oracle 可用的資訊。例如，隻訪問函數值和梯度的 oracle。因此，實際計算效率的相關指導方法可以在理論中以自然的方式施加。

計算和統計數據通過優化結合在一起。而哪些領域會先開始組合在一起？我們如何開始建立理論和實踐？在現實生活、公司和科學中，以下對於成功案例至關重要。一個是基於梯度的優化，我學到的算法版本，是在關注 Hessian 矩陣和牛頓迭代法以及更高階的版本。在二三十年間，它們發揮了很多作用，特別是在大規模計算問題上得到了成功應用，但計算 Hessian 很難，也很難去估算它們。現在我們經常會有隨機差異，在這些問題上我們沒有辦法準確地觀察事物。這些問題只是存在於統計領域，我們可能存在各種錯誤比如采樣偏差等。我們必須面對它並且利用它。最終，加速概念在前蘇聯優化界出現了，它是研究優化算法，尤其是如何獲得最快的優化算法的概念。這類被稱為「加速算法」的優化算法（Nesterov, 1998），通常可以達到 oracle 的最下限速率，儘管 Nesterov 加速方法為什麽能夠達到 oracle 的理論原因還是個謎。

我們認為，一些謎團是出自於離散時間算法和分析的優化的歷史焦點。在優化中，「連續優化」和「離散優化」之間的區別，在於如何匹配（「太空」）變量。相比之下，我們的討論將集中在連續時間上。在連續時間中，我們可以將加速度作為一種差異概念給予數學意義，將它作為沿曲線的速度變化。我們可以提出「最快速率是多少」的問題，來作為變分分析的一個問題。本質上，這是為給定的 oracle 本身找到「優化的最佳方法」作為優化的形式問題。這種變分的觀點也具有生成性的優點——我們可以推導出實現想要的 fast rates 的算法，而不是去為某一個特殊方式得出的特定算法去分析並建立一個符合算法要求的 fast rate。

為了使連續時間上的結果能夠推廣、得出數字電腦可以實現的算法，我們將連續時間動態系統的問題離散化。有趣的是，我們會發現，廣泛應用於從變分或哈密頓角度獲得的動態的辛迭代積分器，與優化有關。從辛積分獲得的算法可以更快地通過相太空移動，這為「加速」賦予了幾何意義。

考慮在某種意義上的「加速」的連續時間下的隨機動態系統也是有意義的。最簡單形式的基於梯度的積分微分方程是 Langevin 擴散。我們看到，通過考慮欠阻尼 Langevin 擴散，我們將獲得更類似於加速梯度下降的方法，並且實際上可證明產生比過阻尼擴散更快的速率。

Nesterov 在 1980 年代提出了一種建立收斂速度下界的梯度下降方法。在 1983 年 Nesterov 發表了開創性論文後，隨後的三十年中，各種其他問題背景下的各種加速算法得到了發展。這些包括鏡像下降、複合目標函數、非歐幾裡德幾何、隨機梯度下降和高階梯度下降。我們已經證明了以上這些算法的收斂速度：他們的收斂速率通常達到 oracle 下限。總體來說，加速一直是現代優化理論中最富有成效的思想之一。

拉格朗日公式可以在連續時間內捕獲加速度，顯示該公式如何產生一系列微分方程，其收斂速度是離散的連續時間對應物。我們強調這些微分方程的數值積分問題，建立了我們在下面討論的辛積分方法。

辛積分是微分方程離散化的一般方法，它保留了動力系統的各種連續對稱性。從力學獲得的微分方程的情況下，這些對稱性包括物理上有意義的積分，例如能量和動量。即使動態量只是近似值，辛積分器也能精確保存這些量，除了從物理守恆的觀點來看這一結果的吸引力之外，連續對稱性的保留意味著辛積分器比其他積分格式更穩定。因此可以在離散時間系統中使用更大的步長。正是後一個事實表明辛積分器在加速優化方法相關的微分方程中起作用。辛積分器可以從拉格朗日框架導出，但更自然地，可以從哈密頓框架導出。但事實上，辛方法在拓撲上比 Nesterov 加速法的一個三序列變種更穩定，如果選擇更大的步長，這一事實就會更加明顯。辛集成與優化中的加速現象之間存在著聯繫，當後者被解釋為連續時間現象時，辛積分提供了獲得離散時間近似的有效且靈活的方式。

最需要注意的是非凸優化中的加速度與鞍點的逃逸問題。現實中存在的問題大都具有非凸特性。事實證明，對於統計學習中的廣泛問題，非凸情形下存在足夠的數學結構，即可以獲得有用的數學結果。實際上，在許多情況下，來自凸優化的想法和算法適當地修改可以被應用於非凸環境。特別對於基於梯度的優化，在凸問題中執行良好的相同算法也傾向於在非凸問題中產生良好的性能。從這個意義上說，凸優化除了擁有自己的許多自然應用之外，還可以作為非凸優化的實驗室。在鞍點附近存在 pancake 區域，在這個區域內進行梯度下降將「卡住」需要指數量級的時間逃逸。這個區域並不平坦，而是隨著 Hessian 的變化而變化。Lipschitz 假設使我們能夠控制這種變化。

到目前為止關注的是動態系統。系統是確定的。隨機性以有限的方式被引入，作為一種擾動，確保從鞍點快速逃離。我們特別分析了球中的非均勻擾動，足以快速逃離，但是這不是必要的。鑒於這種簡單選擇的成功，我們用動力研究中更徹底的隨機方法來解決我們的問題。

基於梯度的優化的一般主題及其在大規模統計推斷問題中的應用，目前非常活躍。我們要強調一下在未來幾年可能引起持續關注的一些課題。一個令人值得注意的問題是，在統計設定中經常使用優化方法來解決點估計問題，其中核心問題是在參數太空中輸出具有所需統計特性的單個點。

而更廣泛的問題是，使用概率分布的一些精煉的形式來提供與該相關的不確定性的指標。通過考慮作為概率分布太空的太空，優化思想也可以在這裡體現：我們可以要求不收斂到單個點，而是收斂到點的分布上。哈密頓方法自然而然地產生震蕩解，並且正如我們所看到的，需要一些工作來獲得收斂到某一個點的算法。這表明哈密頓方法實際上在分布收斂的設定中比在點估計設定中更容易使用，從而提供了點估計和更廣泛的推斷問題之間的算法橋梁。事實上，在貝葉斯推斷中，哈密頓公式（以及不同積分器形式的辛積分）已經成功地應用於 MCMC 算法（馬爾科夫鏈蒙特卡洛算法）的設定中，其中哈密頓函數的動量分量提供了更快的混合。加速算法和高效的推斷算法之間更深層次的聯繫值得研究。

數學正在成為數據領域的一個強大工具，已經證明了許多定理。對力學的梯度流和變分透視的研究可以應用於該區域。最後，我需要重申一下數學工具在解決基於數據的實際問題中的重要性。儘管有一些現實世界的為數據分析的數學應用問題，我們承認這個領域還不是很成熟，但未來非常值得期待。

雷鋒網雷鋒網