When
Title: Primal-dual Methods for Convex-concave Saddle point Problems
Abstract: Recent advances in technology have led researchers to study problems with more complicated structure such as robust classification, distance metric learning, and kernel matrix learning arising in machine learning. In this work, we consider a convex-concave saddle point problem which includes convex constrained optimization problems as a special case. therefore, there has been a pressing need for more powerful, iterative optimization tools that can handle these complicated structures while employing efficient computations in each iteration. This demand has attracted a vast amount of research focusing on developing primal-dual algorithms due to the versatility of the framework. We proposed a primal-dual algorithm and its block coordinate randomized variant with a new momentum term leading to an optimal convergence rate. Moreover, to facilitate the practical implementation of the algorithm a backtracking technique is also proposed. The significance of this work is mainly due to 1) the simplicity of the proposed method, 2) the new momentum in terms of gradients, and 3) its ability to have larger step-sizes compared to the other related work.