Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
arXiv:2109.04522
Abstract
We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. The results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates. Our results shorten, streamline and strengthen existing convergence proofs for several asynchronous optimization methods and allow us to establish convergence guarantees for popular algorithms that were thus far lacking a complete theoretical understanding. Specifically, we use our results to derive better iteration complexity bounds for proximal incremental aggregated gradient methods, to obtain tighter guarantees depending on the average rather than maximum delay for the asynchronous stochastic gradient descent method, to provide less conservative analyses of the speedup conditions for asynchronous block-coordinate implementations of Krasnoselskii-Mann iterations, and to quantify the convergence rates for totally asynchronous iterations under various assumptions on communication delays and update rates.
arXiv comment62 pages, 1 Figure
References in corpus (13)
- Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Optimization with First-Order Surrogate Functions
- SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- Asynchronous Coordinate Descent under More Realistic Assumptions
- CYCLADES: Conflict-free Asynchronous Machine Learning
- Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server
- A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
- More Iterations per Second, Same Quality -- Why Asynchronous Algorithms may Drastically Outperform Traditional Ones
- General Proximal Incremental Aggregated Gradient Algorithms: Better and Novel Results under General Scheme
- AsyncQVI: Asynchronous-Parallel Q-Value Iteration for Discounted Markov Decision Processes with Near-Optimal Sample Complexity