- 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
-
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.
-
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
-
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.
-
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
-
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?
-
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.
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. 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.