An Alternating Proximal Gradient Algorithm for Nonsmooth Nonconvex-Linear Minimax Problems with Coupled Linear Constraints

doi:10.1007/s40305-024-00550-3

Abstract

Abstract: In this paper, we propose an alternating proximal gradient algorithm for solving nonsmooth nonconvex-linear minimax problems with coupled linear constraints, which have attracted wide attention in machine learning, signal processing and many other fields in recent years. The iteration complexity of the proposed algorithm is proved to be $\mathcal{O}\left(\varepsilon^{-3}\right)$ to reach an $\varepsilon$-stationary point. To our knowledge, this is the first algorithm with iteration complexity guarantee for solving nonsmooth nonconvex-linear minimax problems with coupled linear constraints.

Key words: Minimax optimization problem, Alternating proximal gradient algorithm, Iteration complexity, Machine learning

CLC Number:

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.

TrendMD

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

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00550-3

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

References

[1] Berger J O.: Statistical Decision Theory and Bayesian Analysis. Springer (2013)
[2] Cai, Q., Hong, M., Chen, Y., Wang, Z.: On the global convergence of imitation learning: a case for linear quadratic regulator (2019). arXiv:1901.03674
[3] Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program. 159(1–2), 253–287(2016)
[4] Chen, P., Zhang, H., Sharma, Y., Yi, J., Hsieh, Jv, C.: Zoo: zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In: Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15–26(2017)
[5] Dussault, J.P., Haddou, M., Kadrani, A., Migot, T.: On approximate stationary points of the regularized mathematical program with complementarity constraints. J. Optim. Theory Appl. 186, 504–522(2020)
[6] Daskalakis, C., Ilyas, A., Syrgkanis, V., Zeng, H.: Training gans with optimism. In: International Conference on Learning Representations, pp. 1–30(2018)
[7] Daskalakis, C., Panageas, I.: The limit points of (optimistic) gradient descent in min–max optimization. In: Advances in Neural Information Processing Systems, pp. 9236–9246(2018)
[8] Dai, Y.H., Wang, J., Zhang, L.: Optimality conditions and numerical algorithms for a class of linearly constrained minimax optimization problems (2022). arXiv:2204.09185
[9] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin (2007)
[10] Gidel, G., Berard, H., Vignoud, G., Vincent, P., Lacoste-Julien, S.: A variational inequality perspective on generative adversarial networks. In: International conference on learning representations, pp. 1–39(2019)
[11] Gidel, G., Hemmat, R.A., Pezeshki, M., Huang, G., Lepriol, R., Lacoste-Julien, S., Mitliagkas, I.: Negative momentum for improved game dynamics. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1802–1811(2019)
[12] He, J., Zhang, H., Xu, Z.: An approximation proximal gradient algorithm for nonconvex-linear minimax problems with nonconvex nonsmooth terms. J. Glob. Optim. (2024). https://doi.org/10.1007/s10898-024-01383-3
[13] Ho, J., Ermon, S.: Generative adversarial imitation learning. In: Advances in Neural Information Processing Systems, pp. 4565–4573(2016)
[14] Kong, W., Monteiro, R.D.C.: An accelerated inexact proximal point method for solving nonconvex concave min–max problems. SIAM J. Optim. 31(4), 2558–2585(2021)
[15] Kanzow, C., Schwartz, A.: The price of inexactness: convergence properties of relaxation methods for mathematical programs with complementarity constraints revisited. Math. Oper. Res. 40(2), 253–275(2015)
[16] Letcher, A., Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., Graepel, T.: Differentiable game mechanics. J. Mach. Learn. Res. 20(1), 3032–3071(2019)
[17] Lin, T., Jin, C., Jordan, M.: On gradient descent ascent for nonconvex-concave minimax problems. In: International Conference on Machine Learning, pp. 6083–6093(2020)
[18] Lin, T., Jin, C., Jordan, M.: Near-optimal algorithms for minimax optimization. In: Conference on Learning Theory, pp. 2738–2779(2020)
[19] Li, A., Masouros, C., Liu, F., Swindlehurst, A.L.: Massive MIMO 1-bit DAC transmission: a lowcomplexity symbol scaling approach. IEEE Trans. Wirel. Commun. 17(11), 7559–7575(2018)
[20] Lu, S., Tsaknakis, I., Hong, M., Chen, Y.: Hybrid block successive approximation for one-sided nonconvex min–max problems: algorithms and applications. IEEE Trans. Signal Process. 68, 3676– 3691(2020)
[21] Lu, Z., Mei, S.: A first-order augmented Lagrangian method for constrained minimax optimization (2023). arXiv:2301.02060
[22] Moriarty, D.E., Schultz, A.C., Grefenstette, J.J.: Evolutionary algorithms for reinforcement learning. J. Artif. Intell. Res. 11, 241–276(1999)
[23] Nouiehed, M., Sanjabi, M., Huang, T., Lee, J.D.: Solving a class of non-convex min–max games using iterative first order methods. In: Advances in Neural Information Processing Systems. pp. 14934–14942(2019)
[24] Ostrovskii, D.M., Lowy, A., Razaviyayn, M.: Efficient search of first-order nash equilibria in nonconvex-concave smooth min–max problems. SIAM J. Optim. 31(4), 2508–2538(2021)
[25] Pan, W., Shen, J., Xu, Z.: An efficient algorithm for nonconvex-linear minimax optimization problem and its application in solving weighted maximin dispersion problem. Comput. Optim. Appl. 78(1), 287–306(2021)
[26] Qiu, S., Yang, Z., Wei, X., Ye, J., Wang, Z.: Single-timescale stochastic nonconvex-concave optimization for smooth nonlinear TD learning (2020). arXiv:2008.10103
[27] Qian, Q., Zhu, S., Tang, J., Jin, R., Sun, B., Li, H.: Robust optimization over multiple domains. Proc. AAAI Conf. Artif. Intell. 33(01), 4739–4746(2019)
[28] Rafique, H., Liu, M., Lin, Q., Yang, T.: Weakly-convex-concave min–max optimization: provable algorithms and applications in machine learning. Optim. Methods Softw. 37(3), 1087–1121(2022)
[29] Sanjabi, M., Ba, J., Razaviyayn, M., Lee, J.D.: On the convergence and robustness of training gans with regularized optimal transport. In: Advances in Neural Information Processing Systems, pp. 7091–7101(2018)
[30] Shen, J., Wang, Z., Xu, Z.: Zeroth-order single-loop algorithms for nonconvex-linear minimax problems. J. Glob. Optim. 87(2), 551–580(2023)
[31] Tsaknakis, I., Hong, M., Zhang, S.: Minimax problems with coupled linear constraints: computational complexity, duality and solution methods. SIAM J. Optim. 33(4), 2675–2702(2023)
[32] Thekumparampil, K.K., Jain, P., Netrapalli, P.,Oh, S.: Efficient algorithms for smooth minimax optimization. In: Advances in Neural Information Processing Systems. pp. 12680–12691(2019)
[33] Wu, Z., Jiang, B., Liu, Y.F., Dai, Y.H.: A novel negative l1 penalty approach for multiuser onebit massive MIMO downlink with PSK signaling. In: IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 5323–5327(2022)
[34] 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(1), 635–706(2023)
[35] Yang, J., Zhang, S., Kiyavash, N., He, N.: A catalyst framework for minimax optimization. Adv. Neural Inf. Process. Syst. 33, 5667–5678(2020)
[36] Zhang, J., Xiao, P., Sun, R., Luo, Z.: A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min–max problems. Adv. Neural Inf. Process. Syst. 33, 7377–7389(2020)
[37] Zhang, H., Wang, J., Xu, Z., Dai, Y.H.: Primal dual alternating proximal gradient algorithms for nonsmooth nonconvex minimax problems with coupled linear constraints (2022). arXiv:2212.04672