Distributed Stochastic Optimization of the Regularized Risk
This addresses the need for efficient parallel optimization in machine learning for large-scale datasets, though it appears incremental as it builds on existing stochastic optimization methods.
The paper tackles the problem of parallelizing stochastic optimization for regularized risk minimization with massive data by proposing a distributed stochastic optimization algorithm based on a saddle-point reformulation, achieving a convergence rate that scales almost linearly with the number of processors and showing competitive performance in empirical evaluations.
Many machine learning algorithms minimize a regularized risk, and stochastic optimization is widely used for this task. When working with massive data, it is desirable to perform stochastic optimization in parallel. Unfortunately, many existing stochastic optimization algorithms cannot be parallelized efficiently. In this paper we show that one can rewrite the regularized risk minimization problem as an equivalent saddle-point problem, and propose an efficient distributed stochastic optimization (DSO) algorithm. We prove the algorithm's rate of convergence; remarkably, our analysis shows that the algorithm scales almost linearly with the number of processors. We also verify with empirical evaluations that the proposed algorithm is competitive with other parallel, general purpose stochastic and batch optimization algorithms for regularized risk minimization.