mlsanityData to 7 Oct 2026

Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD

arXiv 2409.17499 ↗First posted 26 Sep 2024cs.LG math.OC stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

Distributed learning is essential to train machine learning algorithms across heterogeneous agents while maintaining data privacy. We conduct an asymptotic analysis of Unified Distributed SGD (UD-SGD), exploring a variety of communication patterns, including decentralized SGD and local SGD within Federated Learning (FL), as well as the increasing communication interval in the FL setting. In this study, we assess how different sampling strategies, such as i.i.d. sampling, shuffling, and Markovian sampling, affect the convergence speed of UD-SGD by considering the impact of agent dynamics on the limiting covariance matrix as described in the Central Limit Theorem (CLT). Our findings not only support existing theories on linear speedup and asymptotic network independence, but also theoretically and empirically show how efficient sampling strategies employed by individual agents contribute to overall convergence in UD-SGD. Simulations reveal that a few agents using highly efficient sampling can achieve or surpass the performance of the majority employing moderately improved strategies, providing new insights beyond traditional analyses focusing on the worst-performing agent.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 41 of its 78 references that are in the map. First posted on arXiv 26 Sep 2024.

Builds on

41 of 78 references.

References · 41

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  3. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  4. 2018Federated Learning with Non-IID Datacited by 1,099
  5. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
  6. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  7. 2020An Efficient Framework for Clustered Federated Learningcited by 505
  8. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  9. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 286
  10. 2014The Loss Surfaces of Multilayer Networkscited by 278
  11. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  12. 2020Optimal Client Sampling for Federated Learningcited by 123
29 more
  1. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  2. 2018On Markov Chain Gradient Descentcited by 63
  3. 2019How Good is SGD with Random Shuffling?cited by 63
  4. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  5. 2022A Unified Analysis of Federated Learning with Arbitrary Client Participationcited by 45
  6. 2020Multi-Stage Hybrid Federated Learning over Large-Scale D2D-Enabled Fog Networkscited by 42
  7. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
  8. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  9. 2020Decentralized gradient methods: does topology matter?cited by 35
  10. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  11. 2022Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Datacited by 31
  12. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 29
  13. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
  14. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19
  15. 2022Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Datacited by 18
  16. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 18
  17. 2022A principled framework for the design and analysis of token algorithmscited by 17
  18. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  19. 2023On the Convergence of Decentralized Federated Learning Under Imperfect Information Sharingcited by 16
  20. 2022Adaptive Configuration for Heterogeneous Participants in Decentralized Federated Learningcited by 11
  21. 2020On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Biascited by 10
  22. 2020Finite-Time Convergence Rates of Decentralized Stochastic Approximation with Applications in Multi-Agent and Multi-Task Learningcited by 10
  23. 2019Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learningcited by 9
  24. 2021A General Theory for Client Sampling in Federated Learningcited by 8
  25. 2022Convergence of Stochastic Approximation via Martingale and Converse Lyapunov Methodscited by 8
  26. 2023Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chainscited by 8
  27. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  28. 2020Asymptotic Network Independence and Step-Size for A Distributed Subgradient Methodcited by 3
  29. 2024Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walkscited by 2

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Federated Learning of Quantile Inference under Local Differential Privacycited by 2
  2. 2025Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphscited by 1