Adversarial Online Classification with a Preview
Machine LearningData Structures and Algorithms
Summary
The authors study an online learning scenario where before making predictions, the learner gets a random preview of some labeled examples chosen by an adversary. They show that this preview helps reduce the learning difficulty, measured by how much worse the learner does compared to the best fixed hypothesis. For binary classification, the authors find a precise relationship between preview size, complexity of the hypothesis class, and the prediction error. They also design a new algorithm called ChainedPrediction that uses a layered prediction approach to achieve these results. Their work connects classical statistical learning measures to online learning with limited preview.
Authors
Roi Livni, Sahil Singla
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 $Θ(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.