Near-Optimal Algorithms for Minimax Optimization

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 $\tilde{O}({\kappa }_{\mathbf{x}}+{\kappa }_{\mathbf{y}})$ or $\tilde{O}(\min \{{\kappa }_{\mathbf{x}}\sqrt{{\kappa }_{\mathbf{y}}},\sqrt{{\kappa }_{\mathbf{x}}}{\kappa }_{\mathbf{y}}\})$ gradient evaluations, where ${\kappa }_{\mathbf{x}}$ and ${\kappa }_{\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 $\tilde{\Omega }(\sqrt{{\kappa }_{\mathbf{x}}{\kappa }_{\mathbf{y}}})$. This paper presents the first algorithm with $\tilde{O}(\sqrt{{\kappa }_{\mathbf{x}}{\kappa }_{\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.

Accepted by COLT 2020; Improve the writing and fix some confusing parts in the proof

References in corpus (2)

• Efficient Algorithms for Smooth Minimax Optimization
• Accelerated Primal Dual Method for a Class of Saddle Point Problem with Strongly Convex Component

Cited by in corpus (26)

• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Minimax Estimation of Conditional Moment Models
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• A Statistical Framework of Watermarks for Large Language Models: Pivot, Detection Efficiency and Optimal Rules
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• On the Suboptimality of Negative Momentum for Minimax Optimization
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Coping with Label Shift via Distributionally Robust Optimisation
• Optimality and Stability in Non-Convex Smooth Games
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Majorized Semi-proximal Alternating Coordinate Method for Nonsmooth Convex-Concave Minimax Optimization
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• MIMO Radar Waveform-Filter Design for Extended Target Detection from a View of Games
• Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems
• Convex optimization
• On solving convex min-min problems with smoothness and strong convexity in one variable group and small dimension of the other
• Understanding the Role of Adversarial Regularization in Supervised Learning