Research map / Learning theory and algorithms / Prediction and decision losses
Learning-Augmented Algorithms with Explicit Predictors
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 learning-augmented online algorithms that treat the predictor as an explicit online learner over prefixes of the input, with bounds for caching, load balancing, and non-clairvoyant scheduling.
Problem
Online algorithms with predictions usually treat the predictor as a pre-trained black box; this paper asks how to integrate the learning of the predictor into the online algorithmic task, using hypothesis classes of likely inputs.
Approach
Split the algorithm into an explicit online predictor that learns which hypothesis (or permutation/instance) matches the input prefix, with switching costs, and an algorithm that computes the offline optimum for the current prediction; regret depends on hypothesis class size rather than sqrt(T) in some settings.
Key results
- Caching realizable deterministic predictor achieves cost at most OPT + k log l; randomized agnostic gives OPT + (5+6/k)mu* + (2k+1) ln l.
- Load balancing randomized predictor gives O(log l) competitive ratio in realizable setting, deterministic gives O(log l log tau); matching Omega(log l) lower bound for restricted assignment.
- Non-clairvoyant scheduling realizable deterministic: total completion time at most OPT + l sqrt(2 OPT).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an explicit majority predictor with FitF instead of the multiple-predictor baseline | Caching · Caching, realizable | additive regret: O(\mu^\star + k + \sqrt{Tk\log \ell}) -> k\log\ell | Helped |
| Use an explicit predictor and scheduling algorithm instead of the prior predictor-based algorithm | Non-clairvoyant scheduling · Non-clairvoyant scheduling, agnostic | regret: linear in \OPT and a higher dependency on \mu^* -> \OPT(I) + \mu^* + O(n^{5/3} \log^{1/3}\ell) | Helped |
Surprising findings
- Non-clairvoyant scheduling with jobs of only two distinct lengths achieves regret n log l, while no algorithm achieves regret o(l n) with three or more distinct lengths.
Limitations
- Results are theoretical and the bounds depend on hypothesis class size, which must be restricted to be useful.
- Robustification increases bounds by constant factors; caching agnostic bound is additive in mu* and ln l.
Experimental setup
Metrics: regret competitive ratio total completion time
Baselines: Im et al. multi-predictor caching (regret O(mu + k + sqrt(Tk log l))) Anand et al. multi-predictor scheduling Azar et al. O(log m) online load balancing Lenstra 2-approximation
Builds on: Belady's FitF halving algorithm Round Robin Shortest Job First Azar et al. online load balancing
Closest papers by meaning
- Online Classification with Predictions (NeurIPS 2024 · similarity 0.88)
- Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms (NeurIPS 2024 · similarity 0.86)
- Learning Augmented Exact Exponential Algorithms (NeurIPS 2026 · similarity 0.85)
- Online Algorithms with Uncertainty-Quantified Predictions (ICML 2024 · similarity 0.85)
- Learning-Augmented Algorithms for $k$-median via Online Learning (NeurIPS 2025 · similarity 0.85)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.85)
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.