# Compressing Value Predictions for Learning-Augmented Metrical Task Systems

arXiv: https://arxiv.org/abs/2609.33580 · HTML: https://mlsanity.com/paper/2609.33580/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 29 references that are in the map.
- First posted on arXiv 27 Sep 2026.

## Builds on (most cited first, 19 of 19)

- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [The Randomized k-Server Conjecture is False!](https://mlsanity.com/paper/2211.05753/) (2022)
- [Parsimonious Learning-Augmented Approximations for Dense Instances of NP-hard Problems](https://mlsanity.com/paper/2402.02062/) (2024)
- [Pure entropic regularization for metrical task systems](https://mlsanity.com/paper/1906.04270/) (2019)
- [Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems](https://mlsanity.com/paper/2406.18752/) (2024)
- [Online Primal-Dual Algorithms with Predictions for Packing Problems](https://mlsanity.com/paper/2110.00391/) (2021)
- [Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems](https://mlsanity.com/paper/2402.08701/) (2024)
- [Parsimonious Learning-Augmented Online Metric Matching](https://mlsanity.com/paper/2605.26886/) (2026)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)

## Abstract (arXiv)

Learning-augmented algorithms for metrical task systems (MTS) can exploit predictions of canonical dual values, but existing formulations typically require a prediction for every state. We study whether these predictions can be compressed to a small set of representative states while retaining their algorithmic value. We introduce landmark-compressed value predictions, in which the predictor reports predicted dual values only at m landmarks and the remaining values are reconstructed by a Lipschitz extension. Our algorithm achieves additive excess cost O(T,r(L) + sumt δt), where r(L) is the covering radius of the landmarks and δt measures prediction error up to additive shifts; local and value-dependent bounds refine this guarantee. For sparse landmark sets on unit-spaced finite lines, we prove a matching Omega(T rm) lower bound for every randomized algorithm using fixed landmarks, even with advance access to their entire exact absolute-value table. The prediction interface also matters: on two states with one landmark, exact absolute values permit horizon-independent excess, whereas exact relative values force worst-case expected excess linear in T. We give PAC guarantees for learning compressed prediction tables, with efficient empirical-risk minimization for fixed landmarks. Our results connect metric coverage, prediction interfaces, and learning guarantees for compressed predictions in online MTS.