GIANT: Globally Improved Approximate Newton Method for Distributed Optimization

Abstract

For distributed computing environment, we consider the empirical risk minimization problem and propose a distributed and communication-efficient Newton-type optimization method. At every iteration, each worker locally finds an Approximate NewTon (ANT) direction, which is sent to the main driver. The main driver, then, averages all the ANT directions received from workers to form a {\it Globally Improved ANT} (GIANT) direction. GIANT is highly communication efficient and naturally exploits the trade-offs between local computations and global communications in that more local computations result in fewer overall rounds of communications. Theoretically, we show that GIANT enjoys an improved convergence rate as compared with first-order methods and existing distributed Newton-type methods. Further, and in sharp contrast with many existing distributed Newton-type methods, as well as popular first-order methods, a highly advantageous practical feature of GIANT is that it only involves one tuning parameter. We conduct large-scale experiments on a computer cluster and, empirically, demonstrate the superior performance of GIANT.

Fixed some typos. Improved writing

References in corpus (5)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Federated Multi-Task Learning
• AIDE: Fast and Communication Efficient Distributed Optimization
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study

Cited by in corpus (14)

• Federated Learning via Over-the-Air Computation
• Communication-Efficient Edge AI: Algorithms and Systems
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• Distributed Saddle-Point Problems Under Similarity
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
• Newton-ADMM: A Distributed GPU-Accelerated Optimizer for Multiclass Classification Problems
• Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks
• Precise expressions for random projections: Low-rank approximation and randomized Newton
• Newton Method over Networks is Fast up to the Statistical Precision
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
• On Second-order Optimization Methods for Federated Learning