Practical Network Conditions for the Convergence of Distributed Optimization

The decentralized nature of multi-agent learning often requires continuous information exchange over a (wireless) communication network, in order to accomplish common global objectives. Uncertainty and delay in communication induce large Age of Information (AoI) for data available at the agents, possibly affecting algorithm performance. In order to understand this, one needs communication models that are representative of practical wireless networks. In this paper, we present a representative model based on the Signal-to-Interference-plus-Noise Ratio (SINR) between pairs of agents. Further, we present a novel medium access control (MAC) protocol that is sensitive to local AoI. Our SINR model facilitates the representation of practical dependency effects like shadowing, fading, interference and external noise. The model is driven by an underlying geometrically ergodic Markov chain, which can represent agent mobility. Our MAC protocol enables that the aforementioned dependency effects decay over time. With this dependency decay, we then control the asymptotic growth of the AoI, to facilitate the convergence of distributed algorithms. Finally, we illustrate our ideas by analyzing the distributed stochastic gradient descent scheme that uses delayed communicated data. Copyright (C) 2022 The Authors.