Junyu Zhang is an assistant professor at the Department of Industrial Systems Engineering and Management (ISEM), National University of Singapore. Before joining NUS, he was a postdoctoral research fellow at Princeton University, Department of Electrical and Computer Engineering. He received his Ph.D. degree from University of Minnesota, Twin Cities, in 2020. And he received his B.Sc. degree from Peking University in 2015. He is currently focusing on the convergence and complexity of various stochastic optimization and saddle point problems, as well as their closed related problems in reinforcement learning.
| Name of Speaker | Dr Zhang Junyu |
| Schedule | 29 October 2021, 10am – 11.30am
(60 min talk + 30 min Q&A) |
| Link to Register | https://nus-sg.zoom.us/meeting/register/tZYuc-yqqT4tGN3bunp6tZ9-6SjY3JFy4lYq |
| Title | Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems |
| Abstract | We consider the convex-concave saddle point problems where the decision variables are subject to certain multi-block structure 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 are 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 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. |
