Algorithms with Predictions

Michael Mitzenmacher, Sergei VassilvitskiiBeyond the Worst-Case Analysis of Algorithms 2020 · DOI · DBLP

Abstract

Traditional algorithm design focuses on worst-case performance, providing safe but often overly pessimistic guarantees for real-world data. This paper introduces a framework for "Algorithms with Predictions," demonstrating how to integrate fallible machine learning (ML) forecasts into classical algorithms. By optimizing for consistency (performance with accurate predictions) and robustness (performance with poor predictions), the authors show how to achieve near-optimal average-case performance while maintaining strict worst-case reliability across domains such as online scheduling, caching, and data structures.

Introduction

In classical computer science, algorithms are typically evaluated using worst-case analysis. While this ensures reliability against any adversary, it ignores the patterns present in real-world data. Conversely, modern machine learning excels at identifying these patterns but lacks the formal guarantees required for mission-critical systems. This research bridges the gap by asking how algorithms can utilize ML predictions to improve performance without being derailed by prediction errors.

The Framework: Consistency and Robustness

The authors treat the ML model as a "black box" predictor, $h$. To evaluate algorithms using these predictions, they introduce two primary metrics:

  1. Consistency: The algorithm's performance should approach the theoretical offline optimal as the prediction error approaches zero.
  2. Robustness: The algorithm's performance must remain bounded by a constant factor of the standard worst-case performance, even if predictions are arbitrarily bad.

Applications in Data Structures

One of the most prominent applications is the "Learned Bloom Filter." A standard Bloom filter provides a space-efficient way to test set membership with no false negatives. An ML model can act as a pre-filter to identify negatives more efficiently. However, because ML models can produce false negatives, they cannot be used alone.

Architectures for learned data structures: (Left) A learned function followed by a backup filter. (Right) A "sandwiched" architecture with an initial filter, learned function, and backup filter.

As shown in Figure 1, the authors propose "sandwiching" the ML model. In the basic version (left), the learned function identifies positives, and a backup filter handles potential false negatives. The "sandwiched" version (right) adds an initial filter to catch obvious negatives before they reach the ML model, further optimizing space and maintaining the strict mathematical guarantees of traditional structures.

Online Algorithms and Caching

The framework extends to dynamic problems where decisions must be made without full knowledge of the future:

  • Ski Rental: By introducing a confidence parameter $\lambda$, designers can trade off between trusting the prediction (consistency) and hedging against error (robustness).
  • Caching (Paging): The PredictiveMarker algorithm evicts pages based on ML predictions of future needs. Unlike naive implementations, it maintains an $O(\log k)$ competitive ratio (where $k$ is cache size) even with "garbage" predictions, falling back to the performance of the standard randomized marking algorithm.
  • Scheduling: Using "Shortest Predicted Job First" (SPJF), the authors demonstrate that even noisy predictors can drastically reduce average latency in high-load systems.

Key Results

Empirical and theoretical results highlight the power of this approach:

  • Ski Rental: The algorithm achieves a competitive ratio of $1 + \lambda$ when error is zero and $1 + 1/\lambda$ when error is infinite.
  • Scheduling: In simulations with heavy-tailed job distributions, using predictions reduced average system time from 58 units to under 10 units, even with significant noise.
  • Caching: The PredictiveMarker achieves a competitive ratio of $O(\log(\eta(h)/OPT))$, where $\eta(h)$ is the prediction error, ensuring graceful degradation.

Conclusion

The "Algorithms with Predictions" framework provides a rigorous way to harness the power of machine learning in algorithmic design. By explicitly accounting for the "price of misprediction," researchers can build systems that are both highly efficient in practice and theoretically sound in the worst case. Future work includes exploring the computational costs of training these predictors and extending the framework to more complex network and database problems.

Summary updated

BibTeX
@inproceedings{mitzenmacher2020algorithms,
  author = {Michael Mitzenmacher and Sergei Vassilvitskii},
  title = {{Algorithms with Predictions}},
  booktitle = {Beyond the Worst-Case Analysis of Algorithms},
  year = {2020},
  doi = {10.1017/9781108637435.037},
}

Loading related content...

Figure