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.
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
.
DOI: 10.15960/j.cnki.issn.1007-6093.2022.04.005
[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.
