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

TaeHo Yoon · Ernest Ryu

Keywords: [ Convex Optimization ]

[ Abstract ]
[ Paper ]
[ Visit Poster at Spot C4 in Virtual World ]
Tue 20 Jul 9 p.m. PDT — 11 p.m. PDT
Oral presentation: Optimization (Convex) 2
Tue 20 Jul 7 p.m. PDT — 8 p.m. PDT

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.

Chat is not available.