In the world of computer science, there has long been a divide between the rigorous certainty of classic algorithms and the probabilistic, often messy nature of modern machine learning (ML).

Classic “online algorithms”—like deciding whether to rent skis or buy them when you don’t know how many times you’ll go skiing—are designed to minimize costs even in the absolute worst-case scenario. Machine learning, on the other hand, tries to predict the future based on patterns.

Recently, a new field called Algorithms with Predictions has tried to merge these two worlds. The idea is simple: if we have a hint (a prediction) about the future, can we beat the worst-case performance? Usually, the answer is yes. But there is a catch: How much do we trust the hint?

Most existing approaches ask the user to set a global “trust” parameter, or they assume the prediction is a single point with no context. But modern neural networks can give us more than just a guess; they can tell us how confident they are.

In this post, we are diving deep into a paper titled “Algorithms with Calibrated Machine Learning Predictions” by Shen et al. (2025). This research proposes using calibration—a statistical property where a model’s predicted probability matches the real-world frequency—to dynamically adjust how much an algorithm relies on ML advice.

We will explore how this works through two classic problems: the Ski Rental Problem and Online Job Scheduling, and see why knowing how uncertain a model is can be just as valuable as the prediction itself.

The Core Concept: What is Calibration?

Before we fix our algorithms, we need to understand our tool. In machine learning, a model is often treated as a black box that outputs a score. But does a score of 0.8 mean there is an 80% chance of the event happening? Not always. Many modern deep learning models are “overconfident.”

A predictor is calibrated if the probabilities it assigns to events match their observed frequencies.

Definition of Calibration.

As shown in the equation above, if a calibrated predictor \(f(X)\) outputs a value \(v\) (say, 0.7), then the actual expectation of the target \(T(I)\) should truly be \(v\) (i.e., it happens 70% of the time).

In the real world, perfect calibration is rare. We measure the deviation from perfection using the Max Calibration Error, which looks at the worst-case difference between the predicted probability and the actual outcome across all possible prediction values.

Max Calibration Error equation.

The researchers argue that if we feed these calibrated probabilities into online algorithms, the algorithm can decide per instance whether to trust the ML advice or fall back to a safe, worst-case strategy.

Case Study 1: The Ski Rental Problem

Let’s start with the canonical problem of online decision-making: Ski Rental.

The Dilemma

You are going skiing.

  1. Rent: Costs $1 per day.
  2. Buy: Costs \(b\) dollars (a one-time fee).

The catch? You don’t know how many days (\(z\)) you will ski. If you ski forever, buying is obviously better. If you ski once, renting is better. The “break-even” point is \(b\) days.

If you knew \(z\) exactly, the optimal cost (\(OPT\)) is simple:

\[ \min(z, b) \]

Without knowing \(z\), the best deterministic strategy is to rent for \(b-1\) days and buy on day \(b\). This guarantees you never pay more than twice the optimal cost (a competitive ratio of 2).

Adding Calibrated Predictions

Now, suppose we have an ML model. Instead of just predicting “You will ski 10 days,” our calibrated predictor outputs a probability \(v \in [0, 1]\) representing the likelihood that you will ski more than \(b\) days (the break-even point).

\[ v \approx P(Z > b) \]

The authors propose Algorithm 1, a method that changes its strategy based on this probability \(v\).

Algorithm 1 logic showing the renting strategy based on prediction v.

Here is the intuition behind the math in the image above:

  1. Low Confidence (\(v\) is small): If the model thinks it’s unlikely you’ll ski more than \(b\) days, or if the probability is in a “mushy” middle ground where uncertainty is high relative to the error \(\alpha\), the algorithm plays it safe. It effectively ignores the prediction and defaults to the robust strategy (renting for \(b\) days before buying).
  2. High Confidence: If the model is confident, the algorithm calculates a specific number of days to rent (\(k_*\)) before buying. This calculation smoothly interpolates your risk based on the prediction \(v\) and the calibration error \(\alpha\).

Analyzing the Performance

To prove this works, the authors analyze the Competitive Ratio (CR), which measures how much worse the algorithm performs compared to the optimal “god-view” solution.

Expected Competitive Ratio equation.

The analysis breaks down the problem into different scenarios based on the prediction \(v\) and the actual days skied \(z\). The table below summarizes the cost ratios for different outcomes:

Table 1 showing objective values for different scenarios.

  • Row (ii): If the algorithm decides to buy early (\(k(v) < z\)) but the skiing trip ends shortly after (\(z \le b\)), the algorithm wasted money buying skis.
  • Row (iv): If the algorithm waits too long to buy (\(z > k(v)\)) and skiing continues (\(z > b\)), the algorithm wasted money on rentals.

By minimizing the expected value of these ratios using the calibrated probabilities, the authors derived a powerful bound on performance:

Theorem 3.3 bound on expected competitive ratio.

This inequality tells us that the algorithm’s performance is tightly coupled with the model’s certainty (\(v\)) and its calibration error (\(\alpha\)). When the model is perfectly calibrated (\(\alpha=0\)) and very confident (\(v\) is close to 0 or 1), the performance approaches optimality (Competitive Ratio \(\approx 1\)).

Why Not Use Conformal Prediction?

A popular alternative method for uncertainty is Conformal Prediction, which outputs an interval (e.g., “Days skied will be between [5, 20]”) with a guarantee (e.g., “90% of the time, the truth is in this interval”).

The authors point out a critical flaw in conformal prediction for this specific problem. If the data has high variance, the conformal interval might become huge—e.g., \([0, \infty]\). An interval that says “you will ski between 0 and infinity days” provides zero actionable information.

In contrast, a calibrated predictor might say, “There is a 60% chance you ski more than \(b\) days.” Even though 60% isn’t a certainty, it is a specific probabilistic weight that Algorithm 1 can mathematically exploit to tilt the odds in its favor.

Case Study 2: Online Job Scheduling

The second application is Job Scheduling, specifically motivated by medical triage (e.g., processing diagnostic images).

The Setup

  • We have \(n\) jobs (patients/images).
  • Each job has a priority: High (\(y=1\)) or Low (\(y=0\)).
  • We want to process High priority jobs first to minimize the “weighted completion time.”
  • Problem: We don’t know the priority until after we process the job.

We rely on an ML model to predict the priority.

The Problem with Binary Classification

Previous approaches used a binary classifier: predict if a job is High or Low.

  • If the model predicts “High,” put it in the front.
  • If the model predicts “Low,” put it in the back.

This creates “buckets.” All jobs predicted as “High” are treated equally. But what if one job has a 99% probability of being High, and another has a 51% probability? A binary classifier treats them the same, leading to random ordering within the bucket.

The Calibrated Solution

The authors propose using the raw, calibrated probabilities to sort the jobs. This creates a much finer-grained sequence.

Consider Figure 1 below. It visualizes the difference between a coarse predictor (like a binary classifier that just splits at a threshold \(\beta\)) and a fine-grained calibrated predictor.

Comparison of job sequencing: Fine-grained vs Coarse.

  • Bottom (Coarse): The predictor clumps jobs into two groups. Inside the group, order is random.
  • Top (Fine-grained): The predictor ranks every job by its unique probability. This drastically reduces the chance of “inversions” (processing a Low priority job before a High priority one).

Theoretical Wins

The authors quantify the cost of misordering jobs using “inversions.” An inversion happens when a Low priority job is processed before a High priority one.

The theoretical analysis proves that the expected number of inversions drops significantly as the predictor becomes more granular.

Theorem 4.3 bounds on inversions.

While the math in the image above is dense, the takeaway is in the terms \(\kappa_1\) and \(\kappa_2\). These represent the variance of the predictor. A binary predictor has zero variance within its buckets (it thinks everything in the bucket is identical). A calibrated predictor exploits the variance between instances to push probable High-priority jobs to the very front.

Experiments: Does it Work in Real Life?

The researchers tested their theory on two real-world datasets.

1. Citi Bike (Ski Rental)

They used data from Citi Bike in New York City.

  • Rent: Pay per minute.
  • Buy: Buy a day pass.
  • Goal: Decide based on user features (start time, location, etc.) whether to buy a day pass.

They compared their Calibrated approach against a standard Breakeven algorithm (deterministic), a Binary predictor approach, and a Conformal prediction approach.

Graph comparing Citi Bike algorithms.

Figure 2 (above) shows the ratio of the algorithm’s cost to the optimal cost (lower is better).

  • The Red Line (Calibrated) consistently hugs the bottom of the graph.
  • The Conformal method (Blue) struggles when the break-even point gets high (meaning the decision is riskier), likely because the prediction intervals become too wide to be useful.

Interestingly, the effectiveness depends on the quality of the data features. When the model has “Rich Info” (exact GPS coordinates of the destination), the calibrated model shines even brighter.

XGBoost performance with rich features.

As seen in Figure 6 (above), particularly in panel (c) with “Rich info,” the Calibrated method (Red) maintains a massive lead over the Breakeven strategy (Green).

2. Sepsis Triage (Scheduling)

They utilized a hospital dataset to predict sepsis (a life-threatening reaction to infection). The goal was to “schedule” patients for treatment based on risk.

  • Metric: Total weighted delay (Cost).
  • Comparison: A standard Binary classifier vs. a Calibrated probability ranking.

Sepsis triage results showing cost reduction.

Figure 3 (above) illustrates the results. The y-axis is the cost (normalized regret).

  • The Solid Lines (Calibrated) are consistently lower than the Dashed Lines (Binary).
  • This confirms the theory: treating predictions as granular probabilities rather than binary buckets leads to better sorting and fewer dangerous delays for critical patients.

Conclusion

The paper “Algorithms with Calibrated Machine Learning Predictions” bridges a vital gap between theoretical computer science and practical machine learning.

For years, algorithm designers treated ML predictions as either perfect oracles or untrustworthy noise. This work suggests a middle path: listen to the model, but listen to its uncertainty too.

By using calibration, we can:

  1. Interpolate Risk: In Ski Rental, we don’t just “Rent” or “Buy”; we rent for a duration that precisely matches our confidence.
  2. Improve Ranking: In Scheduling, we stop treating urgent jobs as a monolithic block and prioritize the most probable cases first.

The takeaway for students and practitioners is clear: When building learning-augmented systems, don’t just look at accuracy. Look at calibration. A model that knows when it doesn’t know is a powerful tool for robust decision-making.