On Randomized Distributed Coordinate Descent with Quantized Updates

2016/09/18 by Mostafa El Gamal, Gamal, Mostafa El, Lifeng Lai +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems #Stochastic Gradient Optimization Techniques #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1609.05539

Accepted at CISS 2017

openalex publication_date 2016/09/18 · arxiv created 2017/01/20 · arxiv updated 2017/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we study the randomized distributed coordinate descent algorithm with quantized updates. In the literature, the iteration complexity of the randomized distributed coordinate descent algorithm has been characterized under the assumption that machines can exchange updates with an infinite precision. We consider a practical scenario in which the messages exchange occurs over channels with finite capacity, and hence the updates have to be quantized. We derive sufficient conditions on the quantization error such that the algorithm with quantized update still converge. We further verify our theoretical results by running an experiment, where we apply the algorithm with quantized updates to solve a linear regression problem.

Cited by

• Federated Learning: Strategies for Improving Communication Efficiency

Related

• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Convergence Theory of Generalized Distributed Subgradient Method with Random Quantization
• Stability and Generalization for Randomized Coordinate Descent
• Fast Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization
• Distributed Stochastic Approximation for Solving Network Optimization Problems Under Random Quantization