A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

Resumen Técnico: Una dicotomía de espacios de funciones para el aprendizaje composicional

Planteamiento del problema
Una observación empírica persistente en el aprendizaje profundo es que las redes neuronales entrenadas superan consistentemente los límites de su Kernel de Tangente Neural (NTK) en tareas con estructura composicional o jerárquica. Mientras que la literatura existente atribuye las brechas entre kernel y red mayoritariamente a la maldición de la dimensionalidad (donde los kernels luchan con proyecciones de baja dimensión de entradas de alta dimensión), ha faltado una cuenta cuantitativa de la brecha en dimensiones de entrada fijas —específicamente impulsada por la profundidad de la red y la estructura composicional—. Este artículo aborda la pregunta: ¿En qué objetivos, y en qué medida, es subóptimo el NTK, y qué propiedad específica de esos objetivos impide que el kernel los explote?

Metodología y configuración
Los autores analizan este problema en el círculo unitario $S^1$, donde el NTK admite una descripción de Fourier limpia. Introducen una dicotomía entre dos medidas de complejidad para una función objetivo $f^*$:

1. Complejidad de Fourier: Controla el costo de aprendizaje mediante el NTK (régimen perezoso o lazy regime). Se demuestra que la norma del RKHS del NTK es equivalente (hasta una constante dependiente de la profundidad) a la norma de Sobolev $H^1$, que penaliza las oscilaciones de alta frecuencia.
2. Complejidad Arquitectónica: Controla el costo de aprendizaje mediante el entrenamiento con decaimiento de pesos (weight-decay) en el régimen "rico". Esto se mide mediante la norma de variación profunda ($RBV^2_{deep}$), que cuantifica el tamaño de la red ReLU más pequeña de profundidad-$L$ y ancho-$w$ requerida para construir el objetivo.

Los autores definen la clase de arquitectura $\mathcal{C}_{L,w,R}$ como redes ReLU de profundidad-$L$, ancho-$w$ con una norma de variación profunda $R$ acotada. Comparan la complejidad de muestreo del estimador NTK (Regresión de Ridge por Kernel) contra el límite inferior minimax para esta clase de arquitectura.

Contribuciones clave

1. Caracterización Minimax de Clases de Arquitectura Profunda:
   El artículo establece la tasa minimax $L^2$ para la clase $\mathcal{C}_{L,w,R}$. La tasa se sitúa entre $\Omega(Lw^2R^2/n)$ y $\tilde{O}(L^2w^2R^2/n)$. Este resultado es ajustado hasta un único factor de $L$, lo que representa el suelo estadístico para cualquier estimador en esta clase. Notablemente, esta tasa está indexada por parámetros arquitectónicos $(L, w, R)$ en lugar de exponentes de suavidad del objetivo.

2. Suboptimalidad Exponencial del NTK:
   Los autores demuestran que el estimador NTK se sitúa exponencialmente por encima del suelo minimax siempre que la complejidad de Fourier y la complejidad arquitectónica del objetivo se desacoplen. Específicamente, para un objetivo con frecuencia dominante $k^*$, el NTK requiere $\Omega((k^*)^2)$ muestras, mientras que la clase de arquitectura requiere solo recursos polinómicos en sus parámetros estructurales.

   • El Testigo: La función de sierra iterada de profundidad-$L$ (Telgarsky 2016) sirve como el testigo analítico. Puede construirse con una red de ancho-2 y profundidad-$L$ con $O(L)$ pesos (baja complejidad arquitectónica) pero oscila $2^{L-1}$ veces (complejidad de Fourier exponencial).
   • La Brecha: Para la función de sierra, el NTK requiere $\Omega(4^L)$ muestras, mientras que el suelo minimax es polinómico en $L$ (entre $L^3$ y $L^4$). Esto produce una separación exponencial en la complejidad de muestreo.

3. Validación Empírica:
   Los experimentos numéricos confirman las afirmaciones teóricas en tres frentes:

   • Espectro del NTK: El decaimiento de los autovalores del NTK en $S^1$ sigue el decaimiento $k^{-2}$ predicho, confirmando el fenómeno "profundo es igual a superficial" donde la profundidad no altera la tasa de decaimiento espectral.
   • Objetivos Suaves: En objetivos de banda limitada (suaves), el NTK es competitivo o mejor que las redes anchas, sin mostrar una brecha exponencial.
   • Objetivos Composicionales: En el modelo de paridad dispersa sobre el hipercubo (un dominio diferente donde el SGD es conocido por tener éxito), una red estándar de dos capas supera al NTK por cuatro a seis órdenes de magnitud en error de prueba, realizando la separación predicha de extremo a extremo.

Resultados y Significado
El artículo concluye que la brecha de rendimiento entre el NTK y las redes entrenadas no es un fenómeno genérico de "kernel-versus-red", sino una propiedad del espacio de funciones. La brecha surge de un desajuste entre el sesgo de suavidad inherente del kernel (que favorece funciones de baja frecuencia) y la estructura composicional del objetivo (que puede generar oscilaciones de alta frecuencia con bajo costo arquitectónico).

• Perspectiva Teórica: El trabajo proporciona un mecanismo preciso de por qué la profundidad ayuda: permite a las redes representar funciones oscilatorias de alta frecuencia de forma económica mediante composición, una capacidad que el NTK (que se comporta como un kernel de Sobolev fijo) carece.
• Suelo Minimax: La derivación de la tasa minimax para el espacio de variación profunda se presenta como una contribución independiente, ofreciendo una estimación directa, libre de kernels, de la complejidad de muestreo para problemas composicionales basada en parámetros arquitectónicos.
• Alcance: Los autores aclaran que la brecha no es universal; desaparece para objetivos suaves de banda limitada donde las complejidades de Fourier y arquitectónica están alineadas. Además, distinguen entre límites estadísticos y viabilidad algorítmica, señalando que, si bien la función de sierra es estadísticamente aprendible por la clase de arquitectura, es notoriamente difícil de optimizar para el descenso de gradiente, mientras que la paridad dispersa es tanto estadística como algorítmicamente aprendible.

En resumen, el artículo argumenta que el NTK es casi óptimo para objetivos con suavidad $H^1$, pero exponencialmente subóptimo para objetivos donde la estructura composicional permite representaciones de alta frecuencia de "bajo costo", un régimen donde el entrenamiento en el régimen rico es estadísticamente necesario.