Compressed Regression over Adaptive Networks

Abstract

In this work we derive the performance achievable by a network of distributed agents that solve, adaptively and in the presence of communication constraints, a regression problem. Agents employ the recently proposed ACTC (adapt-compress-then-combine) diffusion strategy, where the signals exchanged locally by neighboring agents are encoded with randomized differential compression operators. We provide a detailed characterization of the mean-square estimation error, which is shown to comprise a term related to the error that agents would achieve without communication constraints, plus a term arising from compression. The analysis reveals quantitative relationships between the compression loss and fundamental attributes of the distributed regression problem, in particular, the stochastic approximation error caused by the gradient noise and the network topology (through the Perron eigenvector). We show that knowledge of such relationships is critical to allocate optimally the communication resources across the agents, taking into account their individual attributes, such as the quality of their data or their degree of centrality in the network topology. We devise an optimized allocation strategy where the parameters necessary for the optimization can be learned online by the agents. Illustrative examples show that a significant performance improvement, as compared to a blind (i.e., uniform) resource allocation, can be achieved by optimizing the allocation by means of the provided mean-square-error formulas.

arXiv commentThis work has been submitted to the IEEE for possible publication

References in corpus (12)

• Federated Learning: Challenges, Methods, and Future Directions
• Gossip Algorithms for Distributed Signal Processing
• Distributed Learning in Wireless Sensor Networks
• Network Lasso: Clustering and Optimization in Large Graphs
• Diffusion Adaptation over Networks under Imperfect Information Exchange and Non-stationary Data
• Distributed Pareto Optimization via Diffusion Strategies
• An Exact Quantized Decentralized Gradient Descent Algorithm
• Multitask learning over graphs: An Approach for Distributed, Streaming Machine Learning
• Stability and Performance Limits of Adaptive Primal-Dual Networks
• Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
• Quantization for decentralized learning under subspace constraints
• Distributed Adaptive Learning Under Communication Constraints