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

Sintesi Tecnica: Limiti Inferiori della Dimensione di Incapsulamento per l'Universalità delle Deep Sets e del Pooling Janossy

Enunciato del Problema
Il lavoro affronta la questione teorica dell'universalità nelle architetture di reti neurali invarianti per permutazione, in particolare le Deep Sets e la loro generalizzazione, il pooling Janossy. Sebbene sia stabilito che queste architetture possono approssimare qualsiasi funzione continua invariante per permutazione, rimane un problema aperto critico: determinare la dimensione minima di incapsulamento $M$ (la dimensione latente) necessaria per garantire tale universalità.

I lavori precedenti hanno fornito limiti superiori (ad esempio, $M \le 2nd + 1$ per le Deep Sets con $d>1$) e limiti inferiori banali (ad esempio, $M \ge n$ per $d=1$). Tuttavia, per le Deep Sets con $d > 1$ e per il pooling Janossy $k$-ario con $k > 1$, non erano noti limiti inferiori non banali che scalassero con la dimensione ambientale $d$. Il lavoro si concentra sul caso di uscita scalare ($p=1$) sul dominio $K = [0, 1]^d$, definendo $M_{univ}(d, n, k)$ come la dimensione minima di incapsulamento richiesta per l'universalità.

Metodologia
Gli autori introducono una tecnica innovativa basata sul teorema di Borsuk-Ulam per stabilire limiti inferiori sulla dimensione di incapsulamento. La metodologia procede attraverso diversi passaggi chiave:

1. Riduzione al Pooling Janossy Indicizzato: Gli autori dimostrano inizialmente che se l'architettura Janossy $k$-aria standard è universale, ciò implica l'universalità di una classe più ampia e non invariante denominata "pooling Janossy indicizzato". In questa variante indicizzata, le funzioni di codifica $\phi_{i_1, \dots, i_k}$ sono autorizzate a dipendere dagli indici specifici della tupla di input, anziché essere condivise su tutte le permutazioni. Questa riduzione permette agli autori di provare limiti inferiori per la classe indicizzata, che si applicano automaticamente alla classe simmetrica originale.
2. Rigidità delle Differenze Finite: Viene stabilita un'importante lemma che mostra come le mappe latenti del pooling Janossy indicizzato soddisfino una specifica "rigidità delle differenze finite". Se la mappa concorda su un sottoinsieme "assiale" di una griglia (dove almeno una coordinata è zero), deve concordare sull'intera griglia. Questa proprietà collega il comportamento del codificatore su un insieme sparso di input al suo comportamento su una griglia densa.
3. Costruzione di Borsuk-Ulam: Per provare il limite inferiore, gli autori costruiscono due insiemi compatti disgiunti, $E_+$ e $E_-$, all'interno dello spazio di input. Utilizzano il teorema di Borsuk-Ulam per dimostrare che se la dimensione di incapsulamento $M$ è troppo piccola (nello specifico, se $M$ è inferiore a una soglia derivata), qualsiasi codificatore continuo $\Phi$ che mappa in $\mathbb{R}^M$ deve mappare una coppia di punti antipodali (uno da $E_+$ e uno da $E_-$) nello stesso vettore latente.
4. Argomento di Collisione: Costruendo una funzione target continua $g$ che assume valori distinti (0 e 1) rispettivamente su $E_-$ e $E_+$, gli autori dimostrano che se il codificatore mappa punti da questi insiemi nello stesso vettore latente, nessun decodificatore $\rho$ può approssimare $g$ con un errore inferiore a $1/2$. Questa contraddizione prova che la dimensione assunta $M$ è insufficiente per l'universalità.

Contributi e Risultati Chiave

• Nuovo Limite Inferiore per le Deep Sets ($k=1$): Il lavoro dimostra che per le Deep Sets che agiscono su insiemi di $n$ punti in $\mathbb{R}^d$, la dimensione minima di incapsulamento soddisfa:
  $$M_{univ}(d, n, 1) \ge d(n - 1)$$
  Questo è il primo limite inferiore per $d > 1$ che cresce con la dimensione ambientale $d$. Se combinato con il limite superiore esistente di $2nd + 1$ (di Dym–Gortler), ciò stabilisce che la dimensione richiesta scala come $\Theta(nd)$, a meno di fattori costanti. Per $d=1$, il limite produce $n-1$, recuperando la dipendenza lineare nota da $n$ a meno di una costante additiva.

• Primo Limite Inferiore Non Banale per il Pooling Janossy $k$-ario ($k > 1$): Per il pooling Janossy $k$-ario generale, gli autori derivano il primo limite inferiore non banale che dipende da $d$. Il risultato è:
  $$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$$
  Questo risultato dimostra che anche con interazioni di ordine finito ($k > 1$), la dimensione latente richiesta deve crescere sia con la dimensione ambientale $d$ sia con la dimensione dell'insieme $n$.

• Quadro Tecnico: Il lavoro fornisce un quadro rigoroso per analizzare l'universalità riducendo le architetture simmetriche a quelle indicizzate e applicando ostacoli topologici (Borsuk-Ulam) alle mappe dello spazio latente.

Significato e Limitazioni
Il lavoro afferma che questi risultati risolvono un problema aperto significativo evidenziato nella letteratura precedente riguardo ai requisiti di dimensionalità per le reti invarianti per permutazione. Nello specifico, conferma che per le Deep Sets, la dimensione di incapsulamento deve scalare linearmente sia con $n$ sia con $d$, correggendo precedenti lacune in cui erano noti solo limiti dipendenti da $n$ per $d>1$. Per il pooling $k$-ario, stabilisce che le interazioni non eliminano la necessità di una crescita della dimensione con $d$.

Gli autori notano limitazioni specifiche nella loro costruzione attuale:

• Per le Deep Sets ($k=1$), il limite è $d(n-1)$ anziché $dn$. Questa "perdita" di un punto deriva dal fatto che la strategia di prova richiede un blocco di variabili per separare i due insiemi compatti disgiunti utilizzati nell'argomento di Borsuk-Ulam.
• Per $k > 1$, l'esponente $1/k$ nel limite inferiore è una limitazione della costruzione attuale, che utilizza $k$ variabili base per etichettare regioni su una sfera. Ciò lascia un divario sostanziale tra il limite inferiore derivato e il limite superiore $O(nd)$ ereditato dalle Deep Sets.

Il lavoro conclude che determinare la dipendenza esatta da $d$, $n$ e $k$, e provare limiti superiori e inferiori corrispondenti per il pooling Janossy di ordine finito, rimane un problema aperto.