Stochastic Primal-Dual Method for Empirical Risk Minimization with $\mathcal{O}(1)$ Per-Iteration Complexity
This addresses computational efficiency for machine learning practitioners dealing with high-dimensional data, though it appears incremental as it builds on existing stochastic methods.
The paper tackles the regularized empirical risk minimization problem with linear predictors by proposing a new stochastic primal-dual method that requires only O(1) operations per iteration, and numerical experiments show it is faster than existing methods like proximal SGD, SVRG, and SAGA on high-dimensional problems.
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.