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）卻能達到很好的效果。這篇論文能為深度學習優化帶來新的思路嗎？或許混合方法會是不錯的選擇，但在實驗研究中是不是早就有這樣的嘗試了呢？