A Theory of Universal Agnostic Learning

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.