A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

Technische Samenvatting: Een functieruimte-dichotomie voor compositioneel leren

Probleemstelling
Een hardnekkige empirische observatie in deep learning is dat getrainde neurale netwerken consequent beter presteren dan hun Neural Tangent Kernel (NTK) limieten op taken met een compositionele of hiërarchische structuur. Terwijl de bestaande literatuur het gat tussen kernels en netwerken grotendeels toeschrijft aan de vloek van dimensionaliteit (waarbij kernels moeite hebben met laagdimensionale projecties van hoogdimensionale inputs), ontbrak een kwantitatieve verklaring voor het gat bij een vaste inputdimensie — specifiek gedreven door netwerkdiepte en compositionele structuur. Dit artikel behandelt de vraag: Op welke targets, en in welke mate, is de NTK suboptimaal, en welke specifieke eigenschap van die targets verhindert de kernel om deze te exploiteren?

Methodologie en Opzet
De auteurs analyseren dit probleem op de eenheidscirkel $S^1$, waar de NTK een heldere Fourier-beschrijving toelaat. Ze introduceren een dichotomie tussen twee complexiteitsmaten voor een doelfunctie $f^*$:

1. Fourier-complexiteit: Controleert de kosten van het leren via de NTK (lazy regime). De NTK Reproducing Kernel Hilbert Space (RKHS) norm blijkt (op een diepteafhankelijke constante) equivalent te zijn aan de Sobolev $H^1$ norm, die hoge-frequentie oscillaties bestraft.
2. Architecturale Complexiteit: Controleert de kosten van het leren via weight-decay training in het "rijke" regime. Dit wordt gemeten door de diepe variatie-norm ($RBV^2_{deep}$), die de omvang van de kleinste diepte-$L$, breedte-$w$ ReLU-netwerk kwantificeert die nodig is om de doelfunctie te construeren.

De auteurs definiëren de architectuurklasse $\mathcal{C}_{L,w,R}$ als diepte-$L$, breedte-$w$ ReLU-netwerken met een begrensde diepe variatie-norm $R$. Ze vergelijken de sample complexiteit van de NTK-schatter (Kernel Ridge Regression) met de minimax ondergrens voor deze architectuurklasse.

Belangrijkste Bijdragen

1. Minimax Karakterisering van Diepe Architectuurklassen:
   Het artikel stelt de minimax $L^2$ rate vast voor de klasse $\mathcal{C}_{L,w,R}$. De rate wordt vastgesteld tussen $\Omega(Lw^2R^2/n)$ en $\tilde{O}(L^2w^2R^2/n)$. Dit resultaat is nauwkeurig tot een factor $L$, wat de statistische bodem vertegenwoordigt voor elke estimator op deze klasse. Opvallend genoeg wordt deze rate geïndexeerd door architecturale parameters $(L, w, R)$ in plaats van target smoothness exponenten.

2. Exponentiële NTK Suboptimaliteit:
   De auteurs bewijzen dat de NTK-estimator exponentieel boven de minimax-bodem ligt wanneer de Fourier-complexiteit en de architecturale complexiteit van de target ontkoppeld zijn. Specifiek, voor een target met een dominante frequentie $k^*$, vereist de NTK $\Omega((k^*)^2)$ samples, terwijl de architectuurklasse slechts polynomiale middelen vereist in haar structurele parameters.

   • De Getuige: De diepte-$L$ iteratieve zaagtandfunctie (Telgarsky 2016) dient als de analytische getuige. Deze kan worden geconstrueerd door een breedte-2, diepte-$L$ netwerk met $O(L)$ gewichten (lage architecturale complexiteit), maar oscilleert $2^{L-1}$ keer (exponentiële Fourier-complexiteit).
   • Het Gat: Voor de zaagtand vereist de NTK $\Omega(4^L)$ samples, terwijl de minimax-bodem polynomiaal is in $L$ (tussen $L^3$ en $L^4$). Dit levert een exponentiële separatie in sample complexiteit op.

3. Empirische Validatie:
   Numerieke experimenten bevestigen de theoretische claims op drie fronten:

   • NTK Spectrum: De eigenvalue decay van de NTK op $S^1$ volgt de voorspelde $k^{-2}$ decay, wat het "deep equals shallow" fenomeen bevestigt: diepte verandert de spectrale decay rate niet.
   • Smooth Targets: Op bandlimited (gladde) targets is de NTK concurrerend met of beter dan brede netwerken, waarbij geen exponentieel gat optreedt.
   • Compositionele Targets: Op het sparse parity model over de hypercube (een ander domein waar SGD bekend staat succesvol te zijn), verslaat een standaard twee-lagen netwerk de NTK met vier tot zes ordes van grootte in testfout, waarmee de voorspelde separatie end-to-end wordt gerealiseerd.

Resultaten en Betekenis
Het artikel concludeert dat het prestatiegat tussen NTK en getrainde netwerken geen generiek "kernel-versus-netwerk" fenomeen is, maar een specifieke functieruimte-eigenschap. Het gat ontstaat door een mismatch tussen de inherente smoothness bias van de kernel (die voorkeur geeft aan lage-frequentie functies) en de compositionele structuur van de target (die met lage architecturale kosten hoge-frequentie oscillaties kan genereren).

• Theoretisch Inzicht: Het werk biedt een precies mechanisme waarom diepte helpt: het stelt netwerken in staat om hoge-frequentie, oscillerende functies goedkoop te representeren via compositie, een capaciteit die de NTK (die zich gedraagt als een vaste Sobolev-kernel) mist.
• Minimax Bodem: De afleiding van de minimax rate voor de diepe variatie-ruimte wordt gepresenteerd als een zelfstandige bijdrage, die een directe, kernel-vrije schatting biedt van de sample complexiteit voor compositionele problemen op basis van architecturale parameters.
• Reikwijdte: De auteurs verduidelijken dat het gat niet universeel is; het verdwijnt voor gladde, bandlimited targets waar Fourier- en architecturale complexiteiten op één lijn liggen. Bovendien maken ze een onderscheid tussen statistische limieten en algoritmische haalbaarheid, waarbij ze opmerken dat hoewel de zaagtand statistisch leerbaar is door de architectuurklasse, het berucht moeilijk is voor gradient descent om te optimaliseren, terwijl de sparse parity zowel statistisch als algoritmisch leerbaar is.

Samenvattend betogen de auteurs dat de NTK nabij optimaal is voor $H^1$-smooth targets, maar exponentieel suboptimaal voor targets waar compositionele structuur "goedkope" hoge-frequentie representaties mogelijk maakt, een regime waarin training in het rijke regime statistisch noodzakelijk is.