秦傳東 楊旭

摘 要：為了更好地應(yīng)對當(dāng)今時(shí)代的大規(guī)模高維稀疏數(shù)據(jù)集，融合BB方法、小批量算法與隨機(jī)方差縮減梯度法（SVRG）優(yōu)勢，提出一種帶有隨機(jī)改進(jìn)BarzilaiBorwein步長的小批量稀疏隨機(jī)方差縮減梯度法（MSSVRGR2BB）。首先，在SVRG外循環(huán)中全梯度計(jì)算的基礎(chǔ)上加入L1范數(shù)次梯度設(shè)計(jì)出一種稀疏近似梯度用于內(nèi)循環(huán)，得到一種稀疏的SVRG算法（SSVRG）。在此基礎(chǔ)上，在小批量的稀疏隨機(jī)方差縮減梯度法中使用隨機(jī)選取的改進(jìn)BB方法自動計(jì)算、更新步長，解決了小批量算法的步長選取問題，拓展得到MSSVRGR2BB算法。數(shù)值實(shí)驗(yàn)表明，在求解大規(guī)模高維稀疏數(shù)據(jù)的線性支持向量機(jī)（SVM）問題時(shí)，MSSVRGR2BB算法不僅可以減小運(yùn)算成本、更快達(dá)到收斂上界，同時(shí)能達(dá)到與其他先進(jìn)的小批量算法相同的優(yōu)化水平，并且對于不同的初始參數(shù)選取表現(xiàn)穩(wěn)定且良好。

關(guān)鍵詞：隨機(jī)梯度下降法； 小批量算法； BarzilaiBorwein方法； 方差縮減； 凸優(yōu)化

中圖分類號：TP183?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號：1001-3695（2023）12-020-3655-05

doi：10.19734/j.issn.1001-3695.2023.04.0177

Minibatch sparse stochastic variance reduced gradient method with randomly improved BarzilaiBorwein steps

Abstract：In order to better cope with largescale highdimensional sparse data sets in todays era， this paper combined the advantages of BB method， minibatch algorithm and stochastic variance reduced gradient（SVRG）， and proposed a minibatch sparse stochastic variance reduced gradient method （MSSVRGR2BB） with randomly improved BarzilaiBorwein step size. Firstly， on the basis of calculating the total gradient in the outer loop of SVRG， this paper added the subgradient of L1 norm， designed a sparse approximate gradient for the inner loop of SVRG， and obtained a sparse SVRG algorithm （SSVRG）. On this basis， it proposed to use the improved BB method of random selection to automatically calculate and update the step size in the minibatch sparse stochastic variance reduced gradient method， which solved the step size selection problem of the minibatch algorithm， and expanded the MSSVRGR2BB algorithm. Numerical experiments show that MSSVRGR2BB algorithm can not only reduce the operation cost and reach the convergence upper bound faster， but also achieve the same optimization level of other advanced smallbatch algorithms， and perform stably and well for different initial parameter selection.

Key words：stochastic gradient descent; small batch algorithm; BarzilaiBorwein method; variance reduction; convex optimization

0 引言

近年來，數(shù)據(jù)的種類和數(shù)量都在迅速增長。在數(shù)據(jù)集規(guī)模不斷膨脹的新環(huán)境下，好的訓(xùn)練方法要求在保證數(shù)據(jù)分類的準(zhǔn)確率的同時(shí)降低操作成本和運(yùn)算成本。在過去的研究和實(shí)踐中，隨機(jī)優(yōu)化被廣泛應(yīng)用于解決這類問題，同時(shí)小批量算法也在處理大規(guī)模數(shù)據(jù)訓(xùn)練時(shí)展現(xiàn)出了極高的效率。

在機(jī)器學(xué)習(xí)中，隨機(jī)梯度下降法（SGD）是最流行和實(shí)用的方法之一。傳統(tǒng)的SGD方法在每次迭代中通過計(jì)算一個隨機(jī)例子的經(jīng)驗(yàn)風(fēng)險(xiǎn)函數(shù)的梯度來迭代更新，這樣的做法顯著降低了每次迭代計(jì)算的成本，但同時(shí)引入了相當(dāng)大的隨機(jī)噪聲。最明顯的表現(xiàn)是梯度的隨機(jī)估計(jì)有一個不消失的方差［1，2］。針對如何處理隨機(jī)噪聲問題的研究主要分為使用逐漸減小的步長［1～5］和使用小批量算法［6～9］兩種方向，然而這兩種方法對隨機(jī)估計(jì)方差的減少都要付出代價(jià)：逐步減小的步長常常會導(dǎo)致在最終極限附近時(shí)收斂速度緩慢，小批量算法則需要更多的迭代計(jì)算。因此，諸多學(xué)者圍繞如何更好地將這兩種方法結(jié)合展開了研究，并將自動計(jì)算步長的BarzilaiBorwein方法引入到隨機(jī)優(yōu)化和小批量算法中［10～16］。Sopya等人［11］將BB方法與SGD算法合并來訓(xùn)練線性支持向量機(jī)。在此基礎(chǔ)上，Tan等人［13］提出了對于強(qiáng)凸目標(biāo)函數(shù)具有線性收斂性的SVRGBB算法。Yang等人［14］使用隨機(jī)的BB方法在mS2GD算法中自動計(jì)算步長。周曉君等人［15］提出使用改進(jìn)的 BB方法計(jì)算小批量稀疏隨機(jī)方差縮減梯度法的步長，求解大規(guī)模高維稀疏數(shù)據(jù)的線性SVM問題。Mania等人［16］提出了一種更為高效的異步稀疏的SVRG變體。

受到上述研究的啟發(fā)，為了更好地應(yīng)對當(dāng)今時(shí)代數(shù)據(jù)集呈現(xiàn)出的大規(guī)模、高維度、稀疏性的特點(diǎn)，降低隨機(jī)估計(jì)帶來的噪聲影響，本文遵循結(jié)合BB方法、小批量算法與隨機(jī)方差縮減梯度法，融合現(xiàn)有方法優(yōu)勢的改進(jìn)趨勢，提出一種帶有隨機(jī)改進(jìn)BarzilaiBorwein步長的小批量稀疏隨機(jī)方差縮減梯度法。首先，在SVRG內(nèi)循環(huán)梯度的計(jì)算中使用加入L1范數(shù)的稀疏近似梯度，以克服外循環(huán)中的全梯度計(jì)算使算法變得稠密的缺陷，得到一種稀疏的SVRG算法（SSVRG）。在此基礎(chǔ)上，為了解決小批量算法的步長選取問題，提出在小批量的稀疏隨機(jī)方差縮減梯度法中使用隨機(jī)選取的改進(jìn)BB方法自動計(jì)算、更新步長，拓展得到MSSVRGR2BB算法。MSSVRGR2BB算法實(shí)現(xiàn)了對大規(guī)模稀疏數(shù)據(jù)集快速、有效的處理，不僅有效克服了對初始參數(shù)選取敏感的問題，并且可以在更小的計(jì)算成本下更快達(dá)到收斂上界。

1 相關(guān)背景知識

1.1 SGD和SVRG方法

在機(jī)器學(xué)習(xí)中，為了使有限訓(xùn)練集樣本上的代價(jià)函數(shù)和最小化，通常將問題表示為如下優(yōu)化問題：

當(dāng)所研究的fi和F（w）都具有Lipschitz連續(xù)導(dǎo)數(shù)且都是強(qiáng)凸的問題時(shí)，隨機(jī)梯度下降法（SGD）及其變體一直是求解式（1）的主要方法。在SGD的第t次迭代中，從{1，2，…，n}中選取一個隨機(jī)的訓(xùn)練樣本it，使wt按照式（2）更新迭代：

wt+1=wt－ηtfit（wt）（2）

其中：fit（wt）表示第it－th分量函數(shù)在wt處的梯度，ηt>0是步長（即學(xué)習(xí)速率）。在式（2）中，通常假設(shè)fit是對F的無偏估計(jì)，即

E[fit（wt）|wt]=F（wt）（3）

接下來，使用這種新的隨機(jī)梯度vt進(jìn)行更新，更新規(guī)則為

wt+1=wt－ηtvt（5）

1.2 SGD法求解SVM優(yōu)化問題

給定訓(xùn)練數(shù)據(jù){（xi，yi），i=1，…，n}，其中每個點(diǎn)xi∈Euclid Math TwoRApd是特征向量；yi∈{+1，－1}是其對應(yīng)的類標(biāo)簽，當(dāng)yi=+1時(shí)，稱其為正例，當(dāng)yi=－1時(shí)，稱其為負(fù)例。在本文討論的線性SVM問題中，通常假設(shè)訓(xùn)練數(shù)據(jù)集是線性可分的，即存在超平面能夠完全正確地將正、負(fù)例劃分到超平面的兩側(cè)。SVM原始優(yōu)化問題為

其中：ξi為松弛變量;C為懲罰因子。最終的分類決策函數(shù)為

優(yōu)化問題式（6）等價(jià)于

SVM使用合頁損失函數(shù)來測量預(yù)測數(shù)據(jù)與真實(shí)數(shù)據(jù)的相似度，常見的合頁損失函數(shù)有

一次合頁損失函數(shù)：L（y（wTx））=[1－y（wTx）]+

二次合頁損失函數(shù)：L（y（wTx））=（[1－y（wTx）]+）2

其中：

即當(dāng)樣本（xi，yi）分類正確且函數(shù)間隔yi（wTxi） 大于1時(shí)損失為0，否則損失為1－yi（wTxi）。

光滑的二次合頁函數(shù)損失更加適合優(yōu)化，但更容易受到數(shù)據(jù)中異常值的干擾。因此本文在非光滑的一次合頁損失函數(shù)的基礎(chǔ)上使用Nesterov光滑策略［18］，得到其光滑近似函數(shù)為

展開為

使用SGD求解SVM問題時(shí)，有

此時(shí)，可以得到SGD求解SVM問題的迭代公式：

wt+1=wt－ηtfit（wt）=wt－ηt（ptxt+λwt）（15）

2 一種稀疏的SVRG

觀察圖1可以發(fā)現(xiàn)，面對稀疏問題時(shí)，經(jīng)L1范數(shù)懲罰項(xiàng)約束后的菱形的解空間與損失函數(shù)的交點(diǎn)更容易落在坐標(biāo)軸上，故而可以得到稀疏解。而作為誘導(dǎo)稀疏性的凸函數(shù)，L1范數(shù)懲罰項(xiàng)是不可微的。針對這個問題，諸多學(xué)者提出了專門的解決方法［19～22］。本文選擇在L1范數(shù)次梯度的基礎(chǔ)上設(shè)計(jì)一種類次梯度，將其代入到SVRG算法內(nèi)循環(huán)的梯度更新之中。

首先L1范數(shù)不可微，但是存在次梯度如下：

其中：sign（x）表示為

在此基礎(chǔ)上，本文提出一種L1范數(shù)的類次梯度，令

將稀疏近似梯度Gt代入到式（4）中，得到稀疏SVRG算法的參數(shù)更新公式和算法：

算法1 稀疏的SVRG算法（SSVRG）

3 帶有隨機(jī)改進(jìn)BB步長的小批量稀疏SVRG算法

無論使用逐漸減小的步長還是使用小批量算法來降低方差都會產(chǎn)生一定的副作用，所以如何更好地將兩種方法結(jié)合成為目前隨機(jī)優(yōu)化方法的一個主要研究方向。

3.1 小批量的SVRG方法

在標(biāo)準(zhǔn)的小批量SGD方法中，首先需要隨機(jī)選取出大小為b的小批量S1{1，2，…，n}，接下來在每個小批量之中隨機(jī)更新參數(shù)w：

其中：ηt是第t次迭代的步長；fi（wt）表示第i個目標(biāo)函數(shù)在wt處的梯度。顯然，當(dāng)批量大小為1時(shí)，式（22）即式（2），小批量的SGD方法退化為普通的SGD方法。

算法2 小批量的SVRG算法（MSVRG）

3.2 隨機(jī)的改進(jìn)BarzilaiBorwein步長

Barzilai等人［23］于1988年提出一種可以自適應(yīng)更新步長的方法。

在無約束極小化問題minw f（w）中，函數(shù)f通常是可微的，典型的擬牛頓法可以通過如下迭代對其求解：

wt+1=wt－B－1tf（wt）（24）

Bt是f在wt處Hessian矩陣的逼近，并且滿足擬牛頓方程Btst=vt。其中：st－1=wt－wt－1； vt－1=p（wt）－p（wt－1）。由此，提出了兩種BB步長：

可以看到，BB方法計(jì)算得到的步長無須任何初始的參數(shù)。Raydan［24］和Dai［25］已經(jīng)分別證明了BB 算法的全局收斂性和R線性收斂性。在后續(xù)研究中，Dai［25］在大量的數(shù)值實(shí)驗(yàn)中提出一種新的譜梯度法，令步長為ηB1t和ηB2t的凸組合來代替直接選取ηB1t或ηB2t，即

η2BBt=γηBB1t+（1－γ）ηBB2t γ∈[0，1]（26）

文獻(xiàn)［26］中詳細(xì)地討論了關(guān)于γ取值的細(xì)節(jié)，本文在數(shù)值實(shí)驗(yàn)中也進(jìn)行了對比。

Bordes［10］和Byrd等人［12］提出使用批量樣品來近似估計(jì)Hessian矩陣。受到該思想的啟發(fā)，本文提出使用隨機(jī)樣本來計(jì)算隨機(jī)階段的估計(jì)步長，而不是使用全梯度來計(jì)算步長。得出隨機(jī)的改進(jìn)BB步長（R2BB），其迭代公式如下所示。

其中：wt是在每次隨機(jī)迭代中得到的；小批量S的大小為b； FS（wt）和FS（wt－1）的定義與式（23）類似，即它們在每次迭代中選擇b個樣本進(jìn)行更新。通過比較可以發(fā)現(xiàn)，在計(jì)算步長時(shí)，R2BB方法通過選取ηB1t和ηB2t凸組合達(dá)到更優(yōu)的步長選擇；采用批量樣本進(jìn)行更新，在降低了計(jì)算成本的同時(shí)保留了準(zhǔn)牛頓性質(zhì)。同時(shí)為了保證本文方法的收斂性，R2BB方法的步長必須除以批量樣本大小b。

將上述R2BB方法與小批量的稀疏SVRG算法結(jié)合，得到如下算法：

算法3 帶有隨機(jī)選取的改進(jìn)BB步長的小批量稀疏SVRG算法（MSSVRGR2BB）

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

本章通過數(shù)值實(shí)驗(yàn)對所提出的MSSVRGR2BB算法的有效性進(jìn)行驗(yàn)證。實(shí)驗(yàn)選取的數(shù)據(jù)集來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫（https：//archive.ics.uci.edu/ml/index.php），并按照文獻(xiàn)［9］選取正則化參數(shù)的精度。數(shù)據(jù)集信息如表1所示。

傳統(tǒng)的SGD方差對初始步長η0的選取十分敏感，同時(shí)，在MSSVRGR2BB算法中兩個小批量的大小b1、b2和BB步長凸組合的比例γ也對收斂速度起著重要作用。為了驗(yàn)證本文算法的性能，設(shè)計(jì)了對不同算法收斂水平、預(yù)測精度，以及MSSVRGR2BB算法對步長凸組合比例γ，初始步長η0和b1、b2大小選取敏感性的對比實(shí)驗(yàn)。參考文獻(xiàn)［9］，基本參數(shù)選取m=2n， max epoch=50，其他參數(shù)在對比實(shí)驗(yàn)中分別具體給出。

4.1 不同凸組合比例γ取值的對比

由式（26）可知，改進(jìn)的BB步長中凸組合比例γ∈[0，1]，并且當(dāng)γ越接近1時(shí)，凸組合ηR2BBt的步長更接近ηRBB1t，反之越接近0時(shí)，更接近ηRBB2t。為了驗(yàn)證不同大小的γ是否會對MSSVRGR2BB算法的性能造成影響，本文首先分別選取不同的γ進(jìn)行了對比實(shí)驗(yàn)。為了排除其他參數(shù)造成的影響，設(shè)置初始步長η0=0.1，b1=b2=10。

圖2展示了在上述參數(shù)設(shè)置下，分別在數(shù)據(jù)集ijcnn1和rcv1中使用固定ηBB1t、ηBB2t步長的MSVRG算法和不同比例γ的MSSVRGR2BB算法求解線性SVM問題的性能對比。其中不同比例γ的MSSVRGR2BB算法由實(shí)線表示，使用ηBB1t、ηBB2t步長的MSVRG算法由虛線表示。

可以看出，在數(shù)據(jù)集ijcnn1中，γ越大，預(yù)測精度和收斂速度表現(xiàn)得越好。當(dāng)γ=0.9時(shí)，雖然收斂速度不及步長為ηBB1t的MSVRG算法，但是可以達(dá)到幾乎相同的預(yù)測精度；而對數(shù)據(jù)集rcv1，ηBB1t或ηBB2t都不是最佳選擇，γ=0.7或者γ=0.9的改進(jìn)BB步長在達(dá)到更好預(yù)測效果的同時(shí)收斂速度更快。文獻(xiàn)［26］中詳細(xì)討論了如何選取γ。為了兼顧預(yù)測精度和收斂速度，本文在后續(xù)實(shí)驗(yàn)中默認(rèn)選取γ=0.5。

4.2 不同批量b1、b2和初始步長η0取值的對比

小批處理算法的性能會因批量大小和步長序列的選擇而發(fā)生很大的變化。首先本文比較了使用固定步長的MSVRG和MSSVRGR2BB方法。

在不同的數(shù)據(jù)集測試對比結(jié)果如圖3、4所示。虛線對應(yīng)不同固定步長η的MSVRG。實(shí)線代表初始步長η0=0.1、具有不同的批量大小b1和b2的MSSVRGR2BB算法。各參數(shù)的不同值在子圖的圖例中給出。

如圖3、4所示，對比實(shí)驗(yàn)中MSSVRGR2BB算法的b1在集合{10，30}中改變，b2在集合{20，30，50}中改變。從圖3、4中可以看出，MSSVRGR2BB始終可以達(dá)到與MSVRG相同的次優(yōu)水平，甚至可以達(dá)到比MSVRG在步長優(yōu)化最佳時(shí)更好的性能。b1、b2的比例對MSSVRGR2BB的性能有一定的影響，但總體而言MSSVRGR2BB方法對參數(shù)b1、b2的選取不敏感。

如3.2節(jié)所述，BB方法對初始步長η0不敏感。為了證明MSSVRGR2BB算法具備該能力，本文在ijcnn1和rcv1兩個數(shù)據(jù)集上為MSSVRGR2BB選擇了三種不同的初始步長η0=0.1，1，10，并為所有數(shù)據(jù)集設(shè)置b1=10和b2=30，在此參數(shù)基礎(chǔ)上進(jìn)行測試，并將結(jié)果繪制在圖5中。從圖5可以看出，MSSVRGR2BB的性能基本不受初始步長η0的影響。

4.3 與其他算法的對比

為了驗(yàn)證改進(jìn)算法的優(yōu)勢，本文與以下算法進(jìn)行了性能對比：

a）SVRG：Johnson等人［17］于2013年提出的一種可以明顯降低方差的SGD變體。

b）MSVRGBB1：帶有BB步長的小批量SVRG。

c）MBSGDB：選取最佳固定步長的小批量隨機(jī)梯度下降法。

d）SAGBB：Tan等人［13］于2016年提出的帶有BB步長的隨機(jī)平均梯度算法。

e）mS2GDBB：Yang等人［14］于2018年提出的利用改進(jìn)的BB方法自動計(jì)算小批量半隨機(jī)梯度下降（mS2GD）的步長。

從圖6、7和表2、3可以看出，MSSVRGR2BB算法達(dá)到的次最優(yōu)水平優(yōu)于一眾算法，與先進(jìn)的mS2GDBB算法十分接近。面對典型的高維稀疏數(shù)據(jù)集，在保證預(yù)測精度的前提下，具有稀疏更新技術(shù)的MSSVRGR2BB算法也有著明顯快于其他算法的收斂速度。

5 結(jié)束語

為了更好地應(yīng)對大規(guī)模、高維度、稀疏性的數(shù)據(jù)集，本文對隨機(jī)方差縮減梯度法進(jìn)行了稀疏化改進(jìn)，并結(jié)合BB方法、小批量算法提出了一種新算法。在傳統(tǒng)SVRG內(nèi)循環(huán)中加入的L1范數(shù)稀疏近似梯度解決了外循環(huán)中全梯度計(jì)算使算法變得稠密的缺陷，得到了稀疏的SVRG算法。在此基礎(chǔ)上，提出了帶有隨機(jī)改進(jìn)BarzilaiBorwein步長的小批量稀疏隨機(jī)方差縮

減方法，不僅進(jìn)一步降低了噪聲，并且解決了小批量算法的步

長選取問題。最終的數(shù)值實(shí)驗(yàn)結(jié)果表明，MSSVRGR2BB具有比其他方法更好的表現(xiàn)。

傳統(tǒng)的BB方法能夠更好地保證收斂性，但每次迭代所需的運(yùn)算成本遠(yuǎn)大于直接運(yùn)用隨機(jī)優(yōu)化，數(shù)值實(shí)驗(yàn)速度比較慢。隨機(jī)選取小批量樣本更新的BB步長顯然具有更好的有效性和可擴(kuò)展性。BB步長的凸組合一定程度上兼顧了兩種BB步長的優(yōu)勢，但固定的凸組合比例γ在迭代中后期的表現(xiàn)并不穩(wěn)定。在后續(xù)的研究中如果可以在迭代過程中動態(tài)地更新凸組合比例γ，可以有效克服這一缺陷。此外，MSSVRGR2BB對初始步長不敏感，但其中涉及到兩個小批量的選取問題，可以引入智能算法來更高效地尋找最優(yōu)參數(shù)。

參考文獻(xiàn)：

[1]Zhang Tong. Solving large scale linear prediction problems using stochastic gradient descent algorithms［C］//Proc of the 21st International Conference on Machine Learning.New York：ACM Press，2004：116.

［2]Shamir O， Zhang Tong. Stochastic gradient descent for nonsmooth optimization： convergence results and optimal averaging schemes［C］//Proc of the 30th International Conference on Machine Learning.［S.l.］：JMLR.org，2013：71-79.

［3]Luo Zhiquan. On the convergence of the LMS algorithm with adaptive learning rate for linear feedforward networks［J］.Neural Computation，1991，3（2）：226-245.

［4]Solodov M V. Incremental gradient algorithms with stepsizes bounded away from zero［J］.Computational Optimization and Applications，1998，11：23-35.

［5]Nemirovski A， Juditsky A， Lan G， et al. Robust stochastic approximation approach to stochastic programming［J］.SIAM Journal on Optimization，2009，19（4）：1574-1609.

［6]ShalevShwartz S， Singer Y， Srebro N. Pegasos： primal estimated subgradient solver for SVM［C］//Proc of the 24th International Conference on Machine Learning.New York：ACM Press，2007：807-814.

［7]Cotter A， Shamir O， Srebro N， et al. Better minibatch algorithms via accelerated gradient methods［EB/OL］.（2011-06-22）.https：//arxiv.org/abs/1106.4574.

［8]Dekel O， GiladBachrach R， Shamir O， et al. Optimal distributed online prediction using minibatches［J］.Journal of Machine Learning Research，2012，13：165202.

［9]Konecˇn J， Liu Jie， Richtárik P， et al. Minibatch semistochastic gradient descent in the proximal setting［J］.IEEE Journal of Selected Topics in Signal Processing，2015，10（2）：242-255.

［10]Bordes A， Bottou L， Gallinari P. SGDQN：careful quasiNewton stochastic gradient descent［J］.Journal of Machine Learning Research，2009，10：1737-1754.

［11]Sopya K， Drozda P. Stochastic gradient descent with BarzilaiBorwein update step for SVM［J］.Information Sciences，2015，316：218-233.

［12]Byrd R H， Hansen S L， Nocedal J， et al. A stochastic quasiNewton method for largescale optimization［J］.SIAM Journal on Optimization，2016，26（2）：1008-1031.

［13]Tan Conghui， Ma Shiqian， Dai Yuhong， et al. BarzilaiBorwein step size for stochastic gradient descent［C］//Proc of the 30th International Conference on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2016：685-693.

［14]Yang Zhuang， Wang Cheng， Zhang Zhemin， et al. Random BarzilaiBorwein step size for minibatch algorithms［J］.Engineering Applications of Artificial Intelligence，2018，72：124-135.

［15]周曉君，于騰騰.求解SVM的稀疏隨機(jī)方差縮減梯度法［J］.計(jì)算機(jī)應(yīng)用研究，2020（S2）：95-97.（Zhou Xiaojun， Yu Tengteng. Sparse random variance reduction gradient method for solving SVM［J］.Application Research of Computers，2020（S2）：95-97.）

［16]Mania H， Pan Xinghao， Papailiopoulos D， et al. Perturbed iterate analysis for asynchronous stochastic optimization［J］.SIAM Journal on Optimization，2017，27（4）：2202-2229.

［17]Johnson R， Zhang Tong. Accelerating stochastic gradient descent using predictive variance reduction［C］//Proc of the 26th International Conference on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2013：315-323.

［18]Nesterov Y. Smooth minimization of nonsmooth functions［J］.Mathematical Programming，2005，103：127-152.

［19]Genkin A， Lewis D D， Madigan D. Largescale Bayesian logistic regression for text categorization［J］.Technometrics，2007，49（3）：291-304.

［20]Koh K， Kim S J， Boyd S. An interiorpoint method for largescale l1regularized logistic regression［J］.Journal of Machine Learning Research，2007，8：1519-1555.

［21]Andrew G， Gao Jianfeng. Scalable training of l1regularized loglinear models［C］//Proc of the 24th International Conference on Machine Learning.New York：ACM Press，2007：33-40.

［22]Liu Jun， Chen Jianhui， Ye Jieping. Largescale sparse logistic regression［C］//Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2009：547-556.

［23]Barzilai J， Borwein J M. Twopoint step size gradient methods［J］.IMA Journal of Numerical Analysis，1988，8（1）：141-148.

［24]Raydan M. On the Barzilai and Borwein choice of steplength for the gradient method ［J］.IMA Journal of Numerical Analysis，1993，13（3）：321-326.

［25]Dai Yuhong. Alternate step gradient method［J］.Optimization，2003，52（4-5）：395-415.

［26]Dai Yuhong， Huang Yakui， Liu Xinwei. A family of spectral gradient methods for optimization［J］.Computational Optimization and Applications，2019，74：43-65.

［27]周曉君.求解SVM的帶有BarzilaiBorwein步長的隨機(jī)方差縮減梯度法［D］.天津：河北工業(yè)大學(xué)，2020.（Zhou Xiaojun. Stochastic variance reduced gradient methods for SVM with BarzilaiBorwein step sizes［D］.Tianjin：Hebei University of Technology，2020.）