基于Polyak步长的随机递归梯度算法.pdf
《基于Polyak步长的随机递归梯度算法.pdf》由会员分享,可在线阅读,更多相关《基于Polyak步长的随机递归梯度算法.pdf(9页珍藏版)》请在咨信网上搜索。
1、应用数学MATHEMATICA APPLICATA2024,37(1):280-288基于Polyak步长的随机递归梯度算法王福胜,李晓桐(太原师范学院数学与统计学院,山西 晋中 030619)摘要:针对机器学习中一类有限光滑凸函数和的最小化问题,将随机递归梯度算法和Polyak步长结合,提出基于Polyak步长的随机递归梯度算法(SARAH-Polyak).分别在强凸和一般凸条件下证明了算法的线性收敛性.实验结果表明SARAH-Polyak算法的有效性.关键词:Polyak步长;随机递归;梯度下降中图分类号:O224AMS(2010)主题分类:90C15;90C25;90C30文献标识码:A
2、文章编号: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).之后,研究者
3、提出了随机梯度下降(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)
4、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-Li
5、pschitz连续的,即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 Evt1
6、2+(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+
7、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 2
8、k)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+k
9、L32+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-Lipsc
10、hitz连续的,那么对于任何 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若
11、假设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
12、 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)的Li
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 Polyak 步长 随机 递归 梯度 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。