Adversarial Online Classification with a Preview

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+√dT), up to the trivial cap at T; for multiclass classes we obtain the corresponding widetilde O(drm DS/p+√drm NatT) 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.