Learning-Augmented Algorithms with Unreliable Predictions

This direction is merged into another direction: consistency-robustness trade-off (performance-safety Pareto frontier). Its last version stays readable and citable here.

Version 1 of 126 papers28 conceptsfrozen 2026-10-04

Traditional algorithm design is often a battle against a malicious universe. In the "worst-case analysis" framework, we assume an adversary provides the input, forcing us to settle for pessimistic guarantees. For example, in the classic secretary problem, the best any algorithm can do is select the best candidate with a probability of $1/e \approx 37\%$.

However, in the real world, we often have access to machine learning (ML) models that can predict the future. While these predictions are rarely perfect, they are often better than nothing. A new research direction, often called "learning-augmented algorithms," seeks to bridge the gap between pessimistic theory and data-driven practice by integrating these untrusted predictions into decision-making.

The Pillars of Consistency and Robustness

When we introduce a prediction into an algorithm, we care about two primary metrics:

  1. Consistency: How well does the algorithm perform if the prediction is perfectly accurate? Ideally, a consistent algorithm should approach the optimal offline solution.
  2. Robustness: How poorly does the algorithm perform if the prediction is completely wrong? A robust algorithm should maintain a "safety net," ensuring it never performs significantly worse than a traditional worst-case algorithm.

As Ravi Kumar, Manish Purohit, and Zoya Svitkina argue in Improving Online Algorithms via ML Predictions, the goal is to move beyond the "pessimism" of the worst case. By using predictions, we can break through classical barriers—like the $1/e$ limit in the secretary problem—when advice is good, without being "tricked" into disaster when it is bad.

The Fundamental Trade-off

You cannot have your cake and eat it too. Research across various domains—from auctions to scheduling—has revealed a fundamental mathematical tension: the more you optimize for perfect predictions (consistency), the more you must sacrifice your safety net (robustness).

Spyros Angelopoulos and Christoph Dürr explored this in Online Computation with Untrusted Advice, deriving Pareto-optimal strategies for problems like ski rental. They showed that any gain in consistency typically requires accepting a higher risk of poor performance if the advice is adversarial.

This is not just a design choice but a mathematical limit. Anirudha Majumdar formalizes this in Fundamental Tradeoffs in Learning with Prior Information as a "learning uncertainty principle." If an algorithm performs exceptionally well when its prior assumptions (the predictions) are met, it must perform poorly when reality deviates from those assumptions.

Application in Competitive Environments

This framework is particularly powerful in mechanism design and auctions. In Competitive Auctions with Imperfect Predictions, Pinyan Lu and Jialin Zhang demonstrate that even imperfect data can help an auctioneer outperform traditional designs. They show it is possible to achieve "perfect consistency"—matching the optimal revenue when predictions are right—while still guaranteeing a baseline "constant robustness" revenue if the predictions are wrong.

Similarly, Vasilis Gkatzelis and Xizhi Tan applied this to Clock Auctions Augmented with Unreliable Advice. They found that while predictions can boost social welfare, the designer must carefully navigate the trade-off to ensure that the auction remains simple and private without becoming vulnerable to bad data.

Robust Scheduling and Consensus

In scheduling, the challenge is often "non-clairvoyance"—not knowing how long a job will take until it's finished. Evripidis Bampis and colleagues in Non-Clairvoyant Makespan Minimization Scheduling with Predictions design algorithms that degrade gracefully as prediction error increases.

A sophisticated example of this is the Iterative-Partial-Rebalancing (IPR) algorithm by Eric Balkanski and Clifford Stein in Scheduling with Speed Predictions. IPR uses predictions of machine speeds to balance loads but maintains a mathematical bound that prevents the schedule from spiraling into inefficiency if those speeds were misestimated.

Even in distributed systems, this logic applies. Dahlia Malkhi and Ryan Marcus introduced BFTBrain, which uses reinforcement learning to switch between consensus protocols. It optimizes for peak performance in stable conditions but is designed to be resilient to "data pollution" from malicious nodes, ensuring the system doesn't collapse if the RL engine is misled.

Why It Works: The Safety Net Intuition

The intuition behind these algorithms is often a "hedging" strategy. Instead of fully committing to the prediction, the algorithm allocates a portion of its "budget" or "capacity" to follow the advice and the remainder to follow a robust, traditional strategy.

As Daan Rutten and Adam Wierman explain in Online Optimization with Untrusted Predictions, there is a threshold of trust. If you demand too much consistency, you eventually reach a region where adversarial inputs can induce unbounded costs. The most effective learning-augmented algorithms are those that find the "sweet spot" on the Pareto frontier—leveraging the power of modern ML while respecting the hard limits of worst-case safety.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_learning_augmented_algorithms_with_unrel_34511f6f,
  title = {Learning-Augmented Algorithms with Unreliable Predictions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-augmented-algorithms-with-unreliable-predictions/rdr_34511f6fad6547608ff23291dff3c59b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_learning_augmented_algorithms_with_unrel_34511f6f_v1,
  title = {Learning-Augmented Algorithms with Unreliable Predictions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-augmented-algorithms-with-unreliable-predictions/rdr_34511f6fad6547608ff23291dff3c59b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}