# Decentralized Multi-Task Stochastic Optimization With Compressed Communications

arXiv: https://arxiv.org/abs/2112.12373 · HTML: https://mlsanity.com/paper/2112.12373/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 56 references that are in the map.
- First posted on arXiv 23 Dec 2021.

## Builds on (most cited first, 30 of 32)

- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization](https://mlsanity.com/paper/1806.08054/) (2018)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Learning Optimal Resource Allocations in Wireless Systems](https://mlsanity.com/paper/1807.08088/) (2018)
- [An Exact Quantized Decentralized Gradient Descent Algorithm](https://mlsanity.com/paper/1806.11536/) (2018)
- [SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimization](https://mlsanity.com/paper/2005.07041/) (2020)
- [Proximity Without Consensus in Online Multi-Agent Optimization](https://mlsanity.com/paper/1606.05578/) (2016)
- [Zeroth Order Nonconvex Multi-Agent Optimization over Networks](https://mlsanity.com/paper/1710.09997/) (2017)
- [Multitask Diffusion Adaptation over Networks](https://mlsanity.com/paper/1311.4894/) (2013)
- [Distributed Discrete-time Optimization in Multi-agent Networks Using only Sign of Relative State](https://mlsanity.com/paper/1709.08360/) (2017)
- [A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programs](https://mlsanity.com/paper/1512.08370/) (2015)
- [Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method](https://mlsanity.com/paper/1304.5590/) (2013)
- [Quantized Consensus by the ADMM: Probabilistic versus Deterministic Quantizers](https://mlsanity.com/paper/1502.01053/) (2015)
- [Design and Analysis of Distributed Averaging with Quantized Communication](https://mlsanity.com/paper/1403.4696/) (2014)
- [Stochastic Subgradient Algorithms for Strongly Convex Optimization over Distributed Networks](https://mlsanity.com/paper/1409.8277/) (2014)
- [Multitask diffusion adaptation over asynchronous networks](https://mlsanity.com/paper/1412.1798/) (2014)

## Built on by (most cited first, 3 of 3)

- [Differential error feedback for communication-efficient decentralized learning](https://mlsanity.com/paper/2406.18418/) (2024)
- [Decentralized Multi-Task Online Convex Optimization Under Random Link Failures](https://mlsanity.com/paper/2401.02011/) (2024)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)

## Abstract (arXiv)

We consider a multi-agent network where each node has a stochastic (local) cost function that depends on the decision variable of that node and a random variable, and further the decision variables of neighboring nodes are pairwise constrained. There is an aggregate objective function for the network, composed additively of the expected values of the local cost functions at the nodes, and the overall goal of the network is to obtain the minimizing solution to this aggregate objective function subject to all the pairwise constraints. This is to be achieved at the node level using decentralized information and local computation, with exchanges of only compressed information allowed by neighboring nodes. The paper develops algorithms and obtains performance bounds for two different models of local information availability at the nodes: (i) sample feedback, where each node has direct access to samples of the local random variable to evaluate its local cost, and (ii) bandit feedback, where samples of the random variables are not available, but only the values of the local cost functions at two random points close to the decision are available to each node. For both models, with compressed communication between neighbors, we have developed decentralized saddle-point algorithms that deliver performances no different (in order sense) from those without communication compression; specifically, we show that deviation from the global minimum value and violations of the constraints are upper-bounded by O(T^-frac12) and O(T^-frac14), respectively, where T is the number of iterations. Numerical examples provided in the paper corroborate these bounds and demonstrate the communication efficiency of the proposed method.