基于Polyak步长的随机递归梯度算法.pdf

应用数学MATHEMATICA APPLICATA2024,37(1):280-288基于Polyak步长的随机递归梯度算法王福胜,李晓桐(太原师范学院数学与统计学院,山西 晋中 030619)摘要：针对机器学习中一类有限光滑凸函数和的最小化问题,将随机递归梯度算法和Polyak步长结合,提出基于Polyak步长的随机递归梯度算法(SARAH-Polyak).分别在强凸和一般凸条件下证明了算法的线性收敛性.实验结果表明SARAH-Polyak算法的有效性.关键词：Polyak步长;随机递归;梯度下降中图分类号：O224AMS(2010)主题分类：90C15;90C25;90C30文献标识码：A文章编号：1001-9847(2024)01-0280-091.引言在机器学习中,经常会出现以下的优化问题:minxRdF(x)=1nni=1fi(x),(1.1)其中n是训练集大小,每个fi,i 1,2,n是凸函数且有Lipschitz连续导数.解决上述优化问题的标准有效的方法为梯度下降法(GD)1.对于光滑优化问题(1.1),梯度下降的迭代方法为xt+1=xt tF(xt)=xttnni=1fi(xt),其中t 0表示步长.当n较大时需要计算全梯度,导致计算量很大.Robbins和Monro2在1951年提出了随机近似(stochastic approximation,SA).之后,研究者提出了随机梯度下降(stochasticgradient descent,SGD)34,该方法的迭代公式如下:xt+1=xt tfit(xt),(1.2)其中下标it是从1,2,n中随机选取得到.在机器学习中有一系列改进SGD的工作34.SGD算法的收敛性质取决于随机方向和真实梯度的方差,因此,如何缩减方差是改进SGD的方法之一.常见的有随机方差缩减梯度算法(SVRG)5,随机递归梯度算法(SARAH)6,随机平均梯度算法(SAG)7等.对于方差缩减类算法而言,步长也是关键因素.传统的步长要选择递减步长或者较小的固定步长,并且满足i=1t=和i=12t 1 then5:tk=f(xk)f(x)v02,v0=0,1,v0=0.h=kk+1/3,k=1mh tk.6:end if7:x1=x0 kv0,8:for t=1,.m 1 do9:随机选取it 1,2,.,n10:vt=fit(xt)fit(xt1)+vt1,11:xt+1=xt kvt,12:end for13:xk=xm.14:end for3.收敛性分析假设3.1假设每个函数fi(x)都是凸函数,且目标函数F(x)是强凸的,即F(y)F(x)+F(x)T(y x)+2y x22,x,y Rd.这里我们定义x为问题(1.1)的最优解.并且由于F(x)是强凸的,因此x是唯一的.假设3.2假设每个函数fi(x)的梯度是L-Lipschitz连续的,即fi(x)fi(y)2 Lx y2,x,y Rd,即F(x)也是L-Lipschitz连续的.引理3.115假设F(x)是凸函数,且F(x)是L-Lipschitz连续的,则对x,y Rd,有(F(y)F(x)T(y x)1LF(y)F(x)22.第 1 期王福胜等：基于Polyak步长的随机递归梯度算法283引理3.215假设F(x)是凸函数,且F(x)是L-Lipschitz连续的,则对x,y Rd,有(F(y)F(x)T(y x)L+Ly x2+1+LF(y)F(x)2.引理3.3若假设3.1和3.2成立并且k2L,则在第k次循环中,对t 1,有Evt2 Evt12+(1 2kL)Evt vt12,且Evt2 Evt12.证Evt2=Evt1(fit(xt1)fit(xt)2=Evt12+Efit(xt1)fit(xt)22k(fit(xt1)fit(xt)T(vt1 vt)Evt12+Efit(xt1)fit(xt)22kL(fit(xt1)fit(xt)2=Evt12+(1 2kL)Evt vt12.注意上面第一不等式中我们利用了引理3.1,最后一个等式中我们利用了vt=fit(xt)fit(xt1)+vt1.由k2L可知(1 2kL)1,有Ee xk+1 x2 ke xk x2,其中k=(1 2k)m+12kL32+kL32+kL22.证Ext+1 x2=Ext kvt x2284应用数学2024=Ext k(F(xt)F(x)k(vt F(xt)x2 Ext x2 2k(xt x)TF(xt)+2kE(xt x)T(F(xt)vt)+2kEvt2(1 2k)xt x2+(2(1+12kL32)32kL32+2kL2)x0 x2.上面最后一个不等式中我们利用了引理3.6以及F(x)的强凸性.并且有Evt2 Ev02=F(x0)F(x)2 L2x0 x2.对t递归地应用上述结论,且注意到e xk=x0,e xk+1=xm,有Ee xk+1 x2(1 2k)me xk x2+(2(1+12kL32)32kL32+2kL2)nj=1(1 2k)je xk x2(1 2k)m+12kL32+kL32+kL22)e xk x2=ke xk x2.定理3.2若假设3.1和3.2成立,设1(0,14),当m满足如下条件:mhL32213,m1hlog(1 41)L,则有不等式Ee xk x2(1 1)ke x0 x2,即算法2具有R-线性收敛速度.证根据目标函数F(x)的强凸性以及F(x)=0,可知tk=F(xk)F(x)F(xk)212,k=1mhtk12mh.由F(x)的Lipschitz连续性可得tk=F(xk)F(x)F(xk)212L,k=1mhtk12mhL,因此12mhL k12mh.故k=(1 2k)m+12kL32+kL32+kL22 exp22mhLm+12kL32+kL32+kL22 expm1hL+L322mh2+L32mh3+L24mh2 0.我们给出以下四个条件:第 1 期王福胜等：基于Polyak步长的随机递归梯度算法2851)Polyak-Lojasiewicz不等式:12F(x)2(F(x)F);2)F(x)(x xproj);3)F(x)F2?x xproj?2;4)限制割线不等式(RSI):(F(x)F(xproj)T(x xproj)?x xproj?2.(3.1)接下来,我们分析了RSI条件下SARAH的性质.引理3.711若假设F是凸的并且满足(3.1)并且F(x)是L-Lipschitz连续的,那么对于任何 0,1,有(F(x)F(xproj)T(x xproj)aL?F(x)F(xproj)?2+(1 )?x xproj?2.引理3.811若假设3.2成立,F是凸的并且满足RSI,0,假设 1L,那么在SARAH-I的第k个时期,对t 1,我们有(E?xt xprojt?2)12(1+212kL32)(E?x0 xproj0?2)12.引理3.9若假设3.1成立,F是凸的并且满足(3.1),假设 1L,那么在第k个时期，对t 1,我们有E(xt xproj)T(F(xt)vt)(1+12kL32)12L32Ex0 x2.证结论可由引理3.4和3.8得到.定理3.3若假设3.2成立,F是凸的并且满足RSI,0.若 1L,则对t 1我们有:E?e xk+1 e xprojk+1?2 e E?e xk e xprojk?2,其中e =(1 2)m+12L32+L32+L22.证在第k个循环中,有E?xt+1 xprojt+1?2E?xt+1 xprojt?2E?xt xprojt?2 2(xt xprojt)TF(xt)+2E(xt xprojt)T(F(xt)vt)+2Ev02(1 2)E?xt xprojt?2+(2(1+212L32)32L32+2L2)?x0 xproj0?2.对t递归地应用上述结论,且注意到e xk=x0,e xk+1=xm,有E?e xk+1 e xprojk+1?2(1 2)m?e xk e xprojk?2+(2(1+212L32)32L32+2L2)m1j=0(1 2)j?e xk e xprojk?2(1 2)m+12L32+L32+L22)E?e xk e xprojk?2e E?e xk e xprojk?2.当F是一般凸时,k的上界会发生变化.因此,我们通过如下式子计算k的上界:k=1mhmintk,1,这里 0满足RSI,设2(0,14),当m满足如下条件:mhL3222,m1hlog(1 42)L则有不等式E?e xk e xprojk?2(1 2)k?e x0 e xproj0?2.证用F(x)的Lipschitz连续性,很容易得到12mhL k1mh.故k=(1 2k)m+12kL32+kL32+kL22 exp22mhLm+12kL32+kL32+kL22 expm1hL+L3212mh2+L3mh2+L22mh 0是正则化参数.我们使用了三个公开的数据集,数据集的大小为n,维度为d,详细信息如表4.1所示,所有数据可以在LIBSVM网站(www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/)下载.表中还列出了实验中所选取的 0值(在所有数据集上设置参数为=104,m=2n.所有的数值实验均在相同的Python计算环境下进行.所有的实验结果如图4.1-4.6所示.表4.1数值实验中使用的数据集和正则化参数数据集ndheart27013104splice100060104ijcnn14999022104图4.1heart上的残差损失图4.2heart上的步长变化趋势第 1 期王福胜等：基于Polyak步长的随机递归梯度算法287图4.1到图4.6展示了SARAH-BB,SARAH 以及SARAH-Polyak三个算法在数据集heart,splice和ijcnn1上的残差损失及步长变化趋势.在所有的图中,蓝色,红色和绿色实线代表不同步长的SARAH-Polyak 算法;黑色实线代表最优步长的SARAH-BB算法;蓝色,红色和绿色虚线对应着固定步长的SARAH算法.在所有的图中,x轴代表外循环数,图4.1,4.3和图4.5中y轴表示最优间隔，即F(xk)F(x),图4.2,4.4和4.6中y轴表示步长变化趋势.从图4.1,4.3和4.5中可以看出:SARAH-Polyak算法收敛速度整体上比采用固定步长的SARAH 算法快,并且当选择不同的初始步长0时,SARAH-Polyak算法的收敛性能不受影响.并且SARAH-Polyak与最优步长的SARAH-BB算法相差不大.图4.2,4.4和4.6中可以看出:当选取不同的初始步长时,SARAH-Polyak算法的步长最终收敛于最优步长的邻域.图4.3splice上的残差损失图4.4splice上的步长变化趋势图4.5ijcnn1上的残差损失图4.6ijcnn1上的步长变化趋势5.结论在本文中,我们提出了一种改进的算法SARAH-Polyak.首先我们用理论说明Polyak步长并没有增加算法的复杂度,因为该算法已经计算出全梯度,并且可以通过其他算法得到最优值.然后分别在强凸和一般凸的假设下证明了它的收敛性.最后从实验结果分析来看,相比于使用固定步长的SARAH算法,新算法的收敛速度更快,并且可以和最优步长的SARAH-BB相媲美,不受初始步长选取的影响.新算法对初始步长的选择是有效的.参考文献：1 HUANG Y K,DAI Y H,LIU X W,et al.Gradient methods exploiting spectral propertiesJ.Opti-mization Methods and Software,2020,35(4):681-705.2 ROBBINS H,MONRO S.A stochastic approximation methodJ.The Annals of Mathematical S-tatistics,1951,22(3):400-407.288应用数学20243 DING F,YANG H Z,LIU F.Performance analysis of stochastic gradient algorithms under weakconditionsJ.Science in China Series F:Information Sciences,2008,51(9):1269-1280.4 BOTTOU L,CURTIS F E,NOCEDAL J.Optimization methods for large-scale machine learningJ.SIAM Review,2018,60(2):223-311.5 JOHNSON R,ZHANG T.Accelerating stochastic gradient descent using predictive variance reductionC/Proceedings of Neural Information Processing Systems.Nevada:Curran Associates,2013:315-323.6 NGUYEN L M,LIU J,SCHEINBERG K,et al.SARAH:A novel method for machine learning prob-lems using stochastic recursive gradientC/International Conference on Machine Learning.PMLR,2017:2613-2621.7 SCHMIDT M,LE ROUX N,BACH F.Minimizing finite sums with the stochastic average gradientJ.Mathematical Programming,2017,162(1):83-112.8 DUCHI J C,HAZAN E,SINGER Y J.Adaptive subgradient methods for online learning and s-tochastic optimization J.Journal of Machine Learning Research,2011,12(7):2121-2159.9 KINGMA D P,BA J.Adam:A method for stochastic optimizationC/3rd International Conferencefor Learning Representations,San Diego:Amsterdam Machine Learning Lab.,2015:1-3.10 BARZILAI J,BORWEIN J M.Two-point step size gradient methodsJ.IMA Journal of NumericalAnalysis,1988,8(1):141-148.11 LIU Y,WANG X,GUO T D.A Linearly Convergent Stochastic Recursive Gradient Method forConvex OptimizationJ.Optimization Letters,2020,14(8):2265-2283.12 POLYAK B T.Introduction to OptimizationM.New York:Chapman&Hall,1987:138-144.13 BECK A.First-Order Methods in OptimizationM.Philadelphia:Society for Industrial and AppliedMathematics,2017:202-204.14 刘彦,郭田德,韩丛英.一类随机方差缩减算法的分析与改进J.中国科学:数学,2021,51(9):1433-1450.15 NESTEROV Y.Introductory Lectures on Convex Optimization:A Basic CourseM.Boston:Springer,2004.Stochastic Recursive Gradient Algorithm Based on PolyakStep SizeWANG Fusheng,LI Xiaotong(School of Mathematics and Statistics,Taiyuan Normal University,Jinzhong 030619,China)Abstract:In order to minimize the sum of finite smooth convex functions in machine learning,a stochastic recursive gradient algorithm based on Polyak step size(SARAH-Polyak)was proposed bycombining the stochastic recursive gradient algorithm with Polyak step size.The linear convergence of thealgorithm is proved under strong convex and general convex conditions respectively.Experimental resultsshow the effectiveness of SARAH-Polyak algorithm.Key words:Polyak step size;Random recursion;Gradient descent