Augment Online Linear Optimization with Arbitrarily Bad Machine-Learned Predictions

Dacheng Wen, Yupeng Li*, Francis C.M. Lau

*Corresponding author for this work

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

3 Citations (Scopus)

Abstract

The online linear optimization paradigm is important to many real-world network applications as well as theoretical algorithmic studies. Recent studies have made attempts to augment online linear optimization with machine-learned predictions of the cost function that are meant to improve the performance of the algorithms. However, they fail to address the critical case in practical systems where the predictions can be arbitrarily bad. In this work, we take the first step to study the problem of online linear optimization with a dynamic number of arbitrarily bad machine-learned predictions per round and propose an algorithm termed OLOAP. Our theoretical analysis shows that, when the qualities of the predictions are satisfactory, OLOAP achieves a regret bound of O(logT), which circumvents the tight lower bound of Ω( T ) for the vanilla problem of online linear optimization (i.e., the one without any predictions). Meanwhile, the regret of our algorithm is never worse than O( T ) irrespective of the qualities of predictions. In addition, we further derive a lower bound for the regret of the studied problem, which demonstrates that OLOAP is near-optimal. We consider two important network applications and conduct extensive evaluations. Our results validate the superiority of our algorithm over state-of-the-art approaches.

Original languageEnglish
Title of host publicationIEEE INFOCOM 2024 - IEEE Conference on Computer Communications
PublisherIEEE
Pages2159-2168
Number of pages10
ISBN (Electronic)9798350383508
DOIs
Publication statusPublished - 20 May 2024
EventIEEE International Conference on Computer Communications, IEEE INFOCOM 2024 - Vancouver, Canada
Duration: 20 May 202423 May 2024
https://infocom2024.ieee-infocom.org/ (Link to conference website)
https://infocom2024.ieee-infocom.org/program/main-technical-program (Link to conference programme)
https://ieeexplore.ieee.org/xpl/conhome/10621050/proceeding

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Conference

ConferenceIEEE International Conference on Computer Communications, IEEE INFOCOM 2024
Country/TerritoryCanada
CityVancouver
Period20/05/2423/05/24
Internet address

Scopus Subject Areas

  • General Computer Science
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Augment Online Linear Optimization with Arbitrarily Bad Machine-Learned Predictions'. Together they form a unique fingerprint.

Cite this