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

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

Abstract

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

CLC Number:

O221.2

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[2]	WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization [J]. Operations Research Transactions, 2014, 18(3): 1-12.
[3]	CHEN Zheng, GAO Yan. Approximating viability kernel for control systems [J]. Operations Research Transactions, 2013, 17(4): 24-32.