mlsanityData to 7 Oct 2026

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

arXiv 2407.21372 ↗First posted 31 Jul 2024math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

Builds on

28 of 46 references.

References · 28

  1. 2021Convex optimizationcited by 2,479
  2. 2018Which Training Methods for GANs do actually Converge?cited by 672
  3. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  4. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 182
  5. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  6. 2015Distributionally Robust Logistic Regressioncited by 124
  7. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  8. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  9. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  10. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  11. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
  12. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
16 more
  1. 2018On the Convergence and Robustness of Training GANs with Regularized Optimal Transportcited by 51
  2. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  3. 2017Covariances, Robustness, and Variational Bayescited by 39
  4. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  5. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  6. 2018Robust Optimization over Multiple Domainscited by 34
  7. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  8. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  9. 2013Optimal Primal-Dual Methods for a Class of Saddle Point Problemscited by 19
  10. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  11. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  12. 2015Decentralized learning for wireless communications and networkingcited by 9
  13. 2022TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimizationcited by 7
  14. 2022Universal Tensor Methods for Monotone Variational Inequalitiescited by 6
  15. 2024A Stochastic GDA Method With Backtracking For Solving Nonconvex Concave Minimax Problemscited by 6
  16. 2014Randomized First-Order Methods for Saddle Point Optimizationcited by 3

Built on by

Not cited yet.