Compositional Approximation Can Strictly Outperform Superpositional Approximation

Sintesi Tecnica: L'approssimazione composizionale può superare strettamente l'approssimazione sovrapposizionale

Enunciato del problema
Il saggio affronta una questione fondamentale nella teoria dell'approssimazione: in quali condizioni i metodi composizionali (come le reti neurali) forniscono tassi di approssimazione strettamente superiori rispetto ai metodi sovrapposizionali (combinazioni lineari di elementi di un dizionario, ad esempio l'approssimazione M-term). Sebbene l'evidenza empirica suggerisca che le reti neurali siano potenti, le giustificazioni teoriche spesso si basano sull'emulazione di metodi esistenti, ottenendo tassi comparabili ma non superiori. Inoltre, molte classi di funzioni classiche ammettono dizionari che producono tassi di approssimazione M-term ottimali. Gli autori cercano di identificare le proprietà strutturali delle classi di funzioni in cui l'approssimazione composizionale può superare strettamente qualsiasi approssimazione sovrapposizionale, anche sotto vincoli che garantiscano un'efficiente codifica a stringa di bit dei parametri (prevenendo la costruzione banale "brute-force" di dizionari).

Metodologia e Framework
Gli autori stabiliscono un rigoroso framework matematico all'interno di uno spazio di Hilbert $H$ per confrontare gli schemi di approssimazione:

1. Tassi di approssimazione: Definiscono il tasso di approssimazione $\gamma(C, S)$ come l'ordine di decadimento polinomiale dell'errore uniforme in funzione del budget dei parametri $M$.
2. Schemi sovrapposizionali: Sono definiti come combinazioni lineari a $M$ termini di elementi di un dizionario $D = (\phi_i)_{i \in \mathbb{N}}$, soggetti a un vincolo di "ricerca della profondità polinomiale" (polynomial depth search). Questo vincolo limita gli indici e le dimensioni dei coefficienti degli elementi del dizionario utilizzati a un polinomio di $M$, garantendo che l'approssimante possa essere codificato come una stringa di bit di lunghezza $O(M \log^q M)$. Il tasso di approssimazione Riesz ($\gamma_{\text{Riesz}}$) è il supremo dei tassi realizzabili da qualsiasi dizionario che soddisfi un limite inferiore di Riesz (garantendo la stabilità).
3. Schemi composizionali: Sono modellati tramite reti neurali con vincoli sulla profondità (polilogaritmica in $M$), connettività (lineare in $M$) e magnitudo dei pesi (polinomiale in $M$). Ciò garantisce una simile efficienza di codifica in stringhe di bit.
4. Prospettiva geometrica: Il nucleo dell'intuizione teorica risiede nella geometria asintotica della classe di funzioni. Gli autori sostengono che se una classe di funzioni può essere $\epsilon$-approssimata da una unione di un numero limitato di sottospazi lineari a bassa dimensionalità (una struttura sfruttabile dalla composizione) ma richiede un sottospazio lineare ad alta dimensionalità per l'approssimazione lineare, può esistere un divario nei tassi. Ciò è legato al concetto di "numeri di copertura" (covering numbers), dove l'insieme non lineare degli approssimanti è infinitamente piccolo rispetto allo spazio lineare necessario quando $\epsilon \to 0$.

Contributi Chiave e Risultati

1. La costruzione SPOON: Gli autori introducono un insieme prototipico di strutture chiamato SPOON (Superpolynomially growing almost Orthogonal sequeNce). Una SPOON consiste in una sequenza di insiemi $V_m$ dove:

   • La cardinalità cresce super-polinomialmente ($|V_m| \ge 2^{m^\alpha}$).
   • Gli elementi hanno norme che decadono come $m^{-\mu}$.
   • Gli elementi sono $\eta$-quasi-ortogonali tra loro, con il limite del prodotto interno che decade come $m^{-\nu}$.

2. Limite superiore sui tassi sovrapposizionali (Teorema 3.4): Il risultato teorico centrale dimostra che se una classe di funzioni $C$ contiene una $(\mu, \nu)$-SPOON, il miglior tasso di approssimazione Riesz realizzabile è limitato da:
   $$\gamma_{\text{Riesz}}(C) \le \frac{1}{2} + \frac{\mu}{\nu}$$
   La prova utilizza un argomento per contraddizione che coinvolge la geometria di insiemi quasi ortogonali e le proprietà dei dizionari Riesz. Dimostra che qualsiasi dizionario che soddisfi la condizione di Riesz non può coprire efficientemente gli insiemi quasi ortogonali esponenzialmente grandi all'interno della SPOON utilizzando solo un numero polinomiale di termini.

3. Costruzione esplicita (Sezione 4): Gli autori costruiscono classi di funzioni esplicite $V(k, \alpha, \beta, \mu)$ usando composizioni di una funzione "hat" $f$. Queste classi sono formate da composizioni iterate di funzioni definite da vettori binari.

   • Dimostrano che queste classi contengono grandi insiemi di funzioni quasi ortogonali che soddisfano le condizioni della SPOON.
   • Dimostrano che le reti neurali ReLU possono approssimare queste classi con un tasso $\gamma_{\rho}^N \ge \frac{\mu}{\alpha}$.
   • Combinando ciò con il limite superiore, mostrano che per specifiche scelte di parametri (ad esempio $\mu = \sqrt{k}$), il divario tra i tassi composizionale e Riesz diventa arbitrariamente grande all'aumentare della profondità di composizione $k$. Nello specifico, $\lim_{k \to \infty} \gamma_{\rho}^N = \infty$ mentre $\lim_{k \to \infty} \gamma_{\text{Riesz}} \le \frac{1}{2}$.

4. Esempio di ortogonalità patologica (Appendice A): Il saggio presenta anche un esempio più semplice, sebbene più patologico, che coinvolge un sistema ortonormale in cui i coefficienti decadono logaritmicamente. In questo caso, l'approssimazione sovrapposizionale produce un tasso di $-\infty$ (nessun decadimento polinomiale), mentre le reti neurali ottengono un tasso positivo, evidenziando la difficoltà che i metodi sovrapposizionali incontrano con strutture altamente ortogonali.

Significato e Rivendicazioni
Il saggio sostiene di fornire i primi esempi espliciti di classi di funzioni in cui l'approssimazione composizionale supera strettamente l'approssimazione sovrapposizionale, anche quando al metodo sovrapposizionale è permesso scegliere il dizionario ottimale sotto vincoli di stabilità (Riesz) e di codifica.

La significatività risiede nell'identificazione di una proprietà strutturale specifica — la presenza di grandi insiemi quasi ortogonali all'interno di sottospazi a dimensione finita — che è intrinsecamente difficile da catturare efficientemente per le combinazioni lineari ma che viene gestita naturalmente dalla composizione gerarchica di elementi costruttivi semplici. Gli autori sostengono che questo disallineamento strutturale spieghi perché le reti neurali possano ottenere tassi migliori senza fare affidamento su instabilità o codifica di parametri illimitata. Il lavoro suggerisce che il vantaggio delle reti neurali non è meramente l'approssimazione universale, ma una specifica adattabilità geometrica a classi di funzioni con questa struttura "quasi ortogonale".

Gli autori mantengono un tono modesto riguardo all'ambito di applicazione, osservando che i loro risultati si applicano a classi di funzioni contenenti queste specifiche strutture SPOON, e che gli attuali limiti sui tassi sovrapposizionali sono ristretti ai dizionari Riesz, sebbene ritengano che questo sia un limite tecnico piuttosto che fondamentale. Non affermano che questi risultati si applichino a tutte le classi di funzioni o che le reti neurali siano universalmente superiori, ma che sono superiori per le classi che esibiscono questa specifica struttura geometrica asintotica.