2025-11-14T20:13:11.521057

Minimax Optimal Kernel Two-Sample Tests with Random Features

Mukherjee, Sriperumbudur
Reproducing Kernel Hilbert Space (RKHS) embedding of probability distributions has proved to be an effective approach, via MMD (maximum mean discrepancy), for nonparametric hypothesis testing problems involving distributions defined over general (non-Euclidean) domains. While a substantial amount of work has been done on this topic, only recently have minimax optimal two-sample tests been constructed that incorporate, unlike MMD, both the mean element and a regularized version of the covariance operator. However, as with most kernel algorithms, the optimal test scales cubically in the sample size, limiting its applicability. In this paper, we propose a spectral-regularized two-sample test based on random Fourier feature (RFF) approximation and investigate the trade-offs between statistical optimality and computational efficiency. We show the proposed test to be minimax optimal if the approximation order of RFF (which depends on the smoothness of the likelihood ratio and the decay rate of the eigenvalues of the integral operator) is sufficiently large. We develop a practically implementable permutation-based version of the proposed test with a data-adaptive strategy for selecting the regularization parameter. Finally, through numerical experiments on simulated and benchmark datasets, we demonstrate that the proposed RFF-based test is computationally efficient and performs almost similarly (with a small drop in power) to the exact test.
academic

Test Minimax Ottimali per Due Campioni con Kernel e Caratteristiche Casuali

Informazioni Fondamentali

  • ID Articolo: 2502.20755
  • Titolo: Minimax Optimal Kernel Two-Sample Tests with Random Features
  • Autori: Soumya Mukherjee, Bharath K. Sriperumbudur (Pennsylvania State University)
  • Classificazione: math.ST cs.LG stat.ML stat.TH
  • Data di Pubblicazione: 17 Ottobre 2025 (preprint arXiv)
  • Link Articolo: https://arxiv.org/abs/2502.20755

Riassunto

Questo articolo propone un metodo di test per due campioni con regolarizzazione spettrale basato su caratteristiche di Fourier casuali (RFF) per il problema del test a due campioni basato su embedding nello spazio di Hilbert a kernel riproducente (RKHS). Il metodo mantiene l'ottimalità statistica riducendo significativamente la complessità computazionale da cubica a quasi lineare, fornendo anche una versione completamente guidata dai dati e praticamente realizzabile.

Contesto di Ricerca e Motivazione

Problema Centrale

Il test a due campioni è un problema fondamentale della statistica, mirato a determinare se due campioni casuali provengono da distribuzioni di probabilità uguali. I metodi parametrici e non parametrici tradizionali affrontano limitazioni significative nel trattare dati ad alta dimensionalità o distribuzioni su domini non euclidei.

Limitazioni dei Metodi Esistenti

  1. Subottimalità del test MMD: Sebbene il test della massima differenza media (MMD) sia ampiamente applicato, manca di ottimalità minimax, considerando solo l'embedding della media e ignorando le informazioni dell'operatore di covarianza
  2. Collo di bottiglia computazionale dei metodi con regolarizzazione spettrale: I recenti test MMD con regolarizzazione spettrale, sebbene raggiungano l'ottimalità minimax, hanno complessità computazionale O(n³), limitando l'applicazione su dati su larga scala
  3. Difficoltà nella selezione dei parametri: La scelta del parametro di regolarizzazione dipende da caratteristiche distributive sconosciute, mancando di strategie adattive guidate dai dati

Motivazione della Ricerca

Questo articolo mira a migliorare significativamente l'efficienza computazionale del test a due campioni con regolarizzazione spettrale attraverso la tecnica di approssimazione con caratteristiche di Fourier casuali, mantenendo l'ottimalità statistica e sviluppando versioni adattive praticamente utilizzabili.

Contributi Principali

  1. Test computazionalmente efficiente e statisticamente ottimale: Propone un test a due campioni con regolarizzazione spettrale basato su RFF, riducendo la complessità computazionale da O(n³) a O(nl²+nld), mantenendo al contempo l'ottimalità minimax sotto condizioni sufficienti
  2. Garanzie Teoriche: Stabilisce il collegamento teorico tra l'ordine di approssimazione RFF e l'ottimalità statistica, provando l'ottimalità minimax del test quando il numero di caratteristiche l soddisfa condizioni specifiche
  3. Versione Adattiva Pratica: Sviluppa una versione completamente guidata dai dati basata su test di permutazione, includendo strategie di selezione adattiva per il parametro di regolarizzazione e la funzione kernel
  4. Verifica Sperimentale Completa: Valida l'efficacia del metodo attraverso dati sintetici e set di dati di riferimento, dimostrando un buon compromesso tra efficienza computazionale e prestazioni statistiche

Dettagli del Metodo

Definizione del Compito

Dati campioni indipendenti X₁:N e Y₁:M da distribuzioni P e Q, testare l'ipotesi H₀: P = Q vs H₁: P ≠ Q.

Architettura del Metodo Principale

1. Framework di Regolarizzazione Spettrale

Per una funzione kernel K, definire la discrepanza con regolarizzazione spettrale:

ηλ(P,Q) = 4⟨Tgλ(T)u, u⟩_{L²(R)}

dove T è l'operatore integrale, u = dP/dR - 1 è la deviazione del rapporto di verosimiglianza, gλ è la funzione di regolarizzazione.

2. Approssimazione con Caratteristiche di Fourier Casuali

Per funzioni kernel della forma K(x,y) = ∫φ(x,θ)φ(y,θ)dΞ(θ), costruire il kernel approssimato:

Kₗ(x,y) = (1/l)∑ᵢ₌₁ˡ φ(x,θᵢ)φ(y,θᵢ)

3. Statistica di Test Approssimata

Basata sul kernel approssimato Kₗ, costruire la statistica di test:

η̂λ,l = (1/[n(n-1)m(m-1)]) ∑ᵢ≠ⱼ ∑ᵢ'≠ⱼ' t(Xᵢ,Xⱼ,Yᵢ',Yⱼ')

dove la funzione t coinvolge la radice quadrata dell'operatore di covarianza regolarizzato.

Punti di Innovazione Tecnica

1. Innovazione Teorica

  • Condizioni di ottimalità minimax: Stabilisce la relazione precisa tra il numero di caratteristiche RFF l e l'ottimalità statistica
  • Casi di decadimento polinomiale ed esponenziale: Analizza separatamente diversi modelli di decadimento degli autovalori dell'operatore integrale
  • Analisi non asintotica: Fornisce garanzie di prestazione con campioni finiti

2. Innovazione Algoritmica

  • Regolarizzazione adattiva: Realizza la selezione guidata dai dati del parametro di regolarizzazione attraverso test congiunto
  • Adattamento della funzione kernel: Estende alla selezione adattiva di funzioni kernel multiple
  • Implementazione del test di permutazione: Fornisce il calcolo completamente guidato dai dati dei valori critici

3. Innovazione Computazionale

  • Algoritmo efficiente: Analisi dettagliata della complessità computazionale e implementazione ottimizzata
  • Parallelizzazione: Caratteristiche di parallelizzazione naturale del test di permutazione

Configurazione Sperimentale

Set di Dati

  1. Dati Sintetici:
    • Spostamento della media gaussiana: P = N(0,I), Q = N(μ,I)
    • Spostamento della scala gaussiana: P = N(0,I), Q = N(0,σ²I)
    • Spostamento della mediana di Cauchy: Distribuzioni di Cauchy con mediane diverse
  2. Dati Reali:
    • Set di dati MNIST: Immagini di cifre scritte a mano 7×7 pixel, dimensione d=49
    • Rilevamento delle differenze distributive tra sottoinsiemi di cifre diverse

Metriche di Valutazione

  • Potenza Statistica: Probabilità di rifiutare correttamente l'ipotesi nulla sotto l'ipotesi alternativa
  • Tempo Computazionale: Confronto dei tempi di esecuzione dell'algoritmo
  • Errore di Primo Tipo: Controllato al livello α=0.05

Metodi di Confronto

  • Test Adattivo Esatto: Test con regolarizzazione spettrale basato sulla matrice kernel completa
  • Diversi Numeri di Caratteristiche RFF: Confronto delle prestazioni per l ∈ {1,3,5,7,9,15,20}

Dettagli di Implementazione

  • Funzione di regolarizzazione: Regolarizzatore di Showalter gλ(x) = (1-e^(-x/λ))/x
  • Funzioni kernel: Kernel gaussiano e laplaciano, con selezione della larghezza di banda adattiva
  • Numero di permutazioni: Versione RFF B=550-800, versione esatta B'=250-450

Risultati Sperimentali

Risultati Principali

1. Prestazioni Statistiche

  • Spostamento della media gaussiana: Con l≥7 caratteristiche, la potenza si avvicina al metodo esatto
  • Spostamento della scala gaussiana: Prestazioni buone con l≥5
  • Distribuzione di Cauchy: Richiede più caratteristiche (l≥10-15) per gestire distribuzioni con code pesanti
  • Dati MNIST: Buone prestazioni su dati reali complessi con l≥15

2. Efficienza Computazionale

Risparmi di tempo computazionale significativi:

  • Esperimenti gaussiani: Il metodo RFF richiede solo il 33-44% del tempo computazionale
  • Spostamento di scala: Consumo di tempo del 30-40%
  • Esperimento di Cauchy: Solo il 5-6% del tempo computazionale
  • MNIST: Consumo di tempo del 5-15%

3. Verifica Teorica

I risultati sperimentali verificano le previsioni teoriche:

  • Il fabbisogno di caratteristiche è correlato alla dimensionalità dei dati e alla complessità distributiva
  • Il compromesso computazionale-statistico è coerente con l'analisi teorica

Esperimenti di Ablazione

Attraverso il confronto di diversi numeri di caratteristiche RFF, si verifica:

  1. L'esistenza di una soglia nel numero di caratteristiche
  2. Troppo poche caratteristiche portano a perdita di potenza
  3. Un numero appropriato di caratteristiche realizza il miglior compromesso

Scoperte Sperimentali

  1. Effetto della Dimensionalità: I dati ad alta dimensionalità richiedono più caratteristiche RFF
  2. Impatto del Tipo di Distribuzione: Le distribuzioni con code pesanti richiedono più caratteristiche per garantire le prestazioni
  3. Soglie Pratiche: Il numero di caratteristiche richiesto dalla teoria può essere leggermente ridotto nella pratica

Lavori Correlati

Test a Due Campioni con Metodi Kernel

  • Test MMD: Lavoro pioneristico di Gretton et al. (2006, 2012)
  • Ottimalità Minimax: Progressi recenti di Li & Yuan (2024), Schrab et al. (2023)
  • Regolarizzazione Spettrale: Scoperta teorica di Hagrass et al. (2024)

Approssimazione con Caratteristiche Casuali

  • Teoria RFF: Framework fondamentale di Rahimi & Recht (2007)
  • Accelerazione MMD: Applicazioni di Zhao & Meng (2015), Choi & Kim (2024)
  • Compromesso Computazionale-Statistico: Analisi teorica di Sriperumbudur & Sterge (2022)

Vantaggi di Questo Articolo

Vantaggi principali rispetto ai lavori esistenti:

  1. Funzioni Kernel più Generali: Non limitato a kernel invarianti per traslazione
  2. Applicabilità più Ampia: Supporta domini non euclidei
  3. Garanzie Teoriche più Forti: Ottimalità minimax non asintotica
  4. Algoritmo più Pratico: Implementazione completamente guidata dai dati

Conclusioni e Discussione

Conclusioni Principali

  1. Contributo Teorico: Stabilisce per la prima volta la teoria dell'ottimalità minimax per il test a due campioni con regolarizzazione spettrale sotto approssimazione RFF
  2. Contributo Algoritmica: Fornisce un algoritmo pratico computazionalmente efficiente e statisticamente ottimale
  3. Verifica Empirica: Valida l'efficacia del metodo su molteplici tipi di dati

Limitazioni

  1. Selezione del Numero di Caratteristiche: Sebbene fornisca guida teorica, la scelta pratica richiede ancora aggiustamenti empirici
  2. Dipendenza dalla Funzione Kernel: Le prestazioni dipendono ancora dalla scelta della funzione kernel
  3. Distribuzioni con Code Pesanti: Per distribuzioni estremamente pesanti potrebbe essere necessario un gran numero di caratteristiche

Direzioni Future

  1. Altri Metodi di Approssimazione: Esplorare tecniche di approssimazione alternative come Nyström
  2. Test di Permutazione Economico: Combinare con cheap permutation testing per ridurre ulteriormente i costi computazionali
  3. Regolazione Automatica dei Parametri: Sviluppare strategie più intelligenti per la selezione degli iperparametri

Valutazione Approfondita

Punti di Forza

  1. Rigore Teorico: Fornisce analisi teorica non asintotica completa, incluse condizioni sufficienti e prove di ottimalità minimax
  2. Forte Praticità: L'algoritmo è completamente guidato dai dati, senza necessità di conoscenza preliminare
  3. Esperimenti Sufficienti: Copre dati sintetici e reali, molteplici tipi di distribuzione
  4. Scrittura Chiara: Dettagli tecnici esaustivi, prove complete

Insufficienze

  1. Analisi della Complessità: Sebbene riduca la complessità asintotica, i fattori costanti potrebbero essere significativi
  2. Sensibilità ai Parametri: La selezione del parametro di regolarizzazione e del numero di caratteristiche rimane sensibile
  3. Gestione delle Code Pesanti: L'efficacia nel trattare distribuzioni estremamente pesanti necessita di miglioramenti

Impatto

  1. Valore Teorico: Fornisce un nuovo framework teorico per il compromesso computazionale-statistico nei metodi kernel
  2. Valore Pratico: Ha importanti prospettive di applicazione nel test a due campioni su dati su larga scala
  3. Contributo Metodologico: L'applicazione di approssimazione RFF nei test statistici fornisce nuove idee per ricerche correlate

Scenari Applicabili

  1. Dati su Larga Scala: I vantaggi computazionali sono evidenti quando la dimensione del campione è grande
  2. Dati ad Alta Dimensionalità: Presenta vantaggi significativi rispetto ai metodi tradizionali in contesti ad alta dimensionalità
  3. Applicazioni in Tempo Reale: L'aumento dell'efficienza computazionale rende possibile il test in tempo reale
  4. Impostazioni Non Parametriche: Applicabile a casi generali dove la forma distributiva è sconosciuta

Bibliografia

  1. Gretton, A., et al. (2012). A kernel two-sample test. JMLR.
  2. Hagrass, O., et al. (2024). Spectral regularized kernel two-sample tests. Annals of Statistics.
  3. Rahimi, A., & Recht, B. (2007). Random features for large-scale kernel machines. NIPS.
  4. Choi, I., & Kim, I. (2024). Computational-statistical trade-off in kernel two-sample testing with random Fourier features.
  5. Sriperumbudur, B. K., & Sterge, N. (2022). Approximate kernel PCA: Computational versus statistical trade-off. Annals of Statistics.

Valutazione Complessiva: Questo è un articolo di alta qualità nel campo della statistica teorica, che applica con successo la tecnica di approssimazione con caratteristiche casuali al test a due campioni con regolarizzazione spettrale, migliorando significativamente l'efficienza computazionale mantenendo l'ottimalità statistica. L'analisi teorica dell'articolo è profonda e meticolosa, la verifica sperimentale è completa, e presenta valore importante sia per la teoria dell'apprendimento statistico che per le applicazioni pratiche.