Optimization Online


Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization

Yuchen Zhang(yuczhang***at***eecs.berkeley.edu)
Lin Xiao(lin.xiao***at***microsoft.com)

Abstract: We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variable. An extrapolation step on the primal variable is performed to obtain accelerated convergence rate. We also develop a mini-batch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods.

Keywords: Stochastic Coordinate Descent/Ascent Method, Accelerated Primal-Dual Algorithms, Empirical Risk Minimization

Category 1: Convex and Nonsmooth Optimization

Citation: Microsoft Research Technical Report: MSR-TR-2014-123, September 2014. (arXiv.1409.3257)

Download: [PDF]

Entry Submitted: 09/12/2014
Entry Accepted: 09/12/2014
Entry Last Modified: 09/12/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society