機(jī)器學(xué)習(xí)中的隨機(jī)優(yōu)化算法計(jì)算機(jī)專業(yè)

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

2、FGS方法及其隨機(jī)算法的改進(jìn)。本文將詳細(xì)全面的敘述機(jī)器學(xué)習(xí)中各種隨機(jī)算法，介紹隨機(jī)算法的發(fā)展歷程，研究方向及研究熱點(diǎn)，最后通過(guò)數(shù)值試驗(yàn)比較了幾種常見(jiàn)隨機(jī)算法，以給讀者直觀的數(shù)值效果。 關(guān)鍵詞：大規(guī)模機(jī)器學(xué)習(xí)，隨機(jī)算法，優(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 基礎(chǔ)知識(shí) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

12、 . . . . . . . . . . . . . . . .142.5 隨機(jī)原始對(duì)偶坐標(biāo)法（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 隨機(jī)牛頓方法 . . . . . . . . . . . . . . . . . . . . . . . . . . .

16、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .254 數(shù)值實(shí)驗(yàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27參考文獻(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29致謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .314 III 引言近些年來(lái)，隨著科學(xué)技術(shù)不斷地進(jìn)步發(fā)展，尤其是在計(jì)算機(jī)、通信等領(lǐng)域的進(jìn)步以

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

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

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

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

22、方向，因此亦被稱為最速下降法，它僅利用了函數(shù)的梯度信息，因此也被稱為一階方法。梯度方法每次迭代的方向?yàn)槠湄?fù)梯度方向，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),但當(dāng)目標(biāo)函數(shù)是強(qiáng)凸函數(shù)時(shí)，其收斂速度為線性收斂速度。梯度下降方法需要需要計(jì)算n個(gè)梯度，這一計(jì)算量為O(nd),當(dāng)n和d很大時(shí)，這一計(jì)算 量和存儲(chǔ)空間是很大的。一個(gè)更實(shí)用的改進(jìn)是每一次迭代時(shí)，隨機(jī)選擇一個(gè)點(diǎn)計(jì)算梯度來(lái)進(jìn)行更新

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

24、因此如果我們能夠改進(jìn)算法使得方差不斷的減小直至零。比較有代表性的方差減小方法有三種，分別稱為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是最早提出的具有線性收斂速度的隨機(jī)梯度方法，其每次更新不依賴于n。SAGA可以看成是結(jié)合SAG和SVRG兩種方法的技巧提出的

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

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

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

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

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

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

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

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

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

34、難獲得的，我們更傾向于采用隨機(jī)采樣的方法來(lái)更新。這一方法被稱為隨機(jī)梯度方法(stochastic gradient method)，或者稱為Robbins-Monro7 算法。2.2 隨機(jī)梯度方法（Stochastic Gradient Method）隨機(jī)梯度方法(SG)迭代的過(guò)程并不由目標(biāo)函數(shù)，初始點(diǎn)，步長(zhǎng)等因素唯一決定，其過(guò)程也是隨機(jī)的，這不同于標(biāo)準(zhǔn)的梯度方法，每一次迭代，其根據(jù)某分布隨機(jī)選擇 一個(gè)樣本點(diǎn)來(lái)更新目標(biāo)變量。其中一種SG方法為隨機(jī)梯度下降算法(stochastic gradientdescent)，SGD并不能保證目標(biāo)函數(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每一輪迭代的計(jì)算量是標(biāo)準(zhǔn)梯度法的1 ，僅為O(d)，但是其步長(zhǎng)要不斷的減小才能保證目標(biāo)函數(shù)能收斂到最優(yōu)值點(diǎn)。我們將從理論對(duì)SG做進(jìn)一步認(rèn)識(shí)，這是一些已知的 結(jié)論16,我們考慮更一般的形式(SG)，如算法1。Algorithm 1 SG選擇初始點(diǎn)x1for t=1,2,. . . ,m do生成一個(gè)隨機(jī)變量k 計(jì)算隨機(jī)向量g(xk, k) 確定步長(zhǎng)k更新： xK+1 = xKkg(xk, k) end for引理 1 如果函數(shù)F(x)是L-光滑函數(shù)，那么算法1

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

37、hitz函數(shù)并且滿足假設(shè)1，那么對(duì)任意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ù)，µ強(qiáng)凸函數(shù)，假設(shè)算法1中步長(zhǎng)固定，即對(duì)任意k N均有k = 且 µG0 < < LM則對(duì)任意k N有如下的不等式：EF(xk) F(x*) LM + (1 cµ)k1(F(x1) F(x*) LM )2Cµ kLM 2Cµ

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

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

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

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

42、以看做是f (k)。在SAGA中， = 1，而在SAG 中 = 1 ，SAG的方差是SAGA的 1 ，但jjnn2是SAGA的估計(jì)是無(wú)偏估計(jì)。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是最早提出的具有線性收斂速度的隨機(jī)梯度方法，其每

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

44、中yk = f (xk)如果i = ik，ik是隨機(jī)選取的指標(biāo)，否則yk保持不變。iiiikSAG方法相比于SGD有著很明顯的優(yōu)點(diǎn)，它可以采用固定步長(zhǎng)進(jìn)行更新，并且有 著更快的收斂性質(zhì)，線性收斂速度。但是它需要存儲(chǔ)n個(gè)梯度，當(dāng)n和d 很大時(shí)，其存儲(chǔ)量為O(nd)，其存儲(chǔ)量是十分巨大的，但是對(duì)于某些特殊的函數(shù)，比如帶有線性預(yù)測(cè)形式的函數(shù)fi(aT x)，其存儲(chǔ)量大大減小，只需要O(d)。如果初始梯度選擇的是零向量，也即yi = 0，那么在算法迭代的初始可以將步長(zhǎng)調(diào)為1 直至更新此處k = n，這樣的調(diào)整可以提高收斂的速度。SAG的算法如下10：當(dāng)取合適的步長(zhǎng)時(shí)，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ù)，µ強(qiáng)凸函數(shù)，如果固定步長(zhǎng)k = 21，這有如下的)k32ix x +o關(guān)系式：Exk x*2 (1 µ8Ln*9 i f (x*)2 4nL2µ進(jìn)一步，如果n 8L ，步長(zhǎng)為k = f rac

46、12nµ，SAG迭代滿足對(duì)于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é)果是當(dāng)k n時(shí)，在前n步使用SG方法，然后以前n步迭代的均值作為SAG的初始值，同時(shí)yi = 0，雖然SAG有著同樣的收斂速度，但是更加難分析，在實(shí)驗(yàn)中可以直接使用SAG方法，這里僅僅為了給出一個(gè)理論上更好的界。LSAG方法是一種線性收斂的隨機(jī)梯度算法，其收斂速度為O(n + )log(1/s)。SAG方法可以使用采用定步長(zhǎng)，在實(shí)際中可取k = 1 ，由

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

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

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

50、i(x0)令x0= xk1 nfor j=1,2,. . . ,m do隨機(jī)選取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ī)選取j 1, 2, . . . , m，令xk+1 = x jk+1m j=1jend for全梯度方法的計(jì)算復(fù)雜度很相近，但它僅需要O(log(1/s)次外循環(huán)，其復(fù)雜度為O(n +)log(1/s)?？梢钥闯?，每次內(nèi)循環(huán)時(shí)，在計(jì)算方向向量時(shí)，會(huì)用到全梯度這一信息，這與SG有 著很明顯的差別，這在其他收斂性

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