Randomized Primal-Dual Methods with Adaptive Step Sizes

In this paper we propose a class of randomized primal-dual methods to contend with large-scale saddle point problems defined by a convex-concave function L(x,y)triangleqsumi=1m fi(xi)+Phi(x,y)-h(y). We analyze the convergence rate of the proposed method under mere convexity and strong convexity assumptions of L in x-variable. In particular, assuming nablayPhi(·,·) is Lipschitz and nablaxPhi(·,y) is coordinate-wise Lipschitz for any fixed y, the ergodic sequence generated by the algorithm achieves the convergence rate of O(M/k) in the expected primal-dual gap. Furthermore, assuming that L(·,y) is strongly convex for any y, and that Phi(x,·) is affine for any x, the scheme enjoys a faster rate of O(M/k2) in terms of primal solution suboptimality. We implemented the proposed algorithmic framework to solve kernel matrix learning problem, and tested it against other state-of-the-art first-order methods