Discrete Hierarchies of Universal Learning Rates

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 227 papers43 conceptsfrozen 2026-10-04

In classical statistical learning theory, we often ask: "How many samples do I need to learn this task?" The answer is usually a worst-case bound, like $1/\epsilon^2$. However, practitioners know that some distributions are "easy" and others are "hard." A recent surge of research has revealed that the speed of learning is not a continuous spectrum of possibilities. Instead, learning rates fall into a discrete hierarchy of "speed limits"—often referred to as trichotomies, tetrachotomies, or pentachotomies.

The End of the Continuous Spectrum

For decades, it was unclear whether the error of a learning algorithm could decay at any arbitrary rate (like $1/n^{0.73}$) or if it was constrained to specific regimes. Work by Steve Hanneke and Shay Moran has fundamentally changed this view.

In Universal Rates for Multiclass Learning, the authors prove a trichotomy: for any hypothesis class, the optimal error rate is either exponential ($e^{-n}$), near-linear ($1/n$), or can be arbitrarily slow. There is no middle ground. This suggests that the "difficulty" of a concept class is quantized. If a class is simple enough to avoid "arbitrarily slow" learning, it immediately jumps to a linear rate. If it is even simpler, it jumps to exponential.

Combinatorial Dimensions as Speed Limits

Why does this quantization happen? The answer lies in the combinatorial "DNA" of the hypothesis class. Just as the VC dimension determines if a class is learnable, newer, more refined dimensions determine how fast it is learnable.

  • The VCL Dimension: In Fine-Grained Distribution-Dependent Learning Curves, Olivier Bousquet, Steve Hanneke, and colleagues introduce the Vapnik–Chervonenkis–Littlestone (VCL) dimension. They show that a learning curve can be decomposed into a linear component (the intrinsic complexity of the class) and an exponential component (the specific distribution).
  • The DSL Tree: To handle multiclass problems with infinite labels, Moran and Hanneke developed the DSL tree. The presence or absence of these infinite tree structures within a hypothesis class acts as a toggle switch, moving the learning rate from one discrete regime to another.

Transduction and the Power of Knowing the Future

One of the most striking examples of these discrete regimes appears in transductive online learning, where the learner knows the sequence of future data points but not their labels.

In A Trichotomy for Transductive Online Learning, Steve Hanneke, Shay Moran, and Jonathan Shafer show that knowing the future sequence collapses the complexity of the problem. The number of mistakes a learner makes can only grow at three specific rates: constant, logarithmic, or linear.

This was extended to multiclass settings by Steve Hanneke, Vinod Raman, and others in Multiclass Transductive Online Learning. They introduced the Level-constrained Littlestone (LCLL) and Branching dimensions to prove that even with an infinite number of labels, the mistake rate remains trapped in this three-tiered hierarchy.

Expanding the Taxonomy: Tetrachotomies and Beyond

As researchers look at more specific learning paradigms, the "staircase" of learning rates gains more steps:

  1. Empirical Risk Minimization (ERM): In Universal Rates of Empirical Risk Minimization, Steve Hanneke and Mingyue Xu identify a tetrachotomy. ERM—the strategy of simply picking any consistent hypothesis—can be slightly slower than the theoretical optimum, introducing a fourth "log-linear" ($\log(n)/n$) regime.
  2. Active Learning: For active learning, Steve Hanneke and Amin Karbasi found another tetrachotomy in Universal Rates for Active Learning, governed by a structure called the Star Tree.
  3. Noisy Learning: When data is corrupted by Massart noise, the hierarchy expands even further. Ariel Avital and Klim Efremenko describe a pentachotomy (five rates) in Learning Partial Concept Classes and Universal Rates Under Massart Noise.

Why It Matters: The Limits of Induction

This research direction isn't just about categorizing rates; it's about the fundamental possibility of science. Zhou Lu uses these frameworks in When Is Inductive Inference Possible? to answer a philosophical question: when can we learn a "law of nature" with only a finite number of mistakes?

The answer is tied to the same discrete structures: induction is possible if and only if the hypothesis class is a countable union of classes with finite Littlestone dimension. By identifying these discrete "jumps" in complexity, researchers are mapping the boundary between what can be known efficiently and what remains forever beyond the reach of finite observation.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 18 papers
  2. Version 1 · 2026-10-04 · 27 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_discrete_learning_rate_regimes_49e2bb10,
  title = {discrete learning rate regimes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-learning-rate-regimes/rdr_49e2bb103ae441be95a743ecf88621ac},
  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_discrete_hierarchies_of_universal_learni_49e2bb10_v1,
  title = {Discrete Hierarchies of Universal Learning Rates},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-hierarchies-of-universal-learning-rates/rdr_49e2bb103ae441be95a743ecf88621ac/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}