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

A. Redder, A. Ramaswamy, H. Karl, ArXiv:2201.11343 (2022).

Download
No fulltext has been uploaded.
Preprint
Author
Redder, Adrian; Ramaswamy, Arunselvan; Karl, Holger
Abstract
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 \ge0$ the processes that describe the success of communication between agents in a SSC network are $\alpha$-mixing with $n^{p-1}\alpha(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 $\alpha(n)$ is summable.
Publishing Year
Journal Title
arXiv:2201.11343
LibreCat-ID

Cite this

Redder A, Ramaswamy A, Karl H. Distributed gradient-based optimization in the presence of dependent  aperiodic communication. arXiv:220111343. Published online 2022.
Redder, A., Ramaswamy, A., & Karl, H. (2022). Distributed gradient-based optimization in the presence of dependent  aperiodic communication. In arXiv:2201.11343.
@article{Redder_Ramaswamy_Karl_2022, title={Distributed gradient-based optimization in the presence of dependent  aperiodic communication}, journal={arXiv:2201.11343}, author={Redder, Adrian and Ramaswamy, Arunselvan and Karl, Holger}, year={2022} }
Redder, Adrian, Arunselvan Ramaswamy, and Holger Karl. “Distributed Gradient-Based Optimization in the Presence of Dependent  Aperiodic Communication.” ArXiv:2201.11343, 2022.
A. Redder, A. Ramaswamy, and H. Karl, “Distributed gradient-based optimization in the presence of dependent  aperiodic communication,” arXiv:2201.11343. 2022.
Redder, Adrian, et al. “Distributed Gradient-Based Optimization in the Presence of Dependent  Aperiodic Communication.” ArXiv:2201.11343, 2022.

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 2201.11343

Search this title in

Google Scholar