# Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 52 references that are in the map.
- First posted on arXiv 30 Sep 2021.

## Builds on (most cited first, 30 of 33)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms](https://mlsanity.com/paper/1506.06438/) (2015)
- [Improved asynchronous parallel optimization analysis for stochastic incremental methods](https://mlsanity.com/paper/1801.03749/) (2018)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [ASAGA: Asynchronous Parallel SAGA](https://mlsanity.com/paper/1606.04809/) (2016)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [A Robust Accelerated Optimization Algorithm for Strongly Convex Functions](https://mlsanity.com/paper/1710.04753/) (2017)
- [Semi-Stochastic Gradient Descent Methods](https://mlsanity.com/paper/1312.1666/) (2013)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates](https://mlsanity.com/paper/1806.11027/) (2018)
- [Direct Acceleration of SAGA using Sampled Negative Momentum](https://mlsanity.com/paper/1806.11048/) (2018)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization](https://mlsanity.com/paper/1710.05080/) (2017)
- [Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates](https://mlsanity.com/paper/2005.12061/) (2020)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)

## Abstract (arXiv)

We show that stochastic acceleration can be achieved under the perturbed iterate framework (Mania et al., 2017) in asynchronous lock-free optimization, which leads to the optimal incremental gradient complexity for finite-sum objectives. We prove that our new accelerated method requires the same linear speed-up condition as the existing non-accelerated methods. Our core algorithmic discovery is a new accelerated SVRG variant with sparse updates. Empirical results are presented to verify our theoretical findings.