acceptodds
Under review as a conference paper at ICLR 2027

Tight Mistake–Abstention Tradeoffs for Sequential Prediction under Adversarial Injections

Abstract

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 , while the learner is allowed to abstain from making a prediction at no cost if the current instance was indeed injected. When 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 is known, our algorithm improves over Goel et al. (2023) and achieves their conjectured mistake bound; When is unknown, for oblivious adversary, our guarantees are tight both in and in terms of the VC dimension , which completely characterizes the abstention-mistake tradeoff in this setting and gives balanced rate. For adaptive adversary, our results are tight up to factors for structured classes with finite so-called reduction dimension . Our guarantees also extend to censored feedback, where the label is hidden after an abstention.

Primary area:
learning theory
Keywords:
Statistical learning theory, Online learning, Abstention learning, Adaptive and oblivious adversaries, Reliable ML

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_C7hZOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies sequential prediction under clean-label adversarial injections, aiming to control both prediction mistakes across all rounds and abstentions on clean inputs. It considers known and unknown clean distributions, oblivious and adaptive adversaries, and full and censored label feedback. Its main techniques include weighted shattering potentials, age-weighted history potentials, and expert compression and aggregation for adaptive adversaries.

Critical strengths
  1. The weighted shattering potential and its history-based variants yield meaningful improvements in the mistake–abstention tradeoff. In the known-distribution setting, the mistake bound improves from quadratic to linear dependence on the Vapnik–Chervonenkis (VC) dimension, which measures the largest number of inputs on which the class can realize every binary labeling.

  2. For unknown distributions with oblivious injections and full feedback, the upper and lower bounds match in their principal dependence on the VC dimension and interaction horizon. This clarifies the worst-case tradeoff beyond the earlier learnability results. Extending the guarantees to censored feedback is also theoretically valuable.

Critical weaknesses
  1. The connection between the evaluation protocol and practical applications remains insufficiently concrete. Although censored feedback removes the requirement to reveal labels after abstention, the protocol still assumes access to correct labels after prediction. Moreover, abstentions are penalized on clean inputs but are free on injected inputs. A clearer account of label acquisition and the application-specific rationale for these costs would help readers understand how the guarantees translate into practical system costs.

  2. The computational requirements of the proposed algorithms remain unclear. Computing the potentials involves counting shattering witnesses, while the adaptive construction additionally requires candidate-expert construction and aggregation. The results establish statistical guarantees, but it is unclear for which function classes the algorithms can be implemented with reasonable time and memory requirements. This limits the assessment of their practical applicability.

Questions for authors
  1. Could the authors provide a concrete application in which input provenance, label acquisition, and abstention costs correspond to the proposed protocol? As a possible extension, could the potential-based analysis provide meaningful weighted-loss guarantees when prediction mistakes and abstentions on clean and injected inputs incur separate costs?

  2. Could the authors specify the computational complexity and required computational primitives of the main algorithms, and identify at least one nontrivial function class admitting an efficient implementation? If feasible, a small-scale demonstration would also help illustrate their computational practicality.

1 comment

We thank the reviewer for the constructive review and positive feedback. We address the reviewer's suggestions and questions below.

W1 and Q1:

We thank the reviewer for raising the concern about the lack of application-specific motivation. We will add the following motivating example to the paper:

Consider speculative execution of input programs: the learner predicts a program's binary branch outcome and executes speculatively, or abstains and waits for the condition to resolve. Execution naturally reveals the correct label; incorrect speculation incurs wasted work and recovery overhead.

The objective is to accelerate ordinary workloads while avoiding slowdowns on injected inputs relative to non-speculative execution. Under this benchmark, correct predictions on injected inputs incur no loss because they improve performance, and abstentions incur no loss because they match the baseline. Incorrect predictions can cause a slowdown. On clean inputs, abstention forfeits the desired acceleration and is therefore charged.

Extension of the loss model. The reviewer's proposal to generalize the loss model is also reasonable, as it would allow us to account for separate costs of prediction mistakes on clean and injected inputs. However, we need to be careful when assigning a nonzero cost to abstentions on injected inputs. Under such a model, the adversary could simply inject at every round, forcing a loss linear in the time horizon for general VC classes with infinite Littlestone dimension. To avoid this issue, we would need to limit the adversary's number of injected rounds, which would weaken our model. An important feature of our original loss model is that it imposes no limit on the adversary's corruption budget.

W2 and Q2:

In general, our algorithms are not computationally efficient, unless we consider relatively trivial classes such as one-dimensional thresholds. We will make this limitation more explicit in the introduction by clarifying that our algorithms are information-theoretic, and we will also discuss computational efficiency in the added conclusion section.

Indeed, it remains unclear whether learning with abstentions can be made computationally efficient, even for linear classifiers in Rp\mathbb R^p. A statistical–computational gap may exist in this setting, a possibility explicitly raised by Goel et al. (2023, §6), who leave open efficient learning even for halfspaces under Gaussian marginals.

J. Yu and M. Blanchard. "Distribution-Free Sequential Prediction with Abstentions." COLT, 2026.

S. Goel, S. Hanneke, S. Moran, and A. Shetty. "Adversarial Resilience in Sequential Prediction via Abstention." NeurIPS, 2023.

Reviewer_crPVOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies sequential prediction with clean-label adversarial injections, where an adversary can inject an arbitrary number of corrupted examples in an i.i.d. sequence from an underlying distribution μ\mu. The learner is allowed to abstain from making a prediction. Its performance is measured through two quantities: MisErr\textsf{MisErr}, the number of mistakes made, and AbsErr\textsf{AbsErr}, the number of times that the learner chooses to abstain but the example is indeed not corrupted.

The authors examine several settings and obtain improved results:

  1. When μ\mu is known, they give an algorithm that makes O(dlog⁡T)O(d \log T) mistakes with a constant abstention error for any hypothesis class of VC dimension dd, even against an adaptive adversary.
  2. For unknown μ\mu and oblivious injections, they propose an algorithm that achieves an O(Tα)O(T^\alpha) versus O(dT1−α)O(dT^{1-\alpha}) tradeoff between MisErr\textsf{MisErr} and E[AbsErr]\mathbb E[\textsf{AbsErr}]. By constructing a hypothesis class with VC dimension dd and an oblivious adversary, they show that this tradeoff is optimal. They also extend this algorithm to handle censored feedback, where the true label is revealed to the learner only when it makes a prediction (and is hidden if the learner chooses to abstain), with only polylogarithmic overhead.
  3. For unknown μ\mu and adaptive injections, they prove a tradeoff that improves over previous work, under a reduction-dimension assumption, including censored feedback.

The technical novelty for the known distribution setting is a potential that combines the shattering probabilities (Def. 3.1) of all levels. Prior work uses only one level at a time and moves from level dd down to 11, thereby paying an extra factor of dd. The proposed potential treats all levels together and therefore avoids such cost. Their method for unknown μ\mu and oblivious injections extends this idea to an empirical analogy, which defines a potential using observed examples only rather than the distribution μ\mu. For censored feedback, they propose to use an unlabeled-history potential and only restrict the version space after a mistake, avoiding the issues that label visibility depends on the learner's predictions.

Their algorithm for unknown μ\mu and adaptive injections builds upon the algorithm in previous work. The improvement is achieved by a block potential that combines different levels (as in the known distribution case), a score compression argument, and direct aggregation of experts.

Critical strengths
  1. A useful unifying potential improves rates in several settings: the authors propose a potential that combines all levels, whereas previous work treats each level separately. The proposed potential technique serves as the central technical contribution of this work and leads to significantly improved rates in several settings.

  2. A lower bound demonstrates hardness when μ\mu is unknown: the authors propose a lower bound showing that their algorithm achieves an optimal tradeoff for unknown μ\mu and oblivious injections. The lower bound extends a previous result, which holds only for d=1d=1, to arbitrary VC dimension dd. It demonstrates a more general hardness in this problem.

Critical weaknesses

I did not identify any severe weaknesses. But I would suggest the authors clarify the following to improve the presentation:

  1. It is worth emphasizing that the lower bound is in the worst case rather than for every hypothesis class. The conclusion that the tradeoff can not be improved in terms of dd and TT in general remains correct. Clarifying this would help the reader understand the result better.

  2. I also suggest explicitly stating that the algorithm for known distribution works in the censored feedback model. If I understand correctly, this is obvious from the algorithm, but it made me a bit confused when I read up to the intro section. Also, it seems there is a typo in line 64: O(dβ)→O(dlog⁡(1+β))O(d\beta) \rightarrow O(d\log(1+\beta)). The presented bound is also true because log⁡(1+β)≤β\log (1+\beta)\le\beta, but it does not give the O(dlog⁡T)O(d\log T) bound with β=T\beta = T.

Questions for authors

Can you discuss more about the reduction dimension? Does it have any relation to other known dimensions? Are ℓ\ell-reduction dimensions comparable for different ℓ\ell? Is there any hardness result for unknown μ\mu and adaptive injections with infinite reduction dimension, or even any class with finite VC dimension that cannot be learned in this setting?

2 comments

We thank the reviewer for the thoughtful review and positive feedback. We address the reviewer's suggestions and questions below.

W1: Theorem 4.2 constructs a class of VC dimension dd for which every learner faces an oblivious process satisfying the stated lower bound. It does not assert the same lower bound for every class of dimension dd. We will clarify that our lower bound only intends to hold for finite VC-classes in general.

W2: The reviewer's interpretation is correct: Algorithm 1 already works unchanged with censored feedback. We will state this explicitly. We also thank the reviewer for catching the typo in line 64. We will correct the display there.

Questions on reduction dimension

Relationships with other complexity measures. The reduction dimension was proposed in Yu and Blanchard (2026). To the best of our knowledge, there are no clear relationships between reduction dimensions and other common complexity notions, such as VC dimension or Littlestone dimension. The class F=0,1X\mathcal F=\\{0,1\\}^{\mathcal X} has infinite VC dimension but finite reduction dimensions, while there are also morbid VC classes with infinite reduction dimensions. Nevertheless, many natural VC classes, including linear classifiers in Rd\mathbb R^d, VC-dimension-1 classes, axis-aligned rectangles, and subsets of bounded size, are known to have finite reduction dimensions (see Yu and Blanchard (2026)). Meanwhile, one can also construct classes with finite Littlestone dimension but infinite reduction dimensions.

Comparison of ℓ\ell-reduction dimensions for different ℓ\ell. The reduction dimension DℓD_\ell is non-decreasing in the constraint budget ℓ\ell. Its growth can nevertheless depend on the class. For linear classifiers in Rp\mathbb R^p, Yu and Blanchard (2026) give Dℓ=O(p2ℓ)D_\ell=O(p^2\ell). For one-dimensional thresholds, Dℓ=O(1)D_\ell=O(1) uniformly in ℓ\ell.

On hardness results for unknown and adaptive injections with infinite reduction dimension and finite VC dimension. We are not aware of VC classes with infinite reduction dimensions that cannot be learned in the abstention learning setting. The question of obtaining general finite-VC guarantees against adaptive injections was left open by Yu and Blanchard (2026) and is not resolved by our results either. We will include a discussion of this question in the added conclusion section.

J. Yu and M. Blanchard. "Distribution-Free Sequential Prediction with Abstentions." COLT, 2026.

Thank you for your response. I have no further questions and maintain my initial recommendation for acceptance.

Reviewer_HBZAOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies online binary classification with a refusal option. An attacker inserts arbitrary inputs into an independent stream from a fixed distribution, and the learner is not told which inputs were inserted. All labels follow one fixed classifier. The paper tracks two errors which are wrong predictions on any round, and refusals on ordinary rounds only. Refusals on inserted inputs are uncharged. The mistake guarantees hold on every run and the ordinary refusal guarantees are in expectation. For VC dimension dd and TT rounds, the known distribution result improves the mistake bound from O(d2log⁡T)O(d^2\log T) to O(dlog⁡T)O(d\log T) while keeping expected ordinary refusals constant. With an unknown distribution, attacks fixed in advance, and full feedback, it obtains a balanced O(dT)O(\sqrt{dT}) guarantee for both error measures in the stated regime. A lower bound establishes the worst-case polynomial tradeoff, including dimension dependence. Extensions cover labels hidden after refusals and adaptive attacks, the latter under an additional reduction dimension assumption. Validation consists of proofs as there are no experiments.

Critical strengths

The unknown-distribution result improves the general finite VC guarantee in both dimension and number of rounds. The comparison concerns the same two quantities which are wrong predictions on all rounds and expected refusals on ordinary rounds. After tuning Yu and Blanchard’s earlier theorem to balance these quantities, its common bound is O(d3/2T3/4log⁡5/4(2T))O(d^{3/2}T^{3/4}\log^{5/4}(2T)), compared with the submitted O(dT)O(\sqrt{dT}) bound. Both bounds are capped by the trivial TT bound. This comparison is for attacks fixed in advance and full feedback. As such, some special classes already had sharper prior results. The improvement for general VC classes, together with the matching worst-case polynomial lower bound, is my main reason for clear acceptance.

The proof gives a useful way to reason from contaminated history without treating it as a representative sample. It counts sets of positions whose labels can still vary freely while the other labels remain fixed. The bound on their size connects VC dimension to a limit on how many replayed positions can cause refusal, further age dependent weights then improve the refusal rate. The single weighted shattering potential also resolves the known distribution conjecture. The one-point shattering inequality, potential framework, and parts of the extension machinery come from prior work and the contribution is the sharper guarantees and the arguments needed to obtain them.

Critical weaknesses

The main limitation is the scope of the model and its practical consequences. Every label must agree with one fixed classifier, the ordinary population is stationary, and refusals on inserted inputs are free. The algorithms also require potentially large combinatorial calculations; efficient implementation is not established. These points limit the paper's relevance to actual defenses against poisoning or noisy labels. I do not regard them as sufficient reasons to reject the stated theoretical contribution. The adaptive extension should also be read separately from the general finite VC result as it requires an additional complexity condition and does not match the oblivious bound's dimension dependence.

Questions for authors

None whose answer is needed to determine my recommendation.

1 comment

We thank the reviewer for the careful review and positive feedback.

We agree with the reviewer's assessment of the scope. Our results characterize statistical performance under a stationary clean distribution and realizable labels, with abstentions charged only on clean inputs. We haven't established robustness to poisoning or noisy labels.

Unless for relatively simple function classes, our algorithms are not computationally efficient in general. We will make these limitations more explicit by adding an explanation that our algorithms are information-theoretic in the introduction section, and will also add a discussion on this in the added conclusion section. In fact, it remains unclear whether learning with abstentions can be made efficient, even for linear classifiers in Rp\mathbb R^p and under benign. A statistical–computational gap may exist in this setting, a possibility explicitly raised by Goel et al. (2023, §6), who leave open efficient learning even for halfspaces under Gaussian marginals.

S. Goel, S. Hanneke, S. Moran, and A. Shetty. "Adversarial Resilience in Sequential Prediction via Abstention." NeurIPS, 2023.

Comments on the paper

1 comment

We thank all three reviewers for their thoughtful feedback. In the revised manuscript, we have made the following clarifications:

  • Model motivation (§2): Added a speculative-execution example explaining the feedback mechanism and motivating the objective of controlling mistakes on all inputs while penalizing abstentions only on clean inputs.
  • Reduction dimension (§2): Expanded the discussion of its dependence on the constraint budget, with illustrative bounds for linear classifiers and one-dimensional thresholds.
  • Computational scope and open questions (§§1, 6): Explicitly identified our algorithms as information-theoretic and added a conclusion discussing computational efficiency, learning general finite-VC classes against adaptive adversaries, and extensions beyond i.i.d. clean samples.
  • Technical clarifications (§§1, 3, 4): Corrected the introductory statement of the known-distribution mistake bound, explicitly noted that Algorithm 1 also applies under censored feedback, and qualified the lower-bound tightness claim as holding in general.

These revisions clarify the motivation, scope, and limitations of our results; the main theoretical guarantees remain unchanged.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.