Related papers: On Large-Scale Multiple Testing Over Networks: A Non-Asymptotic Approach

On Large-Scale Multiple Testing Over Networks: A Non-Asymptotic Approach

URL: http://arxiv.org/abs/2609.14170v1
Date: Sat, 12 Sep 2026 22:05:15 GMT
Title: On Large-Scale Multiple Testing Over Networks: A Non-Asymptotic Approach
Abstract summary: $N$ sites are asked to control a global false discovery rate (FDR) under a tight budget.<n>We show that BONuS-GA dominates at moderate-to-large per-node samples and CFGA with adaptive bandwidth at small ones.<n>All variants keep the $O(sqrtmlog m)$ communication budget, up to e-CFGA's $O( GreebarRlog m)$ reporting round.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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.

Related papers

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
arXiv Detail & Related papers (2026-08-06T19:49:48Z)
Random Parameter Noise Does Not Make Exact ReLU Verification Easy [14.270378035741404]
We study exact verification of ReLU networks in an adversarial smoothed model.<n>We show that, under the standard assumption $mathrmNPnotsubseteqmathrmBPP$, there is no sound and complete verifier whose expected running time is embedding in network size, bit complexity, and inverse noise level for every base instance.
arXiv Detail & Related papers (2026-07-15T21:26:20Z)
SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
arXiv Detail & Related papers (2026-06-14T14:11:07Z)
Matching Rates and Optimal Allocation for Federated Probe-Logit Distillation under Heterogeneous Bandwidth Budgets [12.805268849262243]
In language modeling, $K$ nodes each hold $n$ samples but cannot pool data or exchange full-precision gradients or weights.<n>We study the minimax rate at which a conditional distribution over $V$ tokens can be estimated when each node may upload at most $B$ bits per query in a public probe set.
arXiv Detail & Related papers (2026-05-28T09:08:39Z)
Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning [0.0]
We introduce Graph-SND, which replaces a complete-graph average with a weighted average over the edges of an arbitrary graph $G$.<n>For fixed sparse graphs we prove forwarding-index distortion bounds for expanders and a spectral refinement under low-rank distance structure.<n>For random $d$-regular graphs we prove an unconditional probabilistic $widetildemathcalO(D_max/sqrtn)$ bound.<n>On VMAS we verify recovery, unbiasedness, concentration, and wall-clock scaling.
arXiv Detail & Related papers (2026-05-06T15:18:42Z)
Robust Learning of a Group DRO Neuron [21.632698901872843]
We study the problem of learning a primal neuron under standard squared loss in the presence of arbitrary label noise and group-level distributional shifts.<n>Our framework provides robust learning guarantees in the face of arbitrary label corruptions and group-specific distributional shifts.
arXiv Detail & Related papers (2026-01-26T04:00:53Z)
Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
arXiv Detail & Related papers (2025-06-30T13:27:39Z)
Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
We study a federated linear bandits model, where $M$ clients communicate with a central server to solve a linear contextual bandits problem. To address the unique challenges of adversarial finite action sets, we propose the FedSupLinUCB algorithm. We prove that FedSupLinUCB achieves a total regret of $tildeO(sqrtd T)$, where $T$ is the total number of arm pulls from all clients, and $d$ is the ambient dimension of the linear model.
arXiv Detail & Related papers (2023-11-02T03:41:58Z)
Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
arXiv Detail & Related papers (2023-03-30T02:51:00Z)
Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
arXiv Detail & Related papers (2023-02-18T09:24:15Z)
Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
arXiv Detail & Related papers (2022-12-01T15:57:58Z)
A Law of Robustness beyond Isoperimetry [84.33752026418045]
We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
arXiv Detail & Related papers (2022-02-23T16:10:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.