LocalNewton: Reducing Communication Bottleneck for Distributed Learning

Abstract

To address the communication bottleneck problem in distributed optimization within a master-worker framework, we propose LocalNewton, a distributed second-order algorithm with local averaging. In LocalNewton, the worker machines update their model in every iteration by finding a suitable second-order descent direction using only the data and model stored in their own local memory. We let the workers run multiple such iterations locally and communicate the models to the master node only once every few (say L) iterations. LocalNewton is highly practical since it requires only one hyperparameter, the number L of local iterations. We use novel matrix concentration-based techniques to obtain theoretical guarantees for LocalNewton, and we validate them with detailed empirical evaluation. To enhance practicability, we devise an adaptive scheme to choose L, and we show that this reduces the number of local iterations in worker machines between two model synchronizations as the training proceeds, successively refining the model quality at the master. Via extensive experiments using several real-world datasets with AWS Lambda workers and an AWS EC2 master, we show that LocalNewton requires fewer than 60% of the communication rounds (between master and workers) and less than 40% of the end-to-end running time, compared to state-of-the-art algorithms, to reach the same training~loss.

arXiv commentTo be published in Uncertainty in Artificial Intelligence (UAI) 2021

References in corpus (15)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Sparsified SGD with Memory
• Local SGD Converges Fast and Communicates Little
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• 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
• OverSketch: Approximate Matrix Multiplication for the Cloud
• PyHessian: Neural Networks Through the Lens of the Hessian
• Distributed Learning with Sublinear Communication
• Stochastic Weight Averaging in Parallel: Large-Batch Training that Generalizes Well
• Distributed estimation of the inverse Hessian by determinantal averaging
• Distributed Newton Can Communicate Less and Resist Byzantine Workers

Cited by in corpus (3)

• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• On Second-order Optimization Methods for Federated Learning