📊 statistics

Controlling False Discovery in Arbitrarily Structured Hypothesis Spaces via Reproducing Kernels

This paper introduces a novel framework for controlling the False Discovery Rate in arbitrarily structured hypothesis spaces by reframing the problem as a regularized learning task within a Reproducing Kernel Hilbert Space, thereby unifying diverse structures like graphs and hierarchies to enable smooth, sample-efficient inference with provable FDR guarantees.

Original authors: Binyamin Perets, Shie Mannor

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Binyamin Perets, Shie Mannor

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to find a few specific clues (the "true discoveries") hidden among thousands of pieces of evidence. In modern science, researchers often run thousands of tests at once. The problem is that by pure chance, some of these tests will look like clues when they are actually just "false alarms" (noise).

Traditionally, scientists have used a very strict, conservative rulebook to filter out these false alarms. They treat every test as if it were an isolated island, ignoring the fact that clues often come in clusters. For example, if one brain region lights up, its neighbors likely do too. If one gene is active, its family members probably are, too. The old rulebook ignores these connections, which means it often throws away good clues just to be safe.

This paper introduces a new, smarter way to solve this problem. Here is the breakdown using simple analogies:

1. The Problem: The "Staircase" vs. The "Smooth Hill"

Imagine you are trying to map the temperature of a room.

Old Methods: Imagine you have to draw the temperature map using only square tiles (like a pixelated video game). If the temperature changes smoothly, your map looks like a jagged staircase. This is what previous methods did: they forced the data into rigid, blocky chunks. They also required you to draw the map before you knew where the walls were.
This Paper's Method: This method draws a smooth, continuous hill. It understands that temperature (or scientific signals) usually changes gradually, not in sudden jumps. It uses a mathematical tool called a Reproducing Kernel (think of it as a "smart rubber sheet") that can stretch and bend to fit the shape of the data, whether that data is a grid of pixels, a network of friends, or a family tree.

2. The Core Idea: Learning from Neighbors

The authors realized that if you know a hypothesis (a test) is likely to be true, its neighbors are likely to be true too.

The Analogy: Imagine you are guessing the weather in a city. If you see rain in one neighborhood, you can guess it's raining in the next one without needing a separate weather report for every single street corner.
The Innovation: The paper creates a system that "learns" these patterns. It doesn't just look at one test in isolation; it looks at the whole neighborhood. If a group of tests are clustered together and look suspicious, the system gives them a boost. If they are isolated, it treats them more cautiously.

3. The "Rubber Sheet" (The Kernel)

The paper uses a concept called a Reproducing Kernel Hilbert Space (RKHS).

The Metaphor: Think of the RKHS as a magical, stretchy rubber sheet. You can place your data points on this sheet. The "Kernel" is the rule that tells the sheet how to stretch.
- If your data is a map (like brain scans), the sheet stretches like a normal map.
- If your data is a social network (like protein interactions), the sheet stretches along the connections between people.
- If your data is a family tree, the sheet stretches up and down the branches.
Why it matters: Instead of needing a different computer program for maps, networks, and trees, this one "rubber sheet" can handle all of them just by changing the stretching rule (the kernel).

4. The Two-Step Decision Process

The authors propose a two-step process to make the final decision on what is a "real" discovery:

Step 1: The Smooth Estimate. First, the system uses the rubber sheet to draw a smooth map of "how likely is this a false alarm?" for every single point, even the ones you haven't tested yet. It fills in the gaps between your data points.
Step 2: The Decision Rules. Once the map is drawn, the system uses two different "rules" to decide which clues to keep.
- Rule 1 (The Filter): It filters out the obvious noise first, then applies a standard check to the remaining candidates.
- Rule 2 (The Mirror Trick): This is a clever trick where the system creates a "mirror image" of the data to double-check its work. It ensures that even if the map isn't perfect, the final list of discoveries is still statistically safe.

5. Why This is Better

No More "Staircases": Because it produces smooth maps, it doesn't miss signals that fall between the cracks of rigid blocks.
Filling in the Blanks: Because it understands the "shape" of the data, it can make educated guesses about places where you didn't even run a test. This helps scientists design better experiments by telling them exactly where to look next.
Speed and Safety: The authors proved mathematically that their method controls the rate of false alarms (False Discovery Rate) just as well as the old strict methods, but it finds more real discoveries (higher power).

6. Real-World Tests

The authors tested this on two real scenarios:

Particle Physics (HIGGS): Looking for specific particle collisions among millions of events.
Genetics (TCGA): Looking for genes that behave differently in cancer patients, using a map of how proteins interact with each other.

In both cases, their method found more true signals while keeping the number of false alarms low, outperforming the current standard methods.

Summary

In short, this paper replaces the old, rigid, "one-size-fits-all" way of checking scientific tests with a flexible, smooth, and connected approach. It treats scientific data like a landscape rather than a pile of isolated rocks, allowing scientists to find more true discoveries without getting tricked by false alarms.

Technical Summary: Controlling False Discovery in Arbitrarily Structured Hypothesis Spaces via Reproducing Kernels

Problem Statement

Large-scale hypothesis testing is fundamental to modern science, where controlling the False Discovery Rate (FDR) is the standard for managing false positives. A critical challenge arises because hypotheses rarely exist in isolation; they often exhibit structure through spatial proximity, connectivity (e.g., graphs), or hierarchy. While classical methods (e.g., Benjamini-Hochberg) treat these dependencies as obstacles requiring conservative correction, recent work suggests leveraging known structure can significantly increase discovery power.

However, existing approaches to structured FDR control face significant limitations:

Explicit Dependency Modeling: Methods requiring formal probabilistic dependencies (e.g., joint distributions) are often computationally intractable or statistically infeasible unless dependencies are sparse and explicitly defined.
Adaptive P-value Methods: Approaches like LAWS or STRAW use heuristic spatial weighting but lack explicit models of structure, principled hyperparameter selection, or mechanisms to enforce prior beliefs.
Regularization-Based Approaches: The leading example, SmoothFDR, uses Total Variation (TV) regularization on graphs to enforce piecewise-constant significance patterns. While it relaxes probabilistic requirements, it is constrained to discrete topologies, produces piecewise-constant solutions ill-suited for smooth phenomena, and lacks principled mechanisms for hyperparameter selection or interpolation to unobserved locations.

The paper addresses the general problem of FDR control over arbitrarily structured hypothesis spaces, aiming to unify continuous domains, graphs, and hierarchies under a single framework that supports smooth solutions and principled inference.

Methodology

The authors reframe structured FDR control as a regularized learning problem within a Reproducing Kernel Hilbert Space (RKHS).

1. Spatially Varying Mixture Model

The framework assumes a continuous hypothesis index space $H \subset \mathbb{R}^d$ . For each location $loc \in H$ , the p-value process is modeled via a two-group mixture:
$f(p | loc) = \alpha(loc)f_0(p) + (1 - \alpha(loc))f_1(p)$
Here, $\alpha(loc)$ represents the spatially varying prior probability of the null hypothesis. Crucially, the component densities $f_0$ and $f_1$ are assumed spatially invariant, while the mixing proportion $\alpha(loc)$ captures the structural dependencies. This separation allows $f_0$ and $f_1$ to be estimated using standard non-spatial methods (e.g., empirical null fitting) on the pooled data.

2. RKHS Optimization Framework

The core contribution is estimating $\alpha(loc)$ by minimizing a Tikhonov-regularized negative log-likelihood within an RKHS $\mathcal{H}_K$ :
$\min_{\alpha \in \mathcal{H}_K} \left( -\sum_{i=1}^N \log(\alpha(loc_i)f_0(p_i) + (1-\alpha(loc_i))f_1(p_i)) + \lambda_{reg}\|\alpha - \bar{\alpha}\|^2_{\mathcal{H}_K} \right)$
Key technical innovations include:

Kernel Choice: The structure (spatial, graph, hierarchical) is encoded solely through the choice of the reproducing kernel $K$ . For continuous domains, Matérn kernels are used; for discrete graphs, diffusion kernels replace TV penalties with $L_2$ smoothness; for hierarchies, hyperbolic embeddings are utilized.
Soft Boundary Constraints: Instead of hard box constraints ( $\alpha \in [0,1]$ ), a soft penalty is applied to violations, maintaining convexity and differentiability.
Natural Gradient Descent: Standard optimizers struggle with the ill-conditioned Gram matrix $K$ . The authors derive a natural gradient update where the kernel matrix $K$ cancels out in the gradient step, leading to a simple update rule dependent only on residuals and current parameters. This ensures $O(N^2)$ scaling per iteration.

3. Decision Rules with FDR Guarantees

Two decision rules are proposed to translate the estimated $\hat{\alpha}(loc)$ into rejections:

Model-Free FDR Control (Rule 1): Uses the marginal two-group mixture guarantee. It filters hypotheses through a spatial gate ( $\hat{\alpha}(loc) \leq q$ ) and applies a standard step-up procedure on the marginal local FDR (lfdr) within that set.
Spatial FDR Control via Mirror Statistics (Rule 2): Adapts the Barber-Candès mirror statistic framework. It constructs mirror scores by flipping p-values ( $p \to 1-p$ ) and uses the stability of the RKHS estimator (ensuring $\hat{\alpha}$ changes minimally when a single p-value is flipped) to prove FDR control at level $\alpha + O(1/N)$ .

4. Inference Over the Entire Domain

To extend inference to unobserved locations, the paper proposes a two-stage approach:

Stage 1: Point-wise estimation of $\hat{\alpha}$ at observed locations.
Stage 2: Learning a globally valid function $\alpha(loc) \in [0,1]$ that approximates the point-wise estimates. This is formulated as minimizing the Kullback-Leibler (KL) divergence between the target and the model, solved via kernel logistic regression with a squashing function (logistic) to enforce bounds. This allows for smooth interpolation and uncertainty quantification (via Laplace approximation) at untested locations.

5. Hyperparameter Selection

A key advantage is the ability to perform principled likelihood-based cross-validation for all hyperparameters (regularization strength, kernel type, length-scale). The authors prove that the conditional density is properly normalized for all hyperparameter choices, ensuring valid likelihood comparisons.

Key Contributions

Unified Framework: A single algorithm that handles continuous domains, graphs, and hierarchies through kernel choice alone, moving beyond the piecewise-constant constraints of previous methods.
Smooth Solutions: The use of RKHS enables flexible smoothness regularization, generating continuous significance maps valid at both observed and unobserved locations.
Theoretical Guarantees: Two decision rules are provided with formal FDR control guarantees, even under arbitrary misspecification of the structure. The paper proves that under correct structure specification, the spatial rule strictly dominates the marginal rule in power.
Computational Efficiency: The natural gradient formulation avoids inverting the Gram matrix during updates, scaling as $O(N^2)$ . The framework supports up to 500,000 hypotheses on a single GPU using tiled matrix-vector products.
Experimental Design: The ability to infer $\alpha$ at unseen locations enables data-efficient experimental design (e.g., A-optimal design) to strategically select which hypotheses to test.

Results

The method was validated on semi-synthetic benchmarks and two real-world tasks:

Semi-Synthetic Benchmarks: Using 10 high-dimensional real-world datasets with injected p-values, the proposed method (specifically Rule 2) achieved strictly higher power than all baselines (including AdaPT variants, SmoothFDR, and BH) across all datasets while maintaining a significantly lower False Discovery Rate (mean FDR ~0.023 vs. ~0.08 for AdaPT).
HIGGS Particle Physics: On a dataset of 98K collision events, BH and SmoothFDR failed to control FDR (FDR > 0.25), while the proposed rules controlled FDR at the 0.10 level and recovered meaningful power, whereas the non-spatial Two-group method made no rejections.
TCGA Gene Expression: On differential expression analysis using a protein-protein interaction network (STRING), the proposed rules achieved a power gain of 0.13–0.16 over the strongest FDR-controlling competitor (AdaPT) while maintaining tighter FDR control.
Generalization: The method successfully predicted $\alpha$ at held-out locations with 94.8% coverage of the 95% confidence intervals, demonstrating reliable spatial interpolation.

Significance and Claims

The paper claims to introduce the first method capable of producing continuous prior maps valid across entire domains with convex optimization guarantees, flexible smoothness regularization, and principled hyperparameter selection. It positions the work as a conceptual paradigm shift: rather than treating dependencies as obstacles, the framework exploits known structure as prior information to enhance discovery.

The authors note that while the theoretical guarantees apply to observed locations, the extension to unobserved points relies on standard out-of-sample inference caveats. They also acknowledge that the framework relies on kernel operations which can become a bottleneck for very large sets, though they demonstrate scalability to 500,000 hypotheses. Despite these limitations, the substantial power gains and theoretical robustness presented make the framework a valuable addition to the spatial FDR toolkit when structural assumptions are appropriate.