# Online Prediction with Limited Selectivity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 15 references that are in the map.
- First posted on arXiv 13 Aug 2025.

## Builds on (most cited first, 11 of 11)

- [Online Learning with Abstention](https://mlsanity.com/paper/1703.03478/) (2017)
- [Fast Rates for Online Prediction with Abstention](https://mlsanity.com/paper/2001.10623/) (2020)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [The Extended Littlestone's Dimension for Learning with Mistakes and Abstentions](https://mlsanity.com/paper/1604.06162/) (2016)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [A Theory of Selective Prediction](https://mlsanity.com/paper/1902.04256/) (2019)
- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)
- [Why are images smooth?](https://mlsanity.com/paper/1406.5035/) (2014)
- [Exponential Weights Algorithms for Selective Learning](https://mlsanity.com/paper/2106.15662/) (2021)
- [Chasing Ghosts: Competing with Stateful Policies](https://mlsanity.com/paper/1407.7635/) (2014)
- [Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error](https://mlsanity.com/paper/2112.13832/) (2021)

## Abstract (arXiv)

Selective prediction [Dru13, QV19] models the scenario where a forecaster freely decides on the prediction window that their forecast spans. Many data statistics can be predicted to a non-trivial error rate without any distributional assumptions or expert advice, yet these results rely on that the forecaster may predict at any time. We introduce a model of Prediction with Limited Selectivity (PLS) where the forecaster can start the prediction only on a subset of the time horizon. We study the optimal prediction error both on an instance-by-instance basis and via an average-case analysis. We introduce a complexity measure that gives instance-dependent bounds on the optimal error. For a randomly-generated PLS instance, these bounds match with high probability.