Majority-of-Three is Optimal

Sintesi Tecnica: La Maggioranza di Tre è Ottimale

Enunciato del Problema
Il documento affronta il problema centrale della determinazione della complessità campionaria ottimale per l'apprendimento PAC nel setting realizzabile. Sebbene l'esistenza di apprendisti ottimali sia stata stabilita da Hanneke [Han16] (costruendo sul lavoro di Simon [Sim15]), gli algoritmi risultanti e le loro analisi probabilistiche sono complessi. Un candidato specifico ed elementare per un apprendista ottimale è la regola della "maggioranza di tre": suddividere un campione di addestramento in tre blocchi indipendenti, addestrare un classificatore consistente su ciascun blocco e restituire il voto di maggioranza. Lavori precedenti [AAHLZ24] hanno dimostrato che questa regola raggiunge un limite ottimale in valore atteso e un limite PAC quasi ottimale (fino a un fattore doppio logaritmico, $\log \log(\min\{n/d, 1/\delta\})$). Gli autori di [AAHLZ24] avevano ipotizzato che la regola della maggioranza di tre raggiunga il limite PAC ottimale senza questi fattori extra. Questo articolo fornisce la prova di tale congettura.

Metodologia
La prova stabilisce un limite superiore di alta probabilità sull'errore del classificatore a maggioranza di tre, $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$, dove ogni $\hat{f}_i$ è un classificatore consistente addestrato su un blocco indipendente $S_i$ di dimensione $m = n/3$.

1. Riduzione ai Momenti di Sovrapposizione:
   L'errore della votazione a maggioranza si verifica solo quando almeno due dei tre classificatori classificano erroneamente un punto $x$. Ponendo $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$ come l'insieme di errore del $i$-esimo classificatore, l'errore totale è limitato dalla somma delle intersezioni a coppie:
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   La prova si concentra sulla limitazione dei momenti $L_q$ di queste probabilità di intersezione, specificamente $\|P(E_1 \cap E_2)\|_{L_q}$.

2. Strumento Tecnico Chiave: Proposizione 2.2:
   Il nucleo dell'argomento è la Proposizione 2.2, che fornisce un limite di momento per la sovrapposizione degli insiemi di errore da due campioni indipendenti $S$ e $T$ di dimensione $m$. Per una classe VC con dimensione $d$ e un selettore consistente deterministico $A$ (dove $A(S) \cap S = \emptyset$), la proposizione afferma:
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   Questo risultato è analogo alla stima di sovrapposizione di Simon [Sim15], ma si applica a campioni indipendenti anziché nidificati. L'indipendenza è cruciale per evitare i fattori doppio logaritmici presenti nelle analisi precedenti di strutture nidificate.

3. Decomposizione Ricorsiva e Probabilità Condizionali:
   Per dimostrare la Proposizione 2.2, gli autori analizzano il $q$-esimo momento della sovrapposizione introducendo $q$ punti di test indipendenti $X = (X_1, \dots, X_q)$. Il momento è riscritto come $\mathbb{E}_X [p_q(X)^2]$, dove $p_q(X) = P(X \subseteq A(S))$.
   Utilizzando una decomposizione tramite regola della catena, $p_q(X)$ è espressa come un prodotto di probabilità di inclusione condizionate:
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{dove } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   La prova si basa sul Lemma 3.1, un limite di coda per queste probabilità condizionate. Esso mostra che per un evento di condizionamento $E_z$ con probabilità $p_z$, la probabilità che la probabilità di inclusione condizionata $\alpha_z(X)$ superi una soglia $a$ è limitata da:
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   Questo limite controlla la "rarità" dell'evento di condizionamento senza gonfiare il termine della dimensione VC.

4. Argomento Ricorsivo:
   Gli autori definiscono un funzionale pesato $M_k$ che coinvolge le probabilità condizionate al quadrato e un termine logaritmico. Stabiliscono una ricorsione $M_k \leq \frac{960}{m} M_{k-1}$. Iterando questa ricorsione da $k=1$ a $q$, si ottiene il limite desiderato per il $q$-esimo momento, che viene poi convertito in un limite di alta probabilità usando l'ineguaglianza di Markov con $q = \lceil \log(1/\delta) \rceil$.

Contributi Chiave e Risultati

• Prova di Ottimalità: Il documento dimostra che l'apprendista maggioranza di tre raggiunge la complessità campionaria ottimale nel setting PAC realizzabile. Nello specifico, per ogni distribuzione $P$, target $f^\star$ e confidenza $\delta$:
  $$P\left( \text{err}_P(Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)) \leq 107 \frac{d + \log(1/\delta)}{n} \right) \geq 1 - \delta.$$
  Ciò corrisponde al classico limite inferiore [EHKV89] salvo una costante universale.
• Semplificazione dell'Analisi: La prova semplifica la struttura algoritmica e l'analisi probabilistica di precedenti apprendisti ottimali (come quelli di Hanneke [Han16] e l'analisi del bagging di Larsen [Lar23]). Essa elimina la necessità di complesse strutture di campioni nidificati e dei conseguenti fattori $\log \log$.
• Indipendenza rispetto alla Nidificazione: Il lavoro dimostra che l'uso di blocchi indipendenti (anziché campioni nidificati) permette un'analisi più pulita che evita i fattori $\log \log$ precedentemente ritenuti necessari per semplici schemi di voto.

Significato e Rivendicazioni
Gli autori affermano che questo risultato risolve la congettura di [AAHLZ24] riguardante l'ottimalità della regola della maggioranza di tre. Il documento posiziona questo risultato come una significativa semplificazione nella teoria dell'apprendimento PAC, fornendo lo "schema di voto più semplice" che è provabilmente ottimale. La prova è descritta come breve e autosufficiente, basata su una nuova decomposizione ricorsiva delle probabilità di inclusione condizionate piuttosto che sulle costruzioni più intricate di precedenti apprendisti ottimali.

Il documento include anche un appendice che dettaglia l'uso di Modelli Linguistici di Grandi Dimensioni (LLM) per semplificare la prova. Gli autori notano che la prova iniziale era più lunga e derivata dal primo autore, ma l'assistenza degli LLM è stata utilizzata per esplorare argomenti alternativi, portando alla forma ricorsiva più breve presentata nel manoscritto finale. Le rivendicazioni matematiche sono state verificate e scritte dagli autori.