![[2602.17918] Distribution-Free Sequential Prediction with Abstentions](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.17918] Distribution-Free Sequential Prediction with Abstentions
Summary
This paper explores a distribution-free approach to sequential prediction with abstentions, proposing an algorithm called AbstainBoost that ensures sublinear error rates in the presence of adversarial instances.
Why It Matters
The study addresses a critical gap in machine learning by providing a framework for learning without prior distribution knowledge, which is essential for practical applications in adversarial environments. This research enhances the understanding of how to effectively manage prediction errors while allowing for abstentions, making it relevant for developers and researchers in machine learning.
Key Takeaways
- Introduces a distribution-free algorithm, AbstainBoost, for sequential prediction.
- Addresses the challenge of adversarial instances in machine learning.
- Guarantees sublinear error rates for general VC classes without prior distribution knowledge.
- Explores the trade-off between misclassification error and erroneous abstentions.
- Provides insights into learning under both oblivious and adaptive adversarial conditions.
Computer Science > Machine Learning arXiv:2602.17918 (cs) [Submitted on 20 Feb 2026] Title:Distribution-Free Sequential Prediction with Abstentions Authors:Jialin Yu, Moïse Blanchard View a PDF of the paper titled Distribution-Free Sequential Prediction with Abstentions, by Jialin Yu and Mo\"ise Blanchard View PDF HTML (experimental) Abstract:We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d.\ instances, but at each round, the learner may also \emph{abstain} from making a prediction without incurring any penalty if the instance was indeed corrupted. This semi-adversarial setting naturally sits between the classical stochastic case with i.i.d.\ instances for which function classes with finite VC dimension are learnable; and the adversarial case with arbitrary instances, known to be significantly more restrictive. For this problem, Goel et al. (2023) showed that, if the learner knows the distribution $\mu$ of clean samples in advance, learning can be achieved for all VC classes without restrictions on adversary corruptions. This is, however, a strong assumption in both theory and practice: a natural question is whether similar learning guarantees can be achieved without prior distributional knowledge, as is standard in classical learning frameworks (e.g., PAC learning or asymptotic consistency) and other non-i.i.d.\ models (e.g., smoothed online learning). We therefore focus on the ...