Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees

We introduce novel convergence results for asynchronous iterations that\nappear in the analysis of parallel and distributed optimization algorithms. The\nresults are simple to apply and give explicit estimates for how the degree of\nasynchrony impacts the convergence rates of the iterates. Our results shorten,\nstreamline and strengthen existing convergence proofs for several asynchronous\noptimization methods and allow us to establish convergence guarantees for\npopular algorithms that were thus far lacking a complete theoretical\nunderstanding. Specifically, we use our results to derive better iteration\ncomplexity bounds for proximal incremental aggregated gradient methods, to\nobtain tighter guarantees depending on the average rather than maximum delay\nfor the asynchronous stochastic gradient descent method, to provide less\nconservative analyses of the speedup conditions for asynchronous\nblock-coordinate implementations of Krasnoselskii-Mann iterations, and to\nquantify the convergence rates for totally asynchronous iterations under\nvarious assumptions on communication delays and update rates.\n