The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives

Resumo Técnico: O Risco Minimax em Testes de Uniformidade sobre Grandes Alfabetos sob Alternativas de Bola Ausente

Formulação do Problema
O artigo aborda o problema de testar a bondade de ajuste de dados de contagem categóricos para uma distribuição de Poisson uniforme contra uma classe de alternativas definida pela exclusão de uma bola $\ell_p$ ($p \le 2$) de raio $\epsilon$ em torno da sequência de taxas uniformes. Os dados consistem em variáveis aleatórias de Poisson independentes $O_1, \dots, O_N$, com taxas $nQ_i$, onde $N$ é o número de categorias e $n$ é um parâmetro de escala que controla a contagem total esperada. A hipótese nula $H_0$ postula um vetor de taxas uniforme $U = (1/N, \dots, 1/N)$, enquanto a hipótese alternativa $H(Q)$ envolve vetores de taxas $Q$ tais que $\|Q - U\|_p \ge \epsilon$.

O foco principal é o regime de alta dimensão onde $N \gg n$ (especificamente $n = o(N)$), um cenário onde o clássico teste qui-quadrado é conhecido por comportar-se de forma diferente do caso de baixa dimensão ($N = o(n)$). O objetivo é caracterizar o risco minimax $R^*(V_\epsilon)$, definido como o ínfimo sobre todos os testes do supremo da soma dos erros do Tipo I e Tipo II, conforme tanto $N$ quanto $n$ tendem ao infinito.

Metodologia
A análise emprega um framework minimax reduzido a um cenário bayesiano. Os autores estabelecem que o risco minimax é assintoticamente equivalente ao risco de Bayes minimax sobre uma classe específica de priors de produto. A metodologia envolve várias etapas técnicas fundamentais:

1. Redução a Subconjuntos Estruturados: Os autores primeiro identificam e excluem alternativas "fáceis" usando condições de separação elementares baseadas nas estatísticas de soma, qui-quadrado e máximo. Isso reduz o problema a um subconjunto de alternativas $V_{\epsilon, \xi, r}$ onde as taxas são limitadas e a distância $\ell_2$ é controlada.
2. Estatísticas de Teste Lineares: A análise foca em estatísticas de teste lineares da forma $T_w = \sum_{m=0}^\infty w_m X_m$, onde $X_m$ é o número de categorias com exatamente $m$ ocorrências (o histograma dos dados).
3. Normalidade Assintótica: Uma contribuição técnica central é estabelecer a normalidade assintótica uniforme dessas estatísticas lineares sob uma classe de priors. Isso permite que o problema de teste bayesiano seja aproximado por um experimento de deslocamento gaussiano.
4. Otimização sobre Priors: Os autores resolvem um problema de otimização sobre sequências $N$-dimensionais para identificar o "prior menos favorável". Eles mostram que o prior menos favorável é um produto de distribuições simétricas de dois pontos suportadas em $\{1/N \pm \epsilon N^{-1/p}\}$.
5. Conexão com Detecção de Sinais: A estrutura do problema de otimização resultante é mostrada como análoga a resultados clássicos de detecção de sinais dentro de ruído branco gaussiano.

Principais Contribuições e Resultados

• Caracterização do Risco Minimax: O artigo deriva o risco minimax assintótico para o regime onde o risco converge para uma constante $c \in (0, 1)$. O risco é caracterizado pela função:
  $$\lim_{n,N \to \infty} R^*(V_\epsilon) = 2\Phi(-u_{\epsilon,n,N,p}/2)$$
  onde $\Phi$ é a CDF normal padrão e $u_{\epsilon,n,N,p}^2 = \frac{1}{2}\epsilon^4 n^2 N^{3-4/p}$.
  Este resultado fornece uma caracterização de fator constante, indo além dos trabalhos anteriores que apenas estabeleceram ordens de escala de complexidade de amostra ou taxas de convergência.

• O Teste Minimax: O teste assintoticamente minimax é uma estatística linear baseada nas ordenadas do histograma com pesos $w^*_m = g_{m, \lambda_0}(n\epsilon N^{-1/p})$, onde $g$ é uma função simetrizada derivada da função de massa de probabilidade de Poisson.

  • No limite onde a contagem esperada por categoria $\lambda_0 = n/N \to 0$, o teste depende exclusivamente de "colisões exclusivas" (categorias com exatamente 2 ocorrências, $X_2$).
  • Para $\lambda_0$ maiores, o teste comporta-se de forma semelhante ao teste qui-quadrado, mas com ajustes específicos para contagens pequenas.

• Desempenho de Testes Existentes:

  • Teste Qui-Quadrado: O artigo deriva o risco assintótico do teste qui-quadrado sob o prior menos favorável. Demonstra que, a menos que $n/N \to \infty$, o teste qui-quadrado falha em atingir o risco minimax. A lacuna é quantificada por um fator envolvendo $\sqrt{n/(N+n)}$ no argumento da CDF normal.
  • Testes Baseados em Colisões: Testes baseados puramente em colisões (por exemplo, $X_2$) mostram-se subótimos em comparação ao teste minimax completo quando $\lambda_0$ não é de forma a desaparecer, embora se aproximem da otimalidade conforme $\lambda_0 \to 0$.

• Extensão Multinomial: Os autores argumentam que o risco minimax de Poisson derivado caracteriza o risco minimax para o modelo multinomial de tamanho de amostra fixo. Embora o modelo de Poisson sirva como um limite superior, o artigo afirma (referenciando uma nota complementar) que o limite inferior também se mantém para o caso multinomial via teoremas de limite central condicionais.

Significância
O artigo afirma sua significância ao fornecer uma caracterização precisa, de fator constante, do risco minimax em testes de uniformidade de alta dimensão, um regime onde a literatura anterior estava limitada a resultados de ordem ótima. Ao identificar o risco assintótico exato e o correspondente teste minimax, o trabalho permite comparações fundamentadas entre vários estimadores (incluindo aqueles baseados em estatísticas de colisão e qui-quadrado) que alcançam a mesma ordem de escala de complexidade de amostra.

Os resultados esclarecem as limitações do clássico teste qui-quadrado em cenários de alta dimensão, mostrando que sua subotimalidade não é meramente um problema de calibração, mas uma limitação fundamental sob amostragem de Poisson quando $n/N$ não diverge. Além disso, a derivação do prior menos favorável como uma simples distribuição de dois pontos oferece uma compreensão estrutural concreta das alternativas mais "difíceis" nesta classe de problemas. Os estudos empíricos apresentados confirmam que as estimativas de risco assintótico são precisas mesmo em amostras finitas e que o teste minimax proposto supera tanto o teste qui-quadrado quanto os testes baseados em colisões sob a alternativa menos favorável.