# LocalNewton: Reducing Communication Bottleneck for Distributed Learning

arXiv: https://arxiv.org/abs/2105.07320 · HTML: https://mlsanity.com/paper/2105.07320/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 55 references that are in the map.
- First posted on arXiv 16 May 2021.

## Builds on (most cited first, 30 of 37)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [HAWQ: Hessian AWare Quantization of Neural Networks with Mixed-Precision](https://mlsanity.com/paper/1905.03696/) (2019)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Q-BERT: Hessian Based Ultra Low Precision Quantization of BERT](https://mlsanity.com/paper/1909.05840/) (2019)
- [PyHessian: Neural Networks Through the Lens of the Hessian](https://mlsanity.com/paper/1912.07145/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Communication-efficient distributed SGD with Sketching](https://mlsanity.com/paper/1903.04488/) (2019)
- [Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD](https://mlsanity.com/paper/1810.08313/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [Stochastic Weight Averaging in Parallel: Large-Batch Training that Generalizes Well](https://mlsanity.com/paper/2001.02312/) (2020)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [Distributed Newton Can Communicate Less and Resist Byzantine Workers](https://mlsanity.com/paper/2006.08737/) (2020)
- [On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants](https://mlsanity.com/paper/1506.06840/) (2015)
- [Occupy the Cloud: Distributed Computing for the 99%](https://mlsanity.com/paper/1702.04024/) (2017)
- [Serverless Computing: Current Trends and Open Problems](https://mlsanity.com/paper/1706.03178/) (2017)
- [Distributed estimation of the inverse Hessian by determinantal averaging](https://mlsanity.com/paper/1905.11546/) (2019)
- [Serverless Computing: One Step Forward, Two Steps Back](https://mlsanity.com/paper/1812.03651/) (2018)
- [Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization](https://mlsanity.com/paper/2007.01327/) (2020)
- [OverSketch: Approximate Matrix Multiplication for the Cloud](https://mlsanity.com/paper/1811.02653/) (2018)
- [Distributed Learning with Sublinear Communication](https://mlsanity.com/paper/1902.11259/) (2019)

## Built on by (most cited first, 15 of 15)

- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning](https://mlsanity.com/paper/2111.01847/) (2021)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [On Second-order Optimization Methods for Federated Learning](https://mlsanity.com/paper/2109.02388/) (2021)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [A Stochastic Newton Algorithm for Distributed Convex Optimization](https://mlsanity.com/paper/2110.02954/) (2021)
- [Distributed Quasi-Newton Method for Fair and Fast Federated Learning](https://mlsanity.com/paper/2501.10877/) (2025)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [FedSSO: A Federated Server-Side Second-Order Optimization Algorithm](https://mlsanity.com/paper/2206.09576/) (2022)
- [FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning](https://mlsanity.com/paper/2401.02734/) (2024)
- [GP-FL: Model-Based Hessian Estimation for Second-Order Over-the-Air Federated Learning](https://mlsanity.com/paper/2412.03867/) (2024)
- [FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch](https://mlsanity.com/paper/2409.15216/) (2024)
- [Accelerated Training of Federated Learning via Second-Order Methods](https://mlsanity.com/paper/2505.23588/) (2025)
- [Taming the Instability: A Robust Second-Order Optimizer for Federated Learning over Non-IID Data](https://mlsanity.com/paper/2603.28316/) (2026)
- [Decentralized Learning via Random Walk with Jumps](https://mlsanity.com/paper/2604.12260/) (2026)

## Abstract (arXiv)

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.