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

Sintesi Tecnica: E-value Posteriori Ottimali con Insiemi di Parametri Non Convessi con Applicazioni ai Sistemi di Voto

Definizione del Problema
Il documento affronta la sfida di condurre test d'ipotesi sequenziali su dati di preferenza, specificamente nel contesto dei sondaggi politici e dei sistemi di voto. L'obiettivo è determinare il vincitore di un'elezione (sotto le regole di Condorcet, Borda o Schulze) raccogliendo dati di confronto a coppie in modo sequenziale e fermandosi non appena si ottengono risultati statisticamente significativi.

La difficoltà statistica centrale deriva dalla natura degli insiemi di ipotesi. Mentre lo spazio dei parametri per le preferenze a coppie (dati Bernoulli multivariati) è ben definito, gli insiemi di parametri corrispondenti a specifici vincitori di votazioni ($H_0$ e $H_1$) possono essere complessi.

• I vincitori di Condorcet e Borda corrispondono a insiemi di parametri convessi o semplici.
• I vincitori di Schulze corrispondono a insiemi di parametri non convessi composti da una unione di molti componenti convessi (definiti da ordinamenti stretti delle preferenze).
  I metodi esistenti per la costruzione di test sequenziali ottimali, come gli e-value Growth Rate Optimal (GRO), spesso si basano sulla convessità dell'insieme dell'ipotesi nulla ($H_0$) per calcolare le Proiezioni di Informazione Inversa (RIPr). Il presente articolo mira a sviluppare una teoria e un algoritmo capaci di gestire ipotesi composte generali, inclusi gli insiemi non convessi come quelli del metodo di voto Schulze.

Metodologia
Gli autori propongono un framework basato sugli E-value Posteriori Ottimali (POE).

1. Framework Teorico (POE):

   • Costruendo sul criterio GRO, che massimizza il logaritmo atteso della crescita di un e-value sotto un'alternativa specifica, gli autori estendono questo concetto alle ipotesi composte utilizzando una prospettiva bayesiana.
   • Definiscono una funzione di utilità per un e-value $E$ basata su un prior $\pi$ sull'insieme dei parametri alternativi $\Phi_1$. L'obiettivo è trovare un supermartingala di test che massimizzi l'utilità integrata $G_t(E, \pi, \tau)$ per qualsiasi tempo di arresto $\tau$.
   • Il Teorema 2 stabilisce che l'e-value ottimale (POE) è il prodotto di e-value ottimali a singolo step. Ogni step comporta il calcolo di un rapporto di verosimiglianza in cui il numeratore è la distribuzione predittiva posteriore e il denominatore è la proiezione di questa posteriore sull'insieme nullo $H_0$.
   • A differenza di approcci precedenti (ad esempio, Turner e Grunwald, 2022) che si affidano a specifiche semplificazioni per insiemi convessi o dimensioni fisse, la formulazione POE è generale e si applica a qualsiasi $H_0$ e $H_1$ definiti da insiemi di parametri, a condizione che la divergenza KL sia finita.

2. Implementazione Algoritmica (Frank-Wolfe per RIPr):

   • Calcolare il POE richiede la risoluzione di un problema di Proiezione di Informazione Inversa (RIPr) ad ogni step temporale: trovare una distribuzione in $H_0$ che minimizzi la divergenza KL dalla distribuzione predittiva posteriore corrente.
   • Gli algoritmi standard (come l'algoritmo di Li) sono computazionalmente costosi per dati Bernoulli multivariati ad alta dimensione.
   • Gli autori adattano l'algoritmo di Frank-Wolfe a questo problema. Sfruttando il supporto finito delle distribuzioni (lo spazio di $2^D$ possibili esiti), ricasciano l'ottimizzazione in $\mathbb{R}^{2^D}$.
   • Il Lemma 5 dimostra che i punti estremi dell'insieme delle distribuzioni su un insieme di parametri $\Phi'$ sono distribuzioni di Dirac ($P_{\delta_\phi}$). Ciò consente all'algoritmo di Frank-Wolfe di cercare la proiezione ottimale iterando sui punti estremi (misure di Dirac) dell'insieme dei parametri.
   • Questo approccio permette il calcolo della RIPr anche quando $H_0$ è un'unione non convessa di insiemi convessi (come nel metodo Schulze), uno scenario in cui i precedenti metodi basati su GRO fallivano.

3. Procedure di Test:

   • Capped Sample Size Test: Un test a budget fisso che si interrompe se l'e-value supera $1/\alpha$ o raggiunge un numero massimo di campioni pre-calcolato $T$.
   • Fixed Confidence Test (PPOE): Un test parallelo che utilizza due sequenze di e-value (una per $H_0$ vs $H_1$, una per $H_1$ vs $H_0$). Si interrompe quando una delle due sequenze supera la propria soglia, fornendo garanzie sui tassi di falsi positivi e sulla potenza senza un limite rigido sulla dimensione del campione.

Contributi Chiave

• E-value Posteriori Ottimali (POE): Un nuovo criterio di ottimalità per gli e-value che generalizza il GRO alle ipotesi composte utilizzando un prior bayesiano. È dimostrato che il POE è il prodotto di e-value ottimali a singolo step condizionati dalla posteriore.
• Gestione di Insiemi Non Convessi: Il documento fornisce il primo trattamento statistico del sistema di voto Schulze, che comporta insiemi di parametri non convessi.
• Algoritmo RIPr Efficiente: Gli autori introducono un algoritmo basato su Frank-Wolfe per calcolare le Proiezioni di Informazione Inversa per distribuzioni a supporto finito, un metodo sufficientemente efficiente da gestire le unioni non convesse di insiemi convessi richieste dallo schema di voto Schulze, superando le limitazioni dei metodi precedenti limitati a $H_0$ convessi.
• Garanzie Teoriche: Il documento deriva disuguaglianze di concentrazione per il POE e fornisce limiti sul tempo di arresto atteso per i test a campione fisso e a confidenza fissa, mostrando l'ottimalità in termini di complessità campionaria.

Risultati Sperimentali
Gli autori validano il loro metodo attraverso simulazioni e dati reali:

• Dati Sintetici: Confronti con metodi allo stato dell'arte (Universal Inference, GLRT, e-value di Turner-Grunwald e GRO) su scenari di voto Condorcet, Borda e Schulze con 3 candidati.
  • Il POE e la sua variante parallela (PPOE) dimostrano una potenza e una complessità campionaria competitive.
  • Si dimostra che il POE è essenziale per il voto Schulze (non convesso $H_0$), dove i metodi limitati alla convessità non possono essere applicati direttamente.
  • Il metodo beneficia dei "dati a priori" (pre-addestramento del prior $\pi$), convergendo verso le prestazioni di un test GRO oracle all'aumentare delle informazioni a priori.
• Applicazione su Dati Reali: Il metodo viene applicato a dati di preferenza a coppie delle elezioni presidenziali francesi del 2022.
  • L'obiettivo era determinare il vincitore Borda tramite test sequenziali.
  • Utilizzando lo stimatore Turner-Grunwald (sufficiente per il caso convesso di Borda), il test ha eliminato sequenzialmente i candidati.
  • L'esperimento ha concluso che Yannick Jadot sarebbe stato il vincitore Borda. Il test ha richiesto significativamente meno campioni (171 elettori, 4.721 confronti a coppie) rispetto ai sondaggi politici tradizionali (ad esempio, IPSOS ne ha utilizzati 7.321) per raggiungere una conclusione definitiva.

Significato e Rivendicazioni
Il documento sostiene di fornire un framework generale per il testing sequenziale nelle preferenze di voto che non è limitato dalla convessità degli insiemi di ipotesi.

• È il primo approccio statistico per affrontare il sistema di voto Schulze, che è notoriamente difficile a causa del suo spazio di parametri non convesso.
• L'algoritmo di Frank-Wolfe proposto offre un modo pratico per calcolare le Proiezioni di Informazione Inversa per distribuzioni a supporto finito, potenzialmente estendibile oltre il voto ad altri contesti con vincoli non convessi.
• Gli autori osservano che, sebbene il POE e lo stimatore TG più semplice si comportino in modo simile in contesti convessi (come Borda), il POE è necessario per contesti non convessi. Riconoscono che il costo computazionale del POE (dovuto agli aggiornamenti di Frank-Wolfe) è superiore a quello di TG, ma il compromesso è necessario per problemi non convessi.
• Il lavoro evidenzia la fattibilità del testing sequenziale in scenari reali ad alta dimensione, dimostrando che conclusioni statisticamente significative possono essere raggiunte con meno campioni rispetto ai metodi di rilevamento tradizionali.

Gli autori rimangono modesti riguardo alle direzioni future, notando questioni aperte sulla velocità di convergenza della loro implementazione di Frank-Wolfe, la necessità dello slack $\epsilon$ per la regolarità e il potenziale per metodi più efficienti per gestire il numero esplosivo di componenti convesse nello schema di voto Schulze ad alta dimensione.