Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave\n Saddle Point Problems without Strong Convexity

Abstract

We consider the convex-concave saddle point problem $\\min_{x}\\max_{y}\nf(x)+y^\\top A x-g(y)$ where $f$ is smooth and convex and $g$ is smooth and\nstrongly convex. We prove that if the coupling matrix $A$ has full column rank,\nthe vanilla primal-dual gradient method can achieve linear convergence even if\n$f$ is not strongly convex. Our result generalizes previous work which either\nrequires $f$ and $g$ to be quadratic functions or requires proximal mappings\nfor both $f$ and $g$. We adopt a novel analysis technique that in each\niteration uses a "ghost" update as a reference, and show that the iterates in\nthe primal-dual gradient method converge to this "ghost" sequence. Using the\nsame technique we further give an analysis for the primal-dual stochastic\nvariance reduced gradient (SVRG) method for convex-concave saddle point\nproblems with a finite-sum structure.\n