Stochastic primal-dual method for empirical risk minimization with O(1) per-iteration complexity

Conghui Tan; Shiqian Ma; Tong Zhang; Ji Liu

Stochastic primal-dual method for empirical risk minimization with O(1) per-iteration complexity

Conghui Tan
, Shiqian Ma
, Tong Zhang
, Ji Liu

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English (US)
Pages (from-to)	8366-8375
Number of pages	10
Journal	Advances in Neural Information Processing Systems
Volume	2018-December
State	Published - 2018
Externally published	Yes
Event	32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada Duration: Dec 2 2018 → Dec 8 2018

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Library availability

Discover UIUC Full Text

Cite this

@article{57e4b7beaec544448aa8042c183a6780,

title = "Stochastic primal-dual method for empirical risk minimization with O(1) per-iteration complexity",

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.",

author = "Conghui Tan and Shiqian Ma and Tong Zhang and Ji Liu",

note = "S. Ma is partly supported by a startup package in Department of Mathematics at UC Davis and the National Natural Science Foundation of China under Grant 11631013. J. Liu is in part supported by NSF CCF1718513, IBM faculty award, and NEC fellowship.; 32nd Conference on Neural Information Processing Systems, NeurIPS 2018 ; Conference date: 02-12-2018 Through 08-12-2018",

year = "2018",

language = "English (US)",

volume = "2018-December",

pages = "8366--8375",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

publisher = "Neural information processing systems foundation",

}

TY - JOUR

T1 - Stochastic primal-dual method for empirical risk minimization with O(1) per-iteration complexity

AU - Tan, Conghui

AU - Ma, Shiqian

AU - Zhang, Tong

AU - Liu, Ji

N1 - S. Ma is partly supported by a startup package in Department of Mathematics at UC Davis and the National Natural Science Foundation of China under Grant 11631013. J. Liu is in part supported by NSF CCF1718513, IBM faculty award, and NEC fellowship.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85064845812

UR - https://www.scopus.com/pages/publications/85064845812#tab=citedBy

M3 - Conference article

AN - SCOPUS:85064845812

SN - 1049-5258

VL - 2018-December

SP - 8366

EP - 8375

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

T2 - 32nd Conference on Neural Information Processing Systems, NeurIPS 2018

Y2 - 2 December 2018 through 8 December 2018

ER -

Stochastic primal-dual method for empirical risk minimization with O(1) per-iteration complexity

Abstract

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this