{"id":"arxiv/2601.20961","url":"https://arxiv.org/abs/2601.20961","tags":["cs.LG","math.ST","stat.ML"],"score":0,"title":"A Theory of Universal Agnostic Learning","domain":"cs.LG","source":"arxiv","authors":["Steve Hanneke","Shay Moran"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-28","reactions":{}}