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

Luo Luo, Yujun Li, Cheng ChenNeurIPS 2022 · OpenReview

TL;DR

This paper tackles nonconvex-strongly-concave minimax optimization problems, which are common in machine learning applications like adversarial training and domain adaptation. While most existing methods only find first-order stationary points (which can be suboptimal saddle points), the authors propose Minimax Cubic Newton (MCN) and an inexact variant (IMCN) to efficiently find second-order stationary points, guaranteeing convergence to true local minimax points even in high-dimensional settings.

The Challenge of Saddle Points in Minimax Optimization

Minimax optimization takes the form $\min_x \max_y f(x,y)$. It is the mathematical engine behind many modern machine learning frameworks, such as Generative Adversarial Networks (GANs) and robust reinforcement learning.

When the objective function $f(x,y)$ is nonconvex with respect to $x$, the overarching primal function is also nonconvex. Standard optimization algorithms like Gradient Descent Ascent (GDA) are designed to find First-order Stationary Points (FSPs). However, in a nonconvex landscape, an FSP might just be a saddle point—a flat region that isn't a true local minimum. If an algorithm gets stuck in a saddle point, the resulting model performs poorly.

To guarantee that the algorithm finds a meaningful local minimum, it needs to find a Second-order Stationary Point (SSP). Unfortunately, computing the second-order information (the Hessian matrix) required to find SSPs is notoriously expensive, making it highly challenging to apply to high-dimensional neural networks.

Proposed Methods: MCN and IMCN

To overcome these computational hurdles, the authors propose two novel algorithms designed to find SSPs:

  • Minimax Cubic Newton (MCN): This method alternates between two steps. First, it uses Nesterov’s Accelerated Gradient Descent (AGD) to solve the inner maximization problem (updating $y$). Second, it updates $x$ by solving a cubic regularized Newton sub-problem. This approach uses exact second-order (Hessian) information to navigate the curvature of the function and escape saddle points.
  • Inexact Minimax Cubic Newton (IMCN): Because constructing and inverting a full Hessian matrix is computationally prohibitive for high-dimensional problems, the authors introduce IMCN. Instead of exact Hessians, IMCN approximates the inverse Hessian using matrix Chebyshev polynomials. This clever substitution means the algorithm only needs to compute Hessian-vector products (which are almost as cheap as standard gradients) rather than full matrices. It then solves the cubic sub-problem inexactly using gradient descent.
Pseudocode for the Inexact Minimax Cubic-Newton (IMCN) algorithm and its Cubic-Solver.

Key Insights and Theoretical Guarantees

  • Escaping Saddle Points is Provable: By targeting SSPs rather than FSPs, the optimization process can successfully and mathematically guarantee an escape from strict saddle points where standard first-order methods (like GDA) fail.
  • Chebyshev Polynomials for Scalability: Approximating the inverse of the Hessian matrix using Chebyshev polynomials is a massive computational shortcut. It reduces a highly expensive matrix inversion ($\mathcal{O}(d^3)$) into a series of much cheaper Hessian-vector products, making second-order optimization viable for deep learning models.
  • First Non-asymptotic SSP Bounds: To the authors' knowledge, this is the first work to provide non-asymptotic convergence guarantees for finding SSPs in minimax problems without relying on strict convex-concave assumptions. The exact MCN algorithm finds an SSP using $\mathcal{O}(\kappa^{1.5}\sqrt{\rho}\epsilon^{-1.5})$ second-order oracle calls. The highly scalable IMCN algorithm achieves the same SSP using $\tilde{\mathcal{O}}(\kappa^{1.5}\ell\epsilon^{-2})$ Hessian-vector products and $\tilde{\mathcal{O}}(\kappa^2\sqrt{\rho}\epsilon^{-1.5})$ first-order calls, entirely avoiding expensive full second-order operations.

Experimental Results

The authors evaluate their algorithms on both synthetic and real-world setups:

  • Synthetic Benchmark: On a custom 3D nonconvex-strongly-concave W-shaped scalar function designed with a strict saddle point, standard GDA gets permanently stuck (evidenced by negative minimum Hessian eigenvalues). In contrast, MCN quickly escapes the saddle point and converges to the true local minimum.
  • Real-world Domain Adaptation: The algorithms were tested on the Domain-Adversarial Neural Network (DANN) task, evaluated on the MNIST and MNIST-m datasets. Here, IMCN significantly outperforms GDA in both wall-clock time and the total number of oracle calls required to converge, proving that the theoretical efficiency translates to real-world speedups.

Limitations and Future Work

  • Strong Concavity Assumption: The theoretical guarantees rely on the assumption that the problem is strongly concave in $y$. Extending this framework to general nonconvex-concave problems is an important next step.
  • Reliance on Hessian-Vector Products: While much cheaper than full Hessians, IMCN still requires Hessian-vector products. Developing pure first-order algorithms that can still guarantee finding SSPs remains an open challenge.
  • Stochasticity: The current paper focuses on deterministic settings. Because machine learning models typically use finite-sum or expectation forms (e.g., minibatches), designing efficient stochastic versions of MCN and IMCN is a highly promising direction for future research.

Summary updated

Abstract

We study the smooth minimax optimization problem $\min_{\bf x}\max_{\bf y} f({\bf x},{\bf y})$, where $f$ is $\ell$-smooth, strongly-concave in ${\bf y}$ but possibly nonconvex in ${\bf x}$. Most of existing works focus on finding the first-order stationary point of the function $f({\bf x},{\bf y})$ or its primal function $P({\bf x})\triangleq \max_{\bf y} f({\bf x},{\bf y})$, but few of them focus on achieving the second-order stationary point, which is essential to nonconvex problems. In this paper, we propose a novel approach for minimax optimization, called Minimax Cubic Newton (MCN), which could find an ${\mathcal O}\left(\varepsilon,\kappa^{1.5}\sqrt{\rho\varepsilon}\right)$-second-order stationary point of $P({\bf x})$ with calling ${\mathcal O}\left(\kappa^{1.5}\sqrt{\rho}\varepsilon^{-1.5}\right)$ times of second-order oracles and $\tilde{\mathcal O}\left(\kappa^{2}\sqrt{\rho}\varepsilon^{-1.5}\right)$ times of first-order oracles, where $\kappa$ is the condition number and $\rho$ 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 the 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 $\tilde{\mathcal O}\left(\kappa^{1.5}\ell\varepsilon^{-2}\right)$ Hessian-vector oracle calls and $\tilde{\mathcal O}\left(\kappa^{2}\sqrt{\rho}\varepsilon^{-1.5}\right)$ 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.
BibTeX
@inproceedings{luo2022finding,
  author = {Luo Luo and Yujun Li and Cheng Chen},
  title = {{Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=6HjrDFIW8z},
}
Figure