Distributed Stochastic Optimization of Regularized Risk via Saddle-Point Problem
Distributed Stochastic Optimization of Regularized Risk via Saddle-Point Problem
复制标题
DOI：
10.1007/978-3-319-71249-9_28
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Shin Matsushima;Hyokun Yun;S. Vishwanathan
中科院分区：
文献类型：
--
作者：
Shin Matsushima;Hyokun Yun;S. Vishwanathan
许多机器学习算法使正则化风险最小化，随机优化被广泛用于这一任务。在处理海量数据时，需要并行执行随机优化。遗憾的是，许多现有的随机优化算法不能有效地并行化。本文证明了正则化风险最小化问题可以改写为等价的鞍点问题，并提出了一种有效的分布式随机优化算法。我们证明了该算法的收敛速度；值得注意的是，我们的分析表明，该算法几乎与处理器的数量成线性关系。通过实验验证了该算法在正则化风险最小化问题上与其他并行、通用随机和批处理优化算法相比具有较强的竞争力。
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.