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

Résumé technique : Bornes inférieures de la dimension d'encodage pour l'universalité des Deep Sets et du regroupement Janossy

Énoncé du problème
L'article aborde la question théorique de l'universalité dans les architectures de réseaux de neurones invariantes par permutation, spécifiquement les Deep Sets et leur généralisation, le regroupement Janossy. Bien qu'il soit établi que ces architectures peuvent approximer n'importe quelle fonction continue invariante par permutation, un problème ouvert critique demeure : déterminer la dimension d'encodage minimale $M$ (la dimension latente) requise pour garantir cette universalité.

Les travaux antérieurs ont fourni des bornes supérieures (par exemple, $M \le 2nd + 1$ pour les Deep Sets avec $d>1$) et des bornes inférieures triviales (par exemple, $M \ge n$ pour $d=1$). Cependant, pour les Deep Sets avec $d > 1$ et pour le regroupement Janossy $k$-aire avec $k > 1$, aucune borne inférieure non triviale évoluant avec la dimension ambiante $d$ n'était connue. L'article se concentre sur le cas de sortie scalaire ($p=1$) sur le domaine $K = [0, 1]^d$, en définissant $M_{univ}(d, n, k)$ comme la dimension d'encodage minimale requise pour l'universalité.

Méthodologie
Les auteurs introduisent une nouvelle technique basée sur le théorème de Borsuk-Ulam pour établir des bornes inférieures sur la dimension d'encodage. La méthodologie procède par plusieurs étapes clés :

1. Réduction au regroupement Janossy indexé : Les auteurs démontrent d'abord que si l'architecture Janossy $k$-aire standard est universelle, cela implique l'universalité d'une classe plus large, non invariante, appelée « regroupement Janossy indexé ». Dans cette variante indexée, les fonctions d'encodage $\phi_{i_1, \dots, i_k}$ sont autorisées à dépendre des indices spécifiques du tuple d'entrée, plutôt que d'être partagées sur toutes les permutations. Cette réduction permet aux auteurs de prouver des bornes inférieures pour la classe indexée, qui s'appliquent automatiquement à la classe symétrique originale.
2. Rigidité des différences finies : Un lemme crucial est établi montrant que les cartes latentes du regroupement Janossy indexé satisfont une « rigidité des différences finies » spécifique. Si la carte est d'accord sur un sous-ensemble « axial » d'une grille (où au moins une coordonnée est nulle), elle doit être d'accord sur toute la grille. Cette propriété lie le comportement de l'encodeur sur un ensemble clairsemé d'entrées à son comportement sur une grille dense.
3. Construction de Borsuk-Ulam : Pour prouver la borne inférieure, les auteurs construisent deux ensembles compacts disjoints, $E_+$ et $E_-$, dans l'espace d'entrée. Ils utilisent le théorème de Borsuk-Ulam pour montrer que si la dimension d'encodage $M$ est trop petite (spécifiquement, si $M$ est inférieure à un seuil dérivé), tout encodeur continu $\Phi$ mappant vers $\mathbb{R}^M$ doit mapper une paire de points antipodaux (un de $E_+$ et un de $E_-$) vers le même vecteur latent.
4. Argument de collision : En construisant une fonction cible continue $g$ qui prend des valeurs distinctes (0 et 1) sur $E_-$ et $E_+$ respectivement, les auteurs montrent que si l'encodeur mappe des points de ces ensembles vers le même vecteur latent, aucun décodeur $\rho$ ne peut approximer $g$ avec une erreur inférieure à $1/2$. Cette contradiction prouve que la dimension supposée $M$ est insuffisante pour l'universalité.

Contributions et résultats clés

• Nouvelle borne inférieure pour les Deep Sets ($k=1$) : L'article prouve que pour les Deep Sets agissant sur des ensembles de $n$ points dans $\mathbb{R}^d$, la dimension d'encodage minimale satisfait :
  $$M_{univ}(d, n, 1) \ge d(n - 1)$$
  Il s'agit de la première borne inférieure pour $d > 1$ qui croît avec la dimension ambiante $d$. Combinée à la borne supérieure existante de $2nd + 1$ (de Dym–Gortler), cela établit que la dimension requise évolue comme $\Theta(nd)$, à des facteurs constants près. Pour $d=1$, la borne donne $n-1$, retrouvant la dépendance linéaire connue en $n$ à une constante additive près.

• Première borne inférieure non triviale pour le regroupement Janossy $k$-aire ($k > 1$) : Pour le regroupement Janossy $k$-aire général, les auteurs dérivent la première borne inférieure non triviale dépendant de $d$. Le résultat est :
  $$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$$
  Ce résultat démontre que même avec des interactions d'ordre fini ($k > 1$), la dimension latente requise doit croître à la fois avec la dimension ambiante $d$ et la taille de l'ensemble $n$.

• Cadre technique : L'article fournit un cadre rigoureux pour analyser l'universalité en réduisant les architectures symétriques à des architectures indexées et en appliquant des obstructions topologiques (Borsuk-Ulam) aux mappings de l'espace latent.

Signification et limites
L'article affirme que ces résultats résolvent un problème ouvert significatif souligné dans la littérature antérieure concernant les exigences de dimensionalité pour les réseaux invariants par permutation. Plus précisément, il confirme que pour les Deep Sets, la dimension d'encodage doit évoluer linéairement avec $n$ et $d$, corrigeant les lacunes précédentes où seules des bornes dépendant de $n$ étaient connues pour $d>1$. Pour le regroupement $k$-aire, il établit que les interactions n'éliminent pas le besoin d'une croissance de la dimension avec $d$.

Les auteurs notent des limites spécifiques dans leur construction actuelle :

• Pour les Deep Sets ($k=1$), la borne est $d(n-1)$ et non $dn$. Cette « perte » d'un point découle du fait que la stratégie de preuve nécessite un bloc de variables pour séparer les deux ensembles compacts disjoints utilisés dans l'argument de Borsuk-Ulam.
• Pour $k > 1$, l'exposant $1/k$ dans la borne inférieure est une limitation de la construction actuelle, qui utilise $k$ variables de base pour étiqueter des régions sur une sphère. Cela laisse un écart substantiel entre la borne inférieure dérivée et la borne supérieure héritée de $O(nd)$ des Deep Sets.

L'article conclut que déterminer la dépendance exacte en $d$, $n$ et $k$, et prouver des bornes supérieures et inférieures correspondantes pour le regroupement Janossy d'ordre fini, reste un problème ouvert.