Randomized Primal-Dual Methods with Adaptive Step Sizes

In this paper we propose a class of randomized primal-dual methods incorporating line search to contend with large-scale saddle point (SP) problems defined by a convex-concave function L(x, y), ^PM_i=1f_i(x_i)+Φ(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 ∇_yΦ(·, ·) is Lipschitz and ∇_xΦ(·, y) is coordinate-wise Lipschitz for any fixed y, the ergodic sequence generated by the algorithm achieves the O(M/k) convergence rate in the expected primal-dual gap. Furthermore, assuming that L(·, y) is strongly convex for any y, and that Φ(x, ·) is affine for any x, the scheme enjoys a faster rate of O(M/k²) 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.