# Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 13 Jul 2026.

## Builds on (most cited first, 22 of 22)

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (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)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Federated Learning with Cooperating Devices: A Consensus Approach for Massive IoT Networks](https://mlsanity.com/paper/1912.13163/) (2019)
- [Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2101.12704/) (2021)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!](https://mlsanity.com/paper/2011.01697/) (2020)
- [An Exact Quantized Decentralized Gradient Descent Algorithm](https://mlsanity.com/paper/1806.11536/) (2018)
- [Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs](https://mlsanity.com/paper/1406.2075/) (2014)
- [Balancing Communication and Computation in Distributed Optimization](https://mlsanity.com/paper/1709.02999/) (2017)
- [On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication](https://mlsanity.com/paper/1902.11163/) (2019)
- [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021)
- [Asynchronous Decentralized Learning over Unreliable Wireless Networks](https://mlsanity.com/paper/2202.00955/) (2022)
- [Decentralized optimization over noisy, rate-constrained networks: Achieving consensus by communicating differences](https://mlsanity.com/paper/2010.11292/) (2020)
- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [A Compressed Gradient Tracking Method for Decentralized Optimization with Linear Convergence](https://mlsanity.com/paper/2205.12623/) (2022)
- [Non-Coherent Over-the-Air Decentralized Gradient Descent](https://mlsanity.com/paper/2211.10777/) (2022)
- [On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps](https://mlsanity.com/paper/2006.01665/) (2020)
- [Convergence results of a nested decentralized gradient method for non-strongly convex problems](https://mlsanity.com/paper/2108.02129/) (2021)

## Abstract (arXiv)

Decentralized gradient descent (DGD) is widely used for solving distributed optimization problems over networks of agents. While its convergence properties are well understood, less is known about the communication and computation resources required to attain a prescribed accuracy. In this paper, we study DGD from a resource-aware perspective and characterize the communication-computation budget required to attain a target error level. We develop a bottleneck-centric framework in which different factors dominate the optimization dynamics at different error scales. Specifically, we identify operating regimes governed by initialization, objective heterogeneity and network connectivity, gradient noise, and communication noise. To capture these effects, we introduce two fundamental quantities: the gradient-Diversity-to-Network-connectivity Ratio (DNR) and the Gradient-to-Communication-noise Ratio (GCR). We show that these quantities determine the sequence of bottlenecks encountered during optimization and the corresponding budget-optimal operating strategy. Using a multi-stage analysis, we derive optimal stepsize selections and explicit budget-complexity bounds that quantify the budget resources required to attain a prescribed accuracy. The resulting expressions reveal how the overall budget decomposes into contributions associated with successive bottlenecks and provide insight into the fundamental tradeoffs among objective heterogeneity, network connectivity, gradient noise, and communication noise.