# Distributed gradient-based optimization in the presence of dependent aperiodic communication

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 27 Jan 2022.

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

- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs](https://mlsanity.com/paper/1809.01106/) (2018)
- [ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks](https://mlsanity.com/paper/2102.09234/) (2021)
- [Modeling the Evolution of Line-of-Sight Blockage for V2V Channels](https://mlsanity.com/paper/1607.04420/) (2016)
- [Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization Over Random Networks](https://mlsanity.com/paper/1607.06623/) (2016)
- [Decentralized Stochastic Control of Distributed Energy Resources](https://mlsanity.com/paper/1611.00093/) (2016)
- [Optimization over time-varying networks with unbounded delays](https://mlsanity.com/paper/1912.07055/) (2019)

## Abstract (arXiv)

Iterative distributed optimization algorithms involve multiple agents that communicate with each other, over time, in order to minimize/maximize a global objective. In the presence of unreliable communication networks, the Age-of-Information (AoI), which measures the freshness of data received, may be large and hence hinder algorithmic convergence. In this paper, we study the convergence of general distributed gradient-based optimization algorithms in the presence of communication that neither happens periodically nor at stochastically independent points in time. We show that convergence is guaranteed provided the random variables associated with the AoI processes are stochastically dominated by a random variable with finite first moment. This improves on previous requirements of boundedness of more than the first moment. We then introduce stochastically strongly connected (SSC) networks, a new stochastic form of strong connectedness for time-varying networks. We show: If for any p ≥0 the processes that describe the success of communication between agents in a SSC network are α-mixing with np-1α(n) summable, then the associated AoI processes are stochastically dominated by a random variable with finite p-th moment. In combination with our first contribution, this implies that distributed stochastic gradient descend converges in the presence of AoI, if α(n) is summable.