非凸-凹极小极大问题的双尺度交替梯度下降上升算法.pdf

第 卷第期 年月太 原 师 范 学 院 学 报(自然科学版)J OUR NA LO FT A I YUANNO 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 M a r 收稿日期:基金项目:山西省基础研究计划(自由探索类)面上项目();太原师范学院研究生教育创新项目(S Y Y J S Y C )作者简介:王静(),女,山西运城人,在读硕士研究生,主要从事最优化理论与方法研究通信作者:王福胜,教授,E m a i l:f s w a n g c o m非凸凹极小极大问题的双尺度交替梯度下降上升算法王静,王福胜,覃媛媛(太原师范学院 数学与统计学院,山西 晋中 )摘要针对一类非凸(强)凹极小极大问题,基于双尺度梯度下降上升算法,用交替梯度更新来替代同步梯度更新,从而提出了一种新算法双尺度交替梯度下降上升算法通过数值实验结果表明,新算法在MN I S T数据集上的分类准确率明显高于原算法,从而验证了新算法的有效性 关键词机器学习;非凸极小极大问题;梯度下降上升算法;单循环算法;交替梯度更新 文章编号 ()中图分类号O 文献标识码A 引言极小极大问题的理论研究一直是数学、统计、经济学和计算机科学几十年研究的重点凸凹极小极大问题由于其对应的变分不等式是单调算子,其相关的最优性理论和算法比较成熟,目前关于凸凹极小极大优化问题的研究已取得很好的成果 近年来,由于机器学习的发展进步,极小极大优化问题引起了学术界极大的关注,越来越多的模型可以被表述为极小极大问题,例如,生成式对抗网络,对抗性训练,鲁棒优化和原始对偶强化学习,然而这些问题模型大多是非凸的,使用深度神经网络表述会极大地复杂化其优化问题的理论和数值分析目前关于非凸凹极小极大问题有一些相关的理论成果在非凸凹设置中,多循环算法受到了广泛的关注 ,有些算法在这类设置中获得了很好的复杂度结果尽管它们的理论性结果很好,但多循环算法实现起来比较复杂,对于在机器学习和信号处理的分布式训练中常见的具有多分块结构的极小极大问题难以求解,所以在实践中不实用单循环算法仍然是最先进的 ,目前关于单循环算法的研究成果很少,最简单的单循环算法是梯度下降上升(G D A)算法 G D A算法可以通过同步或交替的渐变更新来进行,因此可以分为交替梯度下降上升算法和同步梯度下降上升算法同步梯度下降上升算法是梯度下降方法运用到极大极小优化问题的直接推广,它同时更新x和y,即xt xtxxf(xt,yt)yt ytyyf(xt,yt),相比之下,交替梯度下降上升算法中迭代xt 和yt 是按顺序计算的,即xt xtxxf(xt,yt)yt ytyyf(xt,yt),交替算法使用第一步得到的信息来更新第二个变量,每一次迭代都是两个半更新的组合,这也使得其理论分析变得更加复杂,其中x,y是步长L i n等人 于 年提出了t w o t i m e s c a l eG D A和S G D A算法,同时更新x和y,在非凸强凹条件下,两种算法得到函数()m a xyYf(,y)的稳定点的迭代复杂度分别为O()和O(),其中为条件数在非凸凹条件下,两种算法分别需要O()和O()的梯度计算 B o等人 于 年针 对弱凸(强)凹问题提出了邻近交替梯度下降上升算法(p r o x i m a l a l t e r n a t i n gG D A),交替更新x和y,在非凸强凹条件下,在确定性和随机性情况下算法得到函数()m a xyYf(,y)的稳定点的迭代复杂度分别为O()和O(),其中为条件数在非凸凹条件下,在确定性和随机性情况下算法分别需要O()和O()的梯度计算 X u等人 于 年提出了交替梯度投影(AG P)算法,交替更新x和y,并证明了对于非凸凹极小极大问题,获得f(x,y)的稳定点的迭代复杂度为O(),对于非凸强凹极小极大问题,其迭代复杂度可以达到O()当x为凸集且y为凸紧集时,年Z h a n g等人 提出了s m o o t h e d G D A算法,交替更新x和y,该算法对于一类特殊的非凸凹目标函数f(x,y)mifi(x)yi,可以达到O()的迭代复杂度,而对于一般的目标函数,其迭代复杂度为O()可以发现最近关于非凸凹极小极大问题的单循环算法大都在G D A算法或其变体的基础上使用交替的渐变更新,那么G D A算法基础上的交替梯度更新是否比同步梯度更新有更好的收敛性效果?目前仅有文献 在理论上证明了A l t G D A对于强凸强凹极小极大问题具有近似最优的局部收敛速度,而S i m G D A的收敛速度要慢得多,这是第一个表明A l t G D A的收敛速度比S i m G D A的收敛速度超过一个常数的结果本文改进了t w o t i m e s c a l eG D A和S G D A算法中的同步梯度更新为交替梯度更新,从实验结果上证明了t w o t i m e s c a l eG D A算法的交替梯度更新比同步梯度更新有更好的效果 算法在本节中,首先给出了问题的描述并回顾了t w o t i m e s c a l eG D A和S G D A算法,之后利用交替更新,提出了新算法t w o t i m e s c a l eAG D A和S AG D A算法 问题的描述考虑下列光滑极小极大问题m i nxRmm a xyYf(x,y),其中f:RmRnR在x上非凸但在y上为(强)凹,且Y为凸紧集 t w o t i m e s c a l eG D A和S G D A算法为了构造新算法,首先回顾一下t w o t i m e s c a l eG D A和S G D A算法(如算法,所示),该算法使用了同步梯度更新算法:t w o t i m e s c a l eG D A第步给定初始迭代点(x,y),步长x,y,令t;第步更新x和y:xt xtxxf(xt,yt),yt PY(ytyyf(xt,yt)第步当算法满足终止准则时,停止;否则,令t:t,返回第步算法:t w o t i m e s c a l eS G D A第步给定初始迭代点(x,y),步长x,y,批量大小M,令t;第步更新x和y:xt xtxMMiGx(xt,yt,i),yt PYyty(MMiGy(xt,yt,i)第步当算法满足终止准则时,停止;否则,令t:t,返回第步 t w o t i m e s c a l eAG D A和S AG D A算法在本小结中,提出了t w o t i m e s c a l eAG D A和S AG D A算法,该算法与t w o t i m e s c a l eG D A和S G D A算法的主要区别是使用交替梯度更新代替同步梯度更新第期王静,等:非凸凹极小极大问题的双尺度交替梯度下降上升算法算法:t w o t i m e s c a l eAG D A第步给定初始迭代点(x,y),步长x,y,令t;第步更新x和y:xt xtxxf(xt,yt),yt PY(ytyyf(xt,yt)第步当算法满足终止准则时,停止;否则,令t:t,返回第步算法:t w o t i m e s c a l eS AG D A第步给定初始迭代点(x,y),步长x,y,批量大小M,令t;第步更新x和y:xt xtxMMiGx(xt,yt,i),yt PYyty(MMiGy(xt ,yt,i)第步当算法满足终止准则时,停止;否则,令t:t,返回第步 数值实验本小节通过数值实验验证了所提出的t w o t i m e s c a l eAG D A和S AG D A算法的有效性所有的试验均在P y t h o n计算环境下的具有 G B内存的I n t e l C o r e i 处理器上进行实验是在iNi的数据样本上训练带有l范数攻击和惩罚参数的经验W a s s e r s t e i n鲁棒模型(WRM),形式为:m i nxm a xyiNiYNNi(l(x,yi)yii)正如S i n h a等人 所证明的,当选择足够大的,l(x,yi)yii是强凹的本文对对抗扰动的设置,和神经网络分类器的设置与S i n h a等人 相同在MN I S T数据集上训练神经网络分类器,该框架包括,和卷积滤波器层,E L U激活,然后是完全连接层和s o f t m a x输出当 时,问题是一个非凸强凹极小极大问题;当 时,问题是一个非凸凹极小极大问题我们设置t w o t i m e s c a l eAG D A和t w o t i m e s c a l eG D A算法中x ,y ,其中x轴代表迭代次数,y轴代表分类准确率,图中虚线和实线分别对应了t w o t i m e s c a l eAG D A和t w o t i m e s c a l eG D A算法实验结果如图、图所示图 t w o t i m e s c a l eAG D A和t w o t i m e s c a l eG D A在WRM模型上的性能比较,其中 图 t w o t i m e s c a l eAG D A和t w o t i m e s c a l eG D A在WRM模型上的性能比较,其中 上述实验结果中,图、图分别表示了在非凸强凹和非凸凹条件下,t w o t i m e s c a l eAG D A和t w o t i m e s c a l eG D A算法在MN I S T数据集上的分类准确率,从图中可以看出,t w o t i m e s c a l eAG D A算法的分类准确率明显高于t w o t i m e s c a l eG D A算法,有效地验证了新算法的可行性太 原 师 范 学 院 学 报(自然科学版)第 卷 小结本文基于t w o t i m e s c a l eG D A和S G D A算法,用交替梯度更新代替同步梯度更新,提出了新算法t w o t i m e s c a l eAG D A和S AG D A算法最后,通过数值实验结果表明t w o t i m e s c a l eAG D A算法在MN I S T数据集上均优于t w o t i m e s c a l eG D A算法,从而验证了新算法的可行性和有效性参考文献:OUYAN GYY,XUYY L o w e r c o m p l e x i t yb o u n d s o f f i r s t o r d e rm e t h o d s f o r c o n v e x c o n c a v eb i l i n e a r s a d d l e p o i n t p r o b l e m sJ M a t h e m a t i c a lP r o g r a mm i n g,():N EM I R OV S K IA P r o x m e t h o dw i t h r a t e o f c o n v e r g e n c eO(/t)f o r v a r i a t i o n a l i n e q u a l i t i e sw i t hL i p s c h i t z c o n t i n u o u sm o n o t o n eo p e r a t o r sa n ds m o o t hc o n v e x c o n c a v es a d d l ep o i n tp r o b l e m sJ S I AMJ o u r n a l o nO p t i m i z a t i o n,():G O O D F E L L OWI J,P OUG E T A B A D I EJ,M I R Z A M,e t a l G e n e r a t i v e a d v e r s a r i a l n e t sCP r o c e e d i n g so f t h e t h I n t e r n a t i o n a lC o n f e r e n c eo 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,M o n t r e a l:M I TP r e s s,:A R J OV S KY M,C H I N T A L AS,B O T T OUL W a s s e r s t e i ng e n e r a t i v ea d v e r s a r i a l n e t w o r k sCP r o c e e d i n g so f t h e t hI n t e r n a t i o n a lC o n f e r e n c eo nM a c h i n eL e a r n i n g,S y d n e y:J ML R o r g,:MA D R YA,MAK E L OVA,S C HM I D TL,e ta l T o w a r d sd e e pl e a r n i n gm o d e l sr e s i s t a n t t oa d v e r s a r i a la t t a c k sCI C L R C o n f e r e n c e,V a n c o u v e r:I C L R,:B E N T A LA,E LGHAOU IL,N EM I R OV S K IA R o b u s to p t i m i z a t i o nM P r i n c e t o n:P r i n c e t o nU n i v e r s i t yP r e s s,D USS,C HE NJS,L ILH,e t a l S t o c h a s t i cv a r i a n c er e d u c t i o nm e t h o d s f o rp o l i c ye v a l u a t i o nCP r o c e e d i n g so f t h e t hI n t e r n a t i o n a lC o n f e r e n c eo nM a c h i n eL e a r n i n g,S y d n e y:J ML R o r g,:YANGMJ,NA C HUMO,D A IB,e t a l O f f p o l i c ye v a l u a t i o nv i a t h e r e g u l a r i z e d l a g r a n g i a nCP r o c e e d i n g s o f t h e t h I n t e r n a t i o n a lC o n f e r e n c eo 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,V a n c o u v e r:C u r r a nA s s o c i a t e s I n c,:THE KUMP R AMP I LKK,J A I NP,N E T R A P A L L IP,e ta l E f f i c i e n ta l g o r i t h m sf o rs m o o t hm i n i m a xo p t i m i z a t i o nCP r o c e e d i n g so f t h e r dI n t e r n a t i o n a lC o n f e r e n c eo 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,R e dH o o k:C u r r a nA s s o c i a t e sI n c,:L I NTY,J I NC,J O R D AN MI N e a r o p t i m a l a l g o r i t h m s f o r m i n i m a xo p t i m i z a t i o nCP r o c e e d i n g so fT h i r t yT h i r dC o n f e r e n c eo nL e a r n i n gT h e o r y,G r a z:PML R,:K ONG WW,MON T E I R O RDC A na c c e l e r a t e di n e x a c tp r o x i m a lp o i n tm e t h o df o rs o l v i n gn o n c o n v e x c o n c a v em i n m a xp r o b l e m sJ S I AMJ o u r n a l o nO p t i m i z a t i o n,():O S T R OV S K I ID M,L OWY A,R A Z AV I YAYN M E f f i c i e n ts e a r c ho ff i r s t o r d e rN a s h e q u i l i b r i ai nn o n c o n v e x c o n c a v es m o o t hm i n m a xp r o b l e m sJ S I AMJ o u r n a l o nO p t i m i z a t i o n,():N OU I EHE D M,S AN J A B IM,HUANGTJ,e ta l S o l v i n gac l a s so fn o n c o n v e xm i n m a xg a m e su s i n gi t e r a t i v ef i r s to r d e rm e t h o d sCP r o c e e d i n g so f t h e r dI n t e r n a t i o n a lC o n f e r e n c eo 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,R e dH o o k:C u r r a nA s s o c i a t e s I n c,:R A F I QU EH,L I U MR,L I NQH,e t a l N o n c o n v e xm i n m a xo p t i m i z a t i o n:p r o v a b l e a l g o r i t h m s a n da p p l i c a t i o n s i nm a c h i n el e a r n i n gE B/O L()网络访问日期缺失 h t t p s:a r x i v o r g/a b s/v L I NTY,J I NC,J O R D AN MI O ng r a d i e n td e s c e n ta s c e n t f o rn o n c o n v e x c o n c a v em i n i m a xp r o b l e m sCP r o c e e d i n g so ft h e t hI n t e r n a t i o n a lC o n f e r e n c eo nM a c h i n eL e a r n i n g,V i r t u a l:J ML R o r g,:B O RI,B HM A A l t e r n a t i n gp r o x i m a l g r a d i e n ts t e p sf o r(s t o c h a s t i c)n o n c o n v e x c o n c a v em i n i m a xp r o b l e m sE B/O L()网络访问日期缺失 h t t p s:a r x i v o r g/a b s/v XUZ,Z HAN G HL,XU Y,e ta l Au n i f i e ds i n g l e l o o pa l t e r n a t i n gg r a d i e n tp r o j e c t i o na l g o r i t h mf o r n o n c o n v e x c o n c a v ea n dc o n v e x n o n c o n c a v em i n i m a xp r o b l e m sE B/O L()网络访问日期缺失 h t t p s:a r x i v o r g/a b s/v Z HAN GJW,X I A OPJ,S UNRY,e ta l As i n g l e l o o ps m o o t h e dg r a d i e n td e s c e n t a s c e n ta l g o r i t h mf o r n o n c o n v e x c o n c a v em i n m a xp r o b l e m sCP r o c e e d i n g so f t h e t hI n t e r n a t i o n a lC o n f e r e n c eo 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,V a n c o u v e r:C u r r a nA s s o c i a t e s I n c,:Z HAN GGD,WANGYH,L E S S A R DL,e t a l N e a r o p t i m a l l o c a l c o n v e r g e n c e o f a l t e r n a t i n gg r a d i e n t d e s c e n t a s c e n t f o r m i n i m a xo p t i m i z a t i o nCP r o c e e d i n g so f t h e t hI n t e r n a t i o n a lC o n f e r e n c eo nA r t i f i c i a l I n t e l l i g e n c ea n dS t a t i s t i c s,V a l e n c i a:PML R,:S I NHAA,NAMK O ON G H,D U C H IJ C e r t i f i a b l ed i s t r i b u t i o n a lr o b u s t n e s sw i t hp r i n c i p l e da d v e r s a r i a l t r a i n i n gE B/O L()网络访问日期缺失 h t t p s:a r x i v o r g/a b s/v 第期王静,等:非凸凹极小极大问题的双尺度交替梯度下降上升算法T w o t i m e S c a l eA l t e r n a t i n gG r a d i e n tD e s c e n tA s c e n tA l g o r i t h mf o rN o n c o n v e x C o n c a v eM i n i m a xP r o b l e m sWA N GJ i n g,WA N GF u s h e n g,Q I NY u a n y u a n(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,J i n z h o n g ,C h i n a)A b s t r a c tF o r a c l a s s o f n o n c o n v e x(s t r o n g l y)c o n c a v em i n i m a xp r o b l e m s,t h i sp a p e rb a s e do nt h e t w o t i m e s c a l eg r a d i e n td e s c e n ta s c e n ta l g o r i t h m,r e p l a c i n gt h es i m u l t a n e o u sg r a d i e n tu p d a t ew i t ha l t e r n a t i n gg r a d i e n tu p d a t e,t h u sp r o p o s i n gan e wa l g o r i t h mt w o t i m e s c a l ea l t e r n a t i n gg r a d i e n td e s c e n t a s c e n t a l g o r i t h m T h er e s u l t so fn u m e r i c a l e x p e r i m e n t ss h o wt h a t t h ec l a s s i f i c a t i o na c c u r a c yo f t h en e wa l g o r i t h mo nt h eMN I S Td a t a s e t i ss i g n i f i c a n t l yh i g h e r t h a nt h a to f t h eo r i g i n a l a l g o r i t h m,w h i c hw e l l v e r i f i e s t h ee f f e c t i v e n e s so f t h en e wa l g o r i t h mK e yw o r d sm a c h i n e l e a r n i n g;n o n c o n v e xm i n i m a xp r o b l e m;g r a d i e n t d e s c e n t a s c e n t a l g o r i t h m;s i n g l e l o o pa l g o r i t h m;a l t e r n a t i n gg r a d i e n tu p d a t e(上接第页)L I NZC,C HE N M M,WULQ,e t a l T h ea u g m e n t e dL a g r a n g em u l t i p l i e rm e t h o d f o r e x a c t r e c o v e r yo f c o r r u p t e d l o w r a n km a t r i c e sE B/O L()网络访问日期缺失 h t t p s:a r x i v o r g/a b s/v C A I JF,O S HE RS F a s t s i n g u l a rv a l u e t h r e s h o l d i n gw i t h o u ts i n g u l a rv a l u ed e c o m p o s i t i o nJ M e t h o d sa n dA p p l i c a t i o n so fA n a l y s i s,():HUY,Z HANGDB,L I UJ,e t a l A c c e l e r a t e d s i n g u l a r v a l u e t h r e s h o l d i n g f o rm a t r i xc o m p l e t i o nCP r o c e e d i n g s o f t h e t hA CMS I G K D DI n t e r n a t i o n a lC o n f e r e n c eo nK n o w l e d g eD i s c o v e r ya n dD a t aM i n i n g N e w Y o r k:A s s o c i a t i o nf o rC o m p u t i n gM a c h i n e r y,:WAN GZ,L A IMJ,L UZS,e t a l O r t h o g o n a l r a n k o n em a t r i xp u r s u i t f o r l o wr a n km a t r i xc o m p l e t i o nJ S I AMJ o u r n a l o nS c i e n t i f i cC o m p u t i n g,():A A AF e a s i b l eD i r e c t i o n a p p r o x i m a t i n gM e t h o df o rM a t r i xC o m p l e t i o nL IX i a o l i,Z H O UH u a r e n,WA N GC h u a n l o n g(A r m yE n g i n e e r i n gU n i v e r s i t yo fP L A,N a n j i n g ,C h i n a;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,J i n z h o n g ,C h i n a)A b s t r a c tT h i sp a p e rp r o p o s ean e wf e a s i b l ed i r e c t i o n a p p r o x i m a t i n gm e t h o df o rm a t r i xc o m p l e t i o nb a s e do nt h es u b s p a c e a p p r o x i m a t i n ga l g o r i t h m A n di t i su s e dq u a d r a t i cp r o g r a mt og e t t h ec l o s e s t f e a s i b l em a t r i x T h e i t e r a t i v em a t r i c e sg e n e r a t e db y t h en e wa l g o r i t h mi sg r a d u a l l yt oa p p r o x i m a t i n gt h e f e a s i b l em a t r i x,a n ds a t i s f y i n gt h ec o n v e r g e n c e s t op r o d u c e t h eb e s t c o m p l e t i o nm a t r i x T h e ni ts h o w st h i sn e wa l g o r i t h mi sm o r ee f f e c t i v et h a nt h ea u g m e n t e dL a g r a n g em u l t i p l i e ra l g o r i t h mf o rm a t r i xc o m p l e t i o nb yn u m e r i c a l e x p e r i m e n t s K e yw o r d sm a t r i xc o m p l e t i o n;f e a s i b l ed i r e c t i o n a p p r o x i m a t i n g;s u b s p a c e a p p r o x i m a t i n g;q u a d r a t i cp r o g r a m;f e a s i b l em a t r i x太 原 师 范 学 院 学 报(自然科学版)第 卷