# Stability and Convergence of Distributed Stochastic Approximations with large Unbounded Stochastic Information Delays

arXiv: https://arxiv.org/abs/2305.07091 · HTML: https://mlsanity.com/paper/2305.07091/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 11 May 2023.

## Builds on (most cited first, 14 of 14)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [The Marginal Value of Adaptive Gradient Methods in Machine Learning](https://mlsanity.com/paper/1705.08292/) (2017)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Convergence and Dynamical Behavior of the ADAM Algorithm for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1810.02263/) (2018)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusions](https://mlsanity.com/paper/1502.01953/) (2015)
- [Online Algorithms for Estimating Change Rates of Web Pages](https://mlsanity.com/paper/2009.08142/) (2020)
- [Multi Timescale Stochastic Approximation: Stability and Convergence](https://mlsanity.com/paper/2112.03515/) (2021)
- [Distributed stochastic optimization with large delays](https://mlsanity.com/paper/2107.02919/) (2021)
- [Gradient Temporal Difference with Momentum: Stability and Convergence](https://mlsanity.com/paper/2111.11004/) (2021)

## Abstract (arXiv)

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.