一種抽樣二階隨機算法

王靜 王湘美

(貴州大學數學與統計學院,貴陽,550025)

1 引言

考慮以下優化問題:

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

與一階隨機算法相比,二階隨機算法除了用到一階導數信息還要用到二階導數信息.牛頓法是經典的二階優化算法,它在一定條件下具有二階收斂速度,其迭代公式如下:

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

本文余下部分安排如下:第二節介紹預備知識?第三節給出SSN-Lissa 算法及其收斂性證明?第四節通過數值實驗驗證SSN-Lissa 算法的有效性.

2 預備知識

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

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

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

我們對問題(1.1)中的函數做以下假設.

假設H1fi二階連續可微,且存在0＜mi ≤Mi ≤1,使得

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

注1在本文的算法收斂性分析中,需要假設H1成立.幸運的是,對于很多機器學習問題的模型,例如嶺回歸模型、邏輯回歸模型等,假設H1都是成立的,詳見附錄表3 或參考文獻[9,15,17,18,19,24].

(2.4)表明函數F強凸且?2F的特征值介于γ和K之間.此時優化問題(1.1)的解x*存在、唯一，且滿足

我們稱κ=為問題(1.1)的條件數.

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

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

設A是一個隨機事件,用Pr(A)表示事件A發生的概率.以下引理是關于隨機矩陣范數的概率估計(見[23,Theorem 1.3]).

引理3設Y是d階隨機實對稱矩陣,且滿足E(Y)=0,Pr(‖Y‖≤R)=1.則對于任意t ≥0有

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

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

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

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

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

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

我們稱g(x)為?F(x)的一個隨機抽樣.

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

假設H2存在函數G:Rd →R 使得對任意的i=1,2,···,n，有

引理5設H2成立.若對任意的ε2,δ2∈(0,1),|S|滿足

則有

注2在假設H2中，需要事先確定G(x).幸運的是,在很多機器學習問題中，G(x)常?？梢允孪冉o出,詳見附錄表4.

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

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

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

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

我們分別按以下方式選取參數ε2和步長αk（k=1,2,···）:

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

表1 確定性算法、隨機算法一次迭代的計算復雜度對比

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

4 數值實驗

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

表2 實驗參數的設置

由定理1 我們知道SSN-Lissa 算法是概率意義下的下降算法,故我們在運行算法時采用如下更新方式:當F(x(k+1))＜F(x(k))時我們更新迭代點,當時則不更新迭代點.算法隨機產生初始迭代點,通過SSN-Lissa 算法對數據進行20 次訓練,比較當選擇不同ε1時SSN-Lissa 算法的性能(圖1).

圖1 選擇不同ε1,對改進SSN-Lissa 算法性能進行比較

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

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

對比圖2 中的三種算法,SSN-lissa 算法每步迭代的時間成本最低.這是因為SSN-Lissa 算法隨機計算部分函數梯度而Lissa 需要計算所有函數梯度,并且SSN-Lissa 算法直接估計Hessian 矩陣的逆,比SSN 算法(先估計Hessian 矩陣然后在計算逆)時間成本低.通過對比不同初始點的選取對三種算法的影響,發現當初始點離最優點較遠時(中間圖)SSN-Lissa 的函數值下降最快,其次是SSN.這是因為SSN-Lissa 算法和SSN 算法都可以達到全局線性收斂,而Lissa 算法僅在初始點接近最優點時達到線性收斂.當初始點在最優點附近時(右邊圖)Lissa 算法函數值在第一步有很快的下降,之后趨于平穩,而SSN-Lissa 算法雖然剛開始沒有Lissa 算法下降快,但是迭代6 次之后就達到了Lissa 算法的精度.

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

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

附錄A

考慮帶正則化的高斯先驗的最大后驗問題(詳見[19]),其目標函數為:

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

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

表A1 假設H1 中mi 和Mi

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

表A2 假設H2 中G(x)的估計