Decentralized online convex optimization based on signs of relative states

Xuanyu Cao, Tamer Başar

Research output: Contribution to journalArticlepeer-review


In this paper, we study a class of decentralized online convex optimization problems with time-varying loss functions over multi-agent networks. We propose a decentralized online subgradient method by using only the signs of the relative states of neighbors, which considerably reduces the sensing and communication requirements for the agents. We show that, despite the loss of information, the proposed algorithm can still achieve O(T) regret bound (T is the time horizon), which matches that of the standard distributed online subgradient method with exact relative state information. We further investigate the scenario of using noisy signs, where the measurements of the directions of the relative states are perturbed by noise. We show that the regret bound is not affected as long as the noise is not too large, which manifests certain noise-tolerance property of the proposed algorithm. Additionally, we extend the algorithm to the case of bandit feedback, where only the values of the local loss functions at two points are revealed to agents at each time. We demonstrate that the regret bound is not influenced by bandit feedback in order sense. Finally, numerical experiments on decentralized online least squares and logistic regression are conducted to corroborate the efficacy of the proposed algorithms.

Original languageEnglish (US)
Article number109676
StatePublished - Jul 2021
Externally publishedYes


  • Bandit feedback
  • Decentralized optimization
  • Noisy measurement
  • Online convex optimization
  • Signs of relative states
  • Subgradient method

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Decentralized online convex optimization based on signs of relative states'. Together they form a unique fingerprint.

Cite this