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

Technische Samenvatting: Ondergrenzen voor Inbeddingsdimensie voor Universaliteit van Deep Sets en Janossy Pooling

Probleemstelling
Het artikel behandelt de theoretische vraag naar universaliteit in permutatie-invariante neurale netwerkarchitecturen, specifiek Deep Sets en de generalisatie daarvan, Janossy pooling. Hoewel vaststaat dat deze architecturen elke continue permutatie-invariante functie kunnen benaderen, blijft een kritiek open probleem bestaan: het bepalen van de minimale inbeddingsdimensie $M$ (de latente dimensie) die nodig is om deze universaliteit te garanderen.

Vorige werk heeft bovengrenzen geleverd (bijvoorbeeld $M \le 2nd + 1$ voor Deep Sets met $d>1$) en triviale ondergrenzen (bijvoorbeeld $M \ge n$ voor $d=1$). Echter, voor Deep Sets met $d > 1$ en voor $k$-aire Janossy pooling met $k > 1$, waren er geen niet-triviale ondergrenzen bekend die schalen met de omgevingsdimensie $d$. Het artikel richt zich op het geval met scalair uitvoer ($p=1$) over het domein $K = [0, 1]^d$, waarbij $M_{univ}(d, n, k)$ wordt gedefinieerd als de minimale inbeddingsdimensie die vereist is voor universaliteit.

Methodologie
De auteurs introduceren een nieuwe techniek gebaseerd op de stelling van Borsuk-Ulam om ondergrenzen voor de inbeddingsdimensie vast te stellen. De methodologie verloopt via enkele sleutelstappen:

1. Reductie tot Geïndexeerde Janossy Pooling: De auteurs tonen eerst aan dat als de standaard $k$-aire Janossy-architectuur universeel is, dit de universaliteit impliceert van een grotere, niet-invariante klasse die "geïndexeerde Janossy pooling" wordt genoemd. In deze geïndexeerde variant mogen de encoderfuncties $\phi_{i_1, \dots, i_k}$ afhankelijk zijn van de specifieke indices van de invoertuple, in plaats van gedeeld te worden over alle permutaties. Deze reductie stelt de auteurs in staat om ondergrenzen te bewijzen voor de geïndexeerde klasse, die automatisch van toepassing zijn op de oorspronkelijke symmetrische klasse.
2. Stijfheid van Eindige Verschillen: Een cruciaal lemma wordt vastgesteld dat aantoont dat geïndexeerde Janossy-late maps voldoen aan een specifieke "stijfheid van eindige verschillen". Als de map overeenkomt op een "as"-deelverzameling van een rooster (waarbij minstens één coördinaat nul is), moet deze overeenkomen op het hele rooster. Deze eigenschap koppelt het gedrag van de encoder op een schaarse set invoeren aan zijn gedrag op een dicht rooster.
3. Constructie van Borsuk-Ulam: Om de ondergrens te bewijzen, construeren de auteurs twee disjuncte compacte verzamelingen, $E_+$ en $E_-$, binnen de invoerruimte. Ze maken gebruik van de stelling van Borsuk-Ulam om aan te tonen dat als de inbeddingsdimensie $M$ te klein is (specifiek, als $M$ kleiner is dan een afgeleide drempel), elke continue encoder $\Phi$ die afbeeldt naar $\mathbb{R}^M$, een paar antipodale punten (één uit $E_+$ en één uit $E_-$) moet afbeelden naar hetzelfde latente vector.
4. Kollisie-argument: Door een continue doelfunctie $g$ te construeren die verschillende waarden (0 en 1) aanneemt op respectievelijk $E_-$ en $E_+$, tonen de auteurs aan dat als de encoder punten uit deze verzamelingen afbeeldt naar hetzelfde latente vector, geen enkele decoder $\rho$ $g$ kan benaderen met een fout kleiner dan $1/2$. Dit contradictie bewijst dat de aangenomen dimensie $M$ ontoereikend is voor universaliteit.

Belangrijkste Bijdragen en Resultaten

• Nieuwe Ondergrens voor Deep Sets ($k=1$): Het artikel bewijst dat voor Deep Sets die werken op verzamelingen van $n$ punten in $\mathbb{R}^d$, de minimale inbeddingsdimensie voldoet aan:
  $$M_{univ}(d, n, 1) \ge d(n - 1)$$
  Dit is de eerste ondergrens voor $d > 1$ die groeit met de omgevingsdimensie $d$. In combinatie met de bestaande bovengrens van $2nd + 1$ (van Dym–Gortler) wordt hiermee vastgesteld dat de vereiste dimensie schaalt als $\Theta(nd)$, tot op constante factoren. Voor $d=1$ levert de grens $n-1$ op, waarmee de bekende lineaire afhankelijkheid van $n$ tot op een additieve constante wordt hersteld.

• Eerste Niet-Triviale Ondergrens voor $k$-aire Janossy Pooling ($k > 1$): Voor algemene $k$-aire Janossy pooling leiden de auteurs de eerste niet-triviale ondergrens af die afhankelijk is van $d$. Het resultaat is:
  $$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$$
  Dit resultaat toont aan dat zelfs met interacties van eindige orde ($k > 1$), de vereiste latente dimensie moet groeien met zowel de omgevingsdimensie $d$ als de verzamelingsgrootte $n$.

• Technisch Kader: Het artikel biedt een rigoureus kader voor het analyseren van universaliteit door symmetrische architecturen te reduceren tot geïndexeerde exemplaren en topologische obstructies (Borsuk-Ulam) toe te passen op afbeeldingen van de latente ruimte.

Betekenis en Beperkingen
Het artikel stelt dat deze resultaten een significant open probleem oplossen dat in eerdere literatuur werd benadrukt met betrekking tot de dimensie-eisen voor permutatie-invariante netwerken. Specifiek bevestigt het dat voor Deep Sets de inbeddingsdimensie lineair moet schalen met zowel $n$ als $d$, waardoor eerdere hiaten worden gecorrigeerd waarbij alleen $n$-afhankelijke grenzen bekend waren voor $d>1$. Voor $k$-aire pooling wordt vastgesteld dat interacties de noodzaak van dimensiegroei met $d$ niet elimineren.

De auteurs merken specifieke beperkingen op in hun huidige constructie:

• Voor Deep Sets ($k=1$) is de grens $d(n-1)$ in plaats van $dn$. Dit "verlies" van één punt ontstaat omdat de bewijsstrategie één blok variabelen vereist om de twee disjuncte compacte verzamelingen te scheiden die worden gebruikt in het Borsuk-Ulam-argument.
• Voor $k > 1$ is de exponent $1/k$ in de ondergrens een beperking van de huidige constructie, die $k$ basisvariabelen gebruikt om gebieden op een bol te labelen. Dit laat een aanzienlijke kloof tussen de afgeleide ondergrens en de geërfd $O(nd)$ bovengrens van Deep Sets.

Het artikel concludeert dat het bepalen van de exacte afhankelijkheid van $d$, $n$ en $k$, en het bewijzen van overeenkomende boven- en ondergrenzen voor Janossy pooling van eindige orde, een open probleem blijft.