VIP內容

優化在機器學習中扮演著重要的角色。作為理論上收斂速度最快的一階優化算 法,加速梯度法在機器學習領域取得了廣泛的應用。本文將研究經典加速算法在帶 約束凸優化問題、隨機凸優化問題、分布式凸優化問題和非凸優化問題上的應用。本文首先介紹加速技巧在交替方向乘子法(ADMM)中的應用,並提出了具有最優 非遍曆意義收斂速度的加速ADMM算法。經典ADMM算法在求解非強凸非光滑問題 時具有遍曆意義下O ( 1 K ) 收斂速度和非遍曆意義下O ( 1 √ K ) 收斂速度。在稀疏和低秩學 習中,遍曆意義中的取平均操作會破壞解的稀疏性和低秩性,因此在實際應用中我們 往往使用非遍曆意義解。我們提出的加速ADMM具有非遍曆意義下更快的O ( 1 K ) 收斂 速度。並且我們還證明了經典ADMM的非遍曆意義下O ( 1 √ K ) 收斂速度是緊的,即經 典ADMM具有較慢的非遍曆意義收斂速度是算法本身的特性,並非由於證明技巧不足 所致。另外,我們證明了當求解非強凸非光滑問題時,ADMM類型算法的複雜度下界 是O ( 1 K ) ,即任何ADMM類型算法都不可能比O ( 1 K ) 更快。

在大數據背景下,加速技巧不僅應用於傳統優化,而且在隨機優化和分布式優化 中也有廣泛應用。本文研究了在隨機優化領域經典的加速隨機對偶坐標上升算法,並 對其原問題解的複雜度進行分析。該算法使用加速隨機坐標下降法求解對偶問題,當 目標函數是強凸非光滑函數時,對偶問題解具有O ( 1 √ ϵ ) 的複雜度。在實際應用中,我 們需要使用的是原問題解,而非對偶問題解,因此我們需要度量原問題解的複雜度。已有結論顯示,對於一般的帶約束凸優化問題,當對偶問題解具有O ( 1 √ ϵ ) 的複雜度時, 原問題解隻有O ( 1 ϵ ) 的複雜度。我們證明了如果對原問題解合適地進行加權平均,原 問題解具有和對偶問題解一樣的O ( 1 √ ϵ ) 的複雜度。當將加速隨機對偶坐標上升算法應 用到機器學習中經典的經驗損失最小問題時,我們的收斂速度比當前已有結論提高 了O ( log 1 ϵ ) 因子。

除了隨機優化領域,本文還研究了分布式優化領域的加速算法。我們首先對分布 式優化中經典的EXTRA算法重新分析,並給出了更快的O ( ( L µ + 1 1−σ2 (W) ) log 1 ϵ ) 的計算 複雜度和通信複雜度。然後我們使用Catalyst框架對EXTRA加速,得到了強凸情況下 複雜度為O (√ L µ(1−σ2 (W)) log L µ(1−σ2 (W)) log 1 ϵ ) 和非強凸情況下複雜度為O (√ L ϵ(1−σ2 (W)) log 1 ϵ ) 的加速EXTRA算法。除了對EXTRA進行擴展,我們還使用加速罰函數法對經典的分 布式加速梯度法進行解釋,並給出了具有最優計算複雜度(強凸情況下 O (√ L µ log 1 ϵ ) 和非強凸情況下O (√ L ϵ ) )和接近最優通信複雜度(強凸情況下O (√ L µ(1−σ2 (W)) log2 1 ϵ ) 和 非強凸情況下O (√ L ϵ(1−σ2 (W)) log 1 ϵ ) )的分布式加速算法。與已有分布式算法相比,我們提出的加速EXTRA算法和加速罰函數法具有更低的計算複雜度,同時我們的通信複 雜度或者與當前最好算法一樣,或者隻比當前最好算法高 O ( log L µ(1−σ2 (W))) 或O ( log 1 ϵ ) 因子。最後,我們研究了加速算法在非凸低秩優化中的應用。我們首先分析了該問題中 目標函數的曲麵性質,證明了當受限於某個特定凸集時,目標函數是受限製的局部強 凸函數。基於該性質,我們提出了交替約束加速梯度法並證明了該算法能夠局部線性 收斂到最優解。相比於梯度下降法,我們的收斂速度對條件數具有最優的 √ L/µ的依賴 關係。另外,當初始值為任意值時,我們的算法能夠全局收斂到梯度為0的點。

成為VIP會員查看完整內容
0
10
0
參考鏈接
Top