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

Abstract

We consider the convex-concave saddle point problem ${\min }_x{\max }_{y}f(x)+y^{\top }Ax-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.

arXiv commentPublished in AISTATS 2019

References in corpus (6)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Convex Sparse Matrix Factorizations
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Gradient descent GAN optimization is locally stable
• Stochastic Variance Reduction Methods for Policy Evaluation
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms

Cited by in corpus (11)

• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• Generalization Bounds for Stochastic Saddle Point Problems
• Exponential Stability of Primal-Dual Gradient Dynamics with Non-Strong Convexity
• An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• A generic adaptive restart scheme with applications to saddle point algorithms
• Block Belief Propagation for Parameter Learning in Markov Random Fields
• Primal-Dual Block Frank-Wolfe