DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization
arXiv:1901.05134
Abstract
For optimization of a sum of functions in a distributed computing environment, we present a novel communication efficient Newton-type algorithm that enjoys a variety of advantages over similar existing methods. Similar to Newton-MR, our algorithm, DINGO, is derived by optimization of the gradient's norm as a surrogate function. DINGO does not impose any specific form on the underlying functions, and its application range extends far beyond convexity. In addition, the distribution of the data across the computing environment can be arbitrary. Further, the underlying sub-problems of DINGO are simple linear least-squares, for which a plethora of efficient algorithms exist. Lastly, DINGO involves a few hyper-parameters that are easy to tune. Moreover, we theoretically show that DINGO is not sensitive to the choice of its hyper-parameters in that a strict reduction in the gradient norm is guaranteed, regardless of the selected hyper-parameters. We demonstrate empirical evidence of the effectiveness, stability and versatility of our method compared to other relevant algorithms.
arXiv comment35 pages
Cited by in corpus (12)
- Guided parallelized stochastic gradient descent for delay compensation
- FedNL: Making Newton-Type Methods Applicable to Federated Learning
- rTop-k: A Statistical Estimation Approach to Distributed SGD
- Distributed Second Order Methods with Fast Rates and Compressed Communication
- Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
- Newton-ADMM: A Distributed GPU-Accelerated Optimizer for Multiclass Classification Problems
- Distributed Newton Can Communicate Less and Resist Byzantine Workers
- A Stochastic Newton Algorithm for Distributed Convex Optimization
- DINO: Distributed Newton-Type Optimization Method
- Implicit Langevin Algorithms for Sampling From Log-concave Densities
- Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
- On Second-order Optimization Methods for Federated Learning