甄 娜，王福胜

(太原师范学院 数学系，山西 晋中 030619)

0 引言

在大规模机器学习背景下，广泛考虑下列优化问题：

(1)

其中n是训练集大小，每个fi,i∈{1,2,…,n}是凸函数且有Lipschitz连续导数.这类问题在监督学习应用中经常出现，而在应用中通常n相对比较大使得标准的梯度下降(GD)方法效率较低，因为它需要多次计算全梯度.针对这个不足，随机梯度下降(SGD)[1]进行了改进，它在每次迭代中随机选取训练集中的一个实例来近似全梯度.在SGD的第t次迭代中，更新规则为：

xt+1=xt-ηtfit(xt),

(2)

其中下标it可以从{1,2,…,n}中随机选取，ηt>0在机器学习中通常被称为学习率，即优化迭代中的步长.在(2)中通常假设随机梯度估计fit(xt)的期望值是F(xt)的无偏估计，即Ε[fit(xt)|xt]=F(xt).然而随机选取一个实例将可能产生方差，不能确保目标函数F(xt)收敛.为了克服这个缺陷，人们通常在迭代过程中选取一个下降步长序列以更新步长，一般情况下SGD的下降步长ηt满足如下条件：

(3)

但这种做法又会导致随机梯度方法的收敛速度较慢，在强凸条件下，标准的SGD算法是次线性收敛的.

近年来，有关学者通过引入方差约简技术进一步改进了SGD算法，例如随机双坐标上升(SDCA)[2]，随机方差约简梯度(SVRG)[3]，小批量半随机梯度下降(mS2GD)[4]，随机递归梯度(SARAH)[5]等.值得注意的是,上述大部分算法均使用固定的步长.文献AdaGrad[6]基于过去梯度的平方和自适应地选择步长，获得了较好的数值效果.在非线性优化问题的算法设计中，BB步长方法[7]具有较好的特性，戴彧虹等学者对此进行了深入研究，获得了丰富的……