  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.
  This paper presents convergence analysis of an async-parallel method from a
probabilistic viewpoint, and it allows for large unbounded 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, often slowing down the convergence of the algorithm.
