Quantitative Approximation Rates for Group Equivariant Learning

1. Problema y Contexto

El Teorema de Aproximación Universal establece que las redes neuronales pueden aproximar cualquier función continua en un conjunto compacto. Sin embargo, este teorema es cualitativo y no proporciona información sobre el tamaño de la red necesaria para lograr una precisión dada. La teoría de aproximación cuantitativa ha avanzado significativamente para redes ReLU estándar, demostrando que para aproximar funciones $\alpha$-Hölder en un dominio de dimensión $N$, se requieren aproximadamente $O(\epsilon^{-N/2\alpha})$ parámetros.

El problema central de este trabajo es determinar si las arquitecturas diseñadas para ser equivariantes o invariantes bajo la acción de un grupo $G$ (como redes para conjuntos de puntos, grafos o nubes de puntos) mantienen estas tasas de aproximación óptimas o si la imposición de simetrías ("hard-coding") conlleva una pérdida de expresividad o eficiencia.

La pregunta clave es: ¿Pueden las arquitecturas invariantes/equivariantes aproximar funciones con la misma tasa asintótica que las redes ReLU genéricas, pero adaptadas a la dimensión del espacio cociente $V/G$ (donde $V$ es el espacio de entrada y $G$ el grupo de simetría)? Específicamente, ¿la tasa de aproximación depende de la dimensión del espacio de órbitas ($N_G$) en lugar de la dimensión del espacio de entrada ($N$)?

2. Metodología

Los autores abordan el problema mediante un análisis teórico riguroso de la complejidad de aproximación (número de parámetros necesarios) para varias arquitecturas prominentes. La metodología se basa en:

1. Análisis de Dimensión Intrínseca: Utilizan la noción de dimensión de Minkowski y recubrimiento (covering numbers) del espacio cociente $K/G$. La hipótesis central es que la complejidad de aproximar una función invariante debe escalar con la dimensión del espacio de órbitas, no con la dimensión total de los datos.
2. Construcción de Redes ReLU: Demuestran la existencia de redes ReLU (no necesariamente invariantes por diseño) que pueden aproximar funciones invariantes alcanzando la tasa óptima esperada basada en la dimensión del cociente.
3. Análisis de Arquitecturas Específicas: Evalúan arquitecturas que incorporan simetrías por diseño:
   • Deep Sets: Para funciones invariantes a permutaciones.
   • Sumformer y Transformers: Para funciones equivariantes a permutaciones.
   • Redes basadas en Frames (Frame Averaging): Para funciones invariantes a permutaciones y movimientos rígidos ($E(d)$).
   • Modelos Bi-Lipschitz: Para grupos de isometrías generales.
4. Herramientas Matemáticas:
   • Teorema de Superposición de Kolmogorov-Arnold: Adaptado para construir redes que aproximan funciones en subespacios definidos por simetrías.
   • Estabilidad del Proceso de Gram-Schmidt: Para manejar la invarianza rotacional, demostrando que se pueden construir bases ortonormales estables mediante redes neuronales.
   • Aproximación de Funciones Raíz y Racionales: Uso de redes profundas para aproximar operaciones no lineales necesarias para la construcción de invariantes (como la normalización de vectores).

3. Contribuciones Clave

El artículo presenta tres escenarios principales de estudio, proporcionando las primeras tasas de aproximación cuantitativas rigurosas para estos modelos:

A. Modelos Invariantes y Equivariantes a Permutaciones ($S_n$)

• Deep Sets: Demuestran que la arquitectura Deep Sets (suma de embeddings individuales seguida de una red externa) puede aproximar funciones $\alpha$-Hölder invariantes a permutaciones con una tasa de $O(\epsilon^{-N/2\alpha})$, donde $N = n \cdot d$ es la dimensión total. Esto confirma que Deep Sets no pierde expresividad asintótica frente a redes MLP generales para funciones invariantes.
• Sumformer y Transformers: Extienden los resultados de Deep Sets para demostrar que arquitecturas equivariantes populares como Sumformer y Transformers también alcanzan estas tasas óptimas.
• Resultado Colateral: Mejoran la tasa de aproximación conocida para funciones no invariantes definidas en dominios con dimensión intrínseca baja ($d_{intrinsic}$), reduciendo la tasa de $O(\epsilon^{-d_{intrinsic}/\alpha})$ a $O(\epsilon^{-d_{intrinsic}/2\alpha})$.

B. Modelos Invariantes a Permutaciones y Movimientos Rígidos ($E(d) \times S_n$)

• Este escenario es crucial para nubes de puntos 3D (visión por computadora, dinámica de partículas).
• Redes ReLU Generales: Demuestran que una red ReLU estándar puede aproximar funciones invariantes a movimientos rígidos con una tasa que depende de la dimensión del espacio cociente: $N_G = n \cdot d - \dim(E(d))$.
• Redes con Frames (Frame Averaging): Analizan arquitecturas que aplican un "frame" (un conjunto de transformaciones) a una red base (como Deep Sets) para lograr invarianza. Demuestran que si la red base tiene la tasa óptima, la red resultante con promediado de frames también la alcanza. Esto incluye métodos basados en alineación a direcciones principales o promediado sobre descomposiciones SVD.

C. Modelos Bi-Lipschitz Invariantes

• Consideran un marco general para grupos de isometrías cerrados.
• Demuestran que cualquier modelo que proporcione una inmersión bi-Lipschitz del espacio cociente $V/G$ en un espacio euclidiano permite alcanzar la tasa de aproximación óptima $O(\epsilon^{-d_{intrinsic}/2\alpha})$.
• Esto aplica a modelos basados en Max Filters y otras construcciones de invariantes que preservan la métrica del espacio de órbitas.

4. Resultados Principales

El hallazgo central y más significativo del trabajo es que la invarianza o equivarianza "hard-coded" no resulta en una pérdida de poder de aproximación asintótico.

• Equivalencia de Expresividad: Las arquitecturas especializadas (Deep Sets, Transformers, redes con frames) tienen la misma capacidad expresiva (en términos de número de parámetros necesarios para una precisión $\epsilon$) que las redes ReLU genéricas cuando se restringen a funciones que obedecen las simetrías del grupo.
• Dependencia de la Dimensión del Cociente: La tasa de aproximación para todas las arquitecturas analizadas escala con la dimensión efectiva del espacio de datos después de cuotientar por el grupo ($N_G$), y no con la dimensión bruta de los datos.
  • Fórmula general de la tasa: $P \sim \epsilon^{-N_G / 2\alpha}$.
• Implicación Práctica: Las ventajas prácticas de los modelos equivariantes (mejor eficiencia de muestra y generalización fuera de distribución) no se deben a una mayor capacidad de aproximación teórica, sino a la eficiencia en la optimización y la reducción de la complejidad de la muestra derivada de la restricción del espacio de parámetros.

5. Significado e Impacto

Este trabajo cierra una brecha importante en la teoría del aprendizaje profundo equivariante:

1. Validación Teórica: Proporciona la primera justificación matemática rigurosa de que las arquitecturas equivariantes populares no son "subóptimas" en términos de capacidad de aproximación en comparación con redes genéricas.
2. Guía de Diseño: Sugiere que la elección de arquitecturas equivariantes debe basarse en consideraciones de eficiencia de entrenamiento, generalización y cantidad de datos, y no en la esperanza de una mayor capacidad de modelado intrínseca.
3. Nuevas Direcciones: Identifica que, aunque las tasas asintóticas son similares, pueden existir diferencias en las constantes ocultas o en el comportamiento a escalas realistas (no asintóticas) entre diferentes métodos equivariantes (ej. EGNN vs. redes con frames), lo que abre la puerta a análisis más finos.
4. Generalización: Los resultados unifican el entendimiento de la aproximación en diversos dominios geométricos (puntos, grafos, nubes de puntos 3D) bajo un marco teórico común basado en la dimensión del espacio cociente.

En resumen, el paper demuestra que incorporar simetrías en la arquitectura es una estrategia eficiente y sin pérdida de poder expresivo, validando teóricamente el paradigma de aprendizaje equivariante en el aprendizaje automático moderno.