Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm

Abstract

In this work, we study the computational complexity of reducing the squared gradient magnitude for smooth minimax optimization problems. First, we present algorithms with accelerated $\mathcal{O}(1/k^2)$ last-iterate rates, faster than the existing $\mathcal{O}(1/k)$ or slower rates for extragradient, Popov, and gradient descent with anchoring. The acceleration mechanism combines extragradient steps with anchoring and is distinct from Nesterov's acceleration. We then establish optimality of the $\mathcal{O}(1/k^2)$ rate through a matching lower bound.

arXiv commentPublished at ICML 2021 as a long talk

References in corpus (16)

• 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
• 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
• Fast Convergence of Regularized Learning in Games
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Near-Optimal Algorithms for Minimax Optimization
• Efficient Algorithms for Smooth Minimax Optimization
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities
• A Warped Resolvent Algorithm to Construct Nash Equilibria

Cited by in corpus (8)

• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems
• A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
• Optimal First-Order Algorithms as a Function of Inequalities
• Analysis and Numerical Solution of a Modular Convex Nash Equilibrium Problem