點選上方“道器”，輕松關注我們
現代大規模資料分析和機器學習應用程式嚴重依賴于計算效率高的算法。其中有2種主要算法：基于優化的算法和基于蒙特卡洛采樣的算法。一般的看法是，采樣必然比優化慢，并且僅在需要不确定性估計的情況下才需要采樣。根據發表在PNAS上的一篇研究論文《Samplingcan be faster than optimization》顯示，一般的看法通常是不正确的，因為存在自然類的非凸問題，對于這些問題，采樣算法的計算複雜度與模型次元成線性比例關系，而優化算法的計算複雜度與模型次元成對數比例增長關系。
論文研究了混合模組化和多穩定系統中出現的一類非凸目标函數，這些算法建立在兩種通用的計算政策之上，這兩種政策都源于數學優化和馬爾科夫蒙特卡洛模型(MCMC)采樣。以前對這些算法的研究大多是分開進行的，對最優化的研究側重于估計和預測問題，對抽樣的研究側重于不确定性的估計，如形成可信區間和進行假設檢驗。近幾年有朝着使用兩種方法的方向發展的趨勢，且更側重于梯度和随機梯度的使用，而不是函數值或高階導數，因為它們在單個算法步驟的計算複雜性和總體收斂速度之間進行了有效的折衷，事實證明的确是很有效的。
通過使用來自優化理論的工具為MCMC采樣建立收斂速度，包括非漸近維數依賴性，結果顯示采樣的速度比優化的速度要慢，這與一般的觀點一緻。但是，這些結果是在凸函數中獲得的。
論文的重點是研究非凸函數，我們發現有一類問題它們在有界區域之外是強烈凸的，但在其内部是非凸的。對于此類問題，抽樣比優化更有效。
算法一：MALA(基于梯度的MCMC算法)
算法二：GD(基于梯度的優化算法)
最優化算法和蒙特卡羅抽樣算法為近年來統計機器學習應用的快速發展提供了計算基礎，然而，理論上對于這兩種方法之間關系的解釋是有限的，對于相對優勢和劣勢的解釋也是有限的。此外，已有的研究成果主要集中在對數凸函數(優化)和對數凹函數(采樣)的設定上。在這種情況下，局部屬性決定全局屬性，優化算法毫無疑問比采樣算法更有效。機器學習和資料科學是結合計算機科學和統計學來解決推理問題，這些問題的規模和複雜性需要現代化的計算機基礎裝置。
批判思維 挑戰權威 敢冒風險 獨立體驗
http://daoqi.org.cn
(編輯：28号淘氣包)