机器学习中随机方差缩减梯度算法的一种新的步长规则

杨一名，王福胜

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

0 引言

在统计机器学习[1]和信号处理[2]等领域中，通常考虑如下形式的优化问题：

其中n代表训练样本数目，d代表变量维度，本文假设每一个fi均是一阶连续可微的.求解上述问题的传统方法是梯度下降算法[3]，但是当n的取值较大时，该方法在计算量上很难容忍甚至不能执行.针对这一缺陷，基于Robbins和Monro[4]提出的随机近似思想，研究者们提出了随机梯度下降算法(SGD)[5]，SGD算法的特点是每次迭代只选取一个或部分样本确定迭代方向，选取一个样本时的迭代公式如下：

ωk+1=ωk-ηk∇fik(ωk)，

其中，∇fik(ωk)表示第ik个分量函数在ωk处的梯度，ηk>0表示步长.目前，通过引入不同技术改进SGD性能的工作被广泛应用[6-8].事实上，SGD算法本身的收敛性取决于随机方向与真实梯度的方差，采用梯度聚合的方式可以有效缩减方差.经典的梯度聚合类算法通过重新使用或修改之前的梯度缩减方差，常见的有随机方差缩减梯度算法(SVRG)[9]，随机对偶坐标上升算法(SDCA)[10]，半随机梯度下降算法(S2GD)[11]，小批量半随机梯度下降算法(mS2GD)[12]，随机递归梯度算法(SARAH)[13]，随机平均梯度算法(SAG)[14]和SAGA[15]等.

对于方差缩减类算法而言，步长是影响算法性能的关键因素，传统的方法是根据人为的经验选择符合某种规律的递减步长或者较小的固定步长，并且满足：

AdaGrad[16]和Adam[17]等采用对角修正技术为每个分量自适应地选取步长.当前，由于BB步长[18]特有的性质，许多学者创新性地提出将方差缩减方法与BB步长相结合以提高算法的收敛速度.受启发于SGD-BB[19]和STSG[20]算法，本文考虑将复合BB步长(CABB)[21]与随机方差缩减梯度算法(SVRG)[9]结合，提出SVRG-CABB.

1 随机方差缩减梯度算法

构造新算法之前，本节首先回顾随机方差缩减梯度算法(SVRG)[9].事实上，SVRG包括两层循环，通常在外循环中计算全梯度，而在内循环中计算方差缩减的随机梯度，在迭代过程中需要随机选取下标it∈{1,…,n}.从总体上看，该算法执行最关键步骤是对于随机梯度的更新，即：

其迭代更新规则为：

ωt+1=ωt-ηkvt.

可以发现SVRG算法中迭代方向vt是真实梯度的无偏估计，且算法在迭代过程中的方差在逐渐减小，以下给出SVRG算法的基本框架：

第4步：如果t>m，转第5步；否则转第3步；

第6步：令k:=k+1，如果k>T，停止；否则转第2步.

2 BB步长

第3步：如果k>0，计算复合BB步长：

第6步：令k:=k+1，如果k>T，停止；否则转第2步.

3 数值实验

本节将SVRG-CABB算法应用于求解带有l2正则化项的逻辑回归模型，并给出实验结果验证算法的有效性，模型表示如下：

表1 数据集信息

实验包括四个部分：首先，对比了SVRG-CABB算法与SVRG算法的收敛速度，验证了SVRG-CABB的有效性；其次，对比了SVRG-CABB算法与SVRG算法的分类准确率；接着，测试了SVRG-CABB算法关于不同初始步长的步长变化趋势；最后，对比了SVRG-CABB算法和STSG[20]算法在不同数据集上的求解目标函数时参数τ对算法性能的影响.所有的实验结果如图1到图4所示.

图1 SVRG-CABB和带有固定步长的SVRG算法残差对比

图1对比了SVRG-CABB和SVRG算法的收敛速度，其中x轴代表迭代次数，y轴代表求解目标函数所得的残差损失，图中的虚线和实线分别对应于带有不同初始步长的SVRG-CABB算法，虚线分别对应于带有固定步长的SVRG算法.四个子图(a)，(b)，(c)和(d)分别对应于两种算法在数据集heart，splice，ijcnn1和a9a上的实验结果对比.从图中可以看出，本文提出的新算法SVRG-CABB收敛速度整体上比带有固定步长的SVRG算法快，并且当选择不同的初始步长η0时，SVRG-CABB算法的收敛性能不受影响，可以看出使用CABB步长的优势是使得新算法对于步长的选取更加容易.

图2 SVRG-CABB和固定步长的SVRG算法分类准确率对比

图2对比了SVRG-CABB和SVRG算法在不同数据集上的求解目标函数的分类准确率，其中x轴代表迭代次数，y轴代表求解分类准确率，图中虚线和实线分别对应带有不同初始步长的SVRG-CABB算法，虚线分别对应带有固定步长的SVRG算法.四个子图(a)，(b)，(c)和(d)分别对应两种算法在数据集heart，splice，ijcnn1和a9a上的实验对比.从图中可以看出，本文提出的SVRG-CABB算法的分类准确率明显高于带有固定步长的SVRG算法，当选择不同的初始步长η0时，SVRG-CABB算法的分类准确率并不受影响.在相同条件下，SVRG-CABB算法分类准确率更加稳定且明显高于带有固定步长的SVRG算法.

图3 SVRG-CABB步长变化趋势

图3测试了SVRG-CABB算法在不同数据集上的求解目标函数时步长的变化趋势，其中x轴代表迭代次数，y轴代表步长，图中虚线和实线分别对应不同的初始步长，虚线分别对应不同的固定步长.两个子图(a)和(b)分别对应于SVRG-CABB算法在数据集heart和splice上的测试结果.从图中可以看出，本文提出的SVRG-CABB算法的步长最终收敛于最优步长的邻域.这说明选取不同的初始步长，对算法收敛性能影响不大.

图4 不同参数值τ下SVRG-CABB和STSG算法性能对比

图4对比了SVRG-CABB算法和STSG算法在不同数据集上的求解目标函数时参数τ对算法性能的影响，其中x轴代表迭代次数，y轴代表残差损失，图中的实线分别对应于τ∈(0,1)的SVRG-CABB算法，虚线分别对应于τ∈(0,1)的STSG算法.两个子图(a)和(b)分别对应于SVRG-CABB算法在数据集heart和a9a上的测试结果.从图中可以看出，本文提出的SVRG-CABB和STSG的算法性能虽然均受参数τ值的影响，并且随着τ值的增加算法性能总体得到提升，但是SVRG-CABB算法的收敛性能最终优于选择相同参数τ的STSG算法.

4 结论

本文将随机方差缩减梯度算法(SVRG)与改进的复合BB步长(CABB)有机结合，提出了一种新的SVRG-CABB算法.从实验结果分析来看，新算法在求解问题的过程中可以动态调节步长的大小，相比于已有的使用固定步长的SVRG算法以及已有的STSG算法，新算法的收敛速度更快，并且不受初始步长选取的影响.