Near-Optimal Algorithms for Minimax Optimization

2020/02/05 by Tianyi Lin, Chi Jin, Lin, Tianyi +3 · 16 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #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.2002.02417

openalex publication_date 2020/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper resolves a longstanding open question pertaining to the design of near-optimal first-order algorithms for smooth and strongly-convex-strongly-concave minimax problems. Current state-of-the-art first-order algorithms find an approximate Nash equilibrium using O(κ_{\mathbf x}+κ_{\mathbf y}) or O(min\κ_{\mathbf x}√κ_{\mathbf y}, √κ_{\mathbf x}κ_{\mathbf y}\) gradient evaluations, where κ_{\mathbf x} and κ_{\mathbf y} are the condition numbers for the strong-convexity and strong-concavity assumptions. A gap still remains between these results and the best existing lower bound Ω(√κ_{\mathbf x}κ_{\mathbf y}). This paper presents the first algorithm with O(√κ_{\mathbf x}κ_{\mathbf y}) gradient complexity, matching the lower bound up to logarithmic factors. Our algorithm is designed based on an accelerated proximal point method and an accelerated solver for minimax proximal steps. It can be easily extended to the settings of strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvex-concave functions. This paper also presents algorithms that match or outperform all existing methods in these settings in terms of gradient complexity, up to logarithmic factors.

Citations

• Distributed Sparse Linear Regression
• Smooth minimization of non-smooth functions
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Last-iterate convergence rates for min-max optimization
• Optimization, Learning, and Games with Predictable Sequences
• Accelerating Smooth Games by Manipulating Spectral Shapes

Cited by

• A first-order method for nonconvex-strongly-concave constrained minimax optimization
• Unified Framework for Outage-Constrained Rate Maximization in Secure ISAC Under Various Sensing Metrics
• DAMA: A Unified Accelerated Approach for Decentralized Nonconvex Minimax Optimization-Part I: Algorithm Development and Results
• Monotone Near-Zero-Sum Games: A Generalization of Convex-Concave Minimax
• On the Condition Number Dependency in Bilevel Optimization
• A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization
• A Retraction-free Method for Nonsmooth Minimax Optimization over a Compact Manifold
• Semi-infinite Nonconvex Constrained Min-Max Optimization
• Stochastic Bilevel Optimization with Heavy-Tailed Noise
• EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization
• Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approach
• Communication-Efficient Algorithms for Distributed Nonconvex Minimax Optimization Problems
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k²) Rate on Squared Gradient Norm
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Min-Max Optimization with Dual-Linear Coupling

Related

• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization
• Improved Algorithms for Convex-Concave Minimax Optimization
• Efficient Algorithms for Smooth Minimax Optimization
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k²) Rate on Squared Gradient Norm