一種抽樣二階隨機(jī)算法

王靜 王湘美

(貴州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,貴陽(yáng),550025)

1 引言

考慮以下優(yōu)化問(wèn)題:

其中每個(gè)fi:Rd →R 是定義在歐氏空間上的連續(xù)可微函數(shù).這類(lèi)問(wèn)題在數(shù)據(jù)擬合、回歸分析、參數(shù)估計(jì)、無(wú)線(xiàn)傳感網(wǎng)絡(luò)中的分布式優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、機(jī)器學(xué)習(xí)等方面有廣泛的應(yīng)用.梯度法和牛頓法等確定性算法是求解優(yōu)化問(wèn)題的經(jīng)典算法.然而當(dāng)問(wèn)題(1.1)的規(guī)模很大(n很大)時(shí),確定性算法每次迭代要計(jì)算所有fi的梯度(牛頓法還要計(jì)算所有fi的Hessian 矩陣),這導(dǎo)致每步迭代的計(jì)算成本和存儲(chǔ)成本都很高.因此,一些學(xué)者提出并研究了求解大規(guī)模問(wèn)題(1.1)的一階隨機(jī)算法和二階隨機(jī)算法.一階隨機(jī)算法(也稱(chēng)為隨機(jī)梯度算法)是結(jié)合梯度算法和隨機(jī)算法的思想提出來(lái)的.自從1951 年Robbins 等[1]提出采用常值步長(zhǎng)的隨機(jī)梯度算法SGD 后,一階隨機(jī)算法已經(jīng)成為訓(xùn)練學(xué)習(xí)模型的重要算法.SGD 算法為了保證收斂,其迭代步長(zhǎng)隨著迭代次數(shù)的增加需趨于零,這通常會(huì)導(dǎo)致算法迭代到一定次數(shù)后收斂速度變慢.后來(lái),Roux 等[2]提出了隨機(jī)平均梯度算法SAG,該算法為每個(gè)樣本保留一個(gè)舊梯度,在每次更新時(shí)隨機(jī)選取一個(gè)樣本計(jì)算新梯度來(lái)替換掉該樣本的舊梯度,然后用所有樣本梯度的平均值作為下一步更新的負(fù)方向.Roux 等證明了在一定條件下SAG 算法線(xiàn)性收斂.但是SAG 算法需要為每個(gè)樣本設(shè)置一個(gè)內(nèi)存空間，這就導(dǎo)致內(nèi)存很大.為了解決這個(gè)問(wèn)題,Johnson 等[3]提出了隨機(jī)方差減小梯度算法SVRG.SVRG 算法相對(duì)于SAG 算法而言,不需要在內(nèi)存中為每個(gè)樣本都保留一個(gè)梯度,節(jié)省了內(nèi)存資源.當(dāng)使用小批樣本梯度的均值估計(jì)全部樣本梯度的均值時(shí)會(huì)產(chǎn)生方差.Johnson 等指出SAG 算法和SVRG 算法之所以線(xiàn)性收斂,是因?yàn)閮煞N算法都減小了方差的干擾.之后，在減小方差這一思想的影響下,學(xué)者們提出了許多一階隨機(jī)梯度算法,見(jiàn)文獻(xiàn)[4-7].另外,應(yīng)用在Pytorch 和Tensorflow 中的隨機(jī)一階算法見(jiàn)文獻(xiàn)[8-14].

與一階隨機(jī)算法相比,二階隨機(jī)算法除了用到一階導(dǎo)數(shù)信息還要用到二階導(dǎo)數(shù)信息.牛頓法是經(jīng)典的二階優(yōu)化算法,它在一定條件下具有二階收斂速度,其迭代公式如下:

本文將Lissa 算法和SSN 算法結(jié)合起來(lái)，給出一種SSN-Lissa 算法.該算法首先采用SSN 算法的抽樣方法計(jì)算隨機(jī)梯度,然后采用Lissa 算法基于泰勒公式A-1=(I -A)i估計(jì)Hessian矩陣的逆,并采用類(lèi)似于SSN 算法的步長(zhǎng)規(guī)則計(jì)算步長(zhǎng).此外,我們還對(duì)SSN-Lissa 算法的全局線(xiàn)性收斂性進(jìn)行證明,并通過(guò)數(shù)值實(shí)驗(yàn)說(shuō)明SSN-Lissa 算法比Lissa 算法和SSN 算法精度更高,每步迭代的時(shí)間成本更低.

本文余下部分安排如下:第二節(jié)介紹預(yù)備知識(shí)?第三節(jié)給出SSN-Lissa 算法及其收斂性證明?第四節(jié)通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證SSN-Lissa 算法的有效性.

2 預(yù)備知識(shí)

設(shè)v ∈Rd,V ∈Rd×d.我們用‖v‖和‖V‖分別表示向量v的2-范數(shù)和矩陣V的譜范數(shù).對(duì)于兩個(gè)實(shí)對(duì)稱(chēng)矩陣A和B,用A ≥B表示A-B是半正定矩陣.對(duì)于二階連續(xù)可微函數(shù)f:Rd →R,我們用?f(x)和?2f(x)分別表示f在點(diǎn)x處的梯度和Hessian 矩陣?若Hessian 矩陣?2f(x)可逆,則用?-2f(x)表示它的逆矩陣.

下面的引理是常見(jiàn)的，容易用定義證明，其中I表示d階單位矩陣.

引理1設(shè)A ∈Rd×d.如果‖A‖≤1 且A正定,則有

我們對(duì)問(wèn)題(1.1)中的函數(shù)做以下假設(shè).

假設(shè)H1fi二階連續(xù)可微,且存在0＜mi ≤Mi ≤1,使得

顯然,在此假設(shè)下,存在0＜γ ≤K ≤1,使得

注1在本文的算法收斂性分析中,需要假設(shè)H1成立.幸運(yùn)的是,對(duì)于很多機(jī)器學(xué)習(xí)問(wèn)題的模型,例如嶺回歸模型、邏輯回歸模型等,假設(shè)H1都是成立的,詳見(jiàn)附錄表3 或參考文獻(xiàn)[9,15,17,18,19,24].

(2.4)表明函數(shù)F強(qiáng)凸且?2F的特征值介于γ和K之間.此時(shí)優(yōu)化問(wèn)題(1.1)的解x*存在、唯一，且滿(mǎn)足

我們稱(chēng)κ=為問(wèn)題(1.1)的條件數(shù).

設(shè)X ∈Rd×d是d階隨機(jī)矩陣.用E[X]表示X的數(shù)學(xué)期望.由(2.2),(2.3)和(2.4)式,可以得到如下引理(見(jiàn)文獻(xiàn)[18]).

引理2設(shè)優(yōu)化問(wèn)題(1.1)中函數(shù)F滿(mǎn)足(2.3)和(2.4),{h1,h2,···,hT}是總體的一組樣本,其中T為樣本數(shù).令

設(shè)A是一個(gè)隨機(jī)事件,用Pr(A)表示事件A發(fā)生的概率.以下引理是關(guān)于隨機(jī)矩陣范數(shù)的概率估計(jì)(見(jiàn)[23,Theorem 1.3]).

引理3設(shè)Y是d階隨機(jī)實(shí)對(duì)稱(chēng)矩陣,且滿(mǎn)足E(Y)=0,Pr(‖Y‖≤R)=1.則對(duì)于任意t ≥0有

引理4設(shè)由(2.6)定義,ε1∈(0,1).如果樣本數(shù)T滿(mǎn)足

由(2.4)知?2F(x)正定且‖?2F(x)‖≤1.再由引理1 可得

結(jié)合(2.10)可知(2.8)成立.

下面的估計(jì)式將在算法收斂性分析中起到重要作用.

命題1設(shè)由(2.6)定義,ε1∈(0,1).如果樣本數(shù)T滿(mǎn)足(2.7),則

設(shè)非空集合S ?{1,2,···,n},用符號(hào)|S|表示集合S中元素的個(gè)數(shù).定義函數(shù)g:Rd →R 如下:

我們稱(chēng)g(x)為?F(x)的一個(gè)隨機(jī)抽樣.

下面的引理給出在概率意義下g和?F的近似程度(見(jiàn)[19,Lemma 2]).為此我們需要以下假設(shè).

假設(shè)H2存在函數(shù)G:Rd →R 使得對(duì)任意的i=1,2,···,n，有

引理5設(shè)H2成立.若對(duì)任意的ε2,δ2∈(0,1),|S|滿(mǎn)足

則有

注2在假設(shè)H2中，需要事先確定G(x).幸運(yùn)的是,在很多機(jī)器學(xué)習(xí)問(wèn)題中，G(x)常?？梢允孪冉o出,詳見(jiàn)附錄表4.

3 SSN-Lissa 算法及收斂性分析

為求解問(wèn)題(1.1),我們給出以下二階隨機(jī)算法(SSN-Lissa 算法).

注3SSN-Lissa 算法是將Lissa 算法([18,Algorithm 1])和SSN 算法([19,Algorithm 4])結(jié)合起來(lái)的一種二階算法，與Lissa 算法異同之處主要體現(xiàn)在以下兩個(gè)方面:一是兩種算法采用相同的Hessian 矩陣逆的近似計(jì)算方法,但是Lissa 算法采用函數(shù)的全梯度,而SSN-Lissa 算法采用隨機(jī)梯度?二是步長(zhǎng)的選取不一樣,Lissa 算法步長(zhǎng)為1,而SSN-Lissa 算法采用步長(zhǎng)(3.2).SSN-Lissa與SSN 算法的異同則主要體現(xiàn)在兩種算法采用相同方式產(chǎn)生隨機(jī)梯度,但是對(duì)Hessian 矩陣或者Hessian 矩陣逆的估計(jì)不一樣.

注4SSN-Lissa 算法一次迭代可以分為兩步.第一步用公式(2.12)計(jì)算當(dāng)前迭代點(diǎn)的隨機(jī)梯度,其中抽取的函數(shù)個(gè)數(shù)|S|滿(mǎn)足(2.13).這里需要設(shè)置參數(shù)δ2∈(0,1)與ε2.δ2,ε2越小,隨機(jī)梯度越接近真實(shí)梯度?F(x(k))?第二步是估計(jì)當(dāng)前迭代點(diǎn)的Hessian 矩陣的逆,抽取的Hessian 矩陣的樣本數(shù),即Taylor 展開(kāi)的深度T越大，越接近真實(shí)Hessian矩陣的逆?-2F(x(k)).

我們分別按以下方式選取參數(shù)ε2和步長(zhǎng)αk（k=1,2,···）:

其中ε,ε1,β ∈(0,1)為任意給定的常數(shù).此時(shí),SSN-Lissa 算法有如下收斂性結(jié)果.

表1 確定性算法、隨機(jī)算法一次迭代的計(jì)算復(fù)雜度對(duì)比

注6從表1 看出,當(dāng)|S|和T遠(yuǎn)小于問(wèn)題的規(guī)模n時(shí),隨機(jī)算法(Lissa,SSN,SSN-Lissa)的計(jì)算成本遠(yuǎn)小于確定性算法(例如梯度法,Newton 法).在下一節(jié)的數(shù)值實(shí)驗(yàn)中,n=9847.在三次迭代之后，|S|≤120,T=5,SSN-Lissa 算法的|S|和T都遠(yuǎn)小于n,同時(shí)也比SSN 算法和Lissa 算法計(jì)算成本低.當(dāng)訓(xùn)練樣本數(shù)n和優(yōu)化參數(shù)d都很大時(shí),SSN-Lissa 算法更加具有優(yōu)勢(shì),這一點(diǎn)在后面的數(shù)值實(shí)驗(yàn)中也有體現(xiàn).

4 數(shù)值實(shí)驗(yàn)

實(shí)驗(yàn)采用MNIST-49 數(shù)據(jù)集進(jìn)行二分類(lèi)學(xué)習(xí),數(shù)據(jù)集包含9847 張訓(xùn)練樣本圖片,1991 張測(cè)試樣本圖片.我們采用附錄中邏輯斯蒂回歸模型進(jìn)行訓(xùn)練.在訓(xùn)練中,設(shè)置參數(shù)λ=0.5,β=0.4,δ2=0.7,ε1分別設(shè)置為0.9,0.7,0.5,0.3,0.1,其他參數(shù)我們按照下表設(shè)置.

表2 實(shí)驗(yàn)參數(shù)的設(shè)置

由定理1 我們知道SSN-Lissa 算法是概率意義下的下降算法,故我們?cè)谶\(yùn)行算法時(shí)采用如下更新方式:當(dāng)F(x(k+1))＜F(x(k))時(shí)我們更新迭代點(diǎn),當(dāng)時(shí)則不更新迭代點(diǎn).算法隨機(jī)產(chǎn)生初始迭代點(diǎn),通過(guò)SSN-Lissa 算法對(duì)數(shù)據(jù)進(jìn)行20 次訓(xùn)練,比較當(dāng)選擇不同ε1時(shí)SSN-Lissa 算法的性能(圖1).

圖1 選擇不同ε1,對(duì)改進(jìn)SSN-Lissa 算法性能進(jìn)行比較

從圖1 可以看出,SSN-Lissa 算法是下降算法.由于算法的初始點(diǎn)是隨機(jī)產(chǎn)生的,故SSN-Lissa算法是全局收斂.同時(shí),我們觀察到,當(dāng)參數(shù)ε1變大時(shí),算法的收斂速度變快.這一現(xiàn)象不難理解,定理1 說(shuō)明算法的收斂速度取決于的值，且ε1越大,收斂速度越快.當(dāng)設(shè)置ε1＞0.5時(shí),|S|≤120,仍然線(xiàn)性收斂.不僅如此,隨著ε1的增大,|S|的期望在減小.值得注意的是,隨著ε1的增大,|S|在減小(意味著每一步迭代所消耗的時(shí)間成本降低).我們觀察到|S|在第2 步之后變化不大，故我們僅計(jì)算前幾步|S|，以后的|S|用前幾步|S|的平均值替代,進(jìn)一步降低了每一步迭代所消耗的時(shí)間成本.

圖2 是關(guān)于SSN-Lissa 算法、Lissa 算法、SSN 算法在運(yùn)行時(shí)間和函數(shù)值的比較.迭代20 次，其中SSN-Lissa 算法設(shè)置ε1=0.9，|S|采取兩種方案:一種方案是每一步更新|S|?另一種方案是僅更新前兩步|S|,第三步以后的|S|用前兩步|S|的平均值替代.Lissa 算法和SSN 算法分別按照文獻(xiàn)[18]和[19]提供的數(shù)值實(shí)驗(yàn)設(shè)置參數(shù).

對(duì)比圖2 中的三種算法,SSN-lissa 算法每步迭代的時(shí)間成本最低.這是因?yàn)镾SN-Lissa 算法隨機(jī)計(jì)算部分函數(shù)梯度而Lissa 需要計(jì)算所有函數(shù)梯度,并且SSN-Lissa 算法直接估計(jì)Hessian 矩陣的逆,比SSN 算法(先估計(jì)Hessian 矩陣然后在計(jì)算逆)時(shí)間成本低.通過(guò)對(duì)比不同初始點(diǎn)的選取對(duì)三種算法的影響,發(fā)現(xiàn)當(dāng)初始點(diǎn)離最優(yōu)點(diǎn)較遠(yuǎn)時(shí)(中間圖)SSN-Lissa 的函數(shù)值下降最快,其次是SSN.這是因?yàn)镾SN-Lissa 算法和SSN 算法都可以達(dá)到全局線(xiàn)性收斂,而Lissa 算法僅在初始點(diǎn)接近最優(yōu)點(diǎn)時(shí)達(dá)到線(xiàn)性收斂.當(dāng)初始點(diǎn)在最優(yōu)點(diǎn)附近時(shí)(右邊圖)Lissa 算法函數(shù)值在第一步有很快的下降,之后趨于平穩(wěn),而SSN-Lissa 算法雖然剛開(kāi)始沒(méi)有Lissa 算法下降快,但是迭代6 次之后就達(dá)到了Lissa 算法的精度.

我們接下來(lái)的工作有兩個(gè)方面,第一方面是在SSN-Lissa 算法中考慮方差減小的思想?另一方面是用其他方式近似求Hessian 矩陣的逆.

圖2 SSN-Lissa(ε1=0.9),SSN,Lissa 三種算法性能對(duì)比

附錄A

考慮帶正則化的高斯先驗(yàn)的最大后驗(yàn)問(wèn)題(詳見(jiàn)[19]),其目標(biāo)函數(shù)為:

其中0＜λ ≤0.5 為正則化參數(shù),表示n組訓(xùn)練數(shù)據(jù),其中ai ∈Rd,bi ∈R.根據(jù)bi的不同取值,對(duì)應(yīng)采用不同的模型Φ(t).例如當(dāng)bi ∈R,Φ(t):=0.5t2時(shí),采用的模型為嶺回歸模型(RR)?當(dāng)bi ∈{0,1},Φ(t)=ln(1+exp(t)) 時(shí),采用的模型為邏輯回歸模型(LR)? 當(dāng)bi ∈{0,1,2,···},Φ(t)=exp(t)時(shí),采用的模型為泊松回歸模型(PR).有關(guān)更多細(xì)節(jié)和應(yīng)用程序,請(qǐng)參閱[24].值得注意的是,為了使數(shù)據(jù)比較集中,可以對(duì)全部ai進(jìn)行等倍縮放處理,使得‖ai‖2≤0.5,bi的值保持不變.為了減少符號(hào)的濫用,在不影響理解的情況下,預(yù)處理后的數(shù)據(jù)依然記為.容易驗(yàn)證F的梯度和Hessian 矩陣分別為

在SSN-Lissa 算法的收斂性證明中需要問(wèn)題(1.1)中函數(shù)滿(mǎn)足條件假設(shè)H1,表A1 說(shuō)明嶺回歸模型、邏輯回歸模型滿(mǎn)足假設(shè)H1.

表A1 假設(shè)H1 中mi 和Mi

引理5 中的|S|依賴(lài)于G(x(k)),表A2 給出了G(x)的一些估計(jì).從表A2 可以看到,每次估計(jì)G(x(k))只需要計(jì)算‖x(k)‖.

表A2 假設(shè)H2 中G(x)的估計(jì)