嵌入Stabilized Barzilai-Borwein步長的一階隨機優(yōu)化算法研究

史衛(wèi)娟 Adibah Shuib Zuraida Alwadood

摘? 要：近年來，機器學(xué)習(xí)發(fā)展迅速，在廣泛應(yīng)用于各個領(lǐng)域的同時取得了許多理論突破。它為系統(tǒng)提供訪問數(shù)據(jù)的能力，通過從過去的經(jīng)驗中學(xué)習(xí)和改進來解決復(fù)雜問題，使機器能夠執(zhí)行認知功能。文中將基于改進的Stabilized Barzilai-Borwein（SBB）方法自動計算步長，與SVRG結(jié)合形成新的算法SVRG-SBB，并從理論上證明新算法收斂，能夠有效地解決機器學(xué)習(xí)中的常見問題。

關(guān)鍵詞：隨機優(yōu)化;SBB步長;機器學(xué)習(xí)

中圖分類號：TP181? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A文章編號：2096-4706（2021）15-0109-04

Abstract： In recent years， machine learning is developing rapidly and has made many theoretical breakthroughs while being widely applied in various fields. It provides the system with the ability to access data， solve complex problems by learning from past experience and improving， and enable the machine to perform cognitive functions. In this paper， the step size is automatically calculated based on the improved Stabilized Barzilai-Borwein（SBB） method， which is combined with SVRG to form a new algorithm SVRG-SBB. It is proved theoretically that the new algorithm converges and can effectively solve the common problems in machine learning.

Keywords： stochastic optimization; SBB step size; machine learning

0? 引? 言

機器學(xué)習(xí)為系統(tǒng)提供訪問數(shù)據(jù)的能力，并通過從過去的經(jīng)驗中學(xué)習(xí)和改進，然后解決復(fù)雜問題，使機器能夠執(zhí)行認知功能。

一階優(yōu)化算法由于其目標函數(shù)假設(shè)弱、收斂速度快、易于實現(xiàn)等優(yōu)點，被廣泛用于求解機器學(xué)習(xí)模型參數(shù)。許多一階隨機優(yōu)化方法已被用于求解機器學(xué)習(xí)的優(yōu)化模型，如Robbins和Monro[1]提出的Stochastic Gradient Descent（SGD），Johnson和Zhang[2]提出的stochastic variance reduced gradient（SVRG）和Kone?ny[3]提出的mini-batch semi-stochastic gradient descent method（mS2GD）。

然而，傳統(tǒng)的一階優(yōu)化算法會遇到各種各樣的問題。一方面，隨著深度神經(jīng)網(wǎng)絡(luò)等機器學(xué)習(xí)模型中數(shù)據(jù)規(guī)模的爆炸性增長和參數(shù)規(guī)模的不斷增大，傳統(tǒng)的確定性數(shù)值優(yōu)化算法存在計算量過大的問題。另一方面，數(shù)值優(yōu)化領(lǐng)域中討論的一階算法分析往往基于最壞情況下的計算復(fù)雜度。

Robbins和Monro于1951提出了隨機梯度下降（SGD）方法。后來，它成為科學(xué)和工程領(lǐng)域的核心組成部分，如統(tǒng)計學(xué)、機器學(xué)習(xí)、信號/圖像處理、反問題等。在經(jīng)典的SGD算法中，每次重復(fù)都會選擇一個隨機示例?？紤]到傳統(tǒng)的線搜索技術(shù)不適用于隨機優(yōu)化算法，在SGD中通常使用遞減步長或手動調(diào)整固定步長。實際上，這兩種方法可能非常耗時。

Nitanda[4]介紹了加AccProx SVRG方法，該方法結(jié)合了Nesterov的加速方法。Nitanda[5]提出了一種新的加速隨機梯度方法，即AMSVRG方法，該方法將另一種類似于Nesterov加速方法的加速梯度方法與ProxSVRG相結(jié)合。

在機器學(xué)習(xí)的隨機優(yōu)化應(yīng)用中，步長是一個重要的問題，特別是在一階隨機優(yōu)化算法中。以更快的速度更新步長會直接影響大量數(shù)據(jù)的處理速度。對這一問題的研究可以積極推動機器學(xué)習(xí)的發(fā)展，具有重大的理論和現(xiàn)實意義。

有一些研究人員在優(yōu)化小批量時特別考慮了步長問題，并取得了顯著的成果。Yang等人[6]通過將Barzilai-Borwein（BB）更新步驟合并到小批量半隨機梯度下降（mS2GD）方法中，引入了一種稱為mS2GD-BB的新小批量方法。他們證明了mS2GD-BB在強凸和非光滑函數(shù)中線性收斂。

Yang等人[7]提出使用Barzilai Borwein（BB）方法自動計算Acc-Prox-SVRG方法的步長，以獲得一種新的加速方法，稱為Acc-Prox-SVRG-BB。Yang等人證明了Acc-Prox-SVRG-BB的收斂性，并表明其復(fù)雜性與最著名的SG方法相當。

De等人[8]和Yang等人提出的方法在使用BB或RBB公式計算步長時沒有避免分母接近零。當使用BB或RBB公式時，如果目標函數(shù)是非凸的，分母可能接近于零甚至為負。

在機器學(xué)習(xí)中，通?？紤]以下優(yōu)化問題。

設(shè)f1，f2，…fn是來自Rd→R.的向量函數(shù)序列。假設(shè)每個fi是凸的和可微的，并且函數(shù)F是強凸的。該模型的目標函數(shù)如下：

其中n是樣本量，w代表模型參數(shù)，fi（w）是一系列損失函數(shù)，用于評估當前參數(shù)w的成本。在這種情況下，每個fi： Rd→R是與第i個樣本數(shù)據(jù)對應(yīng)的成本函數(shù)。通常，fi（w）依賴于訓(xùn)練數(shù)據(jù)（xi，yi）（監(jiān)督學(xué)習(xí)）。

許多一階隨機優(yōu)化方法已被用于求解機器學(xué)習(xí)的優(yōu)化模型，如Stochastic Gradient Descent（SGD）、stochastic variance reduced gradient（SVRG）和mini-batch semi-stochastic gradient descent method（mS2GD）。然而，所有這些方法都采用遞減或者固定步長，這通常是不合適的、不切實際的和耗時的。Tan等[12]將BB方法引入到SGD算法和SVRG算法中，得到兩種新的算法：SGD-BB算法和SVRG-BB算法。Tan等將這兩種算法用于求解目標函數(shù)為光滑函數(shù)的情形，并分析了在此情況下的SVRG-BB算法的收斂性。一階優(yōu)化算法涉及使用一階導(dǎo)數(shù)（梯度）來選擇搜索空間中的移動方向。步長（學(xué)習(xí)率）用于控制在搜索空間中移動的距離。步長太小會導(dǎo)致搜索耗時較長且停留在局部最優(yōu)值，而步長太大則會導(dǎo)致搜索空間出現(xiàn)鋸齒形或跳躍，完全忽略最優(yōu)值。

本文的目的是通過引入Stabilized Barzilai-Borwei（SBB）步長來求解這一類問題，從而獲得類似或更好的結(jié)果。

1? 帶有SBB步長的SVRG算法

Barzilai和Borwein[13]于1988提出的BB法也稱為兩點階梯梯度法。該方法主要用于求解非線性優(yōu)化問題。與傳統(tǒng)的擬牛頓法相比，BB法只需少量計算即可滿足擬牛頓性質(zhì)（有些文獻也將滿足擬牛頓性質(zhì)稱為滿足割線方程）。假設(shè)我們需要解決以下無約束優(yōu)化問題：

其中f（w）是可微的。問題（2）的擬牛頓法迭代公式為：

其中，Bk是f的Hessian矩陣在wk處的近似值。我們使用來近似Hessian矩陣（ηk>0），并將其代入割線方程BkSk=yk，其中sk=wk-wk-1，yk=?f（wk）-?f（wk-1），k>1 。通過求解割線方程的殘差，即：

Burdakov等人[14]在2019年通過修改BB步長提出了穩(wěn)定Stabilized Barzilai-Borwei（SBB），方法是引入每對連續(xù)迭代之間的距離邊界，從而減少BB迭代次數(shù)。所提出的SBB方法保證了收斂性，其中證明了具有Lipschits梯度的強凸函數(shù)的全局收斂性，而不涉及任何線搜索，并且只使用梯度值。Burdakov等人定義的SBB為：

我們將以上SBB算法中的步長除以m，然后與Johnson和Zhang 2013年提出的SVRG算法結(jié)合，得到新的算法SVRG-SBB為;

3? 結(jié)? 論

由第2部分理論證明知，本文提出的SVRG-SBB改進了BB步長可能出現(xiàn)的步長過長的情形。在一定程度上改進了算法的穩(wěn)定性。同時在理論上證明了SVRG-SBB期望上線性收斂，即選擇符合一定條件的m，使得成立。

參考文獻：

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

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

[3] KONE?NY J，LIU J，RICHTáRIK P，et al. mS2GD：Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting [J/OL].arXiv：1410.4744 [cs.LG].[2021-05-10].https：//arxiv.org/abs/1410.4744v1.

[4] GHADIMI，S，GUANGHUI L. Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I：A Generic Algorithmic Framework [J/OL].SIAM Journal on Optimization，2012，22（4）：1469-1492.

[5] NITANDA A. Stochastic proximal gradient descent with acceleration techniques [C]//Advances in Neural Information Processing Systems，Montreal：MIT Press，2014：1574-1582.

[6] NITANDA A. Accelerated Stochastic Gradient Descent for Minimizing Finite Sums [J/OL]. arXiv：1506.03016 [stat.ML].[2021-05-10].https：//arxiv.org/abs/1506.03016.

[7] YANG Z，WANG C，ZANG Y，et al. Mini-batch algorithms with Barzilai-Borwein update step [J].Neurocomputing，2018（314）：177-185.

[8] YANG Z，WANG C，ZHANG Z M，et al. Random Barzilai-Borwein step size for mini-batch algorithms [J].Engineering Applications of Artificial Intelligence，2018（C）：124-135.

[9] YANG Z，WANG C，ZHANG Z，et al. Accelerated stochastic gradient descent with step size selection rules [J].Signal Processing，2019（159）：171-186.

[10] DE S，YADAV A，JACOBS D， et al. Automated Inference with Adaptive Batches [C]//Proceedings of the 20th International Conference on Artificial Intelligence and Statistics.Fort Lauderdale：JMLR，2017（54）：1504-1513.

[11] MA K，ZENG J，XIONG J，et al. Stochastic Non-convex Ordinal Embedding with Stabilized Barzilai-Borwein Step Size [J/OL].arXiv：1711.06446 [stat.ML].[2021-05-10].https：//arxiv.org/abs/1711.06446.

[12] TAN C，MA S，DAI Y H，et al. Barzilai-Borwein step size for stochastic gradient descent [C]//the 30th International Conference on Neural Information Processing Systems.Barcelona：Curran Associates Inc.，2016：685–693.

[13] BARZILAI J，BORWEIN J. Two-Point Step Size Gradient Methods [J].IMA Journal of Numerical Analysis，1988，8（1）：141–148.

[14] BURDAKOV O，DAI Y H，HUANG N. Stabilized Barzilai-Borwein Method [J].Journal of Computational Mathematics.2019，37（6），916-936.

作者簡介：史衛(wèi)娟（1988—），女，漢族，湖南婁底人，講師，碩士研究生，研究方向：最優(yōu)化算法及應(yīng)用。

3986500338202