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 = "Publisher Copyright: {\textcopyright} 2018 Curran Associates Inc.All rights reserved.; 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

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 - http://www.scopus.com/inward/record.url?scp=85064845812&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064845812&partnerID=8YFLogxK

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