mlsanityData to 7 Oct 2026

Two trust region type algorithms for solving nonconvex-strongly concave minimax problems

arXiv 2402.09807 ↗First posted 15 Feb 2024math.OC cs.LG stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose a Minimax Trust Region (MINIMAX-TR) algorithm and a Minimax Trust Region Algorithm with Contractions and Expansions(MINIMAX-TRACE) algorithm for solving nonconvex-strongly concave minimax problems. Both algorithms can find an (ε, √ε)-second order stationary point(SSP) within O(ε-1.5) iterations, which matches the best well known iteration complexity.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 28 of its 43 references that are in the map. First posted on arXiv 15 Feb 2024.

Builds on

28 of 43 references.

References · 28

  1. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  2. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  3. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  4. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  5. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  6. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  7. 2017Sub-sampled Cubic Regularization for Non-convex Optimizationcited by 63
  8. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  9. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
  10. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  11. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  12. 2017Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Informationcited by 41
16 more
  1. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  2. 2020Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimizationcited by 39
  3. 2018Robust Optimization over Multiple Domainscited by 34
  4. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 34
  5. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  6. 2020Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problemscited by 26
  7. 2020Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexitiescited by 21
  8. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  9. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  10. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 10
  11. 2018Trust-Region Algorithms for Training Responses: Machine Learning Methods Using Indefinite Hessian Approximationscited by 8
  12. 2020Zeroth-Order Algorithms for Smooth Saddle-Point Problemscited by 7
  13. 2019A Stochastic Trust Region Method for Non-convex Minimizationcited by 4
  14. 2019Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Modelscited by 4
  15. 2018Accelerating Adaptive Cubic Regularization of Newton's Method via Random Samplingcited by 3
  16. 2018Stochastic Trust Region Inexact Newton Method for Large-scale Machine Learningcited by 2

Built on by

Cited by year

Citing papers per year: 2024: 2.

2 papers.

  1. 2024A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problemscited by 3
  2. 2024Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problemscited by 0