Majority-of-Three is Optimal

Résumé Technique : La règle de la majorité de trois est optimale

Énoncé du problème
Le papier traite du problème central de la détermination de la complexité d'échantillonnage optimale pour l'apprentissage PAC dans le cadre réalisable. Bien que l'existence d'apprenants optimaux ait été établie par Hanneke [Han16] (en s'appuyant sur Simon [Sim15]), les algorithmes résultants et leurs analyses probabilistes sont complexes. Un candidat élémentaire spécifique pour un apprenant optimal est la règle de la « majorité de trois » : diviser un échantillon d'entraînement en trois blocs indépendants, entraîner un classificateur cohérent sur chaque bloc, et produire le vote majoritaire. Des travaux antérieurs [AAHLZ24] ont prouvé que cette règle atteint une borne optimale en espérance et une borne PAC quasi optimale (à un facteur logarithmique doublement logarithmique près, $\log \log(\min\{n/d, 1/\delta\})$). Les auteurs de [AAHLZ24] ont conjecturé que la règle de la majorité de trois atteint la borne PAC optimale sans ces facteurs supplémentaires. Ce papier fournit une preuve de cette conjecture.

Méthodologie
La preuve établit une borne supérieure de haute probabilité sur l'erreur du classificateur de la majorité de trois, $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$, où chaque $\hat{f}_i$ est un classificateur cohérent entraîné sur un bloc indépendant $S_i$ de taille $m = n/3$.

1. Réduction aux moments de chevauchement :
   L'erreur du vote majoritaire ne se produit que lorsque au moins deux des trois classificateurs classifient mal un point $x$. En posant $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$ comme l'ensemble d'erreur du $i$-ème classificateur, l'erreur totale est bornée par la somme des intersections par paires :
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   La preuve se concentre sur la borne des moments $L_q$ de ces probabilités d'intersection, spécifiquement $\|P(E_1 \cap E_2)\|_{L_q}$.

2. Outil technique clé : Proposition 2.2 :
   Le cœur de l'argument est la Proposition 2.2, qui fournit une borne de moment pour le chevauchement des ensembles d'erreur provenant de deux échantillons indépendants $S$ et $T$ de taille $m$. Pour une classe VC $\mathcal{C}$ de dimension $d$ et un sélecteur cohérent déterministe $A$ (où $A(S) \cap S = \emptyset$), la proposition stipule :
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   Ce résultat est analogue à l'estimation de chevauchement de Simon [Sim15] mais s'applique à des échantillons indépendants plutôt qu'à des échantillons imbriqués. L'indépendance est cruciale pour éviter les facteurs doublement logarithmiques présents dans les analyses précédentes de structures imbriquées.

3. Décomposition récursive et probabilités conditionnelles :
   Pour prouver la Proposition 2.2, les auteurs analysent le $q$-ième moment du chevauchement en introduisant $q$ points de test indépendants $X = (X_1, \dots, X_q)$. Le moment est réécrit comme $\mathbb{E}_X [p_q(X)^2]$, où $p_q(X) = P(X \subseteq A(S))$.
   En utilisant une décomposition par règle de chaîne, $p_q(X)$ est exprimée comme un produit de probabilités d'inclusion conditionnelles :
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{où } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   La preuve repose sur le Lemme 3.1, une borne de queue pour ces probabilités conditionnelles. Il montre que pour un événement de conditionnement $E_z$ de probabilité $p_z$, la probabilité que la probabilité d'inclusion conditionnelle $\alpha_z(X)$ dépasse un seuil $a$ est bornée par :
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   Cette borne contrôle la « rareté » de l'événement de conditionnement sans gonfler le terme de la dimension VC.

4. Argument récursif :
   Les auteurs définissent une fonctionnelle pondérée $M_k$ impliquant les probabilités conditionnelles au carré et un terme logarithmique. Ils établissent une récursion $M_k \leq \frac{960}{m} M_{k-1}$. L'itération de cette récursion de $k=1$ à $q$ produit la borne souhaitée pour le $q$-ième moment, qui est ensuite convertie en une borne de haute probabilité en utilisant l'inégalité de Markov avec $q = \lceil \log(1/\delta) \rceil$.

Contributions clés et résultats

• Preuve d'optimalité : Le papier prouve que l'apprenant de la majorité de trois atteint la complexité d'échantillonnage optimale dans le cadre PAC réalisable. Spécifiquement, pour toute distribution $P$, cible $f^\star$ et confiance $\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.$$
  Cela correspond à la borne inférieure classique [EHKV89] à une constante universelle près.
• Simplification de l'analyse : La preuve simplifie la structure algorithmique et l'analyse probabiliste des apprenants optimaux précédents (tels que ceux de Hanneke [Han16] et l'analyse de bagging de Larsen [Lar23]). Elle élimine le besoin de structures d'échantillons imbriqués complexes et les facteurs doublement logarithmiques qui en résultent.
• Indépendance plutôt qu'imbrication : Le travail démontre que l'utilisation de blocs indépendants (par opposition à des échantillons imbriqués) permet une analyse plus propre qui évite les facteurs $\log \log$ précédemment jugés nécessaires pour les schémas de vote simples.

Signification et affirmations
Les auteurs affirment que ce résultat résout la conjecture de [AAHLZ24] concernant l'optimalité de la règle de la majorité de trois. Le papier positionne cela comme une simplification significative de la théorie de l'apprentissage PAC, fournissant le « schéma de vote le plus simple » qui est prouvé optimal. La preuve est décrite comme courte et autonome, reposant sur une nouvelle décomposition récursive des probabilités d'inclusion conditionnelles plutôt que sur les constructions plus complexes des apprenants optimaux antérieurs.

Le papier inclut également une annexe détaillant l'utilisation de modèles de langage (LLM) pour simplifier la preuve. Les auteurs notent que la preuve initiale était plus longue et dérivée par le premier auteur, mais que l'assistance des LLM a été utilisée pour explorer des arguments alternatifs, menant à la forme récursive plus courte présentée dans le manuscrit final. Les affirmations mathématiques ont été vérifiées et écrites par les auteurs.