Majority-of-Three is Optimal

Resumen Técnico: La Regla de la Mayoría de Tres es Óptima

Planteamiento del Problema
El artículo aborda el problema central de determinar la complejidad de muestra óptima para el aprendizaje PAC en el entorno realizable. Si bien la existencia de aprendices óptimos fue establecida por Hanneke [Han16] (basándose en Simon [Sim15]), los algoritmos resultantes y sus análisis probabilísticos son complejos. Un candidato específico y elemental para un aprendiz óptimo es la regla de la "mayoría de tres": dividir una muestra de entrenamiento en tres bloques independientes, entrenar un clasificador consistente en cada bloque y devolver el voto de la mayoría. El trabajo previo [AAHLZ24] demostró que esta regla logra un límite óptimo en expectativa y un límite PAC casi óptimo (salvo por un factor doblemente logarítmico, $\log \log(\min\{n/d, 1/\delta\})$). Los autores de [AAHLZ24] conjeturaron que la regla de la mayoría de tres logra el límite PAC óptimo sin estos factores adicionales. Este artículo proporciona una prueba de dicha conjetura.

Metodología
La prueba establece un límite superior de alta probabilidad para el error del clasificador de la mayoría, $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$, donde cada $\hat{f}_i$ es un clasificador consistente entrenado en un bloque independiente $S_i$ de tamaño $m = n/3$.

1. Reducción a Momentos de Solapamiento:
   El error del voto de la mayoría ocurre solo cuando al menos dos de los tres clasificadores clasifican erróneamente un punto $x$. Definiendo $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$ como el conjunto de error del $i$-ésimo clasificador, el error total está acotado por la suma de las intersecciones por pares:
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   La prueba se centra en acotar los momentos $L_q$ de estas probabilidades de intersección, específicamente $\|P(E_1 \cap E_2)\|_{L_q}$.

2. Herramienta Técnica Clave: Proposición 2.2:
   El núcleo del argumento es la Proposición 2.2, que proporciona un límite de momento para el solapamiento de conjuntos de error de dos muestras independientes $S$ y $T$ de tamaño $m$. Para una clase VC con dimensión $d$ y un selector consistente determinista $A$ (donde $A(S) \cap S = \emptyset$), la proposición establece:
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   Este resultado es análogo a la estimación de solapamiento de Simon [Sim15] pero se aplica a muestras independientes en lugar de anidadas. La independencia es crucial para evitar los factores doblemente logarítmicos presentes en los análisis previos de estructuras anidadas.

3. Descomposición Recursiva y Probabilidades Condicionales:
   Para probar la Proposición 2.2, los autores analizan el $q$-ésimo momento del solapamiento introduciendo $q$ puntos de prueba independientes $X = (X_1, \dots, X_q)$. El momento se reescribe como $\mathbb{E}_X [p_q(X)^2]$, donde $p_q(X) = P(X \subseteq A(S))$.
   Utilizando una descomposición de regla de la cadena, $p_q(X)$ se expresa como un producto de probabilidades de inclusión condicionales:
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{donde } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   La prueba se basa en el Lema 3.1, un límite de cola para estas probabilidades condicionales. Este muestra que para un evento de condicionamiento $E_z$ con probabilidad $p_z$, la probabilidad de que la probabilidad de inclusión condicional $\alpha_z(X)$ exceda un umbral $a$ está acotada por:
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   Este límite controla la "rareza" del evento de condicionamiento sin inflar el término de la dimensión VC.

4. Argumento Recursivo:
   Los autores definen un funcional ponderado $M_k$ que involucra las probabilidades condicionales al cuadrado y un término logarítmico. Establecen una recursión $M_k \leq \frac{960}{m} M_{k-1}$. Iterando esta recursión desde $k=1$ hasta $q$, se obtiene el límite deseado para el $q$-ésimo momento, el cual se convierte luego en un límite de alta probabilidad utilizando la desigualdad de Markov con $q = \lceil \log(1/\delta) \rceil$.

Contribuciones Clave y Resultados

• Prueba de Optimidad: El artículo demuestra que el aprendiz de la mayoría de tres logra la complejidad de muestra óptima en el entorno PAC realizable. Específicamente, para cualquier distribución $P$, objetivo $f^\star$ y confianza $\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.$$
  Esto coincide con el límite inferior clásico [EHKV89] salvo por una constante universal.
• Simplificación del Análisis: La prueba simplifica la estructura algorítmica y el análisis probabilístico de aprendices óptimos previos (como los de Hanneke [Han16] y el análisis de bagging de Larsen [Lar23]). Elimina la necesidad de estructuras de muestras anidadas complejas y los factores doblemente logarítmicos resultantes.
• Independencia sobre Anidamiento: El trabajo demuestra que el uso de bloques independientes (en lugar de muestras anidadas) permite un análisis más limpio que evita los factores $\log \log$ que anteriormente se consideraban necesarios para esquemas de votación simples.

Significado y Reivindicaciones
Los autores afirman que este resultado resuelve la conjetura de [AAHLZ24] respecto a la optimalidad de la regla de la mayoría de tres. El artículo posiciona esto como una simplificación significativa en la teoría del aprendizaje PAC, proporcionando el "esquema de votación más simple" que es demostrablemente óptimo. La prueba se describe como corta y autónoma, basándose en una novedosa descomposición recursiva de las probabilidades de inclusión condicionales en lugar de las construcciones más intrincadas de aprendices óptimos anteriores.

El artículo también incluye un apéndice que detalla el uso de Modelos de Lenguaje Extensos (LLMs) para simplificar la prueba. Los autores señalan que la prueba inicial era más larga y fue derivada por el primer autor, pero se utilizó asistencia de LLM para explorar argumentos alternativos, lo que llevó a la forma recursiva más corta presentada en el manuscrito final. Las afirmaciones matemáticas fueron verificadas y escritas por los autores.