Optimistic Rates for Multiclass PAC Learning

Technische Samenvatting: Optimistische Snelheden voor Multiclass PAC-leren

Probleemstelling
Het artikel behandelt de statistische moeilijkheid van multiclass classificatie binnen het PAC-leerframework. Bestaande worst-case grenzen voor multiclass leren zijn afhankelijk van twee capaciteitsparameters: de Natarajan-dimensie ($d_N$) en de Daniely–Shalev-Shwartz (DS) dimensie ($d_{DS}$). Terwijl de optimale snelheden bekend zijn in de twee extremen—realistisch leren ($L^\star = 0$) en volledig agnostisch leren ($L^\star$ constant)—blijft het gedrag daartussen onopgelost. Specifiek schalen de huidige worst-case agnostische grenzen als $\sqrt{d_N/n} + d_{DS}/n$, wat geen rekening houdt met het feit dat als de beste classifier bijna correct is (kleine oracle-risico $L^\star$), het leerprobleem gemakkelijker zou moeten zijn. Het doel is om een "optimistische snelheid" vast te stellen waarbij de fluctuatieterm schaalt met $L^\star$, wat interpolaat tussen de snelle realistische snelheid en de trage agnostische snelheid.

Methodologie
De auteurs stellen een leerder voor, RMC (Relative Menu Compression), die deze interpolatie bereikt zonder voorafgaande kennis van $L^\star$ of het betrouwbaarheidsniveau $\delta$. De bewijsarchitectuur steunt op een drie-blok sample-splitting strategie, waarbij de "cover–menu–compression" reductie van [CEH+26] wordt aangepast maar een nieuwe statistische interface introduceert.

1. Blok 1 (Cover): Een deterministische compressor reduceert de oneindige hypotheseklasse tot een eindelijke familie $\hat{\mathcal{F}}$ van grootte ongeveer $d_{DS} \log^2 n$. Deze stap zorgt ervoor dat voor elke comparator $h$, er een "canonieke getuige" in $\hat{\mathcal{F}}$ bestaat die overeenkomt met $h$ op de regio waar $h$ correct is.
2. Blok 2 (Menu): Een multiplicative-weights algoritme leert een "menu" $\mu$ (een verzameling kandidaat-labels voor elke input) dat de labels van de canonieke getuige dekt op de correcte regio van de oracle. Deze stap controleert de waarschijnlijkheid dat een correct label ontbreekt in het menu, een foutmodus die wordt beheerst door $d_{DS}$.
3. Blok 3 (Compression): Zodra het menu is vastgesteld, reduceert het probleem zich tot binaire classificatie binnen het menu. De leerder past een compressieregel toe die empirisch domineert ten opzichte van een vaste comparator.

De kern van de technische innovatie is een Comparator-Facing Relative Compression Theorem (Theorem 3.3). In tegenstelling tot standaard compressie-grenzen die het populatierisico van de leerder vergelijken met zijn empirische risico (wat een $\sqrt{k/n}$ fluctuatie oplevert), vergelijkt dit theorem het populatierisico van de leerder direct met het populatierisico $L(h)$ van een vaste comparator. Het stelt vast dat als een compressieregel van grootte $k$ geen groter empirisch verlies heeft dan $h$, dan:
$$L(A(S)) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
Cruciaal is dat de coëfficiënt van $L(h)$ exact 1 is, en de fluctuatie schaalt met $\sqrt{L(h)}$. Dit wordt bereikt met geordende beschrijvingen met herhaalde indices en one-sided Bernstein-ongelijkheden, zonder dat stabiliteitsaannames vereist zijn.

Belangrijkste Bijdragen

1. Optimale Multiclass Optimistische Snelheid: Het artikel bewijst dat voor een klasse met Natarajan-dimensie $d_N$ en DS-dimensie $d_{DS}$, de optimale excessieve risico is:
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   Dit resultaat is uniform in de alfabetgrootte. De $d_N$-term lokaliseert naar het oracle-risico $L^\star$, terwijl de $d_{DS}$-term een realistische-orde restant blijft.
2. Matching Lower Bound: De auteurs construeren een enkele hypotheseklasse en een enkele distributie voor elk vaste $L^\star$ die beide termen van de bovenstaande grens simultaan afdwingen. Dit bevestigt dat de scheiding van rollen—waarbij $d_{DS}$ de labeldekking controleert en $d_N$ de fluctuaties binnen het menu controleert—intrinsiek is aan het probleem, en niet een artefact van de analyse.
3. Extensie naar List Learning: De architectuur wordt uitgebreid naar list learning (het outputten van $r$ labels). De auteurs leiden optimistische snelheden af tegen de beste $r$-tuple van hypothesen, waarbij de fluctuatie lokaliseert bij het oracle list-risico. Dit lost een verwachting van [Pab26] op over de noodzaak van een $r$-aire Natarajan fluctuatieterm en verbetert de bekende realistische list lower bound door een factor $r$ te verwijderen.
4. Formele Verificatie: De hoofdtheorema's en hun bewijzen zijn machine-gecontroleerd in Lean 4, wat de correctheid van constanten en logische afhankelijkheden garandeert.

Resultaten

• Upper Bound (Theorem 3.1): De RMC-leerder bereikt de snelheid $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$ met waarschijnlijkheid $1-\delta$. De leerder is parameter-vrij (onafhankelijk van $L^\star$ en $\delta$).
• Lower Bound (Theorem 4.1): Voor elke $1 \leq d_N \leq d_{DS}$ bestaat er een klasse en distributie waarbij elke leerder een verwacht excessief risico oploopt van minstens $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$. De constructie gebruikt een product van een ruisige Natarajan-kubus en een pseudo-kubus (afgeleid van [BCD+22]) om de twee dimensies te scheiden.
• List Learning (Theorema 5.1 & 5.2): De optimistische snelheid breidt zich uit naar list learners tegen de beste $r$-tuple, met een lower bound die de noodzaak van de fluctuatieterm bevestigt. Daarnaast biedt een nieuwe lower bound voor realistische list learning een factor $r$ die aanwezig was in eerdere resultaten [HMZ24] weg.

Betekenis en Claims
Het artikel claimt de kloof te dichten tussen de bekende realistische en agnostische multiclass snelheden, en biedt de eerste distributie-vrije, parameter-vrije optimistische snelheid voor multiclass leren.

• Theoretische Unificatie: Het demonstreert dat het "coëfficiënt-één" vergelijkingsprincipe, eerder vastgesteld voor binaire classificatie via Boolean cube geometrie [MQZ26], kan worden opgetild naar multiclass settings door de label-geometrie (behandeld door de menu/cover) te ontkoppelen van de stochastische fluctuatie (behandeld door relatieve compressie).
• Intrinsieke Separatie: De lower bound certificeert dat de twee capaciteitsparameters ($d_N$ en $d_{DS}$) verschillende, niet-uitwisselbare rollen spelen: $d_{DS}$ bepaalt of correcte labels zichtbaar zijn (dekking), terwijl $d_N$ de moeilijkheid bepaalt van het selecteren tussen zichtbare labels (fluctuatie).
• Beperkingen: De auteurs merken op dat de logaritmische factoren in de upper bound niet geoptimaliseerd zijn, en de leerder is informatie-theoretisch (niet noodzakelijkerwijs computationeel efficiënt). De resultaten gaan uit van een eindig label-alfabet, hoewel de grens uniform is in de cardinaliteit ervan.

Het werk wordt gepresenteerd als een oplossing voor de interpolatievraag in multiclass PAC-leren, waarbij wordt vastgesteld dat de statistische moeilijkheid inderdaad afhangt van het niveau van realisme, en biedt de precieze snelheid waarmee deze moeilijkheid degradeert.