Titel: Benaderingsraten voor Groep-Equivariante Learning

Auteurs: Jonathan W. Siegel, Snir Hordan, Hannah Lawrence, Ali Syed, Nadav Dym.

1. Probleemstelling

De universele benaderingstelling (Universal Approximation Theorem) garandeert dat neurale netwerken elke continue functie op een compacte verzameling kunnen benaderen. Echter, deze stelling biedt geen kwantitatieve informatie over de grootte van het netwerk die nodig is voor een specifieke nauwkeurigheid. Latere werken hebben kwantitatieve benaderingsraten afgeleid voor ReLU-netwerken op $\alpha$-Hölder-continuïteitsfuncties, waarbij de benodigde grootte exponentieel afhangt van de dimensie van de invoerruimte ($N$).

In het domein van groep-equivariante en invariante learning worden neurale netwerken ontworpen om symmetrieën (zoals permutaties, translaties of rotaties) in de data te respecteren. Hoewel er veel onderzoek is gedaan naar de universaliteit van deze modellen (d.w.z. dat ze theoretisch elke equivariante functie kunnen benaderen), ontbreekt het aan kwantitatieve resultaten. De centrale vragen zijn:

1. Kan de extra aanname van invariance/equivariantie de benaderingsrate verbeteren voor standaard ReLU-netwerken (die niet per se equivariant zijn)?
2. Bereiken specifieke equivariante architecturen (zoals DeepSets, Transformers) dezelfde optimale rates als standaard netwerken, of leiden ze tot een verlies aan expressiviteit?

De intuïtie is dat de exponentiële afhankelijkheid van de dimensie $N$ vervangen zou moeten worden door een afhankelijkheid van de dimensie van de quotiëntruimte $N_G = \dim(V/G)$, aangezien de functiewaarde op een punt de waarden op de hele orbit bepaalt.

2. Methodologie

De auteurs analyseren de benaderingsraten voor $\alpha$-Hölder-functies in drie verschillende settings, gebruikmakend van de theorie van overdekkingsgetallen (covering numbers) en de structuur van de quotiëntruimte.

A. Permutatie-invariante en equivariante modellen (Point Sets)

• Context: Invoeren zijn verzamelingen van $n$ punten in $\mathbb{R}^d$ ($X \in \mathbb{R}^{d \times n}$). De groep $G$ is de permutatiegroep $S_n$.
• Methode: De auteurs analyseren het DeepSets-architectuur (invariant) en Sumformer/Transformer-architecturen (equivariant).
• Technische aanpak: Ze construeren een bewijs waarbij ze een discontinu karakteristieke functie benaderen door een continue ReLU-netwerk. Ze gebruiken een "digit-encoding" strategie om de som van kenmerken over punten te comprimeren tot een enkele waarde, gevolgd door een interpolatie-netwerk. Ze bewijzen dat DeepSets, ondanks zijn eenvoud en gebrek aan directe interactie tussen punten, de optimale rate bereikt.
• Resultaat voor niet-invariante functies: Als bijproduct verbeteren ze de bestaande rates voor het benaderen van functies op domeinen met lage intrinsieke dimensie (Minkowski-dimensie $d_{intrinsic}$) van $\mathcal{O}(\epsilon^{-d_{intrinsic}/\alpha})$ naar $\mathcal{O}(\epsilon^{-d_{intrinsic}/(2\alpha)})$.

B. Modellen invariant voor permutaties en stijve bewegingen (Rigid Motions)

• Context: Invoeren zijn puntenwolken invariant onder $E(d) \times S_n$ (rotaties, translaties en permutaties).
• Methode: De auteurs tonen eerst aan dat standaard ReLU-netwerken de rate $\sim (1/\epsilon)^{(nd - \dim(E(d)))/(2\alpha)}$ kunnen bereiken.
• Technische aanpak: Ze gebruiken een Gram-Schmidt-stabiliteitsanalyse. Ze tonen aan dat men een orthonormale basis kan construeren (via ReLU-netwerken) die de rotatie-invariantie "ontmantelt", waardoor het probleem gereduceerd wordt tot benadering op een lagere-dimensionale deelruimte (de quotiëntruimte).
• Frame Averaging: Ze analyseren modellen die gebruikmaken van "frames" (gemiddelde over een groep) gecombineerd met DeepSets. Ze bewijzen dat als de onderliggende niet-invariante functie goed benaderd kan worden, de frame-gegemiddelde versie dit ook doet, mits de frame-operatoren goed gedefinieerd zijn (bijv. via SVD of uitlijning).

C. Bi-Lipschitz invariante modellen

• Context: Een algemere setting voor gesloten isometriegroepen $G$.
• Methode: Gebruik van bi-Lipschitz invariante embeddings (zoals Max Filters of sortering).
• Technische aanpak: Ze tonen aan dat als er een bi-Lipschitz afbeelding $E: V \to \mathbb{R}^m$ bestaat die de quotiëntruimte $V/G$ isometrisch (of met beperkte vervorming) inbedt, dan kan elke invariante functie $f$ worden geschreven als $f = \psi \circ E$. Omdat $f \circ E^{-1}$ een Hölder-functie is op de ingebedde ruimte, kunnen standaard benaderingstheorieën worden toegepast.

3. Belangrijkste Bijdragen en Resultaten

De belangrijkste bevindingen zijn samengevat in Tabel 1 van het artikel:

1. Optimale Rates voor Standaard ReLU-netwerken:

   • Standaard ReLU-netwerken (die niet expliciet equivariant zijn ontworpen) bereiken de optimale benaderingsrate voor invariante functies. De rate hangt exponentieel af van de dimensie van de quotiëntruimte $N_G$, niet van de oorspronkelijke dimensie $N$.
   • Formule: Aantal parameters $\propto (1/\epsilon)^{N_G / (2\alpha)}$.

2. Expressiviteit van Equivariante Architecturen:

   • DeepSets: Bereikt dezelfde rate als standaard netwerken voor permutatie-invariante functies. Er is geen verlies aan expressiviteit door het hard-coden van permutatie-invariantie.
   • Sumformer & Transformer: Deze equivariante architecturen bereiken eveneens de optimale rates.
   • Frame-based modellen: Modellen die rotatie-invariantie forceren via frames (zoals SVD-gebaseerde methoden) bereiken de gewenste rates voor functies invariant onder $E(d) \times S_n$.
   • Bi-Lipschitz modellen: Modellen gebaseerd op bi-Lipschitz invariante embeddings (zoals Max Filters) bereiken de optimale rates, afhankelijk van de intrinsieke dimensie van de data.

3. Verbeterde Rate voor Intrinsieke Dimensie:

   • Voor functies gedefinieerd op een compacte verzameling $K$ met intrinsieke dimensie $d_{intrinsic}$, verbeteren de auteurs de bestaande rate van $\epsilon^{-d_{intrinsic}/\alpha}$ naar $\epsilon^{-d_{intrinsic}/(2\alpha)}$. Dit is een factor 2 verbetering in de exponent.

4. Betekenis en Conclusie

De paper sluit een belangrijke kloof in de theoretische machine learning door kwantitatieve benaderingsraten te leveren voor groep-equivariante learning.

• Expressiviteit vs. Sample Efficiency: De resultaten tonen aan dat het hard-coden van symmetrieën in de architectuur niet leidt tot een verlies aan expressiviteit of benaderingskracht vergeleken met standaard netwerken van dezelfde grootte. Standaard netwerken kunnen de symmetrieën van de data "leren" en dezelfde asymptotische rates bereiken.
• Praktische Implicatie: De voordelen van equivariante modellen in de praktijk (zoals betere generalisatie en lagere sample complexity) moeten dus worden toegeschreven aan optimalisatie-eigenschappen en sample efficiency, en niet aan een fundamenteel grotere expressiviteit per parameter.
• Toekomstig werk: De auteurs wijzen erop dat hoewel ze rates hebben voor frame-gebaseerde methoden, er nog geen rates zijn voor populaire modellen zoals EGNN, DimeNet of Vector Neurons, wat een richting is voor toekomstig onderzoek.

Kortom, de paper bevestigt dat equivariante architecturen theoretisch optimaal zijn voor het benaderen van symmetrische functies, en dat de keuze voor een equivariante architectuur voornamelijk een kwestie is van efficiëntie in training en data-gebruik, niet van fundamentele beperkingen in wat het model kan leren.