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

1. Problema e Contexto

O artigo aborda o problema de teste de duas amostras (two-sample test) para verificar a igualdade de distribuições de probabilidade ($H_0: P_X = P_Y$ vs $H_1: P_X \neq P_Y$) em espaços de alta dimensão. O foco está em métodos baseados em kernels, especificamente na Discrepância Máxima de Média (MMD).

• Limitações do MMD Padrão: O MMD tradicional baseia-se apenas nos embeddings de média no Espaço de Hilbert de Reprodutor de Kernel (RKHS). Teoricamente, isso pode levar a subotimalidade minimax, pois ignora a variabilidade residual dos dados embutidos.
• Limitações do MMD Normalizado (nMMD): Versões normalizadas do MMD, que incorporam o operador de covariância intra-grupo (semelhante ao teste $T^2$ de Hotelling), oferecem maior poder estatístico. No entanto, a inversão do operador de covariância requer regularização.
  • A estratégia comum de regularização por Ridge resulta em uma distribuição nula complexa (somas infinitas ponderadas), exigindo procedimentos de divisão de dados (data-splitting) ou permutações para calibração, o que aumenta o custo computacional.
  • A truncagem espectral (usar apenas os $T$ primeiros autovetores) é uma alternativa promissora que simplifica a distribuição assintótica para uma $\chi^2$, mas falha em fornecer testes calibrados em regimes não assintóticos (amostras finitas), especialmente para tamanhos de amostra moderados.

O objetivo do trabalho é desenvolver um procedimento de teste não assintótico, calibrado e adaptativo, baseado no MMD normalizado com truncagem espectral, sem a necessidade de divisão de dados.

2. Metodologia

Os autores propõem o st-nMMD (Spectrally Truncated normalized MMD). A metodologia segue os seguintes passos:

2.1 Definição da Estatística

A estatística de teste é definida como:
$$\hat{D}_T^2 = \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}$$
Onde:

• $\hat{\mu}_X, \hat{\mu}_Y$ são os embeddings empíricos das médias.
• $\hat{\Sigma}$ é o estimador do operador de covariância intra-grupo.
• $\hat{\Sigma}_T$ é a versão truncada (mantendo os $T$ maiores autovalores $\hat{\lambda}_t$ e autovetores $\hat{f}_t$).
• A normalização divide a diferença de médias pelos autovalores, atuando como uma distância de Mahalanobis no espaço RKHS.

2.2 Limites de Concentração Não Assintóticos

O núcleo da contribuição teórica é a derivação de um limite superior exponencial para a estatística $\hat{D}_T^2$ sob a hipótese nula.

• Desafio: Controlar as flutuações da estatística quando tanto o numerador (diferença de médias) quanto o denominador (autovalores estimados) são aleatórios.
• Abordagem: Os autores utilizam desigualdades de concentração para processos auto-normalizados (baseadas em Bertail et al., 2008) e teoria de perturbação de operadores.
• Estratégia Local: Em vez de controlar o erro globalmente, eles controlam termo a termo a decomposição espectral. Isso evita que o limite exploda quando os autovalores $\lambda_t$ são pequenos, pois o erro de estimação do autovalor aparece tanto no numerador quanto no denominador da cota.
• Resultado: Eles derivam uma cota explícita $Q(n, \delta, \dots)$ tal que $P(\hat{D}_T^2 > Q) \leq 9T e^{-\delta}$.

2.3 Calibração de Dados e Algoritmo

Para tornar o teste prático, os autores propõem uma aproximação da cota teórica que depende de parâmetros desconhecidos (autovalores e lacunas espectrais).

• Estimador Adaptativo: Eles substituem os parâmetros teóricos por seus estimadores empíricos ($\hat{\lambda}_t, \hat{\Delta}_t$).
• Ajuste de Hiperparâmetros: Introduzem um parâmetro de ajuste $\rho$ (ou $\eta$) que controla a conservatividade do teste. Esse parâmetro é calibrado diretamente nos dados disponíveis, sem necessidade de dividir o conjunto de dados (data-splitting).
• Seleção de $T$: Propõem uma regra heurística para selecionar automaticamente o número de componentes espectrais $T$, baseada na relação sinal-ruído dos autovalores e lacunas espectrais estimados. O teste rejeita $H_0$ se $\hat{D}_T^2 > \hat{Q}_{1-\alpha}(T)$.

3. Principais Contribuições

1. Limites Não Assintóticos: Derivação de desigualdades de concentração exponenciais rigorosas para o st-nMMD, fornecendo uma cota superior explícita e afiada para o quantil sob a hipótese nula.
2. Calibração sem Divisão de Dados: Desenvolvimento de um algoritmo totalmente baseado em dados (data-driven) para estimar o quantil crítico e selecionar o parâmetro de truncagem $T$, eliminando a necessidade de procedimentos de permutação ou divisão de dados, o que reduz o custo computacional.
3. Análise de Regime Assintótico: Demonstração de que o limite não assintótico converge para o comportamento assintótico conhecido (distribuição $\chi^2$ com $T$ graus de liberdade), validando a consistência do método.
4. Validação Empírica: Extensa avaliação experimental mostrando que o teste mantém o nível de erro Tipo I controlado (calibrado) em diversas distribuições, dimensões e tamanhos de amostra, superando a aproximação $\chi^2$ padrão em amostras finitas.

4. Resultados Experimentais

Os autores testaram o método em dados sintéticos (Gaussiana, Uniforme, Cauchy, von Mises-Fisher) e no conjunto de dados MNIST.

• Controle de Erro Tipo I:
  • A aproximação assintótica ($\chi^2$) falha em calibrar o teste para tamanhos de amostra pequenos ($n=100$) e dimensões baixas, apresentando taxas de falso positivo infladas.
  • O método st-nMMD proposto permanece calibrado (a taxa de erro empírica está dentro do intervalo de confiança do nível nominal $\alpha$) independentemente da distribuição, dimensão ou tamanho da amostra.
• Poder Estatístico (Power):
  • Embora o teste seja ligeiramente conservador sob $H_0$ (para garantir a calibração), ele mantém um poder competitivo sob a hipótese alternativa.
  • À medida que o tamanho da amostra aumenta ($n=5000$), o poder do método não assintótico se iguala ao da aproximação assintótica, mas com a vantagem de ser válido para amostras finitas.
• Seleção de $T$: O algoritmo de seleção automática de $T$ tende a escolher valores pequenos, o que é teoricamente coerente sob a hipótese nula (onde componentes de alta ordem contêm apenas ruído), evitando a inflação do erro Tipo I.

5. Significância e Conclusão

Este trabalho preenche uma lacuna importante na teoria de testes de kernel não paramétricos. Enquanto métodos normalizados são conhecidos por serem mais poderosos, sua aplicação prática era limitada pela dificuldade de calibração em amostras finitas.

• Inovação Prática: O método oferece uma solução "plug-and-play" para testes de duas amostras em alta dimensão, sem a penalidade computacional de permutações ou perda de dados por divisão.
• Robustez: A natureza adaptativa do quantil proposto permite que o teste se ajuste à estrutura de covariância dos dados, funcionando bem tanto sob a hipótese nula quanto sob alternativas complexas.
• Impacto: O st-nMMD é particularmente relevante para aplicações em biologia computacional e ciências de dados onde os conjuntos de dados são frequentemente de alta dimensão, mas com tamanhos de amostra moderados, e onde a calibração rigorosa do erro Tipo I é crítica.

Em resumo, os autores transformaram a truncagem espectral de uma aproximação assintótica simples em um procedimento de teste rigoroso, não assintótico e adaptativo, superando as limitações das abordagens anteriores baseadas em Ridge ou permutações.