Bridging the Gap Between Batch and Online Learnability

This direction is merged into another direction: Littlestone dimension. Its last version stays readable and citable here.

Version 1 of 116 papers18 conceptsfrozen 2026-10-04

In classical machine learning theory, we often distinguish between two worlds: the batch world, where we receive a fixed dataset of independent and identically distributed (i.i.d.) samples, and the online world, where data arrives sequentially and may be chosen by a malicious adversary.

For decades, the Vapnik-Chervonenkis (VC) dimension has been the gold standard for understanding the batch world. If a hypothesis class has a finite VC dimension, it is learnable. However, as Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz established in Agnostic Online Learning, the online world is governed by a much more restrictive metric: the Littlestone dimension.

The Complexity Gap: VC vs. Littlestone

The fundamental tension in this research area is that many simple, practical models have a small VC dimension but a massive—or even infinite—Littlestone dimension.

Consider a simple threshold function on a line. In a batch setting, you only need a few samples to find the threshold. But in an adversarial online setting, an adversary can use a "binary search" strategy to force a mistake at every single step, forever. This "mistake tree" structure is what the Littlestone dimension measures. Because the Littlestone dimension for thresholds is infinite, they are theoretically unlearnable in a fully adversarial online environment.

This creates a "depressing impossibility," as noted by Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. If our theoretical models say that even simple linear thresholds are unlearnable online, then our models might be too pessimistic.

Relaxing the Adversary

Recent research has focused on finding the "middle ground"—settings that are more realistic than a perfect adversary but more challenging than i.i.d. data. The goal is to prove that under these relaxed conditions, learnability depends on the (smaller) VC dimension rather than the (larger) Littlestone dimension.

Strategic Mechanisms for Resilience

Beyond changing the data assumptions, researchers have introduced new mechanisms for the learner itself to bypass the Littlestone bottleneck.

In Adversarial Resilience in Sequential Prediction via Abstention, Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetty propose an abstention model. By allowing the learner to say "I don't know" on difficult, adversarially-targeted examples, the learner can maintain high accuracy on the rest of the stream, effectively reducing the complexity requirement from Littlestone back to VC.

A Unified Perspective on Robustness

The Littlestone dimension is increasingly seen as more than just a measure of "mistakes." It is emerging as a fundamental law of adversarial robustness. Jiatong Yu argues in Robust Streaming, Sampling, and a Perspective on Online Learning that the Littlestone dimension is to adversarial data streams what the VC dimension is to i.i.d. samples. It characterizes the "Adversarial Uniform Law of Large Numbers"—the sample complexity required to representatively sample from a stream that is trying to fool you.

Furthermore, the mathematical properties of these dimensions are becoming clearer. Badih Ghazi, Noah Golowich, and their team showed in Near-tight closure bounds for Littlestone and threshold dimensions that when we combine multiple models (e.g., through intersections or unions), the Littlestone dimension behaves predictably, much like the VC dimension does in batch settings.

By mapping the boundaries between the VC and Littlestone dimensions, this research area provides a roadmap for building online learning systems that are robust enough for the real world without being paralyzed by worst-case theoretical bounds.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bridging_the_gap_between_batch_and_onlin_843eaed2,
  title = {Bridging the Gap Between Batch and Online Learnability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bridging-the-gap-between-batch-and-online-learnability/rdr_843eaed2f36745a3bb2a4bf286383b8a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_bridging_the_gap_between_batch_and_onlin_843eaed2_v1,
  title = {Bridging the Gap Between Batch and Online Learnability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bridging-the-gap-between-batch-and-online-learnability/rdr_843eaed2f36745a3bb2a4bf286383b8a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}