Primal-Dual First-Order Methods

讲座简介

We consider the convex-concave saddle point problems where the decision variables are subject to certain multi-block structures and affine coupling constraints, and the objective function possesses a certain separable structure. Although the minimization counterpart of such a 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 is analyzed. When only one of the decision variables has multiple blocks and affine constraints, 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/\sqrt{T}) convergence rates are derived for our algorithms. When both decision variables have multiple blocks and affine constraints, a new algorithm called the ExtraGradient Method of Multipliers (EGMM) is proposed. Under desirable smoothness conditions, an O(1/T) rate of convergence can be guaranteed regardless of the number of blocks in the decision variables. An 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 benefits of the EGMM.

时间

2021-12-22

下午 13:30 ~ 15:00

主讲人

Junyu Zhang，National University of Singapore

地点

会议号码:  949 480 034

参会密码:  123456

参会链接：https://meeting.tencent.com/dm/azbKZxZAjCDP