Resumen Técnico: El Bagging Aprende Robustamente Clases VC con Complejidad de Muestra Lineal

Planteamiento del Problema

El artículo aborda el desafío fundamental de aprender predictores que sean robustos a ejemplos adversarios en el tiempo de prueba. Dado un espacio de instancias $\mathcal{X}$, un espacio de etiquetas $\mathcal{Y} = \{-1, 1\}$, y un adversario definido por un mapa de perturbación $U: \mathcal{X} \to 2^\mathcal{X}$, el objetivo es aprender un predictor $\hat{f}$ que minimice el riesgo robusto poblacional:
$$R_U(\hat{f}; P) = \mathbb{E}_{(X,Y) \sim P} \left[ \sup_{Z \in U(X)} \mathbb{1}\{\hat{f}(Z) \neq Y\} \right]$$
donde $P$ es una distribución desconocida sobre $\mathcal{X} \times \mathcal{Y}$.

El artículo se centra en la capacidad de aprendizaje de clases de funciones $\mathcal{F}$ con dimensión Vapnik-Chervonenkis (VC) finita $d$. Trabajos previos establecieron que, si bien las clases VC son aprendibles en el entorno PAC estándar, el aprendizaje adversariamente robusto enfrenta obstáculos significativos. Específicamente, Montasser, Hanneke y Srebro [2019] demostraron que:

1. El aprendizaje propio (restringir la salida a que pertenezca a $\mathcal{F}$) puede fallar incluso para clases con dimensión VC 1.
2. El aprendizaje impropio es posible, pero el mejor límite conocido de complejidad de muestra era exponencial en $d$.
3. Los algoritmos impropios existentes son computacionalmente ineficientes, requiriendo $O(nd)$ llamadas a un oráculo de Minimización del Riesgo Empírico Robusto (RERM) con una sobrecarga prohibitiva.

La cuestión central es si se pueden diseñar algoritmos que sean tanto eficientes en muestras (lineales en $d$) como eficientes en oráculos (pocas llamadas a RERM) para el aprendizaje adversariamente robusto.

Metodología

El autor propone un sencillo algoritmo de aprendizaje impropio que combina Bagging (Bootstrap Aggregation) con Minimización del Riesgo Empírico Robusto (RERM).

El Algoritmo (Bagging Robust ERMs)

Dado un conjunto de entrenamiento $S$ de tamaño $n$, un parámetro de confianza $\delta$, y un oráculo RERM $\hat{f}$:

1. Establecer el número de muestras de bootstrap $N = O(d^\star + \log(1/\delta))$, donde $d^\star$ es la dimensión VC dual de la clase $\mathcal{F}$.
2. Para cada $i \in \{1, \dots, N\}$:
   • Seleccionar un tamaño aleatorio $t$ de un rango específico $J_n = \{n/4, \dots, n-1\}$.
   • Muestrear un conjunto de datos de bootstrap $S'_i$ de tamaño $t$ uniformemente con reemplazo a partir del prefijo de $S$ de longitud $t$.
   • Ejecutar el oráculo RERM en $S'_i$ para obtener un predictor $\hat{f}_{S'_i} \in \mathcal{F}$.
3. Devolver el voto de la mayoría de los $N$ predictores: $\text{MAJ}(\hat{f}_{S'_1}, \dots, \hat{f}_{S'_N})$.

Enfoque Teórico

El análisis diverge de los argumentos previos de compresión de muestras. En su lugar, emplea un análisis de dejar uno fuera (leave-one-out analysis) adaptado al riesgo robusto:

1. Distribución sobre los RERMs: El autor analiza la distribución de los errores cometidos por los RERMs entrenados en subconjuntos aleatorios. Demuestran que, para un ejemplo de prueba aleatorio $(X, Y)$ y cualquier perturbación $Z \in U(X)$, la fracción de RERMs que clasifican erróneamente a $Z$ es pequeña en expectativa ($\tilde{O}(d/n)$).
2. Límite de Dejar Uno Fuera: Al aplicar esta expectativa a una distribución empírica, establecen un límite sobre el riesgo robusto del predictor de "bagging completo" (un promedio idealizado sobre todos los posibles bootstraps).
3. Sparsificación: Dado que el predictor de bagging completo es intratable, el autor utiliza una técnica de esparcimiento (sparsification) (Moran y Yehudayoff [2016]) para aproximar el voto agregado utilizando solo $N = O(d^\star)$ muestras de bootstrap independientes. Este paso vincula la complejidad del oráculo directamente con la dimensión VC dual $d^\star$.

Contribuciones Clave y Resultados

1. Límite Superior: Complejidad de Muestra Lineal

El resultado principal (Teorema 1) establece que las clases VC son aprendibles adversariamente de forma robusta con una complejidad de muestra lineal en la dimensión VC $d$.

• Complejidad de Muestra: $O(d/\epsilon + \frac{1}{\epsilon}\log(1/\delta))$. Esto proporciona una mejora exponencial respecto al límite previo de $O(\exp(d))$.
• Complejidad de Oráculo: El algoritmo realiza $N = O(d^\star)$ llamadas al oráculo RERM.
• Eficiencia Computacional: El algoritmo es paralelizable (a diferencia de los enfoques basados en boosting previos) e incurre únicamente en una sobrecarga computacional de $O(d^\star n)$.
• Entorno Agnóstico: Al combinar este resultado realizable con una reducción del entorno agnóstico (Montasser et al. [2019]), el autor deriva un aprendiz agnóstico con complejidad de muestra $\tilde{O}(\sqrt{d/n})$ y complejidad de oráculo $O(d^\star \log n)$.

2. Límite Inferior: Necesidad de la Dimensión VC Dual

El artículo demuestra que la dependencia de la dimensión VC dual $d^\star$ en la complejidad del oráculo es inevitable (Teorema 2).

• Resultado: Existen clases con dimensión VC $d$ y dimensión VC dual $d^\star = 2^{d+1}-1$ tales que cualquier algoritmo que realice menos de $d^\star - 1$ llamadas a un oráculo RERM falla en aprender robustamente, independientemente de la cantidad de muestras de entrenamiento proporcionadas.
• Implicación: A diferencia del aprendizaje PAC clásico donde bastan $O(\log n)$ o constantes llamadas al ERM, el aprendizaje adversariamente robusto requiere inherentemente $\Omega(d^\star)$ consultas al oráculo. Esto resalta una separación fundamental entre la complejidad del aprendizaje estándar y el robusto.

3. Caracterización Técnica

Los resultados implican que la medida de complejidad refinada $\dim(\mathcal{F}, U)$ propuesta por Montasser, Hanneke y Srebro [2022] está acotada por la dimensión VC $d$, resolviendo la conjetura de que esta medida podría ser significativamente mayor.

Significancia y Reivindicaciones

El artículo afirma proporcionar una "receta" para el aprendizaje robusto PAC computacionalmente eficiente. Al demostrar que un sencillo heurístico de bagging combinado con RERM logra una complejidad de muestra óptima, el trabajo cierra la brecha entre la robustez teórica y la eficiencia algorítmica práctica.

Las principales reivindicaciones sobre la contribución del artículo incluyen:

• Mejora Exponencial: Pasar de una complejidad de muestra exponencial a una lineal en $d$.
• Eficiencia de Oráculo: Reducir las llamadas al oráculo de $O(nd)$a$O(d^\star)$, haciendo que el enfoque sea factible para clases donde el RERM es computacionalmente tratable.
• Límite Fundamental: Establecer que la dimensión VC dual es la barrera correcta para la eficiencia del oráculo en el aprendizaje robusto, contrastando con el papel de la dimensión VC en el aprendizaje estándar.
• Relevancia Práctica: La paralelizabilidad del algoritmo y su dependencia de oráculos RERM estándar (que corresponden a las heurísticas de entrenamiento adversario utilizadas en la práctica) sugieren que estas mejoras teóricas son directamente aplicables a los contextos modernos de aprendizaje profundo.

El autor señala que, aunque el algoritmo es impropio (devolviendo un voto de la mayoría en lugar de una única función en $\mathcal{F}$), esto es necesario para alcanzar estos límites, reflejando la distinción entre el aprendizaje propio e impropio en el entorno robusto. El trabajo unifica la eficiencia algorítmica con la robustez demostrable, sugiriendo que el aprendizaje robusto eficiente es posible si se acepta el uso de aprendices impropios y se aprovecha la dimensión VC dual.