基于Polyak步长的快速临近随机方差缩减算法.pdf

第 卷第期 年月太 原 师 范 学 院 学 报(自然科学版)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步长的快速临近随机方差缩减算法史鲁玉,王福胜(太原师范学院 数学与统计学院,山西 晋中 )摘要针对信号和图像处理、统计学和机器学习中的正则化风险最小化问题,把快速临近随机方差缩减梯度算法(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步长;方差缩减;机器学习 文章编号 ()中图分类号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 中随机选择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 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)该算法实现了以下复杂度:(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()复杂度()和()有一种特殊的关系,即若条件数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和强凸性参数在一个未知的利普希茨常数的情况下,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(vkGk),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)FIk(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 与最优解的距离的上界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外循环迭代中,已经计算出全梯度,所以计算量并没有增加,相比于其他算法增加了准确率当前,由于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:;第二步:计算一个全梯度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 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步长的快速临近随机方差缩减算法敛速度,验证了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 条件下的收敛速度,包括个子图(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 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,其中子图(b)和(d)使用不同批量的数据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算法从图中可以看出,本文提出的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算法图分析了F I S T A P r o x S V R G P o l y a k算法在不同数据集上的求解目标函数时步长的变化趋势,其中,x轴代表迭代次数,y轴代表步长,图中红色、蓝色和绿色实线分别对应不同的初始步长,虚线分别对应不同的固定步长两个子图(a)和(b)分别是F I S T A P r o x S V R G P o l y a k算法在数据集上i j c n n 和w a在b 上的测试结果从图中可以看出,本文提出的F I S T A P r o x S V R G P o l y a k算法的步长最终收敛于最优步长的邻域,表明对于不同的初始步长,对算法的收敛性能影响不大太 原 师 范 学 院 学 报(自然科学版)第 卷图F I S TA P r o x S V R G P o l y a k和带有固定步长的F I S TA P r o x S V R G算法的分类准确率对比图F I S TA 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 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 B B算法,新算法的收敛速度更快,并不受选取的初始步长影响参考文献:S HA L E V S HWA R T ZS,Z HAN GT P r o x i m a lS t o c h a s t i cD u a lC o o r d i n a t eA s c e n tJ M a t h e m a t i c s,D O I:/a r X i v S HA L E V S HWA R T ZS,Z HAN GT S t o c h a s t i cd u a l c o o r d i n a t ea s c e n tm e t h o d s f o r r e g u l a r i z e d l o s sJ T h eJ o u r n a l o fM a 第期史鲁玉,等:基于P o l y a k步长的快速临近随机方差缩减算法c h i n eL e a r n i n gR e s e a r c h,():S HA L E V S HWA R T ZS,Z HAN GT A c c e l e r a t e dm i n i b a t c hs t o c h a s t i cd u a l c o o r d i n a t ea s c e n tCA d v a n c e s i nN e u r a l I n f o r m a t i o nP r o c e s s i n gS y s t e m s(N I P S )R e dH o o k:C u r r a nA s s o c i a t e s I n c,:S HA L E V S HWA R T ZS,Z HAN GT A c c e l e r a t e dp r o x i m a l s t o c h a s t i cd u a l c o o r d i n a t ea s c e n t f o rr e g u l a r i z e dl o s sm i n i m i z a t i o nJ P r o c e e d i n g so fM a c h i n eL e a r n i n gR e s e a r c h,():R OUXN,S CHM I D T M,B A C HF As t o c h a s t i c g r a d i e n tm e t h o dw i t ha ne x p o n e n t i a l c o n v e r g e n c e r a t e f o r f i n i t e t r a i n i n g s e t sCA d v a n c e s i nN e u r a l I n f o r m a t i o nP r o c e s s i n gS y s t e m s(N I P S )R e dH o o k:C u r r a nA s s o c i a t e s I n c,:J OHN S ONR,Z HAN G T A c c e l e r a t i n gs t o c h a s t i cg r a d i e n td e s c e n tu s i n gp r e d i c t i v ev a r i a n c er e d u c t i o nCA d v a n c e si nN e u r a l I n f o r m a t i o nP r o c e s s i n gS y s t e m s(N I P S )R e dH o o k:C u r r a nA s s o c i a t e s I n c,:X I A OL,Z HAN GT AAP r o x i m a lS t o c h a s t i cG r a d i e n tM e t h o dw i t hP r o g r e s s i v eV a r i a n c eR e d u c t i o nJ S i a mJ o u r n a lo nO p t i m i z a t i o n,()D O I:/N E S T E R OVY I n t r o d u c t o r y l e c t u r e so nc o n v e xo p t i m i z a t i o n:Ab a s i cc o u r s eM B o s t o n:S p r i n g e r,N E S T E R OVY G r a d i e n tm e t h o d s f o rm i n i m i z i n gc o m p o s i t eo b j e c t i v e f u n c t i o n:C o r ed i s c u s s i o np a p e r /R L o u v a i n l a N e u v e:C a t h o l i cU n i v e r s i t yo fL o u v a i n,B E C KA,T E B O U L L EM F a s tg r a d i e n t b a s e da l g o r i t h m s f o rc o n s t r a i n e dt o t a l v a r i a t i o n i m a g ed e n o i s i n ga n dd e b l u r r i n gp r o b l e m sJ I E E ET r a n s a c t i o n so nI m a g eP r o c e s s i n g,():YAN GZ,WAN GC,Z HAN GZM,e t a l A c c e l e r a t e d s t o c h a s t i c g r a d i e n t d e s c e n tw i t hs t e p s i z e s e l e c t i o n r u l e sJ S i g n a l P r o c e s s i n g,:N I T AN D AA S t o c h a s t i cp r o x i m a l g r a d i e n td e s c e n tw i t ha c c e l e r a t i o nt e c h n i q u e sCA d v a n c e s i nN e u r a l I n f o r m a t i o nP r o c e s s i n gS y s t e m s(N I P S )R e dH o o k:C u r r a nA s s o c i a t e s I n c,:P O L YAKBT I n t r o d u c t i o nt oo p t i m i z a t i o nM N e wY o r k:O p t i m i z a t i o nS o f t w a r e,:李蝶基于P o l y a k步长的方差缩减算法J科技资讯,():【责任编辑刘宇民】P o l y a kS t e pS i z e s f o raF a s tP r o x i m a l S t o c h a s t i cG r a d i e n tM e t h o dw i t hP r o g r e s s i v eV a r i a n c eR e d u c t i o nS H IL u y u,WA N GF u s h e n g(S c h o o l o fM a t h e m a t i c sa n dS t a t i s t i c s,T a i y u a nN o r m a lU n i v e r s i t y,S h a n x i J i n z h o n g ,C h i n a)A b s t r a c tT os o l v er e g u l a r i z e dr i s km i n i m i z a t i o np r o b l e m s i ns i g n a l/i m a g ep r o c e s s i n g,s t a t i s t i c sa n dm a c h i n e l e a r n i n g,w ep r o p o s e an e wf a s t p r o x i m a l s t o c h a s t i cg r a d i e n tm e t h o dw i t hp r o g r e s s i v ev a r i a n c er e d u c t i o nc a l l e dF I S T A P r o x S V R G P o l y a k T h en e wa l g o r i t h mc o m b i n e st h ef a s tp r o x i m a l s t o c h a s t i cg r a d i e n tm e t h o dw i t hp r o g r e s s i v ev a r i a n c er e d u c t i o nw i t haP o l y a ks t e ps i z e m e t h o d N u m e r i c a le x p e r i m e n t sc o m p a r e d F I S T A P r o x S V R G P o l y a k a n d F I S T A P r o x S V R Ga l g o r i t h m s,a n dt h er e s u l t ss h o wt h a t t h ep r o p o s e da l g o r i t h mi s f e a s i b l ea n de f f e c t i v e K e yw o r d sP o l y a ks t e ps i z e;v a r i a n c er e d u c t i o n;m a c h i n e l e a r n i n g太 原 师 范 学 院 学 报(自然科学版)第 卷