===== An efficient distributed learning algorithm based on effective local functional approximations =====

//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.

<box 99% orange>
Dhruv Mahajan, Nikunj Agrawal, S Sathiya Keerthi, Sundararajan Sellamanickam and Léon Bottou:  **An efficient distributed learning algorithm based on effective local functional approximations**,  //The Journal of Machine Learning Research//, 19(1):2942--2978, 2018.

[[http://leon.bottou.org/publications/djvu/jmlr-2018.djvu|jmlr-2018.djvu]]
[[http://leon.bottou.org/publications/pdf/jmlr-2018.pdf|jmlr-2018.pdf]]
[[http://leon.bottou.org/publications/psgz/jmlr-2018.ps.gz|jmlr-2018.ps.gz]]
</box>

  @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},
  }