Optimization Over Time-Varying Networks and Unbounded Information Delays

• 成果类型: Article
• 署名作者: Ramaswamy, Arunselvan; Redder, Adrian; Quevedo, Daniel E.
• 署名单位: University of Paderborn; University of Paderborn; Queensland University of Technology (QUT)
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3108492
• 发表日期: 2022
• 页码: 4131-4137
• 关键词: Optimization; Network topology; clocks; wireless networks; DELAYS; TOPOLOGY; Stochastic processes; Age-of-information (AoI); approximate distributed gradient methods; distributed optimization; stochastic approximation algorithms; time-varying communication network topologies; unbounded stochastic communication delays

摘要

Solving optimization problems in multiagent systems involves information exchange between agents. The obtained solutions should be robust to information delays and errors that arise from an unreliable wireless network, which typically connects the multiagent system. In today's large-scale dynamic Internet of Things style multiagent scenarios, the network topology changes and evolves over time. In this article, we present a simple distributed gradient-based optimization framework and an associated algorithm. Convergence to a minimum of a given objective is shown under mild conditions on the network topology and objective. A key feature of our approach is that we merely assume that the messages sent reach the intended receiver, possibly delayed, with some positive probability. To the best of authors' knowledge, ours is the first analysis under such weak general network conditions. We also discuss in detail the verifiability of the assumptions involved. This article also makes a technical contribution in terms of the allowed class of objective functions. Specifically, we present an analysis wherein the objective function is such that its sample-gradient is merely locally Lipschitz continuous. The theory developed herein is supported by empirical results.