mlsanityData to 14 Oct 2026

Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization

arXiv 2109.15292 ↗First posted 30 Sep 2021math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

33 of 52 references.

References · 33

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  4. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  5. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  6. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  7. 2015Asynchronous Parallel Stochastic Gradient for Nonconvex Optimizationcited by 116
  8. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 95
  9. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  10. 2015Perturbed Iterate Analysis for Asynchronous Stochastic Optimizationcited by 67
  11. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  12. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
21 more
  1. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 37
  2. 2016Barzilai-Borwein Step Size for Stochastic Gradient Descentcited by 33
  3. 2015Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithmscited by 31
  4. 2018Improved asynchronous parallel optimization analysis for stochastic incremental methodscited by 30
  5. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 24
  6. 2020Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimizationcited by 19
  7. 2016ASAGA: Asynchronous Parallel SAGAcited by 18
  8. 2021Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updatescited by 17
  9. 2021AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methodscited by 15
  10. 2017A Robust Accelerated Optimization Algorithm for Strongly Convex Functionscited by 14
  11. 2013Semi-Stochastic Gradient Descent Methodscited by 13
  12. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
  13. 2018A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Ratescited by 11
  14. 2018Direct Acceleration of SAGA using Sampled Negative Momentumcited by 9
  15. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  16. 2017DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimizationcited by 7
  17. 2020Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Ratescited by 4
  18. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4
  19. 2017Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimizationcited by 3
  20. 2018Accelerating Asynchronous Algorithms for Convex Optimization by Momentum Compensationcited by 2
  21. 2018Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimizationcited by 1

Built on by

Not cited yet.