Adversarial Online Classification with a Preview

arXiv:2608.29503v1 Announce Type: new Abstract: 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 preview rate p: for binary classes of VC dimension d, the optimal excess loss is Theta(d/p+sqrt{dT}), up to the trivial cap at T; for multiclass classes we obtain the corresponding widetilde O(d_{rm DS}/p+sqrt{d_{rm Nat}T}) bound with no dependence on the number of labels. Thus a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order. To achieve the sharp binary bound, our ChainedPrediction algorithm uses an online analogue of chaining, implemented as a multiscale aggregation algorithm rather than only as an analytic argument.

Source: arXiv cs.LG | 2026-09-01

Related