Cheap Permutation Testing

Resumo Técnico: Teste de Permutação Barato

Enunciado do Problema
Testes de permutação são um pilar da estatística não paramétrica e do aprendizado de máquina, amplamente utilizados para testar homogeneidade (testes de duas amostras) e independência. Eles são favorecidos por sua capacidade de fornecer controle exato de falsos positivos (erro do Tipo I) em amostras finitas e por sua otimalidade minimax quando combinados com U-estatísticas e V-estatísticas. No entanto, os testes de permutação padrão sofrem de custos computacionais proibitivos. Para alcançar um poder confiável, eles tipicamente requerem o recálculo de uma estatística de teste centenas ou milhares de vezes ($B$ permutações) sobre $n$ pontos de dados. Para estatísticas de teste quadráticas como a Discrepância de Média Máxima (MMD) ou o Critério de Independência de Hilbert-Schmidt (HSIC), isso resulta em uma complexidade de tempo de execução de $\Theta(Bn^2)$, tornando-os inviáveis para conjuntos de dados de larga escala.

Metodologia
Os autores propõem o "teste de permutação barato", uma estratégia que acelera o procedimento de teste agrupando pontos de dados em $s$ bins (compartimentos) e permutando os rótulos dos bins em vez dos pontos de dados individuais.

1. Permutação por Bin: Em vez de permutar $n$ índices, o método particiona os índices $[n]$ em $s$ bins consecutivos de tamanho igual. A estatística de teste é computada sobre as amostras formadas pela permutação desses $s$ bins.
2. Estatísticas Suficientes: A inovação central reside no uso de estatísticas suficientes compactas. Para estatísticas de teste quadráticas (incluindo U-estatísticas de homogeneidade e V-estatísticas de independência), os autores demonstram que as estatísticas de teste permutadas dependem apenas de agregados pré-computados das funções base sobre os bins.
   • Para testes de homogeneidade, o método pré-computa $3s^2$ estatísticas suficientes (somas de funções base sobre pares de bins).
   • Para testes de independência (especificamente usando permutações de bootstrap selvagem/wild bootstrap), o método pré-computa $s^2/2$ estatísticas suficientes.
3. Eficiência Algorítmica: Uma vez que a estatística de teste inicial e as $O(s^2)$ estatísticas suficientes sejam computadas (levando tempo $\Theta(n^2)$), cada uma das $B$ estatísticas permutadas pode ser computada em $\Theta(s^2)$ de tempo. Consequentemente, o tempo de execução total torna-se $\Theta(n^2 + Bs^2)$. Se $s$ for escolhido como uma constante ou uma função de crescimento lento de $n$, o overhead de permutação torna-se negligenciável em comparação ao custo de avaliar uma única estatística de teste.

Principais Contribuições
O artigo apresenta várias contribuições teóricas e práticas:

1. Exatidão e Validade: Os autores provam que os testes de permutação baratos (Algoritmos 1 e 2) são exatos. Sob a hipótese nula, eles rejeitam com probabilidade exatamente $\alpha$ para qualquer tamanho de amostra, distribuição de dados e número de permutações $B$, herdando a validade de amostra finita dos testes de permutação padrão.
2. Garantias de Poder: O artigo estabelece garantias quantitativas de poder para testes baratos usando U e V-estatísticas.
   • Homogeneidade: Mostra-se que o limiar de separação necessário para que um teste barato alcance o poder $1-\beta$ é assintoticamente equivalente ao dos testes de permutação padrão. Notavelmente, essa equivalência mantém-se mesmo quando o número de bins $s$ é independente do tamanho da amostra $n$ (por exemplo, $s$ é constante), desde que $s$ seja suficientemente grande em relação aos componentes de variância.
   • Independência: Garantias semelhantes são estabelecidas para testes de independência usando permutações de bootstrap selvagem sobre bins. As taxas de separação correspondem às taxas de teste padrão mesmo com um número constante de bins.
3. Otimatilidade Minimax: Os autores estendem esses resultados para estabelecer a taxa de otimalidade minimax do teste barato para quatro problemas clássicos: homogeneidade discreta, homogeneidade Hölder, independência discreta e independência Hölder. Além disso, provam a otimalidade minimax para testes de homogeneidade baseados em MMD e testes de independência baseados em HSIC. Em todos os casos, as taxas de detecção ótimas são alcançáveis com um número de bins $s$ que é independente de $n$.
4. Análise Refinada: O artigo melhora a análise de poder existente para testes de permutação padrão ao refinar a dependência no número de permutações $B$ e no nível de significância $\alpha$, utilizando um método de comparação de quantis que produz limites mais estreitos do que as abordagens anteriores de "dois momentos".

Resultados
As descobertas teóricas são complementadas por experimentos extensos comparando testes de permutação baratos contra testes de permutação padrão e outros métodos de estado da arte (incluindo cross-MMD/HSIC assintótico, MMD agregado e características de Fourier aleatórias/random Fourier features).

• Homogeneidade (MMD, WMW, MMD Agregado): Experimentos mostram que testes baratos com um pequeno número de bins (por exemplo, $s=32$ ou $s=128$) alcançam um poder quase idêntico ao dos testes de permutação padrão em vários tamanhos de amostra. No entanto, eles são consistentemente 100 a 900 vezes mais rápidos.
• Independência (HSIC): Testes HSIC baratos com $s=64$ ou $s=128$ bins igualam o poder dos testes de bootstrap selvagem padrão, sendo aproximadamente 15 vezes mais rápidos.
• Comparação com Métodos Assintóticos: Embora os métodos assintóticos (como cross-MMD) sejam rápidos, eles sacrificam a validade de amostra finita e frequentemente exibem poder reduzido. Os testes de permutação baratos alcançam os benefícios de velocidade desses métodos assintóticos, mantendo a validade exata de amostra finita e o poder superior dos testes de permutação padrão.
• Escalabilidade: O tempo de execução dos testes baratos permanece essencialmente constante à medida que o tamanho da amostra $n$ aumenta (uma vez computada a estatística inicial $O(n^2)$), enquanto os testes de permutação padrão escalam linearmente com $n$ para o mesmo nível de poder.

Significância
O artigo afirma que o teste de permutação barato oferece um "remédio simples" para o gargalo computacional do teste não paramétrico sem sacrificar o rigor estatístico. Ao desacoplar o overhead de permutação do tamanho da amostra $n$, o método permite o uso de testes de permutação exatos e minimax-ótimos em regimes onde eles eram anteriormente computacionalmente proibitivos. Os autores enfatizam que esta abordagem permite que os pesquisadores mantenham o controle exato de falsos positivos e a otimalidade minimax dos testes de permutação padrão, enquanto operam em uma fração do tempo, tornando o teste de hipótese rigoroso viável para aplicações de dados em larga escala. O trabalho sugere que, para estatísticas de teste quadráticas, o "custo" da exatidão não precisa ser alto, desde que se utilize a estrutura de estatísticas suficientes por bin.