单边相对光滑非凸-凹极小极大问题的镜像梯度算法.pdf

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 gradient 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 iteration 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 first-order stationary point.Keywords nonconvex-concave minimax optimization problem,relatively smooth,mirror gradient methodChinese Library Classification O221.22010 Mathematics Subject Classification 90C47考虑如下的非凸-凹极小极大优化问题：CEXyEy其中和是紧凸集，f(,）关于是非凸函数，关于是凹函数。非凸极小极大优化问题在机器学习和很多其他领域上都有很广泛的应用，包括对抗性学习中的鲁棒优化、经验风险最小化问题以及强化学习等 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 200444,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)，这是目前所知已有嵌套循环算法中复杂度最好的算法。对于单循环算法,Lu等 7 提出了一种 HiBSA算法求解非凸-凹极小极大问题，可以证明算法得到-近似一阶稳定点的迭代复杂度是O（s-4)，但算法关于y的子问题的求解难度没有计算在内。Xu等 8 提出了一种交替梯度投影（AGP）算法，可以证明求解非凸-凹极小极大问题得到 s-近似一阶稳定点的迭代复杂度也是O(e-4)，且每次迭代只需计算两个投影子问题。Zhang 等 9 提出了一种 Smoothed-GDA算法，得到-近似一阶稳定点的迭代复杂度也可以证明为(e-4)，且对于特殊的非凸-线性的情形,迭代复杂度为O(e-2)。更多的对于非凸极小极大问题的最新研究成果可参见近期的综述文章 10 。Tsengl11 提出的加速镜像梯度算法和Hou等 12 提出的小批量镜像梯度法均可以求解凸-凹极小极大问题，且算法收敛到 s-近似鞍点的选代复杂度为(e-1)。H u a n g 等 13)有效地将镜像梯度法应用到了非凸强化学习的问题中,并证明了算法迭代复杂度为(s-4)。此前关于相对光滑的非凸-凹极小极大问题的优化算法很少。本文提出一种镜像梯度下降梯度上升算法求解相对光滑的非凸-凹极小极大问题，并且证明了在一般的假设下，算法收敛到-近似一阶稳定点的迭代复杂度为(e-4)。本文安排如下：第1节提出了镜像梯度下降梯度上升算法；第2 节证明了算法的收敛性以及迭代复杂度；最后是全文总结。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(,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输入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(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 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)关于的下降量：引理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,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，则(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+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-Schwarz不等式,有(Vf(ak+1,yh)-Vuf(ak,k),h+1-yk)=(Vuf(ah+1,yk)-Vuf(ch,yk),ah+1-Ck)-(ch-Ch-1)(yk,Uk+1-yh)2ckCk-1 二Ck22ckyk+1-yk由 Cauchy-Schwarz 不等式,(Vyf(ch,yk)-Vf(ah,k-1),Uh+1)由引理3中得到的性质可以推出,(Vuf(ak,k)-Vuf(ck,k-1),yh-yk-1)1-/Vuf(ach,k)-Vu(ak,yk-1)12Lu+Ck-11L,+Ck-11Vf(ak,k)-uf(ak,h-1)12。结合假设靠 和下面的等式单边相对光滑非凸-凹极小极大问题的镜像梯度算法Ck2232Ck-1-Ck(I(l k;+1 12-Il k/l12)。2I/(ah,k)-V(ak,h-1)I2+9ll u+l/。L+Ck-1yk-yk-1ll2(17)(18)Ck-(19)p(yk+1-yk,yk-yk-1):1l k:+1-k:l22lyk-yk-1l(20)1将式(17)(2 0)代入式(16)中，且根据于(,9)的定义，可以得到F(ck+1,h+1)-f(ak+1,yk)Ck-1-llyk一yk-11/2+2ck将式(2 1)和引理2 的式(8)相加即可得到不等式(11)。引理5考虑由算法1生成的序列【(ak，y k)。若假设1 2 成立，定义Fk+1:=f(achk+1,Jk+1)+若yk+1。(2 1)2口4p4pck3pIlk+1-killCk11Ck+1CkCk+1+C18p2(22)24则Vk2,证明由式(13)和式(15)，我们有p(uh+1,yh+1-yk)(Vuf(ah+1,yk)-V,f(ak,k-1),h+1-yk),与定理4中的式（16)类似，式(2 4)可以写为p(uk+1,Yk+1-k)(Vuf(ah+1,yk)-V(ch,yk),h+1-yk)+(Vuf(ack,yh)-Vuf(ack,yk-1),Uh+1)+(Vuf(ck,yk)-Vuf(ch,Yk-1),k-yk-1)。与式(17)(2 0)的证明类似,由式(2 5)可以得到徐洋，王军霖，徐姿Fk+1-Fk(k-La)h _ L2122ckCk-1 Ck228卷8pL31Ck+1(chk)2Ck-140Cklyk+1-klI2CkCk+1(23)(24)(25)2Uk:-lyk-yk-CkCk-1-lyk+1Ckyk/2+Vf(ak,yk)22p-V,f(ak,yk-1)I21L+Ck-1lyk-yk-1l2。L,+Ck-1因c1L,可得Ck-1+再由p1,将式(2 6)化简得到P-CkIlk+1-yill22Ck-1Ilyk-yk-1l22Ck221IV(ah,yk)-Vu(ak,h-1)12Ck-12L,221Ilk+1-kk:I2(26)Cklyk+1-kll(27)1期在上面式子的左右两边同时乘只，我们有4pCkCk-1pckCk将式(2 8)和引理4中的式（11)相加,由f(ah+1,k+1)-f(ack,yk)(Bk-La)MhL38pL3lk+1-k:122ckCk-1Ck24pCk-再利用Fk+1的定义，得到Fk+1-Fk(k-La)h2Ck-1-2下面我们给出该算法的代复杂度：定理1考虑由算法1生成的序列（h，U k)。若假设1 2 成立，且令c%=部，定义T(e):=mink/IIG(ah,yk)e,k 2,则对任意给定的0,T(e)max单边相对光滑非凸-凹极小极大问题的镜像梯度算法lyk+1ykyk2ck(ch.)2Ck-1Ck(T-1)L2id2d3pe2258pL31(ck)ykCk+1CkCk8pLlak+1-:llCkCk+140，整理得到1CkCkIlyk-k-1 l。(2 8)CkCk-18pIlyk+1-ykillIlyk+1-yklIlyk+1-ykll54其中 1,:=maxll|y e),C1d2=F2-Fo+2d3=max(di,V2(r-1)L2i3p2,b1=min(2(-1/aL,),Fo:=i(36C2minvFk,di为常数。k2(c,y)Exxy)26证明若Ch=取Bk=La+16pTL31hCkMh(ck),Qh=(k-La)h _k2依据上述关系，引理5的结论可以表示如下:ll/h+1-Ci/2+2Fs-Fk+1+Ck-,cCklyk+1l2由于(,y)的定义，我们很容易得到IIVGkl-II/VGllckll ykll。由算法1中的更新方式和定义3可以得到再根据 yk+1=Py(s+Vu(ch+1,k),有其中，第二个不等式成立是由于P的非扩张性。由于(ch-1Ch)2(ch-1-Ch)(ck-1+Ck)=e-1c，再用 Cauchy-Schwarz不等式将式(30)和式(31)结合起来,得到/G(+3 21)/+2/+lu+(3ci-1-3)u。(3(32)因为当足够大时，k和是同阶的，所以存在d1使得Vk1,P+3L31di(k:)2由式(33)，式(32）可以改写为I/VGil/2 di(ak)/h+1-/l+3p?lyk+1-y/l/+(3c-1-3ck)lul/。定义bEm1因为 b）是单调递减序列，所以有bkbk-1。在式(34）左右两边同时乘bk，再结合式(2 9)，可以得到Ck-1-bl/VGAll24256p4S4T(e)max T(y4(37)T()1121/VkVT(e)-1,结合式(37)，可以得到k=2(8(T-1)L2id2d3pe22560,则ck=部，因此clull，从而存在T(e)满足2p8(T-1)L2id2d3maxp&2225654+1y4使得IIVGkllIVGill+ckllyll号+号=。定理1 表明,算法1 的迭代复杂度是(s-4)。3总结本文提出镜像梯度下降梯度上升算法求解相对光滑下的非凸-凹极小极大问题，同样可以用于求解光滑的凸-凹极小极大问题，包括已有文献中考虑的矩阵博奔、线性回归、在线分配以及通信中的天线选择等问题 1 1-1 2,1 7-1 8 。在算法的每次迭代中，我们采用镜像梯度下降步更新相对光滑的变量，用梯度上升投影步更新目标函数中的光滑变量。通过分析辅助函数于(,9）的变化趋势，在理论上证明了算法收敛到目标函数s-近似一阶稳定点的迭代复杂度为(e-4)。28徐洋，王军霖，徐姿28卷参考文献1 Sinha A,Namkoong H,Du C.Certifiable distributional robustness with principled adversarialtraining C/International Conference on Learning Representations,2018.2 Goodfellow I,Pouget-Abadie J,Mirza M.Generative adversarial nets J.Adances in NeuralInformation Processing Systems,2014:2672-2680.3 Zhang Y,Xiao L.Stochastic primal-dual coordinate method for regularized empirical riskminimization C/International Conference on Machine Learning,2015:353-361.4 Nemirovski A.Prox-method with rate of convergence O(1/t)for variational inequalities withLipschitz continuous monotone operators and smooth convex-concave saddle point problemsJ.SIAM Journal on Optimization,2004,15(1):229-251.5 Nesterov Y.Dual extrapolation and its applications to solving variational inequalities andrelated problems J.Mathematical Programming,2007,109(2/3):319-344.6 Lin T,Jin C,Micheal J.Near-optimal algorithms for minimax optimization C/Conferenceon Learning Theory,2020:2738-2779.7 Lu S,Tsaknakis I,Hong M,et al.Hybrid block successive approximation for one-sided non-convex min-max problems:Algorithms and applications J.IEEE Transactions on SignalProcessing,2020,68:3676-3691.8 Xu Z,Zhang H,Xu Y,et al.A unified single-loop alternating gradient projection algorithm fornonconvex-concave and convex-nonconcave minimax problems J.Mathematical Programming,2023,201(1-2):635-706.9 Zhang J,Xiao P,Sun R,et al.A single-loop smoothed gradient descent-ascent algorithm fornonconvex-concave min-max problems J.NeurIPS,2020,33:7377-7389.10徐姿，张慧灵.非凸极小极大问题的优化算法与复杂度分析 J.运筹学学报，2 0 2 1,2 5(3)：1-1 3.11 Tseng P.On accelerated proximal gradient methods for convex-concave optimization EB/OL.(2008-05-21)2021-08-09.https:/www.csie.ntu.edu.tw/b97058/tseng/papers/apgm.pdf.12 Hou C,Thekumparampil K,Fanti G.Efficient algorithms for federated saddle point optimiza-tion EB/OL.(2021-02-12)2021-08-09.arXiv:2102.06333.13 Huang F,Gao S,Heng H.Bregman gradient policy optimization EB/OL.(2021-06-23)2021-08-09.arXiv:2106.12112.14 Lu H,Freund M,Nesterov Y.Relatively-smooth convex optimization by first-order methodsand applications J.SIAM Journal on Optimization,2018,28(1):333-354.15 Ghadimi S,Lan G,Zhang H.Mini-batch stochastic approximation methods for nonconvexstochastic composite optimization J.Mathematical Programming,2016,155:267-305.16 Nesterov Y.Introductory Lectures on Convea Optimization M.New York:Springer Science&Business Media,2013.17 Balseiro S R,Lu H,Mirrokni V.The best of many worlds:Dual mirror descent for onlineallocation problems J.Operations Research,2023,71(1):101-119.18 Ibrahim M,Konar A,Hong M.Mirror-prox SCA algorithm for multicast beamforming andantenna selection C/IEEE 19th International Workshop on Signal Processing Advances inWireless Communications,2018.