Research map / Learning theory and algorithms / Prediction and decision losses
List Update with Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a randomized (1+ε)-smooth list update algorithm with predictions that combines a prediction list with an MTF_ε list, achieving O(1/ε^4) robustness (O(1/ε^2) without prediction paid swaps), plus matching-style lower bounds and simple experiments.
Problem
Online list update with a machine-learned predicted list ordering: achieve near-optimal cost when predictions are accurate while bounding worst-case competitive ratio when they are not.
Approach
Combine the prediction list and an MTF_ε list over space (interleaving elements via a dynamic invariant on positions) rather than alternating between algorithms over time, yielding smoothness 1+ε with robustness O(1/ε^4); also a lazy-conversion lemma that any list-update algorithm can be made lazy without increasing cost.
Key results
- Randomized algorithm is (1+ε)-smooth with robustness O(1/ε^4) when prediction may make paid swaps (bound 3/ε^2 without paid swaps, 1+6ε-smooth in that case).
- Lower bounds: deterministic (1+ε)-smooth algorithms must be Ω(1/ε)-robust; randomized must be Ω(log(1/ε))-robust.
- Experiments show the algorithm typically outperforms MTF, MTF_ε, timestamp and bit algorithms relative to follow-the-prediction.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed randomized algorithm with a prediction restricted to free exchanges | List Update · Prediction uses free exchanges | smoothness: 1 + 6𝜖 | Helped |
| Use the proposed randomized algorithm with a prediction restricted to free exchanges | List Update · Prediction uses free exchanges | robustness: 3/𝜖2 | Helped |
| Allow the prediction to make paid swaps, limited to OPT(𝜎) paid swaps | Proposed randomized algorithm for List Update · Prediction may use paid exchanges | robustness: 3/𝜖2 -> 𝑂( 1/𝜖4 ) | Hurt |
| Allow the prediction to make paid swaps, limited to OPT(𝜎) paid swaps | Proposed randomized algorithm for List Update · Prediction may use paid exchanges | smoothness: 1 + 6𝜖 -> 1+𝜖 | No clear effect |
| Require 1 + 𝜖 smoothness | Deterministic algorithms for List Update · List Update | robustness: Ω( 1/𝜖) | Hurt |
| Require expected cost at most (1 + 𝜖)𝑃𝑅𝐸𝐷 | Randomized algorithms for List Update · “𝑖−1” model | robustness: Ω(log( 1/𝜖)) | Hurt |
| Use the proposed algorithm instead of classical algorithms | List Update · Experiments on generated sequences | cost relative to prediction | Helped |
Surprising findings
- Any list-update algorithm can be converted to a lazy one without increasing cost, which was not previously proved.
Limitations
- Robustness O(1/ε^4) is far from the lower bounds; gap between Ω(log 1/ε) and upper bound remains.
- Deterministic algorithms need Ω(1/ε) robustness, and the randomized algorithm is not deterministic.
- Experiments are on synthetic sequences only.
Experimental setup
Datasets: synthetic request sequences generated by block-wise exponential decay / multiplicative weights distributions
Benchmarks: synthetic list update sequences (n=30/50/100, m=1000-10000)
Metrics: cost ratio relative to follow-the-prediction
Baselines: Move to Front (MTF) MTF_ε timestamp algorithm bit algorithm Random MTF
Builds on: Move to Front MTF_ε Lykouris and Vassilvitskii learning-augmented framework
Closest papers by meaning
- Learning Predictions for Algorithms with Predictions (NeurIPS 2022 · similarity 0.84)
- Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions (NeurIPS 2022 · similarity 0.84)
- Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms (NeurIPS 2024 · similarity 0.83)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.81)
- The Role of Randomness in Stability (ICML 2025 · similarity 0.81)
- Online Algorithms with Uncertainty-Quantified Predictions (ICML 2024 · similarity 0.81)
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.