Paper ID: 2407.21372

Two Completely Parameter-Free Alternating Gradient Projection Algorithms for Nonconvex-(strongly) Concave Minimax Problems

Junnan Yang, Huiling Zhang, Zi Xu

Due to their importance in various emerging applications, efficient algorithms for solving minimax problems have recently received increasing attention. However, many existing algorithms require prior knowledge of the problem parameters in order to achieve optimal iteration complexity. In this paper, we propose two completely parameter-free alternating gradient projection algorithms, i.e., the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm, to solve the smooth nonconvex-strongly concave and nonconvex-concave minimax problems respectively using a backtracking strategy, which does not require prior knowledge of parameters such as the Lipschtiz constant $L$ or the strongly concave constant $\mu$. Moreover, we show that the total number of gradient calls of the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm to obtain an $\varepsilon$-stationary point is upper bounded by $\mathcal{O}\left( L\kappa^3\varepsilon^{-2} \right)$ and $\mathcal{O}\left( L^4\varepsilon^{-4} \right)$ respectively, where $\kappa$ is the condition number. As far as we know, the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm are the first completely parameter-free algorithms for solving nonconvex-strongly concave minimax problems and nonconvex-concave minimax problems respectively. Numerical results validate the efficiency of the proposed PF-AGP algorithm.

Submitted: Jul 31, 2024