An efficient distributed learning algorithm based on effective local functional approximations
Authors:
Preprint
Abstract
Scalable machine learning over big data is an important problem that is receiving a lot of attention in recent years. On popular distributed environments such as Hadoop running on a cluster of commodity machines, communication costs are substantial and algorithms need to be designed suitably considering those costs. In this paper we give a novel approach to the distributed training of linear classifiers (involving smooth losses and L2 regularization) that is designed to reduce the total communication costs. At each iteration, the nodes minimize locally formed approximate objective functions; then the resulting minimizers are combined to form a descent direction to move. Our approach gives a lot of freedom in the formation of the approximate objective function as well as in the choice of methods to solve them. The method is shown to have $O(log(1/\epsilon))$ time convergence. The method can be viewed as an iterative parameter mixing method. A special instantiation yields a parallel stochastic gradient descent method with strong convergence. When communication times between nodes are large, our method is much faster than the Terascale method (Agarwal et al., 2011), which is a state of the art distributed solver based on the statistical query model (Chuet al., 2006) that computes function and gradient values in a distributed fashion. We also evaluate against other recent distributed methods and demonstrate superior performance of our method.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Parallel coordinate descent methods for big data optimizationMathematical Programming, 2015
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- On the Use of Stochastic Hessian Information in Optimization Methods for Machine LearningSIAM Journal on Optimization, 2011
- A dual coordinate descent method for large-scale linear SVM2008
- Map-Reduce for Machine Learning on Multicore2007
- Trust region Newton methods for large-scale logistic regression2007
- Cost Approximation: A Unified Framework of Descent Algorithms for Nonlinear ProgramsSIAM Journal on Optimization, 1998
- Decomposition Methods for Differentiable Optimization Problems over Cartesian Product SetsComputational Optimization and Applications, 1998
- Convergence Conditions for Ascent Methods. II: Some CorrectionsSIAM Review, 1971
- Convergence Conditions for Ascent MethodsSIAM Review, 1969