# Communication-Efficient Algorithms for Decentralized and Stochastic Optimization arXiv: https://arxiv.org/abs/1701.03961 · HTML: https://mlsanity.com/paper/1701.03961/ ## Key facts - Cited by 43 papers in the map (data through 14 Oct 2026). - First posted on arXiv 14 Jan 2017. ## Built on by (most cited first, 30 of 43) - [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021) - [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022) - [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021) - [Federated Learning over Wireless IoT Networks with Optimized Communication and Resources](https://mlsanity.com/paper/2110.11775/) (2021) - [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021) - [Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems](https://mlsanity.com/paper/2112.09579/) (2021) - [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023) - [Communication-Constrained Distributed Quantile Regression with Optimal Statistical Guarantees](https://mlsanity.com/paper/2110.13113/) (2021) - [Confederated Learning: Federated Learning with Decentralized Edge Servers](https://mlsanity.com/paper/2205.14905/) (2022) - [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023) - [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024) - [Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable](https://mlsanity.com/paper/2503.20117/) (2025) - [Blockchain-Based Federated Learning: Incentivizing Data Sharing and Penalizing Dishonest Behavior](https://mlsanity.com/paper/2307.10492/) (2023) - [PIM-Opt: Demystifying Distributed Optimization Algorithms on a Real-World Processing-In-Memory System](https://mlsanity.com/paper/2404.07164/) (2024) - [Distributed Bootstrap for Simultaneous Inference Under High Dimensionality](https://mlsanity.com/paper/2102.10080/) (2021) - [Communication-Efficient Adaptive Batch Size Strategies for Distributed Local Gradient Methods](https://mlsanity.com/paper/2406.13936/) (2024) - [Decentralized Multi-Task Stochastic Optimization With Compressed Communications](https://mlsanity.com/paper/2112.12373/) (2021) - [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023) - [Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy](https://mlsanity.com/paper/2510.19934/) (2025) - [Asynchronous Training Schemes in Distributed Learning with Time Delay](https://mlsanity.com/paper/2208.13154/) (2022) - [A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming](https://mlsanity.com/paper/2211.04088/) (2022) - [CoDeC: Communication-Efficient Decentralized Continual Learning](https://mlsanity.com/paper/2303.15378/) (2023) - [Limited Communications Distributed Optimization via Deep Unfolded Distributed ADMM](https://mlsanity.com/paper/2309.14353/) (2023) - [Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach](https://mlsanity.com/paper/2404.02511/) (2024) - [Convergence of two-timescale gradient descent ascent dynamics: finite-dimensional and mean-field perspectives](https://mlsanity.com/paper/2501.17122/) (2025) - [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021) - [Local Stochastic Factored Gradient Descent for Distributed Quantum State Tomography](https://mlsanity.com/paper/2203.11579/) (2022) - [Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems](https://mlsanity.com/paper/2205.14452/) (2022) - [Enhanced Decentralized Federated Learning based on Consensus in Connected Vehicles](https://mlsanity.com/paper/2209.10722/) (2022) - [Optimal Batch Allocation for Wireless Federated Learning](https://mlsanity.com/paper/2404.02395/) (2024) ## Abstract (arXiv) We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. We first propose a decentralized primal-dual method which can find an ε-solution both in terms of functional optimality gap and feasibility residual in O(1/ε) inter-node communication rounds when the objective functions are convex and the local primal subproblems are solved exactly. Our major contribution is to present a new class of decentralized primal-dual type algorithms, namely the decentralized communication sliding (DCS) methods, which can skip the inter-node communications while agents solve the primal subproblems iteratively through linearizations of their local objective functions. By employing DCS, agents can still find an ε-solution in O(1/ε) (resp., O(1/√ε)) communication rounds for general convex functions (resp., strongly convex functions), while maintaining the O(1/ε2) (resp., O(1/ε)) bound on the total number of intra-node subgradient evaluations. We also present a stochastic counterpart for these algorithms, denoted by SDCS, for solving stochastic optimization problems whose objective function cannot be evaluated exactly. In comparison with existing results for decentralized nonsmooth and stochastic optimization, we can reduce the total number of inter-node communication rounds by orders of magnitude while still maintaining the optimal complexity bounds on intra-node stochastic subgradient evaluations. The bounds on the subgradient evaluations are actually comparable to those required for centralized nonsmooth and stochastic optimization.