  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.
