Quantization for decentralized learning under subspace constraints

Abstract

In this paper, we consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints that require the minimizers across the network to lie in low-dimensional subspaces. This constrained formulation includes consensus or single-task optimization as special cases, and allows for more general task relatedness models such as multitask smoothness and coupled optimization. In order to cope with communication constraints, we propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates before communicating with their neighbors. The analysis shows that, under some general conditions on the quantization noise, and for sufficiently small step-sizes $\mu$, the strategy is stable both in terms of mean-square error and average bit rate: by reducing $\mu$, it is possible to keep the estimation errors small (on the order of $\mu$) without increasing indefinitely the bit rate as $\mu \to 0$. Simulations illustrate the theoretical findings and the effectiveness of the proposed approach, revealing that decentralized learning is achievable at the expense of only a few bits.

References in corpus (14)

• Federated Learning: Challenges, Methods, and Future Directions
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Gossip Algorithms for Distributed Signal Processing
• Multitask Diffusion Adaptation over Networks
• Diffusion Adaptation over Networks under Imperfect Information Exchange and Non-stationary Data
• Communication Compression for Decentralized Training
• An Exact Quantized Decentralized Gradient Descent Algorithm
• Distributed Optimization With Local Domains: Applications in MPC and Network Flows
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Multitask learning over graphs: An Approach for Distributed, Streaming Machine Learning
• Diffusion LMS for Multitask Problems with Local Linear Equality Constraints
• Adaptation and learning over networks under subspace constraints -- Part I: Stability Analysis
• Quantized Decentralized Stochastic Learning over Directed Graphs
• $\mathcal{C}\mathcal{I}\mathcal{R}\mathcal{FE}$: A Distributed Random Fields Estimator

Cited by in corpus (1)

• Compressed Regression over Adaptive Networks