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

arXiv: https://arxiv.org/abs/2109.14212 · HTML: https://mlsanity.com/paper/2109.14212/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2021.

## Built on by (most cited first, 1 of 1)

- [An Augmented Lagrangian Approach to Conically Constrained Non-monotone Variational Inequality Problems](https://mlsanity.com/paper/2306.01214/) (2023)

## Abstract (arXiv)

We consider the convex-concave saddle point problem minxmaxyPhi(x,y), where the decision variables x and/or y subject to a multi-block structure and affine coupling constraints, and Phi(x,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 ε-saddle point is proposed, under which the convergence rate of several proposed algorithms are analyzed. When only one of x and 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, O(1/T) or O(1/√T) convergence rates are derived for our algorithms. When both x and y have multiple blocks and affine constraints, a new algorithm called ExtraGradient Method of Multipliers (EGMM) is proposed. Under desirable smoothness condition, an O(1/T) rate of convergence can be guaranteed regardless of the number of blocks in x and 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.