Distributed Constrained Online Convex Optimization Over Multiple Access Fading Channels

Xuanyu Cao, Tamer Basar

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we study distributed constrained online convex optimization for a wireless system consisting of a parameter server and multiple agents. Each agent has a local constraint function and a time-varying local loss function, and needs to choose sequential actions based on causal information. The goal of the overall system is to minimize the accumulated total loss of all agents over a time horizon subject to total constraints of the agents. To this end, the agents communicate with the server over multiple access noisy fading channels, where the information is exchanged imperfectly. We first consider the full information scenario, where the local loss function of each agent is fully revealed to the corresponding agent in each time slot. We propose a modified saddle-point algorithm, where each agent sends an analog signal pertaining to the current value of the local constraint function and the server receives a superposition of these signals distorted by the noisy fading channels. We analyze the performance of the proposed algorithm, and establish <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(\sqrt{T})$</tex-math></inline-formula> regret bound and <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(T^\frac{3}{4})$</tex-math></inline-formula> constraint violation bound for the algorithm, where <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> is the time horizon. Further, we extend the algorithm and performance analyses to the scenario of bandit feedback, where only the values of the local loss functions at two random points are disclosed to the agents in every time slot. In such a case, performance bounds similar to the full information scenario are established. Finally, numerical examples are presented to corroborate the efficacy of the proposed algorithms.

Original languageEnglish (US)
Pages (from-to)1-16
Number of pages16
JournalIEEE Transactions on Signal Processing
DOIs
StateAccepted/In press - 2022

Keywords

  • Distance learning
  • Fading channels
  • Noise measurement
  • Online convex optimization
  • Optimization
  • Resource management
  • Servers
  • Signal processing algorithms
  • channel fading
  • channel noise
  • constrained optimization
  • distributed optimization
  • multiple access

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Distributed Constrained Online Convex Optimization Over Multiple Access Fading Channels'. Together they form a unique fingerprint.

Cite this