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

2021/04/18 by Haochuan Li, Li, Haochuan, Yi Tian +5 · 7 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2104.08708

openalex publication_date 2021/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Ω(√κε^-2) for deterministic oracles, where ε defines the level of approximate stationarity and κ is the condition number. Our analysis shows that the upper bound achieved in (Lin et al., 2020b) is optimal in the ε and κ dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of Ω(√κε^-2 + κ^1/3ε^-4). It suggests that there is a significant gap between the upper bound O(κ³ ε^-4) in (Lin et al., 2020a) and our lower bound in the condition number dependence.

Citations

• Generative Adversarial Networks
• Zur Theorie der Gesellschaftsspiele
• Smooth minimization of non-smooth functions
• Towards Deep Learning Models Resistant to Adversarial Attacks
• A Variational Inequality Perspective on Generative Adversarial Networks
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Efficient Algorithms for Smooth Minimax Optimization
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems

Cited by

• Worst-case generation via minimax optimization in Wasserstein space
• On the Condition Number Dependency in Bilevel Optimization
• Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
• Semi-infinite Nonconvex Constrained Min-Max Optimization
• Stochastic Bilevel Optimization with Heavy-Tailed Noise
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain

Related

• Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• The Complexity of Constrained Min-Max Optimization
• Improved Algorithms for Convex-Concave Minimax Optimization
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization