Doubly Stochastic Primal-Dual Coordinate Method for Empirical Risk Minimization

April 4 (Monday) at 1:30 pm GHC-8102

Speaker: Adams Wei Yu

Abstract: We proposed a doubly stochastic primal-dual coordinate optimization algorithm for regularized empirical risk minimization that can be formulated as a bilinear saddle-point problem using convex conjugate functions. Our method randomly samples a block of primal and dual coordinates to update in each iteration. The convergence of our method is established in both the solution's distance to optimality and the primal-dual objective gap. We show that the proposed method has a lower overall complexity than existing coordinate methods when the data matrix has a factorized structure or the proximal mapping on each block of coordinates is computationally expensive, e.g., involves an eigenvalue decomposition. Furthermore, we prove a theoretical lower bound on the iteration complexity of a family of primal-dual (block) coordinate methods, including our method, for bilinear saddle-point problems.
A draft of the work can be found in http://arxiv.org/abs/1508.03390.