分块凸-非凹极小极大问题的交替近端梯度算法

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (4): 64-74.doi: 10.15960/j.cnki.issn.1007-6093.2022.04.005

分块凸-非凹极小极大问题的交替近端梯度算法

张慧灵, 徐洋, 徐姿^*

上海大学理学院, 上海 200444

收稿日期:2020-10-26 发布日期:2022-11-28
通讯作者: 徐姿 E-mail:xuzi@shu.edu.cn
基金资助:
国家自然科学基金(Nos. 12071279,11771208), 上海市自然科学基金(No. 20ZR1420600)

Block alternating proximal gradient algorithm for convex-nonconcave minimax problems

ZHANG Huiling, XU Yang, XU Zi^*

College of Sciences, ShanghaiUniversity, Shanghai 200444, China

Received:2020-10-26 Published:2022-11-28

摘要/Abstract

摘要： 本文提出一种单循环分块交替近端梯度算法求解分块凸-非凹的极小极大优化问题。在该算法的每次迭代中, 采用近端梯度法交替更新目标函数中的各个变量。从理论上证明了算法达到ε-稳定点需要的迭代复杂度是O(ε^-4), 这是求解分块凸-非凹的极小极大优化问题的首个带复杂度的单循环算法。

关键词: 极小极大优化问题, 机器学习, 交替近端梯度法

Abstract: This paper proposes a single-loop block-alternating proximal gradient algorithm to solve block convex-nonconcave minimax optimization problems. In each iteration of the algorithm, the proximal gradient method is used to alternately update each variable in the objective function. We have theoretically proved that the algorithm achieves an ε-stationary point in O(ε^-4) iterations. To the best of our knowledge, this is the first time that a single loop algorithm has been proposed to solve a block convexnonconcave minimax optimization problem.

Key words: minimax optimization problem, machine learning, alternating proximal gradient method

中图分类号:

O221.2

张慧灵, 徐洋, 徐姿. 分块凸-非凹极小极大问题的交替近端梯度算法[J]. 运筹学学报, 2022, 26(4): 64-74.

ZHANG Huiling, XU Yang, XU Zi. Block alternating proximal gradient algorithm for convex-nonconcave minimax problems[J]. Operations Research Transactions, 2022, 26(4): 64-74.

参考文献

[1] Goodfellow I, Pouget-Abadie J, Mirza M. Generative adversarial nets[C]//Advances in Neural Information Processing Systems, 2014: 2672-2680.
[2] Sinha A, Namkoong H, Duchi J. Certifiable distributional robustness with principled adversarial training[J]. 2017, arXiv: 1710.10571.
[3] Jordan M I. Artificial intelligence-the revolution hasn’t happened yet[J]. Harvard Data Science Review, 2019, 1(1): 1-9.
[4] Shamma J. Cooperative Control of Distributed Multi-Agent Systems[M]. New Jersey: John Wiley & Sons, 2008.
[5] Mateos G, Bazerque J A, Giannakis G B. Distributed sparse linear regression[J]. IEEE Transactions on Signal Processing, 2010, 58(10): 5262-5276.
[6] 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.
[7] Nesterov Y. Dual extrapolation and its applications to solving variational inequalities and related problems[J]. Mathematical Programming, 2007, 109(2-3): 319-344.
[8] Tseng P. On accelerated proximal gradient methods for convex-concave optimization[EB/OL]. (2008-05-21)[2020-10-20]. https://www.csie.ntu.edu.tw/b97058/tseng/papers/apgm.pdf.
[9] Ouyang Y, Xu Y. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems[J]. Mathematical Programming, 2019, 185: 1-35.
[10] Nouiehed M, Sanjabi M, Huang T, et al. Solving a class of non-convex min-max games using iterative first order methods[C]//Advances in Neural Information Processing Systems, 2019: 14934-14942.
[11] Thekumparampil K K, Jain P, Netrapalli P. Efficient algorithms for smooth minimax optimization[C]//Advances in Neural Information Processing Systems, 2019: 12680-12691.
[12] Lin T, Jin C, Jordan M. Near-optimal algorithms for minimax optimization[J]. 2020, arXiv: 2002.02417.
[13] Lin T, Jin C, Jordan M. On gradient descent ascent for nonconvex-concave minimax problems [C]//International Conference on Machine Learning, 2020: 6083-6093.
[14] Lu S, Tsaknakis I, Hong M, et al. Hybrid block successive approximation for one-sided nonconvex min-max problems: algorithms and applications[J]. IEEE Transactions on Signal Processing, 2020, 68: 3676-3691.
[15] 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]. 2020, arXiv: 2006.02032.
[16] Nesterov Y. Introductory Lectures on Convex Optimization[M]. Berlin: Springer Science & Business Media, 2013.

分块凸-非凹极小极大问题的交替近端梯度算法

Block alternating proximal gradient algorithm for convex-nonconcave minimax problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[2]	陈征, 高岩. 控制系统生存核的逼近算法[J]. 运筹学学报, 2013, 17(4): 24-32.