On Tradeoffs in 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_ | 1866929684055326720 |
|---|---|
| author | Benomar, Ziyad Perchet, Vianney |
| author_facet | Benomar, Ziyad Perchet, Vianney |
| contents | The field of learning-augmented algorithms has gained significant attention in recent years. These algorithms, using potentially inaccurate predictions, must exhibit three key properties: consistency, robustness, and smoothness. In scenarios where distributional information about predictions is available, a strong expected performance is required. Typically, the design of these algorithms involves a natural tradeoff between consistency and robustness, and previous works aimed to achieve Pareto-optimal tradeoffs for specific problems. However, in some settings, this comes at the expense of smoothness. This paper demonstrates that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12770 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Tradeoffs in Learning-Augmented Algorithms Benomar, Ziyad Perchet, Vianney Data Structures and Algorithms Artificial Intelligence Machine Learning The field of learning-augmented algorithms has gained significant attention in recent years. These algorithms, using potentially inaccurate predictions, must exhibit three key properties: consistency, robustness, and smoothness. In scenarios where distributional information about predictions is available, a strong expected performance is required. Typically, the design of these algorithms involves a natural tradeoff between consistency and robustness, and previous works aimed to achieve Pareto-optimal tradeoffs for specific problems. However, in some settings, this comes at the expense of smoothness. This paper demonstrates that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance. |
| title | On Tradeoffs in Learning-Augmented Algorithms |
| topic | Data Structures and Algorithms Artificial Intelligence Machine Learning |
| url | https://arxiv.org/abs/2501.12770 |