Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
This work provides improved theoretical guarantees for asynchronous optimization algorithms, which is important for researchers and practitioners in distributed computing and machine learning, though it appears to be an incremental advancement in analysis rather than a new algorithmic paradigm.
The paper tackles the problem of analyzing convergence rates for asynchronous iterations in parallel and distributed optimization algorithms, introducing new theoretical results that provide explicit estimates of how asynchrony affects convergence and strengthen existing proofs for several methods.
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.