Optimal Posterior E-values with Non-Convex Parameter Sets with Applications to Voting Systems

Resumo Técnico: E-valores Posteriores Ótimos com Conjuntos de Parâmetros Não Convexos com Aplicações a Sistemas de Votação

Declaração do Problema
O artigo aborda o desafio de realizar testes de hipóteses sequenciais em dados de preferência, especificamente no contexto de pesquisas políticas e sistemas de votação. O objetivo é determinar o vencedor de uma eleição (sob as regras de Condorcet, Borda ou Schulze) coletando dados de comparações pareadas sequencialmente e interrompendo o processo assim que resultados estatisticamente significativos forem obtidos.

A dificuldade estatística central surge da natureza dos conjuntos de hipóteses. Enquanto o espaço de parâmetros para preferências pareadas (dados de Bernoulli multivariados) é bem definido, os conjuntos de parâmetros correspondentes a vencedores de votação específicos ($H_0$ e $H_1$) podem ser complexos.

• Vencedores de Condorcet e Borda correspondem a conjuntos de parâmetros convexos ou simples.
• Vencedores de Schulze correspondem a conjuntos de parâmetros não convexos compostos por uma união de muitos componentes convexos (definidos por ordenações estritas de preferências).

Métodos existentes para construir testes sequenciais ótimos, como os e-valores de Taxa de Crescimento Ótima (GRO - Growth Rate Optimal), frequentemente dependem da convexidade do conjunto da hipótese nula ($H_0$) para calcular Projeções de Informação Reversa (RIPr - Reverse Information Projections). O artigo visa desenvolver uma teoria e um algoritmo capazes de lidar com hipóteses compostas gerais, incluindo conjuntos não convexos como os do método de votação de Schulze.

Metodologia
Os autores propõem um framework baseado em E-valores Posteriores Ótimos (POE - Posterior Optimal E-values).

1. Framework Teórico (POE):

   • Baseando-se no critério GRO, que maximiza o crescimento logarítmico esperado de um e-valor sob uma alternativa específica, os autores estendem isso para alternativas compostas usando uma perspectiva bayesiana.
   • Eles definem uma função de utilidade para um e-valor $E$ baseada em uma priori $\pi$ sobre o conjunto de parâmetros da alternativa $\Phi_1$. O objetivo é encontrar um supermartingal de teste que maximize a utilidade integrada $G_t(E, \pi, \tau)$ para qualquer tempo de parada $\tau$.
   • O Teorema 2 estabelece que o e-valor ótimo (POE) é o produto de e-valores ótimos de um passo. Cada passo envolve o cálculo de uma razão de verossimilhança onde o numerador é a distribuição preditiva posterior e o denominador é a projeção desta posterior sobre o conjunto nulo $H_0$.
   • Diferente de abordagens anteriores (ex: Turner e Grunwald, 2022) que dependem de simplificações para conjuntos convexos ou dimensões fixas, a formulação POE é geral e aplica-se a qualquer $H_0$ e $H_1$ definidos por conjuntos de parâmetros, desde que a divergência KL seja finita.

2. Implementação Algorítmica (Frank-Wolfe para RIPr):

   • Calcular o POE requer resolver um problema de Projeção de Informação Reversa (RIPr) em cada passo temporal: encontrar uma distribuição em $H_0$ que minimize a divergência KL da distribuição preditiva posterior atual.
   • Algoritmos padrão (como o algoritmo de Li) são computacionalmente caros para dados de Bernoulli multivariados de alta dimensão.
   • Os autores adaptam o algoritmo de Frank-Wolfe para este problema. Ao aproveitar o suporte finito das distribuições (o espaço de $2^D$ resultados), eles recodificam a otimização em $\mathbb{R}^{2^D}$.
   • O Lema 5 prova que os pontos extremais do conjunto de distribuições sobre um conjunto de parâmetros $\Phi'$ são distribuições de Dirac ($P_{\delta_\phi}$). Isso permite que o algoritmo de Frank-Wolfe busque a projeção ótima iterando sobre os pontos extremais (medidas de Dirac) do conjunto de parâmetros.
   • Esta abordagem permite o cálculo da RIPr mesmo quando $H_0$ é uma união não convexa de conjuntos convexos (como no método Schulze), um cenário onde métodos baseados em GRO anteriores falharam.

3. Procedimentos de Teste:

   • Teste de Tamanho de Amostra Limitado (Capped Sample Size Test): Um teste de orçamento fixo que interrompe se o e-valor exceder $1/\alpha$ ou atingir um tamanho de amostra máximo pré-calculado $T$.
   • Teste de Confiança Fixa (PPOE): Um teste paralelo usando duas sequências de e-valores (uma para $H_0$ vs $H_1$, outra para $H_1$ vs $H_0$). Ele interrompe quando qualquer sequência excede seu limiar, fornecendo garantias sobre taxas de falsos positivos e poder sem um limite rígido de tamanho de amostra.

Principais Contribuições

• E-valores Posteriores Ótimos (POE): Um novo critério de otimalidade de e-valor que generaliza o GRO para hipóteses compostas usando uma priori bayesiana. É demonstrado que o POE é o produto de e-valores de um passo condicionados à posterior.
• Lidando com Conjuntos Não Convexos: O artigo fornece o primeiro tratamento estatístico do sistema de votação de Schulze, que envolve conjuntos de parâmetros não convexos.
• Algoritmo de RIPr Eficiente: Os autores introduzem um algoritmo baseado em Frank-Wolfe para calcular Projeções de Informação Reversa para dados de Bernoulli multivariados. Este método é eficiente o suficiente para lidar com uniões não convexas de conjuntos convexos exigidas pela votação de Schulze, superando as limitações de métodos anteriores restritos a $H_0$ convexo.
• Garantias Teóricas: O artigo deriva desigualdades de concentração para o POE e fornece limites para o tempo de parada esperado para testes de amostra fixa e confiança fixa, mostrando otimalidade em termos de complexidade de amostragem.

Resultados Experimentais
Os autores validam seu método através de simulações e dados do mundo real:

• Dados Sintéticos: Comparações contra métodos de estado da arte (Inferência Universal, GLRT, e-valores de Turner-Grunwald e GRO) para cenários de votação de Condorcet, Borda e Schulze com 3 candidatos.
  • O POE e sua variante paralela (PPOE) demonstram poder competitivo e complexidade de amostragem.
  • O POE mostra-se essencial para a votação de Schulze (não convexo $H_0$), onde métodos restritos a convexidade não podem ser aplicados diretamente.
  • O método beneficia-se de "dados prévios" (pré-treinamento da priori $\pi$), convergindo para o desempenho de um teste GRO de oráculo conforme a informação prévia aumenta.
• Aplicação em Dados Reais: O método é aplicado a dados de preferência pareada da Eleição Presidencial Francesa de 2022.
  • O objetivo era determinar o vencedor de Borda usando testes sequenciais.
  • Usando o estimador Turner-Grunwald (suficiente para o caso convexo de Borda), o teste eliminou candidatos sequencialmente.
  • O experimento concluiu que Yannick Jadot teria sido o vencedor de Borda. O teste exigiu significativamente menos amostras (171 eleitores, 4.721 comparações pareadas) do que pesquisas políticas tradicionais (ex: IPSOS usou 7.321 eleitores) para chegar a uma conclusão definitiva.

Significância e Alegações
O artigo afirma fornecer um framework geral para testes sequenciais em votação de preferência que não é limitado pela convexidade dos conjuntos de hipóteses.

• É a primeira abordagem estatística para abordar o sistema de votação de Schulze, que é notoriamente difícil devido ao seu espaço de parâmetros não convexo.
• O algoritmo de Frank-Wolfe proposto oferece uma maneira prática de calcular Projeções de Informação Reversa para distribuições de suporte finito, potencialmente estendendo-se além da votação para outros contextos com restrições não convexas.
• Os autores observam que, embora o POE e o estimador TG mais simples tenham desempenho semelhante em cenários convexos (como Borda), o POE é necessário para cenários não convexos. Eles reconhecem que o custo computacional do POE (devido às atualizações de Frank-Wolfe) é maior que o do TG, mas o compromisso é necessário para problemas não convexos.
• O trabalho destaca a viabilidade de testes sequenciais em cenários de alta dimensão do mundo real, demonstrando que conclusões estatisticamente significativas podem ser alcançadas com menos amostras do que os métodos tradicionais de pesquisa de opinião.

Os autores mantêm-se modestos quanto às direções futuras, apontando questões em aberto sobre as taxas de convergência de sua implementação de Frank-Wolfe, a necessidade do $\epsilon$-slack para suavidade e o potencial para métodos mais eficientes para lidar com o número explosivo de componentes convexos na votação de Schulze de alta dimensão.