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

Résumé Technique : E-values Postérieures Optimales avec des Ensembles de Paramètres Non-Convexes et Applications aux Systèmes de Vote

Énoncé du Problème
L'article traite du défi consistant à mener des tests d'hypothèses séquentiels sur des données de préférences, spécifiquement dans le contexte des sondages politiques et des systèmes de vote. L'objectif est de déterminer le vainqueur d'une élection (sous les règles de Condorcet, Borda ou Schulze) en collectant séquentiellement des données de comparaisons par paires et en s'arrêtant dès que des résultats statistiquement significatifs sont obtenus.

La difficulté statistique centrale provient de la nature des ensembles d'hypothèses. Bien que l'espace des paramètres pour les préférences par paires (données de Bernoulli multivariées) soit bien défini, les ensembles de paramètres correspondant à des vainqueurs de vote spécifiques ($H_0$ et $H_1$) peuvent être complexes.

• Les vainqueurs de Condorcet et de Borda correspondent à des ensembles de paramètres convexes ou simples.
• Les vainqueurs de Schulze correspondent à des ensembles de paramètres non-convexes composés d'une union de nombreux composants convexes (définis par des ordonnancements stricts des préférences).

Les méthodes existantes pour construire des tests séquentiels optimaux, telles que les e-values de type Growth Rate Optimal (GRO), reposent souvent sur la convexité de l'ensemble de l'hypothèse nulle ($H_0$) pour calculer les Projections d'Information Inverses (RIPr). L'article vise à développer une théorie et un algorithme capables de gérer des hypothèses composites générales, y compris des ensembles non-convexes comme ceux de la méthode de vote de Schulze.

Méthodologie
Les auteurs proposent un cadre basé sur les E-values Postérieures Optimales (POE).

1. Cadre Théorique (POE) :

   • S'appuyant sur le critère GRO, qui maximise l'espérance du logarithme de la croissance d'une e-value sous une alternative spécifique, les auteurs étendent cela aux alternatives composites en utilisant une perspective bayésienne.
   • Ils définissent une fonction d'utilité pour une e-value $E$ basée sur une loi a priori $\pi$ sur l'ensemble des paramètres alternatifs $\Phi_1$. L'objectif est de trouver une supermartingale de test qui maximise l'utilité intégrée $G_t(E, \pi, \tau)$ pour tout temps d'arrêt $\tau$.
   • Le Théorème 2 établit que l'e-value optimale (POE) est le produit d'e-values optimales à une étape. Chaque étape implique le calcul d'un rapport de vraisemblance où le numérateur est la distribution prédictive postérieure et le dénominateur est la projection de cette postérieure sur l'ensemble nul $H_0$.
   • Contrairement aux approches précédentes (par exemple, Turner et Grunwald, 2022) qui reposent sur des simplifications spécifiques pour les ensembles convexes ou des dimensions fixes, la formulation POE est générale et s'applique à n'importe quels $H_0$ et $H_1$ définis par des ensembles de paramètres, à condition que la divergence de Kullback-Leibler soit finie.

2. Implémentation Algorithmique (Frank-Wolfe pour la RIPr) :

   • Calculer la POE nécessite de résoudre un problème de Projection d'Information Inverse (RIPr) à chaque étape : trouver une distribution dans $H_0$ qui minimise la divergence de Kullback-Leibler par rapport à la distribution prédictive postérieure actuelle.
   • Les algorithmes standards (comme l'algorithme de Li) sont coûteux en termes de calcul pour les données de Bernoulli multivariées à haute dimension.
   • Les auteurs adaptent l'algorithme de Frank-Wolfe à ce problème. En exploitant le support fini des distributions (l'espace des $2^D$ issues possibles), ils recadrent l'optimisation dans $\mathbb{R}^{2^D}$.
   • Le Lemme 5 prouve que les points extrémaux de l'ensemble des distributions sur un ensemble de paramètres $\Phi'$ sont les distributions de Dirac ($P_{\delta_\phi}$). Cela permet à l'algorithme de Frank-Wolfe de rechercher la projection optimale en itérant sur les points extrémaux (mesures de Dirac) de l'ensemble de paramètres.
   • Cette approche permet le calcul de la RIPr même lorsque $H_0$ est une union non-convexe d'ensembles convexes (comme dans la méthode de Schulze), un scénario où les méthodes antérieures basées sur le GRO échouaient.

3. Procédures de Test :

   • Test à Taille d'Échantillon Bornée (Capped Sample Size Test) : Un test à budget fixe qui s'arrête si l'e-value dépasse $1/\alpha$ ou atteint une taille d'échantillon maximale $T$ précalculée.
   • Test à Confiance Fixe (PPOE) : Un test parallèle utilisant deux séquences d'e-values (une pour $H_0$ vs $H_1$, une pour $H_1$ vs $H_0$). Il s'arrête lorsque l'une des séquences dépasse son seuil, fournissant des garanties sur les taux de faux positifs et la puissance sans imposer de limite stricte de taille d'échantillon.

Principales Contributions

• E-values Postérieures Optimales (POE) : Un nouveau critère d'optimalité des e-values qui généralise le GRO aux hypothèses composites en utilisant une loi a priori bayésienne. Il est démontré que la POE est le produit d'e-values optimales à une étape conditionnées par la postérieure.
• Gestion des Ensembles Non-Convexes : L'article fournit le premier traitement statistique du système de vote de Schulze, qui implique des ensembles de paramètres non-convexes.
• Algorithme RIPr Efficace : Les auteurs introduisent un algorithme basé sur Frank-Wolfe pour calculer les Projections d'Information Inverse pour les données de Bernoulli multivariées. Cette méthode est suffisamment efficace pour gérer les unions non-convexes d'ensembles convexes requises pour le vote de Schulze, surmontant les limitations des méthodes antérieures restreintes à un $H_0$ convexe.
• Garanties Théoriques : L'article dérive des inégalités de concentration pour la POE et fournit des bornes sur le temps d'arrêt attendu pour les tests à échantillon fixe et à confiance fixe, démontrant l'optimalité en termes de complexité d'échantillonnage.

Résultats Expérimentaux
Les auteurs valident leur méthode via des simulations et des données réelles :

• Données Synthétiques : Comparaisons avec des méthodes de pointe (Universal Inference, GLRT, e-values de Turner-Grunwald, et GRO) sur des scénarios de vote de Condorcet, Borda et Schulze avec 3 candidats.
  • La POE et sa variante parallèle (PPOE) démontrent une puissance et une complexité d'échantillonnage compétitives.
  • Il est montré que la POE est essentielle pour le vote de Schulze (non-convexité de $H_0$), où les méthodes restreintes au convexe ne peuvent pas être appliquées directement.
  • La méthode bénéficie des "données a priori" (pré-entraînement de la loi $\pi$), convergeant vers la performance d'un test GRO oracle à mesure que l'information a priori augmente.
• Application aux Données Réelles : La méthode est appliquée aux données de préférences par paires de l'élection présidentielle française de 2022.
  • L'objectif était de déterminer le vainqueur de Borda par test séquentiel.
  • En utilisant l'estimateur de Turner-Grunwald (suffisant pour le cas convexe de Borda), le test a éliminé séquentiellement les candidats.
  • L'expérience a conclu que Yannick Jadot aurait été le vainqueur de Borda. Le test a nécessité nettement moins d'échantillons (171 électeurs, 4 721 comparaisons par paires) que les sondages politiques traditionnels (par exemple, IPSOS en a utilisé 7 321) pour parvenir à une conclusion définitive.

Signification et Revendications
L'article affirme fournir un cadre général pour le test séquentiel dans le vote de préférence qui n'est pas limité par la convexité des ensembles d'hypothèses.

• Il s'agit de la première approche statistique pour aborder le système de vote de Schulze, qui est notoirement difficile en raison de son espace de paramètres non-convexe.
• L'algorithme de Frank-Wolfe proposé offre un moyen pratique de calculer les Projections d'Information Inverse pour les distributions à support fini, potentiellement extensible au-delà du vote vers d'autres contextes avec des contraintes non-convexes.
• Les auteurs notent que si la POE et l'estimateur TG plus simple se comportent de manière similaire dans les contextes convexes (comme Borda), la POE est nécessaire pour les contextes non-convexes. Ils reconnaissent que le coût computationnel de la POE (dû aux mises à jour de Frank-Wolfe) est plus élevé que celui de TG, mais que ce compromis est nécessaire pour les problèmes non-convexes.
• Ce travail souligne la faisabilité des tests séquentiels dans des scénarios réels à haute dimension, démontant que des conclusions statistiquement significatives peuvent être atteintes avec moins d'échantillons que les méthodes de sondage traditionnelles.

Les auteurs restent modestes quant aux directions futures, notant des questions ouvertes concernant les taux de convergence de leur implémentation de Frank-Wolfe, la nécessité du $\epsilon$-slack pour la lissité, et le potentiel de méthodes plus efficaces pour gérer le nombre explosif de composants convexes dans le vote de Schulze à haute dimension.