Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain

Abstract

We study the problem of finding approximate first-order stationary points in optimization problems of the form ${\min }_{x\in X}{\max }_{y\in Y}f(x,y)$, where the sets $X,Y$ are convex and $Y$ is compact. The objective function $f$ is smooth, but assumed neither convex in $x$ nor concave in $y$. Our approach relies upon replacing the function $f(x,\cdot )$ with its $k$th order Taylor approximation (in $y$) and finding a near-stationary point in the resulting surrogate problem. To guarantee its success, we establish the following result: let the Euclidean diameter of $Y$ be small in terms of the target accuracy $\epsilon$, namely $O({\epsilon }^{\frac{2}{k+1}})$ for $k\in \mathbb{N}$ and $O(\epsilon )$ for $k=0$, with the constant factors controlled by certain regularity parameters of $f$; then any $\epsilon$-stationary point in the surrogate problem remains $O(\epsilon )$-stationary for the initial problem. Moreover, we show that these upper bounds are nearly optimal: the aforementioned reduction provably fails when the diameter of $Y$ is larger. For $0\le k\le 2$ the surrogate function can be efficiently maximized in $y$; our general approximation result then leads to efficient algorithms for finding a near-stationary point in nonconvex-nonconcave min-max problems, for which we also provide convergence guarantees.

References in corpus (38)

• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Theoretically Principled Trade-off between Robustness and Accuracy
• Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization
• Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part I: Nash Equilibria
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• The Numerics of GANs
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Near-Optimal Algorithms for Minimax Optimization
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Fairness for Robust Log Loss Classification
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Last-iterate convergence rates for min-max optimization
• Efficient Algorithms for Smooth Minimax Optimization
• GANs May Have No Nash Equilibria
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
• Improved Algorithms for Convex-Concave Minimax Optimization
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Rényi Fair Inference
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization
• Minimax Optimization with Smooth Algorithmic Adversaries
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems