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

MaRDI QIDQ6360718zbMATH OpenFDO

Authors Taeho Yoon, Ernest K. Ryu

Publication date 15 February 2021

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6360718)