betaFeedback

WorksMathematics

Almost Controlled: The FDR of Benjamini-Hochberg on Weighted Conformal p-Values

Abstract

Weighted conformal p-values generalize conformal inference to cases with covariate shift. One way to use them is to pass them to the Benjamini-Hochberg (BH) procedure, either to decide which test units to select or to detect outliers. But weighted conformal p-values may not be positively dependent, so we want to know: does BH still control the false discovery rate (FDR) in finite samples? Based on experiments, it appears to, but we prove it doesn't. We give two counterexamples, certified in exact rational arithmetic, where the FDR exceeds its target level qq. We also identify how large the difference between the FDR and qq can be. With nn calibration points, mm test units and weight ratio BB, the relative excess FDR/q−1\mathrm{FDR}/q-1 is bounded by a function of nn, mm, BB and qq that is of order Bm/(nq)\sqrt{Bm/(nq)} when Bm/(nq)Bm/(nq) is small. The bound holds for every configuration with B≤nB\le n and every nn. This order can be reached when multiple non-null test units share a common threshold: in a Poisson-limit model, that configuration's excess is c(q)Bm/(nq)c(q)\sqrt{Bm/(nq)} to first order as B/n→0B/n\to0 and then m→∞m\to\infty. For some fixed distributions with this structure, the excess decreases only like n−1/2n^{-1/2} as nn grows. If every test unit is null, the excess is O(B/n)O(B/n) at fixed mm, and in certain configurations it grows linearly with mm. To assist practitioners in judging how large the FDR can be, we turn that bound, which depends only on nn, mm, qq and BB, into a lowered BH level with proved finite-sample control, and give a much less conservative rule of thumb that covers every worst case we were able to find but provides no guarantee.

Introduction

Conformal p-values make a simple comparison: where does a test point’s score fall among the scores of a held-out calibration set? As long as the calibration and test data are exchangeable, these p-values are valid in finite samples [1, 11]. But in many applications, the data aren’t exchangeable. The test units come from a covariate distribution QQ that differs from the calibration distribution PP, and the plain comparison loses its guarantee. Weighted conformal p-values [20, 12] correct for this covariate shift by reweighting each calibration point by the likelihood ratio w(x)∝dQ/dP(x)w(x) \propto dQ/dP(x). They’re used for two tasks. In selection, we’re given mm test units and want the ones whose unobserved outcome clears a threshold. Outlier detection is about flagging test units that don’t come from the calibration distribution. Either way, we form a p-value for each test unit, and we want to control the false discovery rate (FDR). The default tool is the Benjamini–Hochberg (BH) procedure [2].

For unweighted conformal p-values, this is safe. The p-values are positively dependent, and BH controls the FDR [1, 11]. Weights break that argument. Jin & Candès [12] note that weighted conformal p-values “cannot be passed on to classical multiple testing procedures since they may not obey a well-known positive dependence property”, and they propose weighted conformalized selection, which has exact finite-sample control. Does plain BH on weighted conformal p-values also control the FDR? They left that open. In their words, “it remains unclear whether applying existing multiple testing procedures controls the FDR in finite samples” (§1.2), even though BH “empirically controls the FDR in all of our numerical experiments” (§2.3). Recent work still treats the question as open (Section 1.1).

Contributions. This paper answers the question and measures the failure. Throughout, nn is the number of calibration points, mm the number of test units, qq the target level and BB the ratio of the largest to the smallest weight; κ:=B/n\kappa:= B/n.

  1. BH does not control the FDR in finite samples (Theorem 5). We give two configurations that satisfy Jin & Candès’s assumptions and have FDR >q>q, certified in exact rational arithmetic: one in which every test unit is null, and one in strict selection, where the threshold is independent of the outcome given the covariate. In the second, with n=80n=80, m=8m=8 and q=1/10q=1/10, the FDR is 1.136q1.136q.

  1. With non-null units, the worst excess is of order Bm/(nq)\sqrt{Bm/(nq)}. In every configuration with B≤nB\le n and at every nn, FDR/q−1≤κ+1.612(1+κ)Bm/(nq)+O(Bm/(nq))\mathrm{FDR}/q-1\le\kappa+1.612\sqrt{(1+\kappa)Bm/(nq)}+O(Bm/(nq)) (Theorem 6). Conversely, in a Poisson-limit model a construction with non-null “decoy” units that share a threshold has excess c(q)κm/qc(q)\sqrt{\kappa m/q} to first order, as κ→0\kappa\to0 and then m→∞m\to\infty, with c(q)=(1−q)e−1−2q/(22π)c(q)=(1-q)e^{-1-2q}/(2\sqrt{2\pi}) (Theorems 9, 11 and 15). For some fixed distributions the excess decays only like n−1/2n^{-1/2} (Theorem 12 and Example 13).

  1. When every test unit is null, the excess is smaller. It is O(B/n)O(B/n) at fixed mm (Theorem 17), and there are configurations where FDR−q\mathrm{FDR}-q is, to first order, at least 12q(1−q)(m−1)(1−q+q/m)B/n\frac{1}{2}q(1-q)(m-1)(1-q+q/m)B/n, linear in mm; as m→∞m\to\infty the constant per unit of qmB/nqmB/n is at least 12(1−q)\frac{1}{2}(1-q) (Theorem 16). Whether the upper bound is also linear in mm is supported numerically and by a sketch, but not proved.

  1. Practical remedies (§ 7): a computable envelope for the FDR, a level deflation with proved finite-sample control that uses only nn, mm, qq and BB, and a numerical rule of thumb, about ten times less conservative, that covered every worst case we found.

How large is the excess? The certified strict-selection construction uses a weight ratio comparable to nn (B≈1.5nB\approx1.5n to 1.7n1.7n). If we re-tune it for each nn, it gives FDR =1.069q=1.069q, 1.103q1.103q and 1.136q1.136q at n=20n=20, 4040 and 8080 (Remark 88). When B≪nB\ll n, the rates above govern the excess. Across the Poisson-limit configurations our searches found, the relative excess stayed below 0.17Bm/(nq)0.17\sqrt{Bm/(nq)} whenever B/n≤0.1B/n\le0.1. Among those configurations, the largest excess at any B/nB/n was 51%, and it needed extreme weights (BB about 10n10n). But in the Poisson-limit model, the coefficient of B/n\sqrt{B/n} in the excess grows like m\sqrt{m} (Theorem 11, as B/n→0B/n\to0).

Mechanisms and techniques. Given the calibration data DD, the test p-values are independent, so all the dependence that BH sees passes through DD. Lemma 2 makes this exact. When every null is an oracle null (its threshold equals its outcome), FDR−q\mathrm{FDR}-q is a weighted sum of covariances minus a non-negative term. Each covariance is between the null mass below a BH threshold and the probability that the other units drive BH to exactly that many rejections. The non-negative term comes from non-null units with small oracle p-values, and in our constructions it is zero. This covariance behaves very differently in two regimes (§ 3). If every test unit is an oracle null, the conditional law of the test p-value is uniform on average over DD, so a fluctuation of the calibration data has no first-order effect. What’s left is a second-order effect of the curvature of Simes’ test, of order B/nB/n. Things are different when non-null units share a threshold. Their rejection switches on and off with DD, and the switch can be correlated with the null mass at first order, which gives an excess of order B/n\sqrt{B/n}. For the upper bound we use a cruder reduction: the FDR is at most qq times the expected largest ratio, over the BH thresholds, of the conditional null mass below a threshold to the threshold itself (Proposition 3). We then bound the worst relative error of a weighted empirical distribution function on the BH grid.

Some of our lower bounds are proved in a Poisson-limit model, in which a few heavily weighted covariate cells have Poisson calibration counts, and some statements rest on numerical evidence. We say so wherever this is the case.

Outline. § 2 sets up the notation and two reductions, and § 3 gives the counterexamples and the two mechanisms. § 4 proves, with non-null units, an upper bound of order Bm/(nq)\sqrt{Bm/(nq)} and, in the Poisson-limit model, a lower bound of the same order. § 6 treats the global null. § 7 collects what a practitioner can compute, and § 8 discusses open problems. All proofs are in the appendices; Appendix § 14 gives the certificates for the counterexamples.

Related work

Multiple testing under dependence. The BH procedure [2] controls the FDR for independent p-values and, as Jin & Candès [12] recall, “when applied to PRDS p-values” [3]. For all other forms of dependence, Benjamini & Yekutieli [3] show that a conservative modification of BH controls the FDR: BH at level q/∑k≤m1/kq/\sum_{k\le m}1/k. Hommel [10] gives tests of the global (intersection) null hypothesis under arbitrary dependence, with sharp bounds on their error probability, and Sarkar [18] extends FDR control under positive dependence from the BH step-up procedure to more general stepwise procedures with the same critical values. Fithian & Lei [5] calibrate a data-dependent rejection threshold for each hypothesis to target exact FDR control when the dependence is known; their dBH procedure dominates BH under positive regression dependence and BY in general.

Conformal p-values and selection. For unweighted conformal p-values, Bates et al. [1] prove that the p-values are positively dependent and that BH controls the FDR exactly, in a marginal sense. Jin & Candès [11] use conformal p-values with BH-type thresholds for selection under exchangeability. Under covariate shift, weighted conformal p-values [20, 12] “cannot be passed on to classical multiple testing procedures since they may not obey a well-known positive dependence property” [12]. This motivates weighted conformalized selection (WCS), which comes with exact finite-sample control. With e-values, Lee & Ren [15] show that e-BH on weighted conformal e-values controls the FDR, “but unlike before, this is no longer equivalent to applying BH to the weighted conformal p-values” (their §6.2). Lee et al. [16] develop full-conformal e-values with finite-sample control.

The question remains open in recent work. Lee et al. [16] compare with BH on weighted conformal p-values, which “is not necessarily FDR-controlling”. Hennhöfer & Preisach (2026, §5.4) write that applying BH directly to discrete weighted conformal p-values “is not theoretically justified in general”, and Hennhöfer et al. (2026, §2.8) note that “exact finite-sample FDR control generally requires procedures tailored to the weighted setting”. None of these works proves or disproves finite-sample control, or bounds the excess. Neither does any other work we found.

Setting and two reductions

Data and p-values. We observe calibration data (Xi,Yi)(X_i,Y_i), i=1,…,ni=1,\ldots,n, drawn i.i.d. from PP, and mm test units (Xn+j,Yn+j)(X_{n+j},Y_{n+j}) drawn from QQ, where dQ/dP=w(X)/EPw\mathrm{d}Q/\mathrm{d}P=w(X)/\mathbb{E}_P w for a known weight function with 1≤w≤B1\le w\le B. We write B:=sup⁡w/EPw≤BB:=\sup w/\mathbb{E}_P w\le B and κ:=B/n\kappa:=B/n. Test unit jj has a threshold cn+jc_{n+j} and is null iff Yn+j≤cn+jY_{n+j}\le c_{n+j}. With a score V(x,y)V(x,y) that is monotone in yy, write Vi:=V(Xi,Yi)V_i:=V(X_i,Y_i) and V^n+j:=V(Xn+j,cn+j)\widehat V_{n+j}:=V(X_{n+j},c_{n+j}). The weighted conformal p-value of Jin & Candès [12] is

pj=∑i≤nw(Xi)1{Vi<V^n+j}+Uj(w(Xn+j)+∑i≤nw(Xi)1{Vi=V^n+j})∑i≤nw(Xi)+w(Xn+j),p_j=\frac{\sum_{i\le n}w(X_i)\mathbf{1}\{V_i<\widehat V_{n+j}\}+U_j\left(w(X_{n+j})+\sum_{i\le n}w(X_i)\mathbf{1}\{V_i=\widehat V_{n+j}\}\right)}{\sum_{i\le n}w(X_i)+w(X_{n+j})},

with Uj∼Unif⁡(0,1)U_j\sim\operatorname{Unif}(0,1) for tie-breaking. The oracle p-value pj∗p_j^* is the same expression with V^n+j\widehat V_{n+j} replaced by the true score V(Xn+j,Yn+j)V(X_{n+j},Y_{n+j}). A null unit with cn+j=Yn+jc_{n+j}=Y_{n+j} (an oracle null) has pj=pj∗p_j=p_j^*, and every null unit has pj≥pj∗p_j\ge p_j^*. BH at level qq uses the grid tk:=qk/mt_k:=qk/m; it finds the largest kk such that at least kk p-values are at most tkt_k, and rejects the units whose p-values are at most that tkt_k. We write DD for the calibration data. The assumptions of Jin & Candès [12] (i.i.d. test tuples and UjU_j, independent of DD) hold throughout, and some results need only the weaker assumptions (A1)–(A3) of Assumption 61 (Appendix E). Strict selection means that cn+jc_{n+j} is independent of Yn+jY_{n+j} given Xn+jX_{n+j}; in the global null every test unit is null. In outlier detection the inliers are drawn from QQ and are the nulls, and the outliers come from another distribution.

Two exact facts organise the analysis. Oracle p-values are exactly uniform, ties included; and, given DD, the test units are i.i.d., which leads to an exact identity for the excess and to two reductions.

Lemma 1 (Exact uniformity). P(pj∗≤s)=s\mathbb{P}(p_j^*\le s)=s for all s∈[0,1]s\in[0,1].

Intuition. Given the multiset of the n+1n+1 points, the test point is each of them with probability proportional to its weight. The randomised weighted CDF maps each tie group to an interval whose length is exactly that group’s probability. So the intervals tile [0,1][0,1] and p∗p^* is uniform, ties included.

Lemma 2 (Exact covariance identity). Let Ak(D):=P(unit 1 null, p1≤tk∣D)A_k(D) := \mathbb{P}(\text{unit 1 null},\ p_1 \le t_k \mid D) and rk(D):=P(R1=k∣D)r_k(D) := \mathbb{P}(R_1 = k \mid D), where R1R_1 is the number of BH rejections among (0,p2,…,pm)(0,p_2,\ldots,p_m). If every null unit is an oracle null and ϵk:=P(unit 1 non-null, p1∗≤tk)\epsilon_k := \mathbb{P}(\text{unit 1 non-null},\ p_1^* \le t_k), then for every nn,

FDR⁡−q=m∑k=1m1kCov⁡(Ak(D),rk(D))−m∑k=1m1kϵkErk(D).\operatorname{FDR}-q = m\sum_{k=1}^{m}\frac{1}{k}\operatorname{Cov}(A_k(D),r_k(D))-m\sum_{k=1}^{m}\frac{1}{k}\epsilon_k\mathbb{E}r_k(D).

Intuition. Given the calibration data, BH sees mm i.i.d. p-values, and the leave-one-out identity turns the FDR into an average of the null mass below the threshold the other units set. If that null mass did not move with what the other units do, the average would be qq (minus the ϵ\epsilon-term). So the whole excess is a covariance between the null mass below tkt_k and the chance that the others drive BH to exactly kk rejections.

Lemma 2 is the basis of the fixed-distribution analysis in § 4. For upper bounds we use a cruder reduction that needs no oracle assumption.

References

  1. [1]Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. The Annals of Statistics, 51(1):149–178, 2023. doi: 10.1214/22-AOS2244.DOI
  2. [2]Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society Series B: Statistical Methodology, 57(1):289–300, 1995. doi: 10.1111/j.2517-6161.1995.tb02031.x.DOI
  3. [3]Yoav Benjamini and Daniel Yekutieli. The control of the false discovery rate in multiple testing under dependency. The Annals of Statistics, 29(4):1165–1188, 2001. doi: 10.1214/aos/1013699998.DOI
  4. [4]A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642–669, 1956. doi: 10.1214/aoms/1177728174.DOI
  5. [5]William Fithian and Lihua Lei. Conditional calibration for false discovery rate control under dependence. The Annals of Statistics, 50(6):3091–3118, 2022. doi: 10.1214/21-AOS2137.DOI
  6. [6]J. K. Ghosh. A new proof of the Bahadur representation of quantiles and an application. The Annals of Mathematical Statistics, 42(6):1957–1961, 1971. doi: 10.1214/aoms/1177693063.DOI
  7. [9]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. doi: 10.1080/01621459.1963.10500830.DOI
  8. [10]G. Hommel. Tests of the overall hypothesis for arbitrary dependence structures. Biometrical Journal, 25(5):423–430, 1983. doi: 10.1002/bimj.19850250502.DOI
  9. [11]Ying Jin and Emmanuel J. Candès. Selection by prediction with conformal p-values. Journal of Machine Learning Research, 24(244):1–41, 2023.arxiv.org/abs/2210.01408
  10. [12]Ying Jin and Emmanuel J. Candès. Model-free selective inference under covariate shift via weighted conformal p-values. Biometrika, 113(1):asaf066, 2026. doi: 10.1093/biomet/asaf066.DOI
  11. [13]Alexander S. Kechris. Classical Descriptive Set Theory. Graduate Texts in Mathematics. Springer, New York, 1995. doi: 10.1007/978-1-4612-4190-4.DOI
  12. [14]Lucien Le Cam. An approximation theorem for the Poisson binomial distribution. Pacific Journal of Mathematics, 10(4):1181–1197, 1960. doi: 10.2140/pjm.1960.10.1181.DOI
  13. [15]Junu Lee and Zhimei Ren. Boosting e-BH via conditional calibration. arXiv preprint arXiv:2404.17562, 2024.arxiv.org/abs/2404.17562
  14. [16]Junu Lee, Ilia Popov, and Zhimei Ren. Full-conformal novelty detection. arXiv preprint arXiv:2501.02703, 2025.arxiv.org/abs/2501.02703
  15. [17]P. Massart. The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality. The Annals of Probability, 18(3):1269–1283, 1990. doi: 10.1214/aop/1176990746.DOI
  16. [18]Sanat K. Sarkar. Some results on false discovery rate in stepwise multiple testing procedures. The Annals of Statistics, 30(1):239–257, 2002. doi: 10.1214/aos/1015362192.DOI
  17. [19]R. J. Simes. An improved Bonferroni procedure for multiple tests of significance. Biometrika, 73(3):751–754, 1986. doi: 10.1093/biomet/73.3.751.DOI
  18. [20]Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel J. Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. In Advances in Neural Information Processing Systems 32, 2019.arxiv.org/abs/1904.06019
  19. [21]A. W. van der Vaart. Asymptotic Statistics, volume 3 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. doi: 10.1017/CBO9780511802256.

Paper details

vlnc:W_rjcryxeh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Large language models

View statement
Looking for related papers…
Contents