Research map / Learning theory and algorithms / Prediction and decision losses
Online metric algorithms with untrusted predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TRUST&DOUBT instead of prior prediction-augmented caching algorithms (L&V) with POPU predictions | caching · Caching BK and Citi, POPU/PLECO predictions | competitive ratio: BK POPU 1.274 vs L&V 1.262 (L&V better); PLECO 1.292 vs 1.340; Citi POPU 1.774 vs 1.776 | Helped |
| Using PLECO predictions with previously known robust algorithms (L&V, LMarker) instead of Marker | caching · Caching BK, PLECO predictions | competitive ratio: L&V 1.340 vs Marker 1.333 | No clear effect |
| Use simple POPU predictions instead of PLECO predictions for prediction-augmented caching | caching · Caching BK dataset | competitive ratio: L&V 1.340 (PLECO) to 1.262 (POPU) | Helped |
| Replace predictions with LRU predictions for prediction-augmented caching | caching · Caching BK and Citi, LRU predictions | competitive ratio: TRUST&DOUBT 1.291 vs LRU 1.291 (BK); 1.848 vs 1.848 (Citi) | No clear effect |
| Naive follow-the-prediction (FTP) without robustification (ablation) | caching · Caching BK, PLECO predictions | competitive ratio: FTP 2.081 vs Marker 1.333 | Hurt |
| Robustify FTP by combining with Marker (RobustFtP) versus naive FTP (ablation) | caching · Caching BK, POPU predictions | competitive ratio: RobustFtP 1.316 vs FTP 1.707 | Helped |
| Combine work function algorithm with FTP via deterministic and randomized combination on ice cream problem (ablation) | ice cream MTS · Ice cream problem, synthetic predictions | competitive ratio: randomized combination performs even better than the Work Function algorithm, even with completely random predictions | Helped |
| Replace standard Marker-based robust method with randomized combination of FTP and Work Function on ice cream (ablation) | ice cream MTS · Ice cream problem, synthetic predictions | competitive ratio: deterministic combination comparable to best of the algorithms combined | No clear effect |
Closest papers by meaning
- Learning-Augmented Algorithms with Explicit Predictors (NeurIPS 2024 · similarity 0.86)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.85)
- Algorithms for Caching and MTS with reduced number of predictions (ICLR 2024 · similarity 0.85)
- Online Classification with Predictions (NeurIPS 2024 · similarity 0.84)
- Barely Random Algorithms and Collective Metrical Task Systems (NeurIPS 2024 · similarity 0.84)
- A General Online Algorithm for Optimizing Complex Performance Metrics (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.