Delay-Tolerant Constrained OCO with Application to Network Resource Allocation

Juncheng Wang, Ben Liang, Min Dong, Gary Boudreau, Hatem Abou-Zeid

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

5 Citations (Scopus)

Abstract

We consider online convex optimization (OCO) with multi-slot feedback delay, where an agent makes a sequence of online decisions to minimize the accumulation of time-varying convex loss functions, subject to short-term and long-term constraints that are possibly time-varying. The current convex loss function and the long-term constraint function are revealed to the agent only after the decision is made, and they may be delayed for multiple time slots. Existing work on OCO under this general setting has focused on the static regret, which measures the gap of losses between the online decision sequence and an offline benchmark that is fixed over time. In this work, we consider both the static regret and the more practically meaningful dynamic regret, where the benchmark is a time-varying sequence of per-slot optimizers. We propose an efficient algorithm, termed Delay-Tolerant Constrained-OCO (DTC-OCO), which uses a novel constraint penalty with double regularization to tackle the asynchrony between information feedback and decision updates. We derive upper bounds on its dynamic regret, static regret, and constraint violation, proving them to be sublinear under mild conditions. We further apply DTC-OCO to a general network resource allocation problem, which arises in many systems such as data networks and cloud computing. Simulation results demonstrate substantial performance gain of DTC-OCO over the known best alternative.
Original languageEnglish
Title of host publicationIEEE INFOCOM 2021 - IEEE Conference on Computer Communications
PublisherIEEE
Number of pages10
ISBN (Electronic)9781665403252
ISBN (Print)9781665431316
DOIs
Publication statusPublished - May 2021
Event40th IEEE Conference on Computer Communications, IEEE INFOCOM 2021 - Vancouver, BC, Canada
Duration: 10 May 202113 May 2021
https://infocom2021.ieee-infocom.org/ (Conference website)
https://ieeexplore.ieee.org/xpl/conhome/9488422/proceeding (Conference proceedings)

Publication series

NameProceedings of IEEE Conference on Computer Communications
PublisherIEEE
Volume2021-May
ISSN (Print)0743-166X
ISSN (Electronic)2641-9874

Conference

Conference40th IEEE Conference on Computer Communications, IEEE INFOCOM 2021
Country/TerritoryCanada
CityVancouver, BC
Period10/05/2113/05/21
Internet address

User-Defined Keywords

  • Online convex optimization
  • Multi-slot delay
  • Long-term constraints
  • Dynamic regret
  • Constraint violation
  • Network resource allocation

Fingerprint

Dive into the research topics of 'Delay-Tolerant Constrained OCO with Application to Network Resource Allocation'. Together they form a unique fingerprint.

Cite this