Non-asymptotic two-sample kernel testing with the spectrally truncated normalized MMD

1. Il Problema

Il lavoro si concentra sul problema del test a due campioni (two-sample test) per verificare l'uguaglianza di distribuzioni ($H_0: P_X = P_Y$) utilizzando metodi basati sui kernel.

• Contesto: I metodi tradizionali si basano sulla Maximum Mean Discrepancy (MMD), che misura la distanza tra le medie delle distribuzioni incorporate in uno spazio di Hilbert a kernel riproducente (RKHS).
• Limitazioni delle approcci esistenti:
  • Le distribuzioni asintotiche della MMD standard sono complesse (somme pesate di variabili chi-quadrato) e dipendono da quantità sconosciute, rendendo necessario l'uso di tecniche di data-splitting (divisione dei dati) o permutazioni per calibrare i quantili, con conseguenti costi computazionali elevati.
  • Le varianti normalizzate della MMD (che dividono la discrepanza per la varianza intra-gruppo, analogamente al test di Hotelling $T^2$) offrono maggiore potenza statistica, ma richiedono l'inversione dell'operatore di covarianza, che è singolare.
  • Le strategie di regolarizzazione attuali (es. ridge) portano a distribuzioni nulle ancora complesse, richiedendo nuovamente la divisione dei dati.
  • L'uso della troncatura spettrale (spectral truncation) come regolarizzazione è stato proposto in passato per semplificare la distribuzione asintotica (che diventa una $\chi^2$ con $T$ gradi di libertà), ma non è stato adeguatamente esplorato nel regime non-asintotico (campioni finiti), dove i quantili asintotici falliscono nel garantire un controllo corretto dell'errore di Tipo I.

2. Metodologia

Gli autori propongono un nuovo statistic test chiamato st-nMMD (Spectrally Truncated Normalized MMD).

• Definizione dello Statistico:
  Lo statistico è definito come:
  $$\hat{D}^2_T = \frac{n_X n_Y}{n_X + n_Y} \left\| \hat{\Sigma}_T^{-1/2} (\hat{\mu}_X - \hat{\mu}_Y) \right\|_H^2 = \frac{n_X n_Y}{n_X + n_Y} \sum_{t=1}^T \frac{\langle \hat{f}_t, \hat{\mu}_X - \hat{\mu}_Y \rangle_H^2}{\hat{\lambda}_t}$$
  dove $\hat{\Sigma}_T$ è la decomposizione spettrale troncata dell'operatore di covarianza intra-gruppo stimato, $\hat{\lambda}_t$ e $\hat{f}_t$ sono autovalori e autovettori empirici, e $T$ è il numero di componenti spettrali trattenute.

• Regolarizzazione: Invece di usare la regolarizzazione di Tikhonov (ridge), si utilizza la troncatura spettrale, mantenendo solo i primi $T$ autovalori positivi. Questo trasforma lo statistico in una somma finita di rapporti.

• Approccio Non-Asintotico:
  Gli autori derivano un limite superiore esponenziale per la distribuzione dello statistico sotto l'ipotesi nulla ($H_0$).

  • Si basano su disuguaglianze di concentrazione per processi auto-normalizzati (auto-renormalized processes), adattando risultati di Bertail et al. (2008).
  • La strategia di prova utilizza un approccio "locale" (direzione per direzione), controllando simultaneamente le fluttuazioni della differenza delle medie e degli autovettori/autovalori stimati, evitando che il limite esploda quando gli autovalori sono piccoli.
  • Vengono introdotte condizioni tecniche sugli autovalori e sui "gap spettrali" (differenze tra autovalori consecutivi) per garantire la stabilità della stima.

• Calibrazione dei Dati (Data-Driven):
  Poiché i limiti teorici contengono costanti che possono rendere il test troppo conservativo, gli autori propongono un algoritmo completamente data-adaptive:

  1. Stima degli autovalori e dei gap spettrali dai dati.
  2. Calibrazione di un parametro di regolarizzazione $\rho$ direttamente sul dataset, senza necessità di data-splitting.
  3. Selezione automatica del parametro di troncamento $T$ basata su un rapporto segnale-rumore degli autovalori stimati.

3. Contributi Chiave

1. Teoria Non-Asintotica: Derivazione di una disuguaglianza di deviazione esponenziale esplicita e precisa per lo statistico st-nMMD sotto $H_0$, fornendo un limite superiore per il quantile che garantisce il controllo dell'errore di Tipo I per campioni finiti.
2. Ottimalità Asintotica: Dimostrazione che, nel regime asintotico ($n \to \infty$), il quantile proposto converge al quantile della distribuzione $\chi^2(T)$, confermando la coerenza con i risultati noti.
3. Procedura Pratica senza Data-Splitting: Sviluppo di un algoritmo che stima i quantili non-asintotici e seleziona $T$ utilizzando l'intero dataset, evitando la perdita di potenza statistica dovuta alla divisione dei dati.
4. Analisi di Potenza: Dimostrazione che la natura adattiva del quantile (che dipende dalla struttura di covarianza stimata) permette di mantenere una buona potenza anche sotto l'ipotesi alternativa, compensando la conservatività necessaria sotto $H_0$.

4. Risultati Sperimentali

Gli autori hanno valutato le prestazioni su dati simulati (distribuzioni Gaussiane, Uniformi, Cauchy, von Mises-Fisher) e sul dataset MNIST (immagini di cifre scritte).

• Calibrazione (Errore di Tipo I):
  • Il metodo proposto mantiene il livello di significatività nominale (es. $\alpha=0.05$) in modo robusto, indipendentemente dalla dimensione del campione ($n$), dalla dimensionalità ($d$) e dalla distribuzione sottostante.
  • Al contrario, l'approssimazione asintotica $\chi^2$ fallisce nel regime non-asintotico (es. $n=100$), mostrando un errore di Tipo I inflazionato (test non calibrato).
• Potenza Statistica:
  • Sebbene il test proposto sia leggermente conservativo rispetto all'approssimazione $\chi^2$ (che però è errata per piccoli campioni), la sua potenza empirica rimane competitiva.
  • Man mano che la dimensione del campione aumenta, la potenza del metodo proposto converge a quella del metodo asintotico, ma garantendo al contempo la validità teorica per campioni finiti.
• Selezione di T: L'algoritmo di selezione automatica di $T$ tende a scegliere valori piccoli, specialmente in alta dimensionalità sotto $H_0$, evitando di includere direzioni non informative che potrebbero aumentare il tasso di falsi positivi.

5. Significato e Impatto

Questo lavoro è significativo perché colma il divario tra la teoria asintotica e le applicazioni pratiche con campioni finiti nel contesto dei test a due campioni basati su kernel.

• Risoluzione del problema di calibrazione: Offre una soluzione rigorosa per la calibrazione dei test normalizzati senza ricorrere a costosi metodi di permutazione o alla divisione dei dati.
• Efficienza Computazionale: La troncatura spettrale, combinata con una calibrazione analitica non-asintotica, rende il metodo scalabile e applicabile in scenari reali dove i dati sono complessi e le dimensioni sono elevate.
• Flessibilità: La procedura adattiva si adatta alla struttura dei dati (sia sotto $H_0$ che sotto $H_1$), offrendo un compromesso ottimale tra controllo dell'errore e potenza statistica.

In sintesi, il paper introduce un metodo di testing statistico st-nMMD che è teoricamente fondato, calibrato per campioni finiti, e praticamente implementabile senza divisione dei dati, superando le limitazioni delle approcci precedenti basati su regolarizzazione ridge o approssimazioni asintotiche.