Randomized Primal-Dual Methods with Adaptive Step Sizes

MaRDI QIDQ6302872zbMATH OpenFDO

Authors Erfan Yazdandoost Hamedani, Afrooz Jalilzadeh, N. S. Aybat

Publication date 11 June 2018

Abstract: 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 $mathcalL(mathbfx,y)riangleqsu{m}_{i=1}^m{f}_i(x_i)+Phi(mathbfx,y)-h(y)$. We analyze the convergence rate of the proposed method under mere convexity and strong convexity assumptions of $mathcalL$ in $mathbfx$-variable. In particular, assuming $abl{a}_{y}Phi(cdot,cdot)$ is Lipschitz and $abl{a}_{m}athbfxPhi(cdot,y)$ is coordinate-wise Lipschitz for any fixed $y$, the ergodic sequence generated by the algorithm achieves the convergence rate of $mathcalO(M/k)$ in the expected primal-dual gap. Furthermore, assuming that $mathcalL(cdot,y)$ is strongly convex for any $y$, and that $Phi(mathbfx,cdot)$ is affine for any $mathbfx$, the scheme enjoys a faster rate of $mathcalO(M/k^2)$ 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

This page was built for publication: Randomized Primal-Dual Methods with Adaptive Step Sizes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6302872)