Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
This provides a theoretical advancement for optimization in machine learning by relaxing assumptions for linear convergence in saddle point problems, though it is incremental as it builds on prior work.
The paper tackles the convex-concave saddle point problem by proving that the primal-dual gradient method achieves linear convergence without strong convexity in the primal function, requiring only full column rank of the coupling matrix, and extends this analysis to a stochastic variance reduced gradient method for finite-sum problems.
We consider the convex-concave saddle point problem $\min_{x}\max_{y} f(x)+y^\top A x-g(y)$ where $f$ is smooth and convex and $g$ is smooth and strongly convex. We prove that if the coupling matrix $A$ has full column rank, the vanilla primal-dual gradient method can achieve linear convergence even if $f$ is not strongly convex. Our result generalizes previous work which either requires $f$ and $g$ to be quadratic functions or requires proximal mappings for both $f$ and $g$. We adopt a novel analysis technique that in each iteration uses a "ghost" update as a reference, and show that the iterates in the primal-dual gradient method converge to this "ghost" sequence. Using the same technique we further give an analysis for the primal-dual stochastic variance reduced gradient (SVRG) method for convex-concave saddle point problems with a finite-sum structure.