Optimistic Rates for Multiclass PAC Learning

Resumen Técnico: Tasas Optimistas para el Aprendizaje PAC Multiclase

Planteamiento del Problema
El artículo aborda la dificultad estadística de la clasificación multiclase en el marco del aprendizaje PAC. Los límites actuales de caso peor (worst-case) para el aprendizaje multiclase dependen de dos parámetros de capacidad: la dimensión de Natarjan ($d_N$) y la dimensión de Daniely–Shalev-Shwartz ($d_{DS}$). Aunque se conocen las tasas óptimas en los dos extremos —aprendizaje realizable ($L^\star = 0$) y aprendizaje agnóstico total ($L^\star$ constante)—, el comportamiento intermedio sigue sin resolverse. Específicamente, los límites agnósticos de caso peor actuales escalan como $\sqrt{d_N/n} + d_{DS}/n$, lo que no refleja el hecho de que si el mejor clasificador es casi correcto (riesgo de oráculo $L^\star$ pequeño), el problema de aprendizaje debería ser más fácil. El objetivo es establecer una "tasa optimista" donde el término de fluctuación escale con $L^\star$, interpolando entre la tasa rápida realizable y la tasa lenta agnóstica.

Metodología
Los autores proponen un aprendiz, RMC (Compresión de Menú Relativo), que logra esta interpolación sin conocimiento previo de $L^\star$ o del nivel de confianza $\delta$. La arquitectura de la prueba se basa en una estrategia de división de muestras en tres bloques, adaptando la reducción "cover–menu–compression" de [CEH+26] pero introduciendo una interfaz estadística novedosa.

1. Bloque 1 (Cover/Cobertura): Un compresor determinista reduce la clase de hipótesis infinita a una familia finita $\hat{\mathcal{F}}$ de tamaño aproximadamente $d_{DS} \log^2 n$. Este paso asegura que, para cualquier comparador $h$, exista un "testigo canónico" en $\hat{\mathcal{F}}$ que concuerde con $h$ en la región donde $h$ es correcto.
2. Bloque 2 (Menu/Menú): Un algoritmo de pesos multiplicativos aprende un "menú" $\mu$ (un conjunto de etiquetas candidatas para cada entrada) que cubre las etiquetas del testigo canónico en la región correcta del oráculo. Este paso controla la probabilidad de que falte una etiqueta correcta en el menú, un modo de fallo gobernado por $d_{DS}$.
3. Bloque 3 (Compression/Compresión): Una vez fijado el menú, el problema se reduce a la clasificación binaria dentro del menú. El aprendiz aplica una regla de compresión que domina empíricamente a un comparador fijo.

La innovación técnica central es un Teorema de Compresión Relativa Orientado al Comparador (Teorema 3.3). A diferencia de los límites de compresión estándar que comparan el riesgo poblacional del aprendiz con su riesgo empírico (produciendo una fluctuación de $\sqrt{k/n}$), este teorema compara el riesgo poblacional del aprendiz directamente con el riesgo poblacional $L(h)$ de un comparador fijo $h$. Establece que si una regla de compresión de tamaño $k$ no tiene un pérdida empírica mayor que $h$, entonces:
$$L(A(S)) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
Crucialmente, el coeficiente de $L(h)$ es exactamente 1, y la fluctuación escala con $\sqrt{L(h)}$. Esto se logra mediante descripciones ordenadas con índices repetidos e desigualdades de Bernstein de un solo lado, sin requerir supuestos de estabilidad.

Contribuciones Clave

1. Tasa Optimista Multiclase Óptima: El artículo demuestra que para una clase con dimensión de Natarajan $d_N$ y dimensión de DS $d_{DS}$, el exceso de riesgo óptimo es:
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   Este resultado es uniforme en el tamaño del alfabeto. El término $d_N$ se localiza en el riesgo del oráculo $L^\star$, mientras que el término $d_{DS}$ permanece como un remanente de orden realizable.
2. Límite Inferior Coincidente (Matching Lower Bound): Los autores construyen una clase de hipótesis única y una distribución única para cualquier $L^\star$ fijo que fuerza ambos términos del límite superior simultáneamente. Esto confirma que la separación de roles —$d_{DS}$ controlando la cobertura de etiquetas y $d_N$ controlando las fluctuaciones dentro del menú— es intrínseca al problema, no un artefacto del análisis.
3. Extensión al Aprendizaje de Listas (List Learning): La arquitectura se extiende al aprendizaje de listas (que devuelve $r$ etiquetas). Los autores derivan tasas optimistas contra el mejor $r$-tupla de hipótesis, localizando la fluctuación en el riesgo de lista del oráculo y mejorando el límite inferior de aprendizaje de listas realizable conocido al eliminar un factor de $r$.
4. Verificación Formal: Los teoremas principales y sus pruebas han sido verificados mediante máquinas en Lean 4, asegurando la corrección de las constantes y las dependencias lógicas.

Resultos

• Límite Superior (Teorema 3.1): El aprendiz RMC logra la tasa $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$ con probabilidad $1-\delta$. El aprendiz no requiere parámetros (es independiente de $L^\star$ y $\delta$).
• Límite Inferior (Teorema 4.1): Para cualquier $1 \leq d_N \leq d_{DS}$, existe una clase y una distribución donde cualquier aprendiz incurre en un exceso de riesgo esperado de al menos $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$. La construcción utiliza un producto de un cubo de Natarajan ruidoso y un pseudo-cubo (derivado de [BCD+22]) para separar las dos dimensiones.
• Aprendizaje de Listas (Teoremas 5.1 y 5.2): La tasa optimista se extiende a aprendices de listas contra el mejor $r$-tupla, con un límite inferior que confirma la necesidad del término de fluctuación. Además, un nuevo límite inferior para el aprendizaje de listas realizable elimina el factor $r$ presente en resultados previos [HMZ24].

Significancia y Reivindicaciones
El artículo afirma cerrar la brecha entre las tasas realizables y agnósticas conocidas para el aprendizaje multiclase, proporcionando la primera tasa optimista libre de distribución y de parámetros para el aprendizaje multiclase.

• Unificación Teórica: Demuestra que el principio de comparación de "coeficiente uno", establecido previamente para la clasificación binaria mediante la geometría del cubo Booleano [MQZ26], puede elevarse a entornos multiclase desacoplando la geometría de las etiquetas (gestionada por el menú/cobertura) de la fluctuación estocástica (gestionada por la compresión relativa).
• Separación Intrínseca: El límite inferior certifica que los dos parámetros de capacidad ($d_N$ y $d_{DS}$) juegan roles distintos e intercambiables: $d_{DS}$ dicta si las etiquetas correctas son visibles (cobertura), mientras que $d_N$ dicta la dificultad de seleccionar entre las etiquetas visibles (fluctuación).
• Limitaciones: Los autores señalan que los factores logarítmicos en el límite superior no están optimizados, y que el aprendiz es de carácter informacional (no necesariamente eficiente computacionalmente). Los resultados asumen un alfabeto de etiquetas finito, aunque el límite es uniforme en su cardinalidad.

El trabajo se presenta como una resolución a la cuestión de la interpolación en el aprendizaje PAC multiclase, estableciendo que la dificultad estadística depende, de hecho, del nivel de realizabilidad, y proporcionando la tasa precisa a la que esta dificultad se degrada.