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 $L_2$ 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/\varepsilon))$ 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 (Chu et 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.

@article{mahajan-2018,
  title = {An efficient distributed learning algorithm based on effective local functional approximations},
  author = {Mahajan, Dhruv and Agrawal, Nikunj and Keerthi, S Sathiya and Sellamanickam, Sundararajan and Bottou, L{\'e}on},
  journal = {The Journal of Machine Learning Research},
  volume = {19},
  number = {1},
  pages = {2942--2978},
  year = {2018},
  url = {http://leon.bottou.org/papers/mahajan-2018},
}