单边相对光滑非凸-凹极小极大问题的镜像梯度算法.pdf
《单边相对光滑非凸-凹极小极大问题的镜像梯度算法.pdf》由会员分享,可在线阅读,更多相关《单边相对光滑非凸-凹极小极大问题的镜像梯度算法.pdf(11页珍藏版)》请在咨信网上搜索。
1、2024年3月Mar.,2024DOI:10.15960/ki.issn.1007-6093.2024.01.002单边相对光滑非凸-凹极小极大问题的镜像梯度算法徐洋1王军霖1徐姿1,摘要本文提出了一种镜像梯度下降梯度上升算法来求解单边相对光滑的非凸-凹极小极大问题。在算法的每次迭代中,我们采用镜像梯度下降步来更新相对光滑的变量,采用梯度上升投影步来更新目标函数中光滑的变量。本文在理论上证明了算法收敛到-近似一阶稳定点的迭代复杂度是(e-4)。关键词非凸-凹极小极大问题,相对光滑,镜像梯度法中图分类号0 2 2 1.22010数学分类号9 0 C47A mirror descent gradi
2、ent ascent algorithm for oneside relatively smooth nonconvex-concaveminimax optimization problemsXU YanglWANG JunlinlXU Zil,tAbstract In this paper,we propose a mirror descent gradient ascent algorithm tosolve one side relatively smooth nonconvex-concave minimax optimization problems.Ateach iteratio
3、n of the proposed algorithm,a mirror descent step is performed to update therelatively smooth variable,while a gradient ascent projection step is used to update thesmooth variable alternately.We also prove that the iteration complexity of the proposedalgorithm is O(e-4)to achieve an e-approximate fi
4、rst-order stationary point.Keywords nonconvex-concave minimax optimization problem,relatively smooth,mirror gradient methodChinese Library Classification O221.22010 Mathematics Subject Classification 90C47考虑如下的非凸-凹极小极大优化问题:CEXyEy其中和是紧凸集,f(,)关于是非凸函数,关于是凹函数。非凸极小极大优化问题在机器学习和很多其他领域上都有很广泛的应用,包括对抗性学习中的鲁棒优
5、化、经验风险最小化问题以及强化学习等 1-3。对于凸-凹极小极大优化问题,目前已有许多算法可以求解这类问题,比如Nemirovski等 4 提出的mirror-prox算法以及Nesterov 等 5 提出的对偶外推算法等,均可以证明算收稿日期:2 0 2 1-0 9-2 4*基金项目:国家自然科学基金(No.12071279),上海市自然科学基金(No.20ZR1420600)1.上海大学理学院数学系,上海 2 0 0 444;Department of Mathematics,College of Sciences,Sh a n g h a iUniversity,Shanghai 200
6、444,China+通信作者E-mail:这筹学学报(中英文)Operations Research Transactionsminmaxf(a,y),第2 8 卷第1期Vol.28No.1(1)1期法求到e-近似鞍点的迭代复杂度是(e-1),且该复杂度在一般情形下是最优的。对于一般的非凸极小极大优化问题,鞍点可能不存在;即使鞍点存在,一般情形下求解鞍点也是NP-难的。已有研究结果大多退而求其次,寻找问题的-近似一阶稳定点,求解方法主要有嵌套循环算法和单循环算法两类。Lin等 6 提出一种可以求解光滑非凸-凹极小极大问题的加速算法,且证明了算法的迭代复杂度是(e-2.5),这是目前所知已有嵌套
7、循环算法中复杂度最好的算法。对于单循环算法,Lu等 7 提出了一种 HiBSA算法求解非凸-凹极小极大问题,可以证明算法得到-近似一阶稳定点的迭代复杂度是O(s-4),但算法关于y的子问题的求解难度没有计算在内。Xu等 8 提出了一种交替梯度投影(AGP)算法,可以证明求解非凸-凹极小极大问题得到 s-近似一阶稳定点的迭代复杂度也是O(e-4),且每次迭代只需计算两个投影子问题。Zhang 等 9 提出了一种 Smoothed-GDA算法,得到-近似一阶稳定点的迭代复杂度也可以证明为(e-4),且对于特殊的非凸-线性的情形,迭代复杂度为O(e-2)。更多的对于非凸极小极大问题的最新研究成果可参
8、见近期的综述文章 10 。Tsengl11 提出的加速镜像梯度算法和Hou等 12 提出的小批量镜像梯度法均可以求解凸-凹极小极大问题,且算法收敛到 s-近似鞍点的选代复杂度为(e-1)。H u a n g 等 13)有效地将镜像梯度法应用到了非凸强化学习的问题中,并证明了算法迭代复杂度为(s-4)。此前关于相对光滑的非凸-凹极小极大问题的优化算法很少。本文提出一种镜像梯度下降梯度上升算法求解相对光滑的非凸-凹极小极大问题,并且证明了在一般的假设下,算法收敛到-近似一阶稳定点的迭代复杂度为(e-4)。本文安排如下:第1节提出了镜像梯度下降梯度上升算法;第2 节证明了算法的收敛性以及迭代复杂度;
9、最后是全文总结。1镜像梯度下降梯度上升算法在本节中,我们提出镜像梯度下降梯度上升算法来求解单边相对光滑的非凸-凹极小极大问题。在给出具体的算法之前,我们先给出如下定义:定义1对强凸系数为h的可微强凸函数h:R,定义其Bregman距离为D(a1,a2):=h(1)-h(a2)-(Vh(a2),1-a2),Va1,2 E X,显然,D(a1,2)12且D(1,2)=0当且仅当=2。定义2 14 若对于任意的1,2E,,存在常数 L0,有f(c1,y)f(a2,y)+(Vaf(c2,y),a1-a2)+LD(a1,a2),则称函数f(,y)在上相对 h()是L光滑的。定义3定义上的广义投影和f(,
10、y)关于的广义投影梯度 15 如下:a+(a,y):=arg min(Vaf(a,),u-a)+D(u,),VGa(a,y):=(-+(a,y)。特别地,当=Rn,Bregman距离D中h(a)=lla时,+(a,y)即为欧氏空间中的投影且 VGa(a,y)=Vf(c,y)。单边相对光滑非凸-凹极小极大问题的镜像梯度算法19(2)(3)20在镜像梯度下降梯度上升算法的每一步迭代过程中,沿方向使用镜像梯度下降步。在更新y时,我们考虑如下目标函数的正则化函数:于(k+1,)=(h+1,)-号 2其中ck0。沿y方向,对于使用投影梯度上升步。算法具体步骤如下:算法1(镜像梯度下降梯度上升算法)步骤1
11、输入1,y1,1,p,令k=1,步骤2 计算k并更新ak:Ch+1=arg min(Vaf(ch,yk),a-ak)+hD(a,ak),aE.X步骤3更新yk:yk+11=arg max(Vuf(ah+1,yk),y-yk)-lly-yllyEy(uk+Vuf(c+1.y)步骤4当算法满足某种收敛准则时,终止;否则,令k:=k 1,回到步骤2。接下来我们分析算法1收敛到一阶稳定点的迭代复杂度。我们考虑目标函数在上的广义投影梯度 15 和上的投影梯度,稳定点定义如下:定义4在算法1的每一步迭代中,问题(1)的稳定点定义为:VGa(ak,yk)VG(ck,yk):=L p(us-P(ys+Vuf(
12、a,r)其中Ga(ak,k)如定义3所示,P为投影算子。为了表示方便,定义VG=VG(ak,,k)。定义5在算法1的每一步迭代中,问题(1)对于于(,9)的稳定点定义为:VG(k,k):=其中VGa(ak,k)如定义3所示,P为投影算子。为了表示方便,定义VG=VG(k,k),(VGk)a:=VGa(ck,yk),(VGh):=p(k-Py(徐洋,王军霖,徐姿VGa(ak,k)p(uk-Py(us+Vf(ck w)(+uf(ck,yk)28卷(4)(5)(6)(7)1期单边相对光滑非凸-凹极小极大问题的镜像梯度算法21(8)2复杂度分析假设1f(,y)是连续可微的函数,且存在常数 L0,L2
13、1 0,使得对任意a,Ex和y,yey,有IVyf(,y)-Vyf(a,y)ll L21 ll-all,IIVf(a,y)-Vuf(a,y)ll Ly lly-gll。假设2【ck是非负单调递减序列。引理 1 对任意 a1,C2,3 E X,有(V1D(1,2),2-3)=D(a3,a1)-D(a2,c1)-D(3,a2),其中V1D(a1,2)表示 D(1,c2)关于第一个变量的梯度。证明由定义1,可得D(3,1)-D(a2,1)-D(3,c2)=(Vh(c1)-Vh(c2),22-3),而 ViD(1,2)=Vh(ac1)-Vh(2),证毕。下面我们分析辅助函数于(,g)关于的下降量:引理
14、2 考虑由算法1产生的序列【(ak,yk)。若假设1成立,Vk,La,有证明由式(4)的最优性条件,有(Vaf(ch,k)+hViD(ak+1,Ck),a-Ch+1)0。代入=k,并由引理1可得(Vaf(ak,Yk),ak+1-Ck)k(ViD(ah+1,ak),Ck-Ch+1)结合定义1 2 和上式,以及kLc,可以得到f(ch+1,yk)-f(ck,yk)=f(ah+1 s)-(ak,Un)+C-,_kl(Vaf(ah,k),ah+1-ak)+LaD(ah+1,ak)+Ck-1-Ck-(k-Lr)D(ck+1,Ck)+2222=hD(ak+1,Ck+1)-D(ak,C+1)-hD(ah+1
15、,ak)-BkD(k+1,Ck)。22Ck-1-2(9)(11)22由于(,y)的定义及假设1 2,有/(c,yh)-Vuf(ak,k-1)l=Iuf(ah,yk)-Vuf(ch,k-1)-Ch-(y-h-1)l其中 L,=Ly+C1。引理3(16)中定理2.1.12)于(ak,9)关于y是Lf-光滑,ck-1-强凹,则(Vuf(ak,yk)-Vf(ch k-1),k-k-1)1Vuf(ak,y)-Vuf(ck,k-1)L,+Ck-1和引理2 类似,下面我们分析辅助函数从于(ak+1,yk+1)到于(ak,y k)的变化趋势:引理4考虑由算法1生成的序列(ak,Uu)。若假设1 2 成立,p,
16、则(ak+1,k+1)-f(ak,yk)(B%-La)h _ L21)22ck证明由式(5)的最优性条件,VyEy,Vk1,我们有(Vf(ch+1,yk)-p(yk+1-yk),y-h+1)0。在式(12)中取y=yk,可以得到(Vf(ah+1,yk)-p(yh+1-yk),k-yh+1)0。在式(12)中,用k-1代替k并取y=yh+1,得到(Vf(ach,Yk-1)-p(yk-Yk-1),h+1-yk)0,移项得(Vu(ak,k-1),yh+1-k)p(yk-yk-1,Yh+1-ys)。由于(,y)关于y的强凹性和式(15),得到(ak+1,yh+1)-f(ak+1,yk)(Vuf(ah+
17、1,yk),h+1-yk)-%2(Vuf(ak+1,yk)-V(ak,yk),h+1-yk)+(Vuf(ck,k)-Vuf(ack,k-1),k-yk-1)+(Vuf(ak,yk)-Vuf(ack,yk-1),Uh+1)徐洋,王军霖,徐姿(Ly+Ch-1)l k-yk-1ll L,lyk-yk-ll,Ilah+1-a:/l2+228卷Ck-1Il/k-/k-1 I2。(10)Lu+Ck-1Ilyk+1-ykll(12)(13)(14)(15)(16)1期其中U+1=k+1k(u k y k-1)。下面我们将分别给出上式右端内积项的上界。首先由f(ac,y)的定义,假设12 以及 Cauchy-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单边 相对 光滑 极小 极大 问题 梯度 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。