NeurIPS 2018poster42 citations
Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity
Conghui Tan, Tong Zhang, Shiqian Ma, Ji Liu
Abstract
Regularized empirical risk minimization problem with linear predictor appears frequently in machine learning. In this paper, we propose a new stochastic primal-dual method to solve this class of problems. Different from existing methods, our proposed methods only require O(1) operations in each iteration. We also develop a variance-reduction variant of the algorithm that converges linearly. Numerical experiments suggest that our methods are faster than existing ones such as proximal SGD, SVRG and SAGA on high-dimensional problems.
BibTeX
@inproceedings{NEURIPS2018_08048a9c,
author = {Tan, Conghui and Zhang, Tong and Ma, Shiqian and Liu, Ji},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/08048a9c5630ccb67789a198f35d30ec-Paper.pdf},
volume = {31},
year = {2018}
}