A Distributed Second-Order Algorithm You Can Trust

Celestine Duenner, Aurelien Lucchi, Matilde Gargiani, An Bian, Thomas Hofmann, Martin Jaggi
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1358-1366, 2018.

Abstract

Due to the rapid growth of data and computational resources, distributed optimization has become an active research area in recent years. While first-order methods seem to dominate the field, second-order methods are nevertheless attractive as they potentially require fewer communication rounds to converge. However, there are significant drawbacks that impede their wide adoption, such as the computation and the communication of a large Hessian matrix. In this paper we present a new algorithm for distributed training of generalized linear models that only requires the computation of diagonal blocks of the Hessian matrix on the individual workers. To deal with this approximate information we propose an adaptive approach that - akin to trust-region methods - dynamically adapts the auxiliary model to compensate for modeling errors. We provide theoretical rates of convergence for a wide class of problems including $L_1$-regularized objectives. We also demonstrate that our approach achieves state-of-the-art results on multiple large benchmark datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-duenner18a, title = {A Distributed Second-Order Algorithm You Can Trust}, author = {Duenner, Celestine and Lucchi, Aurelien and Gargiani, Matilde and Bian, An and Hofmann, Thomas and Jaggi, Martin}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1358--1366}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/duenner18a/duenner18a.pdf}, url = {https://proceedings.mlr.press/v80/duenner18a.html}, abstract = {Due to the rapid growth of data and computational resources, distributed optimization has become an active research area in recent years. While first-order methods seem to dominate the field, second-order methods are nevertheless attractive as they potentially require fewer communication rounds to converge. However, there are significant drawbacks that impede their wide adoption, such as the computation and the communication of a large Hessian matrix. In this paper we present a new algorithm for distributed training of generalized linear models that only requires the computation of diagonal blocks of the Hessian matrix on the individual workers. To deal with this approximate information we propose an adaptive approach that - akin to trust-region methods - dynamically adapts the auxiliary model to compensate for modeling errors. We provide theoretical rates of convergence for a wide class of problems including $L_1$-regularized objectives. We also demonstrate that our approach achieves state-of-the-art results on multiple large benchmark datasets.} }
Endnote
%0 Conference Paper %T A Distributed Second-Order Algorithm You Can Trust %A Celestine Duenner %A Aurelien Lucchi %A Matilde Gargiani %A An Bian %A Thomas Hofmann %A Martin Jaggi %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-duenner18a %I PMLR %P 1358--1366 %U https://proceedings.mlr.press/v80/duenner18a.html %V 80 %X Due to the rapid growth of data and computational resources, distributed optimization has become an active research area in recent years. While first-order methods seem to dominate the field, second-order methods are nevertheless attractive as they potentially require fewer communication rounds to converge. However, there are significant drawbacks that impede their wide adoption, such as the computation and the communication of a large Hessian matrix. In this paper we present a new algorithm for distributed training of generalized linear models that only requires the computation of diagonal blocks of the Hessian matrix on the individual workers. To deal with this approximate information we propose an adaptive approach that - akin to trust-region methods - dynamically adapts the auxiliary model to compensate for modeling errors. We provide theoretical rates of convergence for a wide class of problems including $L_1$-regularized objectives. We also demonstrate that our approach achieves state-of-the-art results on multiple large benchmark datasets.
APA
Duenner, C., Lucchi, A., Gargiani, M., Bian, A., Hofmann, T. & Jaggi, M.. (2018). A Distributed Second-Order Algorithm You Can Trust. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1358-1366 Available from https://proceedings.mlr.press/v80/duenner18a.html.

Related Material