Decentralized Online Convex Optimization with Feedback Delays

Xuanyu Cao, Tamer Basar

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)2889-2904
Number of pages16
JournalIEEE Transactions on Automatic Control
Issue number6
StatePublished - Jun 1 2022


  • bandit feedback
  • Benchmark testing
  • Convex functions
  • Decentralized optimization
  • Delays
  • feedback delays
  • full information
  • Heuristic algorithms
  • Measurement
  • online convex optimization
  • Optimization
  • Sensors
  • Bandit feedback
  • decentralized optimization
  • online convex optimization (OCO)

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications


Dive into the research topics of 'Decentralized Online Convex Optimization with Feedback Delays'. Together they form a unique fingerprint.

Cite this