An Alternating Gradient Projection Algorithm with Momentum for Nonconvex-Concave Minimax Problems

doi:10.1007/s40305-024-00540-5

Journal of the Operations Research Society of China ›› 2026, Vol. 14 ›› Issue (2): 632-652.doi: 10.1007/s40305-024-00540-5

Previous Articles Next Articles

An Alternating Gradient Projection Algorithm with Momentum for Nonconvex-Concave Minimax Problems

Jue-You Li¹, Tao Xie²

1 School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China;
2 Big Data & Intelligence Engineering School, Chongqing College of International Business and Economics, Chongqing 401520, China

Received:2023-05-09 Revised:2024-03-05 Online:2026-06-30 Published:2026-07-06
Contact: Jue-You Li E-mail:lijueyou@cqnu.edu.cn
Supported by:
This work was partially supported by the National Key R&D Program of China (No. 2023YFA1011303), the National Natural Science Foundation of China (Nos. 11971083 and 11991024), the Team Project of Innovation Leading Talent in Chongqing (No. CQYC20210309536), and the Contract System Project of Chongqing Talent Plan (No. cstc2022ycjh-bgzxm0147).

Abstract

Abstract: The growing interest in addressing minimax optimization problem has been fueled by recent applications in machine learning. Although extensively studied in the convex-concave regime, where a global solution can be efficiently computed, this paper delves into the minimax problem within the nonconvex-concave setup. We propose an alternating gradient projection algorithm with momentum (M-AGP), belonging to single-loop algorithms that not only are easier to implement but also require only the computation of gradient projection updates. We demonstrate that the proposed algorithm identifies an ε-stationary point of the nonconvex-strongly concave minimax problem in O(ε^-2) iterations, representing the best-known rate in the literature. Finally, we utilize two test problems, namely robust nonlinear regression and an image classification problem, to showcase the efficacy of the proposed algorithm.

Key words: Minimax optimization, Alternating gradient projection algorithm, Gradient descent–ascent algorithm, Iteration complexity

CLC Number:

Jue-You Li, Tao Xie. An Alternating Gradient Projection Algorithm with Momentum for Nonconvex-Concave Minimax Problems[J]. Journal of the Operations Research Society of China, 2026, 14(2): 632-652.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00540-5

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/632

References

[1] Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., Graepel, T.: The mechanics of n-player differentiable games. In: International Conference on Machine Learning, PMLR, pp. 354–363(2018)
[2] Chen, Y., Lan, G., Ouyang, Y.: Optimal primal-dual methods for a class of saddle point problems. SIAM J. Optim. 24, 1779–1814(2014)
[3] Chen, Y., Lan, G., Ouyang, Y.: Accelerated schemes for a class of variational inequalities. Math. Program. 165, 113–149(2017)
[4] Creswell, A., White, T., Dumoulin, V., Arulkumaran, K., Sengupta, B., Bharath, A.: Generative adversarial networks: an overview. IEEE Signal Proc. Mag. 35, 53–65(2018)
[5] Chan, E., Lin, C., Chan, M., Nagano, M., Pan, B.: Efficient geometry-aware 3D generative adversarial networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16123–16133(2022)
[6] Daskalakis,C.,Panageas,I.:Thelimitpointsof (optimistic) gradientdescentin min–max optimization. In: Advances in Neural Information Processing Systems, vol. 31, pp. 1–11(2018)
[7] Dai, Y.H., Zhang, L.W.: Optimality conditions for constrained minimax optimization. CSIAM Trans. Appl. Math. 1, 296–315(2020)
[8] Dai, Y.H., Zhang, L.W.: The rate of convergence of augmented Lagrangian method for minimax optimization problems with equality constraints. J. Oper. Res. Soc. China (2022). https://doi.org/10. 1007/s40305-022-00439-z
[9] Gidel, G., Hemmat, R., Pezeshki, M., Priol, R., Huang, G. Julien, S., Mitliagkas, I.: Negative momentum for improved game dynamics. In: The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, pp. 1802–1811(2019)
[10] Juditsky, A., Nemirovski, A.: Solving variational inequalities with monotone operators on domains given by linear minimization oracles. Math. Program. 156, 221–256(2016)
[11] Letcher, A., Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., Graepel, T.: Differentiable game mechanics. J. Mach. Learn. Res. 20, 1–40(2019)
[12] Lin, T., Jin, C., Jordan, M.: Near-optimal algorithms for minimax optimization. In: Conference on Learning Theory, PMLR, pp. 2738–2779(2020)
[13] Lin, T., Jin, C., Jordan, M.: On gradient descent ascent for nonconvex–concave minimax problems. In: International Conference on Machine Learning, PMLR, pp. 6083–6093(2020)
[14] Lu, S., Tsaknakis, I., Hong, M., Chen, Y.: Hybrid block successive approximation for onesided nonconvex min-max problems: algorithms and applications. IEEE Signal Proc. Mag. 68, 3676–3691(2021)
[15] Mescheder, L., Geiger, A., Nowozin, S.: Which training methods for GANs do actually converge? In: International Conference on Machine Learning, PMLR, pp. 3481–3490(2018)
[16] Mai, T., Mihail, M., Panageas, I., Ratcliff, W., Vazirani, V., Yunker, P.: Cycles in zero-sum differential games and biological diversity. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 339–350(2018)
[17] Mokhtari, A., Ozdaglar, A., Pattathil, S.: Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM J. Optim. 30, 3230– 3251(2020)
[18] Nesterov, Y.: Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109, 319–344(2007)
[19] 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. SIAM J. Optim. 15, 229–251(2004)
[20] Nemirovski, A., Juditsky, A., Lan, G.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19, 1574–1609(2009)
[21] Nouiehed, M., Sanjabi, M., Huang, T., Lee, J., Razaviyayn, M.: Solving a class of non-convex min–max games using iterative first order methods. In: Advances in Neural Information Processing Systems, vol. 32, pp. 311–319(2019)
[22] Rafique, H., Liu, M., Lin, Q., Yang, T.: Weakly-convex-concave min-max optimization: provable algorithms and applications in machine learning. Optim. Method Softw. 37, 1087–1121(2022)
[23] Shen, J., Wang, Z., Xu, Z.: Zeroth-order single-loop algorithms for nonconvex-linear minimax problems. J. Global Optim. 87, 551–580(2023)
[24] Thekumparampil, K., Jain, P., Netrapalli, P., Oh, S.: Efficient algorithms for smooth minimax optimization. In: Advances in Neural Information Processing Systems, vol. 32, pp. 1–10(2019)
[25] Xu, Z., Zhang, H.: Optimization algorithms and their complexity analysis for non-convex minimax problems. Oper. Res. Trans. 25, 74–86(2021). (in Chinese)
[26] Xu, Z., Shen, J., Wang, Z., Dai, Y.: Zeroth-order alternating randomized gradient projection algorithms for general nonconvex–concave minimax problems (2021). arXiv:2108.00473
[27] Xu, Z., Zhang, H., Xu, Y., Lan, G.: A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems. Math. Program. 201, 635–706(2023)
[28] Yang, J., Orvieto, A., Lucchi, A., He, N.: Faster single-loop algorithms for minimax optimization without strong concavity. In: International Conference on Artificial Intelligence and Statistics, PMLR, pp. 5485–5517(2022)
[29] Zhang, J., Xiao, P., Sun, R., Luo, Z.: A single-loop smoothed gradient descent–ascent algorithm for nonconvex–concave min–max problems. In: Advances in Neural Information Processing Systems, vol. 33, pp. 7377–7389(2020)
[30] Zhang, H., Xu, Y., Xu, Z.: Block alternating proximal gradient algorithm for convex–nonconcave minimax problems. Oper. Res. Trans. 26, 65–73(2022). (in Chinese)

An Alternating Gradient Projection Algorithm with Momentum for Nonconvex-Concave Minimax Problems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 5

Recommended Articles

Metrics

Comments

[1]	Hui-Ling Zhang, Zi Xu. An Alternating Proximal Gradient Algorithm for Nonsmooth Nonconvex-Linear Minimax Problems with Coupled Linear Constraints [J]. Journal of the Operations Research Society of China, 2026, 14(2): 502-520.
[2]	Yu-Hong Dai, Li-Wei Zhang. The Rate of Convergence of Augmented Lagrangian Method for Minimax Optimization Problems with Equality Constraints [J]. Journal of the Operations Research Society of China, 2024, 12(2): 265-297.
[3]	Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang. Randomized Primal–Dual Proximal Block Coordinate Updates [J]. Journal of the Operations Research Society of China, 2019, 7(2): 205-250.
[4]	Xiang Gao· Shu-Zhong Zhang. First-Order Algorithms for Convex Optimization with Nonseparable Objective and Coupled Constraints [J]. Journal of the Operations Research Society of China, 2017, 5(2): 131-.
[5]	Xiang-Feng Wang. On the Convergence Rate of a Class of Proximal-Based Decomposition Methods for Monotone Variational Inequalities [J]. Journal of the Operations Research Society of China, 2015, 3(3): 347-.