基于Polyak步长的快速临近随机方差缩减算法.pdf
《基于Polyak步长的快速临近随机方差缩减算法.pdf》由会员分享,可在线阅读,更多相关《基于Polyak步长的快速临近随机方差缩减算法.pdf(6页珍藏版)》请在咨信网上搜索。
1、第 卷第期 年月太 原 师 范 学 院 学 报(自然科学版)J OUR NA LO FT A I YUANN O RMA LUN I V E R S I T Y(N a t u r a lS c i e n c eE d i t i o n)V o l N o S e p 收稿日期:基金项目:山西省基础研究计划(自由探索类)面上项目()作者简介:史鲁玉(),女,山东菏泽人,太原师范学院数学与统计学院在读研究生,主要从事最优化理论与方法研究通信作者:王福胜,教授,E m a i l:f s w a n g o c m基于P o l y a k步长的快速临近随机方差缩减算法史鲁玉,王福胜(太原师范
2、学院 数学与统计学院,山西 晋中 )摘要针对信号和图像处理、统计学和机器学习中的正则化风险最小化问题,把快速临近随机方差缩减梯度算法(F I S T A P r o x S V R G)和P o l y a k步长方法相结合,得到一种新的快速临近随机方差缩减梯度算法通过数值实验将新算法F I S T A P r o x S V R G P o l y a k与已有的两种算法F I S T A P r o x S V R G B B、F I S T A P r o x S V R G进行比较,结果表明新算法是可行有效的 关键词P o l y a k步长;方差缩减;机器学习 文章编号 ()中图分类
3、号O 文献标识码A 引言在信号和图像处理、统计和机器学习中出现的许多优化问题可以表述为随机复合优化(S C O)问题,形式如下:m i nxRdP(x)F(x)R(x)()其中F:RdR是光滑凸函数,即F(x)nnifi(x),并且RRdR是一个相对简单的可以不可微的凸函数为解决问题(),经常采用临近梯度下降(P G D)算法,可以用以下更新规则来描述:xk p r o xkR(xkkF(xk),k,其中p r o x是临近算子,定义为p r o xR(y)a r gm i nxRdxyR(x)算法P G D的一个随机变体是随机临近梯度下降算法(S P G D)该算法在每次迭代时,需要从,n
4、中随机选择ik,并进行以下更新:xkp r o xkR(xkkfik(xk)算法S P G D相对于P G D的优点是:在每次迭代中,S P G D只需要计算单个梯度fik(xk)相比之下,P G D的每次迭代都会计算n个梯度因此,每次迭代的S P G D的计算成本是P G D的n倍为了改进随机(临近)梯度下降,我们需要采取一种方差缩减技术,它允许我们采取更大的学习率最近,有几篇论文针对问题()的各种特殊情况提出了这类方差缩减方法在fi(x)是L 光滑,R(x)是强凸的情况下,S h a l e v S h w a r t z和Z h a n g,提出了一个临近随机对偶坐标上升算法(P r o
5、 x S D C A);同时,S h a l e v S h w a r t z和Z h a n g还提出了算法S D C A,的加速变体 L eR o u x等提出了一个随机平均梯度算法(S AG),其中fi(x)为L 光滑,R(x)这些方法均达到了线性收敛速度然而,算法S D C A和S AG需要存储所有的梯度,因此在一般问题中需要存储(n d)尽管对于线性预测问题,可以简化为(n),但这些方法可能不适用于更复杂和大规模的问题最近,J o h n s o n和Z h a n g提出了随机方差缩减梯度算法(S V R G),其中fi(x)是L 光滑,F(x)是强凸,和R(x)该算法实现了以下
6、复杂度:(n)l o g()其中,条件数L此外,这种方法不需要存储所有的梯度 X i a o和Z h a n g提出了算法S V R G的临近变体,称为P r o x S V R G,它也达到了相同的复杂度 P r o x S V R G方法在每次迭代中,随机选 取ik,n,然后依次计算F(x)nnifik(x),Gk fik(xk)fik(x)F(x),xkp r o xkR(xk kGk)另一种求解问题()的有效方法是由N e s t e r o v,提出的加速临近梯度下降算法(A P G)该算法通过找到一个精确的解,实现了以下复杂度:nl o g()复杂度()和()有一种特殊的关系,即若
7、条件数n,则复杂度()小于()另一方面,我们可以知道算法A P G的复杂度更依赖于条件数近几年,N i t a n d a 提出了加速小批量P r o x S V R G(A c c P r o x S V R G)方法,该方法在小批量中结合了N e s t e r o v的加速方法和临近随机方差缩减梯度(P r o x S V R G)方法他证明了在适当的小批量大小条件下,算法A c c P r o x S V R G的复杂度比算法P r o x S V R G和N e s t e r o v的加速方法更有效但是在A c c P r o x S V R G算法中,参数k依赖于利普希茨常数L和
8、强凸性参数在一个未知的利普希茨常数的情况下,B e c k和T e b o u l l e 提出了使用b a c k t r a c k i n g估计最优步长受这一差距的影响,Y a n gZ等 在小批量中加入了F I S T A和P r o x S V R G,从而生成了另一种新的A S G D方法,即F I S T A P r o x S V R G算法在介绍F I S T A P r o x S V R G算法之前,首先简要介绍F I S T A的迭代方案对于任何初始点vxRd和t,F I S T A方案包括以下步骤来解决问题():kxktktk(xkxk),xkp r o xR(vk
9、Gk),tktk通过比较F I S T A迭代方案和N e s t e r o v的加速方案,可以清楚地看到F I S T A用tktk替换参数k,其中参数tk易于访问,如上述迭代所示 算法描述在构造新算法之前,本节先回顾F I S T A P r o x S V R G算法(参考文献 )以下给F I S T A P r o x S V R G算法的基本框架:第一步:给定已知步长,外循环迭代次数T,内循环迭代数m,样本数n,小批量数bn 以及初始点x,s:;第二步:计算一个全梯度gsnninfi(x),令xxs,vxx,t;第三步:随机选取一个大小为b的子集Ik,n,计算GkFIk(vk)FI
10、k(xk)gs,xkp r o xR(vkGk),tktk,kk,转第四步;第四步:如果km,转第五步;否则转第三步;第五步:更新xsxm;第六步:令ss,若sT,则停止;否则转第二步 P o l y a k步长P o l y a k 提出的P o l y a k步长普遍用于次梯度法假设要求解以下的无约束优化问题:m i nxRdf(x)式中,f是凸但可能非光滑函数假定在xk处的次梯度f(xk)是可以计算的次梯度法有形式:xk xkkf(xk)f(xk),k,kk 式中,k趋于,k的和是无穷的太 原 师 范 学 院 学 报(自然科学版)第 卷对于凸函数,在第k步极小化迭代点xk 与最优解的距离
11、的上界Q():xk xQ()式中,Q()xkxf(xk)f(x)f(xk)故ka r gm i nQ()f(xk)f(x)f(xk)因为f(x)f,所以值f使得构造不包含任何参数的次梯度法的如下变体成为可能:xk xkf(xk)ff(xk)f(xk)因此,P o l y a k步长为:kf(xk)ff(xk),f(xk),f(xk)在这种情况下,步长依赖于fm i nxf(x)的估计在一些应用中,f的值是已知的(或者为),该方法可以不用估计直接使用现有的随机算法中P o l y a k步长使用的是随机梯度或是部分梯度,而本文使用的是全梯度在F I S T A P r o x S V R G外循
12、环迭代中,已经计算出全梯度,所以计算量并没有增加,相比于其他算法增加了准确率当前,由于P o l y a k步长具有较好的性质,李蝶等 将随机方差缩减算法(S V R G)与P o l y a k步长相结合,提出了算法S V R G P o l y a k,并获得较好的数值效果受其启发,本文考虑将P o l y a k步长规则与F I S T A P r o x S V R G算法相结合构成一个新的算法F I S T A P r o x S V R G P o l y a k,其框架为:第一步:给定已知步长,外循环迭代次数T,内循环迭代数m,样本数n,小批量数bn 以及初始点x,s:;第二步:
13、计算一个全梯度gsnninfi(x),令xxs,vxx,t;第三步:计算P o l y a k步长:kf(xk)ff(xk),f(xk),f(xk);第四步:随机选取一个大小为b的子集Ik,n,计算GkFIk(vk)FIk(xk)gs,xkp r o xsR(vksGk),tktk,vkxktktk(xkxk),kk,转第五步;第五步:如果km,转第六步;否则转第三步;第六步:更新xsxm;第七步:令ss,若sT,则停止;否则转第二步 数值实验在本节中,我们将F I S T A P r o x S V R G P o l y a k算法应用到求解以下模型:m i nxRdP(x)nnil o
14、g(e x p(biaTix)xx所有实验均采用fi(x)l o g(e x p(biaTix)x和R(x)x其中(ai,bi)niRd,n是给定的训练样本集,和是两个正则化参数同时,所有的实验均在P y t h o n计算环境下进行实验所用的数据集均在L I B S VM网站下载,如表所示表数据集信息数据集训练集大小测试集大小数据集维度i j c n n w a 实验包括三个部分:首先,对比了F I S T A P r o x S V R G P o l y a k算法与F I S T A P r o x S V R G B B算法的收第期史鲁玉,等:基于P o l y a k步长的快速临近
15、随机方差缩减算法敛速度,验证了F I S T A P r o x S V R G P o l y a k的有效性;其次,对比了F I S T A P r o x S V R G P o l y a k与F I S T A P r o x S V R G算法的分类准确率;最后,测试了F I S T A P r o x S V R G P o l y a k算法关于不同的初始步长变化趋势所有的实验结果如图到图所示图对比了F I S T A P r o x S V R G P o l y a k和F I S T A P r o x S V R G B B算法在b 和b 条件下的收敛速度,包括个子图(
16、a),(b),(c)和(d)分别对应使用数据i j c n n 和w a 在所有子图中,x轴代表迭代次数,y轴代表目标残差损失图中红色、蓝色和绿色实线分别对应于带有不同初始步长的F I S T A P r o x S V R G P o l y a k算法,虚线分别对应于带有固定步长的F I S T A P r o x S V R G B B算法从图中可以看出,本文提出的新算法F I S T A P r o x S V R G P o l y a k收敛速度比带有固定步长的算法F I S T A P r o x S V R G B B快,并且当选择不同的初始步长时,F I S T A P r
17、o x S V R G P o l y a k算法的收敛性能不受影响,同时可以看出使用P o l y a k步长的优点是使得新算法对于步长的选取更加容易图F I S T A P r o x S V R G P o l y a k和带有固定步长的F I S T A P r o x S V R G算法的残差损失对比图对比了F I S T A P r o x S V R G P o l y a k和F I S T A P r o x S V R G算法在b 和b 条件下求解目标函数的分类准确率,包括个子图(a),(b),(c)和(d),其中子图(a)和(c)使用不同批量的数据i j c n n,其中
- 配套讲稿:
如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。