非凸极小极大问题的优化算法与复杂度分析

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

摘要/Abstract

摘要： 非凸极小极大问题是近期国际上优化与机器学习、信号处理等交叉领域的一个重要研究前沿和热点，包括对抗学习、强化学习、分布式非凸优化等前沿研究方向的一些关键科学问题都归结为该类问题。国际上凸-凹极小极大问题的研究已取得很好的成果，但非凸极小极大问题不同于凸-凹极小极大问题，是有其自身结构的非凸非光滑优化问题，理论研究和求解难度都更具挑战性，一般都是NP-难的。重点介绍非凸极小极大问题的优化算法和复杂度分析方面的最新进展。

关键词: 极小极大优化问题, 复杂度分析, 一阶算法, (随机)梯度下降上升算法, 交替梯度投影算法, 非凸优化, 机器学习

Abstract: The non-convex minimax problem is an important research front and hot spot in the cross-fields of optimization, machine learning, signal processing, etc. Some key scientific issues in frontier research directions such as adversarial learning, reinforcement learning, and distributed non-convex optimization, all belong to this type of problem. Internationally, the research on convex-concave minimax problems has achieved good results. However, the non-convex minimax problem is different from the convex-concave minimax problem, and it is a non-convex and non-smooth optimization problem with its own structure, for which, the theoretical analysis and the algorithm design are more challenging than that of the convex-concave minimax problem, and it is generally NPhard. This paper focuses on the latest developments in optimization algorithms and complexity analysis for non-convex minimax problems.

Key words: minimax optimization problem, complexity analysis, first order method, (stochastic) gradient descent ascent algorithm, alternating gradient projection algorithm, nonconvex optimization, machine learning

中图分类号:

O221.2

徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.

XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems[J]. Operations Research Transactions, 2021, 25(3): 74-86.

[1] Nesterov Y. Dual extrapolation and its applications to solving variational inequalities and related problems[J]. Mathematical Programming, 2007, 109(2/3):319-344.
[2] Monteiro R, Svaiter B. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean[J]. SIAM Journal on Optimization, 2010, 20(6):2755-2787.
[3] Juditsky A, Nemirovski A. Solving variational inequalities with monotone operators on domains given by linear minimization oracles[J]. Mathematical Programming, 2016, 156(1/2):221-256.
[4] Facchinei F, Pang J. Finite-Dimensional Variational Inequalities and Complementarity Problems[M]. Berlin:Springer Science & Business Media, 2007.
[5] Von Neumann J, Morgenstern O. Theory of Games and Economic Behavior[M]. Princeton:Princeton University Press, 2007.
[6] Gidel G, Berard H, Vignoud G, et al. A variational inequality perspective on generative adversarial networks[C]//International Conference on Learning Representations, 2019.
[7] Chen X. Global and superlinear convergence of inexact uzawa methods for saddle point problems with nondifferentiable mappings[J]. SIAM Journal on Numerical Analysis, 1998, 35(3):1130-1148.
[8] 袁亚湘. 非线性优化计算方法[M]. 北京:科学出版社,2008.
[9] He B, Yuan X. Convergence analysis of primal-dual algorithms for a saddle-point problem:From contraction perspective[J]. SIAM Journal on Imaging Sciences, 2012, 5(1):119-149.
[10] Chen Y, Lan G, Ouyang Y. Optimal primal-dual methods for a class of saddle point problems[J]. SIAM Journal on Optimization, 2014, 24(4):1779-1814.
[11] Chen Y, Lan G, Ouyang Y. Accelerated schemes for a class of variational inequalities[J]. Mathematical Programming, 2017, 165(1):113-149.
[12] Goodfellow I, Pouget-Abadie J, Mirza M. Generative Adversarial Nets[M]. Cambridge:MIT Press, 2014.
[13] Qian Q, Zhu S, Tang J, et al. Robust optimization over multiple domains[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019:4739-4746.
[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] Sinha A, Namkoong H, Duchi J. Certifiable distributional robustness with principled adversarial training[C]//International Conference on Learning Representations, 2018.
[16] Dai B, Shaw A, Li L. Sbeed:Convergent reinforcement learning with nonlinear function approximation[C]//International Conference on Machine Learning, PMLR, 2018:1125-1134.
[17] Shafieezadeh-Abadeh S, Esfahani P, Kuhn D. Distributionally robust logistic regression[C]//Proceedings of the 28th International Conference on Neural Information Processing Systems, 2015:1576-1584.
[18] Smale S. Mathematical problems for the next century[J]. Mathematical Intelligencer, 1998, 20:7-15.
[19] Hiriart-Urruty J. A new series of conjectures and open questions in optimization and matrix analysis[J]. ESAIM:Control, Optimisation and Calculus of Variations, 2009, 15:454-470.
[20] 10000个科学难题数学编委会. 10000个科学难题:数学卷[M]. 北京:科学出版社,2008.
[21] 胡晓东,袁亚湘,章祥荪. 运筹学发展的回顾与展望[J]. 中国科学院院刊, 2012, (2):145-160.
[22] 王奇超,文再文,蓝光辉,等. 优化算法的复杂度分析[J]. 中国科学:数学,2020, (9):144-209.
[23] Bubeck S. Convex optimization:Algorithms and complexity[J]. Foundations and Trends in Machine Learning, 2015, 8(3/4):231-357.
[24] Daskalakis C, Panageas I. The limit points of (optimistic) gradient descent in min-max optimization[C]//Advances in Neural Information Processing Systems, 2018:9256-9266.
[25] Mazumdar E, Jordan M, Sastry S. On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games[J]. 2019, arXiv:1901.00838.
[26] Jin C, Netrapalli P, Jordan M. What is local optimality in nonconvex-nonconcave minimax optimization?[C]//International Conference on Machine Learning, PMLR, 2020:4880-4889.
[27] Dai Y, Zhang L. Optimality conditions for constrained minimax optimization[J]. CSIAM Transactions on Applied Mathematics, 2020, 1:296-315.
[28] 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.
[29] Nouiehed M, Sanjabi M, Huang T, et al. Solving a class of nonconvex min-max games using iterative first order methods[J]. Advances in Neural Information Processing Systems, 2019:14905-14916.
[30] Nemirovski A. 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.
[31] Auslender A, Teboulle M. Interior projection-like methods for monotone variational inequalities[J]. Mathematical programming, 2005, 104(1):39-68.
[32] Monteiro R, Svaiter B. Complexity of variants of Tseng.s modified FB splitting and Korpelevich.s methods for generalized variational inequalities with applications to saddle point and convex optimization problems[J]. SIAM Journal on Optimization, 2010, 21(4):1688-1720.
[33] Tseng P. On accelerated proximal gradient methods for convex-concave optimization[J/OL]. SIAM Journal on Optimization, (2008-01-23)[2021-03-02]. https://www.csie.ntu.edu.tw/b97058/tseng/papers/apgm.pdf.
[34] 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.
[35] Mertikopoulos P, Zenati H, Lecouat B, et al. Mirror descent in saddle-point problems:Going the extra (gradient) mile[J]. 2018, arXiv:1807.02629.
[36] Rafique H, Liu M, Lin Q, et al. Non-convex min-max optimization:Provable algorithms and applications in machine learning[J]. 2018, arXiv:1810.02060.
[37] Sanjabi M, Ba J, Razaviyayn M, et al. On the convergence and robustness of training gans with regularized optimal transport[C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018:7091-7101.
[38] Sanjabi M, Razaviyayn M, Lee J. Solving non-convex non-concave min-max games under polyak-lojasiewicz condition[J]. 2018, arXiv:1812.02878.
[39] Thekumparampil K, Jain P, Netrapalli P et al. Efficient algorithms for smooth minimax optimization[J]. 2019, arXiv:1907.01543.
[40] Kong W, Monteiro R. An accelerated inexact proximal point method for solving nonconvex concave min-max problems[J]. 2019, arXiv:1905.13433.
[41] Lin T, Jin C Jordan M. Near-optimal algorithms for minimax optimization[J]. 2020, arXiv:2002.02417.
[42] Letcher A, Balduzzi D, Racaniere S, et al. Differentiable game mechanics[J]. Journal of Machine Learning Research, 2019, 20(84):1-40.
[43] Lin T, Jin C, Jordan M. On gradient descent ascent for nonconvex-concave minimax problems[J]. 2019, arXiv:1906.00331.
[44] Jin C, Netrapalli P, Jordan M. Minmax optimization:Stable limit points of gradient descent ascent are locally optimal[J]. 2019, arXiv:1902.00618.
[45] Pan W, Shen J, Xu Z. An efficient algorithm for nonconvex-linear minimax optimization problem and its application in solving weighted maximin dispsersion problem[J]. Computational Optimization and Applications, 2021, 78(1):287-306.
[46] 张慧灵, 徐洋, 徐姿. 分块凸-非凹极小极大问题的交替近端梯度算法[J/OL]. 运筹学学报, (2021-03-15)[2021-02-26]. https://www.ort.shu.edu.cn/CN/abstract/abstract18248.shtml.
[47] Zhang J, Xiao P, Sun R, et al. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[48] Lin Q, Liu M, Rafique H, et al. Solving weakly-convex-weakly-concave saddle-point problems as weakly-monotone variational inequality[J]. 2018, arXiv:1810.10207.
[49] Dang C, Lan G. On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators[J]. Computational Optimization and Applications, 2015, 60(2):277-310.
[50] Yang J, Kiyavash N, He N. Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[51] Menickelly M, Wild S. Derivative-free robust optimization by outer approximations[J]. Mathematical Programming, 2018, 179(1):1-37.
[52] Picheny V, Binois M, Habbal A. A bayesian optimization approach to find nash equilibria[J]. Journal of Global Optimization, 2019, 73(1):171-192.
[53] Roy A, Chen Y, Balasubramanian K, et al. Online and bandit algorithms for nonstationary stochastic saddle-point optimization[J]. 2019, arXiv:1912.01698.
[54] Liu S, Lu S, Chen X, et al. Min-max optimization without gradients:Convergence and applications to adversarialml[C]//International Conference on Machine Learning, 2020, 6282-6293.
[55] Wang Z, Balasubramanian K, Ma S, et al. Zeroth-order algorithms for nonconvex minimax problems with improved complexities[J]. 2020, arXiv:2001.07819.
[56] Xu T, Wang Z, Liang Y, et al. Enhanced first and zeroth order variance reduced algorithms for min-max optimization[J]. 2020, arXiv:2006.09361.
[57] Huang F, Gao S, Pei J, et al. Accelerated zeroth-order and first-order momentum methods from mini to minimax optimization[J]. 2020, arXiv:2008.08170.
[58] Luo L, Ye H, Zhang T. Stochastic recursive gradient descent ascent for stochastic nonconvexstrongly-concave minimax problems[C]//Proceedings of the 33th International Conference on Neural Information Processing Systems, 2020.
[59] Carmon Y, Duchi J, Hinder O, et al. Lower bounds for finding stationary points II:first-order methods[J]. Mathematical Programming, 2021, 185:315-355.

非凸极小极大问题的优化算法与复杂度分析

Optimization algorithms and their complexity analysis for non-convex minimax problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王子琦, 王军霖, 徐姿. 一类非凸-非凹极小极大问题的方差缩减梯度下降上升算法[J]. 运筹学学报（中英文）, 2026, 30(1): 197-206.
[2]	魏佳祯, 边伟. 共识优化算法的研究进展综述[J]. 运筹学学报（中英文）, 2026, 30(1): 1-23.
[3]	谭子琳, 罗洪林. 二阶分裂算法及其应用[J]. 运筹学学报（中英文）, 2025, 29(4): 121-140.
[4]	王福胜, 史鲁玉. 基于Polyak步长的加速临近随机方差缩减算法[J]. 运筹学学报（中英文）, 2024, 28(2): 131-142.
[5]	王祥丰, 李文浩. 机器学习驱动的多智能体路径搜寻算法综述[J]. 运筹学学报, 2023, 27(4): 106-135.
[6]	曾静, 丁若文. 一类带映射差的非凸向量优化问题解的稳定性[J]. 运筹学学报, 2023, 27(3): 121-128.
[7]	彭建文, 雷宏旺. 非凸两分块优化问题的一类惯性对称正则化交替方向乘子法[J]. 运筹学学报, 2023, 27(3): 37-52.
[8]	邵虎, 卓越, 刘鹏杰, 邵枫. 城市交通流量估计的运筹学方法[J]. 运筹学学报, 2023, 27(2): 27-48.
[9]	张慧灵, 徐洋, 徐姿. 分块凸-非凹极小极大问题的交替近端梯度算法[J]. 运筹学学报, 2022, 26(4): 64-74.
[10]	吕袈豪, 罗洪林, 杨泽华, 彭建文. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用[J]. 运筹学学报, 2022, 26(2): 16-30.
[11]	胡佳, 郭田德, 韩丛英. 小批量随机块坐标下降算法[J]. 运筹学学报, 2022, 26(1): 1-22.
[12]	叶加青, 陈倩竹, 胡海平. 梯度Q-线性收敛的光滑凸极小化的一阶算法[J]. 运筹学学报, 2021, 25(1): 96-106.
[13]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[14]	张勇, 叶万洲. 一种求解弹性l_2-l_q正则化问题的算法[J]. 运筹学学报, 2016, 20(4): 11-20.
[15]	陈征, 高岩. 控制系统生存核的逼近算法[J]. 运筹学学报, 2013, 17(4): 24-32.