ICML 2015poster310 citations
Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
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 method, which alternates between maximizing over one (or more) randomly chosen dual variable and minimizing over the primal variable. We also develop an extension to non-smooth and non-strongly convex loss functions, and an extension with better convergence rate 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.
BibTeX
@InProceedings{pmlr-v37-zhanga15,
title = {Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization},
author = {Zhang, Yuchen and Lin, Xiao},
booktitle = {Proceedings of the 32nd International Conference on Machine Learning},
pages = {353--361},
year = {2015},
editor = {Bach, Francis and Blei, David},
volume = {37},
series = {Proceedings of Machine Learning Research},
address = {Lille, France},
month = {07--09 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v37/zhanga15.pdf},
url = {https://proceedings.mlr.press/v37/zhanga15.html},
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 method, which alternates between maximizing over one (or more) randomly chosen dual variable and minimizing over the primal variable. We also develop an extension to non-smooth and non-strongly convex loss functions, and an extension with better convergence rate 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.}
}