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

李蝶

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

關鍵詞：Polyak步長? 方差縮減? 強凸? 線性收斂

中圖分類號：O1? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：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

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

（1）

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

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

（2）

式中，是第t次迭代的學習率，用于調整參數更新的幅度。

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

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

通常假設，是對的無偏估計，即。

SGD由于算法的隨機性，產生了方差，導致算法的收斂速度不如梯度下降算法快，因此涌現了大量的方差縮減算法[2-4]。對于光滑和強凸的函數，Johnson等人提出的隨機方差縮減梯度法（SVRG）[2]可以達到與SDCA和SAG[4]算法相同快的收斂率，都可以達到線性收斂，并且SVRG的線性收斂結果證明更簡單、具有直觀解釋，而且與SDCA和SAG不同，SVRG無需存儲中間梯度，因此對于一些復雜問題如結構預測問題和神經網絡學習，此方法更易實現。

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

（4）

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

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

1? Polyak步長

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

（5）

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

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

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

其中

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

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

因此，Polyak步長為：

（6）

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

2? 帶有Polyak步長的SVRG

定義1：函數是強凸的，如果滿足：

（7）

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

（8）

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

（9）

等價于

（10）

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

2.1 SVRG-Polyak算法

算法：

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

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

步1：計算一個全梯度;

步2：計算步長;

步3：;

步4：對執(zhí)行;

步5：隨機選取;

步6：;

步7：結束內層循環(huán);

步8：;

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

2.2 收斂性分析

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

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

證明：令（10）中，就有，便得到了ηk的下界。根據強凸性，

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

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

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

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

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

其中第三個不等式用的是的強凸性。通過對t遞歸應用上面不等式，并結合和，可以得到：

當選取充分大的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可以實現期望上的線性收斂：

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

3? 數值實驗

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

邏輯回歸：

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

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

4? 結語

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

參考文獻

[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/OL].自動化學報：1-17[2021-07-26].https：//www.doi.org/10.16383/j.aas.c190260.

[6] 劉彥，郭田德，韓叢英.一類隨機方差縮減算法的分析與改進[J/OL].中國科學：數學（英文版）：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.