mlsanityData to 7 Oct 2026

Perturbed Iterate Analysis for Asynchronous Stochastic Optimization

arXiv 1507.06970 ↗First posted 24 Jul 2015stat.ML cs.DC cs.DScited by 67

Not on the map. Why?

Abstract (arXiv)

We introduce and analyze stochastic optimization methods where the input to each gradient update is perturbed by bounded noise. We show that this framework forms the basis of a unified approach to analyze asynchronous implementations of stochastic optimization algorithms.In this framework, asynchronous stochastic optimization algorithms can be thought of as serial methods operating on noisy inputs. Using our perturbed iterate framework, we provide new analyses of the Hogwild! algorithm and asynchronous stochastic coordinate descent, that are simpler than earlier analyses, remove many assumptions of previous models, and in some cases yield improved upper bounds on the convergence rates. We proceed to apply our framework to develop and analyze KroMagnon: a novel, parallel, sparse stochastic variance-reduced gradient (SVRG) algorithm. We demonstrate experimentally on a 16-core machine that the sparse and parallel version of SVRG is in some cases more than four orders of magnitude faster than the standard SVRG algorithm.

Key facts. Cited by 67 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 18; 2022: 10; 2023: 15; 2024: 11; 2025: 6; 2026: 7.

67 papers.

Sort:

  1. 2021Federated Learning with Buffered Asynchronous Aggregationcited by 188
  2. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  3. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 76
  4. 2024AdaptSFL: Adaptive Split Federated Learning in Resource-constrained Edge Networkscited by 64
  5. 2021Pufferfish: Communication-efficient Models At No Extra Costcited by 61
  6. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 61
  7. 2024Hierarchical Split Federated Learning: Convergence Analysis and System Optimizationcited by 38
  8. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  9. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  10. 2021Resource-Efficient Federated Learningcited by 26
  11. 2021Preserved central model for faster bidirectional compression in distributed settingscited by 21
  12. 2022AsyncFedED: Asynchronous Federated Learning with Euclidean Distance based Adaptive Weight Aggregationcited by 19
38 more
  1. 2023Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacycited by 18
  2. 2021Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guaranteescited by 17
  3. 2021Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updatescited by 16
  4. 2022Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noisecited by 16
  5. 2023AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithmscited by 16
  6. 2025HASFL: Heterogeneity-aware Split Federated Learning over Edge Computing Systemscited by 15
  7. 2021Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimizationcited by 14
  8. 2023Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learningcited by 12
  9. 2024FedFa: A Fully Asynchronous Training Paradigm for Federated Learningcited by 12
  10. 2023Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimizationcited by 11
  11. 2023Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learningcited by 10
  12. 2023Asynchronous Federated Learning with Bidirectional Quantized Communications and Buffered Aggregationcited by 10
  13. 2024FADAS: Towards Federated Adaptive Asynchronous Optimizationcited by 10
  14. 2021Federated Learning over Noisy Channels: Convergence Analysis and Design Examplescited by 8
  15. 2022Pisces: Efficient Federated Learning via Guided Asynchronous Trainingcited by 8
  16. 2023Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopescited by 8
  17. 2023Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneitycited by 8
  18. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  19. 2023Locally Adaptive Federated Learningcited by 7
  20. 2024MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Timescited by 5
  21. 2025Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneitycited by 5
  22. 2022On Federated Learning with Energy Harvesting Clientscited by 4
  23. 2022Distributed Methods with Absolute Compression and Error Compensationcited by 4
  24. 2023Post Quantum Secure Blockchain-based Federated Learning for Mobile Edge Computingcited by 4
  25. 2024Distributed Learning based on 1-Bit Gradient Coding in the Presence of Stragglerscited by 4
  26. 2021Asynchronous speedup in decentralized optimizationcited by 3
  27. 2021Distributed stochastic optimization with large delayscited by 3
  28. 2021Decentralized Multi-Task Stochastic Optimization With Compressed Communicationscited by 3
  29. 2024FedAST: Federated Asynchronous Simultaneous Trainingcited by 3
  30. 2021Statistical Estimation and Inference via Local SGD in Federated Learningcited by 2
  31. 2023Considerations on the Theory of Training Models with Differential Privacycited by 2
  32. 2024Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delayscited by 2
  33. 2026Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneitycited by 2
  34. 2021Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossipingcited by 1
  35. 2021AET-SGD: Asynchronous Event-triggered Stochastic Gradient Descentcited by 1
  36. 2022Distributed Dynamic Safe Screening Algorithms for Sparse Regularizationcited by 1
  37. 2023Differentially Private Wireless Federated Learning Using Orthogonal Sequencescited by 1
  38. 2024Learning from straggler clients in federated learningcited by 1

50 most cited of 67 All 67 (JSON)