Online Algorithms with Uncertainty-Quantified Predictions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909215652577280 |
|---|---|
| author | Sun, Bo Huang, Jerry Christianson, Nicolas Hajiesmaili, Mohammad Wierman, Adam Boutaba, Raouf |
| author_facet | Sun, Bo Huang, Jerry Christianson, Nicolas Hajiesmaili, Mohammad Wierman, Adam Boutaba, Raouf |
| contents | The burgeoning field of algorithms with predictions studies the problem of using possibly imperfect machine learning predictions to improve online algorithm performance. While nearly all existing algorithms in this framework make no assumptions on prediction quality, a number of methods providing uncertainty quantification (UQ) on machine learning models have been developed in recent years, which could enable additional information about prediction quality at decision time. In this work, we investigate the problem of optimally utilizing uncertainty-quantified predictions in the design of online algorithms. In particular, we study two classic online problems, ski rental and online search, where the decision-maker is provided predictions augmented with UQ describing the likelihood of the ground truth falling within a particular range of values. We demonstrate that non-trivial modifications to algorithm design are needed to fully leverage the UQ predictions. Moreover, we consider how to utilize more general forms of UQ, proposing an online learning framework that learns to exploit UQ to make decisions in multi-instance settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_11558 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Online Algorithms with Uncertainty-Quantified Predictions Sun, Bo Huang, Jerry Christianson, Nicolas Hajiesmaili, Mohammad Wierman, Adam Boutaba, Raouf Machine Learning Data Structures and Algorithms The burgeoning field of algorithms with predictions studies the problem of using possibly imperfect machine learning predictions to improve online algorithm performance. While nearly all existing algorithms in this framework make no assumptions on prediction quality, a number of methods providing uncertainty quantification (UQ) on machine learning models have been developed in recent years, which could enable additional information about prediction quality at decision time. In this work, we investigate the problem of optimally utilizing uncertainty-quantified predictions in the design of online algorithms. In particular, we study two classic online problems, ski rental and online search, where the decision-maker is provided predictions augmented with UQ describing the likelihood of the ground truth falling within a particular range of values. We demonstrate that non-trivial modifications to algorithm design are needed to fully leverage the UQ predictions. Moreover, we consider how to utilize more general forms of UQ, proposing an online learning framework that learns to exploit UQ to make decisions in multi-instance settings. |
| title | Online Algorithms with Uncertainty-Quantified Predictions |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2310.11558 |