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

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

## Key facts

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

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

- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Robust Optimization over Multiple Domains](https://mlsanity.com/paper/1805.07588/) (2018)
- [An accelerated inexact proximal point method for solving nonconvex-concave min-max problems](https://mlsanity.com/paper/1905.13433/) (2019)
- [Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems](https://mlsanity.com/paper/2007.13605/) (2020)
- [Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities](https://mlsanity.com/paper/2001.07819/) (2020)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2211.13668/) (2022)
- [Trust-Region Algorithms for Training Responses: Machine Learning Methods Using Indefinite Hessian Approximations](https://mlsanity.com/paper/1807.00251/) (2018)
- [Zeroth-Order Algorithms for Smooth Saddle-Point Problems](https://mlsanity.com/paper/2009.09908/) (2020)
- [A Stochastic Trust Region Method for Non-convex Minimization](https://mlsanity.com/paper/1903.01540/) (2019)
- [Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models](https://mlsanity.com/paper/1904.03342/) (2019)
- [Accelerating Adaptive Cubic Regularization of Newton's Method via Random Sampling](https://mlsanity.com/paper/1802.05426/) (2018)
- [Stochastic Trust Region Inexact Newton Method for Large-scale Machine Learning](https://mlsanity.com/paper/1812.10426/) (2018)

## Built on by (most cited first, 2 of 2)

- [A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems](https://mlsanity.com/paper/2407.03571/) (2024)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)

## 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.