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

TaeHo Yoon; Ernest K. Ryu

paper

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

arXiv:2102.07922

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 $O (1/ k^{2})$ last-iterate rates, faster than the existing $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 $O (1/ k^{2})$ rate through a matching lower bound.

Published at ICML 2021 as a long talk

Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm

Abstract

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