嵌入Stabilized Barzilai-Borwein步长的一阶随机优化算法研究

史卫娟 Adibah Shuib Zuraida Alwadood

摘  要：近年来，机器学习发展迅速，在广泛应用于各个领域的同时取得了许多理论突破。它为系统提供访问数据的能力，通过从过去的经验中学习和改进来解决复杂问题，使机器能够执行认知功能。文中将基于改进的Stabilized Barzilai-Borwein（SBB）方法自动计算步长，与SVRG结合形成新的算法SVRG-SBB，并从理论上证明新算法收敛，能够有效地解决机器学习中的常见问题。

关键词：随机优化;SBB步长;机器学习

中图分类号：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  引  言

机器学习为系统提供访问数据的能力，并通过从过去的经验中学习和改进，然后解决复杂问题，使机器能够执行认知功能。

一阶优化算法由于其目标函数假设弱、收敛速度快、易于实现等优点，被广泛用于求解机器学习模型参数。许多一阶随机优化方法已被用于求解机器学习的优化模型，如Robbins和Monro[1]提出的Stochastic Gradient Descent（SGD），Johnson和Zhang[2]提出的stochastic variance reduced gradient（SVRG）和Konečný[3]提出的mini-batch semi-stochastic gradient descent method（mS2GD）。

然而，傳统的一阶优化算法会遇到各种各样的问题。一方面，随着深度神经网络等机器学习模型中数据规模的爆炸性增长和参数规模的不断增大，传统的确定性数值优化算法存在计算量过大的问题。另一方面，数值优化领域中讨论的一阶算法分析往往基于最坏情况下的计算复杂度。

Robbins和Monro于1951提出了随机梯度下降（SGD）方法。后来，它成为科学和工程领域的核心组成部分，如统计学、机器学习、信号/图像处理、反问题等。在经典的SGD算法中，每次重复都会选择一个随机示例。考虑到传统的线搜索技术不适用于随机优化算法，在SGD中通常使用递减步长或手动调整固定步长。实际上，这两种方法可能非常耗时。

Nitanda[4]介绍了加AccProx SVRG方法，该方法结合了Nesterov的加速方法。Nitanda[5]提出了一种新的加速随机梯度方法，即AMSVRG方法，该方法将另一种类似于Nesterov加速方法的加速梯度方法与ProxSVRG相结合。

在机器学习的随机优化应用中，步长是一个重要的问题，特别是在一阶随机优化算法中。以更快的速度更新步长会直接影响大量数据的处理速度。对这一问题的研究可以积极推动机器学习的发展，具有重大的理论和现实意义。

有一些研究人员在优化小批量时特别考虑了步长问题，并取得了显著的成果。Yang等人[6]通过将Barzilai-Borwein（BB）更新步骤合并到小批量半随机梯度下降（mS2GD）方法中，引入了一种称为mS2GD-BB的新小批量方法。他们证明了mS2GD-BB在强凸和非光滑函数中线性收敛。

Yang等人[7]提出使用Barzilai Borwein（BB）方法自动计算Acc-Prox-SVRG方法的步长，以获得一种新的加速方法，称为Acc-Prox-SVRG-BB。Yang等人证明了Acc-Prox-SVRG-BB的收敛性，并表明其复杂性与最著名的SG方法相当。

De等人[8]和Yang等人提出的方法在使用BB或RBB公式计算步长时没有避免分母接近零。当使用BB或RBB公式时，如果目标函数是非凸的，分母可能接近于零甚至为负。

在机器学习中，通常考虑以下优化问题。

设f1，f2，…fn是来自Rd→R.的向量函数序列。假设每个fi是凸的和可微的，并且函数F是强凸的。该模型的目标函数如下：

其中n是样本量，w代表模型参数，fi（w）是一系列损失函数，用于评估当前参数w的成本。在这种情况下，每个fi： Rd→R是与第i个样本数据对应的成本函数。通常，fi（w）依赖于训练数据（xi，yi）（监督学习）。

許多一阶随机优化方法已被用于求解机器学习的优化模型，如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等将这两种算法用于求解目标函数为光滑函数的情形，并分析了在此情况下的SVRG-BB算法的收敛性。一阶优化算法涉及使用一阶导数（梯度）来选择搜索空间中的移动方向。步长（学习率）用于控制在搜索空间中移动的距离。步长太小会导致搜索耗时较长且停留在局部最优值，而步长太大则会导致搜索空间出现锯齿形或跳跃，完全忽略最优值。

本文的目的是通过引入Stabilized Barzilai-Borwei（SBB）步长来求解这一类问题，从而获得类似或更好的结果。

1  带有SBB步长的SVRG算法

Barzilai和Borwein[13]于1988提出的BB法也称为两点阶梯梯度法。该方法主要用于求解非线性优化问题。与传统的拟牛顿法相比，BB法只需少量计算即可满足拟牛顿性质（有些文献也将满足拟牛顿性质称为满足割线方程）。假设我们需要解决以下无约束优化问题：

其中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步长提出了稳定Stabilized Barzilai-Borwei（SBB），方法是引入每对连续迭代之间的距离边界，从而减少BB迭代次数。所提出的SBB方法保证了收敛性，其中证明了具有Lipschits梯度的强凸函数的全局收敛性，而不涉及任何线搜索，并且只使用梯度值。Burdakov等人定义的SBB为：

我们将以上SBB算法中的步长除以m，然后与Johnson和Zhang 2013年提出的SVRG算法结合，得到新的算法SVRG-SBB为;

3  结  论

由第2部分理论证明知，本文提出的SVRG-SBB改进了BB步长可能出现的步长过长的情形。在一定程度上改进了算法的稳定性。同时在理论上证明了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ČNÝ 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.

作者簡介：史卫娟（1988—），女，汉族，湖南娄底人，讲师，硕士研究生，研究方向：最优化算法及应用。

3986500338202