Sequential Rademacher Complexity for Online Learnability

This direction is split into other directions: sequential fat-shattering dimension, sequential Rademacher complexity. Its last version stays readable and citable here.

Version 1 of 158 papers96 conceptsfrozen 2026-10-04

In classical statistical learning theory, we often assume that data is independent and identically distributed (i.i.d.). Under this assumption, tools like the VC-dimension and Rademacher complexity allow us to bound how well a model will generalize from a finite sample. However, these tools break down in the "online" setting, where data arrives sequentially and may be chosen by an adversary who reacts to the learner's previous actions.

To handle this, a body of research led by Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari has developed a "sequential" version of statistical learning theory. This framework replaces static sets of data with tree-structured processes to characterize the fundamental limits of online learnability.

From Sets to Trees

The core difficulty of online learning is that the future depends on the past. In Online Learning: Random Averages, Combinatorial Parameters, and Learnability, the authors argue that a static set of points is insufficient to represent the challenges of sequential data. Instead, they model the input space as a complete binary tree.

In this tree, each node represents a possible observation. A path from the root to a leaf represents one possible realization of a data sequence. This structure captures the adversary's power: at each step, the adversary can choose the next data point based on the learner's previous moves. To be "learnable," a hypothesis class must be simple enough that it cannot "shatter" the nodes of these trees, regardless of which path the adversary forces the learner down.

Sequential Rademacher Complexity

In batch learning, Rademacher complexity measures a model's ability to fit random noise. Nicolò Cesa-Bianchi and Gábor Lugosi first bridged this concept with online learning in On prediction of individual sequences, showing that "minimax regret"—the best possible performance against a worst-case adversary—is tied to the geometric complexity of the expert class.

The modern refinement of this idea is Sequential Rademacher Complexity. As defined in Online Learning via Sequential Complexities, this metric evaluates the expected supremum of a Rademacher process over a data tree. Instead of assigning random signs to a fixed set of points, we assign them to the nodes of the tree. This measures the capacity of a function class to fit random fluctuations across all possible adaptive histories.

This complexity measure provides a tight upper bound on minimax regret. It tells us that if the sequential Rademacher complexity of a class grows sublinearly with time, the class is learnable online.

Combinatorial Dimensions of Sequences

Just as the VC-dimension characterizes batch learnability, sequential counterparts define the limits of online learning.

  1. Littlestone Dimension: Originally used for binary classification, this measures the depth of the largest tree a class can shatter.
  2. Sequential Fat-Shattering Dimension: For real-valued functions, Alexander Rakhlin and colleagues introduced this scale-sensitive dimension in Sequential complexities and uniform martingale laws of large numbers. It quantifies the richness of a function class by its ability to shatter nodes across different paths in a tree at a specific margin.

These dimensions are not just theoretical curiosities; they provide the necessary and sufficient conditions for a "Uniform Law of Large Numbers" for martingales, extending classical probability theory to dependent, adversarial data.

Chaining and the Logarithmic Tax

To calculate these complexities for complex models like neural networks, researchers use "chaining"—a technique that decomposes the complexity of a class across different scales. In Majorizing Measures, Sequential Complexities, and Online Learning, Adam Block and Alexander Rakhlin introduced sequential majorizing measures to provide sharper bounds than standard entropy integrals.

However, sequential learning comes with an inherent "tax." In On Contraction of Sequential and Offset Rademacher Complexities, the authors prove that while the Ledoux–Talagrand contraction lemma (which allows us to ignore Lipschitz compositions in batch learning) still holds, it incurs a logarithmic tax. This polylogarithmic factor in the sample size is fundamentally unavoidable in the sequential setting, reflecting the increased difficulty of generalizing when data is revealed adaptively.

Applications Across the Field

This framework has unified several disparate areas of machine learning:

By shifting the focus from specific algorithms to the sequential statistical complexity of the problem itself, this research direction provides a universal language for understanding learning in dynamic, adversarial, and non-i.i.d. environments.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_rademacher_complexity_for_onl_bed7709f,
  title = {Sequential Rademacher Complexity for Online Learnability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-rademacher-complexity-for-online-learnability/rdr_bed7709fe6db472bb8d67279d48d89d1},
  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_sequential_rademacher_complexity_for_onl_bed7709f_v1,
  title = {Sequential Rademacher Complexity for Online Learnability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-rademacher-complexity-for-online-learnability/rdr_bed7709fe6db472bb8d67279d48d89d1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}