# Beyond Worst-Case Analysis

arXiv: https://arxiv.org/abs/1806.09817 · HTML: https://mlsanity.com/paper/1806.09817/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2018.

## Built on by (most cited first, 6 of 6)

- [Average gradient outer product as a mechanism for deep neural collapse](https://mlsanity.com/paper/2402.13728/) (2024)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)
- [Online Primal-Dual Algorithms with Predictions for Packing Problems](https://mlsanity.com/paper/2110.00391/) (2021)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Sublinear Time Algorithms for Several Geometric Optimization (With Outliers) Problems In Machine Learning](https://mlsanity.com/paper/2301.02870/) (2023)

## Abstract (arXiv)

In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input. This approach has countless success stories, but there are also important computational problems --- like linear programming, clustering, online caching, and neural network training --- where the worst-case analysis framework does not provide any helpful advice on how to solve the problem. This article covers a number of modeling methods for going beyond worst-case analysis and articulating which inputs are the most relevant.