機器學習中的隨機優(yōu)化算法計算機專業(yè)

1、摘要對于機器學習中的數(shù)值優(yōu)化問題，考慮到其規(guī)模和維數(shù)都比較大，傳統(tǒng)的方法難以高效的解決這一問題。近些年來，針對大規(guī)模的機器學習問題做了很多研究，比較重要的一類方法是 隨機算法。優(yōu)化方法主要分為一階梯度方法和二階牛頓方法兩大類，針對一階方法的改進和研究比較成熟和完善，一階方法又可以分為兩類，原始方法和對偶方法，原始方法比較有代表性的有SAG、SAGA、SVRG，對偶方法有SDCA和SPDC兩種。此外，加速方法如Catalyst、Katyusha，其收斂速度為一階方法所能達到的最好結(jié)果。二階方法目前是機器學習領域研究的重要方向，其收斂速度要優(yōu)于一階方法，但是其實踐中會有一些難度，比較實用的是L-B

2、FGS方法及其隨機算法的改進。本文將詳細全面的敘述機器學習中各種隨機算法，介紹隨機算法的發(fā)展歷程，研究方向及研究熱點，最后通過數(shù)值試驗比較了幾種常見隨機算法，以給讀者直觀的數(shù)值效果。 關鍵詞：大規(guī)模機器學習，隨機算法，優(yōu)化方法1 I Stochastic Optimization Algorithm in Machine LearningAbstractFor the optimization problem in machine learning field, traditional method have difficulties in solving the high dimension

3、 and big data problem . In recent years, there are many researches in large scale machine learning problems, especially stochastic algorithms. Generally, stochastic method can divided into two parts. One is first-order gradient method and the other is second- order Newton method. There is more impro

4、vement and research in first order method , and the first order method is more mature and perfect. There is two classes for first order method. For the primal class, SVRG,SAG,SAGA is the representation , and SDCA ,SPDC for dual class. Otherwise , the acceleration method such as catalyst and katyusha

5、, which has the optimal con- vergence speed for first order method, is put forward in last two years. Second order method is one important research area , and it has better convergence but not better performance because it has to compute the hessian matrix , one useful method is L-BFGS and its varia

6、nts.In this paper, the author will introduce stochastic algorithms in machine learning area in detail. In the end , numerical experiments compare some common algorithm and give a direct view to readers. Key Words:Large-scale machine learning problem,Stochastic algorithm,Optimization method2 II 目錄摘要.

7、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .IAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8、. . . . . . . . . . .II引言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 基礎知識 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9、. . . . . . . . . . . . . . . . . . .52 一階方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62.1 梯度下降法（Gradient Descent） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10、 . . . . . . .62.2 隨機梯度方法（Stochastic Gradient Method） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.3 方差減小方法（Variance Reduction Method) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.3.1隨機平均梯度方法(StochasticAverage Gradient). . . . . . . . . . . . . . .

11、. . . . . . . . . . .112.3.2 隨機方差減小梯度方法(Stochastic Variance Reduction Gradient). . . . . . . . . .122.3.3 SAGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .132.4 隨機對偶坐標上升法（Stochastic Dual Coordinate Ascent） . . .

12、 . . . . . . . . . . . . . . . .142.5 隨機原始對偶坐標法（Stochastic Primal Dual Coordinate）. . . . . . . . . . . . . . . . . . . .162.6 加速方法Catalyst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192.7 Katyusha . . . . . . . . . . .

13、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203 二階方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .223.1 牛頓法與擬牛頓法 . . . . .

14、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .223.1.1 SR1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .233.1.2 BFGS、DFP . . . . . . . . . . . .

15、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .233.2 Limited-memory-BFGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .243.3 隨機牛頓方法 . . . . . . . . . . . . . . . . . . . . . . . . . . .

16、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .254 數(shù)值實驗 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27參考文獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29致謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .314 III 引言近些年來，隨著科學技術不斷地進步發(fā)展，尤其是在計算機、通信等領域的進步以

18、及互聯(lián)網(wǎng)不斷的普及。人們產(chǎn)生數(shù)據(jù)速率大大提高的同時又能夠容易廉價地獲取和存儲數(shù)據(jù)。數(shù)據(jù)中蘊含是大量信息，但是如何在大量數(shù)據(jù)中發(fā)掘出有效的信息是一個很困難的問題。為了解決該問題，人們嘗試采用各種方式。其中，比較好的處理方式是使用機器學習、數(shù)理統(tǒng)計的方法。機器學習利用數(shù)據(jù)建立模型來進行預測，其中常見的方法是將問題轉(zhuǎn)化成一個優(yōu)化模型，進而求解一個目標函數(shù)來。然而在大數(shù)據(jù)時代，數(shù)據(jù)的數(shù)量和數(shù)據(jù)的維數(shù)都比較高，如何更有效的處理和挖掘大數(shù)據(jù)，不僅要不斷的改進和發(fā)展計算機硬件，也要不斷的去改進機器學習算法的效率。提高機器學習算方法的效率更多的依賴于對數(shù)值優(yōu)化算法的改進，因此有必要對大規(guī)模機器學習中的優(yōu)化算法

19、進行總結(jié)。本文力求詳細全面地對現(xiàn)有的機器學習中的優(yōu)化方法做一概述，也是對自己最近學習的一個總結(jié)。給定一個訓練數(shù)據(jù)集T = (x1, y1), (x2, y2), . . . , (xN, yN)，機器學習的策略是求經(jīng)驗風險最小損失的模型，常見的經(jīng)驗風險損失模型為65=min F(x) + g(x)1 nfi(x)xdn i=1其中， fi(x) : d 是一個凸的光滑損失函數(shù), fi與樣本密切相關，n代表著樣本的個數(shù)。然而，當樣本容量很小時，容易產(chǎn)生“過擬合”現(xiàn)象，為了防止過擬合。常在經(jīng)驗風險上加上表示模型復雜度的正則化項或懲罰項，稱為結(jié)構風險損失函數(shù)。=min F(x) + g(x)1 nf

20、i(x) + g(x)xdn i=1其中， fi(x) : d 是一個凸的光滑損失函數(shù), fi與樣本密切相關，n代表著樣本的個數(shù)。g(x) : d 是正則化函數(shù)，通常也是一個凸函數(shù)。這種形式的問題在機器學習中有著很廣的應用，許多機器學習方法可以歸結(jié)成求如上形式的優(yōu)化問題：線性支持向量機可以轉(zhuǎn)化成求一些的優(yōu)化問題123:=min P(x)1 n1 bi(aT x) +x2xn i=1i+2其中，a+ = max0, a 邏輯回歸是歸結(jié)為解決下述的優(yōu)化問題23：min P(x)1 n log(1 + ebiaT x) + x2x= ni=1i22LASSO可以轉(zhuǎn)化成求解以下優(yōu)化問題23：min P

21、(x) = 1 n(ai x bi)2 + 1 x2x2ni=121解決這一問題的難點在于，當優(yōu)化變量的維數(shù)d和樣本的個數(shù)n比較大時，求解這 一問題需要非常大的計算量和存儲內(nèi)存。對于這種大規(guī)模的優(yōu)化問題，比較常見的方 法可以分為批處理方法和隨機算法。批處理方法主要包括全梯度下降方法和擬牛頓L-BFGS方法，隨機方法主要有隨機梯度下降法（SGD）以及這種算法的改進，比如隨機方差下降梯度方法(SVRG)、隨機平均梯度方法(SAG);隨機對偶坐標上升法（SDCA），隨機原始對偶坐標方法（SPDC）。梯度下降法是一種線搜索方法4，每一次迭代選擇該點的負梯度方向作為搜索方 向，因為負梯度方向是最快的下降

22、方向，因此亦被稱為最速下降法，它僅利用了函數(shù)的梯度信息，因此也被稱為一階方法。梯度方法每次迭代的方向為其負梯度方向，xk 1 = xk kgk = xk k n fi(xk)+ni=1它的收斂速度為O(1/n),是一種次線性的迭代算法。一種加速的梯度算法AGD45形如：xk+1 = xk + (xk xk1) k f (xk + (xk xk1)它的收斂速度為O(1/n2),但當目標函數(shù)是強凸函數(shù)時，其收斂速度為線性收斂速度。梯度下降方法需要需要計算n個梯度，這一計算量為O(nd),當n和d很大時，這一計算 量和存儲空間是很大的。一個更實用的改進是每一次迭代時，隨機選擇一個點計算梯度來進行更新

23、,SGD形式如67：xk+1 = xk k fik (xk)ni=1并且需要滿足E fik (xk)|xk1 = 1 n fi(xk)。這一改進的好處是，每一個次迭代其計算n量是標準梯度下降法的1 。對于隨機梯度下降法(SGD),其隨機向量g(xk, k)是函數(shù)全梯度的無偏估計，因此其滿足 EF(x) g(x , ) f (x ) (2L 222 * L/2) F(x ) +Eg(x , ) F(x )k+1kkkkkkk22kkk上式不等號右邊的第二項是我們預期的誤差，第三項我們稱之為方差，因為方差的存在，所以SGD也需要采用變步長的方式才能保證算法的收斂。方差的存在導致了算法性能上的不足，

24、因此如果我們能夠改進算法使得方差不斷的減小直至零。比較有代表性的方差減小方法有三種，分別稱為SVRG8，SAG910，SAGA11，這三種方法的更 新方式如下：f (xk) f (k)1jxk 1 = xk jj +n f (k)(S AG)+nni=1 iixk 1 = xk f (xk) f (k)1 n f (k)(S AGA)+jjj + n i=1 iixk 1 = xk f (xk) f (x) +1 nf (x)(S VRG)+jj n i=1 i SAG9是最早提出的具有線性收斂速度的隨機梯度方法，其每次更新不依賴于n。SAGA可以看成是結(jié)合SAG和SVRG兩種方法的技巧提出的

25、新的算法，它與SVRG的收斂速度相近，并適用于非強凸的問題。SVRG有著良好的性質(zhì)，并且適用于非凸函數(shù)。另外一類比較實用的方法是隨機對偶方法，主要有SDCA12和SPDC13，SDCA是 將原始問題轉(zhuǎn)化為其對偶形式，采用隨機坐標的思想，隨機選擇對偶坐標不斷求極大直到最優(yōu)值，SPDC 是將其原問題轉(zhuǎn)化為鞍點問題，通過交替最小化原始變量和最大化對偶變量來求鞍點，在正文中將繼續(xù)介紹著兩種方法。牛頓方法14是利用函數(shù)二階信息的一種優(yōu)化方法，現(xiàn)實中我們常常使用一種近似 的牛頓方法，擬牛頓法，在機器學習領域中，比較常用的是L-BFGS擬牛頓方法，這一 方法在最優(yōu)值附近可以達到次線性的收斂速度。其迭代格式為

26、：xk+1 = xk kHkFk其中，k是步長，Hk是Hessian陣的逆的一種近似。更新的方式為：Hk+1 = VT HkVk + kyk sTkkkyT skk其中k = 1 , Vk = I kyk sT .sk = xk+1 xk, yk = fk+1 fk。因為二階方法在計算中復雜度比較高，對二階方法的改進存在一定的難度，因此關于二階的隨機方法的工作還比較有限，我們將在正文介紹幾種改進的算法。 接下來第一章我將介紹相關的數(shù)學知識背景，第二章我將分別對一階算法進行介紹，第三章我將對二階算法的做一介紹，第四章我將通過一些實驗來對比不同的優(yōu)化算法。1基礎知識定義 1 L-Lipshistz

27、連續(xù) 稱函數(shù)f : d 為L-Lipschitz連續(xù)函數(shù)， L > 0 ， 如果對于a, b d，均有| f (a) f (b)| L|a b|定義 2 光滑稱函數(shù)f : d 為光滑函數(shù)， > 0，如果對于任意a, b d，均有2f (b) f (a) + f (a), T (b a) + b a2定義 3 凸函數(shù) 稱函數(shù)f : d 為凸函數(shù)，如果對于任意a, b d，均有f (b) f (a) + f (a), T (b a)定義 4 µ強凸函數(shù) 稱連續(xù)可微的函數(shù)f : d 為µ強凸函數(shù)，µ > 0，如果對于任意a, b d，均有2f (b)

28、f (a) + f (a), T (b a) + µb a2定義 5 條件數(shù) 如果連續(xù)可微的函數(shù)f : d 為光滑函數(shù)，µ強凸函數(shù)，記 =µ稱為原函數(shù)的條件數(shù)。定義 6 最小值點 點x*稱之為局部最小值點，如果存在x*的領域N，使得對任意x N均有f (x) f (x*) 點x*稱之為嚴格最小值點（強最小值點），如果存在x*的領域N，使得對任意x N且x Ç x*，均有f (x) > f (x*)定理 1 一階必要性條件如果x*是最小值點，并且函數(shù)f 在x*的一個開領域是連續(xù)可微的，那么有 f (x*) = 0。定理 2 如果函數(shù)f 是凸函數(shù)，那么

29、任意局部最小值點均為全局最小值點。此外，當函數(shù)是可微時，任何x滿足 f (x) = 0的點均為全局最小值點。2一階方法2.1 梯度下降法（Gradient Descent）梯度下降法是一種線搜索方法，每一次迭代選擇該點的負梯度方向作為搜索方向， 因為負梯度方向是最快的下降方向，因此亦被稱為最速下降法，它僅利用了函數(shù)的梯度信息，因此也被稱為一階方法。它的形式非常的直觀簡單，在每一次迭代選擇負梯度方向作為其下降方向，其更新形式如下：xk 1 = xk kgk = xk k n fi(xk)+ni=1其中，k是步長或?qū)W習率，它可由一些準則確定，比如Wolfe準則、Armijo準則等。L當函數(shù)F是凸函

30、數(shù)，并且其梯度是L Lipshitz函數(shù)時，取 = 1 時，它的收斂速度可以達到O(1/k)5，f (xk) f (x*) 2L x0 x* 22k + 4進一步，當F是µ強凸，并且其梯度是L lipshitz函數(shù)時，其收斂速度為線性收斂5：f (xk) f (x*) L ( L µ)2k x0 x* 22 L + µNesterov證明了一階方法的理論最優(yōu)下界45，并且采用了一種加速的方法對梯度下降算法進行了改進，稱之為Nesterov加速，稱這一算法為加速梯度下降算法（AGD）。一種常用的AGD 迭代方式如下：xk+1 = yk k f (yk)yk+1 =

31、xk+1 + (xk+1 xk)L當函數(shù)F是凸函數(shù)，并且其梯度是L Lipshitz函數(shù)時,如果k =22µ)速度為1 、 =L µL+ µ 其收斂L(2zzzzzzzf (xk) f (x*) min(1 µ)k,4L L + k * f (x0) f (x*) + µ x0 x* 2上述收斂速度對于非強凸函數(shù)和強凸函數(shù)都是適合的，當函數(shù)為非強凸時，取µ=0。通 過迭代格式，可以看出，在其迭代時，僅涉及到向量的加減以及數(shù)乘運算，因此其每一次迭代的計算復雜度為O(nd)。然而，在每一步，梯度下降方法需要需要計算n個梯度，其計算量為O(

32、nd),當n和d很 大時，這一計算量和存儲空間是很大的。因此，如何改進梯度算法，使得其適用于大規(guī)模的機器學習優(yōu)化問題，特別是在數(shù)據(jù)爆炸的今天，成為一個很有意義的問題。然而，在每一步，梯度下降方法需要需要計算n個梯度，其計算量為O(nd),當n和d很 大時，這一計算量和存儲空間是很大的。因此，如何改進梯度算法，使得其適用于大規(guī)模的機器學習優(yōu)化問題，特別是在數(shù)據(jù)爆炸的今天，成為一個很有意義的問題。一種比較常見的方法是確定性提升梯度方法(deterministic incremental gradient0method)15，稱之為IG。IG方法和標準的梯度下降方法非常相似，對于n個函數(shù)和的形式的目

33、標函數(shù)，其主要區(qū)別是IG方法使變量沿著其中一個函數(shù)的梯度方向循環(huán)更新。 具體的可以看成是一個有著兩層循環(huán)的算法，每一次外層迭代可以看成是一個m次內(nèi)層迭代的循環(huán)。令初始點為x0 n，對于任意k > 0，更新方式為x(k) = x(k) k fi(x)(k)ii1其中k > 0，代表著步長，x(k+1) = xk 。i10nIG方法的性能取決于內(nèi)循環(huán)中迭代順序，如果對于某些具體問題，如果存在一些已 知的信息，并能確定出一個迭代順序(1, . . . , n 的一個排列)，那么IG方法則有很好的性能。x(k) = x(k) k f(x(k) )ii1(i)i1然而，在現(xiàn)實當中先驗信息是很

34、難獲得的，我們更傾向于采用隨機采樣的方法來更新。這一方法被稱為隨機梯度方法(stochastic gradient method)，或者稱為Robbins-Monro7 算法。2.2 隨機梯度方法（Stochastic Gradient Method）隨機梯度方法(SG)迭代的過程并不由目標函數(shù)，初始點，步長等因素唯一決定，其過程也是隨機的，這不同于標準的梯度方法，每一次迭代，其根據(jù)某分布隨機選擇 一個樣本點來更新目標變量。其中一種SG方法為隨機梯度下降算法(stochastic gradientdescent)，SGD并不能保證目標函數(shù)在每相鄰兩次迭代都一定下降，只是期望意義上的下降算法67

35、：x(k+1) = x(k) k fik (x(k)ni=1且滿足E fik (x(k) = 1 n fi(x(k) = F(x(k)。n每一輪迭代的計算量是標準梯度法的1 ，僅為O(d)，但是其步長要不斷的減小才能保證目標函數(shù)能收斂到最優(yōu)值點。我們將從理論對SG做進一步認識，這是一些已知的 結(jié)論16,我們考慮更一般的形式(SG)，如算法1。Algorithm 1 SG選擇初始點x1for t=1,2,. . . ,m do生成一個隨機變量k 計算隨機向量g(xk, k) 確定步長k更新： xK+1 = xKkg(xk, k) end for引理 1 如果函數(shù)F(x)是L-光滑函數(shù)，那么算法1

36、滿足如下的不等式，對于任意的k N：Ek F(xk+1) F(xk) kF(xk)T Eg(xk, k) + 1 2LE g(xk, k) 2k2 kk2假設 1 目標函數(shù)和SG(算法1)滿足如下條件:(1) 函數(shù)F是下有界的，并且序列xk在一個開集中(2) 存在µG µ > 0，使得對于任意k NF(xk)T E g(xk, k) µ F(xk) 2k2 Ek g(xk, k) 2 µG F(xk) 2(3) 存在M 0和Mv 0，使得對于任意k Nk2V g(xk, sk) M + Mv F(xk) 2引理 2 如果函數(shù)F(x)是L-Lipsc

37、hitz函數(shù)并且滿足假設1，那么對任意k N滿足如下不等式:E F(x1+) F(x ) F(x )T E g(x , )2 LE g(x , ) 2kk+1kkkkkk2 kkkk2 (µ 1 kLMG)k F(xk) 21 2 LM22 + 2 k定理 3 如果函數(shù)F是L-Lipschitz連續(xù)函數(shù)，µ強凸函數(shù)，假設算法1中步長固定，即對任意k N均有k = 且 µG0 < < LM則對任意k N有如下的不等式：EF(xk) F(x*) LM + (1 cµ)k1(F(x1) F(x*) LM )2Cµ kLM 2Cµ

38、2cµ由上述定理可以得知，如果步長是固定時，那么算法最終僅能收斂到最優(yōu)值點的鄰域附近的次優(yōu)點，因此可以通過不斷減小步長來保證算法收斂到最優(yōu)值點，這可有以下定理在理論上得以保證。定理 4 如果函數(shù)F是L-Lipschitz連續(xù)函數(shù)，µ強凸函數(shù)，假設算法1中步長采用如下序列更新： k = + k其中 > 1 并且 > 0使得1 µ cµ則對任意k N有：LMG v EF(xk) F(x*) + k其中v :2LM*= max 2cµ 1), ( + 1)(F(x1) f (x )對于隨機梯度下降法(SGD),其隨機向量g(xk, k)是

39、函數(shù)全梯度的無偏估計， 也即滿足F(xk) = Eg(xk, k)。因此其滿足EF(x) g(x , ) f (x ) (2L * L/2) F(x ) +Eg(x , ) F(x )k+1kkkkkkk22kkk 222上式不等號右邊的第二項是我們預期的誤差，第三項我們稱之為方差，因為方差的存在，所以SGD也需要采用變步長的方式才能保證算法的收斂。方差的存在導致了算法性能上的欠缺，如果我們能夠改進算法使得方差不斷的減小直至零，便能夠提升算法的性能，在下一節(jié)中我們將介紹三種這樣的方法。隨機梯度方法相比于標準梯度方法更加有效地利用了數(shù)據(jù)，標準梯度方法每一次更新目標變量需要用到所有的樣本，但是在實

40、際問題中，數(shù)據(jù)會存在這一定的冗余，因此，每次用到全體數(shù)據(jù)的一部分也能產(chǎn)生很好的效果，并且其效率會更高。通過實驗可以得知，隨機梯度方法在剛開始下降的比較劇烈，會很快達到一定精度的次優(yōu)解。再 者，如果忽略通信時間，標準梯度方法的收斂速度為O(nlog(1/s)(因為每次迭代需要計 算n個梯度)，而雖然SGD 的收斂速度為O(1/T )，但是其每次只計算一個梯度，因此其收斂速度為1/s，當n很大時，并且在實際中計算時間和精度要求有限時，SGD并不比標準梯度的效果差。2.3 方差減小方法（Variance Reduction Method)方差的存在是使得隨機梯度方法性能欠缺的一個主要原因，通過減小方

41、差來提升算法的性能是一個很好的想法。首先給出一種方差減小的觀點11，假設用蒙特卡洛采樣 的方法去更新EX，如果能夠高效的計算出EY，并且Y與X 有著密切的關系，那么可以不斷用 來不斷逼近Y。其中 = (X Y) + EY，那么E 是EX 和EY 的凸組合， 的方差為Var() = 2Var(X) + Var(Y) 2Cov(X, Y)。如果取 = 1，那么 是X 的無偏估計。有三種比較經(jīng)典的方法可以看成是采用這一思想來改進SGD，分別是SAG(隨機平 均梯度方法),SVRG(隨機方差減小方法)和SAGA。j對于SAGA11和SAG910， X是隨機梯度方法(SGD)的方向采樣f (xk),Y可

42、以看做是f (k)。在SAGA中， = 1，而在SAG 中 = 1 ，SAG的方差是SAGA的 1 ，但jjnn2是SAGA的估計是無偏估計。SVRG8采用的是Y = f (x)，并且它分為了內(nèi)外兩層循環(huán)。這三種方法的更新方式如下：j f (xk) f (k)1jxk 1 = xk jj +n f (k)(S AG)+nni=1 iixk 1 = xk f (xk) f (k)1 n f (k)(S AGA)+jjj + n i=1 iixk 1 = xk f (xk) f (x) +1 nf (x)(S VRG)+jj n i=1 i SAG9是最早提出的具有線性收斂速度的隨機梯度方法，其每

43、次更新不依賴于n。SAGA 可以看成是結(jié)合SAG和SVRG兩種方法的技巧提出的新的算法，它與SVRG的收斂速度相近，并適用于非強凸的問題。SVRG 有著良好的性質(zhì)，并且適用于非凸函數(shù)，近幾年來，關于SVRG的研究不斷進行，得到不斷發(fā)展。接下來將分別介紹三種方法。2.3.1 隨機平均梯度方法(Stochastic Average Gradient)SAG910可以看成是IAG17的一種隨機版本，類似于是隨機梯度方法，每一次迭代僅需要一個樣本點來計算方向向量，并且每次迭代的向量方向是全梯度的有偏估計， 但是它的收斂速度是線性的。SAG的迭代格式如下：xk 1 = xk k n yk+ni=1 i其

44、中yk = f (xk)如果i = ik，ik是隨機選取的指標，否則yk保持不變。iiiikSAG方法相比于SGD有著很明顯的優(yōu)點，它可以采用固定步長進行更新，并且有 著更快的收斂性質(zhì)，線性收斂速度。但是它需要存儲n個梯度，當n和d 很大時，其存儲量為O(nd)，其存儲量是十分巨大的，但是對于某些特殊的函數(shù)，比如帶有線性預測形式的函數(shù)fi(aT x)，其存儲量大大減小，只需要O(d)。如果初始梯度選擇的是零向量，也即yi = 0，那么在算法迭代的初始可以將步長調(diào)為1 直至更新此處k = n，這樣的調(diào)整可以提高收斂的速度。SAG的算法如下10：當取合適的步長時，SAG是一種線性收斂的算法，其收斂

45、速度為O(n + )log(1/s)，Algorithm 2 SAGd = 0, yi = 0i = 1, 2, . . . , nfor t=1,2,. . . ,m do均勻采樣 i 1, 2, . . . , n d = d yi + f (x)iiyi = f (x)x = x dn end for有如下定理9：nL定理 5 如果函數(shù)f 是L-Lipschitz連續(xù)，µ強凸函數(shù)，如果固定步長k = 21，這有如下的)k32ix x +o關系式：Exk x*2 (1 µ8Ln*9 i f (x*)2 4nL2µ進一步，如果n 8L ，步長為k = f rac

46、12nµ，SAG迭代滿足對于k n：8nE f (xk) f (x*) (1 1 )kC其中C = 16L x x*2 + 4i f (x*)2 (8log(1 + µn ) + 1)i3n#03n2µ4L上式的結(jié)果是當k n時，在前n步使用SG方法，然后以前n步迭代的均值作為SAG的初始值，同時yi = 0，雖然SAG有著同樣的收斂速度，但是更加難分析，在實驗中可以直接使用SAG方法，這里僅僅為了給出一個理論上更好的界。LSAG方法是一種線性收斂的隨機梯度算法，其收斂速度為O(n + )log(1/s)。SAG方法可以使用采用定步長，在實際中可取k = 1 ，由

47、于L通常未知，常采用線搜索的方式確定9。但是每次迭代其存儲量為O(nd)，計算量為O(d)，當n 和d 都比較大時，這會影響到算法的實際使用效率。2.3.2 隨機方差減小梯度方法 SAG是第一個取得線性收斂效果的隨機梯度方法，此后，對隨機算法的研究不斷深入，隨機方差下降梯度方法(SVRG)是其中最重要的算法之一。這是由8等人在2013年 提出的方法，是一種具有線性收斂的算法。它適用的范圍極其廣泛，不僅適用于強凸的函數(shù)，非強凸，非凸的情況也同樣有著很好的收斂性質(zhì)。這種方法不需要有存儲整個梯度并且在迭代過程中并不需要改變每一步的步長，在實際操作中更加的方便。這一方法分為兩層循環(huán)，每m次在一個點x計

48、算一次全梯度嗎，然后在該點計算一個 方向向量，并且這一向量是全梯度的一個無偏估計，然后做一次梯度”下降“。算法的主要思想如下：µ = F(x) =1 n fi(x)n i=1xt = xt1 t( fi (xt1) fi (x) + µ)tt 其中it 是隨機的從1, ., n選擇，因此我們有Ext|xt1 = xt1 tF(xt1)SVRG是一種方差不斷下降的方法。根據(jù)梯度的迭代格式， fit (xt1) fit (x) + µ。t 1(t 1)當x 和 x(t)都收斂到同一個x*時，µ 0。因此，當 fi(x) fi(x*)時fi (x ) fi (

49、x) + µ fi(x ) fi(x*) 0 tt 通過這一格式，方差能夠得到有效的控制，這提高了收斂的速度。SVRG算法是=+線性收斂的，如果F是L-Lipschitz光滑連續(xù)且µ 強凸時，當m足夠大使得 1µ(12L)m 2L 12L< 1可以得到EF(xs) F(x*) sF(x0) F(x*)其中x*是最優(yōu)值點。SVRG是一種線性收斂的隨機算法，其每一個內(nèi)循環(huán)需要計算2m + n次梯度，這和Algorithm 3 SVRG給定初始向量x0，步長，正整數(shù)m。for k=1,2,. . . do計算方向向量µ = F(x0) = n i=1 f

50、i(x0)令x0= xk1 nfor j=1,2,. . . ,m do隨機選取ij 1, 2, . . . , nx j = x j1 ( fij (xj1) fij (x0) + µ)end for選擇(1):令x= x k+1選擇(2):令xm= 1 m x選擇(3):隨機選取j 1, 2, . . . , m，令xk+1 = x jk+1m j=1jend for全梯度方法的計算復雜度很相近，但它僅需要O(log(1/s)次外循環(huán)，其復雜度為O(n +)log(1/s)?？梢钥闯?，每次內(nèi)循環(huán)時，在計算方向向量時，會用到全梯度這一信息，這與SG有 著很明顯的差別，這在其他收斂性

51、質(zhì)比較好的算法中也會得到體現(xiàn)，全梯度的使用控制了優(yōu)化過程的一個總體方向，使得優(yōu)化過程不會偏離整體方向太遠。SVRG方法的收斂速度為O(n + )log(1/s)，每輪內(nèi)循環(huán)的其計算量為O(nd + md)，通常m取為n的倍數(shù)，實際中取m = 2n即可。SVRG同樣適用于非強凸或者非凸的目標函數(shù)， 有著極好的性質(zhì)，可參見1819202.3.3 SAGA另 一 個 比 較 重 要 的 方 差 下 降 的 方 法 是SAGA11方 法， SAGA可 以 看 成是SAG和SVRG兩種方法思想的融合。SAGA中每次迭代的方向向量可以看成是之前 數(shù)次迭代方向的平均值， j 1, . . . , n是隨機選取的，具體的方式為：gk = f (xk) f (k)1 n f (k)jjj + n i=1 iin可以看出SAGA中方向的選取方式與SAG很類似，僅僅是將1 替換成了1，這一改變使得每次選取的方向向量是全梯度的無偏估計。它可以看成是SVRG與SAG兩種思想結(jié) 合形成的一種新的隨機算法1611。除了初始化時需要計算n個梯度，需要O(nd)的