Quantitative Approximation Rates for Group Equivariant Learning

1. Problema e Contesto

Il teorema di approssimazione universale stabilisce che le reti neurali possono approssimare qualsiasi funzione continua su un insieme compatto. Tuttavia, questo risultato è qualitativo e non fornisce informazioni quantitative sulla dimensione della rete necessaria per raggiungere un certo errore di approssimazione $\epsilon$. La ricerca successiva ha derivato tassi di approssimazione quantitativi per le reti ReLU su funzioni $\alpha$-Hölder, mostrando che il numero di parametri necessari scala come $(1/\epsilon)^{N/2\alpha}$, dove $N$ è la dimensione dello spazio di input.

Il problema centrale affrontato in questo lavoro è estendere questi risultati quantitativi al contesto dell'apprendimento equivariante e invariante per gruppi. In molti compiti di machine learning (es. classificazione di immagini, analisi di nuvole di punti), le funzioni target possiedono simmetrie specifiche (es. invarianza per traslazioni, rotazioni o permutazioni). La domanda di ricerca è duplice:

1. L'assunzione di invarianza/equivarianza riduce il tasso di approssimazione necessario per le reti ReLU generiche? (Ci si aspetta che la dipendenza esponenziale dalla dimensione $N$ sia sostituita da una dipendenza dalla dimensione dello spazio quoziente $N_G = \dim(V/G)$).
2. Le architetture moderne progettate per essere intrinsecamente invarianti/equivarianti (come Deep Sets, Transformer, modelli basati su frame) raggiungono questi tassi ottimali, o soffrono di una perdita di espressività rispetto alle reti generiche?

2. Metodologia

Gli autori analizzano tre scenari distinti, utilizzando strumenti di teoria dell'approssimazione, geometria differenziale e teoria dei gruppi:

• Modelli Invarianti/Equivarianti alle Permutazioni:

  • Analizzano l'architettura Deep Sets (invariante) e le sue varianti equivarianti (Sumformer e Transformer).
  • Dimostrano che le funzioni invarianti per permutazioni possono essere rappresentate come funzioni di somme di embedding.
  • Utilizzano una costruzione basata su partizioni dell'unità e codifica digitale per approssimare funzioni su domini con bassa dimensione intrinseca (o su spazi quoziente).
  • Dimostrano che le reti Transformer possono essere configurate per calcolare esattamente le somme necessarie per l'approssimazione equivariante.

• Modelli Invarianti a Permutazioni e Moti Rigidi ($E(d)$):

  • Considerano nuvole di punti invarianti sia per permutazioni che per rotazioni e traslazioni.
  • La sfida principale è la stabilità numerica della procedura di Gram-Schmidt per costruire basi ortonormali a partire dai punti, necessaria per ridurre il problema a uno spazio di dimensione inferiore (lo spazio quoziente).
  • Introducono nuovi risultati sull'approssimazione delle funzioni radice e delle operazioni di normalizzazione tramite reti ReLU profonde.
  • Utilizzano il concetto di Frame Averaging (media su un frame di gruppo) applicato a un backbone Deep Sets per costruire modelli invarianti.

• Modelli Bi-Lipschitz Invarianti:

  • Analizzano modelli che forniscono un embedding bi-Lipschitz dello spazio quoziente $V/G$ in uno spazio euclideo.
  • Dimostrano che se esiste una mappa invariante bi-Lipschitz $E$, allora l'approssimazione di una funzione invariante $f$ può essere ridotta all'approssimazione di $f \circ E^{-1}$ su un dominio di dimensione inferiore.

3. Contributi Chiave e Risultati Principali

A. Tassi di Approssimazione Ottimali

Il risultato fondamentale è che le architetture equivarianti raggiungono gli stessi tassi di approssimazione asintotici delle reti ReLU generiche, ma sulla dimensione dello spazio quoziente $N_G$.
Per una funzione $\alpha$-Hölder definita su un dominio $V$ con azione di gruppo $G$, il numero di parametri necessari scala come:
$$P \sim \left(\frac{1}{\epsilon}\right)^{\frac{N_G}{2\alpha}}$$
dove $N_G$ è la dimensione effettiva dello spazio quoziente (es. $nd - \dim(G)$ per nuvole di punti).

B. Risultati Specifici per Architetture

1. Deep Sets: Viene dimostrato che Deep Sets può approssimare funzioni invarianti per permutazioni con il tasso ottimale $(1/\epsilon)^{nd/2\alpha}$. Questo confuta l'idea che la mancanza di interazioni a coppie (pairwise interactions) limiti l'espressività asintotica per funzioni Hölder.
2. Sumformer e Transformer: Vengono derivati tassi di approssimazione per queste architetture equivarianti, mostrando che sono in grado di catturare le stesse funzioni con la stessa efficienza asintotica.
3. Modelli per Moti Rigidi: Viene dimostrato che le reti basate su frame (che applicano rotazioni canoniche a un backbone Deep Sets) raggiungono il tasso $(1/\epsilon)^{(nd - \dim(E(d)))/2\alpha}$.
4. Modelli Bi-Lipschitz: Viene provato che qualsiasi modello che fornisce un embedding bi-Lipschitz dello spazio quoziente (es. Max Filters, ordinamento multidimensionale) raggiunge il tasso ottimale $(1/\epsilon)^{d_{intrinsic}/2\alpha}$.

C. Miglioramento sui Risultati Precedenti

Per funzioni non invarianti definite su domini con bassa dimensione intrinseca (ma immersi in spazi ad alta dimensione), gli autori migliorano il tasso di approssimazione noto. Mentre lavori precedenti (es. Nakada e Imaizumi, 2020) ottenevano un tasso di $(1/\epsilon)^{d_{intrinsic}/\alpha}$, questo lavoro dimostra un tasso di $(1/\epsilon)^{d_{intrinsic}/2\alpha}$, raddoppiando l'efficienza nell'esponente.

4. Significato e Implicazioni

• Espressività vs. Efficienza: Il risultato più significativo è che l'incorporazione di simmetrie (hard-coding) non comporta una perdita di potere espressivo o di capacità di approssimazione rispetto alle reti generiche. Sia le reti generiche che quelle specializzate raggiungono lo stesso limite asintotico.
• Origine dei Vantaggi Pratici: Poiché l'espressività è equivalente, i vantaggi pratici osservati nei modelli equivarianti (migliore generalizzazione fuori distribuzione, minore complessità del campione) non derivano da una maggiore capacità di approssimazione, ma da una migliore efficienza nell'ottimizzazione e nella complessità del campione (sample complexity).
• Teoria Quantitativa: Questo lavoro colma un vuoto significativo nella teoria dell'apprendimento profondo, fornendo per la prima volta stime quantitative rigorose per modelli equivarianti, passando oltre la semplice dimostrazione di universalità.
• Prospettive Future: Gli autori notano che, sebbene i tassi asintotici siano simili, potrebbero esistere differenze nelle costanti o nelle prestazioni a scale realistiche tra diversi modelli equivarianti (es. EGNN vs. modelli basati su frame), un'area che richiede analisi più raffinate.

In sintesi, il paper stabilisce che la simmetria è un vincolo che non penalizza la capacità di approssimazione asintotica, confermando che le architetture equivarianti sono teoricamente solide e ottimali per l'approssimazione di funzioni simmetriche.