Michael Jordan新研究：採樣可以比優化更快地收斂

選自 arXiv，作者：Yi-An Ma 等，機器之心編譯。

對於凸函數而言，局部最優點即全局最優點，這是很多優化方法奏效的重要前提。對於非凸函數，可以使用採樣方法（如 MCMC），但普遍比優化方法的收斂要慢得多。而在 Michael Jordan 等人的這篇論文中，他們給出了一個新的觀點：有時候，採樣方法比優化方法收斂更快，還是指數量級的。

打開今日頭條，查看更多精彩圖片

凸函數（左）和非凸函數（右）

機器學習和數據科學融合了計算機科學與統計學，以解決推理問題。它們的規模和複雜性都要求現代計算基礎設施的支持。它們的演算法基礎基於兩種通用的計算策略，這兩種策略都源於數學——優化和馬爾科夫鏈蒙特卡洛方法（MCMC）採樣。針對這些策略的研究大多是單獨進行的：優化研究側重於評估和預測問題，而採樣研究側重於需要評估不確定性的任務，如形成置信區間和進行假設測試。然而，在兩個研究領域中使用共同的方法要素開始成為一種趨勢。特別是這兩個領域都側重於使用梯度和隨機梯度——而不是函數值或高階導數——來作為單個演算法步驟的計算複雜性和總體收斂速率之間的有益折衷。實驗證明，這種妥協的效果相當驚人。但是，將優化和採樣聯繫起來的理論研究相對較少，因此限制了這種思路的發展。尤其是，優化理論最近的快速發展 [34] 並沒有帶來採樣理論的此類發展。因此，機器學習的推理範圍仍然有限，很少能夠考慮不確定性的估計。

在最近的研究 [13, 15, 14, 11, 9, 17, 30, 31] 中，理論聯繫開始出現。其中優化理論中的工具已經被用於證明 MCMC 採樣中的收斂速率——通常還包括維度相關性。這些結果顯示的總體信息是採樣比優化要慢，這一結果符合普遍觀點，即採樣方法只有在需要其提供更強的輸出推理時才合理。但是，這些結果是在凸函數的設定中取得的。對於凸函數，可以通過局部信息來評估全局屬性。而基於梯度的優化非常適合這種設置。

在本文中，Michael Jordan 等研究者關注的是非凸設定。他們考慮了有界區域之外為凸而區域內為非凸的一類問題。這種問題出現在具有適當先驗的貝葉斯混合模型問題 [33, 32]，以及統計物理學中常見的帶雜訊多穩態模型中 [24, 25]。研究者發現，如果這一非凸區域在 R^d 中具有一個恆定的非零半徑，那麼 MCMC 方法就會在 O(d/ε) 或 O(d^2ln(1/ε)) 步數內收斂到 ε 準確率，而任何優化方法都需要 O((1/ε)^d) 步以上才能收斂。因此，對於這類問題，採樣比優化更高效。

論文：Sampling Can Be Faster Than Optimization

論文鏈接：https://arxiv.org/pdf/1811.08413.pdf

摘要：近年來，優化演算法和蒙特卡洛採樣演算法為統計機器學習應用的快速發展提供了計算基礎。然而，關於這兩種方法論之間關係的理論理解非常有限，對其相對優勢和劣勢的理解也比較缺乏。此外，現有的結果主要是在凸函數（用於優化）及對數凹函數（用於採樣）中獲得的。在這種設定下，局部屬性決定全局屬性，優化演算法在計算層面無疑比採樣演算法更高效。我們測試了一類來自混合建模及多穩態系統的非凸目標函數。在這種非凸設定下，我們發現採樣演算法的計算複雜度隨模型維度線性擴展，而優化演算法的計算複雜度則呈指數擴展。

仔細考慮非凸半徑 R 和維度 d 之間的相對尺度是很有趣的（對於常數 Lipschitz 平滑度 L）；當 R 是常量或者小於 O(log d) 時，採樣通常比優化更容易；當 R≤√ d 時，採樣的收斂上界仍然比優化複雜度下界稍低；當 R>√ d 時，其對比是不確定的；並且當 R>d 時，相反的結論成立。

近年來基於梯度優化的理論快速發展，部分是因為下界理論的研究，類似定理 4 的形式，其對很多種演算法都有效。在 MCMC 演算法上發展這樣的下界理論是很有趣的，尤其是能捕捉維度依賴關係的理論。此外，開發其它類型的非凸性的下界和上界理論也是很有趣的。

深度神經網路的目標函數是高度非凸的，但使用優化方法（SGD）卻能達到很好的效果。這篇論文能為深度學習優化帶來新的思路嗎？或許混合方法會是不錯的選擇，但在實驗研究中是不是早就有這樣的嘗試了呢？

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！