DRIVE: One-bit Distributed Mean Estimation

Abstract

We consider the problem where $n$ clients transmit $d$-dimensional real-valued vectors using $d(1+o(1))$ bits each, in a manner that allows the receiver to approximately reconstruct their mean. Such compression problems naturally arise in distributed and federated learning. We provide novel mathematical results and derive computationally efficient algorithms that are more accurate than previous compression techniques. We evaluate our methods on a collection of distributed and federated learning tasks, using a variety of datasets, and show a consistent improvement over the state of the art.

Appears in NeurIPS 2021

References in corpus (17)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• LEAF: A Benchmark for Federated Settings
• Sparsified SGD with Memory
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Distributed Mean Estimation with Limited Communication
• Post-training 4-bit quantization of convolution networks for rapid-deployment
• Uncertainty Principles and Vector Quantization
• Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
• On Biased Compression for Distributed Learning
• Communication-efficient distributed SGD with Sketching

Cited by in corpus (1)

• Bit-efficient Numerical Aggregation and Stronger Privacy for Trust in Federated Analytics