# Completely Parameter-Free Single-Loop Algorithms for Nonconvex-Concave Minimax Problems

arXiv: https://arxiv.org/abs/2407.21372 · HTML: https://mlsanity.com/paper/2407.21372/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 46 references that are in the map.
- First posted on arXiv 31 Jul 2024.

## Builds on (most cited first, 28 of 28)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Which Training Methods for GANs do actually Converge?](https://mlsanity.com/paper/1801.04406/) (2018)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Covariances, Robustness, and Variational Bayes](https://mlsanity.com/paper/1709.02536/) (2017)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [Robust Optimization over Multiple Domains](https://mlsanity.com/paper/1805.07588/) (2018)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [An accelerated inexact proximal point method for solving nonconvex-concave min-max problems](https://mlsanity.com/paper/1905.13433/) (2019)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Decentralized learning for wireless communications and networking](https://mlsanity.com/paper/1503.08855/) (2015)
- [TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2210.17478/) (2022)
- [Universal Tensor Methods for Monotone Variational Inequalities](https://mlsanity.com/paper/2212.07824/) (2022)
- [A Stochastic GDA Method With Backtracking For Solving Nonconvex Concave Minimax Problems](https://mlsanity.com/paper/2403.07806/) (2024)
- [Randomized First-Order Methods for Saddle Point Optimization](https://mlsanity.com/paper/1409.8625/) (2014)

## Abstract (arXiv)

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, three completely parameter-free single-loop algorithms, namely PF-AGP-NSC algorithm, PF-AGP-NC algorithm and PF-AGP-NL algorithm, are proposed to solve the smooth nonconvex-strongly concave, nonconvex-concave minimax problems and nonconvex-linear minimax problems respectively using line search without requiring any prior knowledge about parameters such as the Lipschtiz constant L or the strongly concave modulus μ. Furthermore, we prove that the total number of gradient calls required to obtain an varepsilon-stationary point for the PF-AGP-NSC algorithm, the PF-AGP-NC algorithm, and the PF-AGP-NL algorithm are upper bounded by Oleft( L2kappa3varepsilon-2 right), Oleft( log2(L)L4varepsilon-4 right), and Oleft( L3varepsilon-3 right), respectively, where kappa is the condition number. To the best of our knowledge, PF-AGP-NC and PF-AGP-NL are the first completely parameter-free algorithms for solving nonconvex-concave and nonconvex-linear minimax problems, respectively. PF-AGP-NSC is a completely parameter-free algorithm for solving nonconvex-strongly concave minimax problems, achieving the best known complexity with respect to varepsilon. Numerical results demonstrate the efficiency of the three proposed algorithms.