Which Spaces can be Embedded in $L_p$-type Reproducing Kernel Banach Space? A Characterization via Metric Entropy

Sintesi Tecnica: "Quali spazi possono essere incorporati in uno Spazio di Ricerca di Kernel di tipo $\mathcal{L}_p$? Una caratterizzazione tramite l'entropia metrica"

Problema
Il saggio affronta una questione fondamentale nelle basi teoriche del machine learning: determinare l'ambito e i limiti degli Spazi di Ricoli di Kernel di tipo Banach (RKBS), specificamente gli RKBS di tipo $\mathcal{L}_p$, come framework di modellazione per classi di funzioni apprendibili. Sebbene gli RKBS offrano un framework flessibile per caratterizzare stimatori complessi (come le reti neurali) e offrano vantaggi rispetto agli spazi di Hilbert (ad esempio, la sparsità tramite norme $\ell_p$), rimane poco chiaro se gli RKBS di tipo $\mathcal{L}_p$ siano sufficientemente generali da incorporare arbitrari spazi di funzioni che siano apprendibili in modo efficiente.

La letteratura esistente stabilisce che l'incorporamento di uno spazio di funzioni in uno Spazio di Ricerca di Kernel di Hilbert (RKHS) implica un limite specifico sulla crescita della sua entropia metrica. Tuttavia, il inverso — ovvero se un limite sulla crescita dell'entropia metrica implichi l'incorporamento in un tipo specifico di spazio di Banach — non è stato pienamente caratterizzato per un $p$ generale. Gli autori cercano di rispondere alla domanda: Ogni classe di funzioni apprendibile con un numero polinomiale di punti dati (rispetto all'eccesso di rischio) può essere incorporata in un RKBS di tipo $\mathcal{L}_p$?

Metodologia
Gli autori stabiliscono una nuova connessione tra l'entropia metrica e l'incorporamento di spazi di funzioni in RKBS di tipo $\mathcal{L}_p$. La metodologia procede attraverso i seguenti passaggi logici:

1. Dall'entropia metrica alla complessità di Rademacher: Gli autori generalizzano i risultati classici (Lemma di Massart e Teorema di Chaining di Dudley) ad spazi di Banach astratti. Dimostrano che se l'entropia metrica di una palla unitaria in uno spazio di Banach $E$ (misurata in uno spazio target $F = \ell_\infty(\Omega)$) cresce polinomialmente come $\mathcal{E}_E^F(\delta) \leq \delta^{-p}$ per $p \geq 2$, allora la complessità di Rademacher dello spazio decade a un tasso di $n^{-1/p}$.
2. Dalla complessità di Rademacher al Tipo di spazio di Banach: Un contributo tecnico chiave è un nuovo lemma che mostra come un limite sulla norma di Rademacher implichi il Tipo dello spazio di Banach. Nello specifico, se la complessità di Rademacher decade come $n^{-1/p'}$, lo spazio (dotato della norma target) è di Tipo $s'$ per ogni $s' < p'$.
3. Dal Tipo all'incorporamento di tipo $\mathcal{L}_p$: Sfruttando il Teorema 3 (una conseguenza del Teorema di Dominazione di Pietsch e del Teorema di Maurey-Pisier), gli autori utilizzano la proprietà di Tipo stabilita per costruire un embedding isomorfico dello spazio di ipotesi in un sottospazio chiuso di $\mathcal{L}_{s'}(\mu)$.
4. Costruzione dell'RKBS: Utilizzando il teorema di estensione di Hahn-Banach e la dualità tra $\mathcal{L}_{s'}$ e $\mathcal{L}_s$ (dove $1/s + 1/s' = 1$), costruiscono una mappa di feature $\Phi: \Omega \to \mathcal{L}_s(\mu)$. Questa mappa di feature induce un RKBS di tipo $\mathcal{L}_s$ tale che l'originale spazio $E$ si incorpora in $\mathcal{B}_s$, il quale a sua volta si incorpora nello spazio delle funzioni limitate $\ell_\infty(\Omega)$.

Contributi Chiave

• Caratterizzazione Inversa: Il saggio prova un inverso ai risultati classici degli RKHS. Mentre l'incorporamento in un RKHS implica un limite sull'entropia metrica, gli autori dimostrano che un limite polinomiale sulla crescita dell'entropia metrica ($\delta^{-p}$) è sufficiente a garantire l'incorporamento in un RKBS di tipo $\mathcal{L}_s$ per qualche $s > p$.
• Framework Unificato tramite Entropia Metrica: A differenza degli approcci precedenti che si basano su specifiche proprietà geometriche (come i controlli di Tipo-2) che variano tra i diversi spazi di funzioni, questo lavoro fornisce un approccio unificato basato sull'entropia metrica per determinare l'incorporabilità.
• Collegare l'Apprendibilità alla Geometria: Gli autori collegano il concetto di "apprendibilità polinomiale" (apprendimento con un dataset polinomialmente grande rispetto all'errore) direttamente alla struttura geometrica degli RKBS di tipo $\mathcal{L}_p$. Mostrano che qualsiasi classe di funzioni apprendibile in questo regime possiede i necessari limiti di entropia metrica per essere incorporata in tali spazi.

Risultati Principali

• Teorema 4: Dato un dominio limitato $\Omega \subset \mathbb{R}^d$ e un RKBS $E$ che si incorpora compattamente in $F = \ell_\infty(\Omega)$, se la crescita dell'entropia metrica è limitata da $\mathcal{E}_E^F(\delta) \leq \delta^{-p}$ per $p \geq 2$, allora per ogni $s > p$, esiste un RKBS di tipo $\mathcal{L}_s$ tale che $E \hookrightarrow \mathcal{B}_s \hookrightarrow F$.
• Implicazione per l'Apprendibilità: Poiché l'apprendibilità polinomiale implica limiti polinomiali sull'entropia metrica, il risultato conferma che gli RKBS di tipo $\mathcal{L}_p$ costituiscono una classe di modelli potente ed espressiva, capace di rappresentare qualsiasi classe di funzioni apprendibile in modo efficiente.
• Limiti Tecnici: Il saggio fornisce limiti espliciti che mettono in relazione l'esponente dell'entropia $p$ con il parametro $s$ dell'RKBS richiesto, mostrando che $s$ può essere scelto arbitrariamente vicino a $p$ (specificamente $s > p$).

Significatività e Rivendicazioni
Gli autori affermano che i loro risultati gettano nuova luce sul potere e sui limiti dei metodi kernel per l'apprendimento di spazi di funzioni complessi. Stabilendo che gli RKBS di tipo $\mathcal{L}_p$ sono sufficientemente generali da modellare qualsiasi classe di funzioni con un controllo (polinomiale) dell'entropia metrica, il saggio valida l'uso di questi spazi come un ampio framework teorico per il machine learning.

La significatività risiede nella praticità della caratterizzazione: stimare l'entropia metrica è spesso più agevole in pratica (ad esempio, per gli spazi classici di Sobolev e Besov) rispetto alla ricerca di embedding espliciti. Pertanto, questo lavoro fornisce una condizione verificabile per determinare se uno specifico spazio di funzioni può essere efficacemente modellato utilizzando RKBS di tipo $\mathcal{L}_p$. Gli autori sottolineano come questo approccio unifichi lo studio delle proprietà degli spazi di funzioni, la teoria dell'apprendimento e gli embedding in contesti non-Hilbert, offrendo un framework più versatile rispetto alle precedenti caratterizzazioni basate sul Tipo-2.