On the Convergence of Asynchronous Parallel Iteration with Arbitrary Delays

Zhimin Peng, Yangyang Xu, Ming Yan, Wotao Yin

Published in Journal of the Operations Research Society of China


Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to the need for solving problems with very large-scale data and a large number of decision variables. Because of asynchrony, these algorithms generate their iterates with outdated information, and the age of the outdated information, which we call delay, is the number of times the information has been updated since its creation. Almost all recent works prove convergence under the assumption of a finite maximum delay and set their stepsize parameters accordingly. However, the maximum delay is practically unknown.

This paper presents convergence analysis of a randomized async-parallel method from a probabilistic viewpoint, and it permits arbitrarily large delays. An explicit formula of stepsize that guarantees convergence is given depending on delays’ statistics.

With p+1 identical processors, we empirically measured that delays closely follow the Poisson distribution with parameter p, matching our theoretical model, and thus the stepsize can be set accordingly. Simulations on both convex and nonconvex optimization problems demonstrate the validness of our analysis and also show that the existing maximum-delay induced stepsize is too conservative, causing unnecessary convergence slowdown.


Z. Peng, Y. Xu, M. Yan, and W. Yin, On the convergence of asynchronous parallel iteration with arbitrary delays, Journal of the Operations Research Society of China 7(1), 5-42, 2019.

« Back