On Distributed Online Convex Optimization with Sublinear Dynamic Regret and Fit

Pranay Sharma, Prashant Khanduri, Lixin Shen, Donald J. Bucci, Pramod K. Varshney

Research output: Chapter in Book/Entry/PoemConference contribution

5 Scopus citations

Abstract

In this work, we consider a distributed online convex optimization problem, with time-varying (potentially adversarial) constraints. A set of nodes, jointly aim to minimize a global objective function, which is the sum of local convex functions. The objective and constraint functions are revealed locally to the nodes, at each time, after taking an action. Naturally, the constraints cannot be instantaneously satisfied. Therefore, we reformulate the problem to satisfy these constraints in the long term. To this end, we propose a distributed primal-dual mirror descent-based algorithm, in which the primal and dual updates are carried out locally at all the nodes. This is followed by sharing and mixing of the primal variables by the local nodes via communication with the immediate neighbors. To quantify the performance of the proposed algorithm, we utilize the challenging, but more realistic metrics of dynamic regret and fit. Dynamic regret measures the cumulative loss incurred by the algorithm compared to the best dynamic strategy, while fit measures the long term cumulative constraint violations. Without assuming the restrictive Slater's conditions, we show that the proposed algorithm achieves sublinear regret and fit under mild, commonly used assumptions.

Original languageEnglish (US)
Title of host publication55th Asilomar Conference on Signals, Systems and Computers, ACSSC 2021
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Pages1013-1017
Number of pages5
ISBN (Electronic)9781665458283
DOIs
StatePublished - 2021
Event55th Asilomar Conference on Signals, Systems and Computers, ACSSC 2021 - Virtual, Pacific Grove, United States
Duration: Oct 31 2021Nov 3 2021

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
Volume2021-October
ISSN (Print)1058-6393

Conference

Conference55th Asilomar Conference on Signals, Systems and Computers, ACSSC 2021
Country/TerritoryUnited States
CityVirtual, Pacific Grove
Period10/31/2111/3/21

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'On Distributed Online Convex Optimization with Sublinear Dynamic Regret and Fit'. Together they form a unique fingerprint.

Cite this