Proximal Projection for Doubly Sparse Regularized Models

Riepilogo Tecnico: Proiezione Prossimale per Modoli con Regolarizzazione Doppia Sparsa

Enunciato del Problema
In contesti di regressione ad alta dimensionalità dove il numero di predittori ($p$) supera la dimensione del campione ($n$), i minimi quadrati ordinari (OLS) standard falliscono a causa di singolarità e multicollinearità. Sebbene i metodi di regolarizzazione come LASSO (penalità $l_1$) e Ridge (penalità $l_2$) affrontino la sparsità e la stabilità, spesso ignorano le relazioni strutturali sottostanti tra i predittori. Quando i predittori possono essere rappresentati da un modello grafico gaussiano, sfruttare tale struttura migliora la stima.

Gli approcci esistenti, come la Regressione Sparsa che Incorpora la Struttura Grafica (SRIG) e la sua estensione a doppia sparsità (DSRIG), decompongono il vettore dei coefficienti $\beta$ in variabili latenti corrispondenti ai contributi dei nodi e applicano la regolarizzazione su queste variabili latenti. Tuttavia, il modello DSRIG, che ottiene la "doppia sparsità" (sparsità tra gruppi e all'interno dei gruppi), si basa sulla duplicazione dei predittori per gestire gruppi sovrapposti. Questo approccio diventa computazionalmente proibitivo per dati ad alta dimensionalità o grafi densi, poiché aumenta significativamente la dimensionalità del problema di ottimizzazione. Inoltre, DSRIG richiede la regolazione di due parametri ($\lambda$ e $\xi$) per bilanciare la sparsità tra gruppi e all'interno dei gruppi, complicando la ricerca di soluzioni ottimali.

Metodologia
Gli autori propongono il modello LASSO a Gruppi Sovrapposti Sparsi che Incorpora la Struttura Grafica (SGLIG). Questo modello riparametrizza il framework DSRIG per mantenere la doppia sparsità riducendo al contempo la complessità computazionale e il numero di parametri di regolazione.

1. Formulazione del Modello:
   Il modello SGLIG minimizza la funzione obiettivo:
   $$\min_{\beta, V^{(1)}, \dots, V^{(p)}} \frac{1}{2n}\|Y - X\beta\|_2^2 + \lambda^* \sum_{i=1}^p \left( \alpha \tau_i \|V^{(i)}\|_2 + (1-\alpha) \frac{1}{\sqrt{d_i}} \|V^{(i)}\|_1 \right)$$
   dove $\beta = \sum V^{(i)}$, $V^{(i)}$ rappresenta il contributo del predittore $i$, $d_i$ è il grado del vicinato, e $\alpha \in [0, 1]$ controlla il compromesso tra le penalità $l_2$ (gruppo) e $l_1$ (all'interno del gruppo). A differenza di DSRIG, SGLIG utilizza un singolo parametro di regolazione $\alpha$ (con $\lambda^*$ fissato come costante basata su $\lambda_{max}$), semplificando la ricerca sulla griglia di ottimizzazione.

2. Algoritmo Prossimale Doppio Proiettato:
   Per ottimizzare l'obiettivo SGLIG, gli autori sviluppano un Algoritmo Prossimale Doppio Proiettato basato su FISTA (Fast Iterative Shrinkage-Thresholding Algorithm).

   • Strategia del Gruppo Attivo: L'algoritmo identifica un insieme attivo di gruppi $\hat{G}_m$ basato sui gradiente attuali.
   • Proiezione sull'Intersezione: Invece di duplicare i predittori, l'algoritmo calcola l'operatore prossimale proiettando sull'intersezione di insiemi convessi definiti da sfere di norme $l_2$ e $l_\infty$.
   • Proiezione a Due Stadi: La proiezione viene calcolata sequenzialmente: prima applicando la soglia morbida per la sparsità all'interno del gruppo ($l_1$/$l_\infty$), seguita dalla soglia morbida di gruppo per la sparsità tra gruppi ($l_2$). Ciò è implementato utilizzando una sequenza di composizioni (POCS) piuttosto che l'algoritmo parallelo simile a Dykstra, che gli autori ritengono più efficiente per la loro strategia di insieme attivo.

3. Proprietà Teoriche:
   Il documento deriva un limite di errore su campioni finiti per lo stimatore SGLIG sotto assunzioni di decomposizione ottimale, convessità forte ristretta (RSC) e limiti specifici sui pesi $\tau_i$ e sui gradi dei nodi. Inoltre, gli autori dimostrano la normalità asintotica dello stimatore quando $n \to \infty$ con $p$ fissato, mostrando coerenza con il modello SRIG nonostante l'aggiunta della penalità $l_1$.

Contributi Chiave

• Innovazione Algoritmica: Lo sviluppo di un nuovo algoritmo prossimale doppio proiettato che evita la duplicazione dei predittori. Questo metodo calcola le proiezioni sull'intersezione di insiemi convessi in modo iterativo, conservando le risorse computazionali per strutture grafiche ad alta dimensionalità e dense.
• Efficienza del Modello: Il modello SGLIG ottiene la doppia sparsità con un solo parametro di regolazione ($\alpha$), riducendo il carico computazionale della selezione degli iperparametri rispetto al DSRIG a due parametri.
• Garanzie Teoriche: Derivazione di limiti di errore su campioni finiti e dimostrazione della normalità asintotica per lo stimatore SGLIG, stabilendone la validità statistica sotto assunzioni standard.
• Validazione Empirica: Valutazione completa su dati simulati con cinque strutture grafiche distinte (Due Classi, Bipartito, Random, a Blocchi, a Banda) e due dataset reali (Barriera Emato-Encefalica e Alzheimer's Disease Neuroimaging Initiative).

Risultati

• Studi di Simulazione:

  • Accuratezza: Il modello DSRIG ha generalmente ottenuto il più basso Errore Quadratico Medio (MSE) e la distanza $l_2$. Tuttavia, il modello SGLIG ha mostrato prestazioni competitive, spesso avvicinandosi all'accuratezza di DSRIG mentre superava significativamente il modello SRIG a sparsità singola.
  • Efficienza: Il modello SGLIG ha dimostrato una sostanziale riduzione del tempo di calcolo rispetto a DSRIG. In scenari ad alta dimensionalità (ad esempio, 800 predittori), DSRIG ha richiesto oltre 2.900 secondi, mentre SGLIG ha richiesto circa 60 secondi e SRIG 40 secondi. SGLIG colma efficacemente il divario tra la velocità di SRIG e l'accuratezza di DSRIG.
  • Sensibilità al Grafo: SGLIG ha mostrato prestazioni robuste su varie topologie di grafi, con l'eccezione del grafo "Banda", dove la sparsità all'interno del gruppo è stata meno benefica a causa della struttura di connettività lineare.

• Dati Reali:

  • Sul dataset della Barriera Emato-Encefalica, SGLIG ha ottenuto il MSE più basso tra i tre modelli mantenendo tempi di calcolo comparabili a SRIG e significativamente inferiori a DSRIG.
  • L'analisi della selezione delle variabili ha mostrato che SGLIG e DSRIG (entrambi a doppia sparsità) hanno selezionato variabili relative alla carica delle particelle, mentre SRIG si è concentrato maggiormente sulle misure dell'area superficiale, suggerendo che la doppia sparsità cattura diverse sfumature strutturali.

Significato e Affermazioni
Il documento afferma che il modello SGLIG offre un compromesso pratico per la regressione ad alta dimensionalità con struttura grafica. Sostituendo la duplicazione dei predittori con una nuova tecnica di proiezione prossimale, gli autori affermano che il loro metodo conserva le risorse computazionali senza sacrificare i benefici della doppia sparsità. I risultati suggeriscono che SGLIG esibisce prestazioni stabili rispetto ad altri modelli di regressione grafica a sparsità singola o doppia, rendendolo un'alternativa praticabile per scenari in cui DSRIG è computazionalmente non fattibile. Gli autori sottolineano che la loro implementazione è particolarmente vantaggiosa per dati ad alta dimensionalità con grafi di predittori densi.