The Complexity of Nonconvex-Strongly-Concave Minimax Optimization

Abstract

This paper studies the complexity for finding approximate stationary points of nonconvex-strongly-concave (NC-SC) smooth minimax problems, in both general and averaged smooth finite-sum settings. We establish nontrivial lower complexity bounds of $\Omega (\sqrt{\kappa }\Delta L{\epsilon }^{-2})$ and $\Omega (n+\sqrt{n\kappa }\Delta L{\epsilon }^{-2})$ for the two settings, respectively, where $\kappa$ is the condition number, $L$ is the smoothness constant, and $\Delta$ is the initial gap. Our result reveals substantial gaps between these limits and best-known upper bounds in the literature. To close these gaps, we introduce a generic acceleration scheme that deploys existing gradient-based methods to solve a sequence of crafted strongly-convex-strongly-concave subproblems. In the general setting, the complexity of our proposed algorithm nearly matches the lower bound; in particular, it removes an additional poly-logarithmic dependence on accuracy present in previous works. In the averaged smooth finite-sum setting, our proposed algorithm improves over previous algorithms by providing a nearly-tight dependence on the condition number.

References in corpus (19)

• A Universal Catalyst for First-Order Optimization
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• A Lower Bound for the Optimization of Finite Sums
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• Variance Reduction for Matrix Games
• Linear Lower Bounds and Conditioning of Differentiable Games
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity

Cited by in corpus (5)

• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
• Minimax Optimization with Smooth Algorithmic Adversaries