On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays

Understand

Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables.

• Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we call delay, is the number of times it 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.