SOURCE-LINKED INTELLIGENCE

Adversarial Online Classification with a Preview

arXiv · AI, language, vision and robotics · article · Aug 30, 2026 · UTC

Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as thresholds of VC dimension one. We study a preview model in which an oblivious adversary fixes an entire labeled sequence of length $T$, a uniformly random subset of size $pT$ is revealed before prediction begins, and the remaining $(1-p)T$ examples are then presented in their original adversarial order. Against the best full-sequence hypothesis evaluated on the unrevealed examples, we characterize the dependence on the previ

Read original source ↗ Open in workspace

recordType

paper

region

Global