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

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

Problem Statement
The paper addresses the challenge of conducting sequential hypothesis tests on preference data, specifically within the context of political polling and voting systems. The goal is to determine the winner of an election (under Condorcet, Borda, or Schulze rules) by collecting pairwise comparison data sequentially and stopping as soon as statistically significant results are obtained.

The core statistical difficulty arises from the nature of the hypothesis sets. While the parameter space for pairwise preferences (multivariate Bernoulli data) is well-defined, the sets of parameters corresponding to specific voting winners ($H_0$ and $H_1$) can be complex.

• Condorcet and Borda winners correspond to convex or simple parameter sets.
• Schulze winners correspond to non-convex parameter sets composed of a union of many convex components (defined by strict orderings of preferences).
  Existing methods for constructing optimal sequential tests, such as Growth Rate Optimal (GRO) e-values, often rely on the convexity of the null hypothesis set ($H_0$) to compute Reverse Information Projections (RIPr). The paper aims to develop a theory and algorithm capable of handling general composite hypotheses, including non-convex sets like those found in the Schulze voting method.

Methodology
The authors propose a framework based on Posterior Optimal E-values (POE).

1. Theoretical Framework (POE):

   • Building on the GRO criterion, which maximizes the expected log-growth of an e-value under a specific alternative, the authors extend this to composite alternatives using a Bayesian perspective.
   • They define a utility function for an e-value $E$ based on a prior $\pi$ over the alternative parameter set $\Phi_1$. The goal is to find a test supermartingale that maximizes the integrated utility $G_t(E, \pi, \tau)$ for any stopping time $\tau$.
   • Theorem 2 establishes that the optimal e-value (POE) is the product of one-step optimal e-values. Each step involves computing a likelihood ratio where the numerator is the posterior predictive distribution and the denominator is the projection of this posterior onto the null set $H_0$.
   • Unlike previous approaches (e.g., Turner and Grunwald, 2022) that rely on specific simplifications for convex sets or fixed dimensions, the POE formulation is general and applies to any $H_0$ and $H_1$ defined by parameter sets, provided the KL divergence is finite.

2. Algorithmic Implementation (Frank-Wolfe for RIPr):

   • Computing the POE requires solving a Reverse Information Projection (RIPr) problem at each time step: finding a distribution in $H_0$ that minimizes the KL divergence from the current posterior predictive distribution.
   • Standard algorithms (like Li's algorithm) are computationally expensive for high-dimensional multivariate Bernoulli data.
   • The authors adapt the Frank-Wolfe algorithm to this problem. By leveraging the finite support of the distributions (the space of $2^D$ possible outcomes), they recast the optimization in $\mathbb{R}^{2^D}$.
   • Lemma 5 proves that the extremal points of the set of distributions over a parameter set $\Phi'$ are Dirac distributions ($P_{\delta_\phi}$). This allows the Frank-Wolfe algorithm to search for the optimal projection by iterating over the extremal points (Dirac measures) of the parameter set.
   • This approach enables the computation of RIPr even when $H_0$ is a non-convex union of convex sets (as in the Schulze method), a scenario where previous GRO-based methods failed.

3. Testing Procedures:

   • Capped Sample Size Test: A fixed-budget test that stops if the e-value exceeds $1/\alpha$ or reaches a pre-computed maximum sample size $T$.
   • Fixed Confidence Test (PPOE): A parallel test using two sequences of e-values (one for $H_0$ vs $H_1$, one for $H_1$ vs $H_0$). It stops when either sequence exceeds its threshold, providing guarantees on false positive rates and power without a hard cap on sample size.

Key Contributions

• Posterior Optimal E-values (POE): A new criterion for e-value optimality that generalizes GRO to composite hypotheses using a Bayesian prior. It is shown to be the product of one-step optimal e-values conditioned on the posterior.
• Handling Non-Convex Sets: The paper provides the first statistical treatment of the Schulze voting system, which involves non-convex parameter sets.
• Efficient RIPr Algorithm: The authors introduce a Frank-Wolfe-based algorithm to compute Reverse Information Projections for multivariate Bernoulli data. This method is efficient enough to handle the non-convex unions of convex sets required for Schulze voting, overcoming the limitations of prior methods restricted to convex $H_0$.
• Theoretical Guarantees: The paper derives concentration inequalities for POE and provides bounds on the expected stopping time for both fixed-sample and fixed-confidence tests, showing optimality in terms of sample complexity.

Experimental Results
The authors validate their method through simulations and real-world data:

• Synthetic Data: Comparisons against state-of-the-art methods (Universal Inference, GLRT, Turner-Grunwald e-values, and GRO) on Condorcet, Borda, and Schulze voting scenarios with 3 candidates.
  • POE and its parallel variant (PPOE) demonstrate competitive power and sample complexity.
  • POE is shown to be essential for Schulze voting (non-convex $H_0$), where convex-restricted methods cannot be applied directly.
  • The method benefits from "prior data" (pre-training the prior $\pi$), converging toward the performance of an oracle GRO test as prior information increases.
• Real Data Application: The method is applied to pairwise preference data from the 2022 French Presidential Election.
  • The goal was to determine the Borda winner using sequential testing.
  • Using the Turner-Grunwald (TG) estimator (sufficient for the convex Borda case), the test sequentially eliminated candidates.
  • The experiment concluded that Yannick Jadot would have been the Borda winner. The test required significantly fewer samples (171 voters, 4,721 pairwise comparisons) than traditional political surveys (e.g., IPSOS used 7,321 voters) to reach a definitive conclusion.

Significance and Claims
The paper claims to provide a general framework for sequential testing in preference voting that is not limited by the convexity of the hypothesis sets.

• It is the first statistical approach to tackle the Schulze voting system, which is notoriously difficult due to its non-convex parameter space.
• The proposed Frank-Wolfe algorithm offers a practical way to compute Reverse Information Projections for finite-support distributions, potentially extending beyond voting to other settings with non-convex constraints.
• The authors note that while POE and the simpler TG estimator perform similarly in convex settings (like Borda), POE is necessary for non-convex settings. They acknowledge that the computational cost of POE (due to Frank-Wolfe updates) is higher than TG, but the trade-off is necessary for non-convex problems.
• The work highlights the feasibility of sequential testing in high-dimensional real-world scenarios, demonstrating that statistically significant conclusions can be reached with fewer samples than traditional polling methods.

The authors remain modest regarding future directions, noting open questions about the convergence rates of their Frank-Wolfe implementation, the necessity of the $\epsilon$-slack for smoothness, and the potential for more efficient methods to handle the exploding number of convex components in high-dimensional Schulze voting.