Optimistic Rates for Multiclass PAC Learning

Technisches Resümee: Optimistische Raten für Multiclass-PAC-Lernen

Problemstellung
Die Arbeit befasst sich mit der statistischen Schwierigkeit der Multiclass-Klassifizierung im Rahmen des PAC-Lernens. Bestehende Worst-Case-Schranken für das Multiclass-Lernen hängen von zwei Kapazitätsparametern ab: der Natarajan-Dimension ($d_N$) und der Daniely–Shalev-Shwartz (DS)-Dimension ($d_{DS}$). Während die optimalen Raten an den beiden Extremen – realisierbares Lernen ($L^\star = 0$) und voll-agnostisches Lernen ($L^\star$ konstant) – bekannt sind, bleibt das Verhalten dazwischen ungeklärt. Speziell skalieren aktuelle Worst-Case-agnostische Schranken als $\sqrt{d_N/n} + d_{DS}/n$, was nicht widerspiegelt, dass das Lernproblem einfacher sein sollte, wenn der beste Klassifikator nahezu korrekt ist (kleines Oracle-Risiko $L^\star$). Das Ziel ist es, eine „optimistische Rate“ zu etablieren, bei der der Fluktuationsterm mit $L^\star$ skaliert und so zwischen der schnellen realisierbaren Rate und der langsamen agnostischen Rate interpoliert.

Methodik
Die Autoren schlagen einen Lerner vor, RMC (Relative Menu Compression), der diese Interpolation ohne Vorwissen über $L^\star$ oder das Konfidenzniveau $\delta$ erreicht. Die Architektur des Beweises stützt sich auf eine Drei-Block-Stichproben-Aufteilung, welche die „Cover–Menu–Compression“-Reduktion aus [CEH+26] adaptiert, jedoch eine neuartige statistische Schnittstelle einführt.

1. Block 1 (Cover): Ein deterministischer Kompressor reduziert die unendliche Hypothesenklasse auf eine endliche Familie $\hat{\mathcal{F}}$ der Größe etwa $d_{DS} \log^2 n$. Dieser Schritt stellt sicher, dass für jeden Komparator $h$ ein „kanonischer Zeuge“ in $\hat{\mathcal{F}}$ existiert, der mit $h$ in dem Bereich übereinstimmt, in dem $h$ korrekt ist.
2. Block 2 (Menu): Ein Multiplicative-Weights-Algorithmus lernt ein „Menü“ $\mu$ (eine Menge potenzieller Labels für jeden Input), das die Labels des kanonischen Zeugen auf dem korrekten Bereich des Oracles abdeckt. Dieser Schritt kontrolliert die Wahrscheinlichkeit, dass ein korrektes Label im Menü fehlt, ein Ausfallmodus, der durch $d_{DS}$ gesteuert wird.
3. Block 3 (Compression): Sobald das Menü fixiert ist, reduziert sich das Problem auf die binäre Klassifizierung innerhalb des Menüs. Der Lerner wendet eine Kompressionsregel an, die einen festen Komparator empirisch dominiert.

Die zentrale technische Innovation ist ein Comparator-Facing Relative Compression Theorem (Theorem 3.3). Im Gegensatz zu Standard-Kompressionsschranken, die das Populationsrisiko eines Lerners mit seinem empirischen Risiko vergleichen (was eine Fluktuation von $\sqrt{k/n}$ ergibt), vergleicht dieses Theorem das Populationsrisiko des Lerners direkt mit dem Populationsrisiko eines festen Komparators $L(h)$. Es stellt fest, dass, wenn eine Kompressionsregel der Größe $k$ keinen größeren empirischen Verlust als $h$ hat, dann gilt:
$$L(A(S)) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
Entscheidend ist, dass der Koeffizient von $L(h)$ exakt 1 ist und die Fluktuation mit $\sqrt{L(h)}$ skaliert. Dies wird durch geordnete Beschreibungen mit wiederholten Indizes und einseitigen Bernstein-Ungleichungen erreicht, ohne Stabilitätsannahmen vorauszusetzen.

Wesentliche Beiträge

1. Optimale Multiclass-Optimistische Rate: Die Arbeit beweist, dass für eine Klasse mit Natarajan-Dimension $d_N$ und DS-Dimension $d_{DS}$ die optimale exzessive Risiko-Rate ist:
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   Dieses Ergebnis gilt uniform über die Alphabetgröße. Der $d_N$-Term lokalisiert sich auf das Oracle-Risiko $L^\star$, während der $d_{DS}$-Term als Realisierbarkeits-Ordnung-Rest bestehen bleibt.
2. Matching Lower Bound: Die Autoren konstruieren eine einzelne Hypothesenklasse und eine einzelne Verteilung für jedes feste $L^\star$, die beide Terme der oberen Schranke gleichzeitig erzwingt. Dies bestätigt, dass die Trennung der Rollen – $d_{DS}$ steuert die Label-Abdeckung und $d_N$ steuert die Fluktuationen innerhalb des Menüs – intrinsisch für das Problem ist und kein Artefakt der Analyse.
3. Erweiterung auf List Learning: Die Architektur wird auf das List Learning (Ausgabe von $r$ Labels) erweitert. Die Autoren leiten optimistische Raten gegen das beste $r$-Tupel von Hypothesen ab, wobei die Fluktuation am optimalen Listen-Risiko lokalisiert wird. Dies löst eine Erwartung aus [Pab26] bezüglich der Notwendigkeit eines $r$-ären Natarajan-Fluktuationsterms und verbessert die bekannte realisierbare List-Lower-Bound durch Entfernung eines Faktors von $r$.
4. Formale Verifikation: Die Haupttheoreme und ihre Beweise wurden in Lean 4 maschinell überprüft, um die Korrektheit der Konstanten und logischen Abhängigkeiten sicherzustellen.

Ergebnisse

• Obere Schranke (Theorem 3.1): Der RMC-Lerner erreicht die Rate $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$ mit einer Wahrscheinlichkeit von $1-\delta$. Der Lerner ist parameterfrei (unabhängig von $L^\star$ und $\delta$).
• Untere Schranke (Theorem 4.1): Für jede $1 \leq d_N \leq d_{DS}$ existiert eine Klasse und Verteilung, bei der jeder Lerner einen erwarteten exzessiven Risiko-Wert von mindestens $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$ erleidet. Die Konstruktion nutzt ein Produkt aus einem verrauschten Natarajan-Würfel und einem Pseudo-Würfel (abgeleitet von [BCD+22]), um die beiden Dimensionen zu trennen.
• List Learning (Theoreme 5.1 & 5.2): Die optimistische Rate erstreckt sich auf List-Lerner gegen das beste $r$-Tupel, mit einer unteren Schranke, die den Notwendigkeitsgrad des Fluktuationsterms bestätigt. Zusätzlich entfernt eine neue untere Schranke für das realisierbare List Learning den Faktor $r$, der in früheren Ergebnissen [HMZ24] vorhanden war.

Bedeutung und Behauptungen
Die Arbeit beansprucht, die Lücke zwischen den bekannten realisierbaren und agnostischen Multiclass-Raten zu schließen, indem sie die erste distributionsfreie, parameterfreie optimistische Rate für das Multiclass-Lernen bereitstellt.

• Theoretische Vereinheitlichung: Sie zeigt, dass das „Koeffizient-Eins“-Vergleichsprinzip, das zuvor für die binäre Klassifizierung via Boolescher Würfelgeometrie [MQZ26] etabliert wurde, auf Multiclass-Settings übertragen werden kann, indem die Label-Geometrie (gehandhabt durch das Menü/Cover) von der stochastischen Fluktuation (gehandhabt durch relative Kompression) entkoppelt wird.
• Intrinsische Trennung: Die untere Schranke zertifiziert, dass die beiden Kapazitätsparameter ($d_N$ und $d_{DS}$) distinkte, nicht austauschbare Rollen spielen: $d_{DS}$ bestimmt, ob korrekte Labels sichtbar sind (Coverage), während $d_N$ die Schwierigkeit bestimmt, zwischen sichtbaren Labels zu wählen (Fluktuation).
• Limitierungen: Die Autoren merken an, dass die logarithmischen Faktoren in der oberen Schranke nicht optimiert sind und der Lerner informationstheoretisch (nicht notwendigerweise computergestützt effizient) ist. Die Ergebnisse setzen ein endliches Label-Alphabet voraus, obwohl die Schranke uniform in dessen Kardinalität ist.

Die Arbeit präsentiert sich als Lösung der Interpolationsfrage im Multiclass-PAC-Lernen und etabliert, dass die statistische Schwierigkeit tatsächlich vom Grad der Realisierbarkeit abhängt, und liefert die präzise Rate, mit der diese Schwierigkeit abnimmt.