Coordinate Descent Algorithm for Least Absolute Deviations Regression

1. Il Problema: Regressione a Minimi Assoluti (LAD) e le sue Sfide

La regressione lineare classica si basa spesso sui Minimi Quadrati Ordinari (OLS), che minimizzano la somma dei quadrati dei residui. Sebbene ottimali sotto specifiche assunzioni (errori omoschedastici con momenti finiti), gli OLS sono estremamente sensibili agli outlier e a distribuzioni di errore a code pesanti.

L'alternativa robusta è la Regressione a Minimi Assoluti (LAD), che minimizza la somma dei valori assoluti dei residui ($\sum |y_i - x_i^T \beta|$). Questo corrisponde alla regressione della mediana. Tuttavia, l'adozione diffusa della LAD è stata storicamente limitata da:

• Costo Computazionale: I metodi tradizionali si basano sulla programmazione lineare (LP), utilizzando algoritmi come il Simplex o punti interni. Questi diventano proibitivi in dimensioni elevate.
• Instabilità Numerica: In contesti ad alta dimensionalità (dove il numero di predittori $p$ è maggiore o uguale al numero di osservazioni $n$, cioè $p \ge n$) o in matrici di rango ridotto, le formulazioni LP possono soffrire di malcondizionamento numerico o fallire nel trovare soluzioni.
• Dipendenza da Software Specializzato: La necessità di solver LP complessi rende l'implementazione meno accessibile.

2. Metodologia Proposta: Coordinate Descent (CD) per LAD

Gli autori propongono un algoritmo di Coordinate Descent (discesa per coordinate) specifico per la LAD, che evita l'inversione di matrici e gestisce naturalmente la non differenziabilità della funzione obiettivo.

Fondamenti Teorici

Il cuore dell'algoritmo risiede nella scomposizione del problema multivariato in una serie di sottoproblemi univariati. Fissando tutte le coordinate del vettore dei coefficienti $\beta$ tranne una ($\beta_j$), il problema di ottimizzazione si riduce a:
$$\min_{t \in \mathbb{R}} \sum_{i=1}^n |r_i^{(j)} - x_{ij}t|$$
dove $r_i^{(j)}$ è il residuo parziale.

• Se $x_{ij} = 1$ (termine di intercetta), la soluzione è la mediana dei residui parziali.
• Se $x_{ij} \neq 0$, la soluzione è la mediana pesata dei rapporti $r_i^{(j)}/x_{ij}$ con pesi $|x_{ij}|$.

Poiché la funzione obiettivo LAD è convessa e ogni aggiornamento di coordinata è una minimizzazione esatta, l'algoritmo è garantito per convergere a un minimo globale.

Ottimizzazioni Computazionali

Per rendere l'algoritmo scalabile, gli autori introducono due strategie chiave:

1. Aggiornamenti Incrementali dei Residui: Invece di ricalcolare l'intero vettore dei residui parziali ad ogni passo (costo $O(np)$), l'algoritmo mantiene un vettore di residuo globale e lo aggiorna in loco ($O(n)$) quando un coefficiente cambia. Questo riduce la complessità per iterazione da $O(np^2)$ a $O(np \log n)$ (dominata dall'ordinamento necessario per calcolare la mediana pesata).
2. Strategie di "Warm-Start" (Inizializzazione): Poiché la CD è un metodo di discesa, la scelta del punto di partenza è cruciale, specialmente in regimi sottodeterminati ($p \ge n$).
   • Ridge Regression: Fornisce una stima iniziale stabile e chiusa, riducendo la varianza.
   • Algoritmi Genetici (GA): Utilizzati per una ricerca globale iniziale in casi complessi, seguita dalla raffinazione locale della CD.
   • Multi-start Random: Utilizzato come fallback quando non sono disponibili modelli pre-addestrati.

3. Risultati Sperimentali

Gli esperimenti sono stati condotti su dati sintetici e dataset reali (Boston Housing, Air Quality, Concrete Compressive Strength).

• Convergenza e Stabilità: L'algoritmo converge in poche decine di iterazioni (spesso < 50). In 1000 repliche con inizializzazioni casuali, la soluzione finale è quasi identica (deviazione standard minima), dimostrando la robustezza del metodo.
• Robustezza agli Outlier: In presenza di dati contaminati (20% di outlier), la LAD-CD recupera accuratamente il segnale sottostante, superando nettamente gli OLS e avvicinandosi alle prestazioni dei solver LP basati su quantili (QuantReg).
• Regimi ad Alta Dimensionalità ($p \ge n$):
  • I solver LP basati su QuantReg falliscono o non restituiscono soluzioni quando $p > n$.
  • La LAD-CD rimane stabile e ben definita.
  • L'inizializzazione con Ridge + LAD-CD ha mostrato le migliori prestazioni, riducendo l'errore di previsione fino al 30-40% rispetto a stime grezze e superando le alternative basate su Algoritmi Genetici in termini di accuratezza predittiva e scalabilità.
• Confronto con Solutori LP: Su dataset reali di dimensioni moderate, la LAD-CD raggiunge un'accuratezza predittiva (MAE) paragonabile a quella dei solver LP (es. pacchetto quantreg), pur essendo un metodo "senza inversione di matrice" e più semplice da implementare. Sebbene i solver LP siano leggermente più veloci su dataset piccoli, la LAD-CD offre un vantaggio significativo in termini di scalabilità e stabilità numerica per $p$ grandi.

4. Contributi Chiave

1. Algoritmo Scalabile: Introduzione di un metodo CD per LAD con complessità $O(np \log n)$ per ciclo completo, eliminando la dipendenza da solver LP complessi.
2. Gestione di $p \ge n$: Dimostrazione che il metodo funziona efficacemente anche quando il numero di predittori supera le osservazioni, un regime dove i metodi tradizionali falliscono.
3. Strategia Ibrida: Validazione empirica che l'inizializzazione tramite regressione Ridge seguita da raffinazione LAD-CD offre il miglior compromesso tra velocità, stabilità e accuratezza.
4. Semplicità Implementativa: Il metodo non richiede librerie di ottimizzazione specializzate, rendendolo accessibile e facile da integrare in qualsiasi ambiente di calcolo.

5. Significato e Implicazioni

Questo lavoro fornisce un'alternativa pratica e robusta alla regressione lineare classica e ai solutori LAD basati su programmazione lineare.

• Per la Statistica Applicata: Offre uno strumento robusto per modellare dati con errori a code pesanti o outlier, senza i costi computazionali dei metodi LP.
• Per l'Apprendimento Automatico: Abilita l'uso della regressione LAD in contesti di "Big Data" o alta dimensionalità, dove la stabilità numerica è critica.
• Pedagogico: La chiarezza della derivazione (basata su mediane) e la semplicità dell'algoritmo lo rendono un ottimo strumento didattico per spiegare la regressione robusta.

In conclusione, gli autori dimostrano che la combinazione di un aggiornamento esatto per coordinate e strategie di inizializzazione intelligenti rende la regressione LAD una soluzione competitiva, scalabile e affidabile per la modellazione statistica moderna.