Stability and Convergence of Distributed Stochastic Approximations with large Unbounded Stochastic Information Delays
This work addresses stability issues in distributed optimization and learning systems with delays, which is incremental but important for applications like distributed gradient-based optimization.
The authors generalized the Borkar-Meyn stability Theorem to distributed stochastic approximations with unbounded stochastic information delays, showing that delays with arbitrary moment bounds do not compromise stability under a suitable stepsize. They introduced Age of Information Processes to model delays and developed a new Gronwall-type inequality for analysis.
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.