Source-linked AI summary
Adversarial Online Classification with a Preview
Roi Livni, Sahil Singla
TL;DR
Worst-case online classification can remain impossible for statistically simple classes because adversarial order is governed by Littlestone dimension. This paper studies random preview of an adversarially fixed sequence and develops preview-based online algorithms, obtaining sharp binary and label-independent multiclass bounds. The results show that statistical dimensions can replace sequential complexity without randomizing online arrivals.
Problem
Adversarial online order can make classification hard even for VC-simple classes, so the paper asks what random preview reveals without changing that order.
Method
The paper uses preview-derived finite representations and online multiscale aggregation, including ChainedPrediction, to convert preview information into online prediction algorithms.
Results
Binary excess loss is Θ(d/p + √(dT)) up to the cap at T, while multiclass excess loss is Õ(d_DS/p + √(d_Nat T)) with no dependence on |Y|.
Takeaways & Limitations
A random preview can replace worst-case sequential complexity with classical statistical dimensions while the online examples remain adversarially ordered.
Takeaways & Limitations
The results are information-theoretic and do not claim polynomial-time implementability for arbitrary hypothesis classes without additional structure or oracle access.
Abstract
from arXiv · showhide
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.
1 Introduction
The preview model retains adversarial online order but reveals a random subset beforehand, allowing statistical dimensions to replace Littlestone dimension in the main bounds. Binary rates are sharp, while multiclass rates separate DS label discovery from Natarajan-controlled online aggregation.
- Motivation: VC dimension one does not prevent arbitrarily many mistakes for thresholds, whose Littlestone dimension is infinite under binary-search adversarial sequences.This exhibits the separation between statistical and sequential complexity.
- Preview model: A random preview removes the Littlestone-dimension obstruction while leaving the unrevealed examples in adversarial order.The learner sees pT randomly selected indexed examples before predicting on the remaining sequence.
- Binary results: Θ(d/p + √(dT)) is the sharp binary excess-loss rate, up to the trivial cap at T, with matching lower bounds.The d/p term reflects preview-based discovery, while √(dT) is unavoidable statistical fluctuation.
- Binary results: p ≳ √(d/T) marks the saturation regime where the preview cost is dominated and the rate reaches the statistical scale.For constant d and p = T^-1/2, the bound is already at that scale, unlike a preview-only learner’s Õ(T^3/4) rate.
- Multiclass results: Õ(d_DS/p + √(d_Nat T)) controls multiclass learning independently of the number of labels.The DS term pays for discovering relevant labels, whereas Natarajan dimension controls online aggregation after the local label space is reduced.
- Techniques: ChainedPrediction creates a preview-derived hierarchy and aggregates corrections across levels, turning chaining into an online algorithm rather than only an analytic tool.The construction uses multiscale aggregation, with one-inclusion and sparse online chaining removing logarithmic losses.
2 Model and Preliminaries
The model fixes an adversarial labeled sequence, reveals a uniformly random preview, and presents unrevealed examples online in their original order. Its preliminaries develop randomized-loss evaluation, expert advice, and one-inclusion predictors for preview-based learning.
- Model: The adversary fixes a labeled sequence, after which a uniformly random preview is revealed and the remaining indices arrive online in original order.The learner observes preview positions, instances, and labels before predicting on the unrevealed indices.
- Model: The learner minimizes regret on Real against a fixed best hypothesis chosen independently of the preview.Randomized binary predictions are evaluated through their conditional expected absolute error, with expectations over preview and learner randomness.
- Expert advice: PROD supplies second-order expert-advice regret guarantees for sequential loss vectors, including losses that may be negative.The algorithm chooses distributions over experts and compares cumulative loss with the best expert in hindsight.
- One-inclusion graphs: The one-inclusion graph algorithm permits improper predictions rather than selecting only hypotheses from the target class.Its preview-indexed completion predicts an unseen coordinate from an observed trace and a fixed orientation.
- One-inclusion graphs: Trace-indexed one-inclusion predictors have cardinality equal to the number of hypothesis traces and are therefore controlled by Sauer–Shelah.For a trace on I, the completion depends on the indexed sample, observed trace, and fixed one-inclusion orientation.
3 Binary Classification
The binary section develops ChainedPrediction, a multiscale expert-aggregation algorithm built from increasingly refined preview subsamples, and proves its regret guarantees and matching lower bounds.
- Algorithm: The algorithm constructs a hierarchy of expert classes from increasingly refined preview subsamples, with one-inclusion graphs governing successive refinements.Each level is more informative than its predecessor, and terminal predictors retain ancestors through parent maps.
- Algorithm: ChainedPrediction decomposes prediction across the hierarchy and runs a second-order experts algorithm for the base predictor and each increment.An increment is charged only when it changes the preceding level’s prediction; one-inclusion and Sauer–Shelah bounds control these changes and class sizes.
- Guarantee: The regret guarantee applies to any fixed hypothesis independent of the uniformly sampled preview, in expectation over preview and algorithmic randomness.The guarantee is stated for arbitrary labeled sequences and preview size pT.
- Guarantee: The upper-bound proof combines the comparator’s preview-induced expert with the hierarchical regret bounds, using random-subset properties of each subsample.The analysis handles the trivial regime d/p ≥ T separately and assumes pT ≥ d for the nontrivial multiscale construction.
- Guarantee: The binary upper bound also holds against the stronger comparator that minimizes loss directly on the unrevealed sequence.This follows by combining the theorem with transductive VC uniform convergence for the binary loss class.
- Lower bound: The lower bound uses two constructions yielding Ω(√dT) and Ω(min{T,d/p}) terms, establishing the matching dependence up to the trivial cap.One construction repeats shattered points with independent labels; another measures how many levels remain unseen by the preview.
4 Multiclass Classification
The multiclass section addresses large or infinite label spaces by combining DS-controlled proxy construction, local label menus, and Natarajan-controlled covers before online aggregation.
- Motivation: Large or infinite label spaces make the binary trace-counting strategy non-scalable, even for classes with DS and Natarajan dimension one.The constant-label class illustrates this issue because its preview trace can contain many labels.
- Reduction: The multiclass reduction uses three phases: a DS proxy protects correct comparator predictions, a finite proxy yields local label menus, and Natarajan dimension handles the menu-restricted problem.The resulting strategy separates label-space reduction from the final finite-label learning step.
- Reduction: The DS correct-region cover produces a finite proxy class with logarithmic size controlled by DS dimension and a one-sided comparator guarantee.The proxy only needs to imitate the comparator where the comparator is correct.
- Reduction: Finite-class menu reduction produces a local menu with logarithmic maximum size and preserves a fixed proxy comparator’s labels with high probability.The construction uses a short list of proxy classifiers and includes their predictions in each pointwise menu.
- Reduction: A Natarajan cover inside a menu has logarithmic class size controlled by Natarajan dimension and the menu size.Restricting each point to M candidate labels yields a bound of eO(N log M).
- Online aggregation: The online phase runs multiplicative weights over the final finite expert class, while exact preview sampling supplies the independent uniform subsamples needed by the three offline stages.The imported tools fail with probability at most 3δ, and choosing δ = T^-4 makes the failure contribution negligible.
- Results: A DS-only variant already gives a bound depending only on DS dimension, while the full construction yields the theorem’s improved Natarajan-dependent guarantee.The DS-only stopping point runs multiplicative weights directly over the proxy class.