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

Resumen Técnico: E-valores Posteriores Óptimos con Conjuntos de Parámetros No Convexos con Aplicaciones a Sistemas de Votación

Planteamiento del Problema
El artículo aborda el desafío de realizar pruebas de hipótesis secuenciales sobre datos de preferencias, específicamente dentro del contexto de las encuestas políticas y los sistemas de votación. El objetivo es determinar al ganador de una elección (bajo las reglas de Condorcet, Borda o Schulze) mediante la recopilación secuencial de datos de comparaciones por pares y deteniéndose tan pronto como se obtengan resultados estadísticamente significativos.

La dificultad estadística central surge de la naturaleza de los conjuntos de hipótesis. Mientras que el espacio de parámetros para las preferencias por pares (datos de Bernoulli multivariantes) está bien definido, los conjuntos de parámetros correspondientes a ganadores de votación específicos ($H_0$ y $H_1$) pueden ser complejos.

• Los ganadores de Condorcet y Borda corresponden a conjuntos de parámetros convexos o simples.
• Los ganadores de Schulze corresponden a conjuntos de parámetros no convexos compuestos por una unión de muchos componentes convexos (definidos por ordenamientos estrictos de preferencias).

Los métodos existentes para construir pruebas secuenciales óptimas, como los e-valores de Tasa de Crecimiento Óptima (GRO, por sus siglas en inglés), a menudo dependen de la convexidad del conjunto de la hipótesis nula ($H_0$) para calcular las Proyecciones de Información Inversa (RIPr). El artículo tiene como objetivo desarrollar una teoría y un algoritmo capaces de manejar hipótesis compuestas generales, incluyendo los conjuntos no convexos como los del método de votación de Schulze.

Metodología
Los autores proponen un marco basado en E-valores Óptimos Posteriores (POE).

1. Marco Teórico (POE):

   • Basándose en el criterio GRO, que maximiza el crecimiento logarítmico esperado de un e-valor bajo una alternativa específica, los autores lo extienden a alternativas compuestas utilizando una perspectiva bayesiana.
   • Definen una función de utilidad para un e-valor $E$ basada en una distribución previa $\pi$ sobre el conjunto de parámetros alternativos $\Phi_1$. El objetivo es encontrar un supermartingala de prueba que maximice la utilidad integrada $G_t(E, \pi, \tau)$ para cualquier tiempo de parada $\tau$.
   • El Teorema 2 establece que el e-valor óptimo (POE) es el producto de e-valores óptimos de un solo paso. Cada paso implica el cálculo de una razón de verosimilitud donde el numerador es la distribución predictiva posterior y el denominador es la proyección de esta posterior sobre el conjunto nulo $H_0$.
   • A diferencia de enfoques previos (como Turner y Grunwald, 2022) que dependen de simplificaciones específicas para conjuntos convexos o dimensiones fijas, la formulación POE es general y se aplica a cualquier $H_0$ y $H_1$ definidos por conjuntos de parámetros, siempre que la divergencia KL sea finita.

2. Implementación Algorítmica (Frank-Wolfe para RIPr):

   • Calcular el POE requiere resolver un problema de Proyección de Información Inversa (RIPr) en cada paso de tiempo: encontrar una distribución en $H_0$ que minimice la divergencia KL desde la distribución predictiva posterior actual.
   • Los algoritmos estándar (como el algoritmo de Li) son computacionalmente costosos para datos de Bernoulli multivariantes de alta dimensión.
   • Los autores adaptan el algoritmo de Frank-Wolfe a este problema. Aprovechando el soporte finito de las distribuciones (el espacio de $2^D$ resultados), reformulan la optimización en $\mathbb{R}^{2^D}$.
   • El Lema 5 demuestra que los puntos extremales del conjunto de distribuciones sobre un conjunto de parámetros $\Phi'$ son distribuciones de Dirac ($P_{\delta_\phi}$). Esto permite que el algoritmo de Frank-Wolfe busque la proyección óptima iterando sobre los puntos extremales (medidas de Dirac) del conjunto de parámetros.
   • Este enfoque permite el cálculo de la RIPr incluso cuando $H_0$ es una unión no convexa de conjuntos convexos (como en el método de votación de Schulze), un escenario donde los métodos previos basados en GRO fallaron.

3. Procedimientos de Prueba:

   • Prueba de Tamaño de Muestra Acotada: Una prueba de presupuesto fijo que se detiene si el e-valor supera $1/\alpha$ o alcanza un tamaño de muestra máximo precalculado $T$.
   • Prueba de Confianza Fija (PPOE): Una prueba paralela que utiliza dos secuencias de e-valores (uno para $H_0$ vs $H_1$, y otro para $H_1$ vs $H_0$). Se detiene cuando cualquiera de las secuencias supera su umbral, proporcionando garantías sobre las tasas de falsos positivos y el poder sin un límite estricto de tamaño de muestra.

Contribuciones Clave

• E-valores Óptimos Posteriores (POE): Un nuevo criterio de optimalidad de e-valores que generaliza el GRO a hipótesis compuestas utilizando una distribución previa bayesiana. Se demuestra que es el producto de e-valores óptimos de un solo paso condicionados a la posterior.
• Manejo de Conjuntos No Convexos: El artículo proporciona el primer tratamiento estadístico del sistema de votación de Schulze, el cual involucra conjuntos de parámetros no convexos.
• Algoritmo de RIPr Eficiente: Los autores introducen un algoritmo basado en Frank-Wolfe para calcular Proyecciones de Información Inversa para datos de Bernoulli multivariantes. Este método es lo suficientemente eficiente como para manejar las uniones no convexas de conjuntos convexos requeridas para la votación de Schulze, superando las limitaciones de los métodos previos restringidos a un $H_0$ convexo.
• Garantías Teóricas: El artículo deriva desigualdades de concentración para el POE y proporciona límites para el tiempo de parada esperado tanto para las pruebas de muestra fija como para las de confianza fija, mostrando la optimalidad en términos de complejidad de muestra.

Resultados Experimentales
Los autores validan su método mediante simulaciones y datos del mundo real:

• Datos Sintéticos: Comparaciones contra métodos de vanguardia (Inferencia Universal, GLRT, e-valores de Turner-Grunwald y GRO) en escenarios de votación de Condorcet, Borda y Schulze con 3 candidatos.
  • El POE y su variante paralela (PPOE) demuestran un poder y una complejidad de muestra competitivos.
  • Se muestra que el POE es esencial para la votación de Schulke (no convexa $H_0$), donde los métodos restringidos a la convexidad no pueden aplicarse directamente.
  • El método se beneficia de los "datos previos" (pre-entrenar la distribución previa $\pi$), convergiendo hacia el rendimiento de una prueba GRO de oráculo a medida que aumenta la información previa.
• Aplicación a Datos Reales: El método se aplica a datos de preferencias por pares de las elecciones presidenciales francesas de 2022.
  • El objetivo era determinar al ganador de Borda mediante pruebas secuenciales.
  • Utilizando el estimador de Turner-Grunwald (suficiente para el caso convexo de Borda), la prueba eliminó candidatos secuencialmente.
  • El experimento concluyó que Yannick Jadot habría sido el ganador de Borda. La prueba requirió significativamente menos muestras (171 votantes, 4,721 comparaciones por pares) que las encuestas políticas tradicionales (por ejemplo, IPSOS utilizó 7,321 votantes) para llegar a una conclusión definitiva.

Significado y Reivindicaciones
El artículo afirma proporcionar un marco general para la votación secuencial de preferencias que no está limitado por la convexidad de los conjuntos de hipótesis.

• Es el primer enfoque estadístico para abordar el sistema de votación de Schulze, que es notoriamente difícil debido a su espacio de parámetros no convexo.
• El algoritmo de Frank-Wolfe propuesto ofrece una forma práctica de calcular Proyecciones de Información Inversa para distribuciones de soporte finito, lo que potencialmente extiende su uso más allá de la votación a otros entornos con restricciones no convexas.
• Los autores señalan que, si bien el POE y el estimador TG más simple se comportan de manera similar en entornos convexos (como Borda), el POE es necesario en entornos no convexos. Reconocen que el costo computacional del POE (debido a las actualizaciones de Frank-Wolfe) es mayor que el de TG, pero el intercambio es necesario para problemas no convexos.
• El trabajo destaca la viabilidad de las pruebas secuenciales en escenarios del mundo real de alta dimensión, demostrando que se pueden alcanzar conclusiones estadísticamente significativas con menos muestras que los métodos de encuestas tradicionales.

Los autores mantienen la modestia respecto a las direcciones futuras, señalando preguntas abiertas sobre las tasas de convergencia de su implementación de Frank-Wolfe, la necesidad del $\epsilon$-slack para la suavidad, y el potencial de métodos más eficientes para manejar el número explosivo de componentes convexas en la votación de Schulze de alta dimensión.