Distributed learning with compressed gradients

Abstract

Asynchronous computation and gradient compression have emerged as two key techniques for achieving scalability in distributed optimization for large-scale machine learning. This paper presents a unified analysis framework for distributed gradient methods operating with staled and compressed gradients. Non-asymptotic bounds on convergence rates and information exchange are derived for several optimization algorithms. These bounds give explicit expressions for step-sizes and characterize how the amount of asynchrony and the compression accuracy affect iteration and communication complexity guarantees. Numerical results highlight convergence properties of different gradient compression algorithms and confirm that fast convergence under limited information exchange is indeed possible.

arXiv comment33 pages, 4 figures, 2 tables

References in corpus (5)

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Revisiting Distributed Synchronous SGD
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server

Cited by in corpus (26)

• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
• Natural Compression for Distributed Deep Learning
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Better Theory for SGD in the Nonconvex World
• 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
• Linearly Converging Error Compensated SGD
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Communication trade-offs for synchronized distributed SGD with large step size
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Stochastic Sign Descent Methods: New Algorithms and Better Theory
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• A flexible framework for communication-efficient machine learning: from HPC to IoT
• Federated Learning is Better with Non-Homomorphic Encryption
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• DEED: A General Quantization Scheme for Communication Efficiency in Bits
• Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization