Finite-Sample Inference for Sparsely Permuted Linear Regression

Sintesi Tecnica: Inferenza a Campione Finito per la Regressione Lineare Sparsamente Permutata

Definizione del Problema
Il documento affronta il problema dell'inferenza statistica nella regressione lineare in cui la corrispondenza tra covariate e risposte è interrotta da una permutazione ignota. Nello specifico, gli autori considerano il modello:
$$Y_{\text{obs}} = \Pi_0 X \beta_0 + \sigma_0 u_{\text{rel}}$$
dove $Y_{\text{obs}} \in \mathbb{R}^n$ è il vettore di risposta osservato, $X \in \mathbb{R}^{n \times p}$ è una matrice di design deterministica, $\beta_0 \in \mathbb{R}^p$ è il vettore dei coefficienti ignoti e $\Pi_0$ è una matrice di permutazione $n \times n$ ignota. Il rumore $u_{\text{rel}}$ segue una distribuzione normale standard.

L'attenzione è rivolta al regime di permutazione sparsa, in cui il numero di discrepanze (la distanza di Hamming tra $\Pi_0$ e la matrice identità $I_n$) è limitato da un piccolo intero $k$ (ovvero $d(\Pi_0, I_n) \leq k$). Il documento mira a risolvere due obiettivi inferenziali primari in un contesto a campione finito:

1. Test di Ipotesi: Determinare se esiste una discrepanza (testare $H_0: \Pi_0 \in \mathcal{P}_{n, k_0}$ contro $H_1: \Pi_0 \in \mathcal{P}_{n, k} \setminus \mathcal{P}_{n, k_0}$).
2. Insiemi di Confidenza: Costruire insiemi di confidenza validi per i coefficienti di regressione $\beta_0$ che tengano conto dell'incertezza nella stima di $\Pi_0$.

Metodologia
Il framework proposto si basa sul metodo dei campioni di riproduzione (repro samples method) combinato con un passaggio di localizzazione per gestire la complessità combinatoria dello spazio delle permutazioni $\mathcal{P}_{n,k}$, che cresce fattorialmente con $n$.

1. Localizzazione tramite Campioni di Riproduzione:
   Invece di cercare in tutto lo spazio delle permutazioni, gli autori generano un insieme di candidati dipendente dai dati $\mathcal{C}(L) \subset \mathcal{P}_{n,k}$. Ciò viene ottenuto generando $L$ vettori di rumore artificiali $u^*_1, \dots, u^*_L \sim N(0, I_n)$ e risolvendo un problema di ottimizzazione per ciascuno:
   $$\hat{\Pi}_\ell = \arg\min_{\Pi \in \mathcal{P}_{n,k}} \|(I_n - M(\Pi X, u^*_\ell))Y_{\text{obs}}\|_2^2$$
   dove $M(\cdot)$ denota la matrice di proiezione ortogonale. L'insieme dei candidati è definito come $\mathcal{C}(L) = \{\hat{\Pi}_1, \dots, \hat{\Pi}_L\}$. I risultati teorici mostrano che se $L$ è sufficientemente grande, $\mathcal{C}(L)$ contiene il vero $\Pi_0$ con alta probabilità, e la probabilità di esclusione decade polinomialmente con $L$.

2. Surrogato Computazionale (LAP Pesato per Score):
   Risolvere l'obiettivo dei minimi quadrati su permutazioni è computazionalmente intrattabile. Gli autori propongono un Problema di Assegnazione Lineare (LAP) pesato per score come surrogato. La matrice dei costi $\Omega$ è costruita per penalizzare le assegnazioni fuori diagonale pur premiando le corrispondenze diagonali, incorporando un termine che induce la sparsità. Questo problema surrogato viene risolto esattamente in tempo $O(n^3)$ utilizzando l'algoritmo di Hungarian. Il documento dimostra che, sotto specifiche condizioni a campione finito, la soluzione di questo LAP coincide con il minimizzatore globale dell'originale obiettivo dei minimi quadrati con alta probabilità.

3. Procedure di Inferenza a Campione Finito:

   • Test di Permutazione: Viene sviluppato un test Monte Carlo condizionale per testare la sparsità della permutazione. La statistica del test $D(Y)$ misura la distanza di Hamming tra la migliore permutazione in $\mathcal{C}(L)$ e la matrice identità. Il valore critico è calibrato uniformemente sull'insieme nullo localizzato $\hat{\mathcal{P}}_{n, k_0} = \mathcal{C}(L) \cap \mathcal{P}_{n, k_0}$ utilizzando distribuzioni condizionate che eliminano i parametri di disturbo ($\beta, \sigma$).
   • Inferenza sui Coefficienti: Gli insiemi di confidenza per $\beta_0$ sono costruiti prendendo l'unione delle regioni di confidenza basate sulla statistica $F$ su tutti i $\Pi \in \mathcal{C}(L)$. Questo approccio "localmente simultaneo" garantisce una copertura valida anche quando l'allineamento reale è incerto, a condizione che il vero $\Pi_0$ risieda in $\mathcal{C}(L)$.

Contributi Chiave

• Garanzie Teoriche: Il documento fornisce garanzie non asintotiche per tutte le componenti del framework.
  • Teorema 4.1: Stabilisce che la probabilità di mancata copertura dell'insieme di candidati $\mathcal{C}(L)$ decade polinomialmente con il numero di campioni di riproduzione $L$.
  • Teorema 4.3: Dimostra che il test proposto controlla l'errore di Tipo I al livello $\alpha$ in campioni finiti, condizionatamente all'evento di localizzazione.
  • Teorema 4.4: Dimostra che l'insieme di confidenza basato sull'unione per $\beta_0$ raggiunge la copertura nominale fino a un termine di errore trascurabile relativo alla probabilità di localizzazione.
  • Teorema 4.5: Fornisce un'equivalenza ad alta probabilità tra l'efficiente LAP pesato per score e l'originale problema combinatorio dei minimi quadrati.
• Efficienza Computazionale: Riducendo la ricerca a un insieme localizzato e utilizzando l'algoritmo di Hungarian, il metodo evita la complessità fattoriale della ricerca esaustiva, scalando polinomialmente ($O(n^3)$) con la dimensione del campione.
• Estensioni: La metodologia è estesa per gestire design parzialmente permutati (dove solo un sottoinsieme di covariate è disallineato) e regressione permutata con regolarizzazione ridge.

Risultati

• Simulazioni: Simulazioni estese con variabili dimensioni campionarie ($n$), conteggi di discrepanza ($k$) e livelli di rumore ($\sigma_0$) confermano le proprietà teoriche.
  • La dimensione dell'insieme dei candidati rimane gestibile e il vero valore di permutazione è incluso con alta frequenza.
  • Il test di permutazione mantiene il controllo valido dell'errore di Tipo I (tassi di rifiuto $\leq 0,05$ quando $k=0$) ed esibisce una potenza crescente al crescere delle discrepanze.
  • Gli insiemi di confidenza per $\beta_0$ raggiungono una copertura empirica vicina al livello nominale (ad esempio, 95%) in tutti i regimi, con volumi che non mostrano un eccessivo conservatorismo.
• Applicazione su Dati Reali: Il metodo è stato applicato ai dati sulla qualità dell'aria di Pechino (concentrazioni di PM2.5 rispetto alle covariate meteorologiche).
  • In uno scenario con discrepanze locali introdotte artificialmente (8% delle righe rimescolate entro una finestra di 3 ore), il metodo ha rifiutato con successo l'ipotesi nulla di assenza di discrepanza.
  • Nello scenario non perturbato, l'insieme dei candidati è collassato alla matrice identità e l'ipotesi nulla non è stata rifiutata, confermando il controllo dell'errore di Tipo I nella pratica.

Significatività
Il documento sostiene di offrire una base generale e computazionalmente fattibile per la validità esatta a campione finito in modelli statistici che coinvolgono parametri discreti e combinatori come le permutazioni. A differenza degli approcci asintotici tradizionali o dei metodi di inferenza selettiva che faticano con la natura non poliedrica della selezione delle permutazioni, questo framework:

1. Evita l'uso di asintotica locale o espansioni di verosimiglianza lisce.
2. Fornisce un rigoroso controllo dell'errore a campione finito sia per il test di ipotesi che per la stima dei parametri.
3. Colma il divario tra teoria statistica e trattabilità computazionale in presenza di incertezza di allineamento.

Gli autori pongono questo lavoro come una soluzione alla sfida di eseguire l'inferenza quando le coppie di dati sono parzialmente ignote o corrotte, un problema comune nell'integrazione di dati per la preservazione della privacy e nel collegamento dei record (record linkage).