Tight Mistake–Abstention Tradeoffs for Sequential Prediction under Adversarial Injections

We study the sequential prediction problem introduced by Goel et al. (2023) , where an adversary can inject arbitrarily many corrupted instances in an i.i.d. stream from a clean distribution $\mu$, while the learner is allowed to abstain from making a prediction at no cost if the current instance was indeed injected. When $\mu$ is unknown, Yu and Blanchard (2026) shows a polynomial tradeoff between mistakes and false abstentions for classes with finite VC dimension, but still leaves open a significant gap between upper and lower bounds in their tradeoff landscape. In this paper, we propose the weighted shattering potential, and based on variants of this potential, provide algorithms that essentially characterize the tradeoffs under various settings of interest: When $\mu$ is known, our algorithm improves over Goel et al. (2023) and achieves their conjectured $O(d\log T)$ mistake bound; When $\mu$ is unknown, for oblivious adversary, our guarantees are tight both in $T$ and in terms of the VC dimension $d$, which completely characterizes the abstention-mistake tradeoff in this setting and gives $O(\sqrt{dT})$ balanced rate. For adaptive adversary, our results are tight up to $poly(dD\log T)$ factors for structured classes with finite so-called reduction dimension $D$. Our guarantees also extend to censored feedback, where the label is hidden after an abstention.