Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems

Abstract

We consider the convex-concave saddle point problem ${\min }_{\mathbf{x}}{\max }_{\mathbf{y}}\Phi (\mathbf{x},\mathbf{y})$, where the decision variables $\mathbf{x}$ and/or $\mathbf{y}$ subject to a multi-block structure and affine coupling constraints, and $\Phi (\mathbf{x},\mathbf{y})$ possesses certain separable structure. Although the minimization counterpart of such problem has been widely studied under the topics of ADMM, this minimax problem is rarely investigated. In this paper, a convenient notion of $\epsilon$-saddle point is proposed, under which the convergence rate of several proposed algorithms are analyzed. When only one of $\mathbf{x}$ and $\mathbf{y}$ has multiple blocks and affine constraint, several natural extensions of ADMM are proposed to solve the problem. Depending on the number of blocks and the level of smoothness, $\mathcal{O}(1/T)$ or $\mathcal{O}(1/\sqrt{T})$ convergence rates are derived for our algorithms. When both $\mathbf{x}$ and $\mathbf{y}$ have multiple blocks and affine constraints, a new algorithm called ExtraGradient Method of Multipliers (EGMM) is proposed. Under desirable smoothness condition, an $\mathcal{O}(1/T)$ rate of convergence can be guaranteed regardless of the number of blocks in $\mathbf{x}$ and $\mathbf{y}$. In depth comparison between EGMM (fully primal-dual method) and ADMM (approximate dual method) is made over the multi-block optimization problems to illustrate the advantage of the EGMM.

arXiv comment25 pages

References in corpus (6)

• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Near-Optimal Algorithms for Minimax Optimization
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Last-iterate convergence rates for min-max optimization
• Improved Algorithms for Convex-Concave Minimax Optimization