Majority-of-Three is Optimal

Technische Samenvatting: Meerderheid-van-Drie is Optimaal

Probleemstelling
Het artikel behandelt het centrale probleem van het bepalen van de optimale steekproefcomplexiteit voor PAC-leren in de realiseerbare setting. Hoewel het bestaan van optimale leerders werd vastgesteld door Hanneke [Han16] (voortbouwend op Simon [Sim15]), zijn de resulterende algoritmen en hun probabilistische analyses complex. Een specifieke, elementaire kandidaat voor een optimale leerling is de "meerderheid-van-drie"-regel: het splitsen van een trainingssteekproef in drie onafhankelijke blokken, het trainen van een consistente classifier op elk blok, en het uitvoeren van de meerderheidsstem. Vorig werk [AAHLZ24] bewees dat deze regel een optimale bovengrens bereikt in verwachting en een bijna-optimale PAC-bovengrens (tot een dubbel logaritmische factor, $\log \log(\min\{n/d, 1/\delta\})$). De auteurs van [AAHLZ24] vermoedden dat de meerderheid-van-drie-regel de optimale PAC-bovengrens bereikt zonder deze extra factoren. Dit artikel levert een bewijs van dat vermoeden.

Methodologie
Het bewijs vestigt een bovengrens met hoge waarschijnlijkheid op de fout van de meerderheidsstem-classifier, Maj(\hat{f}_1, \hat{f}_}_2, \hat{f}_3), waarbij elke $\hat{f}_i$ een consistente classifier is die getraind is op een onafhankelijk blok $S_i$ van grootte $m = n/3$.

1. Reductie naar Overlap-momenten:
   De fout van de meerderheidsstem treedt alleen op wanneer ten minste twee van de drie classifiers een punt $x$ foutief classificeren. Door de foutset van de $i$-de classifier aan te duiden als $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$, wordt de totale fout begrensd door de som van de paarwijze intersecties:
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   Het bewijs richt zich op het begrenzen van de $L_q$-momenten van deze intersectiekansen, specifiek $\|P(E_1 \cap E_2)\|_{L_q}$.

2. Kerntechnisch Instrument: Propositie 2.2:
   De kern van het argument is Propositie 2.2, die een moment-begrenzing biedt voor de overlap van foutsets van twee onafhankelijke steekproeven $S$ en $T$ van grootte $m$. Voor een VC-klasse $\mathcal{C}$ met dimensie $d$ en een deterministische consistente selector $A$ (waarbij $A(S) \cap S = \emptyset$), stelt de propositie:
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   Dit resultaat is analoog aan de overlap-schatting van Simon [Sim15], maar is van toepassing op onafhankelijke steekproeven in plaats van geneste steekproeven. De onafhankelijkheid is cruciaal om de dubbel logaritmische factoren te vermijden die aanwezig zijn in eerdere analyses van geneste structuren.

3. Recursieve Decompositie en Conditionele Probabiliteiten:
   Om Propositie 2.2 te bewijzen, analyseren de auteurs het $q$-de moment van de overlap door $q$ onafhankelijke testpunten $X = (X_1, \dots, X_q)$ te introduceren. Het moment wordt herschreven als $\mathbb{E}_X [p_q(X)^2]$, waarbij $p_q(X) = P(X \subseteq A(S))$.
   Met behulp van een ketenregel-decompositie wordt $p_q(X)$ uitgedrukt als een product van conditionele inclusie-probabiliteiten:
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{waarbij } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   Het bewijs rust op Lemma 3.1, een tail-bound voor deze conditionele probabiliteiten. Het toont aan dat voor een conditionele gebeurtenis $E_z$ met waarschijnlijkheid $p_z$, de kans dat de conditionele inclusie-probabiliteit $\alpha_z(X)$ een drempel $a$ overschrijdt, begrensd wordt door:
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   Deze bovengrens controleert de "zeldzaamheid" van de conditionele gebeurtenis zonder de VC-dimensie term op te blazen.

4. Recursief Argument:
   De auteurs definiëren een gewogen functionaal $M_k$ bestaande uit de gekwadrateerde conditionele probabiliteiten en een logaritmische term. Ze stellen een recursie vast: $M_k \leq \frac{960}{m} M_{k-1}$. Het itereren van deze recursie van $k=1$ tot $q$ levert de gewenste bovengrens voor het $q$-de moment op, die vervolgens wordt omgezet naar een bovengrens met hoge waarschijnlijkheid met behulp van de Markov-ongelijkheid met $q = \lceil \log(1/\delta) \rceil$.

Belangrijkste Bijdragen en Resultaten

• Optimaliteitsbewijs: Het artikel bewijst dat de meerderheid-van-drie leerling de optimale steekproefcomplexiteit bereikt in de realiseerbare PAC-setting. Specifiek, voor elke distributie $P$, doel $f^\star$, en betrouwbaarheid $\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.$$
  Dit komt overeen met de klassieke ondergrens [EHKV89] tot een universele constante.
• Vereenvoudiging van Analyse: Het bewijs vereenvoudigt de algoritmische structuur en de probabilistische analyse van eerdere optimale leerders (zoals Hanneke's [Han16] en Larsen's bagging-analyse [Lar23]). Het elimineert de noodzaak voor complexe geneste steekproefstructuren en de daaruit voortvloeiende dubbel logaritmische factoren.
• Onafhankelijkheid boven Nesting: Het werk toont aan dat het gebruik van onafhankelijke blokken (in tegenstelling tot geneste steekproeven) een schonere analyse mogelijk maakt die de $\log \log$-factoren vermijdt die voorheen als noodzakelijk werden beschouwd voor eenvoudige stemschema's.

Betekenis en Claims
De auteurs beweren dat dit resultaat het vermoeden uit [AAHLZ24] oplost met betrekking tot de optimaliteit van de meerderheid-van-drie-regel. Het artikel positioneert dit als een significante vereenvoudiging in de theorie van PAC-leren, waarbij het het "eenvoudigste stemschema" biedt dat bewezen optimaal is. Het bewijs wordt beschreven als kort en zelfstandig, gebaseerd op een nieuwe recursieve decompositie van conditionele inclusie-probabiliteiten in plaats van de meer ingewikkelde constructies van eerdere optimale leerders.

Het artikel bevat ook een appendix waarin het gebruik van Large Language Models (LLM's) om het bewijs te vereenvoudigen wordt toegelicht. De auteurs merken op dat het oorspronkelijke bewijs langer was en werd afgeleid door de eerste auteur, maar dat LLM-assistentie werd gebruikt om alternatieve argumenten te verkennen, wat leidde tot de kortere recursieve vorm die in het definitieve manuscript wordt gepresenteerd. De wiskundige claims werden geverifieerd en geschreven door de auteurs.