Serhat Aybat, Pennsylvania State University

Abstract

In this talk, we propose a primal-dual algorithm with a momentum term, which can be viewed as a generalization of the method proposed by Chambolle and Pock in 2016, to solve saddle point problems defined by a convex-concave function L(x,y) = f(x) + Phi(x,y) - h(y) with a general coupling term Phi(x,y) that is not assumed to be bilinear. Given a saddle point (x*,y*), assuming the partial gradients of Phi satisfy certain Lipshitz continuity property, we derive error bounds in terms of L(x_k,x*)-L(y*,y_k) for the ergodic sequence {x_k, y_k}; in particular, we show O(1/k) rate that when the problem is merely convex in x. Furthermore, assuming Phi(x,y) is linear in y for each fixed x and f is strongly convex, we can obtain the ergodic convergence rate of O(1/k^2) – we are not aware of any other work in the related literature showing O(1/k^2) rate when Phi is not bilinear. We tested our method for solving kernel matrix learning problem, and compare it against the Mirror-prox algorithm and interior point methods.

Slides     Video