# Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 34 references that are in the map.
- First posted on arXiv 7 Jun 2021.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [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)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Stochastic Distributed Learning with Gradient Quantization and Variance Reduction](https://mlsanity.com/paper/1904.05115/) (2019)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [Stochastic Sign Descent Methods: New Algorithms and Better Theory](https://mlsanity.com/paper/1905.12938/) (2019)
- [Adaptive Gradient Quantization for Data-Parallel SGD](https://mlsanity.com/paper/2010.12460/) (2020)
- [Randomized Distributed Mean Estimation: Accuracy vs Communication](https://mlsanity.com/paper/1611.07555/) (2016)
- [Optimal Gradient Compression for Distributed and Federated Learning](https://mlsanity.com/paper/2010.03246/) (2020)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization](https://mlsanity.com/paper/1908.06077/) (2019)
- [On Optimal Probabilities in Stochastic Coordinate Descent Methods](https://mlsanity.com/paper/1310.3438/) (2013)
- [Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity](https://mlsanity.com/paper/1412.8060/) (2014)
- [Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches](https://mlsanity.com/paper/1809.09354/) (2018)
- [One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods](https://mlsanity.com/paper/1905.11266/) (2019)

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

- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneity](https://mlsanity.com/paper/2404.09816/) (2024)
- [Unbiased Gradient Low-Rank Projection](https://mlsanity.com/paper/2510.17802/) (2025)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Data-Aware Gradient Compression for FL in Communication-Constrained Mobile Computing](https://mlsanity.com/paper/2311.07324/) (2023)
- [Problem-dependent convergence bounds for randomized linear gradient compression](https://mlsanity.com/paper/2411.12898/) (2024)
- [Layer-wise Quantization for Quantized Optimistic Dual Averaging](https://mlsanity.com/paper/2505.14371/) (2025)
- [MSfusion: A Dynamic Model Splitting Approach for Resource-Constrained Machines to Collaboratively Train Larger Models](https://mlsanity.com/paper/2407.03622/) (2024)
- [Randomized Subspace Nesterov Accelerated Gradient](https://mlsanity.com/paper/2605.00740/) (2026)

## Abstract (arXiv)

To address the high communication costs of distributed machine learning, a large body of work has been devoted in recent years to designing various compression strategies, such as sparsification and quantization, and optimization algorithms capable of using them. Recently, Safaryan et al. (2021) pioneered a dramatically different compression design approach: they first use the local training data to form local smoothness matrices and then propose to design a compressor capable of exploiting the smoothness information contained therein. While this novel approach leads to substantial savings in communication, it is limited to sparsification as it crucially depends on the linearity of the compression operator. In this work, we generalize their smoothness-aware compression strategy to arbitrary unbiased compression operators, which also include sparsification. Specializing our results to stochastic quantization, we guarantee significant savings in communication complexity compared to standard quantization. In particular, we prove that block quantization with n blocks theoretically outperforms single block quantization, leading to a reduction in communication complexity by an O(n) factor, where n is the number of nodes in the distributed system. Finally, we provide extensive numerical evidence with convex optimization problems that our smoothness-aware quantization strategies outperform existing quantization schemes as well as the aforementioned smoothness-aware sparsification strategies with respect to three evaluation metrics: the number of iterations, the total amount of bits communicated, and wall-clock time.