# Improving the Transient Times for Distributed Stochastic Gradient Methods arXiv: https://arxiv.org/abs/2105.04851 · HTML: https://mlsanity.com/paper/2105.04851/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 31 of its 55 references that are in the map. - First posted on arXiv 11 May 2021. ## Builds on (most cited first, 30 of 31) - [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) - [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018) - [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016) - [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018) - [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017) - [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016) - [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018) - [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020) - [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017) - [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018) - [On the Influence of Bias-Correction on Distributed Stochastic Optimization](https://mlsanity.com/paper/1903.10956/) (2019) - [Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs](https://mlsanity.com/paper/1406.2075/) (2014) - [Fast Convergence Rates for Distributed Non-Bayesian Learning](https://mlsanity.com/paper/1508.05161/) (2015) - [On the Learning Behavior of Adaptive Networks - Part I: Transient Analysis](https://mlsanity.com/paper/1312.7581/) (2013) - [Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions](https://mlsanity.com/paper/1811.03982/) (2018) - [Convergence rates for distributed stochastic optimization over random networks](https://mlsanity.com/paper/1803.07836/) (2018) - [Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis](https://mlsanity.com/paper/1702.05142/) (2017) - [S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs](https://mlsanity.com/paper/2005.07785/) (2020) - [Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication](https://mlsanity.com/paper/1401.4432/) (2014) - [On the Learning Behavior of Adaptive Networks - Part II: Performance Analysis](https://mlsanity.com/paper/1312.7580/) (2013) - [On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression](https://mlsanity.com/paper/1606.03000/) (2016) - [Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning](https://mlsanity.com/paper/1906.12345/) (2019) - [Distributed Learning Algorithms for Spectrum Sharing in Spatial Random Access Wireless Networks](https://mlsanity.com/paper/1507.05664/) (2015) - [Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization](https://mlsanity.com/paper/1610.04702/) (2016) - [Excess-Risk of Distributed Stochastic Learners](https://mlsanity.com/paper/1302.1157/) (2013) - [Supervised Learning Under Distributed Features](https://mlsanity.com/paper/1805.11384/) (2018) - [Success and Failure of Adaptation-Diffusion Algorithms for Consensus in Multi-Agent Networks](https://mlsanity.com/paper/1410.6956/) (2014) - [Swarming for Faster Convergence in Stochastic Optimization](https://mlsanity.com/paper/1806.04207/) (2018) ## Built on by (most cited first, 13 of 13) - [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021) - [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022) - [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021) - [Beyond spectral gap: The role of the topology in decentralized learning](https://mlsanity.com/paper/2206.03093/) (2022) - [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021) - [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023) - [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021) - [Distributed Stochastic Optimization under a General Variance Condition](https://mlsanity.com/paper/2301.12677/) (2023) - [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023) - [Locally Differentially Private Gradient Tracking for Distributed Online Learning over Directed Graphs](https://mlsanity.com/paper/2310.16105/) (2023) - [Adjacent Leader Decentralized Stochastic Gradient Descent](https://mlsanity.com/paper/2405.11389/) (2024) - [Distributed optimization: designed for federated learning](https://mlsanity.com/paper/2508.08606/) (2025) - [Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization](https://mlsanity.com/paper/2606.07496/) (2026) ## Abstract (arXiv) We consider the distributed optimization problem where n agents each possessing a local cost function, collaboratively minimize the average of the n cost functions over a connected network. Assuming stochastic gradient information is available, we study a distributed stochastic gradient algorithm, called exact diffusion with adaptive stepsizes (EDAS) adapted from the Exact Diffusion method and NIDS and perform a non-asymptotic convergence analysis. We not only show that EDAS asymptotically achieves the same network independent convergence rate as centralized stochastic gradient descent (SGD) for minimizing strongly convex and smooth objective functions, but also characterize the transient time needed for the algorithm to approach the asymptotic convergence rate, which behaves as KT=Oleft(fracn1-λ2right), where 1-λ2 stands for the spectral gap of the mixing matrix. To the best of our knowledge, EDAS achieves the shortest transient time when the average of the n cost functions is strongly convex and each cost function is smooth. Numerical simulations further corroborate and strengthen the obtained theoretical results.