Reductions from Agnostic to Realizable Learning

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

Version 1 of 2174 papers186 conceptsfrozen 2026-10-04

In computational learning theory, we typically categorize problems into two worlds. In the realizable setting, we assume the "truth" is simple: there exists some hypothesis within our model class that perfectly labels the data. In the agnostic setting, we drop this optimism. The data might be noisy, or the true relationship might be too complex for our model to capture perfectly. Our goal shifts from finding perfection to simply doing as well as the best possible hypothesis in our class.

For decades, these two settings were treated as distinct challenges. Realizable learning is often significantly easier to analyze and yields faster learning rates, while agnostic learning is more representative of the messy real world. However, a growing body of research is proving that these two worlds are more deeply connected than they appear.

The Gap Between Ideal and Reality

The difficulty of agnostic learning stems from the fact that the learner must compete with the best hypothesis under arbitrary noise. David Lopez-Paz and Ilya O. Tolstikhin demonstrated that even in transductive settings—where the learner sees the test points ahead of time—unlabeled data provides no inherent shortcut to overcoming this agnostic hurdle without additional assumptions.

This gap is quantified by minimax lower bounds. Aryeh Kontorovich and Iosif Pinelis established exact limits for agnostic PAC learning, showing that the expected excess risk decays much more slowly than in the realizable case. While a realizable learner might see its error drop at a rate of $1/n$, an agnostic learner is often stuck with $1/\sqrt{n}$.

The Blackbox Reduction

The most significant theoretical bridge between these settings was recently proposed by Daniel Kane, Shachar Lovett, and their colleagues in Realizable Learning is All You Need. They introduced a "blackbox" reduction showing that if a concept class is learnable in the realizable setting, it is fundamentally learnable in the agnostic setting as well.

The intuition behind this works through non-uniform covers. Imagine the space of all possible ways to label your data. In the realizable setting, you only care about the labels that your hypothesis class can actually produce. In the agnostic setting, the "noisy" labels could be anything. The researchers showed that you can "cover" the complex agnostic space using a collection of realizable problems. By solving these realizable sub-problems, you can effectively navigate the agnostic space. This result unifies disparate findings across robust, private, and fair learning, suggesting that the "hardness" of noise is often just a reflection of the underlying complexity of the clean concept class.

Domain-Specific Extensions

This "realizable-to-agnostic" transition is a recurring theme across several specialized subfields:

  • Boosting: Traditional boosting assumes a "weak learner" can always do slightly better than random on any distribution (a realizable assumption). Nataly Brukhim, Shay Moran, and others extended this to the agnostic online setting by reducing boosting to regret minimization in online convex optimization.
  • Differential Privacy: Many private learning algorithms, such as those for halfspaces developed by Haim Kaplan and Uri Stemmer, were initially built for the realizable case to achieve better sample complexity. Translating these to agnostic settings remains a primary hurdle for making private ML practical for noisy datasets.
  • Strategic and Adversarial ML: In strategic classification, where agents manipulate their data to get a better outcome, Han Shao and Avrim Blum have noted that most current guarantees rely on the existence of a perfectly robust classifier (realizability). Moving to agnostic settings is essential for handling scenarios where no model is perfectly immune to manipulation.

Open Frontiers in Distribution Learning

While the equivalence between realizable and agnostic learning is becoming clear for function classification, it remains an open question in other areas. Shai Ben-David and Gautam Kamath have pointed out that in probability distribution learning, the transition from a perfect model to an approximate one introduces unique theoretical challenges that the standard PAC framework doesn't fully capture.

Similarly, in multiclass learning, Steve Hanneke and Shay Moran have characterized "universal rates" that describe how fast models learn. While they have established a trichotomy of rates for the realizable case, extending these precise "speed limits" to the agnostic case—where model mismatch is the norm—is the next major step in the field's evolution.

Papers in this version

Showing 60 of 174 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_realizability_assumption_37d166c2,
  title = {realizability assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/realizability-assumption/rdr_37d166c2fbb94712a4599d430aed3a04},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_reductions_from_agnostic_to_realizable_l_37d166c2_v1,
  title = {Reductions from Agnostic to Realizable Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/reductions-from-agnostic-to-realizable-learning/rdr_37d166c2fbb94712a4599d430aed3a04/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}