SIGMETRICS'26 - Prediction-Specific Design of Learning-Augmented Algorithms

Why It Matters

This work enables algorithm designers to exploit prediction values more effectively, improving practical performance without sacrificing worst-case safety—boosting real-world decision systems that rely on forecasts. The method provides a systematic, provable route to stronger average-case outcomes across canonical online problems.

Summary

Researchers introduce a prediction-specific framework for learning-augmented online algorithms that decouples worst-case instance analysis from the prediction layer, allowing performance guarantees tailored to particular prediction values. They define prediction-specific consistency and robustness and formalize weak and strong optimality, where strong optimality requires Pareto-optimal trade-offs for every prediction. The paper presents a bilevel optimization method that, given a robustness target, first minimizes consistency then robustness to produce strongly optimal algorithms, and supplies explicit strong-alpha designs for deterministic and randomized ski rental and one-way search. Empirical tests on synthetic data and real-world price series (DPM and VIX) show these strongly optimal algorithms outperform prior weakly optimal and classic competitive algorithms for most predictions while preserving worst-case guarantees.