Random Preview Improves Adversarial Online Classification Performance.

In traditional worst-case online classification, performance is often limited by sequential complexity, making even statistically simple tasks challenging. This research introduces a "preview model" to address these limitations. In this model, an adversary defines an entire labeled sequence of data, but a uniformly random subset of this data (of size `pT`, where `T` is the total length) is revealed to the classifier *before* any predictions are made. The remaining data is then presented in its original adversarial order. The study characterizes how the optimal excess loss depends on this preview rate `p`. For binary classification problems with a VC dimension `d`, the optimal excess loss is found to be proportional to `d/p + sqrt(dT)`. This demonstrates that introducing a random preview can effectively transform the problem, allowing classical statistical dimensions to govern performance instead of the more restrictive worst-case sequential complexity, without randomizing the online order of the remaining data. To achieve these bounds, the researchers developed an algorithm called ChainedPrediction, which implements an online analogue of chaining using a multiscale aggregation approach. This work provides a novel perspective on improving online classification performance in adversarial settings by leveraging a small, random glimpse into the future data.