Decentralized Online Convex Optimization with Feedback Delays

Xuanyu Cao, Tamer Basar

Research output: Contribution to journalArticlepeer-review

Abstract

In online decision making, feedback delays often arise due to the latency caused by computation and communication in practical systems. In this paper, we study decentralized online convex optimization over a multi-agent 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 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-p

Original languageEnglish (US)
JournalIEEE Transactions on Automatic Control
DOIs
StateAccepted/In press - 2021

Keywords

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

ASJC Scopus subject areas

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

Fingerprint

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

Cite this