Distributed testing method keeps error rate low with little data sharing
On Large-Scale Multiple Testing Over Networks: A Non-Asymptotic Approach
Information Theory
Summary
When many different sites test lots of hypotheses, they need to keep mistakes (false discoveries) under control while sharing very little data. The authors studied a previous approach that worked well when data was very large but sometimes made too many errors with smaller data. They found the source of this problem and proposed new methods that reliably keep error rates low even in smaller data samples. Their methods also use little communication between sites, making them practical for large networks.
What this means in practice
- •For biomedical data teams: Improve error control when combining testing results from many hospitals with limited shared information.
- •For network anomaly detectors: Maintain accurate detection of network threats across many sensors while minimizing data exchange.
Authors
Mehrdad Pournaderi
Abstract
Distributed multiple testing asks $N$ sites to control a global false discovery rate (FDR) under a tight communication budget. The greedy interval-aggregation algorithm of Pournaderi and Xiang (2024) solves this asymptotically but can violate $\mathrm{FDR}\leα$ at finite samples. We trace the violation to a winner's-curse bias in the selected density statistics, of exact order $Θ(m^{-1/4}\sqrt{\log m})$ at the standard bandwidth $\varepsilon\asymp m^{-1/2}$, with $m$ the total number of p-values in the network. Cross-Fit Greedy Aggregation (CFGA) eliminates the curse by selecting the nested rejection family on one half of each node's data and scoring it on the other, achieving finite-sample $\mathrm{FDR}\leα$ when per-node null rates are known; an inflated variant covers the plug-in setting at a vanishing $η=1/m$ slack. BONuS-GA instead masks a bag of synthetic uniform nulls calibrated by counting knockoffs, so every p-value serves both selection and inference; a per-node budgeted variant removes all oracle input, controlling $\mathrm{FDR}\leα$ for any data-independent bag. Aggregating the CFGA folds by e-values over random splits (e-CFGA) removes the Bonferroni factor and averages the split randomness. All variants keep the $O(\sqrt{m}\log m)$ communication budget, up to e-CFGA's $O(\bar{R}\log m)$ reporting round; empirically, BONuS-GA dominates at moderate-to-large per-node samples and CFGA with adaptive bandwidth at small ones.