|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Online metric algorithms with untrusted predictions | | Antonios Antoniadis
; Christian Coester
; Marek Elias
; Adam Polak
; Bertrand Simon
; | | Date: |
4 Mar 2020 | | Abstract: | Machine-learned predictors, although achieving very good results for inputs
resembling training data, cannot possibly provide perfect predictions in all
situations. Still, decision-making systems that are based on such predictors
need not only to benefit from good predictions but also to achieve a decent
performance when the predictions are inadequate. In this paper, we propose a
prediction setup for arbitrary metrical task systems (MTS) (e.g., caching,
k-server and convex body chasing) and online matching on the line. We utilize
results from the theory of online algorithms to show how to make the setup
robust. Specifically for caching, we present an algorithm whose performance, as
a function of the prediction error, is exponentially better than what is
achievable for general MTS. Finally, we present an empirical evaluation of our
methods on real world datasets, which suggests practicality. | | Source: | arXiv, 2003.2144 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER