# Perturbed Iterate Analysis for Asynchronous Stochastic Optimization

arXiv: https://arxiv.org/abs/1507.06970 · HTML: https://mlsanity.com/paper/1507.06970/

## Key facts

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

## Built on by (most cited first, 30 of 67)

- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [AdaptSFL: Adaptive Split Federated Learning in Resource-constrained Edge Networks](https://mlsanity.com/paper/2403.13101/) (2024)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [Pufferfish: Communication-efficient Models At No Extra Cost](https://mlsanity.com/paper/2103.03936/) (2021)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Hierarchical Split Federated Learning: Convergence Analysis and System Optimization](https://mlsanity.com/paper/2412.07197/) (2024)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Resource-Efficient Federated Learning](https://mlsanity.com/paper/2111.01108/) (2021)
- [Preserved central model for faster bidirectional compression in distributed settings](https://mlsanity.com/paper/2102.12528/) (2021)
- [AsyncFedED: Asynchronous Federated Learning with Euclidean Distance based Adaptive Weight Aggregation](https://mlsanity.com/paper/2205.13797/) (2022)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise](https://mlsanity.com/paper/2204.02593/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [HASFL: Heterogeneity-aware Split Federated Learning over Edge Computing Systems](https://mlsanity.com/paper/2506.08426/) (2025)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [FedFa: A Fully Asynchronous Training Paradigm for Federated Learning](https://mlsanity.com/paper/2404.11015/) (2024)
- [Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimization](https://mlsanity.com/paper/2311.00465/) (2023)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Asynchronous Federated Learning with Bidirectional Quantized Communications and Buffered Aggregation](https://mlsanity.com/paper/2308.00263/) (2023)
- [FADAS: Towards Federated Adaptive Asynchronous Optimization](https://mlsanity.com/paper/2407.18365/) (2024)
- [Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneity](https://mlsanity.com/paper/2305.18285/) (2023)
- [Federated Learning over Noisy Channels: Convergence Analysis and Design Examples](https://mlsanity.com/paper/2101.02198/) (2021)
- [Pisces: Efficient Federated Learning via Guided Asynchronous Training](https://mlsanity.com/paper/2206.09264/) (2022)
- [Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopes](https://mlsanity.com/paper/2301.06806/) (2023)
- [On Convergence of Incremental Gradient for Non-Convex Smooth Functions](https://mlsanity.com/paper/2305.19259/) (2023)

## 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.