楊一名，王福勝

(太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

0 引言

在統(tǒng)計(jì)機(jī)器學(xué)習(xí)[1]和信號處理[2]等領(lǐng)域中，通常考慮如下形式的優(yōu)化問題：

其中n代表訓(xùn)練樣本數(shù)目，d代表變量維度，本文假設(shè)每一個fi均是一階連續(xù)可微的.求解上述問題的傳統(tǒng)方法是梯度下降算法[3]，但是當(dāng)n的取值較大時，該方法在計(jì)算量上很難容忍甚至不能執(zhí)行.針對這一缺陷，基于Robbins和Monro[4]提出的隨機(jī)近似思想，研究者們提出了隨機(jī)梯度下降算法(SGD)[5]，SGD算法的特點(diǎn)是每次迭代只選取一個或部分樣本確定迭代方向，選取一個樣本時的迭代公式如下：

ωk+1=ωk-ηk?fik(ωk)，

其中，?fik(ωk)表示第ik個分量函數(shù)在ωk處的梯度，ηk>0表示步長.目前，通過引入不同技術(shù)改進(jìn)SGD性能的工作被廣泛應(yīng)用[6-8].事實(shí)上，SGD算法本身的收斂性取決于隨機(jī)方向與真實(shí)梯度的方差，采用梯度聚合的方式可以有效縮減方差.經(jīng)典的梯度聚合類算法通過重新使用或修改之前的梯度縮減方差，常見的有隨機(jī)方差縮減梯度算法(SVRG)[9]，隨機(jī)對偶坐標(biāo)上升算法(SDCA)[10]，半隨機(jī)梯度下降算法(S2GD)[11]，小批量半隨機(jī)梯度下降算法(mS2GD)[12]，隨機(jī)遞歸梯度算法(SARAH)[13]，隨機(jī)平均梯度算法(SAG)[14]和SAGA[15]等.

對于方差縮減類算法而言，步長是影響算法性能的關(guān)鍵因素，傳統(tǒng)的方法是根據(jù)人為的經(jīng)驗(yàn)選擇符合某種規(guī)律的遞減步長或者較小的固定步長，并且滿足：

AdaGrad[16]和Adam[17]等采用對角修正技術(shù)為每個分量自適應(yīng)地選取步長.當(dāng)前，由于BB步長[18]特有的性質(zhì)，許多學(xué)者創(chuàng)新性地提出將方差縮減方法與BB步長相結(jié)合以提高算法的收斂速度.受啟發(fā)于SGD-BB[19]和STSG[20]算法，本文考慮將復(fù)合BB步長(CABB)[21]與隨機(jī)方差縮減梯度算法(SVRG)[9]結(jié)合，提出SVRG-CABB.

1 隨機(jī)方差縮減梯度算法

構(gòu)造新算法之前，本節(jié)首先回顧隨機(jī)方差縮減梯度算法(SVRG)[9].事實(shí)上，SVRG包括兩層循環(huán)，通常在外循環(huán)中計(jì)算全梯度，而在內(nèi)循環(huán)中計(jì)算方差縮減的隨機(jī)梯度，在迭代過程中需要隨機(jī)選取下標(biāo)it∈{1,…,n}.從總體上看，該算法執(zhí)行最關(guān)鍵步驟是對于隨機(jī)梯度的更新，即：

其迭代更新規(guī)則為：

ωt+1=ωt-ηkvt.

可以發(fā)現(xiàn)SVRG算法中迭代方向vt是真實(shí)梯度的無偏估計(jì)，且算法在迭代過程中的方差在逐漸減小，以下給出SVRG算法的基本框架：

第4步：如果t>m，轉(zhuǎn)第5步；否則轉(zhuǎn)第3步；

第6步：令k:=k+1，如果k>T，停止；否則轉(zhuǎn)第2步.

2 BB步長

第3步：如果k>0，計(jì)算復(fù)合BB步長：

第6步：令k:=k+1，如果k>T，停止；否則轉(zhuǎn)第2步.

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

本節(jié)將SVRG-CABB算法應(yīng)用于求解帶有l(wèi)2正則化項(xiàng)的邏輯回歸模型，并給出實(shí)驗(yàn)結(jié)果驗(yàn)證算法的有效性，模型表示如下：

表1 數(shù)據(jù)集信息

實(shí)驗(yàn)包括四個部分：首先，對比了SVRG-CABB算法與SVRG算法的收斂速度，驗(yàn)證了SVRG-CABB的有效性；其次，對比了SVRG-CABB算法與SVRG算法的分類準(zhǔn)確率；接著，測試了SVRG-CABB算法關(guān)于不同初始步長的步長變化趨勢；最后，對比了SVRG-CABB算法和STSG[20]算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)時參數(shù)τ對算法性能的影響.所有的實(shí)驗(yàn)結(jié)果如圖1到圖4所示.

圖1 SVRG-CABB和帶有固定步長的SVRG算法殘差對比

圖1對比了SVRG-CABB和SVRG算法的收斂速度，其中x軸代表迭代次數(shù)，y軸代表求解目標(biāo)函數(shù)所得的殘差損失，圖中的虛線和實(shí)線分別對應(yīng)于帶有不同初始步長的SVRG-CABB算法，虛線分別對應(yīng)于帶有固定步長的SVRG算法.四個子圖(a)，(b)，(c)和(d)分別對應(yīng)于兩種算法在數(shù)據(jù)集heart，splice，ijcnn1和a9a上的實(shí)驗(yàn)結(jié)果對比.從圖中可以看出，本文提出的新算法SVRG-CABB收斂速度整體上比帶有固定步長的SVRG算法快，并且當(dāng)選擇不同的初始步長η0時，SVRG-CABB算法的收斂性能不受影響，可以看出使用CABB步長的優(yōu)勢是使得新算法對于步長的選取更加容易.

圖2 SVRG-CABB和固定步長的SVRG算法分類準(zhǔn)確率對比

圖2對比了SVRG-CABB和SVRG算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)的分類準(zhǔn)確率，其中x軸代表迭代次數(shù)，y軸代表求解分類準(zhǔn)確率，圖中虛線和實(shí)線分別對應(yīng)帶有不同初始步長的SVRG-CABB算法，虛線分別對應(yīng)帶有固定步長的SVRG算法.四個子圖(a)，(b)，(c)和(d)分別對應(yīng)兩種算法在數(shù)據(jù)集heart，splice，ijcnn1和a9a上的實(shí)驗(yàn)對比.從圖中可以看出，本文提出的SVRG-CABB算法的分類準(zhǔn)確率明顯高于帶有固定步長的SVRG算法，當(dāng)選擇不同的初始步長η0時，SVRG-CABB算法的分類準(zhǔn)確率并不受影響.在相同條件下，SVRG-CABB算法分類準(zhǔn)確率更加穩(wěn)定且明顯高于帶有固定步長的SVRG算法.

圖3 SVRG-CABB步長變化趨勢

圖3測試了SVRG-CABB算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)時步長的變化趨勢，其中x軸代表迭代次數(shù)，y軸代表步長，圖中虛線和實(shí)線分別對應(yīng)不同的初始步長，虛線分別對應(yīng)不同的固定步長.兩個子圖(a)和(b)分別對應(yīng)于SVRG-CABB算法在數(shù)據(jù)集heart和splice上的測試結(jié)果.從圖中可以看出，本文提出的SVRG-CABB算法的步長最終收斂于最優(yōu)步長的鄰域.這說明選取不同的初始步長，對算法收斂性能影響不大.

圖4 不同參數(shù)值τ下SVRG-CABB和STSG算法性能對比

圖4對比了SVRG-CABB算法和STSG算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)時參數(shù)τ對算法性能的影響，其中x軸代表迭代次數(shù)，y軸代表殘差損失，圖中的實(shí)線分別對應(yīng)于τ∈(0,1)的SVRG-CABB算法，虛線分別對應(yīng)于τ∈(0,1)的STSG算法.兩個子圖(a)和(b)分別對應(yīng)于SVRG-CABB算法在數(shù)據(jù)集heart和a9a上的測試結(jié)果.從圖中可以看出，本文提出的SVRG-CABB和STSG的算法性能雖然均受參數(shù)τ值的影響，并且隨著τ值的增加算法性能總體得到提升，但是SVRG-CABB算法的收斂性能最終優(yōu)于選擇相同參數(shù)τ的STSG算法.

4 結(jié)論

本文將隨機(jī)方差縮減梯度算法(SVRG)與改進(jìn)的復(fù)合BB步長(CABB)有機(jī)結(jié)合，提出了一種新的SVRG-CABB算法.從實(shí)驗(yàn)結(jié)果分析來看，新算法在求解問題的過程中可以動態(tài)調(diào)節(jié)步長的大小，相比于已有的使用固定步長的SVRG算法以及已有的STSG算法，新算法的收斂速度更快，并且不受初始步長選取的影響.