Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling

Dmitry Kovalev, Alexander Gasnikov, Peter Richtárik

In this paper we study a convex-concave saddle-point problem $\min_x\max_y
f(x) + y^\top\mathbf{A} x - g(y)$, where $f(x)$ and $g(y)$ are smooth and
convex functions. We propose an Accelerated Primal-Dual Gradient Method for
solving this problem which (i) achieves an optimal linear convergence rate in
the strongly-convex-strongly-concave regime matching the lower complexity bound
(Zhang et al., 2021) and (ii) achieves an accelerated linear convergence rate
in the case when only one of the functions $f(x)$ and $g(y)$ is strongly convex
or even none of them are. Finally, we obtain a linearly-convergent algorithm
for the general smooth and convex-concave saddle point problem $\min_x\max_y
F(x,y)$ without requirement of strong convexity or strong concavity.