Optimistic Rates for Multiclass PAC Learning

Sintesi Tecnica: Tassi Ottimistici per l'Apprendimento PAC Multiclasse

Enunciato del Problema
Il saggio affronta la difficoltà statistica della classificazione multiclasse nel framework dell'apprendimento PAC. I limiti esistenti nel caso peggiore (worst-case) per l'apprendimento multiclasse dipendono da due parametri di capacità: la dimensione di Natarajan ($d_N$) e la dimensione di Daniely–Shalev-Shwartz ($d_{DS}$). Sebbene i tassi ottimali siano noti ai due estremi — apprendimento realizzabile ($L^\star = 0$) e apprendimento agnostico completo ($L^\star$ costante) — il comportamento intermedio rimane irrisolto. Nello specifico, gli attuali limiti agnostici nel caso peggiore scalano come $\sqrt{d_N/n} + d_{DS}/n$, fallendo nel riflettere il fatto che se il miglior classificatore è quasi corretto (piccolo rischio dell'oracolo $L^\star$), il problema dell'apprendimento dovrebbe essere più semplice. L'obiettivo è stabilire un "tasso ottimistico" in cui il termine di fluttuazione scala con $L^\star$, interpolando tra il tasso veloce del realizzabile e il tasso lento dell'agnostico.

Metodologia
Gli autori propongono un apprenditore, RMC (Relative Menu Compression), che raggiunge questa interpolazione senza la conoscenza preventiva di $L^\star$ o del livello di confidenza $\delta$. L'architettura della dimostrazione si basa su una strategia di divisione del campione in tre blocchi, adattando la riduzione "cover–menu–compression" da [CEH+26] ma introducendo una nuova interfaccia statistica.

1. Blocco 1 (Cover): Un compressore deterministico riduce la classe di ipotesi infinita a una famiglia finita $\hat{\mathcal{F}}$ di dimensione circa $d_{DS} \log^2 n$. Questo passaggio assicura che per ogni comparatore $h$, esista un "testimone canonico" in $\hat{\mathcal{F}}$ che concorda con $h$ nella regione in cui $h$ è corretto.
2. Blocco 2 (Menu): Un algoritmo di pesi moltiplicativi apprende un "menu" $\mu$ (un insieme di etichette candidate per ogni input) che copre le etichette del testimone canonico sulla regione corretta dell'oracolo. Questo passaggio controlla la probabilità che un'etichetta corretta manchi dal menu, un modo di fallimento governato da $d_{DS}$.
3. Blocco 3 (Compression): Una volta fissato il menu, il problema si riduce alla classificazione binaria all'interno del menu. L'apprenditore applica una regola di compressione che domina empiricamente un comparatore fisso.

L'innovazione tecnica centrale è un Teorema di Compressione Relativa Orientato al Comparatore (Teorema 3.3). A differenza dei classici limiti di compressione che confrontano il rischio di popolazione dell'apprenditore con il suo rischio empirico (generando una fluttuazione $\sqrt{k/n}$), questo teorema confronta il rischio di popolazione dell'apprenditore direttamente con il rischio di popolazione $L(h)$ di un comparatore fisso. Stabilisce che se una regola di compressione di dimensione $k$ non ha una perdita empirica maggiore di $h$, allora:
$$L(A(S)) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
Crucialmente, il coefficiente di $L(h)$ è esattamente 1, e la fluttuazione scala con $\sqrt{L(h)}$. Ciò è ottenuto utilizzando descrizioni ordinate con indici ripetuti e disuguaglianze di Bernstein a lato singolo, senza richiedere assunzioni di stabilità.

Contributi Chiave

1. Tasso Ottimistico Multiclasse Ottimale: Il saggio dimostra che per una classe con dimensione di Natarajan $d_N$ e dimensione DS $d_{DS}$, l'eccesso di rischio ottimale è:
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   Questo risultato è uniforme rispetto alla dimensione dell'alfabeto. Il termine $d_N$ si localizza al rischio dell'oracolo $L^\star$, mentre il termine $d_{DS}$ rimane un residuo di ordine realizzabile.
2. Limite Inferiore Coerente (Matching Lower Bound): Gli autori costruiscono una singola classe di ipotesi e una singola distribuzione per qualsiasi $L^\star$ fisso che costringa simultaneamente entrambi i termini del limite superiore. Ciò conferma che la separazione dei ruoli — $d_{DS}$ che controlla la copertura delle etichette e $d_N$ che controlla le fluttuazioni all'interno del menu — è intrinseca al problema, non un artefatto dell'analisi.
3. Estensione all'Apprendimento di Liste (List Learning): L'architettura è estesa all'apprendimento di liste (output di $r$ etichette). Gli autori derivano tassi ottimistici contro il miglior $r$-tupla di ipotesi, localizzando la fluttuazione al rischio della lista dell'oracolo. Ciò risolve un'aspettativa di [Pab26] riguardante la necessità di un termine di fluttuazione di Natarajan $r$-ario e migliora il noto limite inferiore del realizzabile rimuovendo un fattore $r$.
4. Verifica Formale: I teoremi principali e le loro dimostrazioni sono stati verificati tramite macchina in Lean 4, garantendo la correttezza delle costanti e delle dipendenze logiche.

Risultati

• Limite Superiore (Teorema 3.1): L'apprenditore RMC raggiunge il tasso $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$ con probabilità $1-\delta$. L'apprenditore è privo di parametri (indipendente da $L^\star$ e $\delta$).
• Limite Inferiore (Teorema 4.1): Per ogni $1 \leq d_N \leq d_{DS}$, esiste una classe e una distribuzione dove qualsiasi apprenditore incorre in un eccesso di rischio atteso di almeno $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$. La costruzione utilizza un prodotto di un cubo di Natarajan rumoroso e un pseudo-cubo (derivato da [BCD+22]) per separare i due termini.
• Apprendimento di Liste (Teoremi 5.1 & 5.2): Il tasso ottimistico si estende agli apprenditori di liste contro il miglior $r$-tupla, con un limite inferiore che conferma la necessità del termine di fluttuazione. Inoltre, un nuovo limite inferiore per l'apprendimento di liste realizzabile rimuove il fattore $r$ presente nei risultati precedenti [HMZ24].

Significatività e Rivendicazioni
Il saggio sostiene di aver colmato il divario tra i noti tassi del realizzabile e dell'agnostico per il caso multiclasse, fornendo il primo tasso ottimistico, indipendente dalla distribuzione e privo di parametri, per l'apprendimento multiclasse.

• Unificazione Teorica: Dimostra che il principio di confronto "coefficiente-uno", precedentemente stabilito per la classificazione binaria tramite la geometria del cubo booleano [MQZ26], può essere elevato al setting multiclasse disaccoppiando la geometria delle etichette (gestita dal menu/cover) dalla fluttuazione stocastica (gestita dalla compressione relativa).
• Separazione Intrinseca: Il limite inferiore certifica che i due parametri di capacità ($d_N$ e $d_{DS}$) giocano ruoli distinti e non intercambiabili: $d_{DS}$ determina se le etichette corrette sono visibili (copertura), mentre $d_N$ determina la difficoltà di selezione tra le etichette visibili (fluttuazione).
• Limitazioni: Gli autori notano che i fattori logaritmici nel limite superiore non sono ottimizzati, e l'apprenditore è informazionale (non necessariamente efficiente dal punto di vista computazionale). I risultati assumono un alfabeto di etichette finito, sebbene il limite sia uniforme rispetto alla sua cardinalità.

Il lavoro è presentato come una risoluzione della questione dell'interpolazione nell'apprendimento multiclasse PAC, stabilendo che la difficoltà statistica dipende effettivamente dal livello di realizzabilità e fornendo il tasso preciso con cui tale difficoltà degrada.