Online metric algorithms with untrusted predictions

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 Metrical Task Systems (MTS), a broad class of online decision-making problems including, e.g., caching, k-server and convex body chasing. We utilize results from the theory of online algorithms to show how to make the setup robust. We extend our setup in two ways, (1) adapting it beyond MTS to the online matching on the line problem, and (2) specifically for caching, slightly enriching the predictor’s output to achieve an improved dependence on the prediction error. Finally, we present an empirical evaluation of our methods on real world datasets, which suggests practicality