# Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 46 references that are in the map.
- First posted on arXiv 10 Oct 2021.

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

- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [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)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach](https://mlsanity.com/paper/1910.07512/) (2019)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning](https://mlsanity.com/paper/2008.10103/) (2020)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition](https://mlsanity.com/paper/2006.06889/) (2020)
- [Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step](https://mlsanity.com/paper/1612.00547/) (2016)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Newton-type Methods for Minimax Optimization](https://mlsanity.com/paper/2006.14592/) (2020)

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

- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Accelerating Inexact HyperGradient Descent for Bilevel Optimization](https://mlsanity.com/paper/2307.00126/) (2023)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization](https://mlsanity.com/paper/2110.07098/) (2021)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems](https://mlsanity.com/paper/2407.03571/) (2024)
- [Two trust region type algorithms for solving nonconvex-strongly concave minimax problems](https://mlsanity.com/paper/2402.09807/) (2024)
- [Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization](https://mlsanity.com/paper/2509.02937/) (2025)
- [Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization](https://mlsanity.com/paper/2405.00914/) (2024)
- [Completely Parameter-Free Single-Loop Algorithms for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2407.21372/) (2024)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)
- [Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimization](https://mlsanity.com/paper/2602.01339/) (2026)

## Abstract (arXiv)

We study the smooth minimax optimization problem minbf xmaxbf y f(bf x,bf y), where f is ℓ-smooth, strongly-concave in bf y but possibly nonconvex in bf x. Most of existing works focus on finding the first-order stationary points of the function f(bf x,bf y) or its primal function P(bf x)triangleq maxbf y f(bf x,bf y), but few of them focus on achieving second-order stationary points. In this paper, we propose a novel approach for minimax optimization, called Minimax Cubic Newton (MCN), which could find an big(varepsilon,kappa1.5√ρvarepsilon,big)-second-order stationary point of P(bf x) with calling mathcal Obig(kappa1.5√ρvarepsilon-1.5big) times of second-order oracles and tildemathcal Obig(kappa2√ρvarepsilon-1.5big) times of first-order oracles, where kappa is the condition number and ρ is the Lipschitz continuous constant for the Hessian of f(bf x,bf y). In addition, we propose an inexact variant of MCN for high-dimensional problems to avoid calling expensive second-order oracles. Instead, our method solves the cubic sub-problem inexactly via gradient descent and matrix Chebyshev expansion. This strategy still obtains the desired approximate second-order stationary point with high probability but only requires tildemathcal Obig(kappa1.5ℓvarepsilon-2big) Hessian-vector oracle calls and tildemathcal Obig(kappa2√ρvarepsilon-1.5big) first-order oracle calls. To the best of our knowledge, this is the first work that considers the non-asymptotic convergence behavior of finding second-order stationary points for minimax problems without the convex-concave assumptions.