基于自适应步长的随机递归梯度算法
2023-03-02李晓桐王福胜乔晓云
李晓桐,王福胜*,乔晓云
(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 G 假设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-μη) 针对机器学习中二分类的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算法中取不同γ对残差的影响 在本文中,将自适应步长与SARAH++算法结合,提出了一种改进的算法SARAH++AS.从实验结果分析来看,相比于使用固定步长的SARAH++算法,新算法的收敛速度更快,不受初始步长选取的影响.新算法对初始步长的选择是有效的.
2 收敛性分析
3 数值实验
4 结论
