Stochastic Primal-Dual Method For Empirical Risk Minimization With O(1) Per-Iteration Complexity

Authors:
Conghui Tan The Chinese University of Hong Kong
Tong Zhang Tencent AI Lab
Shiqian Ma
Ji Liu University of Rochester, Tencent AI lab

Introduction:

Regularized empirical risk minimization problem with linear predictor appears frequently in machine learning.In this paper, the authors propose a new stochastic primal-dual method to solve this class of problems.

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.

You may want to know: