On Biased Compression for Distributed Learning

Abstract

In the last few years, various communication compression techniques have emerged as an indispensable tool helping to alleviate the communication bottleneck in distributed learning. However, despite the fact biased compressors often show superior performance in practice when compared to the much more studied and understood unbiased compressors, very little is known about them. In this work we study three classes of biased compression operators, two of which are new, and their performance when applied to (stochastic) gradient descent and distributed (stochastic) gradient descent. We show for the first time that biased compressors can lead to linear convergence rates both in the single node and distributed settings. We prove that distributed compressed SGD method, employed with error feedback mechanism, enjoys the ergodic rate $O\left(\delta L\exp \left[-\frac{\mu K}{\delta L}\right]+\frac{(C+\delta D)}{K\mu }\right)$, where $\delta \ge 1$ is a compression parameter which grows when more compression is applied, $L$ and $\mu$ are the smoothness and strong convexity constants, $C$ captures stochastic gradient noise ($C=0$ if full gradients are computed on each node) and $D$ captures the variance of the gradients at the optimum ($D=0$ for over-parameterized models). Further, via a theoretical study of several synthetic and empirical distributions of communicated gradients, we shed light on why and by how much biased compressors outperform their unbiased variants. Finally, we propose several new biased compressors with promising theoretical guarantees and practical performance.

50 pages, 9 figures, 5 tables, 22 theorems and lemmas, 7 new compression operators, 1 algorithm

References in corpus (1)

• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction

Cited by in corpus (31)

• A Field Guide to Federated Optimization
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Optimal Gradient Compression for Distributed and Federated Learning
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• Recent theoretical advances in decentralized distributed convex optimization
• Rethinking gradient sparsification as total error minimization
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• On the Convergence of SGD with Biased Gradients
• MARINA: Faster Non-Convex Distributed Learning with Compression
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
• What Do We Mean by Generalization in Federated Learning?
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Local SGD: Unified Theory and New Efficient Methods
• DRIVE: One-bit Distributed Mean Estimation
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Error Compensated Distributed SGD Can Be Accelerated
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• On Faster Convergence of Scaled Sign Gradient Descent
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• About some works of Boris Polyak on convergence of gradient methods and their development
• Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimization
• Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization
• On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
• Parallel and Distributed algorithms for ML problems