Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

Resumen Técnico: Límites Inferiores de la Dimensión de Incrustación para la Universalidad de Deep Sets y Agrupamiento Janossy

Enunciado del Problema
El artículo aborda la cuestión teórica de la universalidad en arquitecturas de redes neuronales invariantes a permutaciones, específicamente Deep Sets y su generalización, el agrupamiento Janossy. Si bien está establecido que estas arquitecturas pueden aproximar cualquier función continua invariante a permutaciones, persiste un problema abierto crítico: determinar la dimensión mínima de incrustación $M$ (la dimensión latente) requerida para garantizar dicha universalidad.

Trabajos anteriores han proporcionado cotas superiores (por ejemplo, $M \le 2nd + 1$ para Deep Sets con $d>1$) y cotas inferiores triviales (por ejemplo, $M \ge n$ para $d=1$). Sin embargo, para Deep Sets con $d > 1$ y para el agrupamiento Janossy $k$-ario con $k > 1$, no se conocían cotas inferiores no triviales que escalen con la dimensión ambiental $d$. El artículo se centra en el caso de salida escalar ($p=1$) sobre el dominio $K = [0, 1]^d$, definiendo $M_{univ}(d, n, k)$ como la dimensión mínima de incrustación requerida para la universalidad.

Metodología
Los autores introducen una técnica novedosa basada en el teorema de Borsuk-Ulam para establecer cotas inferiores sobre la dimensión de incrustación. La metodología procede a través de varios pasos clave:

1. Reducción al Agrupamiento Janossy Indexado: Los autores demuestran primero que si la arquitectura Janossy $k$-aria estándar es universal, esto implica la universalidad de una clase más amplia e invariante llamada "agrupamiento Janossy indexado". En esta variante indexada, las funciones codificadoras $\phi_{i_1, \dots, i_k}$ pueden depender de los índices específicos de la tupla de entrada, en lugar de compartirse entre todas las permutaciones. Esta reducción permite a los autores probar cotas inferiores para la clase indexada, las cuales se aplican automáticamente a la clase simétrica original.
2. Rigidez de Diferencias Finitas: Se establece un lema crucial que muestra que los mapas latentes del agrupamiento Janossy indexado satisfacen una "rigidez de diferencias finitas" específica. Si el mapa coincide en un subconjunto "axial" de una cuadrícula (donde al menos una coordenada es cero), debe coincidir en toda la cuadrícula. Esta propiedad vincula el comportamiento del codificador en un conjunto disperso de entradas con su comportamiento en una cuadrícula densa.
3. Construcción de Borsuk-Ulam: Para probar la cota inferior, los autores construyen dos conjuntos compactos disjuntos, $E_+$ y $E_-$, dentro del espacio de entrada. Utilizan el teorema de Borsuk-Ulam para demostrar que si la dimensión de incrustación $M$ es demasiado pequeña (específicamente, si $M$ es menor que un umbral derivado), cualquier codificador continuo $\Phi$ que mapee a $\mathbb{R}^M$ debe mapear un par de puntos antipodales (uno de $E_+$ y otro de $E_-$) al mismo vector latente.
4. Argumento de Colisión: Mediante la construcción de una función objetivo continua $g$ que toma valores distintos (0 y 1) en $E_-$ y $E_+$ respectivamente, los autores muestran que si el codificador mapea puntos de estos conjuntos al mismo vector latente, ningún decodificador $\rho$ puede aproximar $g$ con un error menor a $1/2$. Esta contradicción prueba que la dimensión asumida $M$ es insuficiente para la universalidad.

Contribuciones y Resultados Clave

• Nueva Cota Inferior para Deep Sets ($k=1$): El artículo demuestra que para Deep Sets actuando sobre conjuntos de $n$ puntos en $\mathbb{R}^d$, la dimensión mínima de incrustación satisface:
  $$M_{univ}(d, n, 1) \ge d(n - 1)$$
  Esta es la primera cota inferior para $d > 1$ que crece con la dimensión ambiental $d$. Combinada con la cota superior existente de $2nd + 1$ (de Dym–Gortler), esto establece que la dimensión requerida escala como $\Theta(nd)$, hasta factores constantes. Para $d=1$, la cota produce $n-1$, recuperando la dependencia lineal conocida con $n$ hasta una constante aditiva.

• Primera Cota Inferior No Trivial para Agrupamiento Janossy $k$-ario ($k > 1$): Para el agrupamiento Janossy $k$-ario general, los autores derivan la primera cota inferior no trivial que depende de $d$. El resultado es:
  $$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$$
  Este resultado demuestra que incluso con interacciones de orden finito ($k > 1$), la dimensión latente requerida debe crecer tanto con la dimensión ambiental $d$ como con el tamaño del conjunto $n$.

• Marco Técnico: El artículo proporciona un marco riguroso para analizar la universalidad mediante la reducción de arquitecturas simétricas a indexadas y la aplicación de obstrucciones topológicas (Borsuk-Ulam) a los mapeos del espacio latente.

Significado y Limitaciones
El artículo afirma que estos resultados resuelven un problema abierto significativo destacado en la literatura previa respecto a los requisitos de dimensionalidad para redes invariantes a permutaciones. Específicamente, confirma que para Deep Sets, la dimensión de incrustación debe escalar linealmente tanto con $n$ como con $d$, corrigiendo brechas anteriores donde solo se conocían cotas dependientes de $n$ para $d>1$. Para el agrupamiento $k$-ario, establece que las interacciones no eliminan la necesidad de crecimiento dimensional con $d$.

Los autores señalan limitaciones específicas en su construcción actual:

• Para Deep Sets ($k=1$), la cota es $d(n-1)$ en lugar de $dn$. Esta "pérdida" de un punto surge porque la estrategia de prueba requiere un bloque de variables para separar los dos conjuntos compactos disjuntos utilizados en el argumento de Borsuk-Ulam.
• Para $k > 1$, el exponente $1/k$ en la cota inferior es una limitación de la construcción actual, que utiliza $k$ variables base para etiquetar regiones en una esfera. Esto deja una brecha sustancial entre la cota inferior derivada y la cota superior heredada de $O(nd)$ de Deep Sets.

El artículo concluye que determinar la dependencia exacta con $d$, $n$ y $k$, y probar cotas superiores e inferiores coincidentes para el agrupamiento Janossy de orden finito, sigue siendo un problema abierto.