Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908539090370560 |
|---|---|
| author | Angelopoulos, Spyros Dürr, Christoph Melidi, Georgii |
| author_facet | Angelopoulos, Spyros Dürr, Christoph Melidi, Georgii |
| contents | We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, and stochastic measures that balance the trade-off between the algorithm's performance and the risk associated with the imperfect oracle. These approaches allow us to quantify the algorithm's performance across the full spectrum of the prediction error, and thus choose the best algorithm within an entire class of otherwise incomparable ones. We apply our framework to three well-known problems from online decision making, namely ski-rental, one-max search, and contract scheduling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17701 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms Angelopoulos, Spyros Dürr, Christoph Melidi, Georgii Data Structures and Algorithms Machine Learning We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, and stochastic measures that balance the trade-off between the algorithm's performance and the risk associated with the imperfect oracle. These approaches allow us to quantify the algorithm's performance across the full spectrum of the prediction error, and thus choose the best algorithm within an entire class of otherwise incomparable ones. We apply our framework to three well-known problems from online decision making, namely ski-rental, one-max search, and contract scheduling. |
| title | Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2501.17701 |