Decentralized Online Convex Optimization With Feedback Delays

In online decision making, feedback delays often arise due to the latency caused by computation and communication in practical systems. In this article, we study decentralized online convex optimization over a multiagent network in the presence of feedback delays. Each agent is associated with a time-varying local loss function, which is revealed to the agent sequentially with delays. The goal of every agent is to minimize the accumulated total loss function (the sum of the local loss functions of all agents) by choosing appropriate local actions. We first develop an online decentralized gradient descent algorithm for the delayed full information case, in which the delayed local loss function is fully disclosed to each agent. The (static) regret of each agent is upper bounded in terms of the delays for both convex and strongly convex loss functions. We show that, as long as the average delay among all agents is sublinear, so is the regret of every agent. Further, we extend the algorithm and analysis to the scenario of bandit feedback, where only the values of the delayed loss functions at two random points close to the local action are revealed. We demonstrate that the two-point bandit feedback does not entail regret degradation in order sense compared to the full information scenario. Finally, numerical results are presented to corroborate the efficacy of the proposed algorithms.