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

doi:10.15960/j.cnki.issn.1007-6093.2024.01.002

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (1): 18-28.doi: 10.15960/j.cnki.issn.1007-6093.2024.01.002

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

徐洋¹, 王军霖¹, 徐姿¹^,*()

1. 上海大学理学院数学系, 上海 200444

收稿日期:2021-09-24 出版日期:2024-03-15 发布日期:2024-03-15
通讯作者: 徐姿 E-mail:xuzi@shu.edu.cn
基金资助:
国家自然科学基金(12071279);上海市自然科学基金(20ZR1420600)

A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems

Yang XU¹, Junlin WANG¹, Zi XU¹^,*()

1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Received:2021-09-24 Online:2024-03-15 Published:2024-03-15
Contact: Zi XU E-mail:xuzi@shu.edu.cn

摘要/Abstract

摘要：

本文提出了一种镜像梯度下降梯度上升算法来求解单边相对光滑的非凸-凹极小极大问题。在算法的每次迭代中, 我们采用镜像梯度下降步来更新相对光滑的变量, 采用梯度上升投影步来更新目标函数中光滑的变量。本文在理论上证明了算法收敛到$\varepsilon$-近似一阶稳定点的迭代复杂度是$\mathcal{O}\left( \varepsilon^{-4} \right)$。

关键词: 非凸-凹极小极大问题, 相对光滑, 镜像梯度法

Abstract:

In this paper, we propose a mirror descent gradient ascent algorithm to solve one side relatively smooth nonconvex-concave minimax optimization problems. At each iteration of the proposed algorithm, a mirror descent step is performed to update the relatively smooth variable, while a gradient ascent projection step is used to update the smooth variable alternately. We also prove that the iteration complexity of the proposed algorithm is $\mathcal{O}\left( \varepsilon ^{-4} \right)$ to achieve an $\varepsilon$-approximate first-order stationary point.

Key words: nonconvex-concave minimax optimization problem, relatively smooth, mirror gradient method

中图分类号:

O221.2

徐洋, 王军霖, 徐姿. 单边相对光滑非凸-凹极小极大问题的镜像梯度算法[J]. 运筹学学报（中英文）, 2024, 28(1): 18-28.

Yang XU, Junlin WANG, Zi XU. A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems[J]. Operations Research Transactions, 2024, 28(1): 18-28.

参考文献 18

1	Sinha A, Namkoong H, Du C. Certifiable distributional robustness with principled adversarial training[C]//International Conference on Learning Representations, 2018.
2	Goodfellow I , Pouget-Abadie J , Mirza M .Generative adversarial nets[J].Advances in Neural Information Processing Systems,2014,2672-2680.
3	Zhang Y, Xiao L. Stochastic primal-dual coordinate method for regularized empirical risk minimization[C]//International Conference on Machine Learning, 2015: 353-361.
4	Nemirovski A .Prox-method with rate of convergence O(1/$t$) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[J].SIAM Journal on Optimization,2004,15(1):229-251. doi: 10.1137/S1052623403425629
5	Nesterov Y .Dual extrapolation and its applications to solving variational inequalities and related problems[J].Mathematical Programming,2007,109(2/3):319-344.
6	Lin T, Jin C, Micheal J. Near-optimal algorithms for minimax optimization[C]//Conference on 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 Signal Processing,2020,68,3676-3691. doi: 10.1109/TSP.2020.2986363
8	Xu Z , Zhang H , Xu Y , et al.A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems[J].Mathematical Programming,2023,201(1-2):635-706. doi: 10.1007/s10107-022-01919-z
9	Zhang J , Xiao P , Sun R , et al.A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems[J].NeurIPS,2020,33,7377-7389.
10	徐姿, 张慧灵.非凸极小极大问题的优化算法与复杂度分析[J].运筹学学报,2021,25(3):1-13.
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 optimization[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 methods and applications[J].SIAM Journal on Optimization,2018,28(1):333-354. doi: 10.1137/16M1099546
15	Ghadimi S , Lan G , Zhang H .Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization[J].Mathematical Programming,2016,155,267-305. doi: 10.1007/s10107-014-0846-1
16	Nesterov Y .Introductory Lectures on Convex 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 online allocation problems[J].Operations Research,2023,71(1):101-119. doi: 10.1287/opre.2021.2242
18	Ibrahim M, Konar A, Hong M. Mirror-prox SCA algorithm for multicast beamforming and antenna selection[C]//IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications, 2018.

[1]	程郁琨, 韩鑫, 陈修杨, 张昭. 基于网络环境的若干组合优化博弈问题研究[J]. 运筹学学报（中英文）, 2024, 28(2): 1-29.
[2]	张家棋, 李觉友. 一类自适应梯度裁剪的差分隐私随机梯度下降算法[J]. 运筹学学报（中英文）, 2024, 28(2): 47-57.
[3]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[4]	叶明露, 黄明. 连续非单调变分不等式的一种惯性投影算法[J]. 运筹学学报（中英文）, 2024, 28(2): 81-92.
[5]	王福胜, 史鲁玉. 基于Polyak步长的加速临近随机方差缩减算法[J]. 运筹学学报（中英文）, 2024, 28(2): 131-142.
[6]	吕雪征, 马梦郁. 链图的距离特征值[J]. 运筹学学报（中英文）, 2024, 28(1): 112-120.
[7]	白富生, 兰秘. 带隐藏约束昂贵黑箱问题的自适应代理优化方法[J]. 运筹学学报（中英文）, 2024, 28(1): 89-100.
[8]	李颖涵, 童小娇, 杨柳. 基于矩不确定模糊集的分布鲁棒风险-回报优化模型研究[J]. 运筹学学报（中英文）, 2024, 28(1): 77-88.
[9]	孟辛晴, 张文星. 求解一类线性等式约束凸优化问题的加速方法[J]. 运筹学学报（中英文）, 2024, 28(1): 1-17.
[10]	王晓. 非凸约束优化的随机近似算法[J]. 运筹学学报, 2023, 27(4): 153-165.
[11]	王祥丰, 李文浩. 机器学习驱动的多智能体路径搜寻算法综述[J]. 运筹学学报, 2023, 27(4): 106-135.
[12]	刘永鸿, 韩丛英, 郭田德. 基于深度学习的指纹方向场提取算法[J]. 运筹学学报, 2023, 27(4): 1-19.
[13]	张莹, 敬新奇, 王长军. 一个双拟阵下的最优定价存在性猜想[J]. 运筹学学报, 2023, 27(4): 166-174.
[14]	姜波. 非负正交约束优化问题的理论、算法及应用[J]. 运筹学学报, 2023, 27(4): 136-152.
[15]	邵梦真, 余长君. 最优控制问题的直接法综述[J]. 运筹学学报, 2023, 27(4): 81-105.

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

A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 18

相关文章 15

编辑推荐

Metrics

本文评价