Stochastic primal-dual coordinate method for regularized empirical risk minimization

Yuchen Zhang, Lin Xiao

Research output: Contribution to journalArticlepeer-review

53 Scopus citations


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 variables. An extrapolation step on the primal variables 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.

Original languageEnglish
Pages (from-to)1-42
Number of pages42
JournalJournal of Machine Learning Research
StatePublished - Jul 1 2017
Externally publishedYes


  • Computational complexity
  • Convex-concave saddle point problems
  • Empirical risk minimization
  • Primal-dual algorithms
  • Randomized algorithms


Dive into the research topics of 'Stochastic primal-dual coordinate method for regularized empirical risk minimization'. Together they form a unique fingerprint.

Cite this