Online Metric Algorithms with Untrusted Predictions
From MaRDI portal
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.
Cites work
- A decision-theoretic generalization of on-line learning and an application to boosting
- A poly-log competitive posted-price algorithm for online metrical matching on a spider
- A primal-dual randomized algorithm for weighted paging
- An optimal on-line algorithm for metrical task system
- Competitive k-server algorithms
- Competitive Algorithms for Layered Graph Traversal
- Competitive algorithms for server problems
- Competitive paging algorithms
- Competitively pricing parking in a tree
- scientific article; zbMATH DE number 1232130 (Why is no real title available?)
- scientific article; zbMATH DE number 2079319 (Why is no real title available?)
- scientific article; zbMATH DE number 7204578 (Why is no real title available?)
- scientific article; zbMATH DE number 7236471 (Why is no real title available?)
- scientific article; zbMATH DE number 7650400 (Why is no real title available?)
- scientific article; zbMATH DE number 7758362 (Why is no real title available?)
- Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
- Metrical task systems on trees via mirror descent and unfair gluing
- Near-Optimal Bounds for Online Caching with Machine Learned Advice
- On-line algorithms for weighted bipartite matching and stable marriages
- On-line learning and the metrical task system problem
- Online computation with advice
- Online matching on a line
- Online Optimization with Uncertain Information
- Online Scheduling via Learned Weights
- Online Weighted Matching
- Parametrized Metrical Task Systems
- Pure entropic regularization for metrical task systems
- Scheduling with Predictions and the Price of Misprediction
- The advice complexity of a class of hard online problems
- The online k-taxi problem
- The weighted majority algorithm
Cited in
(11)- scientific article; zbMATH DE number 7650400 (Why is no real title available?)
- Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
- scientific article; zbMATH DE number 7759300 (Why is no real title available?)
- Learning-augmented algorithms for online subset sum
- Online unit profit knapsack with predictions
- Incorporating predictions in online graph coloring algorithms
- Boosting double coverage for k-server via imperfect predictions
- Online delay management on a single train line with predictions
- Online knapsack problems with estimates
- On approximability of _2² min-sum clustering
- Online promise problems with online width metrics
This page was built for publication: Online Metric Algorithms with Untrusted Predictions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075754)
