Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization

Abstract

We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex in the minimization variable, and strongly concave in the maximization variable. We establish a lower bound of $\Omega \left(\sqrt{\kappa }{\epsilon }^{-2}\right)$ for deterministic oracles, where $\epsilon$ defines the level of approximate stationarity and $\kappa$ is the condition number. Our analysis shows that the upper bound achieved in (Lin et al., 2020b) is optimal in the $\epsilon$ and $\kappa$ dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of $\Omega \left(\sqrt{\kappa }{\epsilon }^{-2}+{\kappa }^{1/3}{\epsilon }^{-4}\right)$. It suggests that there is a significant gap between the upper bound $\mathcal{O}({\kappa }^3{\epsilon }^{-4})$ in (Lin et al., 2020a) and our lower bound in the condition number dependence.

arXiv comment20 pages, 1 figure

References in corpus (14)

• Towards Deep Learning Models Resistant to Adversarial Attacks
• A Variational Inequality Perspective on Generative Adversarial Networks
• Optimization, Learning, and Games with Predictable Sequences
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Near-Optimal Algorithms for Minimax Optimization
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Efficient Algorithms for Smooth Minimax Optimization
• Linear Lower Bounds and Conditioning of Differentiable Games
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
• Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Accelerated methods for composite non-bilinear saddle point problem

Cited by in corpus (3)

• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Minimax Optimization with Smooth Algorithmic Adversaries