Riepilogo Tecnico: Un Test di Indipendenza a Kernel Martingala

1. Enunciato del Problema

Il documento affronta le sfide computazionali e di calibrazione statistica intrinseche ai test di indipendenza basati su kernel, in particolare il Criterio di Indipendenza Hilbert–Schmidt (HSIC) e la sua estensione all'indipendenza congiunta, dHSIC.

Le implementazioni standard di HSIC e dHSIC si basano su statistiche V degeneri. Sotto l'ipotesi nulla di indipendenza ($H_0$), le statistiche riscalate convergono a una somma pesata di variabili casuali $\chi^2$, dove i pesi dipendono dalla distribuzione congiunta sconosciuta dei dati. Di conseguenza, la calibrazione pratica richiede test di permutazione per approssimare la distribuzione nulla. Questo processo comporta il ricalcolo della statistica $B$ volte (tipicamente $B \ge 200$), gonfiando il costo computazionale per test da $O(n^2)$ a $O(B n^2)$, un fattore di due ordini di grandezza.

Gli autori mirano a eliminare completamente il passaggio di permutazione costruendo statistiche con un limite nullo noto e libero dalla distribuzione (normale standard), riducendo così il costo per test a pari complessità quadratica della stessa statistica V distorta.

2. Metodologia

L'approccio proposto adatta la recente costruzione martingala MMD per il test a due campioni (Chatterjee e Ramdas [2025]) al contesto dell'indipendenza. L'idea centrale è trasformare lo stimatore quadratico a tempo $O(n^2)$ in una somma di differenze martingala, che può quindi essere studentizzata per convergere a una distribuzione normale standard tramite il Teorema del Limite Centrale (CLT) per martingale auto-normalizzate.

2.1 La Statistica mHSIC (Indipendenza Bivariata)

Per testare l'indipendenza tra due variabili $X$ e $Y$, gli autori definiscono mHSIC.

• Costruzione: La statistica è una somma triangolare inferiore studentizzata del prodotto di Hadamard di due matrici di Gram centrate empiricamente ($K_X$ e $K_Y$).
  $$\hat{T}^{\text{mHSIC}}_n = \frac{1}{n} \sum_{i=2}^n \frac{1}{i} \sum_{j=1}^{i-1} (HK_XH)_{ij} (HK_YH)_{ij}$$
• Studentizzazione: La statistica è normalizzata dalla sua variazione quadratica empirica $\hat{\sigma}_n$.
• Base Teorica: Sotto $H_0$, il prodotto dei kernel $\bar{k}_X \bar{k}_Y$ (dove $\bar{k}$ indica kernel centrati sulla popolazione) forma una sequenza di differenze martingala. Sebbene la matrice di centraggio empirica $H$ introduca un bias, gli autori dimostrano che tale bias è $O_P(1/\sqrt{n})$ e asintoticamente trascurabile dopo la studentizzazione.
• Proprietà: Sotto condizioni di quarto momento limitato, mHSIC converge a $\mathcal{N}(0, 1)$ indipendentemente dalla legge dei dati. È consistente contro ogni alternativa fissa e mantiene un costo computazionale $O(n^2)$ senza divisione del campione.

2.2 La Statistica mdHSIC (Indipendenza Congiunta)

Per testare l'indipendenza congiunta tra $d$ variabili ($X_1, \dots, X_d$), un'estensione ingenua di mHSIC fallisce.

• Il Fallimento del Prodotto Diretto: Sostituire il kernel bivariato con un prodotto di $d$ kernel centrati empiricamente risulta in un bias aggregato di $O_P(d/\sqrt{n})$. Quando il numero di variabili $d$ supera $\sqrt{n}$, questo bias domina la scala studentizzata, rompendo la calibrazione normale standard.
• La Soluzione a Martingala Divisa (mdHSIC): Per risolvere ciò, gli autori introducono un singolo split di metà campione:
  1. Split: Il campione è diviso in $S_1$ (prima metà) e $S_2$ (seconda metà).
  2. Centraggio: Gli embedding della media e i kernel centrati sono stimati utilizzando solo $S_1$.
  3. Esecuzione Martingala: La somma martingala auto-normalizzata triangolare inferiore è calcolata utilizzando i kernel centrati su $S_1$ applicati alle coppie all'interno di $S_2$.
• Base Teorica: Questa costruzione garantisce che il residuo della media condizionata del prodotto dei kernel sia $O_P(m^{-d/2})$ (dove $m \approx n/2$). Questo residuo è esponenzialmente piccolo in $d$, rendendolo trascurabile per qualsiasi $d \ge 2$ fisso.
• Proprietà: mdHSIC converge a $\mathcal{N}(0, 1)$ per qualsiasi $d$ fisso sotto indipendenza congiunta. Il costo per test è $O(d n^2)$, lineare in $d$, evitando il fattore di permutazione $B$.

3. Contributi Chiave

1. mHSIC: Una statistica priva di permutazioni e priva di divisione del campione per l'indipendenza bivariata che converge a una distribuzione normale standard sotto l'ipotesi nulla, abbinando il costo $O(n^2)$ della statistica V distorta HSIC.
2. mdHSIC: Una statistica priva di permutazioni per l'indipendenza congiunta di $d$ variabili. Corregge il bias di centraggio empirico delle estensioni a prodotto diretto tramite un singolo split di metà campione, garantendo normalità asintotica per qualsiasi $d$ fisso con complessità $O(d n^2)$.
3. Garanzie Teoriche: Dimostrazioni di convergenza a $\mathcal{N}(0, 1)$ sotto l'ipotesi nulla (Teoremi 3 e 6) e consistenza contro alternative fisse, basate sul CLT per martingale auto-normalizzate (Fan [2018]).
4. Validazione Empirica: Dimostrazione che entrambe le statistiche corrispondono ai tassi di errore di Tipo I e alla potenza dei test delle baseline calibrate per permutazione, ottenendo al contempo significativi acceleramenti.

4. Risultati Sperimentali

Gli autori hanno valutato i metodi su dati sintetici con dimensioni e dimensioni del campione variabili.

• Calibrazione (Errore di Tipo I):
  • mHSIC: Su dati bivariati con dimensioni ambientali fino a 500, il tasso di errore di Tipo I empirico a $\alpha=0.05$ è rimasto stretto intorno al livello nominale per $n$ sufficientemente grande. Gli autori notano una "maledizione della dimensionalità a campione finito" in cui il tasso di errore si gonfia se $d_{\text{ambient}} \gtrsim n^{0.875}$ a causa del bias di centraggio residuo.
  • mdHSIC: Su compiti di indipendenza congiunta con $d \in \{2, \dots, 10\}$, il tasso di errore di Tipo I è rimasto nell'intervallo $[0.036, 0.066]$ attraverso tutte le dimensioni e le dimensioni del campione testate, confermando la calibrazione libera dalla distribuzione.
• Potenza: Entrambe le statistiche hanno mostrato aumenti monotoni della potenza con la forza di dipendenza e la dimensione del campione, corrispondendo alle prestazioni delle baseline basate su permutazioni.
• Efficienza Computazionale:
  • mHSIC e mdHSIC sono stati 25-60 volte più veloci delle loro controparti calibrate per permutazione (HSIC-perm e dHSIC-perm con $B=200$).
  • Per $n=16.000$, mHSIC ha richiesto 0,042 secondi rispetto a 2,532 secondi per HSIC-perm.
  • L'accelerazione scala con $n$ perché il costo di permutazione cresce linearmente con $B$, mentre il costo martingala rimane costante per test.

5. Significato e Affermazioni

Il documento afferma di risolvere il collo di bottiglia della calibrazione nei test di indipendenza a kernel. Sfruttando strutture martingala, gli autori eliminano la necessità di costosi campionamenti di permutazione, riducendo il carico computazionale di due ordini di grandezza preservando al contempo la validità statistica.

• Privo di Permutazioni: Il significato principale è la sostituzione del passaggio di permutazione $O(B n^2)$ con un'unica ricerca di quantili normali, rendendo i test fattibili per dataset su larga scala dove la permutazione è proibitiva.
• Robustezza: I metodi sono liberi dalla distribuzione; il limite nullo è normale standard indipendentemente dalla legge dei dati sottostante, a condizione che siano soddisfatte lievi condizioni di momento.
• Scalabilità: La statistica mdHSIC affronta specificamente il problema della scalabilità nei test di indipendenza congiunta ad alta dimensionalità, dove le estensioni ingenu falliscono a causa di bias cumulativi.

Gli autori posizionano il loro lavoro come un adattamento diretto del paradigma martingala MMD (Chatterjee e Ramdas [2025]) al problema dell'indipendenza, offrendo un'alternativa pratica ai metodi esistenti di divisione del campione (come xHSIC) mantenendo la struttura triangolare inferiore che utilizza tutte le coppie disponibili nella seconda metà del campione, migliorando così la potenza statistica rispetto agli approcci a blocchi incrociati rettangolari.