On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication

Abstract

In distributed optimization and machine learning, multiple nodes coordinate to solve large problems. To do this, the nodes need to compress important algorithm information to bits so that it can be communicated over a digital channel. The communication time of these algorithms follows a complex interplay between a) the algorithm's convergence properties, b) the compression scheme, and c) the transmission rate offered by the digital channel. We explore these relationships for a general class of linearly convergent distributed algorithms. In particular, we illustrate how to design quantizers for these algorithms that compress the communicated information to a few bits while still preserving the linear convergence. Moreover, we characterize the communication time of these algorithms as a function of the available transmission rate. We illustrate our results on learning algorithms using different communication structures, such as decentralized algorithms where a single master coordinates information from many workers and fully distributed algorithms where only neighbours in a communication graph can communicate. We conclude that a co-design of machine learning and communication protocols are mandatory to flourish machine learning over networks.

References in corpus (7)

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Harnessing Smoothness to Accelerate Distributed Optimization
• Sparsified SGD with Memory
• Communication-Computation Efficient Gradient Coding
• High-Accuracy Low-Precision Training
• Distributed learning with compressed gradients

Cited by in corpus (13)

• Edge Learning for B5G Networks with Distributed Signal Processing: Semantic Communication, Edge Computing, and Wireless Sensing
• Joint Optimization of Communications and Federated Learning Over the Air
• Distributed and Inexact Proximal Gradient Method for Online Convex Optimization
• A Hybrid Model-based and Data-driven Approach to Spectrum Sharing in mmWave Cellular Networks
• Linear Convergent Decentralized Optimization with Compression
• Communication-Efficient Distributed SGD with Compressed Sensing
• Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networks
• Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
• Decentralized Composite Optimization with Compression
• A Low Complexity Decentralized Neural Net with Centralized Equivalence using Layer-wise Learning
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Quantized Primal-Dual Algorithms for Network Optimization with Linear Convergence
• On the Convergence of Inexact Gradient Descent with Controlled Synchronization Steps