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