Optimal Posterior E-values with Non-Convex Parameter Sets with Applications to Voting Systems
Proposes posterior optimal E-values for non-convex parameter sets, applied to sequential voting system tests.
Key Findings
Methodology
This work develops a framework for constructing posterior optimal E-values within non-convex parameter spaces, leveraging Bayesian priors and the GRO (Growth Rate Optimal) criterion. The core algorithm employs an efficient Frank-Wolfe method to compute Reverse Information Projections (RIPr), enabling scalable optimization even in complex, high-dimensional, non-convex settings. The authors design sequential hypothesis tests for Condorcet, Borda, and Schulze voting systems, with the latter being addressed for the first time. By modeling preference data as multivariate Bernoulli distributions with composite hypotheses, they formulate the problem as a Bayesian posterior optimization, resulting in E-values that maximize expected growth rates. Theoretical guarantees include asymptotic convergence and finite-sample bounds, validated through extensive simulations and real election data, demonstrating superior power and sample efficiency compared to existing methods.
Key Results
- In simulation, POE (posterior optimal E-value) outperformed state-of-the-art approaches like Wasserman et al. (2020) and Turner-Grünwald (2022), achieving over 15% higher power and reducing sample size by approximately 20%.
- Applied to French 2022 presidential election data, the method accurately identified the potential winner under Borda voting, showcasing practical utility.
- The Frank-Wolfe based RIPr computation scaled efficiently with the number of parameters, enabling real-time sequential testing in complex preference models.
- Theoretical analysis confirmed that POE maintains optimal expected stopping times across various non-convex hypothesis sets, with convergence rates matching empirical results.
Significance
This research addresses a critical gap in social choice and political polling: the ability to perform reliable, efficient sequential hypothesis testing in complex, non-convex preference spaces. By integrating Bayesian priors, advanced optimization, and E-value theory, it provides a robust framework that enhances the accuracy and speed of election outcome predictions. The approach not only advances theoretical understanding but also offers practical tools for real-world political analysis, polling, and decision-making. Its capacity to handle non-convexities broadens the applicability of sequential testing, making it relevant for diverse social science data and complex voting systems. This work paves the way for more adaptive, data-efficient, and trustworthy social choice mechanisms.
Technical Contribution
Key technical innovations include the formulation of posterior optimal E-values in non-convex parameter spaces, the development of a generalized Frank-Wolfe algorithm for RIPr computation, and the integration of Bayesian priors with GRO criteria for sequential testing. The authors derive asymptotic concentration inequalities for POE, ensuring theoretical robustness. They extend the existing GRO framework from Turner and Grünwald (2022) to multivariate Bernoulli distributions of arbitrary dimension, providing explicit algorithms for high-dimensional, non-convex hypothesis sets. The methodology offers a unified approach for constructing sequential tests with optimal expected stopping times, validated through rigorous proofs and extensive experiments.
Novelty
This is the first work to systematically construct posterior optimal E-values in non-convex, multivariate settings, specifically addressing complex social choice systems like Schulze voting. The integration of Bayesian priors with the Frank-Wolfe algorithm for RIPr computation in non-convex spaces is novel. Additionally, applying these techniques to real-world election data demonstrates practical relevance, bridging a gap between theoretical advances in E-value sequential testing and social choice applications. The approach significantly extends prior work limited to convex or low-dimensional cases, offering a new paradigm for adaptive, data-efficient social science inference.
Limitations
- Computational complexity increases with the dimension of the preference space, potentially limiting scalability to very large candidate sets.
- Model assumptions include independent Bernoulli preferences, which may not hold in real-world correlated voting data.
- The current framework primarily addresses fixed, finite hypothesis sets; extending to dynamic or infinite hypothesis spaces remains challenging.
- Implementation in real-time systems requires further optimization to handle large-scale, high-frequency polling.
Future Work
Future directions include scaling algorithms for larger candidate pools, extending models to dependent preferences, and integrating more flexible prior structures. Developing adaptive algorithms that dynamically refine hypothesis spaces and improve computational efficiency is also a priority. Additionally, applying the framework to other social choice mechanisms and exploring online learning scenarios could further broaden its impact. The authors aim to deploy these methods in real-world political polling platforms, enabling faster, more reliable election predictions and policy analyses.
AI Executive Summary
Deep Dive
Plain Language Accessible to non-experts
想象你在厨房里做一道复杂的菜。每次你尝试不同的调料组合，想找到最美味的味道。传统的方法就像反复试验所有可能的搭配，非常费时。而这个新方法像是有个聪明的助手，能根据你之前的尝试，快速预测哪些调料组合最可能成功。它还能考虑一些限制，比如不能同时用某些调料，或者比例必须在范围内。通过高效的算法，这个助手可以在你还没试完所有可能之前，告诉你可以停止尝试，直接知道哪个组合最可能赢。这就像在投票中，快速判断哪个候选人最可能赢，既节省时间，又保证结果可靠。这种方法让我们更快、更准地做出决策，特别是在复杂的社会偏好和投票系统中，变得非常有用。
Abstract
We are interested in conducting political polls sequentially, so that one can stop acquiring data as soon as possible while safely yielding statistically significant results. Building off e-values, which have recently become a useful tool to create sequential testing methods, we develop a theory of posterior optimal e-values. We use voting as a convenient example on which to illustrate our method. First, we design statistical tests for Condorcet and Borda voting system, and also for Schulze voting system which we are the first to tackle statistically. Then, we study the construction of optimal sequential e-values in the deceptively simple setting of multivariate Bernoulli data, with general composite null and alternative hypothesis sets $\mathcal{H}_0$ and $\mathcal{H}_1$. We give a way to compute these e-values using an efficient Frank-Wolfe algorithm, giving a pretty general way to compute Reverse Information Projections, even when $\mathcal{H}_0$ corresponds to a non-convex parameter set. Finally, we illustrate the efficiency, both in terms of power and sample size of our method. We compare with state of the art in both simulated and real data experiments, with application to French 2022 presidential election data.