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.

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

References in corpus (15)

• Robustness and Regularization of Support Vector Machines
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• A Variational Inequality Perspective on Generative Adversarial Networks
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Online Learning with Predictable Sequences
• Optimization, Learning, and Games with Predictable Sequences
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Last-iterate convergence rates for min-max optimization
• Efficient Algorithms for Smooth Minimax Optimization
• Accelerating Smooth Games by Manipulating Spectral Shapes
• Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
• Accelerated Primal Dual Method for a Class of Saddle Point Problem with Strongly Convex Component

Cited by in corpus (27)

• 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
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• On the Suboptimality of Negative Momentum for Minimax 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
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• Convex optimization
• Understanding the Role of Adversarial Regularization in Supervised Learning
• Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems
• MIMO Radar Waveform-Filter Design for Extended Target Detection from a View of Games
• On solving convex min-min problems with smoothness and strong convexity in one variable group and small dimension of the other