基于自适应步长的随机递归梯度算法

李晓桐,王福胜*,乔晓云

(1.太原师范学院 数学与统计学院,山西 晋中 030619;2.山西工程科技职业大学 基础课教学部,山西 晋中 030619)

0 引言

在大规模机器学习中,如下优化问题常常出现:

(1)

xt+1=xt-ηt∇fit(xt),

(2)

其中下标it是从{1,2,…,n}中随机选取得到.

在机器学习中有许多改进SGD的工作[3-4].近年来,出现了大量被称为方差减少方法的随机梯度算法的改进变体,如:随机方差缩减梯度算法(SVRG)[5],随机递归梯度算法(SARAH,SARAH+)[6],随机平均梯度算法(SAG)[7],随机对偶坐标上升算法(SDCA)[8],小批量半随机梯度下降算法(mS2GD)[9],和SAGA[10]等.近年来,对于随机递归梯度算法有新的改进,如SARAH++[11].

1 算法

因此,文献[11]中将SARAH+修改为SARAH++,算法如下:

算法1 SARAH++输入: 0<γ≤1,步长0<η≤γL,内循环数m,最大迭代数T,样本数n以及初始点x～0,G=0,s=0;1:while G

下面将上述自适应步长与SARAH++算法相结合构造成新的算法,见算法2.

算法2 SARAH++AS输入: 0<γ≤1,步长0<η≤γL,内循环数m,最大迭代数T,样本数n以及初始点x～0,G=0,s=0;1:while G1 then4: 计算Ls= Fxs()- F(xs-1)xs-xs-15: 计算步长ηs=γmLs6: end if7: while v(s)t2≥γv(s)02 and t≤m do8: x(s)t+1=x(s)t-ηv(s)t,t=t+19: if m≠0 do10: 随机选取it∈{1,2,…,n},11: v(s)t= fit(x(s)t)- fit(x(s)t-1)+v(s)t-112: end if 13: end while14:KS=t,x～s=x(s)KS,G=G+KS15: end whileS=s,x^=x～s

2 收敛性分析

假设1假设每个函数fi(x)的梯度是L-Lipschitz连续的,即存在一个常数L,有

假设2假设每个fi都是凸的,且目标函数F(x)是μ-强凸的,即

在假设2中,我们定义x*为最优解,F(x)的强凸性等价为:

假设3假设每个函数fi(x)都是凸函数,则有

fi(y)≥fi(x)+∇fi(x)T(y-x),∀x,y∈d.

其中x*是F(x)的最优解.

在上述式子中,若假设Lη

证：根据F(x)的强凸的可知:

(1-μη)

3 数值实验

针对机器学习中二分类的l2正则化逻辑回归问题:给定一组训练集(a1,b1),……,(an,bn),其中ai∈d,bi∈{+1,-1},通过求解下列问题得到最优预测值x∈d,

实验包括三个部分:首先,展示了SARAH++AS与SARAH++两个算法的收敛速度,验证了SARAH++AS的有效性;其次,对比了两个算法取不同步长的变化趋势;最后,对比了SARAH++AS取不同γ之后对残差的影响.所有的实验结果如图1所示.

图1 不同数据集上的SARAH++AS和SARAH++算法残差对比

图1对比了SARAH++AS与SARAH++两个算法的收敛速度,其中x轴代表外循环数,y轴表示残差对比,即F(xs)-F(x*).图中,蓝色,红色和绿色实线代表不同步长的 SARAH++AS 算法,蓝色,红色和绿色虚线对应着固定步长的 SARAH++ 算法.四个子图(a),(b),(c)和(d)分别对应于phishing,ijcnn1,w8a和 splice 四个数据集.从图中可以看出,SARAH++AS比固定步长的SARAH++算法快,并且当选择不同的初始步长η时,SARAH++AS算法的收敛性能不受影响,对于步长的选取更加容易.

图2对比了两个算法在不同数据集上的求解目标函数时步长的变化趋势,其中x轴代表外循环数,y轴表示步长变化.图中蓝色,红色和绿色实线代表不同步长的 SARAH++AS 算法,蓝色,红色和绿色虚线对应着固定步长的 SARAH++ 算法.从图中可以看出,SARAH++AS比固定步长的SARAH++算法快,并且当选择不同的初始步长η时,SARAH++AS算法的收敛性能不受影响,对于步长的选取更加容易.

图2 不同数据集上的SARAH++AS和SARAH++算法步长对比

图3 SARAH++AS算法中取不同γ对残差的影响

4 结论

在本文中,将自适应步长与SARAH++算法结合,提出了一种改进的算法SARAH++AS.从实验结果分析来看,相比于使用固定步长的SARAH++算法,新算法的收敛速度更快,不受初始步长选取的影响.新算法对初始步长的选择是有效的.