# Competitive strategies to use "warm start" algorithms with predictions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 25 references that are in the map.
- First posted on arXiv 6 May 2024.

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

- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Predictive Flows for Faster Ford-Fulkerson](https://mlsanity.com/paper/2303.00837/) (2023)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Learning-to-learn non-convex piecewise-Lipschitz functions](https://mlsanity.com/paper/2108.08770/) (2021)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [On the Complexity of Algorithms with Predictions for Dynamic Graph Problems](https://mlsanity.com/paper/2307.16771/) (2023)
- [Fully Dynamic k-Clustering in tilde O(k) Update Time](https://mlsanity.com/paper/2310.17420/) (2023)

## Built on by (most cited first, 4 of 4)

- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)
- [Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach](https://mlsanity.com/paper/2512.07313/) (2025)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)
- [CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees](https://mlsanity.com/paper/2607.14545/) (2026)

## Abstract (arXiv)

We consider the problem of learning and using predictions for warm start algorithms with predictions. In this setting, an algorithm is given an instance of a problem, and a prediction of the solution. The runtime of the algorithm is bounded by the distance from the predicted solution to the true solution of the instance. Previous work has shown that when instances are drawn iid from some distribution, it is possible to learn an approximately optimal fixed prediction (Dinitz et al, NeurIPS 2021), and in the adversarial online case, it is possible to compete with the best fixed prediction in hindsight (Khodak et al, NeurIPS 2022). In this work we give competitive guarantees against stronger benchmarks that consider a set of k predictions P. That is, the "optimal offline cost" to solve an instance with respect to P is the distance from the true solution to the closest member of P. This is analogous to the k-medians objective function. In the distributional setting, we show a simple strategy that incurs cost that is at most an O(k) factor worse than the optimal offline cost. We then show a way to leverage learnable coarse information, in the form of partitions of the instance space into groups of "similar" instances, that allows us to potentially avoid this O(k) factor. Finally, we consider an online version of the problem, where we compete against offline strategies that are allowed to maintain a moving set of k predictions or "trajectories," and are charged for how much the predictions move. We give an algorithm that does at most O(k4 ln2 k) times as much work as any offline strategy of k trajectories. This algorithm is deterministic (robust to an adaptive adversary), and oblivious to the setting of k. Thus the guarantee holds for all k simultaneously.