Everywhere Valid Bounds on False Discovery Proportions in Conformal Inference

Technical Summary: Everywhere Valid Bounds on False Discovery Proportions in Conformal Inference

Problem Statement
Modern applications of conformal inference, such as outlier detection and candidate selection in drug discovery, often involve selecting test samples based on whether their conformal $p$-values fall below a specific threshold. The reliability of these selections is quantified by the False Discovery Proportion (FDP), defined as the fraction of incorrect selections among all selected units.

Existing methods, such as the Benjamini–Hochberg (BH) procedure, primarily control the False Discovery Rate (FDR), which is the expected value of the FDP over repeated data realizations. This paper identifies two critical limitations in the current state of the art:

1. Lack of Realized Guarantees: Controlling the expected FDP does not guarantee that the FDP on a specific dataset is small. The realized FDP can substantially exceed the expected value, offering no instance-wise protection for practitioners.
2. Inflexibility to Post Hoc Selection: Existing guarantees require the significance level $\alpha$ to be fixed in advance. If a practitioner inspects the data and adjusts the threshold (e.g., to increase the number of discoveries), the FDR control is invalidated.

The authors aim to establish finite-sample, distribution-free upper bounds on the FDP that hold simultaneously over all possible rejection thresholds $t \in [0, 1]$. This enables arbitrary post hoc selection of the threshold while maintaining rigorous statistical guarantees.

Methodology
The core of the proposed framework relies on the tractable joint distribution of "null" conformal $p$-values induced by the exchangeability assumption.

1. Conformal Uniform Variables: The authors define conformal uniform variables $u_j$ as normalized ranks of test scores relative to a calibration set. Under exchangeability, the vector of these variables admits a known joint distribution $P_{n,m}$ that is independent of the underlying data-generating mechanism.
2. Envelope Construction via Sampling: Instead of relying on concentration inequalities (like Dvoretzky–Kiefer–Wolfowitz) which yield conservative, linear bounds, the authors propose sampling from the joint distribution $P_{n,m}$ to construct a high-probability envelope for the empirical cumulative distribution function (CDF) of the null $p$-values.
   • They define a summary statistic $T(F)$ (e.g., Kolmogorov–Smirnov, Higher-Criticism, or Berk-Jones statistics) applied to the empirical CDF.
   • By generating $B$ Monte Carlo samples from $P_{n,m}$, they compute the $(1-\delta)$-quantile of the statistic to determine a cutoff $\hat{T}$.
   • This cutoff is inverted to produce an envelope function $G(t)$ such that $P(\hat{F}_{n,m}(t) \leq G(t), \forall t) \geq 1-\delta$.
3. Refinement Strategies for Outlier Detection: For outlier detection, where the number of true nulls (inliers) is unknown, the authors integrate two tightening techniques:
   • Self-Refinement: Adapting a technique from [HSG19] to iteratively improve the bound on the number of false discoveries by leveraging the monotonicity of the selection set.
   • Null-Proportion Tightening: Estimating an upper bound on the number of true nulls ($m_0$) and constructing the envelope based on the distribution $P_{n,m_0}$ rather than $P_{n,m}$, significantly reducing conservativeness.
4. Application to Conformal Selection: For conformal selection (e.g., drug discovery), the authors utilize "oracle" conformal $p$-values (which depend on unknown true outcomes) to bound the number of false discoveries. They prove that under specific monotone score functions (e.g., clipped scores), the number of false discoveries is bounded by the empirical CDF of these oracle variables, allowing the simultaneous envelope method to be applied directly.

Key Contributions

1. Novel Upper Bounds on Empirical CDFs: The paper establishes a new high-probability upper bound on the empirical CDF of conformal uniform variables. Empirically, this bound is tighter than existing bounds based on DKW-type inequalities, particularly by adapting to the heteroskedasticity of the empirical CDF (which varies with $t$).
2. Simultaneous FDP Bounds for Outlier Detection: The authors develop a method to bound the FDP for outlier detection simultaneously over all thresholds. This combines the improved CDF bound with self-refinement and null-proportion tightening techniques.
3. First Finite-Sample FDP Bounds for Conformal Selection: The paper provides the first finite-sample FDP bounds that hold uniformly over all rejection thresholds for conformal selection problems.
4. General Framework: The work introduces a general framework for deriving high-probability bounds on random functions by sampling from the joint distribution of null $p$-values, offering sharper bounds than concentration inequality-based approaches while preserving finite-sample validity.

Results
The authors validate their framework through synthetic and real-data experiments:

• Synthetic Outlier Detection: Experiments on Gaussian mixture models demonstrate that the proposed FDP bounds (specifically using the Truncated Higher-Criticism statistic) maintain valid coverage (exceeding the target 90% confidence) across 100 replications. The bounds are shown to be substantially less conservative than the baseline linear bounds, especially for small rejection thresholds. The combination of self-refinement and null-proportion tightening yields the sharpest bounds.
• Real-World Drug Discovery: Using the DAVIS dataset for drug-target interaction prediction, the method is applied to select promising drug candidates. The results show that the simultaneous upper bound consistently lies above the true FDP across all selection thresholds in 92% of independent runs.
• Post Hoc Adaptivity: The paper demonstrates that practitioners can adaptively vary the selection threshold (e.g., increasing $\alpha$ to find more candidates) while the proposed bound remains valid. In contrast, standard post hoc adjustments of the BH level fail to upper-bound the realized FDP.

Significance and Claims
The paper claims to provide a solution to the "realized FDP" problem, offering practitioners instance-wise guarantees rather than just average-case guarantees. By enabling arbitrary post hoc threshold selection, the framework supports flexible, data-driven exploration without sacrificing statistical rigor. The authors emphasize that their approach yields "substantially less conservative" bounds compared to existing methods, making conformal inference more practical for high-stakes applications like scientific discovery and medical screening where follow-up costs are high. The work is presented as a unified strategy applicable to any problem where the joint distribution of null $p$-values can be simulated, extending beyond the specific examples of outlier detection and conformal selection.