Highly Adaptive Principal Component Regression

Riepilogo Tecnico: Regressione ai Componenti Principali Altamente Adattiva

Enunciato del Problema
Il Lasso Altamente Adattivo (HAL) è un metodo di regressione non parametrico capace di raggiungere tassi di convergenza indipendenti dalla dimensionalità sotto ipotesi minime di regolarità (norma di variazione sezionale limitata). Tuttavia, la sua implementazione diretta è computazionalmente proibitiva in dimensioni elevate. La matrice di design HAL $H$ ha dimensioni $n \times p$, dove $p = n(2^d - 1)$ per $d$ covariate. Costruire questa matrice e risolvere il conseguente problema di ottimizzazione penalizzato con $\ell_1$ ad alta dimensionalità (anche con discesa di coordinate efficiente) diventa impraticabile all'aumentare di $n$ e $d$. Sebbene lo stimatore Ridge Altamente Adattivo (HAR) offra un'alternativa kernelizzata sostituendo la penalità $\ell_1$ con una penalità $\ell_2$, richiede comunque di lavorare con una matrice kernel $n \times n$, $K = HH^\top$, che può essere computazionalmente intensiva per grandi $n$ e manca delle proprietà di induzione della sparsità del Lasso.

Metodologia
Gli autori propongono due nuovi stimatori, Lasso Altamente Adattivo ai Componenti Principali (PCHAL) e Ridge Altamente Adattivo ai Componenti Principali (PCHAR), che affrontano questi colli di bottiglia computazionali attraverso una riduzione della dimensionalità "cieca all'outcome" della base HAL.

1. Decomposizione Kernel e Spettrale:
   Il metodo sfrutta la rappresentazione kernel di HAL/HAR. Sia $H \in \{0, 1\}^{n \times p}$ la matrice di design HAL. La matrice di Gram (kernel) associata è $K = HH^\top \in \mathbb{R}^{n \times n}$. Gli elementi di $K$ ammettono una valutazione in forma chiusa:
   $$K(x, x') = \sum_{i=1}^n (2^{|S_i(x, x')|} - 1)$$
   dove $S_i(x, x')$ è l'insieme delle coordinate attive sulla coppia di punti $(x, x')$.

2. Riduzione ai Componenti Principali:
   Invece di lavorare nello spazio delle caratteristiche completo a $p$ dimensioni o nello spazio kernel completo a $n$ dimensioni, gli autori approssimano $K$ utilizzando i suoi primi $k$ componenti principali. Sia $H = U D^{1/2} V^\top$ la decomposizione ai valori singolari (SVD) di $H$. Il metodo proietta il problema di regressione sullo spazio ortogonale delle score a $k$ dimensioni definito dalle prime $k$ colonne di $U$ (denotate $U_k$) e dai corrispondenti valori singolari $D_k$.
   La mappa delle caratteristiche PC è definita come $z_k(x) = V_k^\top h(x)$, dove $h(x)$ è il vettore delle caratteristiche HAL. Crucialmente, $z_k$ può essere calcolato direttamente dalla matrice kernel $K$ senza formare esplicitamente $H$ o $V$.

3. Stimatori:

   • PCHAR: Uno stimatore penalizzato con $\ell_2$ nello spazio PC a $k$ dimensioni. A causa dell'ortogonalità delle score PC, questo ammette una soluzione ridge in forma chiusa:
     $$\hat{\beta}_{PCHAR} = (D_k + n\lambda I_k)^{-1} D_k^{1/2} U_k^\top Y$$
   • PCHAL: Uno stimatore penalizzato con $\ell_1$ nello spazio PC a $k$ dimensioni. Poiché la matrice di design nello spazio PC ($Z_k = U_k D_k^{1/2}$) ha colonne ortogonali, il problema Lasso si disaccoppia in una soglia morbida componente per componente:
     $$\hat{\beta}_{PCHAL, j} = \frac{\text{sign}(Z_{k,j}^\top Y)}{d_j} (|Z_{k,j}^\top Y| - n\lambda)_+$$
     Queste soluzioni in forma chiusa eliminano la necessità di ottimizzazione iterativa durante l'adattamento del modello e la convalida incrociata.

4. Varianti di Regularizzazione:
   Il paper introduce anche una variante di discesa del gradiente con arresto anticipato. Invece di selezionare un cutoff rigido $k$, questo metodo utilizza tutti i componenti principali e regolarizza fermando la discesa del gradiente a una specifica iterazione $t$. Ciò induce un percorso di regolarizzazione spettrale fluido dove le direzioni con autovalori grandi entrano nell'adattamento rapidamente, mentre le direzioni con autovalori piccoli (suscettibili al rumore) vengono ritardate.

5. Previsione:
   Per prevedere su nuovi dati senza costruire la massiccia matrice $H'$, il metodo utilizza la matrice cross-kernel $K' = H' H^\top$. La previsione è calcolata come $\hat{f}' = K' U_k D_k^{-1/2} \hat{\beta}$, evitando la costruzione esplicita di caratteristiche ad alta dimensionalità.

Contributi Chiave

• Efficienza Computazionale: PCHAL e PCHAR riducono il costo computazionale di HAL/HAR proiettando il problema in uno spazio ortogonale a rango ridotto. Ciò permette soluzioni in forma chiusa ed evita l'ottimizzazione iterativa, accelerando significativamente la convalida incrociata.
• Struttura Cieca all'Outcome: L'embedding ai componenti principali è determinato interamente dalle covariate (tramite la geometria della base HAL) ed è indipendente dalla risposta $Y$. Ciò fornisce una riparametrizzazione universale e guidata dalla geometria del campione.
• Connessione Teorica al Moto Browniano: Gli autori scoprono che in circostanze speciali (specificamente quando il campione può essere totalmente ordinato coordinatamente), la matrice di Gram HAL di ordine zero è un multiplo scalare della matrice $A_{ij} = \min(i, j)$. Questa matrice è la covarianza discreta di un cammino casuale, e i suoi autovettori sono funzioni seno discrete, che corrispondono all'espansione di Karhunen–Loève del moto browniano.
• Ottimalità Oracle: Il paper stabilisce che per una libreria fissa di ordini di interazione e parametri di regolarizzazione, il selettore convalidato incrociatamente è asintoticamente oracle-ottimale nel rischio.

Risultati Empirici
Gli autori valutano PCHAL e PCHAR su una raccolta di dataset di regressione reali (ad esempio blog, boston, energy, kin8nm, naval, yearmsd) confrontandoli con baseline che includono ridge kernel HAR, ridge standard, ridge kernel gaussiano, k-vicini più prossimi, foreste casuali, GAM, MARS e XGBoost.

• Prestazioni: Gli stimatori basati su PC si comportano in modo stabile attraverso i dataset. Sebbene raramente siano il singolo metodo migliore, evitano costantemente gravi degradazioni delle prestazioni e rimangono vicini ai benchmark HAL/HAR completi.
• Confronto: A differenza di alcuni apprendisti concorrenti (ad esempio metodi basati su alberi) che mostrano alta variabilità tra i dataset, PCHAL/PCHAR mantengono prestazioni robuste. Su dataset dove HAL/HAR è computazionalmente impraticabile da eseguire direttamente, questi metodi offrono un'alternativa praticabile con prestazioni empiriche comparabili.

Significato e Affermazioni
Il paper afferma che PCHAL e PCHAR offrono un percorso pratico per sfruttare i vantaggi statistici di HAL (tassi indipendenti dalla dimensionalità e adattabilità a bassa regolarità) senza i costi computazionali proibitivi della base completa. Sfruttando la struttura spettrale del kernel HAL, il metodo raggiunge:

1. Scalabilità: Rende la regressione stile HAL fattibile per dimensioni campionarie più grandi e dimensioni più elevate riducendo il problema a uno spazio ortogonale a bassa dimensionalità.
2. Efficienza Statistica: I risultati teorici suggeriscono che la riduzione ai componenti principali non sacrifica i tassi di convergenza che motivano HAL, purché valgano appropriate ipotesi di controllo della complessità.
3. Interpretabilità: La connessione al moto browniano e il percorso di regolarizzazione spettrale fluido offrono nuove intuizioni teoriche sul comportamento degli stimatori non parametrici adattivi.

Gli autori sottolineano che il metodo è "cieco all'outcome", il che significa che la riduzione delle caratteristiche è guidata esclusivamente dalla geometria delle covariate, semplificando il processo di adattamento e permettendo soluzioni efficienti in forma chiusa non disponibili nelle implementazioni HAL standard.