# Adversarial Online Classification with a Preview

arXiv: https://arxiv.org/abs/2608.29503 · HTML: https://mlsanity.com/paper/2608.29503/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 30 Aug 2026.

## Builds on (most cited first, 16 of 16)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Limits of Private Learning with Access to Public Data](https://mlsanity.com/paper/1910.11519/) (2019)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [Competitive Analysis with a Sample and the Secretary Problem](https://mlsanity.com/paper/1907.05350/) (2019)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [Online Weighted Matching with a Sample](https://mlsanity.com/paper/2104.05771/) (2021)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)
- [Set Covering with Our Eyes Wide Shut](https://mlsanity.com/paper/2304.02063/) (2023)
- [Online Learning in the Random Order Model](https://mlsanity.com/paper/2510.02820/) (2025)
- [Optimal Mistake Bounds for Transductive Online Learning](https://mlsanity.com/paper/2512.12567/) (2025)
- [Online Combinatorial Optimization with Graphical Dependencies](https://mlsanity.com/paper/2507.16031/) (2025)

## Abstract (arXiv)

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.