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

Sintesi Tecnica: Una dicotomia degli spazi di funzioni per l'apprendimento composizionale

Problema
Un'osservazione empirica persistente nel deep learning è che le reti neurali addestrate superano costantemente i limiti del loro Neural Tangent Kernel (NTK) in compiti con struttura composizionale o gerarchica. Mentre la letteratura esistente attribuisce i gap tra kernel e reti principalmente alla maledizione della dimensionalità (dove i kernel faticano con proiezioni a bassa dimensione di input ad alta dimensione), mancava un resoconto quantitativo del gap a dimensione dell'input fissa — specificamente guidato dalla profondità della rete e dalla struttura composizionale. Questo articolo affronta la domanda: Su quali target, e per quanto, il NTK è sub-ottimale, e quale proprietà specifica di quei target impedisce al kernel di sfruttarli?

Metodologia e Setup
Gli autori analizzano questo problema sul cerchio unitario $S^1$, dove il NTK ammette una descrizione di Fourier pulita. Introducono una dicotomia tra due misure di complessità per una funzione target $f^*$:

1. Complessità di Fourier: Controlla il costo dell'apprendimento tramite il NTK (regime lazy). Si dimostra che la norma dell'RKHS del NTK è equivalente (fino a una costante dipendente dalla profondità) alla norma Sobolev $H^1$, che penalizza le oscillazioni ad alta frequenza.
2. Complessità Architetturale: Controlla il costo dell'apprendimento tramite l'addestramento con decadimento del peso (weight-decay) nel regime "ricco" (rich regime). Questa è misurata tramite la norma di variazione profonda ($RBV^2_{deep}$), che quantifica la dimensione della più piccola rete ReLU di profondità-$L$ e larghezza-$w$ necessaria per costruire il target.

Gli autori definiscono la classe di architettura $\mathcal{C}_{L,w,R}$ come reti ReLU di profondità-$L$, larghezza-$w$ con una norma di variazione profonda limitata $R$. Confrontano la complessità campionaria dell'estimatore NTK (Kernel Ridge Regression) rispetto al limite inferiore minimax per questa classe di architettura.

Contributi Chiave

1. Caratterizzazione Minimax delle Classi di Architettura Profonda:
   L'articolo stabilisce il tasso minimax $L^2$ per la classe $\mathcal{C}_{L,w,R}$. Il tasso è fissato tra $\Omega(Lw^2R^2/n)$ e $\tilde{O}(L^2w^2R^2/n)$. Questo risultato è stretto fino a un singolo fattore di $L$, rappresentando il pavimento statistico per qualsiasi estimatore su questa classe. Notevolmente, questo tasso è indicizzato da parametri architetturali $(L, w, R)$ piuttosto che da esponenti di regolarità del target.

2. Sub-ottimalità Esponenziale del NTK:
   Gli autori dimostrano che l'estimatore NTK si posiziona esponenzialmente sopra il pavimento minimax ogni volta che la complessità di Fourier e la complessità architetturale del target si disaccoppiano. Specificamente, per un target con frequenza dominante $k^*$, il NTK richiede $\Omega((k^*)^2)$ campioni, mentre la classe di architettura richiede solo risorse polinomiali nei suoi parametri strutturali.

   • Il Testimone (Witness): La funzione a dente di sega iterata di profondità-$L$ (Telgarsky 2016) funge da testimone analitico. Può essere costruita da una rete di larghezza-2 e profondità-$L$ con $O(L)$ pesi (bassa complessità architetturale) ma oscilla $2^{L-1}$ volte (esponenziale complessità di Fourier).
   • Il Gap: Per il dente di sega, il NTK richiede $\Omega(4^L)$ campioni, mentre il pavimento minimax è polinomiale in $L$ (tra $L^3$ e $L^4$). Ciò produce una separazione esponenziale nella complessità campionaria.

3. Validazione Empirica:
   Gli esperimenti numerici confermano le affermazioni teoriche su tre fronti:

   • Spettro NTK: Il decadimento degli autovalori del NTK su $S^1$ segue il decadimento previsto $k^{-2}$, confermando il fenomeno "deep equals shallow" dove la profondità non altera il tasso di decadimento spettrale.
   • Target Smooth: Su target band-limited (smooth), il NTK è competitivo con o migliore delle reti larghe, non mostrando alcun gap esponenziale.
   • Target Composizionali: Sul modello di parità sparsa sull'ipercubo (un dominio diverso dove SGD è noto per avere successo), una rete standard a due strati batte il NTK di quattro o sei ordini di grandezza in errore di test, realizzando la separazione prevista end-to-end.

Risultati e Significato
L'articolo conclude che il gap di performance tra NTK e reti addestrate non è un fenomeno generico "kernel-contro-rete", ma una specifica proprietà dello spazio delle funzioni. Il gap deriva da un disallineamento tra il bias di regolarità intrinseco del kernel (che favorisce funzioni a bassa frequenza) e la struttura composizionale del target (che può generare oscillazioni ad alta frequenza con basso costo architetturale).

• Insight Teorico: Il lavoro fornisce un meccanismo preciso per cui la profondità aiuta: permette alle reti di rappresentare funzioni oscillanti ad alta frequenza a basso costo tramite composizione, una capacità che il NTK (che si comporta come un kernel Sobolev fisso) non possiede.
• Pavimento Minimax: La derivazione del tasso minimax per lo spazio di variazione profonda è presentata come un contributo autonomo, offrendo una stima diretta, priva di kernel, della complessità campionaria per problemi composizionali basata su parametri architetturali.
• Ambito: Gli autori chiariscono che il gap non è universale; scompare per target smooth e band-limited dove le complessità di Fourier e architetturale sono allineate. Inoltre, distinguono tra limiti statistici e fattibilità algoritmica, notando che mentre il dente di sega è statisticamente apprendibile dalla classe di architettura, è notoriamente difficile da ottimizzare per il gradiente discendente, mentre la parità sparsa è sia statisticamente che algoritmicamente apprendibile.

In sintesi, l'articolo sostiene che il NTK è vicino all'ottimalità per target $H^1$-smooth, ma esponenzialmente sub-ottimale per target in cui la struttura composizionale permette rappresentazioni ad alta frequenza "economiche", un regime in cui l'addestramento nel regime ricco è statisticamente necessario.