Abstract
Given $K$ uncertainty sets that are arbitrarily dependent -- for example, confidence intervals for an unknown parameter obtained with $K$ different estimators, or prediction sets obtained via conformal prediction based on $K$ different algorithms on shared data -- we address the question of how to efficiently combine them in a black-box manner to produce a single uncertainty set. We present a simple and broadly applicable majority vote procedure that produces a merged set with nearly the same error guarantee as the input sets. We then extend this core idea in a few ways: we show that weighted averaging can be a powerful way to incorporate prior information, and a simple randomization trick produces strictly smaller merged sets without altering the coverage guarantee. Further improvements can be obtained if the sets are exchangeable. We also show that many modern methods, like split conformal prediction, median of means, HulC and cross-fitted "double machine learning", can be effectively derandomized using these ideas.
Introduction
In modern statistical inference and machine learning, researchers often generate multiple uncertainty sets for a single target parameter or prediction. For instance, one might apply several different algorithms to the same dataset to obtain a collection of prediction intervals. Because these intervals are derived from the same underlying data, they exhibit complex, unknown dependencies.
The fundamental challenge lies in aggregating these dependent sets into a single, reliable uncertainty set. While a simple union of all sets is often excessively conservative (resulting in intervals that are too wide), a simple intersection typically fails to provide any rigorous statistical coverage guarantee. This paper introduces a "black-box" framework to bridge this gap, requiring no access to the internal mechanics of the estimators or the raw data.
The Majority Vote Procedure
The primary contribution is the Majority Vote Procedure. A point $s$ is included in the merged set $C^M$ if it is contained in more than half of the $K$ input sets. Formally, if each input set $C_k$ has a coverage guarantee of at least $1-\alpha$, the authors prove that the majority vote set $C^M$ maintains a coverage of at least $1-2\alpha$, regardless of the dependency structure between the input sets.
This $1-2\alpha$ "price" for arbitrary dependence is a key theoretical result, showing that one can handle any dependency by essentially doubling the error rate. For intervals of equal width, this procedure simplifies to an intuitive "median of midpoints" rule.
Advanced Aggregation Methods
Beyond the basic majority vote, the paper explores several refinements:
- Weighted Majority Vote: Weights can be assigned to prioritize more reliable models while preserving the $1-2\alpha$ guarantee.
- Randomized Thresholding ($C^R$): By introducing independent noise into the voting threshold, the procedure can produce strictly smaller merged sets without sacrificing coverage.
- Exchangeable Aggregation ($C^E$): When sets are exchangeable (e.g., from different random splits of the same data), a "running intersection" method can produce significantly tighter, more stable sets.
- Derandomization: The framework can be used to stabilize randomized algorithms like Median-of-Means (MoM) and HulC. By running these algorithms multiple times and applying a majority vote, researchers can obtain reproducible results that do not depend on the "luck of the draw" of a single data split.
Empirical Results
The effectiveness of these methods was validated through simulations and real-world datasets:
- Parkinson’s Disease Dataset: In predicting UPDRS scores, the randomized majority vote ($C^R$) and exchangeable version ($C^\pi$) yielded narrower intervals than the standard majority vote while maintaining target coverage.
- Diabetes Treatment Study: The methods were applied to estimate Average Treatment Effects (ATE), demonstrating robustness in causal inference tasks.
- Stability: In MoM simulations, the derandomized "MoMoM" estimator stabilized with as few as 25 to 50 replications, offering a more reliable alternative to single-run estimates.
Discussion and Limitations
While the majority vote provides a robust worst-case bound, it can be conservative in practice, often achieving coverage significantly higher than $1-2\alpha$. Additionally, in cases where input sets are disjoint, the merged set could theoretically be empty, though this was rarely observed in empirical tests. Despite the computational cost of generating $K$ initial sets, the merging process itself is instantaneous, making it a practical tool for high-stakes uncertainty quantification.
Summary updated