Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization
arXiv:2109.15292
Abstract
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.
arXiv comment21 pages, 22 figures
References in corpus (11)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Barzilai-Borwein Step Size for Stochastic Gradient Descent
- Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- Direct Acceleration of SAGA using Sampled Negative Momentum
- Accelerating Asynchronous Algorithms for Convex Optimization by Momentum Compensation
- ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
- Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization
- AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
- Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums