DINO: Distributed Newton-Type Optimization Method

Rixon Crane, Fred Roosta
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:2174-2184, 2020.

Abstract

We present a novel communication-efficient Newton-type algorithm for finite-sum optimization over a distributed computing environment. Our method, named DINO, overcomes both theoretical and practical shortcomings of similar existing methods. Under minimal assumptions, we guarantee global sub-linear convergence of DINO to a first-order stationary point for general non-convex functions and arbitrary data distribution over the network. Furthermore, for functions satisfying Polyak-Lojasiewicz (PL) inequality, we show that DINO enjoys a linear convergence rate. Our proposed algorithm is practically parameter free, in that it will converge regardless of the selected hyper-parameters, which are easy to tune. Additionally, its sub-problems are simple linear least-squares, for which efficient solvers exist, and numerical simulations demonstrate the efficiency of DINO as compared with similar alternatives.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-crane20a, title = {{DINO}: Distributed {N}ewton-Type Optimization Method}, author = {Crane, Rixon and Roosta, Fred}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {2174--2184}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/crane20a/crane20a.pdf}, url = {https://proceedings.mlr.press/v119/crane20a.html}, abstract = {We present a novel communication-efficient Newton-type algorithm for finite-sum optimization over a distributed computing environment. Our method, named DINO, overcomes both theoretical and practical shortcomings of similar existing methods. Under minimal assumptions, we guarantee global sub-linear convergence of DINO to a first-order stationary point for general non-convex functions and arbitrary data distribution over the network. Furthermore, for functions satisfying Polyak-Lojasiewicz (PL) inequality, we show that DINO enjoys a linear convergence rate. Our proposed algorithm is practically parameter free, in that it will converge regardless of the selected hyper-parameters, which are easy to tune. Additionally, its sub-problems are simple linear least-squares, for which efficient solvers exist, and numerical simulations demonstrate the efficiency of DINO as compared with similar alternatives.} }
Endnote
%0 Conference Paper %T DINO: Distributed Newton-Type Optimization Method %A Rixon Crane %A Fred Roosta %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-crane20a %I PMLR %P 2174--2184 %U https://proceedings.mlr.press/v119/crane20a.html %V 119 %X We present a novel communication-efficient Newton-type algorithm for finite-sum optimization over a distributed computing environment. Our method, named DINO, overcomes both theoretical and practical shortcomings of similar existing methods. Under minimal assumptions, we guarantee global sub-linear convergence of DINO to a first-order stationary point for general non-convex functions and arbitrary data distribution over the network. Furthermore, for functions satisfying Polyak-Lojasiewicz (PL) inequality, we show that DINO enjoys a linear convergence rate. Our proposed algorithm is practically parameter free, in that it will converge regardless of the selected hyper-parameters, which are easy to tune. Additionally, its sub-problems are simple linear least-squares, for which efficient solvers exist, and numerical simulations demonstrate the efficiency of DINO as compared with similar alternatives.
APA
Crane, R. & Roosta, F.. (2020). DINO: Distributed Newton-Type Optimization Method. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:2174-2184 Available from https://proceedings.mlr.press/v119/crane20a.html.

Related Material