Neue Theorie liefert optimale Lernraten für binäre Klassifikation ohne Annahmen

Ein kürzlich veröffentlichtes arXiv‑Preprint (2601.20961v1) präsentiert die erste vollständige Theorie zu optimalen Lernraten für binäre Klassifikationsaufgaben im agnostischen Rahmen. Im Gegensatz zu früheren Arbeiten, die die Realisierbarkeit der Datenverteilung voraussetzten, gilt die neue Theorie für beliebige Verteilungen.

Die Autoren zeigen, dass jede Konzeptklasse in genau eine von vier Kategorien fällt: exponentiell schnell ($e^{-n}$), fast exponentiell ($e^{-o(n)}$), sublineare Raten ($o(n^{-1/2})$) oder beliebig langsam. Diese „Tetrachotomie“ liefert ein klares Bild darüber, wie schnell ein Lernalgorithmus im schlimmsten Fall konvergiert.

Wichtig ist, dass die Zugehörigkeit zu einer dieser Kategorien durch leicht zu identifizierende kombinatorische Strukturen bestimmt wird. Damit erhalten Forscher und Praktiker ein praktisches Werkzeug, um die theoretische Leistungsgrenze einer gegebenen Konzeptklasse zu bestimmen, ohne auf komplexe Simulationen zurückgreifen zu müssen.