Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information
Abstract
Algorithms in multi-agent systems such as federated learning, mobile robotic swarming, and consensus control can be designed and analyzed as distributed stochastic approximation algorithms. Such algorithms involve information exchanges between agents for various computations. The freshness of the information can be quantified using the Age of Information (AoI) metric. Consider robotic teams operating in highly obstructed geographical settings, such as subterranean or dense urban environments. Because of spatial disconnections, AoI has empirically been observed to be heavy-tailed with unbounded moments. However, most analyses assume AoI with bounded moments, creating a gap between theory and practice. To the best of our knowledge, ours is the first analysis under general heavy-tailed AoI with potentially infinite mean. We study the stability (almost sure boundedness of the distributed iterates) and convergence of multi-agent systems that are strictly dissipative in the scaling limit (system at ``infinity''). Examples include most gradient-based and consensus algorithms under the Robbins-Monro step-size regime.
Related
- Bitcoin UTXO Values Are Heavy-Tailed but not Power-Law Distributed: A Clauset-Shalizi-Newman Test across Eight Snapshots
- Accelerated Stochastic Method under (H0,H1)-Smoothness and Heavy-Tailed Noise
- TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise
- Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
- The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization
BibTeX
@misc{redder2026distributed,
title = {{Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information}},
author = {Adrian Redder and Arunselvan Ramaswamy and Holger Karl},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27499},
eprint = {2609.27499},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27499},
}
RIS
TY - UNPB
TI - Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information
AU - Adrian Redder
AU - Arunselvan Ramaswamy
AU - Holger Karl
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27499
UR - https://arxiv.org/abs/2609.27499
AB - Algorithms in multi-agent systems such as federated learning, mobile robotic swarming, and consensus control can be designed and analyzed as distributed stochastic approximation algorithms. Such algorithms involve information exchanges between agents for various computations. The freshness of the information can be quantified using the Age of Information (AoI) metric. Consider robotic teams operating in highly obstructed geographical settings, such as subterranean or dense urban environments. Because of spatial disconnections, AoI has empirically been observed to be heavy-tailed with unbounded moments. However, most analyses assume AoI with bounded moments, creating a gap between theory and practice. To the best of our knowledge, ours is the first analysis under general heavy-tailed AoI with potentially infinite mean. We study the stability (almost sure boundedness of the distributed iterates) and convergence of multi-agent systems that are strictly dissipative in the scaling limit (system at ``infinity''). Examples include most gradient-based and consensus algorithms under the Robbins-Monro step-size regime.
ER -