# Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology arXiv: https://arxiv.org/abs/2207.03730 ยท HTML: https://mlsanity.com/paper/2207.03730/ ## Key facts - Cited by 10 papers in the map (data through 14 Oct 2026). - Builds on 30 of its 48 references that are in the map. - First posted on arXiv 8 Jul 2022. ## Builds on (most cited first, 30 of 30) - [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016) - [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019) - [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018) - [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017) - [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014) - [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020) - [The Non-IID Data Quagmire of Decentralized Machine Learning](https://mlsanity.com/paper/1910.00189/) (2019) - [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019) - [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017) - [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013) - [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) - [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017) - [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015) - [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016) - [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018) - [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020) - [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019) - [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017) - [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018) - [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015) - [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019) - [Accelerating Gossip SGD with Periodic Global Averaging](https://mlsanity.com/paper/2105.09080/) (2021) - [An Optimal Algorithm for Decentralized Finite Sum Optimization](https://mlsanity.com/paper/2005.10675/) (2020) - [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021) - [DSA: Decentralized Double Stochastic Averaging Gradient Algorithm](https://mlsanity.com/paper/1506.04216/) (2015) - [L-SVRG and L-Katyusha with Arbitrary Sampling](https://mlsanity.com/paper/1906.01481/) (2019) - [A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints](https://mlsanity.com/paper/1706.08141/) (2017) - [Distributed stochastic gradient tracking algorithm with variance reduction for non-convex optimization](https://mlsanity.com/paper/2106.14479/) (2021) - [Distributed SAGA: Maintaining linear convergence rate with limited communication](https://mlsanity.com/paper/1705.10405/) (2017) ## Built on by (most cited first, 10 of 10) - [NeurAR: Neural Uncertainty for Autonomous 3D Reconstruction with Implicit Neural Representations](https://mlsanity.com/paper/2207.10985/) (2022) - [Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compression](https://mlsanity.com/paper/2305.09896/) (2023) - [Distributed Stochastic Optimization under a General Variance Condition](https://mlsanity.com/paper/2301.12677/) (2023) - [On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approach](https://mlsanity.com/paper/2306.07159/) (2023) - [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023) - [Reducing Training Time in Cross-Silo Federated Learning using Multigraph Topology](https://mlsanity.com/paper/2207.09657/) (2022) - [Structured Cooperative Learning with Graphical Model Priors](https://mlsanity.com/paper/2306.09595/) (2023) - [Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2406.02939/) (2024) - [Unified analysis of SGD-type methods](https://mlsanity.com/paper/2303.16502/) (2023) - [Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking](https://mlsanity.com/paper/2509.18129/) (2025) ## Abstract (arXiv) We develop a general framework unifying several gradient-based stochastic optimization methods for empirical risk minimization problems both in centralized and distributed scenarios. The framework hinges on the introduction of an augmented graph consisting of nodes modeling the samples and edges modeling both the inter-device communication and intra-device stochastic gradient computation. By designing properly the topology of the augmented graph, we are able to recover as special cases the renowned Local-SGD and DSGD algorithms, and provide a unified perspective for variance-reduction (VR) and gradient-tracking (GT) methods such as SAGA, Local-SVRG and GT-SAGA. We also provide a unified convergence analysis for smooth and (strongly) convex objectives relying on a proper structured Lyapunov function, and the obtained rate can recover the best known results for many existing algorithms. The rate results further reveal that VR and GT methods can effectively eliminate data heterogeneity within and across devices, respectively, enabling the exact convergence of the algorithm to the optimal solution. Numerical experiments confirm the findings in this paper.