# Communication-Efficient Distributed Optimization with Quantized Preconditioners

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 38 references that are in the map.
- First posted on arXiv 14 Feb 2021.

## Builds on (most cited first, 18 of 18)

- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/1802.09941/) (2018)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [AIDE: Fast and Communication Efficient Distributed Optimization](https://mlsanity.com/paper/1608.06879/) (2016)
- [Communication-Efficient Distributed Dual Coordinate Ascent](https://mlsanity.com/paper/1409.1458/) (2014)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [Communication-Computation Efficient Gradient Coding](https://mlsanity.com/paper/1802.03475/) (2018)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication](https://mlsanity.com/paper/1902.11163/) (2019)
- [The Communication Complexity of Optimization](https://mlsanity.com/paper/1906.05832/) (2019)
- [Communication-efficient Variance-reduced Stochastic Gradient Descent](https://mlsanity.com/paper/2003.04686/) (2020)
- [Randomized Block-Diagonal Preconditioning for Parallel Learning](https://mlsanity.com/paper/2006.13591/) (2020)

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

- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning](https://mlsanity.com/paper/2111.01847/) (2021)
- [SHED: A Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing](https://mlsanity.com/paper/2202.05800/) (2022)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [Q-SHED: Distributed Optimization at the Edge via Hessian Eigenvectors Quantization](https://mlsanity.com/paper/2305.10852/) (2023)
- [Eva: A General Vectorized Approximation Framework for Second-order Optimization](https://mlsanity.com/paper/2308.02123/) (2023)
- [Quantized Adaptive Subgradient Algorithms and Their Applications](https://mlsanity.com/paper/2208.05631/) (2022)

## Abstract (arXiv)

We investigate fast and communication-efficient algorithms for the classic problem of minimizing a sum of strongly convex and smooth functions that are distributed among n different nodes, which can communicate using a limited number of bits. Most previous communication-efficient approaches for this problem are limited to first-order optimization, and therefore have linear dependence on the condition number in their communication complexity. We show that this dependence is not inherent: communication-efficient methods can in fact have sublinear dependence on the condition number. For this, we design and analyze the first communication-efficient distributed variants of preconditioned gradient descent for Generalized Linear Models, and for Newton's method. Our results rely on a new technique for quantizing both the preconditioner and the descent direction at each step of the algorithms, while controlling their convergence rate. We also validate our findings experimentally, showing fast convergence and reduced communication.