Search papers, labs, and topics across Lattice.
This paper investigates decentralized gradient descent (DGD) by analyzing the communication and computation resources necessary to achieve specific accuracy levels in distributed optimization. The authors introduce a bottleneck-centric framework that identifies how various factors, such as initialization, objective heterogeneity, and noise, influence optimization dynamics across different error scales. Key findings include the introduction of two critical ratios, DNR and GCR, which dictate the bottlenecks encountered and inform optimal strategies for resource allocation during the optimization process.
The resource requirements for decentralized gradient descent reveal surprising trade-offs that could redefine how we approach distributed optimization in complex networks.
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.
