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 language | English |
---|---|
Title of host publication | IEEE INFOCOM 2024 - IEEE Conference on Computer Communications |
Publisher | IEEE |
Pages | 2159-2168 |
Number of pages | 10 |
ISBN (Electronic) | 9798350383508 |
DOIs | |
Publication status | Published - 20 May 2024 |
Event | IEEE International Conference on Computer Communications, IEEE INFOCOM 2024 - Vancouver, Canada Duration: 20 May 2024 → 23 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
Name | Proceedings - IEEE INFOCOM |
---|---|
ISSN (Print) | 0743-166X |
Conference
Conference | IEEE International Conference on Computer Communications, IEEE INFOCOM 2024 |
---|---|
Country/Territory | Canada |
City | Vancouver |
Period | 20/05/24 → 23/05/24 |
Internet address |
|
Scopus Subject Areas
- General Computer Science
- Electrical and Electronic Engineering