# Fast Rates for Online Prediction with Abstention

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2020.

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

- [Classification with abstention but without disparities](https://mlsanity.com/paper/2102.12258/) (2021)
- [Exponential Savings in Agnostic Active Learning through Abstention](https://mlsanity.com/paper/2102.00451/) (2021)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Faster online calibration without randomization: interval forecasts and the power of two choices](https://mlsanity.com/paper/2204.13087/) (2022)
- [Online Decision Mediation](https://mlsanity.com/paper/2310.18601/) (2023)
- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)
- [Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds](https://mlsanity.com/paper/2602.20111/) (2026)
- [Online Learning with Sublinear Best-Action Queries](https://mlsanity.com/paper/2407.16355/) (2024)
- [Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention](https://mlsanity.com/paper/2402.15127/) (2024)
- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [Selective Nonparametric Regression via Testing](https://mlsanity.com/paper/2309.16412/) (2023)
- [Online Prediction with Limited Selectivity](https://mlsanity.com/paper/2508.09592/) (2025)
- [Learning When Not to Learn: Risk-Sensitive Abstention in Bandits with Unbounded Rewards](https://mlsanity.com/paper/2510.14884/) (2025)
- [Policy Learning with Abstention](https://mlsanity.com/paper/2510.19672/) (2025)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)

## Abstract (arXiv)

In the setting of sequential prediction of individual 0, 1-sequences with expert advice, we show that by allowing the learner to abstain from the prediction by paying a cost marginally smaller than frac 12 (say, 0.49), it is possible to achieve expected regret bounds that are independent of the time horizon T. We exactly characterize the dependence on the abstention cost c and the number of experts N by providing matching upper and lower bounds of order fraclog N1-2c, which is to be contrasted with the best possible rate of √Tlog N that is available without the option to abstain. We also discuss various extensions of our model, including a setting where the sequence of abstention costs can change arbitrarily over time, where we show regret bounds interpolating between the slow and the fast rates mentioned above, under some natural assumptions on the sequence of abstention costs.