# A Theory of Universal Agnostic Learning

arXiv: https://arxiv.org/abs/2601.20961 · HTML: https://mlsanity.com/paper/2601.20961/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2026.

## Built on by (most cited first, 1 of 1)

- [Reconciling Universal and Uniform Learning with Q-Aggregation](https://mlsanity.com/paper/2609.05041/) (2026)

## Abstract (arXiv)

We provide a complete theory of optimal universal rates for binary classification in the agnostic setting. This extends the realizable-case theory of Bousquet, Hanneke, Moran, van Handel, and Yehudayoff (2021) by removing the realizability assumption on the distribution. We identify a fundamental tetrachotomy of optimal rates: for every concept class, the optimal universal rate of convergence of the excess error rate is one of e-n, e-o(n), o(n-1/2), or arbitrarily slow. We further identify simple combinatorial structures which determine which of these categories any given concept class falls into.