基于Polyak步長的方差縮減算法

李蝶

摘? 要：方差縮減算法的主要問題之一是如何選取一個合適的步長。在實踐中，手動調(diào)整一個最佳的固定步長是很耗時的，所以該文提出將Polyak步長用于隨機(jī)方差縮減梯度算法（SVRG），得到了一種新的SVRG-Polyak算法。對于光滑強(qiáng)凸的目標(biāo)函數(shù)我們證明了SVRG-Polyak算法的線性收斂性。數(shù)值實驗對比了SVRG-Polyak、SVRG和帶有BB步長的SVRG（SVRG-BB）3種算法，結(jié)果表明SVRG-Polyak算法的有效性。

關(guān)鍵詞：Polyak步長? 方差縮減? 強(qiáng)凸? 線性收斂

中圖分類號：O1? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A文章編號：1672-3791（2021）06（a）-0174-04

Polyak Step Size for Variance Reduction Algorithm

LI Die

（college of science， Hebei University of Technology， Tianjin， 300401? China）

Abstract：One of the main problems of the variance reduction algorithm is how to choose an appropriate step size. In practice， it is time-consuming to manually adjust an optimal fixed step size， so this paper proposes to use Polyak step size for the random variance reduction gradient algorithm （SVRG）， and a new SVRG-Polyak algorithm is obtained. For the smooth and strongly convex objective function， we prove the linear convergence of the SVRG-Polyak algorithm. Numerical experiments compared SVRG-Polyak， SVRG and SVRG with BB step size （SVRG-BB） three algorithms， and the results show the effectiveness of SVRG-Polyak algorithm.

Key Words：Polyak step size; variance reduction; strong convexity; linear convergence

機(jī)器學(xué)習(xí)具有十分廣泛的作用和研究價值，優(yōu)化是機(jī)器學(xué)習(xí)研究的關(guān)鍵一步。幾乎所有機(jī)器學(xué)習(xí)問題的模型求解都依賴于優(yōu)化算法。因此，設(shè)計快速有效的優(yōu)化算法在機(jī)器學(xué)習(xí)研究中至關(guān)重要。在機(jī)器學(xué)習(xí)中，我們經(jīng)常遇到以下優(yōu)化問題，設(shè)為從到的向量函數(shù)序列。

（1）

例如，給定一個由n個獨立且分布均勻的樣本組成的訓(xùn)練集，其中是第i個樣本的輸入特征向量，并且是第i個樣本的標(biāo)簽（或目標(biāo)），此時問題也稱為監(jiān)督學(xué)習(xí)。如果設(shè)置，則可以獲得最小二乘回歸;如果設(shè)置則將獲得正則邏輯回歸。

為了解決優(yōu)化問題（1），一種流行的方法是梯度下降算法（GD），它可以通過以下更新規(guī)則來描述，對于…時，有

（2）

式中，是第t次迭代的學(xué)習(xí)率，用于調(diào)整參數(shù)更新的幅度。

GD在一階算法中占據(jù)重要地位，但是在實際應(yīng)用中還存在很多問題，需要對其進(jìn)行改進(jìn)。GD的一個主要問題是當(dāng)問題規(guī)模較大時，由于需要計算全部梯度，導(dǎo)致計算量很大。隨機(jī)梯度下降算法（SGD）[1]在一定程度上解決了這個問題。SGD使用隨機(jī)梯度代替全梯度，減少了計算量：由于隨機(jī)梯度的不確定性，可能導(dǎo)致在迭代過程中目標(biāo)函數(shù)值不斷反升，使得算法具備一定的跳出極小點的能力，從而增大算法找到全局最小點的概率。

SGD可以通過以下更新規(guī)則來描述，對于…，我們從{1，2…，n}中隨機(jī)抽取it。

通常假設(shè)，是對的無偏估計，即。

SGD由于算法的隨機(jī)性，產(chǎn)生了方差，導(dǎo)致算法的收斂速度不如梯度下降算法快，因此涌現(xiàn)了大量的方差縮減算法[2-4]。對于光滑和強(qiáng)凸的函數(shù)，Johnson等人提出的隨機(jī)方差縮減梯度法（SVRG）[2]可以達(dá)到與SDCA和SAG[4]算法相同快的收斂率，都可以達(dá)到線性收斂，并且SVRG的線性收斂結(jié)果證明更簡單、具有直觀解釋，而且與SDCA和SAG不同，SVRG無需存儲中間梯度，因此對于一些復(fù)雜問題如結(jié)構(gòu)預(yù)測問題和神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)，此方法更易實現(xiàn)。

SVRG可以通過以下更新規(guī)則來描述，對于…時，有

（4）

其中，是每m次內(nèi)循環(huán)迭代后得到的快照點，是函數(shù)在處的全梯度，且

對于隨機(jī)算法（SGD及其變體）來說，一個重要的問題是如何選取一個合適的步長。對于SGD來說，使用一個固定步長可以確保收斂到解的一個鄰域內(nèi)。確保解收斂到精確最優(yōu)值的一個普遍技術(shù)是使用下降步長。另外，還有一些動態(tài)調(diào)整步長的自適應(yīng)方法[5-6]也很流行。步長的自適應(yīng)選擇使優(yōu)化算法可以根據(jù)優(yōu)化曲線的局部曲率和光滑性快速加速。但是從理論上講，沒有參數(shù)的算法很少。除了對SGD進(jìn)行方差縮減和步長上的改進(jìn)，還有結(jié)合動量的改進(jìn)，例如：結(jié)合Nesterov動量的加速梯度算法（NAG），結(jié)合Katyusha動量的Katyusha算法[7]等。

1? Polyak步長

Polyak在文獻(xiàn)[8]中提出Polyak步長，Polyak步長普遍用于次梯度法。假設(shè)我們要求解以下的無約束優(yōu)化問題：

（5）

式中，f是凸但可能非光滑函數(shù)。假定在xt處的次梯度是可以計算的。次梯度法有如下形式：

式中，r趨于0，r的和是無窮的。滿足上式的例子為：

對于凸函數(shù)，在第t步極小化迭代點與最優(yōu)解的距離的上界：

其中

所以，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 。

值f *使得構(gòu)造不包含任何參數(shù)的次梯度法的如下變體成為可能：

因此，Polyak步長為：

（6）

在這種情況下，步長依賴于的估計。在一些應(yīng)用中，f *的值是已知的（或者為0），該方法可以不用估計直接使用?，F(xiàn)有的隨機(jī)算法中Polyak步長使用的是隨機(jī)梯度或是部分梯度，而該文使用的是全梯度。在隨機(jī)方差縮減梯度算法外層迭代中，已計算出全梯度，所以計算量并沒有增加，相比于其他算法增加了準(zhǔn)確率。

2? 帶有Polyak步長的SVRG

定義1：函數(shù)是強(qiáng)凸的，如果滿足：

（7）

定義2：函數(shù)是光滑的，或者是Lipschitz連續(xù)的，如果滿足以下條件：

（8）

從上述定義可以得到函數(shù)是光滑的，或者是Lipschitz連續(xù)的。

（9）

等價于

（10）

定義3：如果函數(shù)F是光滑且強(qiáng)凸的，則函數(shù) F的Lipschitz常數(shù)L與強(qiáng)凸常數(shù)μ的比為條件數(shù)k，即。

2.1 SVRG-Polyak算法

算法：

輸入：內(nèi)循環(huán)迭代次數(shù)m，初始點;

步0：對…執(zhí)行;

步1：計算一個全梯度;

步2：計算步長;

步3：;

步4：對執(zhí)行;

步5：隨機(jī)選取;

步6：;

步7：結(jié)束內(nèi)層循環(huán);

步8：;

步9：結(jié)束外層循環(huán)。

2.2 收斂性分析

引理1（co-coercivity）[9]：如果是凸函數(shù)并且它的梯度是Lipschitz連續(xù)的，那么就有：

引理2：假定F是強(qiáng)凸且光滑的函數(shù)，那么算法SVRG-Polyak中的步長就滿足下面的不等式：

證明：令（10）中，就有，便得到了ηk的下界。根據(jù)強(qiáng)凸性，

令，就有，便得到了的上界。

定理1：假定是強(qiáng)凸的，是光滑的，令。假定m充分大時得：

那么對于SVRG-Polyak，我們就可以得到期望上的線性收斂：

證明：對SVRG-Polyak的第k個時期，令，那么

第一個不等式是利用兩次得到，第二個不等式是對函數(shù)使用引理1以及利用和的Lipschitz連續(xù)性得到，最后一個等式是利用和得到。下面我們在和的條件下界定與的距離。

其中第三個不等式用的是的強(qiáng)凸性。通過對t遞歸應(yīng)用上面不等式，并結(jié)合和，可以得到：

當(dāng)選取充分大的m時，，算法～SVRG-Polyak～在期望上線性收斂：

推論1[SVRG-BB中推論3.6][10]：在SVRG-I中，如果m和η的選取使得下面的不等式成立：

那么SVRG-I（SVRG算法Option I）在期望上線性收斂：

可以看出，SVRG-Polyak算法也滿足這樣的收斂性。

推論2：定義，可以看出。在SVRG-Polyak中，如果選取m滿足

那么SVRG-Polyak可以實現(xiàn)期望上的線性收斂：

證明：結(jié)合推論1和η以及m的范圍有：

3? 數(shù)值實驗

下面我們給出了該文要用到的問題模型l2-正則的邏輯回歸。

邏輯回歸：

其中，和分別是第i個樣本的特征向量和類標(biāo)簽，是一個權(quán)重參數(shù)。該文中的數(shù)值實驗使用的是w8a數(shù)據(jù)集，它可以從LIBSVM網(wǎng)站上得到。該數(shù)據(jù)集的大小n為49 749，特征維數(shù)d為300。

在該節(jié)，我們針對求解邏輯回歸問題在w8a數(shù)據(jù)集上比較了SVRG-Polyak和SVRG以及SVRG-BB，如圖1所示。對于SVRG，使用的是3種不同的步長，分別為0.02、0.1、0.5;對于SVRG-BB，選擇手調(diào)的最優(yōu)步長（0.1）為初始步長。對于SVRG-Polyak、SVRG、SVRG-BB，選取m=2n，正如文獻(xiàn)[2]建議的那樣。在圖1中，x軸代表的是時期數(shù)k，從左到右y軸代表的分別是函數(shù)值與最優(yōu)值的距離、函數(shù)梯度和步長。其中一長一短分布不均的虛線代表SVRG算法，從圖中可以看出，步長為0.1的那條虛線收斂性最好。分布均勻的那條虛線對應(yīng)于初始步長為最佳的固定步長的SVRG-BB 算法，帶有十字的實線對應(yīng)于該文提出的SVRG-Polyak 算法。SVRG-Polyak始終可以實現(xiàn)與SVRG相同的次優(yōu)水平，并且優(yōu)于SVRG-BB，且不需要給定初始步長。盡管與調(diào)整了最佳步長的SVRG相比，SVRG-Polyak需要更多的時間，但SVRG-Polyak明顯比選擇另兩種步長的SVRG和SVRG-BB好。

4? 結(jié)語

綜上所述，提出了使用帶有Polyak步長的隨機(jī)方差縮減梯度法（SVRG-Polyak）。對于強(qiáng)凸函數(shù)，從理論上證明了SVRG-Polyak的線性收斂性，并且還證明了SVRG-Polyak需要更少的內(nèi)循環(huán)迭代步便可以達(dá)到這樣一個收斂。相比于SVRG-BB而言，SVRG-Polyak相比于SVRG-BB無需存儲上一步的變量和梯度，并且不需要給定初始步長。而且我們還做了數(shù)值實驗，比較了SVRG-Polyak、SVRG-BB和SVRG。數(shù)值實驗表明我們的算法和SVRG-BB、SVRG具有可比性，甚至要優(yōu)于這兩種算法。

參考文獻(xiàn)

[1] ROBBINS H， MONRO S.A Stochastic Approximation Method[J].Annals of Mathematical Stats， 1951，22（3）：400-407.

[2] JOHNSON R，ZHANG T.Accelerating stochastic gradient descent using predictive variance reduction[J].News in physiological ences，2013，1（3）：315-323.

[3] SHANG F，ZHOU K，LIU H，et al.VR-SGD：A Simple Stochastic Variance Reduction Method for Machine Learning[J]. IEEE Transactions on Knowledge and Data Engineering，2020，32（1）：188-202.

[4] SCHMIDT M，ROUX NL，BACH F.Minimizing Finite Sums with the Stochastic Average Gradient[J]. Mathematical Programming，2017，162（1-2）：1-30.

[5] 史加榮，王丹，尚凡華，等.隨機(jī)梯度下降算法研究進(jìn)展[J/OL].自動化學(xué)報：1-17[2021-07-26].https：//www.doi.org/10.16383/j.aas.c190260.

[6] 劉彥，郭田德，韓叢英.一類隨機(jī)方差縮減算法的分析與改進(jìn)[J/OL].中國科學(xué)：數(shù)學(xué)（英文版）：1-18[2021-07-26].https：//www.kns.cnki.net/kcms/detail/11.5837.O1.20200922.1600.002.html.

[7] Allen-Zhu Z. Katyusha： The first direct acceleration of stochastic gradient methods[J].The Journal of Machine Learning Research，2017，18（1）：8194-8244.

[8] POLYAK B T. Introduction to optimization[M].New York：Chapman & Hall，1987：138-144.

[9] NESTEROV Y.Introductory Lectures on Convex Optimization：A Basic Course[M].Boston：Springer US，2004.

[10] TAN CH， MA SQ， DAI YH， et al.Barzilai-Borwein Step Size for Stochastic Gradient Descent[C]//Advances in Neural Information Processing Systems. New York：Curran Associates Inc，2016：685-693.