An Exact Quantized Decentralized Gradient Descent Algorithm

Abstract

We consider the problem of decentralized consensus optimization, where the sum of $n$ smooth and strongly convex functions are minimized over $n$ distributed agents that form a connected network. In particular, we consider the case that the communicated local decision variables among nodes are quantized in order to alleviate the communication bottleneck in distributed optimization. We propose the Quantized Decentralized Gradient Descent (QDGD) algorithm, in which nodes update their local decision variables by combining the quantized information received from their neighbors with their local information. We prove that under standard strong convexity and smoothness assumptions for the objective function, QDGD achieves a vanishing mean solution error under customary conditions for quantizers. To the best of our knowledge, this is the first algorithm that achieves vanishing consensus error in the presence of quantization noise. Moreover, we provide simulation results that show tight agreement between our derived theoretical convergence rate and the numerical results.

References in corpus (6)

• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Speeding Up Distributed Machine Learning Using Codes
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Decentralized Quasi-Newton Methods
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers

Cited by in corpus (29)

• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Quantization for decentralized learning under subspace constraints
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Distributed Online Optimization in Time-Varying Unbalanced Networks without Explicit Subgradients
• Decentralized Deep Learning with Arbitrary Communication Compression
• FedAT: A High-Performance and Communication-Efficient Federated Learning System with Asynchronous Tiers
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• Distributed and Inexact Proximal Gradient Method for Online Convex Optimization
• Distributed Adaptive Learning Under Communication Constraints
• Linear Convergent Decentralized Optimization with Compression
• An introduction to decentralized stochastic optimization with gradient tracking
• Communication-Efficient Distributed SGD with Compressed Sensing
• Robust and Communication-Efficient Collaborative Learning
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• Compressed Regression over Adaptive Networks
• Nested Distributed Gradient Methods with Adaptive Quantized Communication
• Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
• Private and Communication-Efficient Edge Learning: A Sparse Differential Gaussian-Masking Distributed SGD Approach
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework
• A Stochastic Operator Framework for Optimization and Learning with Sub-Weibull Errors
• Decentralized Composite Optimization with Compression
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Asynchronous Federated Learning for Sensor Data with Concept Drift
• A general framework for decentralized optimization with first-order methods
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems
• Design and Analysis of Uplink and Downlink Communications for Federated Learning
• A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks