# A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 76 references that are in the map.
- First posted on arXiv 14 Oct 2021.

## Builds on (most cited first, 30 of 35)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [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)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Multi-Agent Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1807.09936/) (2018)
- [Gradient descent GAN optimization is locally stable](https://mlsanity.com/paper/1706.04156/) (2017)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [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)
- [On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach](https://mlsanity.com/paper/1910.07512/) (2019)
- [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018)
- [Local Saddle Point Optimization: A Curvature Exploitation Approach](https://mlsanity.com/paper/1805.05751/) (2018)
- [Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent](https://mlsanity.com/paper/1909.00843/) (2019)
- [Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning](https://mlsanity.com/paper/2008.10103/) (2020)
- [Saddle-point dynamics: conditions for asymptotic stability of saddle points](https://mlsanity.com/paper/1510.02145/) (2015)
- [Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step](https://mlsanity.com/paper/1612.00547/) (2016)
- [Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometry](https://mlsanity.com/paper/2102.04653/) (2021)
- [Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization](https://mlsanity.com/paper/1802.07372/) (2018)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence](https://mlsanity.com/paper/2006.09361/) (2020)
- [Newton-type Methods for Minimax Optimization](https://mlsanity.com/paper/2006.14592/) (2020)
- [On the Suboptimality of Negative Momentum for Minimax Optimization](https://mlsanity.com/paper/2008.07459/) (2020)

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

- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Two-timescale Extragradient for Finding Local Minimax Points](https://mlsanity.com/paper/2305.16242/) (2023)
- [A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems](https://mlsanity.com/paper/2407.03571/) (2024)
- [Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization](https://mlsanity.com/paper/2405.00914/) (2024)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)

## Abstract (arXiv)

Gradient descent-ascent (GDA) is a widely used algorithm for minimax optimization. However, GDA has been proved to converge to stationary points for nonconvex minimax optimization, which are suboptimal compared with local minimax points. In this work, we develop cubic regularization (CR) type algorithms that globally converge to local minimax points in nonconvex-strongly-concave minimax optimization. We first show that local minimax points are equivalent to second-order stationary points of a certain envelope function. Then, inspired by the classic cubic regularization algorithm, we propose an algorithm named Cubic-LocalMinimax for finding local minimax points, and provide a comprehensive convergence analysis by leveraging its intrinsic potential function. Specifically, we establish the global convergence of Cubic-LocalMinimax to a local minimax point at a sublinear convergence rate and characterize its iteration complexity. Also, we propose a GDA-based solver for solving the cubic subproblem involved in Cubic-LocalMinimax up to certain pre-defined accuracy, and analyze the overall gradient and Hessian-vector product computation complexities of such an inexact Cubic-LocalMinimax algorithm. Moreover, we propose a stochastic variant of Cubic-LocalMinimax for large-scale minimax optimization, and characterize its sample complexity under stochastic sub-sampling. Experimental results demonstrate faster convergence of our stochastic Cubic-LocalMinimax than some existing algorithms.