Research map / Learning theory and algorithms / Prediction and decision losses
Algorithms with Calibrated Machine Learning Predictions
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 using calibrated ML predictions (instead of a global trust parameter or conformal intervals) to drive online algorithms for ski rental and job scheduling, with competitive-ratio guarantees and experiments on Citi Bike and sepsis data.
Problem
Algorithms with predictions typically rely on a single aggregate trust parameter, ignoring prediction-level uncertainty that modern ML models can provide; conformal-interval approaches can be uninformative under high variance.
Approach
Use a calibrated predictor's per-instance probability estimates directly in the decision rule: for ski rental, a deterministic policy that rents for a value depending on the predicted probability and a bound on calibration error; for scheduling, order jobs by calibrated probabilities with a threshold rule, showing finer-grained calibration yields better ordering than binary predictions.
Key results
- For ski rental, the calibrated algorithm achieves expected competitive ratio at most 1.8 when advice is calibrated (alpha = 0) and is 1-consistent, with a bound of 1+2alpha+min{E[f(X)]+alpha, 2sqrt(eta+3alpha)}.
- Theory shows the calibrated ski-rental policy beats conformal-prediction-based policy whenever 2alpha + 2sqrt(eta+3alpha) < a for a family of distributions where conformal intervals default to break-even, with expected CR 1+a for break-even.
- On Citi Bike data, the Calibrated algorithm performs best on average among Breakeven, Binary, and Conformal baselines with a small MLP predictor.
- On sepsis scheduling, histogram-calibrated predictions consistently yield smaller normalized delay costs than the naive binary-calibrated predictor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use calibrated predictions instead of the ski-rental baselines | Ski rental on Citi Bike rentals · Citi Bike rentals | expected competitive ratio | Helped |
| use histogram-calibrated, finer-grained predictions instead of naive binary calibration | Online job scheduling · Sepsis triage | normalized delay cost | Helped |
| use a finer-grained calibrated predictor instead of a two-valued coarse calibrated predictor | Online job scheduling · Scheduling with calibrated predictions | expected number of priority inversions | Helped |
| use calibrated predictions instead of conformal prediction | Ski rental · High-variance ski-rental distributions | expected competitive ratio | Helped |
Surprising findings
- Conformal prediction intervals for binary targets can return {0,1}, becoming uninformative under high variance, while calibration still aids decisions.
- Most of the Citi Bike predictors without final-destination features are close to random, limiting predictor usefulness.
Limitations
- Guarantees for ski rental are stated in terms of max calibration error and MSE rather than binary cross entropy or expected calibration error.
- Scheduling analysis assumes iid jobs and a single machine with unit processing times.
- Citi Bike uses single-ride durations as a proxy for day-pass decisions, and predictor accuracy is around 80% at best.
Experimental setup
Datasets: Citi Bike ride data (June 2015) sepsis hospital admissions dataset (110,204 admissions)
Benchmarks: Citi Bike ski rental simulation sepsis job scheduling simulation
Metrics: expected competitive ratio (ALG/OPT) expected additive regret (ALG-OPT, normalized)
Baselines: Breakeven Binary Conformal
Builds on: Platt scaling histogram binning conformal prediction for algorithms with predictions binary-predictor scheduling with predictions
Closest papers by meaning
- Online Algorithms with Uncertainty-Quantified Predictions (ICML 2024 · similarity 0.90)
- Improving Online Algorithms via ML Predictions (NeurIPS 2018 · similarity 0.89)
- Learning Predictions for Algorithms with Predictions (NeurIPS 2022 · similarity 0.89)
- Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice (NeurIPS 2020 · similarity 0.88)
- Testing Calibration in Nearly-Linear Time (NeurIPS 2024 · similarity 0.88)
- Reassessing How to Compare and Improve the Calibration of Machine Learning Models (ICLR 2025 · similarity 0.86)
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.