Stability and Convergence of Distributed Stochastic Approximations with
  large Unbounded Stochastic Information Delays
Adrian Redder Arunselvan Ramaswamy Holger Karl
We generalize the Borkar-Meyn stability Theorem (BMT) to distributed
stochastic approximations (SAs) with information delays that possess an
arbitrary moment bound. To model the delays, we introduce Age of Information
Processes (AoIPs): stochastic processes on the non-negative integers with a
unit growth property. We show that AoIPs with an arbitrary moment bound cannot
exceed any fraction of time infinitely often. In combination with a suitably
chosen stepsize, this property turns out to be sufficient for the stability of
distributed SAs. Compared to the BMT, our analysis requires crucial
modifications and a new line of argument to handle the SA errors caused by AoI.
In our analysis, we show that these SA errors satisfy a recursive inequality.
To evaluate this recursion, we propose a new Gronwall-type inequality for
time-varying lower limits of summations. As applications to our distributed
BMT, we discuss distributed gradient-based optimization and a new approach to
analyzing SAs with momentum.