GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
arXiv:1709.03528
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.
arXiv commentFixed some typos. Improved writing
References in corpus (20)
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Federated Learning: Strategies for Improving Communication Efficiency
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- Distributed Coordinate Descent Method for Learning with Big Data
- Randomized algorithms for matrices and data
- Federated Multi-Task Learning
- AIDE: Fast and Communication Efficient Distributed Optimization
- On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
- CoCoA: A General Framework for Communication-Efficient Distributed Optimization
- Sub-Sampled Newton Methods I: Globally Convergent Algorithms
- Sub-Sampled Newton Methods II: Local Convergence Rates
- Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
- Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
- Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
- SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions
- A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization
- A Parallel SGD method with Strong Convergence
- An efficient distributed learning algorithm based on effective local functional approximations
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