$p_{i}=\frac{1+|\\{j\in\mathcal{D}^{\textnormal{cal}}:S_{j}\leq\hat{s}(X_{2n+i})\\}|}{n+1}=\frac{1+|\\{j\in\mathcal{D}^{\textnormal{cal}}:F_{S}(S_{j})\leq
F_{S}(\hat{s}(X_{2n+i}))\\}|}{n+1}$

where $F_{S}$ denotes the CDF of $\hat{s}(X)$ conditional on $\mathcal{D}$. As
a result, we can assume $\hat{s}(X)\sim\textnormal{Unif}([0,1])$ without loss
of generality. Conditional on $\mathcal{D}$, $p_{1},\ldots,p_{m}$ are i.i.d.
random variables with

$\mathbb{P}\left[p_{i}=\frac{j}{n+1}\mid\mathcal{D}\right]=S_{(j)}-S_{(j-1)},\qquad
j=1,\ldots,n+1,$

where $S_{(1)}<S_{(2)}<\ldots<S_{(n)}$ denote the order statistics of
$(S_{1},\ldots,S_{n})$, and $S_{(0)}=0,S_{(n+1)}=1$. By Lemma 3, we can
reformulate the distribution of $p_{i}$ conditional on $\mathcal{D}$ as

$\mathbb{P}\left[p_{i}=\frac{j}{n+1}\mid\mathcal{D}\right]=\frac{V_{j}}{\sum_{k=1}^{n+1}V_{k}},\qquad
j=1,\ldots,n+1.$ (27)

As a result, for $k\in\\{1,2\\}$,

$\displaystyle\mathbb{E}\left[G^{k}(p_{i})\mid\mathcal{D}\right]=\frac{\sum_{j=1}^{n+1}G^{k}\left(\frac{j}{n+1}\right)V_{j}}{\sum_{j=1}^{n+1}V_{j}}=\frac{(n+1)^{-1}\sum_{j=1}^{n+1}G^{k}\left(\frac{j}{n+1}\right)V_{j}}{(n+1)^{-1}\sum_{j=1}^{n+1}V_{j}}.$
(28)

By the strong law of large number,

$\frac{1}{n+1}\sum_{j=1}^{n+1}V_{j}\stackrel{{\scriptstyle\mathrm{a.s.}}}{{\rightarrow}}\mathbb{E}[V_{1}]=1.$
(29)

Let $g_{n}=\max_{j\in\\{1,\ldots,n+1\\}}G(j/(n+1))$. Since
$V_{1},\ldots,V_{n+1}$ are independent,

$\displaystyle\textnormal{Var}\left[\frac{1}{n+1}\sum_{j=1}^{n+1}G^{k}\left(\frac{j}{n+1}\right)V_{j}\right]=\sum_{j=1}^{n+1}\frac{1}{(n+1)^{2}}\mathbb{E}\left[G^{2k}\left(\frac{j}{n+1}\right)(V_{j}-1)^{2}\right]$
$\displaystyle=\frac{1}{(n+1)^{2}}\sum_{j=1}^{n+1}G^{2k}\left(\frac{j}{n+1}\right)\leq\frac{g_{n}^{2k-2}}{(n+1)}\frac{1}{n+1}\sum_{j=1}^{n+1}G^{2}\left(\frac{j}{n+1}\right).$
(30)

By condition (ii),

$\bigg{|}\frac{1}{n+1}\sum_{j=1}^{n+1}G^{2}\left(\frac{j}{n+1}\right)-\int_{0}^{1}G^{2}(u)du\bigg{|}=o(1),$

and thus

$\frac{1}{n+1}\sum_{j=1}^{n+1}G^{2}\left(\frac{j}{n+1}\right)=O(1).$

By condition (iii), $g_{n}=o(\sqrt{n})$. Together with (30), we obtain that
for $k\in\\{1,2\\}$,

$\textnormal{Var}\left[\frac{1}{n+1}\sum_{j=1}^{n+1}G^{k}\left(\frac{j}{n+1}\right)V_{j}\right]=o(1).$

By Chebyshev’s inequality,

$\frac{1}{n+1}\sum_{i=1}^{n}G^{k}\left(\frac{j}{n+1}\right)(V_{j}-1)=o_{P}(1).$

Applying the condition (ii) again, we arrive at

$\frac{1}{n+1}\sum_{i=1}^{n}G^{k}\left(\frac{j}{n+1}\right)V_{j}-\int_{0}^{1}G^{k}(u)du=o_{P}(1).$

By (28),

$\mathbb{E}\left[G^{k}(p_{i})\mid\mathcal{D}\right]-\int_{0}^{1}G^{k}(u)du=o_{P}(1),\qquad
k\in\\{1,2\\}.$ (31)

Let $a_{n}$ be a deterministic sequence such that $a_{n}<1/2$, and
$U\sim\textnormal{Unif}([0,1])$. Let also $\mathcal{E}_{n}$ be the event that
$\mathcal{D}$ is such that

$\mathcal{E}_{n}=\left\\{\mathcal{D}:\frac{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}{\textnormal{Var}[G(U)]}\in[1-a_{n},1+a_{n}]\right\\}.$
(32)

Since $G$ is a non-constant function, $\textnormal{Var}[G(U)]>0$. By (31), we
can choose $a_{n}=o(1)$ such that

$\mathbb{P}\left[\mathcal{E}_{n}^{c}\right]=o(1).$

Let

$W_{m}=\frac{\sum_{i=1}^{m}\left\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\right\\}}{\sqrt{m\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}}.$

By Lemma 2 with $g(x)=x$,

$d_{K}\left(\mathcal{L}\left(W_{m}\mid\mathcal{D}\right),N(0,1)\right)\leq\frac{A}{\sqrt{m}}\frac{\mathbb{E}\left[|G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]|^{3}\right]}{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]^{3/2}},$

where $A$ is a universal constant. Since $G(p_{i})\leq g_{n}$ almost surely,
by condition (iii),

$\mathbb{E}\left[|G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]|^{3}\right]\leq
2g_{n}\textnormal{Var}[G(p_{i})\mid\mathcal{D}].$

Thus,

$d_{K}\left(\mathcal{L}\left(W_{m}\mid\mathcal{D}\right),N(0,1)\right)\leq\frac{2A}{\sqrt{m}}\frac{g_{n}}{\textnormal{Var}\left[G(p_{i})\mid\mathcal{D}\right]^{1/2}}.$

On the event $\mathcal{E}_{n}$, the condition (iii) and that $n=O(m)$ imply
that

$d_{K}\left(\mathcal{L}\left(W_{m}\mid\mathcal{D}\right),N(0,1)\right)\leq\frac{4Ag_{n}}{\sqrt{m\textnormal{Var}[G(U)]}}=o(1).$

Since the Kolmogorov distance is invariant under rescalings, we have

$d_{K}\left(\mathcal{L}\left(\sqrt{\frac{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}{\textnormal{Var}[G(U)]}}W_{m}\mid\mathcal{D}\right),N\left(0,\frac{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}{\textnormal{Var}[G(U)]}\right)\right)=o(1).$

Since
$\textnormal{Var}[G(p_{i})\mid\mathcal{D}]/\textnormal{Var}[G(U)]\in[1-a_{n},1+a_{n}]\rightarrow
1$,

$d_{K}\left(N\left(0,\frac{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}{\textnormal{Var}[G(U)]}\right),N(0,1)\right)=o(1).$

Let

$K_{n}\triangleq
d_{K}\left(\mathcal{L}\left(\sqrt{\frac{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}{\textnormal{Var}[G(U)]}}W_{m}\mid\mathcal{D}\right),N(0,1)\right).$
(33)

The above arguments show that $K_{n}=o(1)$ on the event $\mathcal{E}_{n}$.

On the other hand, let

$c_{m}=\frac{c_{1-\alpha}(G)-m\mathbb{E}[G(U)]}{\sqrt{m\textnormal{Var}[G(U)]}},$

and

$\tilde{W}_{n}=\frac{\sqrt{n+1}(\mathbb{E}[G(p_{i})\mid\mathcal{D}]-\mathbb{E}[G(U)])}{\sqrt{\textnormal{Var}[G(U)]}}.$

Then

$\displaystyle\mathbb{P}\left[\sum_{i=1}^{m}G(p_{i})\geq\xi
c_{1-\alpha}(G)-m(\xi-1)\mathbb{E}[G(U)]\mid\mathcal{D}\right]=\mathbb{P}\left[\sqrt{\frac{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}{\textnormal{Var}[G(U)]}}W_{m}+\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\geq\xi
c_{m}\mid\mathcal{D}\right].$

By (33),

$\bigg{|}\mathbb{P}\left[\sqrt{\frac{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}{\textnormal{Var}[G(U)]}}W_{m}+\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\geq\xi
c_{m}\mid\mathcal{D}\right]-\bar{\Phi}\left(\xi
c_{m}-\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\right)\bigg{|}\leq K_{n}.$

Since $K_{n}=o(1)$ on $\mathcal{E}_{n}$ and
$\mathbb{P}[\mathcal{E}_{n}^{c}]=o(1)$, we obtain that

$\bigg{|}\mathbb{P}\left[\sum_{i=1}^{m}G(p_{i})\geq
c_{1-\alpha}(G)\mid\mathcal{D}\right]-\bar{\Phi}\left(\xi
c_{m}-\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\right)\bigg{|}=o_{P}(1).$ (34)

Since $\bar{\Phi}$ is a continuous function and $m/n\rightarrow\gamma$, to
prove (26), it remains to prove

$c_{m}\stackrel{{\scriptstyle
p}}{{\rightarrow}}z_{1-\alpha},\quad\tilde{W}_{n}\stackrel{{\scriptstyle
d}}{{\rightarrow}}N(0,1).$ (35)

Without loss of generality, we assume that $\eta\leq 1$ in the condition (i).
By Lemma 2 with $g(x)=x^{\eta}$, which clearly fulfills the criteria, we have
that

$d_{K}\left(\frac{\sum_{j=1}^{m}G(U_{i})-\mathbb{E}[G(U)]}{\sqrt{m\textnormal{Var}[G(U)]}},N(0,1)\right)\leq\frac{A}{m^{\eta/2}}\frac{\mathbb{E}[|G(U)-\mathbb{E}[G(U)]|^{2+\eta}]}{\textnormal{Var}[G(U)]^{1+\eta/2}}=o(1).$
(36)

By definition, $c_{m}$ is the $(1-\alpha)$-th quantile of
$\left(\sum_{j=1}^{m}G(U_{i})-\mathbb{E}[G(U)]\right)/\sqrt{m\textnormal{Var}[G(U)]}$.
By (36),

$|\bar{\Phi}(c_{m})-\alpha|=|\bar{\Phi}(c_{m})-\bar{\Phi}(z_{1-\alpha})|=o(1).$

Since $\bar{\Phi}^{\prime}(z_{1-\alpha})>0$, it implies the first part of
(35).

To prove the second part of (35), we recall (28) with $k=1$ that

$\tilde{W}_{n}=\frac{(n+1)^{-1/2}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(U)]\right\\}V_{j}}{\sqrt{\textnormal{Var}[G(U)]}\left(\sum_{j=1}^{n+1}V_{j}\right)/(n+1)}.$

Set
$X_{j}=(n+1)^{-1/2}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(U)]\right\\}(V_{j}-1)$
and $g(x)=x$ in Lemma 2. Then

$B_{n}=\frac{1}{n+1}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(U)]\right\\}^{2}.$

By the condition (ii), we have that

$B_{n}=\frac{1}{n+1}\sum_{j=1}^{n}G^{2}\left(\frac{j}{n+1}\right)-\frac{2\mathbb{E}[G(U)]}{n+1}\sum_{j=1}^{n}G\left(\frac{j}{n+1}\right)+(\mathbb{E}[G(U)])^{2}\rightarrow\textnormal{Var}[G(U)].$
(37)

By the condition (i), (iii) and (37),

$\displaystyle\sum_{j=1}^{n+1}\mathbb{E}|X_{j}|^{3}$
$\displaystyle\leq\frac{1}{(n+1)^{3/2}}\sum_{j=1}^{n+1}\bigg{|}G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(U)]\bigg{|}^{3}$
$\displaystyle\leq\frac{g_{n}+\mathbb{E}[G(U)]}{\sqrt{n+1}}\frac{1}{n+1}\sum_{j=1}^{n+1}\left(G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(U)]\right)^{2}$
$\displaystyle=\frac{g_{n}+\mathbb{E}[G(U)]}{\sqrt{n+1}}B_{n}=o(1).$

Let

$\tilde{W}^{\prime}_{n}=\frac{1}{\sqrt{B_{n}}}\sum_{j=1}^{n+1}X_{j}=\frac{1}{\sqrt{(n+1)B_{n}}}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(U)]\right\\}(V_{j}-1).$

Then Lemma 2 implies that

$d_{K}\left(\tilde{W}^{\prime}_{n},N(0,1)\right)\leq\frac{A\sum_{j=1}^{n+1}\mathbb{E}|X_{j}|^{3}}{B_{n}^{3/2}}=o(1).$
(38)

By definition,

$\tilde{W}_{n}=\left(\tilde{W}^{\prime}_{n}+\frac{1}{\sqrt{(n+1)B_{n}}}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(U)]\right\\}\right)\sqrt{\frac{B_{n}}{\textnormal{Var}[G(U)]}}\frac{1}{\left(\sum_{j=1}^{n}V_{j}\right)/(n+1)}.$

The condition (ii) with $k=1$ implies that

$\frac{1}{\sqrt{(n+1)}}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(U)]\right\\}=o(1).$
(39)

By (29), (37), (38), (39) and Slutsky’s Lemma, we prove the second part of
(35). Therefore, the limiting conditional type-I error (26) is proved.

Next, we prove the limiting marginal type-I error (25). Since

$\mathbb{P}\left[\sum_{i=1}^{m}G(p_{i})\geq\xi
c_{1-\alpha}(G)-m(\xi-1)\mathbb{E}[G(U)]\mid\mathcal{D}\right]$

is bounded almost surely, the convergence in distribution implies the
convergence in expectation. Therefore,

$\mathbb{P}\left[\sum_{i=1}^{m}G(p_{i})\geq\xi
c_{1-\alpha}(G)-m(\xi-1)\mathbb{E}[G(U)]\right]\rightarrow\mathbb{E}[\bar{\Phi}(\xi
z_{1-\alpha}+\sqrt{\gamma}W)].$

Let $W^{\prime}$ be an independent copy of $W$. Then

$\bar{\Phi}(\xi z_{1-\alpha}+\sqrt{\gamma}W)=\mathbb{P}\left[W^{\prime}\geq\xi
z_{1-\alpha}+\sqrt{\gamma}W\mid W\right].$

As a result,

$\mathbb{E}[\bar{\Phi}(\xi
z_{1-\alpha}+\sqrt{\gamma}W)]=\mathbb{P}\left[W^{\prime}\geq\xi
z_{1-\alpha}-\sqrt{\gamma}W\right]=\mathbb{P}\left[W^{\prime}-\sqrt{\gamma}W\geq\xi
z_{1-\alpha}\right].$

The proof is completed by the fact that $W^{\prime}-\sqrt{\gamma}W\sim
N(0,1+\gamma)$.

∎

###  A.3 Conformal p-values are PRDS

###### Proof of Theorem 2.

Let $Z=(S_{(1)},\dots,S_{(n)})$ be the order statistics of
$(\hat{s}(X_{i}))_{i\in\\{n+1,\dots,2n\\}}$, the conformal scores evaluated on
the calibration set. Let $Y=(p_{1},\dots,p_{m})$ be the conformal p-values
evaluated on the test set (i.e.,
$p_{j}=\hat{u}^{\textnormal{(marg)}}(X_{2n+j})$). Then,

$\displaystyle\mathbb{P}\left[Y\in A\mid Y_{i}=y\right]$
$\displaystyle=\int\mathbb{P}\left[Y\in A\mid
Z=z\right]\mathbb{P}\left[Z=z\mid Y_{i}=y\right]dz$
$\displaystyle=\mathbb{E}_{Z\mid Y_{i}=y}\left[\mathbb{P}\left[Y\in A\mid
Z\right]\right].$

With this representation, the conclusion will be implied by the following two
lemmas.

######  Lemma 4.

For a non-decreasing set $A$ and vectors $z,z^{\prime}$ such that $z\preceq
z^{\prime}$, then

$\mathbb{P}\left[Y\in A\mid Z=z\right]\geq\mathbb{P}\left[Y\in A\mid
Z=z^{\prime}\right].$

######  Lemma 5.

For $y\geq y^{\prime}$, if $i$ belongs to the set of inliers, there exists
$Z_{1}\sim Z\mid Y_{i}=y$ and $Z_{2}\sim Z\mid Y_{i}=y^{\prime}$ such that
$\mathbb{P}\left[Z_{1}\preceq Z_{2}\right]=1$.

In other words, Lemma 4 states that the conformal p-values increase as the
conformal scores on the calibration set decrease, while Lemma 5 states that a
larger conformal p-value indicates the calibration conformal scores are
smaller. The proof follows easily from these. Take any $y\geq y^{\prime}$ and
let $Z_{1}$ and $Z_{2}$ be as in the statement of Lemma 5. Then, for any $i$
belonging to the set of inliers,

$\displaystyle\mathbb{P}\left[Y\in A\mid Y_{i}=y\right]$
$\displaystyle=\mathbb{E}_{Z_{1}}\left[\mathbb{P}\left[Y\in A\mid
Z=Z_{1}\right]\right]$
$\displaystyle\geq\mathbb{E}_{Z_{2}}\left[\mathbb{P}\left[Y\in A\mid
Z=Z_{2}\right]\right]$ $\displaystyle=\mathbb{P}\left[Y\in A\mid
Y_{i}=y^{\prime}\right].$

The inequality follows from Lemma 4 and the fact that
$\mathbb{P}\left[Z_{1}\preceq Z_{2}\right]=1$, which comes from Lemma 5. ∎

Lemma 4 follows immediately from the definition of marginal conformal p-values
in (3). Lemma 5 is proved below.

###### Proof of Lemma 5, continuous case.

As in the proof of Theorem 6, since $\hat{s}(X)$ is continuously distributed,
we can assume without loss of generality that the scores $S_{i}$ follow the
uniform distribution on $[0,1]$. Let $S^{\prime}_{(1)}\leq
S^{\prime}_{(2)}\leq\ldots\leq S^{\prime}_{(n+1)}$ be the order statistics of
$(\hat{s}(X_{n+1}),\ldots,\hat{s}(X_{2n+1}))$ and $R_{2n+1}$ be the rank of
$\hat{s}(X_{2n+1})$ among these. By definition,

$\bigg{\\{}(S_{(1)},\ldots,S_{(n)})\mid
R_{2n+1}=k,S^{\prime}_{(1)},\ldots,S^{\prime}_{(n+1)}\bigg{\\}}=(S^{\prime}_{(1)},\ldots,S^{\prime}_{(k-1)},S^{\prime}_{(k+1)},\ldots,S^{\prime}_{(n+1)}).$

Since $\hat{s}(X)$ is continuously distributed, $R_{2n+1}$ is independent of
$(S^{\prime}_{(1)},S^{\prime}_{(2)},\ldots,S^{\prime}_{(n+1)})$. As a result,
for any positive integer $k\leq n+1$,

$\bigg{\\{}(S_{(1)},\ldots,S_{(n)})\mid
R_{2n+1}=k\bigg{\\}}\stackrel{{\scriptstyle
d}}{{=}}(S^{\prime}_{(1)},\ldots,S^{\prime}_{(k-1)},S^{\prime}_{(k+1)},\ldots,S^{\prime}_{(n+1)}).$

The right-hand-side is clearly entry-wise non-increasing in $k$. Since
$p_{1}=R_{2n+1}/(n+1)$, Lemma 5 is proved for $i=1$. The same proof carries
over to other indices $i$ belonging to the set of inliers.

∎

##### Extension to non-continuous scores.

When $\hat{s}(X)$ has atoms, the set of conformity scores
$\\{\hat{s}(X_{i}):i\in\mathcal{D}^{\textnormal{cal}}\\}$ have ties with non-
zero probability. In this case, we replace the marginal conformal p-value (2)
by a randomized version, i.e.,

$p_{j}=\frac{|\\{i\in\mathcal{D}^{\text{cal}}:\hat{s}(X_{i})<\hat{s}(X_{2n+j})\\}|+\lceil(1+|\\{i\in\mathcal{D}^{\text{cal}}:\hat{s}(X_{i})=\hat{s}(X_{2n+j})\\}|)U_{j}\rceil}{n+1},$
(40)

where $U_{1},U_{2},\ldots$ are i.i.d. random variables drawn from
$\textnormal{Unif}([0,1])$ which are independent of the data. Note that (40)
is identical to (2) almost surely when $\hat{s}(X)$ is continuously
distributed. Now we prove that the marginal conformal p-values defined in (40)
satisfy the PRDS property.

######  Proposition 4 (Theorem 2 for the non-continuous case).

Consider the setting of Theorem 2, but where $\hat{s}(\cdot)$ is not assumed
to be continuous. Define the randomized marginal p-values as in (40). Then,
the marginal conformal p-values $(p_{1},\dots,p_{m})$ are PRDS.

The proof follows as above, once we verify Lemma 4 and Lemma 5 in the more
general setting.

###### Proof of Lemma 4, general case.

Let $U=(U_{1},\ldots,U_{m})$. By definition, $U$ is independent of $(Y,Z)$,
and thus

$\mathbb{P}[Y\in A\mid Z=z]=\mathbb{P}[Y\in A\mid Z=z,U],\quad\text{a.s.}.$

Let $p_{j}(x;z,u)$ denote the mapping from $(X_{2n+j},Z,U)$ to $p_{j}$. Then

$p_{j}(x;z,u)=\frac{m_{<}(x;z)+\lceil\\{1+m_{=}(x;z)\\}u\rceil}{n+1},$

where

$m_{<}(x,z)=\sum_{i=1}^{n}I(z_{i}<x),\quad
m_{=}(x,z)=\sum_{i=1}^{n}I(z_{i}=x).$

If $z\preceq z^{\prime}$,

$m_{<}(x,z)\geq m_{<}(x,z^{\prime}),\quad m_{<}(x,z)+m_{=}(x,z)\geq
m_{<}(x,z^{\prime})+m_{=}(x,z^{\prime}).$ (41)

We claim that the mapping $p_{j}(x;z,u)$ is non-increasing in $z$ for every
$x$ and $u$. Equivalently, we will show that for any $x$ and $u\in[0,1]$,

$m_{<}(x,z)+\lceil\\{1+m_{=}(x,z)\\}u\rceil\geq
m_{<}(x,z^{\prime})+\lceil\\{1+m_{=}(x,z^{\prime})\\}u\rceil.$ (42)

We consider three cases.

  1. Case 1:

if $m_{<}(x,z)=m_{<}(x,z^{\prime})$, (41) implies that $m_{=}(x,z)\geq
m_{=}(x,z^{\prime})$. Thus, (42) is obviously true.

  2. Case 2:

if $m_{<}(x,z)+m_{=}(x,z)=m_{<}(x,z^{\prime})+m_{=}(x,z^{\prime})$, let
$a=1+m_{=}(x,z)$ and $b=m_{<}(x,z)-m_{<}(x,z^{\prime})$. Then (42) is
equivalent to

$b\geq\lceil(a+b)u\rceil-\lceil au\rceil.$

This can be proved using the fact that $\lceil(a+b)u\rceil\leq\lceil
au\rceil+\lceil bu\rceil$.

  3. Case 3:

if $m_{<}(x,z)>m_{<}(x,z^{\prime})$ and
$m_{<}(x,z)+m_{=}(x,z)>m_{<}(x,z^{\prime})+m_{=}(x,z^{\prime})$, then
$m_{<}(x,z)\geq m_{<}(x,z^{\prime})+1$ and $m_{<}(x,z)+m_{=}(x,z)\geq
m_{<}(x,z^{\prime})+m_{=}(x,z^{\prime})+1$ since
$m_{<}(x,z),m_{<}(x,z^{\prime}),m_{=}(x,z)$, and $m_{=}(x,z^{\prime})$ are all
integers. Then

$\displaystyle m_{<}(x,z)+\lceil\\{1+m_{=}(x,z)\\}u\rceil$ $\displaystyle\geq
m_{<}(x,z)+\\{1+m_{=}(x,z)\\}u$
$\displaystyle=m_{<}(x,z)(1-u)+\\{1+m_{=}(x,z)+m_{<}(x,z)\\}u$
$\displaystyle\geq\\{1+m_{<}(x,z^{\prime})\\}(1-u)+\\{2+m_{=}(x,z^{\prime})+m_{<}(x,z^{\prime})\\}u$
$\displaystyle=m_{<}(x,z^{\prime})+\\{1+m_{=}(x,z^{\prime})\\}u+1$
$\displaystyle\geq
m_{<}(x,z^{\prime})+\lceil\\{1+m_{=}(x,z^{\prime})\\}u\rceil.$

Therefore, (42) is proved. As a result, the mapping from
$(X_{2n+1},\ldots,X_{2n+m},Z,U)$ to $Y$ is entry-wise non-increasing in $Z$
given $(X_{2n+j},\ldots,X_{2n+m},U)$. Since $\\{X_{2n+j}:j=1,\ldots,m\\}$,
$Z$, and $U$ are mutually independent, we arrive at

$\mathbb{P}[Y\in A\mid Z=z,U]\geq\mathbb{P}[Y\in A\mid
Z=z^{\prime},U],\quad\text{a.s.}.$

The independence between $U$ and $Z$ implies that $(U\mid
Z=z)\stackrel{{\scriptstyle d}}{{=}}(U\mid Z=z^{\prime})$. Lemma 4 then
follows from the above inequality. ∎

###### Proof of Lemma 5, general case.

Let $R_{2n+j}=(n+1)p_{j}$. Note that $R_{2n+j}$ can be interpreted as the rank
with ties broken randomly. As in the proof for the continuous case, we first
prove that

$\bigg{\\{}(S_{(1)},\ldots,S_{(n)})\mid
R_{2n+1}=k,S^{\prime}_{(1)},\ldots,S^{\prime}_{(n+1)}\bigg{\\}}=(S^{\prime}_{(1)},\ldots,S^{\prime}_{(k-1)},S^{\prime}_{(k+1)},\ldots,S^{\prime}_{(n+1)}).$
(43)

Let $k_{-}=\max\\{\ell:S^{\prime}_{(\ell)}<S_{2n+1}\\}$ and
$k_{+}=\min\\{\ell:S^{\prime}_{(\ell)}>S_{2n+1}\\}$. Then
$S^{\prime}_{\ell}=S_{2n+1}$ for any $k_{-}<\ell<k_{+}$. Since there exists at
least one $\ell$ with $S^{\prime}_{(\ell)}=S_{2n+1}$, i.e., the index
corresponding to $S_{2n+1}$, we have $k_{+}-k_{-}\geq 2$. By definition,

$1+|\\{i\in\mathcal{D}^{\text{cal}}:\hat{s}(X_{i})=\hat{s}(X_{2n+j})\\}|=|\\{i\in\mathcal{D}^{\text{cal}}\cup\\{2n+1\\}:\hat{s}(X_{i})=\hat{s}(X_{2n+j})\\}|=k_{+}-k_{-}-1.$

As a result,

$k=k_{-}+\lceil(k_{+}-k_{-}-1)U_{1}\rceil\in(k_{-},k_{+}).$

Therefore, $\hat{s}(X_{2n+1})=S^{\prime}_{(k)}$ and (43) is proved.

It remains to prove that $R_{2n+1}$ is independent of
$(S^{\prime}_{(1)},S^{\prime}_{(2)},\ldots,S^{\prime}_{(n+1)})$. For any non-
decreasing sequence $a_{1}\leq\ldots\leq a_{n+1}$, let
$1=n_{0}<n_{1}<\ldots<n_{m}=n+1$ be integers such that

$a_{n_{j-1}}=\ldots=a_{n_{j}-1}<a_{n_{j}},\quad j=1,\ldots,m-1,\quad
a_{n_{m-1}-1}<a_{n_{m-1}}=\ldots=a_{n_{m}}$

Let $\pi:\\{1,\ldots,n+1\\}\mapsto\\{1,\ldots,n+1\\}$ be a uniform random
permutation. Since $X_{n+1},\ldots,X_{2n+1}$ are i.i.d., Conditioning on the
event that,

$\bigg{\\{}\left(\hat{s}(X_{n+1}),\ldots,\hat{s}(X_{2n+1})\right)\mid(S^{\prime}_{(1)},\ldots,S^{\prime}_{(n+1)})=(a_{1},\ldots,a_{n+1})\bigg{\\}}\stackrel{{\scriptstyle
d}}{{=}}\left(a_{\pi(1)},\ldots,a_{\pi(n+1)}\right).$

For any $j=1,\ldots,m-1$, if $\pi(n+1)\in[n_{j-1},n_{j})$,

$|\\{i:a_{\pi(i)}=a_{\pi(n+1)}\\}|=n_{j}-n_{j-1},\quad|\\{i:a_{\pi(i)}<a_{\pi(n+1)}\\}|=n_{j-1}-1,$

and thus,

$R_{2n+1}=n_{j-1}-1+\lceil(n_{j}-n_{j-1})U_{j}\rceil.$

Similarly, if $\pi(n+1)\in[n_{m-1},n_{m}]$,

$R_{2n+1}=n_{m-1}-1+\lceil(n_{m}-n_{m-1}+1)U_{j}\rceil.$

For any $k$, let $j_{k}=\max\\{j:n_{j}\leq k\\}$, and $\mathcal{I}_{k}$ be the
set $\\{n_{j_{k}-1},\ldots,n_{j_{k}}-1\\}$ if $j_{k}<m$ and
$\\{n_{j_{k}-1},\ldots,n_{j_{k}}\\}$ otherwise. Then

$\displaystyle\mathbb{P}(R_{2n+1}=k\mid(S^{\prime}_{(1)},\ldots,S^{\prime}_{(n+1)})=(a_{1},\ldots,a_{n+1}))$
$\displaystyle=\mathbb{P}\left(\pi(n+1)\in\mathcal{I}_{k},U_{1}\in\left(\frac{k-n_{j_{k}-1}}{|\mathcal{I}_{k}|},\frac{k+1-n_{j_{k}-1}}{|\mathcal{I}_{k}|}\right]\right)$
$\displaystyle=\mathbb{P}\left(\pi(n+1)\in\mathcal{I}_{k}\right)\mathbb{P}\left(U_{1}\in\left(\frac{k-n_{j_{k}-1}}{|\mathcal{I}_{k}|},\frac{k+1-n_{j_{k}-1}}{|\mathcal{I}_{k}|}\right]\right)$
$\displaystyle=\frac{|\mathcal{I}_{k}|}{n+1}\frac{1}{|\mathcal{I}_{k}|}=\frac{1}{n+1}.$

Therefore, $R_{2n+1}$ is independent of
$(S^{\prime}_{(1)},\ldots,S^{\prime}_{(n+1)})$. The proof of Lemma 5 is then
completed. ∎

###  A.4 Storey’s correction does not break FDR control

Given a p-value $p_{i}$ for the $i$-th null hypothesis, let
$p_{(1)}\leq\ldots\leq p_{(m)}$ be the ordered statistics. Given a target FDR
level $\alpha$ and a scalar $\lambda\in(0,1)$, the rejection set of the
Storey-BH procedure is

$\mathcal{R}=\left\\{i:p_{i}\leq\frac{\alpha
R}{m\hat{\pi}_{0}},p_{i}<\lambda\right\\},$

where

$\hat{\pi}_{0}=\frac{1+\sum_{i=1}^{m}I(p_{i}\geq\lambda)}{m(1-\lambda)}\triangleq\frac{1+A}{m(1-\lambda)}$

and

$R=\max\left\\{r:p_{(r)}\leq\frac{\alpha
r}{m\hat{\pi}_{0}},p_{(r)}<\lambda\right\\}.$

The parameter $\lambda$ is often chosen as $0.5$, $\alpha$ or $1-\alpha$.

We start with a novel FDR bound for this procedure applied to PRDS p-values.

######  Theorem 7.

Assume that $(p_{1},\ldots,p_{n})$ is PRDS and each null p-value is super-
uniform with an almost sure lower bound $p_{\min}\in[0,1]$. Then

$\mathbb{E}\left[\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{\max\\{1,|\mathcal{R}|\\}}\right]\leq\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\mathbb{E}\left[\frac{1}{1+A}\mid
p_{i}\leq p_{*}\right],$

where

$p_{*}=\max\left\\{\frac{\alpha(1-\lambda)}{m},p_{\min}\right\\}.$

###### Proof.

Let

$V_{i}=I(H_{i}\text{ is rejected})\leq
I\left(p_{i}\leq\alpha(1-\lambda)\frac{R}{1+A}\right).$

Then

$\displaystyle\mathbb{E}\left[\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{\max\\{1,|\mathcal{R}|\\}}\right]$
$\displaystyle=\sum_{i\in\mathcal{H}_{0}}\mathbb{E}\left[\frac{V_{i}}{R\vee
1}\right]=\sum_{i\in\mathcal{H}_{0}}\sum_{r=1}^{m}\frac{1}{r}\mathbb{P}\left(p_{i}\leq\alpha(1-\lambda)\frac{r}{1+A},R=r\right)$
$\displaystyle=\sum_{i\in\mathcal{H}_{0}}\sum_{r=1}^{m}\sum_{a=1}^{m}\frac{1}{r}\mathbb{P}\left(p_{i}\leq\alpha(1-\lambda)\frac{r}{1+a},R=r,A=a\right).$

Let $r_{0}(a)=\max\\{1,\lceil(1+a)p_{\min}/(1-\lambda)\alpha\rceil\\}$. By
definition, the summand for a given $a$ is non-zero only if $r\geq r_{0}(a)$.
Thus,

$\displaystyle\mathbb{E}\left[\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{\max\\{1,|\mathcal{R}|\\}}\right]$
$\displaystyle=\sum_{i\in\mathcal{H}_{0}}\sum_{a=1}^{m}\sum_{r=r_{0}(a)}^{m}\frac{1}{r}\mathbb{P}\left(p_{i}\leq\alpha(1-\lambda)\frac{r}{1+a}\right)\mathbb{P}\left(R=r,A=a\mid
p_{i}\leq\alpha(1-\lambda)\frac{r}{1+a}\right)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\sum_{i\in\mathcal{H}_{0}}\sum_{a=1}^{m}\sum_{r=r_{0}(a)}^{m}\frac{1}{r}\cdot\alpha(1-\lambda)\frac{r}{1+a}\mathbb{P}\left(R=r,A=a\mid
p_{i}\leq\alpha(1-\lambda)\frac{r}{1+a}\right)$
$\displaystyle=\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\sum_{a=1}^{m}\sum_{r=r_{0}(a)}^{m}\frac{1}{1+a}\mathbb{P}\left(R=r,A=a\mid
p_{i}\leq\alpha(1-\lambda)\frac{r}{1+a}\right),$

where (i) uses the super-uniformity of the null p-value. Let $\mathcal{T}$
denote the set of all possible values that $r/(1+a)$ can take such that
$\mathbb{P}(p_{i}\leq\alpha(1-\lambda)r/(1+a))>0$, i.e.

$\mathcal{T}=\left\\{\frac{r}{1+a}:a\in\\{1,\ldots,m\\},r\in\\{r_{0}(a),\ldots,m\\},a+r\leq
m\right\\}.$

Clearly, $\mathcal{T}$ is a finite set. Let $t_{1}\leq t_{2}\leq\ldots\leq
t_{M}$ denote the elements of $\mathcal{T}$. It is easy to see that

$\alpha(1-\lambda)t_{1}\geq\max\left\\{p_{\min},\frac{\alpha(1-\lambda)}{m}\right\\}=p_{*}.$
(44)

Then,

$\displaystyle\mathbb{E}\left[\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{\max\\{1,|\mathcal{R}|\\}}\right]$
$\displaystyle\leq\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\sum_{a=1}^{m}\sum_{r=r_{0}(a)}^{m}\frac{1}{1+a}\mathbb{P}\left(R=r,A=a\mid
p_{i}\leq\alpha(1-\lambda)\frac{r}{1+a}\right)$
$\displaystyle=\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\sum_{j=1}^{M}\sum_{a=1}^{m}\sum_{r=r_{0}(a)}^{m}\frac{1}{1+a}\mathbb{P}\left(R=r,A=a\mid
p_{i}\leq\alpha(1-\lambda)\frac{r}{1+a}\right)\mathbb{I}\left[t_{j}=\frac{r}{1+a}\right]$
$\displaystyle=\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\sum_{j=1}^{M}\sum_{a=1}^{m}\sum_{r=r_{0}(a)}^{m}\frac{1}{1+a}\mathbb{P}\left(R=t_{j}(1+a),A=a\mid
p_{i}\leq\alpha(1-\lambda)t_{j}\right)\mathbb{I}\left[t_{j}=\frac{r}{1+a}\right]$
$\displaystyle=\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\sum_{j=1}^{M}\sum_{a=1}^{m}\frac{1}{1+a}\mathbb{P}\left(R=(1+a)t_{j},A=a\mid
p_{i}\leq\alpha(1-\lambda)t_{j}\right)$
$\displaystyle=\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\sum_{j=1}^{M}\mathbb{E}\left[\frac{I\\{R=(1+A)t_{j}\\}}{1+A}\mid
p_{i}\leq\alpha(1-\lambda)t_{j}\right]$
$\displaystyle=\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\sum_{j=1}^{M}\bigg{\\{}\mathbb{E}\left[H_{j}(p)\mid
p_{i}\leq\alpha(1-\lambda)t_{j}\right]-\mathbb{E}\left[H_{j+1}(p)\mid
p_{i}\leq\alpha(1-\lambda)t_{j}\right]\bigg{\\}}$
$\displaystyle=\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\bigg{\\{}\mathbb{E}\left[H_{1}(p)\mid
p_{i}\leq\alpha(1-\lambda)t_{1}\right]$
$\displaystyle\quad-\sum_{j=1}^{M-1}\left(\mathbb{E}\left[H_{j+1}(p)\mid
p_{i}\leq\alpha(1-\lambda)t_{j}\right]-\mathbb{E}\left[H_{j+1}(p)\mid
p_{i}\leq\alpha(1-\lambda)t_{j+1}\right]\right)\bigg{\\}},$

where $p=(p_{1},\ldots,p_{m})$ and

$H_{j}(p)=\frac{I\\{R\geq(1+A)t_{j}\\}}{1+A},\quad H_{M+1}(p)=0.$

Since $A$ is an increasing function of $p$ (element-wise) and $R$ is a
decreasing function of $p$ (element-wise), $H_{j}(p)$ is decreasing in $p$
(element-wise). The PRDS property implies that for any $j=1,\ldots,M-1$,

$\mathbb{E}\left[H_{j+1}(p)\mid
p_{i}\leq\alpha(1-\lambda)t_{j}\right]-\mathbb{E}\left[H_{j+1}(p)\mid
p_{i}\leq\alpha(1-\lambda)t_{j+1}\right]\geq 0.$

Therefore,

$\displaystyle\mathbb{E}\left[\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{\max\\{1,|\mathcal{R}|\\}}\right]$
$\displaystyle\leq\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\mathbb{E}\left[H_{1}(p)\mid
p_{i}\leq\alpha(1-\lambda)t_{1}\right]$
$\displaystyle\leq\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\mathbb{E}\left[\frac{1}{1+A}\mid
p_{i}\leq\alpha(1-\lambda)t_{1}\right]$
$\displaystyle\leq\alpha(1-\lambda)\sum_{i\in\mathcal{H}_{0}}\mathbb{E}\left[\frac{1}{1+A}\mid
p_{i}\leq p_{*}\right],$

where the last step follows from (44), the PRDS property, and the fact that
$p\mapsto 1/(1+A)$ is decreasing element-wise. ∎

To prove Theorem 3, we present an additional lemma.

######  Lemma 6.

[Lemma 1 from [78]] If $Y\sim\mathrm{Binom}(k-1,p)$, then
$\mathbb{E}[1/(1+Y)]\leq 1/kp$.

###### Proof of Theorem 3.

As in the proof of Theorem 6, since $\hat{s}(X)$ is continuously distributed,
we can assume $\hat{s}(X)\sim\textnormal{Unif}([0,1])$ without loss of
generality. We write $p_{i}$ instead of
$\hat{u}^{\textnormal{(marg)}}(X_{2n+i})$ and $S_{j}$ instead of
$\hat{s}(X_{n+j})$. Then

$p_{j}=\frac{1+\sum_{i=1}^{n}I(S_{i}\leq S_{n+j})}{n+1}.$

Then $p_{j}\geq 1/(n+1)$ almost surely. Let $m_{0}=|\mathcal{H}_{0}|$ and we
assume that $\mathcal{H}_{0}=\\{1,\ldots,m_{0}\\}$ without loss of generality.
Since $p=(p_{1},\ldots,p_{m})$ are PRDS and exchangeable, Theorem 4 implies
that

$\mathbb{E}\left[\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{\max\\{1,|\mathcal{R}|\\}}\right]\leq\alpha(1-\lambda)m_{0}\mathbb{E}\left[\frac{1}{1+A}\mid
p_{1}\leq\max\left\\{\frac{1}{n+1},\frac{\alpha(1-\lambda)}{m}\right\\}\right].$

Since $1/(1+A)$ is decreasing in $p$, using the PRDS property again, we have

$\mathbb{E}\left[\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{\max\\{1,|\mathcal{R}|\\}}\right]\leq\alpha(1-\lambda)m_{0}\mathbb{E}\left[\frac{1}{1+A}\mid
p_{1}\leq\frac{1}{n+1}\right]=\alpha(1-\lambda)m_{0}\mathbb{E}\left[\frac{1}{1+A}\mid
p_{1}=\frac{1}{n+1}\right].$ (45)

Let $A_{0}=\sum_{j=2}^{m_{0}}I(p_{j}\geq\lambda)$. Then

$\mathbb{E}\left[\frac{1}{1+A}\mid
p_{1}=\frac{1}{n+1}\right]\leq\mathbb{E}\left[\frac{1}{1+A_{0}}\mid
p_{1}=\frac{1}{n+1}\right].$

Let $S_{(1)}\leq S_{(2)}\leq\ldots\leq S_{(n+1)}$ denote the order statistics
of $S_{1},\ldots,S_{n+1}$ and $R_{n+1}$ denote the rank of $S_{n+1}$. Since
$S_{1}\sim\mathrm{Unif}([0,1])$, there is no tie almost surely.

Now we compute

$\mathbb{E}\left[\frac{1}{1+A_{0}}\mid
p_{1}=\frac{1}{n+1},S_{(1)},\ldots,S_{(n+1)}\right]=\mathbb{E}\left[\frac{1}{1+A_{0}}\mid
R_{n+1}=1,S_{(1)},\ldots,S_{(n+1)}\right].$ (46)

By definition,

$p_{2},\ldots,p_{m_{0}}\mid S_{1},\ldots,S_{n+1}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\frac{1+\sum_{j=1}^{n}I(S_{j}\leq U)}{n+1}$

where $U\sim\mathrm{Unif}([0,1])$. Note that there is a bijection between
$(S_{1},\ldots,S_{n+1})$ and $(S_{(1)},\ldots,S_{(n+1)},R_{1},\ldots,R_{n+1})$
for vectors without ties. The above distributional equivalence can be
rewritten as

$p_{2},\ldots,p_{m_{0}}\mid
R_{1},\ldots,R_{n+1},S_{(1)},\ldots,S_{(n+1)}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\frac{1+\sum_{j=1}^{n+1}I(S_{(j)}\leq U)-I(S_{(R_{n+1})}\leq
U)}{n+1}.$

Since the RHS does not depend on $(R_{1},\ldots,R_{n})$,
$(p_{2},\ldots,p_{m_{0}})$ is independent of $(R_{1},\ldots,R_{n})$
conditional on $(R_{n+1},S_{(1)},\ldots,S_{(n+1)})$. As a result,

$p_{2},\ldots,p_{m_{0}}\mid
R_{n+1}=1,S_{(1)},\ldots,S_{(n+1)}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\frac{1+\sum_{j=2}^{n+1}I(S_{(j)}\leq U)}{n+1}.$

Recall $K=(n+1)\lambda\in\mathbb{Z}$. Then

$\displaystyle\mathbb{P}\left(p_{2}\geq\lambda\mid
R_{n+1}=1,S_{(1)},\ldots,S_{(n+1)}\right)$
$\displaystyle=\mathbb{P}\left(\sum_{j=2}^{n+1}I(S_{(j)}\leq U)\geq K-1\mid
S_{(2)},\ldots,S_{(n+1)}\right)$ $\displaystyle=\mathbb{P}\left(U\geq
S_{(K)}\mid S_{(2)},\ldots,S_{(n+1)}\right)$ $\displaystyle=1-S_{(K)}.$

Therefore,

$I(p_{2}\geq\lambda),\ldots,I(p_{m_{0}}\geq\lambda)\mid
R_{n+1}=1,S_{(1)},\ldots,S_{(n+1)}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\mathrm{Ber}\left(1-S_{(K)}\right).$

This implies that

$A_{0}\mid
R_{n+1}=1,S_{(1)},\ldots,S_{(n+1)}\sim\mathrm{Binom}\left(m_{0}-1,1-S_{(K)}\right).$

By Lemma 6,

$\mathbb{E}\left[\frac{1}{1+A_{0}}\mid
R_{n+1}=1,S_{(1)},\ldots,S_{(n+1)}\right]\leq\frac{1}{m_{0}\\{1-S_{(K)}\\}}.$

Since $R_{n+1}$ is independent of $(S_{(1)},\ldots,S_{(n+1)})$,

$\mathbb{E}\left[\frac{1}{1+A_{0}}\mid
R_{n+1}=1\right]\leq\mathbb{E}\left[\frac{1}{m_{0}\\{1-S_{(K)}\\}}\right].$
(47)

By symmetry and the property of order statistics,

$1-S_{(K)}\stackrel{{\scriptstyle
d}}{{=}}S_{(n+2-K)}\sim\mathrm{Beta}(n+2-K,K).$

Thus,

$\displaystyle\mathbb{E}\left[\frac{1}{1-S_{(K)}}\right]$
$\displaystyle=\int_{0}^{1}\frac{1}{x}\frac{\Gamma(n+2)}{\Gamma(n+2-K)\Gamma(K)}x^{n+1-K}(1-x)^{K-1}dx$
$\displaystyle=\int_{0}^{1}\frac{\Gamma(n+2)}{\Gamma(n+2-K)\Gamma(K)}x^{n-K}(1-x)^{K-1}dx$
$\displaystyle=\frac{\Gamma(n+2)\Gamma(n+1-K)}{\Gamma(n+2-K)\Gamma(n+1)}$
$\displaystyle=\frac{n+1}{n+1-K}=\frac{1}{1-\lambda}.$ (48)

Putting (45), (47) and (48) together, we prove the result. ∎

###  A.5 Conditional p-value adjustment

###### Proof of Theorem 4.

Let $S_{i}=\hat{s}(X_{n+i})$ for $i=1,\ldots,n$ with
$F^{-}(t)=\mathbb{P}[S_{i}<t\mid\mathcal{D}^{\textnormal{train}}]$, and
$S_{(1)}\leq S_{(2)}\leq\ldots\leq S_{(n)}$ be the order statistics. Note that
here we condition on the training data in $\mathcal{D}^{\textnormal{train}}$,
which makes the $S_{i}$ are independent of another. Then it is easy to see
that

$(F^{-}(S_{(1)}),\ldots,F^{-}(S_{(n)}))\preceq(U_{(1)},\ldots,U_{(n)}),$

where $\preceq$ denotes the entry-wise stochastic dominance in the sense that
$(A_{1},\ldots,A_{n})\preceq(B_{1},\ldots,B_{n})$ iff

$\mathbb{P}[A_{1}\leq z_{1},\ldots,A_{n}\leq z_{n}]\geq\mathbb{P}[B_{1}\leq
z_{1},\ldots,B_{n}\leq
z_{n}],\quad\forall(z_{1},\ldots,z_{n})\in\mathbb{R}^{n}.$

When $F$ is continuous, the equality in distribution holds. Let
$\mathcal{E}_{n}$ denote the event on which $F^{-}(S_{(i)})\leq b_{i}$ for all
$i=1,\ldots,n$. Then

$\mathbb{P}[\mathcal{E}_{n}]\geq 1-\delta.$

Now we prove the following claim, which directly yields the theorem:

$\mathbb{P}\left[\hat{u}^{\textnormal{(ccv)}}(X_{2n+1})\leq
t\mid\mathcal{D}\right]\leq t,\quad\forall t\in[0,1],\quad\text{if
}\mathcal{E}_{n}\text{ occurs}.$ (49)

Note that the image of $\hat{u}^{\textnormal{(ccv)}}$ is
$\\{b_{1},\ldots,b_{n},1\\}$, it remains to prove (49) with
$t\in\\{b_{1},\ldots,b_{n},1\\}$. When $t=1$, it clearly holds. When
$t=b_{i}$,

$\hat{u}^{\textnormal{(ccv)}}(X_{2n+1})\leq
b_{i}\Longleftrightarrow\hat{u}^{\textnormal{(marg)}}(X_{2n+1})\leq\frac{i}{n+1}\Longleftrightarrow\hat{s}(X_{2n+1})<S_{(i)}.$

Thus,

$\mathbb{P}\left[\hat{u}^{\textnormal{(ccv)}}(X_{2n+1})\leq
b_{i}\mid\mathcal{D}\right]=\mathbb{P}\left[\hat{s}(X_{2n+1})<S_{(i)}\mid\mathcal{D}\right]=F^{-}(S_{(i)}).$

By definition of $\mathcal{E}_{n}$, (49) holds for all
$t\in\\{b_{1},\ldots,b_{n}\\}$.

∎

###  A.6 Simultaneous confidence bounds for the false positive rate

###### Proof of Proposition 3.

Note that $h(i/n)=b_{\lceil i+i/n\rceil}=b_{i+1}$ where we let $b_{n+1}=1$ for
convenience. Then, the event that $F(Z_{(i)})\leq h((i-1)/n)=b_{i}$ for all
$i\in\\{1,\ldots,n\\}$ occurs with probability at least $1-\delta$, where
$Z_{(1)}\leq\ldots\leq Z_{(n)}$ are the order statistics. Under this event,
for any $z\in[Z_{(i-1)},Z_{(i)})$, where we let $Z_{(0)}=\infty$ and
$Z_{(n+1)}=\infty$ for convenience, $\hat{F}_{n}(z)=(i-1)/n$ and thus

$F(z)\leq F(Z_{(i)})\leq b_{i}=h\left(\hat{F}_{n}(z)\right).$

On the other hand, if $h:[0,1]\rightarrow[0,1]$ is a function such that
$h(\hat{F}_{n}(z))$ is a uniform upper confidence band of $F$ for any CDF $F$,
then (10) holds with $b_{i}=h(i/n)$. ∎

##  Appendix B Power analysis of Fisher’s combination test

In this section, we investigate the effective $\alpha$-level of Fisher’s
combination test applied to calibration-conditional conformal p-values
$\hat{u}_{i}^{\textnormal{(ccv)}}\equiv
h\circ\hat{u}_{i}^{\textnormal{(marg)}}$, for different adjustment functions
$h$. To be self-contained, we summarize the three calibration-conditional
adjustments as follows.

  * •

Asymptotic adjustment:

$h^{\textnormal{a}}\left(\frac{i}{n+1}\right)=\min\left\\{\frac{i}{n}+c_{n}(\delta)\frac{\sqrt{i(n-i)}}{n\sqrt{n}},1\right\\},$
(50) $\text{where }c_{n}(\delta)=\frac{-\log[-\log(1-\delta)]+2\log\log
n+(1/2)\log\log\log n-(1/2)\log\pi}{\sqrt{2\log\log n}}.$

  * •

DKWM adjustment:

$h^{\textnormal{d}}\left(\frac{i}{n+1}\right)=\min\left\\{\frac{i}{n+1}+\sqrt{\frac{\log(2/\delta)}{2n}},1\right\\}.$

  * •

Simes adjustment:

$h^{\textnormal{s}}\left(\frac{n+1-i}{n+1}\right)=1-\delta^{1/k}\left(\frac{i\cdots(i-k+1)}{n\cdots(n-k+1)}\right)^{1/k},$

where $k$ is chosen to be $0.5n$ in the experiments.

Throughout the section, we will treat $\delta\in(0,1)$ as a constant that does
not vary with $n$ or $m$, though it is not hard to recover the dependence on
$\delta$ from the proofs. As a result, the big-O notation could hide constants
that solely depend on $\delta$.

###  B.1 Asymptotic adjustment

####  B.1.1 Monotonicity of $h^{\textnormal{a}}$

For notational convenience, we write $a_{n}$ for $c_{n}(\delta)/\sqrt{n}$
throughout the subsection. It should be kept in mind that $a_{n}$ depends on
$\delta$. We first prove that $h^{\textnormal{a}}$ is non-decreasing.

######  Proposition 5.

$h^{\textnormal{a}}$ is non-decreasing for any $n$ and $\delta$. Furthermore,

$h^{\textnormal{a}}\left(\frac{i}{n+1}\right)=1\text{ for any }i\geq
t_{n},\text{ where }t_{n}=\left\lceil\frac{n}{a_{n}^{2}+1}\right\rceil.$

###### Proof.

Let $g_{n}(x)=x+a_{n}\sqrt{x(1-x)}$. By definition,

$h^{\textnormal{a}}\left(\frac{i}{n+1}\right)=g_{n}\left(\frac{i}{n}\right).$

It is left to prove $\min\\{g(x),1\\}$ is non-decreasing on $[0,1]$. Taking
the derivative, we obtain that

$g_{n}^{\prime}(x)=1+a_{n}\frac{1-2x}{2\sqrt{x(1-x)}}.$

Clearly, $g_{n}^{\prime}(x)\geq 0$ for any $x\leq 1/2$. When $x>1/2$,

$\displaystyle g_{n}^{\prime}(x)>0$ $\displaystyle\Longleftrightarrow
2\sqrt{x(1-x)}\geq a_{n}(2x-1)$ $\displaystyle\Longleftrightarrow 4x(1-x)\geq
a_{n}^{2}(2x-1)^{2}$
$\displaystyle\Longleftrightarrow(a_{n}^{2}+1)(2x-1)^{2}\leq 1$
$\displaystyle\Longleftrightarrow
x\leq\frac{1}{2}\left(1+\sqrt{\frac{1}{a_{n}^{2}+1}}\right)\equiv d_{n}.$

As a result, $g_{n}(x)$ is increasing on $[0,d_{n}]$ and decreasing on
$[d_{n},1]$. On the other hand,

$g_{n}\left(\frac{1}{a_{n}^{2}+1}\right)=1,$

and

$\frac{1}{a_{n}^{2}+1}-d_{n}=\left(\sqrt{\frac{1}{a_{n}^{2}+1}}+\frac{1}{2}\right)\left(\sqrt{\frac{1}{a_{n}^{2}+1}}-1\right)<0.$

Therefore, $g_{n}(x)$ is increasing on $[0,1/(a_{n}^{2}+1)]$ with
$g_{n}(1/(a_{n}^{2}+1))=1$. On $[1/(a_{n}^{2}+1),1]$,

$g_{n}(x)\geq\min\\{g_{n}(1/(a_{n}^{2}+1)),g_{n}(1)\\}=1.$

Therefore, $\min\\{g_{n}(x),1\\}$ is increasing and, when $i\geq t_{n}$,

$h^{\textnormal{a}}\left(\frac{i}{n+1}\right)=1.$

∎

####  B.1.2 Mean of Fisher’s combination statistic

As a stepping stone to analyze the effective $\alpha$-level, we will first
compute the mean of Fisher’s combination statistic under the null, which
roughly measures the conservatism of the test.

######  Lemma 7.

Let $\int f(x)dx$ denote the indefinite integral of $f(x)$. Then

$\int\frac{dx}{\sqrt{x(1-x)}+a_{n}(1-x)}=\frac{2}{a_{n}^{2}+1}\left\\{\arcsin(\sqrt{x})-a_{n}\log\left(\sqrt{x}+a_{n}\sqrt{1-x}\right)\right\\}+\mathrm{Const}.$

###### Proof.

$\displaystyle\int\frac{dx}{\sqrt{x(1-x)}+a_{n}(1-x)}\stackrel{{\scriptstyle
x=\sin^{2}\theta}}{{=}}\int\frac{d\sin^{2}\theta}{\sin\theta\cos\theta+a_{n}\cos^{2}\theta}=2\int\frac{\sin\theta}{\sin\theta+a_{n}\cos\theta}d\theta.$

Let

$f_{1}(\theta)=\int\frac{\sin\theta}{\sin\theta+a_{n}\cos\theta}d\theta,\quad
f_{2}(\theta)=\int\frac{\cos\theta}{\sin\theta+a_{n}\cos\theta}d\theta.$

Then

$f_{1}(\theta)+a_{n}f_{2}(\theta)=\int 1d\theta=\theta+\mathrm{Const},$

and

$f_{2}(\theta)-a_{n}f_{1}(\theta)=\int\frac{\cos\theta-
a_{n}\sin\theta}{\sin\theta+a_{n}\cos\theta}d\theta=\log(\sin\theta+a_{n}\cos\theta)+\mathrm{Const}.$

Therefore,

$f_{1}(\theta)=\frac{1}{a_{n}^{2}+1}\left(\theta-
a_{n}\log(\sin\theta+a_{n}\cos\theta)\right)+\mathrm{Const},$

which implies the lemma. ∎

######  Theorem 8 (Part (a) of Theorem 5).

$\mathbb{E}_{H_{0}}[-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})]=1-\frac{\pi}{2}\frac{c_{n}(\delta)}{\sqrt{n}}+O\left(\frac{(\log
n)(\log\log n)}{n}\right).$

###### Proof.

Let $g_{n}(x)=x+a_{n}\sqrt{x(1-x)}$. Since $-\log(1)=0$,

$\mathbb{E}_{H_{0}}[-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})]=\frac{1}{n+1}\sum_{i=1}^{n+1}h^{\textnormal{a}}\left(\frac{i}{n+1}\right)=\frac{1}{n+1}\sum_{i=1}^{t_{n}-1}-\log\left\\{g_{n}\left(\frac{i}{n}\right)\right\\}.$

We have shown in the proof of Proposition 5 that $g_{n}(x)$ is increasing on
$[0,t_{n}/n]$. Thus,

$\frac{n+1}{n}\mathbb{E}_{H_{0}}[-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})]\in\left[\int_{1/n}^{t_{n}/n}-\log\\{g_{n}(x)\\}dx,\int_{0}^{(t_{n}-1)/n}-\log\\{g_{n}(x)\\}dx\right].$
(51)

Now we calculate the indefinite integral of $-\log\\{g_{n}(x)\\}$. Using
integration by parts,

$\displaystyle\int-\log\\{g_{n}(x)\\}dx$
$\displaystyle=-x\log\\{g_{n}(x)\\}+\int
x\frac{1+a_{n}(1-2x)/2\sqrt{x(1-x)}}{x+a_{n}\sqrt{x(1-x)}}dx$
$\displaystyle=-x\log\\{g_{n}(x)\\}+\int
x\frac{2\sqrt{x(1-x)}+a_{n}(1-2x)}{2x\sqrt{x(1-x)}+2a_{n}x(1-x)}dx$
$\displaystyle=-x\log\\{g_{n}(x)\\}+\int\frac{2\sqrt{x(1-x)}+a_{n}(1-2x)}{2\sqrt{x(1-x)}+2a_{n}(1-x)}dx$
$\displaystyle=-x\log\\{g_{n}(x)\\}+x-\frac{a_{n}}{2}\int\frac{1}{\sqrt{x(1-x)}+a_{n}(1-x)}dx$
$\displaystyle=-x\log\\{g_{n}(x)\\}+x-\frac{a_{n}}{a_{n}^{2}+1}\arcsin(\sqrt{x})+\frac{a_{n}^{2}}{a_{n}^{2}+1}\log\left(\sqrt{x}+a_{n}\sqrt{1-x}\right)+\mathrm{Const}\,\,\text{(Lemma
\ref{lem:integral})}$ $\displaystyle\equiv G_{n}(x)+\mathrm{Const}.$

Applying this to (51), by Newton-Leibniz formula,

$\int_{1/n}^{t_{n}/n}-\log\\{g_{n}(x)\\}dx=G_{n}(t_{n}/n)-G_{n}(1/n).$

By definition,

$1-\frac{t_{n}}{n}=O(a_{n}^{2}),\quad\frac{1}{n}=O\left(a_{n}^{2}\right).$

Then

$\displaystyle-\frac{t_{n}}{n}\log\left\\{\frac{t_{n}}{n}+a_{n}\sqrt{\frac{t_{n}}{n}}\left(1-\frac{t_{n}}{n}\right)\right\\}$
$\displaystyle=O\left(1-\frac{t_{n}}{n}-a_{n}\sqrt{\frac{t_{n}}{n}}\left(1-\frac{t_{n}}{n}\right)\right)$
$\displaystyle=O(a_{n}^{2})=O\left(\frac{(\log n)(\log\log n)}{n}\right),$

and

$-\frac{1}{n}\log\left\\{\frac{1}{n}+a_{n}\sqrt{\frac{n-1}{n^{2}}}\right\\}=O\left(\frac{(\log
n)(\log\log n)}{n}\right).$

Thus,

$-x\log\\{g_{n}(x)\\}\bigg{|}_{1/n}^{t_{n}/n}=O\left(a_{n}^{2}+\frac{(\log
n)(\log\log n)}{n}\right)=O\left(\frac{(\log n)(\log\log n)}{n}\right).$ (52)

Similarly,

$x\bigg{|}_{1/n}^{t_{n}/n}=1+O\left(a_{n}^{2}\right)=1+O\left(\frac{(\log
n)(\log\log n)}{n}\right).$ (53)

Next,

$\frac{a_{n}}{a_{n}^{2}+1}\arcsin(\sqrt{1/n})=O\left(\frac{a_{n}}{\sqrt{n}}\right)=O\left(\frac{(\log
n)(\log\log n)}{n}\right),$

and

$\displaystyle-\frac{a_{n}}{a_{n}^{2}+1}\arcsin(\sqrt{t_{n}/n})$
$\displaystyle=-\frac{a_{n}}{a_{n}^{2}+1}\left(\arcsin(1)-\int_{\sqrt{t_{n}/n}}^{1}\frac{dx}{\sqrt{1-x^{2}}}\right)$
$\displaystyle\in-\frac{\pi}{2}\frac{a_{n}}{a_{n}^{2}+1}+\frac{a_{n}}{a_{n}^{2}+1}\sqrt{1-\frac{t_{n}}{n}}\cdot\left[1,\frac{1}{1-t_{n}/n}\right]$
$\displaystyle=-\frac{\pi}{2}a_{n}+O(a_{n}^{2})=-\frac{\pi}{2}a_{n}+O\left(\frac{(\log
n)(\log\log n)}{n}\right).$

Thus,

$-\frac{a_{n}}{a_{n}^{2}+1}\arcsin(\sqrt{x})\bigg{|}_{1/n}^{t_{n}/n}=-\frac{\pi}{2}a_{n}+O\left(\frac{(\log
n)(\log\log n)}{n}\right).$ (54)

Finally,

$\displaystyle\frac{a_{n}^{2}}{a_{n}^{2}+1}\log\left(\sqrt{\frac{t_{n}}{n}}+a_{n}\sqrt{1-\frac{t_{n}}{n}}\right)=O\left(a_{n}^{2}\left\\{1-\sqrt{\frac{t_{n}}{n}}-a_{n}\sqrt{1-\frac{t_{n}}{n}}\right\\}\right)$
$\displaystyle=O(a_{n}^{4})=O\left(\frac{(\log n)(\log\log n)}{n}\right),$

and

$\displaystyle\frac{a_{n}^{2}}{a_{n}^{2}+1}\log\left(\sqrt{\frac{1}{n}}+a_{n}\sqrt{1-\frac{1}{n}}\right)=O(a_{n}^{2}\log
n)=O\left(\frac{(\log n)(\log\log n)}{n}\right).$

As a result,

$\frac{a_{n}^{2}}{a_{n}^{2}+1}\log\left(\sqrt{x}+a_{n}\sqrt{1-x}\right)\bigg{|}_{1/n}^{t_{n}/n}=O\left(\frac{(\log
n)(\log\log n)}{n}\right).$ (55)

Putting (52) - (55) together, we obtain that

$\int_{1/n}^{t_{n}/n}-\log\\{g_{n}(x)\\}dx=1-\frac{\pi}{2}a_{n}+O\left(\frac{(\log
n)(\log\log n)}{n}\right).$

Similarly,

$\int_{0}^{(t_{n}-1)/n}-\log\\{g_{n}(x)\\}dx=1-\frac{\pi}{2}a_{n}+O\left(\frac{(\log
n)(\log\log n)}{n}\right).$

The proof is then completed. ∎

####  B.1.3 Effective $\alpha$-level

The next result shows the distributional approximation for Fisher’s
combination statistic. The proof is involved and thus relegated to Section
B.1.4.

######  Lemma 8.

Under the global null, as $m,n\rightarrow\infty$,

$\displaystyle\bigg{|}\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-\log\left(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}}_{i}\right)\geq\sqrt{m}\sqrt{1+\frac{m}{n}}z_{1-\alpha}+m\left\\{1-\frac{\pi}{2}\frac{c_{n}(\delta)}{\sqrt{n}}\right\\}\right)-\alpha\bigg{|}=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}\right).$

We apply Lemma 8 to derive the effective $\alpha$-level in two practically
relevant regimes.

######  Theorem 9.

Assume that $m=\gamma n$ for some $\gamma\in(0,\infty)$. The type-I error of
Fisher’s combination test applied to
$h^{\textnormal{a}}\circ\hat{u}_{i}^{\textnormal{(marg)}}$’s

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{a}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)$
$\displaystyle=(1+o(1))\cdot
C(\alpha;\gamma)\exp\left\\{-\frac{\pi^{2}\gamma}{4(1+\gamma)}\log\log
n-\frac{\pi\sqrt{\gamma}z_{1-\alpha}}{\sqrt{2}(1+\gamma)}\sqrt{\log\log
n}-\frac{1}{2}\log\log\log n\right\\}$ $\displaystyle=\frac{1}{(\log
n)^{e(\gamma)(1+o(1))}},$

where

$C(\alpha;\gamma)=\sqrt{\frac{2(1+\gamma)\exp\\{-z_{1-\alpha}^{2}/(1+\gamma)\\}}{\pi^{2}\gamma}},\quad
e(\gamma)=\frac{\pi^{2}\gamma}{4(1+\gamma)}.$

######  Remark 6.

When $\gamma=1,\alpha=0.05$,

$C(\alpha;\gamma)\approx 0.32,\quad e(\gamma)\approx 1.23,$

and thus the type-I error is approximately

$0.32(\log n)^{-1.23}\cdot\exp\left\\{-1.83\sqrt{\log\log n}-0.5\log\log\log
n\right\\}.$

###### Proof.

Choose $\alpha_{n}\in(0,1)$ such that

$\sqrt{1+\gamma}z_{1-\alpha_{n}}-\frac{\pi\sqrt{\gamma}}{2}c_{n}(\delta)=\frac{\chi^{2}(2m;1-\alpha)-2m}{2\sqrt{m}}\triangleq
A_{m}.$

The standard CLT implies that

$A_{m}=z_{1-\alpha}+O\left(\frac{1}{\sqrt{m}}\right)=z_{1-\alpha}+O\left(\frac{1}{\sqrt{n}}\right).$
(56)

Then

$z_{1-\alpha_{n}}=\frac{A_{m}}{\sqrt{1+\gamma}}+\frac{\pi}{2}\sqrt{\frac{\gamma}{1+\gamma}}c_{n}(\delta)=\frac{z_{1-\alpha}}{\sqrt{1+\gamma}}+\frac{\pi}{\sqrt{2}}\sqrt{\frac{\gamma}{1+\gamma}}\sqrt{\log\log
n}+o(1).$ (57)

Since $z_{1-\alpha_{n}}\rightarrow\infty$,

$\displaystyle\alpha_{n}$
$\displaystyle=1-\Phi(z_{1-\alpha_{n}})=(1+o(1))\cdot\frac{1}{z_{1-\alpha_{n}}}\exp\left\\{-\frac{z_{1-\alpha_{n}}^{2}}{2}\right\\}$
$\displaystyle=(1+o(1))\cdot\frac{C(\alpha;\gamma)}{\sqrt{\log\log
n}}\exp\left\\{-\frac{\pi^{2}\gamma}{4(1+\gamma)}\log\log
n-\frac{\pi\sqrt{\gamma}z_{1-\alpha}}{\sqrt{2}(1+\gamma)}\sqrt{\log\log
n}\right\\}$ $\displaystyle=(1+o(1))\cdot
C(\alpha;\gamma)\exp\left\\{-\frac{\pi^{2}\gamma}{4(1+\gamma)}\log\log
n-\frac{\pi\sqrt{\gamma}z_{1-\alpha}}{\sqrt{2}(1+\gamma)}\sqrt{\log\log
n}-\frac{1}{2}\log\log\log n\right\\}.$

Clearly, $\alpha_{n}$ decays more slowly than any polynomial of $1/n$. By
Lemma 8,

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{a}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)$
$\displaystyle=(1+o(1))\cdot
C(\alpha;\gamma)\exp\left\\{-\frac{\pi^{2}\gamma}{4(1+\gamma)}\log\log
n-\frac{\pi\sqrt{\gamma}z_{1-\alpha}}{\sqrt{2}(1+\gamma)}\sqrt{\log\log
n}-\frac{1}{2}\log\log\log n\right\\}.$

∎

######  Theorem 10.

Assume that $m\rightarrow\infty$ and $m=o(n/\log\log n)$. The type-I error of
Fisher’s combination test applied to
$h^{\textnormal{a}}\circ\hat{u}_{i}^{\textnormal{(marg)}}$’s

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{a}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)=\alpha+o(1).$

###### Proof.

Adopting the notation utilized in the proof of Theorem 9, by (57),

$\displaystyle z_{1-\alpha_{n}}$
$\displaystyle=\frac{A_{m}}{\sqrt{1+m/n}}+\frac{\pi}{2}\sqrt{\frac{m/n}{1+m/n}}c_{n}(\delta)$
$\displaystyle=\frac{z_{1-\alpha}}{\sqrt{1+m/n}}+\frac{\pi}{\sqrt{2}}\sqrt{\frac{m/n}{1+m/n}}\sqrt{\log\log
n}(1+o(1))$ $\displaystyle=z_{1-\alpha}+o(1).$

This implies $\alpha_{n}=\alpha+o(1)$. By Lemma 8,

$\bigg{|}\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{a}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)-\alpha_{n}\bigg{|}=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}\right)=o(1).$

The proof is then completed. ∎

####  B.1.4 Proof of Lemma 8

######  Lemma 9.

There exist universal constants $C,c>0$ and a constant $C(\delta)>0$ that only
depends on $\delta$ such that, with probability $1-\exp\\{-c(\log n)^{2}\\}$,

$\sum_{k=1}^{2}\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\mid\mathcal{D}\right]-k\bigg{|}\leq\frac{C(\delta)\log^{6}n}{\sqrt{n}},$
(58)

and

$\sum_{k=3}^{4}\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\mid\mathcal{D}\right]\bigg{|}\leq
C.$ (59)

###### Proof.

Following [109], we call a random variable $V$ _sub-exponential_ with
parameters $(\nu,b)$ if

$\mathbb{E}[e^{\lambda(V-\mathbb{E}[V])}]\leq
e^{\nu^{2}\lambda^{2}/2},\quad\text{for all }\lambda<1/b.$

If $V\sim\mathrm{Exp}(1)$, then for any $\lambda<1/2$, it is easy to verify
that

$\mathbb{E}[e^{\lambda(V-\mathbb{E}[V])}]=\frac{e^{-\lambda}}{1-\lambda}\leq
e^{2\lambda^{2}}.$

Thus, $V$ is sub-exponential with parameters $(2,2)$.

Let $G(p)=-\log(h^{\textnormal{a}}(p))$. By (28) in the proof of Theorem 6,

$\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\mid\mathcal{D}\right]=\frac{\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)V_{i}}{\frac{1}{n+1}\sum_{i=1}^{n+1}V_{i}},$
(60)

where $V_{1},\ldots,V_{n+1}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\mathrm{Exp}(1)$. Let $\mathcal{E}_{n}$ denote the event that

$\displaystyle\sum_{k=0}^{4}\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)(V_{i}-1)\bigg{|}\leq\frac{\log^{6}n}{\sqrt{n}}.$
(61)

Note that

$G\left(\frac{i}{n+1}\right)\leq\log n,\quad i=1,\ldots,n+1.$

Then $G^{k}\left(\frac{i}{n+1}\right)(V_{i}-1)$ is exponential with parameters
$(2\log^{4}n,2\log^{4}n)$ for $k\leq 4$. By Bernstein’s inequality [109,
e.g.,],

$\mathbb{P}\left(\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)(V_{i}-1)\bigg{|}\geq
t\right)\leq
2\exp\left(-\min\left\\{\frac{(n+1)t^{2}}{8\log^{8}n},\frac{(n+1)t}{4\log^{4}n}\right\\}\right).$

Let $t=\frac{\log^{6}n}{5\sqrt{n}}$, we obtain that

$\mathbb{P}\left(\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)(V_{i}-1)\bigg{|}\geq\frac{\log^{6}n}{5\sqrt{n}}\right)\leq
2\exp\left\\{-O(\log^{2}n)\right\\}.$

Applying the union bound, there exists a universal constant $c>0$ such that

$\mathbb{P}\left(\mathcal{E}_{n}^{c}\right)\leq\exp\left\\{-c\log^{2}n\right\\}.$
(62)

Adopting the notation in Section B.1, we have

$\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)=\frac{1}{n+1}\sum_{i=1}^{t_{n}-1}\left(-\log\left\\{g_{n}\left(\frac{i}{n}\right)\right\\}\right)^{k}.$

We have shown in the proof of Proposition 5 that $g_{n}(x)\leq 1$ is
increasing on $[0,t_{n}/n]$. Then,

$\displaystyle\frac{1}{n}\sum_{i=1}^{t_{n}-1}\log^{2}\left\\{g_{n}\left(\frac{i}{n}\right)\right\\}\in\left[\int_{1/n}^{t_{n}/n}\log^{2}\\{g_{n}(x)\\}dx,\frac{\log^{2}\left\\{g_{n}(1/n)\right\\}}{n}+\int_{1/n}^{t_{n}/n}\log^{2}\\{g_{n}(x)\\}dx\right].$
(63)

For any $x\in(0,1)$,

$|\log(g_{n}(x))-\log(x)|\leq\frac{|g_{n}(x)-x|}{x}=a_{n}\sqrt{\frac{1-x}{x}}.$

Then

$\displaystyle\bigg{|}\int_{1/n}^{t_{n}/n}\log^{2}\\{g_{n}(x)\\}dx-\int_{1/n}^{t_{n}/n}\log^{2}xdx\bigg{|}$
$\displaystyle\leq 2a_{n}\int_{1/n}^{t_{n}/n}\sqrt{\frac{1-x}{x}}(-\log
x)dx+a_{n}^{2}\int_{1/n}^{t_{n}/n}\frac{1-x}{x}dx$ $\displaystyle\leq
2a_{n}\sqrt{\int_{1/n}^{t_{n}/n}\frac{1-x}{x}dx}\sqrt{\int_{1/n}^{t_{n}/n}\log^{2}xdx}+a_{n}^{2}\int_{1/n}^{t_{n}/n}\frac{1-x}{x}dx,$

where the last line uses the Cauchy-Schwarz inequality. Clearly,

$\int_{1/n}^{t_{n}/n}\frac{1-x}{x}dx=\log t_{n}-\frac{t_{n}-1}{n}\leq\log n,$

and

$\int_{1/n}^{t_{n}/n}\log^{2}xdx=x\log^{2}x-2x\log
x+2x\bigg{|}_{1/n}^{t_{n}/n}.$

Using the same reasoning as in (52),

$\int_{1/n}^{t_{n}/n}\log^{2}xdx=2+O(a_{n}^{2})=2+o_{\delta}\left(\frac{1}{\sqrt{n}}\right),$
(64)

where we use $o_{\delta}$ and $O_{\delta}$ herein to hide the dependence on
$\delta$. Therefore,

$\displaystyle\bigg{|}\int_{1/n}^{t_{n}/n}\log^{2}\\{g_{n}(x)\\}dx-\int_{1/n}^{t_{n}/n}\log^{2}xdx\bigg{|}=O(a_{n}\sqrt{\log
n}+a_{n}^{2}\log n)=O_{\delta}\left(\frac{\log^{6}n}{\sqrt{n}}\right).$

Putting pieces together with (63), we have

$\displaystyle\int_{1/n}^{t_{n}/n}\log^{2}\\{g_{n}(x)\\}dx=2+O_{\delta}\left(\frac{\log^{6}n}{\sqrt{n}}\right).$

On the other hand, by Theorem 8,

$\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)-1\bigg{|}=O\left(\frac{\sqrt{\log\log
n}}{\sqrt{n}}\right)=O\left(\frac{\log^{6}n}{\sqrt{n}}\right).$

As a result, there exists a constant $C_{1}(\delta)$ that only depends on
$\delta$ such that

$\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)-2\bigg{|}+\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)-1\bigg{|}\leq
C_{1}(\delta)\frac{\log^{6}n}{\sqrt{n}}.$ (65)

Putting (60), (61), and (65) together, on the event $\mathcal{E}_{n}$, for
$k=1,2$,

$\mathbb{E}_{H_{0}}\left[\left(-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})\right)^{k}\mid\mathcal{D}\right]\in\left[\frac{k-C_{1}(\delta)\log^{6}n/\sqrt{n}}{1+\log^{6}n/\sqrt{n}},\frac{k+C_{1}(\delta)\log^{6}n/\sqrt{n}}{1-\log^{6}n/\sqrt{n}}\right].$

As a result, for sufficiently large $n$,

$\sum_{k=1}^{2}\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\mid\mathcal{D}\right]-k\bigg{|}\leq
2(C_{1}(\delta)+2)\frac{\log^{6}n}{\sqrt{n}}.$

This completes the proof of (58).

To prove (59), note that

$\displaystyle\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)=\frac{1}{n+1}\sum_{i=1}^{t_{n}-1}\left(-\log\left\\{g_{n}\left(\frac{i}{n}\right)\right\\}\right)^{k}$
$\displaystyle\leq\int_{0}^{t_{n}/n}\left(-\log
g_{n}(x)\right)^{k}dx\leq\int_{0}^{1}\left(-\log x\right)^{k}dx=k!.$

By (60) and (61), on the event $\mathcal{E}_{n}$, for $k=3,4$,

$\mathbb{E}_{H_{0}}\left[\left(-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})\right)^{k}\mid\mathcal{D}\right]\leq\frac{k!+\log^{6}n/\sqrt{n}}{1-\log^{6}n/\sqrt{n}}.$

This proves (59). ∎

######  Lemma 10.

There exist a universal constant $C>0$ and a constant $C(\delta)>0$ that only
depends on $\delta$ such that,

$\sum_{k=1}^{2}\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\right]-k\bigg{|}\leq\frac{C(\delta)\log^{6}n}{\sqrt{n}},$
(66)

and

$\sum_{k=3}^{4}\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\right]\bigg{|}\leq
C.$ (67)

###### Proof.

Let $\mathcal{E}_{n}$ be the event defined in Lemma 9. By Lemma 9,
$\mathbb{P}(\mathcal{E}_{n}^{c})\leq\exp\\{-c(\log n)^{2}\\}$. On
$\mathcal{E}_{n}^{c}$.

$\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\mid\mathcal{D}\right]\leq(\log
n)^{k}.$

Thus, for $k\leq 4$,

$\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}I(\mathcal{E}^{c})\right]\leq\exp\\{-c(\log
n)^{2}\\}(\log n)^{4}=O\left(\frac{1}{\sqrt{n}}\right).$

By the triangle inequality, for $k=1,2$,

$\displaystyle\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}-k\right]\bigg{|}$
$\displaystyle\leq\bigg{|}\mathbb{E}_{H_{0}}\left[\left(|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}-k\right)I(\mathcal{E}_{n})\right]\bigg{|}+k\mathbb{P}(\mathcal{E}_{n}^{c})+\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}I(\mathcal{E}^{c})\right]\bigg{|}$
$\displaystyle=\mathbb{E}\left\\{\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}-k\mid\mathcal{D}\right]\bigg{|}I(\mathcal{E}_{n})\right\\}+O\left(\frac{1}{\sqrt{n}}\right)$
$\displaystyle\leq\frac{C(\delta)\log^{6}n}{\sqrt{n}}+O\left(\frac{1}{\sqrt{n}}\right)$

where the last line uses (58). Using a similar argument, we can also prove
(67). ∎

######  Lemma 11.

For any $\mu\in\mathbb{R}$ and $\sigma^{2}>0$,

$d_{K}(N(\mu,\sigma^{2}),N(0,1))\leq|\mu|+|1/\sigma-1|\cdot\max\\{1,\sigma\\}.$

###### Proof.

Let $W\sim N(0,1)$. By the triangle inequality,

$\displaystyle d_{K}(N(\mu,\sigma^{2}),N(0,1))$ $\displaystyle\leq
d_{K}(N(\mu,\sigma^{2}),N(\mu,1))+d_{K}(N(\mu,1),N(0,1))$
$\displaystyle=d_{K}(N(0,\sigma^{2}),N(0,1))+d_{K}(N(\mu,1),N(0,1))$
$\displaystyle=\sup_{x}|\Phi(x/\sigma)-\Phi(x)|+\sup_{x}|\Phi(x-\mu)-\Phi(x)|$

For any $x\in\mathbb{R}$,

$\displaystyle|\Phi(x/\sigma)-\Phi(x)|$
$\displaystyle\leq\bigg{|}\frac{1}{\sigma}-1\bigg{|}\cdot|x|\cdot\frac{1}{\sqrt{2\pi}}\exp\left\\{-\frac{x^{2}}{2\max\\{1,\sigma\\}^{2}}\right\\}$
$\displaystyle\leq\bigg{|}\frac{1}{\sigma}-1\bigg{|}\cdot\max\\{1,\sigma\\}\cdot\sup_{y\in\mathbb{R}}\frac{1}{\sqrt{2\pi}}|y|\exp\left\\{-\frac{y^{2}}{2}\right\\}$
$\displaystyle\leq\bigg{|}\frac{1}{\sigma}-1\bigg{|}\cdot\max\\{1,\sigma\\}.$

Similarly,

$|\Phi(x-\mu)-\Phi(x)|\leq|\mu|\cdot\sup_{y\in\mathbb{R}}\frac{1}{\sqrt{2\pi}}\exp\left\\{-\frac{y^{2}}{2}\right\\}\leq|\mu|.$

∎

######  Lemma 12.

[[110], Theorem 3.2 with $D=1$] Let $X_{1},X_{2},\ldots,X_{n}$ be independent
random variables such that $\mathbb{E}[X_{j}]=0$ and
$\mathbb{E}[X_{j}^{4}]<\infty$, for all $j$. Write
$B_{n}=\sum_{j}\textnormal{Var}[X_{j}]$. Then

$d_{W}\left(\mathcal{L}\left(\frac{1}{\sqrt{B_{n}}}\sum_{j=1}^{n}X_{j}\right),N(0,1)\right)\leq\frac{1}{B_{n}^{3/2}}\sum_{j=1}^{n}\mathbb{E}[|X_{j}|^{3}]+\frac{\sqrt{28}}{\sqrt{\pi}B_{n}}\sqrt{\sum_{j=1}^{n}\mathbb{E}[X_{j}^{4}]}.$

###### Proof of Lemma 8.

Write $p_{i}$ for $\hat{u}^{\textnormal{(marg)}}_{i}$. Throughout the proof we
suppress $H_{0}$ from the expectation $\mathbb{E}_{H_{0}}$ and
$\mathbb{P}_{H_{0}}$ because we will only consider the global null. This proof
refines that of Theorem 6. Let $p_{i}=\hat{u}_{i}^{\textnormal{(marg)}}$,
$G(p)=-\log(h^{\textnormal{a}}(p))$, and $\mathcal{E}_{n}$ be the event
defined in (61). By Lemma 9, on the event $\mathcal{E}_{n}$,

$\sum_{k=1}^{2}\bigg{|}\mathbb{E}[G^{k}(p_{i})\mid\mathcal{D}]-k\bigg{|}\leq\frac{C(\delta)\log^{6}n}{\sqrt{n}},\quad\text{and}\quad\sum_{k=3}^{4}\bigg{|}\mathbb{E}[G^{k}(p_{i})\mid\mathcal{D}]\bigg{|}\leq
C.$

Recalling that we treat $\delta$ as a constant and ignore all terms that
solely depend on $\delta$ in the big-O notation, we will simply write $C$ for
$C(\delta)$ for the rest of the proof.

Analogous to the proof of Theorem 6, we define

$W_{m}=\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\left\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\right\\},\quad\tilde{W}_{n}=\sqrt{n+1}\left\\{\mathbb{E}[G(p_{i})\mid\mathcal{D}]-\mathbb{E}[G(p_{i})]\right\\}.$

By Lemma 2 with $g(x)=|x|$,

$\displaystyle
d_{K}\left(\mathcal{L}\left(\frac{W_{m}}{\sqrt{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}}\mid\mathcal{D}\right),N(0,1)\right)$
$\displaystyle\leq\frac{A}{\sqrt{m}}\frac{\mathbb{E}\left[|G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]|^{3}\right]}{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]^{3/2}}$
$\displaystyle\leq\frac{8A}{\sqrt{m}}\frac{\mathbb{E}\left[|G(p_{i})|^{3}\mid\mathcal{D}\right]}{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]^{3/2}},$

where $A$ is a universal constant. By definition of $\mathcal{E}_{n}$,

$\bigg{|}\textnormal{Var}[G(p_{i})\mid\mathcal{D}]-1\bigg{|}\leq\frac{2C\log^{6}n}{\sqrt{n}},\quad\text{on
the event }\mathcal{E}_{n}.$ (68)

When $n$ is sufficiently large,

$d_{K}\left(\mathcal{L}\left(\frac{W_{m}}{\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}\mid\mathcal{D}\right),N(0,1)\right)\leq\frac{1}{\sqrt{m}}\cdot\frac{8CA}{\left(1-\frac{2C\log^{6}n}{\sqrt{n}}\right)^{3/2}}\leq\frac{16CA}{\sqrt{m}},\quad\text{on
the event }\mathcal{E}_{n}.$

The scale-invariance of the Kolmogorov distance then implies

$d_{K}\left(\mathcal{L}\left(W_{m}\mid\mathcal{D}\right),N(0,\textnormal{Var}[G(p_{i})\mid\mathcal{D}])\right)\leq\frac{16CA}{\sqrt{m}},\quad\text{on
the event }\mathcal{E}_{n}.$

By (68), Lemma 11 and the triangle inequality, for a sufficiently large $n$,

$d_{K}\left(\mathcal{L}\left(W_{m}\mid\mathcal{D}\right),N(0,1)\right)\leq\frac{16CA}{\sqrt{m}}+\frac{6C\log^{6}n}{\sqrt{n}},\quad\text{on
the event }\mathcal{E}_{n}.$ (69)

Since $\tilde{W}_{n}$ is a function of $\mathcal{D}$, for any
$t\in\mathbb{R}$,

$\bigg{|}\mathbb{P}\left(W_{m}+\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\geq
t\mid\mathcal{D}\right)-\bar{\Phi}\left(t-\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\right)\bigg{|}\leq\frac{16CA}{\sqrt{m}}+\frac{6C\log^{6}n}{\sqrt{n}},\quad\text{on
the event }\mathcal{E}_{n}.$

By (62), when $n$ is sufficiently large,

$\displaystyle\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\left(W_{m}+\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\geq
t\right)-\mathbb{E}\left[\bar{\Phi}\left(t-\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\right)\right]\bigg{|}$
$\displaystyle\leq\frac{16CA}{\sqrt{m}}+\frac{6C\log^{6}n}{\sqrt{n}}+\mathbb{P}(\mathcal{E}_{n}^{c})=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}\right).$
(70)

Recall from (60) with $k=1$ that

$\tilde{W}_{n}=\frac{(n+1)^{-1/2}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(p_{i})]\right\\}V_{j}}{\frac{1}{n+1}\sum_{j=1}^{n+1}V_{j}}\triangleq\frac{\tilde{W}_{1n}}{\tilde{W}_{2n}}.$

Let

$B_{n}=\frac{1}{n+1}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(p_{i})]\right\\}^{2}.$

Since
$\mathbb{E}[G(p_{i})]=\frac{1}{n+1}\sum_{j=1}^{n+1}G\left(\frac{j}{n+1}\right)$,

$B_{n}=\mathbb{E}\left[|-\log(h^{\textnormal{a}}(p_{i}))|^{2}\right]-\left(\mathbb{E}\left[|-\log(h^{\textnormal{a}}(p_{i}))|\right]\right)^{2}.$

By (58) in Lemma 10,

$|B_{n}-1|\leq
2+\frac{C\log^{6}n}{\sqrt{n}}-\left(1-\frac{C\log^{6}n}{\sqrt{n}}\right)^{2}\leq
1+\frac{3C\log^{6}n}{\sqrt{n}}.$

Similarly, Lemma 10 implies that

$\sum_{k=3}^{4}\frac{1}{n+1}\sum_{j=1}^{n}\bigg{|}G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(p_{i})]\bigg{|}^{k}\leq\sum_{k=3}^{4}2^{k}\frac{1}{n+1}\sum_{j=1}^{n}\bigg{|}G\left(\frac{j}{n+1}\right)\bigg{|}^{k}=O(1),$

where the first step applies Jensen’s inequality that

$\Bigg{|}\frac{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(p_{i})]}{2}\Bigg{|}^{k}\leq\frac{1}{2}\left(\bigg{|}G\left(\frac{j}{n+1}\right)\bigg{|}^{k}+|\mathbb{E}[G(p_{i})]|^{k}\right),$

and

$|\mathbb{E}[G(p_{i})]|^{k}\leq\bigg{|}\frac{1}{n+1}\sum_{j=1}^{n+1}G\left(\frac{j}{n+1}\right)\bigg{|}^{k}\leq\frac{1}{n+1}\sum_{j=1}^{n+1}\bigg{|}G\left(\frac{j}{n+1}\right)\bigg{|}^{k}.$

By Lemma 12,

$\displaystyle
d_{W}\left(\mathcal{L}\left(\frac{\tilde{W}_{1n}}{\sqrt{B_{n}}}\right),N(0,1)\right)$
$\displaystyle\leq\frac{\mathbb{E}[V_{1}^{3}]}{(n+1)^{3/2}B_{n}^{3/2}}\sum_{j=1}^{n}\bigg{|}G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(p_{i})]\bigg{|}^{3}+\frac{\sqrt{28}\mathbb{E}[V_{1}^{4}]}{\sqrt{\pi}(n+1)B_{n}}\sqrt{\sum_{j=1}^{n}\bigg{|}G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(p_{i})]\bigg{|}^{4}}$
$\displaystyle=O\left(\frac{1}{\sqrt{n}}\right).$

As a result,

$d_{W}\left(\mathcal{L}(\tilde{W}_{1n}),N(0,B_{n})\right)=\sqrt{B_{n}}\cdot
d_{W}\left(\mathcal{L}\left(\frac{\tilde{W}_{1n}}{\sqrt{B_{n}}}\right),N(0,1)\right)=O\left(\frac{1}{\sqrt{n}}\right).$

Let $Z$ denotes a standard normal random variable. Using the coupling
definition of the Wasserstein distance,

$d_{W}(N(0,B_{n}),N(0,1))\leq\mathbb{E}|\sqrt{B_{n}}Z-Z|=|\sqrt{B_{n}}-1|\cdot\mathbb{E}|Z|=O(B_{n}-1)=O\left(\frac{\log^{6}n}{\sqrt{n}}\right).$

By the triangle inequality,

$d_{W}\left(\mathcal{L}(\tilde{W}_{1n}),N(0,1)\right)\leq
d_{W}\left(\mathcal{L}(\tilde{W}_{1n}),N(0,B_{n})\right)+d_{W}\left(N(0,B_{n}),N(0,1)\right)=O\left(\frac{\log^{6}n}{\sqrt{n}}\right).$
(71)

On the other hand, using the coupling definition of Wasserstein distance
again,

$\displaystyle d_{W}\left(\tilde{W}_{n},\tilde{W}_{1n}\right)$
$\displaystyle\leq\mathbb{E}\left|\frac{\tilde{W}_{1n}}{\tilde{W}_{2n}}-\tilde{W}_{1n}\right|=\mathbb{E}\left[|\tilde{W}_{1n}|\cdot\left|\frac{1}{\tilde{W}_{2n}}-1\right|\right].$
(72)

Since $V_{i}\sim\mathrm{Exp}(1)\sim\Gamma(1,1)$,

$(n+1)\tilde{W}_{2n}\sim\Gamma(n+1,1).$

Using the properties of inverse-Gamma distributions,

$\mathbb{E}\left[\frac{1}{\tilde{W}_{2n}}\right]=1+\frac{1}{n},\quad\textnormal{Var}\left[\frac{1}{\tilde{W}_{2n}}\right]=\frac{(n+1)^{2}}{n^{2}(n-1)}.$

By the triangle inequality and Cauchy-Schwarz inequality,

$\displaystyle\mathbb{E}\left[|\tilde{W}_{1n}|\cdot\left|\frac{1}{\tilde{W}_{2n}}-1\right|\right]$
$\displaystyle\leq\frac{1}{n}\mathbb{E}\left[|\tilde{W}_{1n}|\right]+\mathbb{E}\left[|\tilde{W}_{1n}|\cdot\left|\frac{1}{\tilde{W}_{2n}}-\mathbb{E}\left[\frac{1}{\tilde{W}_{2n}}\right]\right|\right]$
$\displaystyle\leq\frac{1}{n}\sqrt{\mathbb{E}[\tilde{W}_{1n}^{2}]}+\sqrt{\mathbb{E}[\tilde{W}_{1n}^{2}]}\cdot\sqrt{\textnormal{Var}\left[\frac{1}{\tilde{W}_{2n}}\right]}$
$\displaystyle=O\left(\frac{\sqrt{\mathbb{E}[\tilde{W}_{1n}^{2}]}}{\sqrt{n}}\right).$

Note that

$\mathbb{E}[\tilde{W}_{1n}]=(n+1)^{-1/2}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(p_{i})]\right\\}=0,$

and by Lemma 10,

$\textnormal{Var}[\tilde{W}_{1n}]=\frac{1}{n+1}\sum_{j=1}^{n+1}\left\\{G\left(\frac{j}{n+1}\right)-\mathbb{E}[G(p_{i})]\right\\}^{2}\leq\frac{1}{n+1}\sum_{j=1}^{n+1}G^{2}\left(\frac{j}{n+1}\right)=O(1).$

Thus,

$\mathbb{E}\left[|\tilde{W}_{1n}|\cdot\left|\frac{1}{\tilde{W}_{2n}}-1\right|\right]=O\left(\frac{\sqrt{\textnormal{Var}[\tilde{W}_{1n}]}}{\sqrt{n}}\right)=O\left(\frac{1}{\sqrt{n}}\right).$

By the triangle inequality, (71), and (72)

$d_{W}\left(\tilde{W}_{n},N(0,1)\right)\leq
d_{W}\left(\tilde{W}_{n},\tilde{W}_{1n}\right)+d_{W}\left(\tilde{W}_{1n},N(0,1)\right)=O\left(\frac{\log^{6}n}{\sqrt{n}}\right).$
(73)

Note that

$|\bar{\Phi}^{\prime}(x)|=\frac{1}{\sqrt{2\pi}}\exp\left\\{-\frac{x^{2}}{2}\right\\}\leq
1.$

Again, Let $Z$ denotes a standard normal random variable. Using the
Kantorovich-Rubinstein dual representation of the Wasserstein’s distance,

$\sup_{t\in\mathbb{R}}\bigg{|}\bar{\Phi}\left(t-\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\right)-\bar{\Phi}\left(t-\sqrt{\frac{m}{n+1}}Z\right)\bigg{|}\leq\sqrt{\frac{m}{n+1}}d_{W}(\tilde{W}_{n},Z)=O\left(\frac{\sqrt{m}\log^{6}n}{n}\right).$
(74)

Similar to the last step in the proof of Theorem 6, letting $\tilde{Z}$ denote
a standard normal random variable that is independent of $Z$,

$\mathbb{E}\left[\bar{\Phi}\left(t-\sqrt{\frac{m}{n+1}}Z\right)\right]=\mathbb{P}\left(\sqrt{\frac{m}{n+1}}Z+\tilde{Z}\geq
t\right)=\mathbb{P}\left(N\left(0,1+\frac{m}{n+1}\right)\geq
t\right)=\bar{\Phi}\left(\frac{t}{\sqrt{1+\frac{m}{n+1}}}\right).$ (75)

Combining (70), (74), and (75),

$\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\left(W_{m}+\sqrt{\frac{m}{n+1}}\tilde{W}_{n}\geq
t\right)-\bar{\Phi}\left(\frac{t}{\sqrt{1+\frac{m}{n+1}}}\right)\bigg{|}=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}\right).$
(76)

Note that
$W_{m}+\sqrt{\frac{m}{n+1}}\tilde{W}_{n}=(1/\sqrt{m})\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})]\\}$.
Let

$t=\sqrt{1+\frac{m}{n}}z_{1-\alpha}+\sqrt{m}\left\\{1-\frac{\pi}{2}\frac{c_{n}(\delta)}{\sqrt{n}}-\mathbb{E}[G(p_{i})]\right\\}.$

Then (76) implies that

$\sup_{\alpha\in(0,1)}\bigg{|}\mathbb{P}\left(\sum_{i=1}^{m}G(p_{i})\geq\sqrt{m}\sqrt{1+\frac{m}{n}}z_{1-\alpha}+m\left\\{1-\frac{\pi}{2}\frac{c_{n}(\delta)}{\sqrt{n}}\right\\}\right)-\bar{\Phi}\left(z_{1-\alpha}+b_{m,n}\right)\bigg{|}=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}\right),$

where

$b_{m,n}=\left(\sqrt{\frac{1+m/n}{1+m/(n+1)}}-1\right)z_{1-\alpha}+\sqrt{\frac{m(n+1)}{n+m+1}}\left\\{1-\frac{\pi}{2}\frac{c_{n}(\delta)}{\sqrt{n}}-\mathbb{E}[G(p_{i})]\right\\}.$

As shown in the previous steps, $\bar{\Phi}$ is $1$-Lipschitz. Thus,

$\sup_{\alpha\in(0,1)}\bigg{|}\mathbb{P}\left(\sum_{i=1}^{m}G(p_{i})\geq\sqrt{m}\sqrt{1+\frac{m}{n}}z_{1-\alpha}+m\left\\{1-\frac{\pi}{2}\frac{c_{n}(\delta)}{\sqrt{n}}\right\\}\right)-\alpha\bigg{|}=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}+b_{m,n}\right).$

By Theorem 8,

$\bigg{|}1-\frac{\pi}{2}\frac{c_{n}(\delta)}{\sqrt{n}}-\mathbb{E}[G(p_{i})]\bigg{|}=O\left(\frac{(\log
n)(\log\log n)}{n}\right).$

Therefore,

$b_{m,n}=O\left(\frac{1}{n}+\sqrt{\frac{m}{m+n}}\frac{(\log n)(\log\log
n)}{\sqrt{n}}\right)=O\left(\frac{\log^{6}n}{\sqrt{n}}\right).$

The proof is then completed. ∎

###  B.2 DKWM adjustment

####  B.2.1 Mean of Fisher’s combination statistic

For notational convenience, let

$b_{n}=\sqrt{\frac{\log(2/\delta)}{2n}}.$

It should be kept in mind that $b_{n}$ depends on $\delta$.

######  Theorem 11 (Part (b) of Theorem 5).

$\mathbb{E}_{H_{0}}[-\log(h^{\textnormal{d}}\circ\hat{u}^{\textnormal{(marg)}})]=1-b_{n}\log\left(\frac{e}{b_{n}}\right)+O\left(\frac{\log
n}{n}\right).$

###### Proof.

For notational convenience, let $t_{n}=\lfloor(n+1)(1-b_{n})\rfloor$. Since
the mapping $x\mapsto-\log(x+b_{n})$ is monotone decreasing,

$\displaystyle\mathbb{E}_{H_{0}}[-\log(h^{\textnormal{d}}\circ\hat{u}^{\textnormal{(marg)}})]$
$\displaystyle=\frac{1}{n+1}\sum_{i=1}^{n+1}-\log\left(\min\left\\{\frac{i}{n+1}+b_{n},1\right\\}\right)$
$\displaystyle=\frac{1}{n+1}\sum_{i=1}^{t_{n}}-\log\left(\frac{i}{n+1}+b_{n}\right)$
$\displaystyle\in\left[\int_{b_{n}+1/(n+1)}^{b_{n}+t_{n}/(n+1)}(-\log
x)dx,\int_{b_{n}}^{b_{n}+t_{n}/(n+1)}(-\log x)dx\right].$ (77)

Note that the indefinite integral of $(-\log x)$ is

$\int(-\log x)dx=-x\log x+x\triangleq h_{1}(x).$

It is easy to see that

$h_{1}\left(b_{n}\right)=b_{n}\log\left(\frac{e}{b_{n}}\right),$
$h_{1}\left(b_{n}+\frac{1}{n+1}\right)=h_{1}(b_{n})+O\left(\frac{h_{1}^{\prime}(b_{n})}{n+1}\right)=b_{n}\log\left(\frac{e}{b_{n}}\right)+O\left(\frac{\log
n}{n}\right),$

and

$\bigg{|}h_{1}\left(b_{n}+\frac{t_{n}}{n+1}\right)-1\bigg{|}=O\left(1-b_{n}-\frac{t_{n}}{n+1}\right)=O\left(\frac{1}{n}\right).$

By Newton-Leibniz formula,

$\int_{b_{n}+1/(n+1)}^{b_{n}+t_{n}/(n+1)}(-\log
x)dx,\int_{b_{n}}^{b_{n}+t_{n}/(n+1)}(-\log
x)dx=1-b_{n}\log\left(\frac{e}{b_{n}}\right)+O\left(\frac{\log n}{n}\right).$

The proof is then closed by (77). ∎

####  B.2.2 Conditional moments of the adjusted p-values

######  Lemma 13.

There exist universal constants $C,c>0$ and a constant $C(\delta)>0$ that only
depends on $\delta$ such that, with probability $1-\exp\\{-c(\log n)^{2}\\}$,

$\sum_{k=1}^{2}\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{d}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\mid\mathcal{D}\right]-k\bigg{|}\leq\frac{C(\delta)\log^{6}n}{\sqrt{n}},$

and

$\sum_{k=3}^{4}\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{d}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\mid\mathcal{D}\right]\bigg{|}\leq
C.$

###### Proof.

Let $G(p)=-\log(h^{\textnormal{d}}(p))$. Then

$G\left(\frac{i}{n+1}\right)\leq-\log\left(\frac{1}{n+1}+\sqrt{\frac{\log(2/\delta)}{2n}}\right)\leq\log
n,$ (78)

where we use the fact that

$\sqrt{\frac{\log(2/\delta)}{2n}}\geq\sqrt{\frac{\log
2}{2n}}\geq\frac{1}{n(n+1)}.$

Using the same argument as in the proof of Lemma 9,

$\mathbb{P}\left(\mathcal{E}_{n}^{c}\right)\leq\exp\left\\{-c\log^{2}n\right\\},$

where $\mathcal{E}_{n}$ denotes the event that

$\sum_{k=0}^{4}\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)(V_{i}-1)\bigg{|}\leq\frac{\log^{6}n}{\sqrt{n}}.$

Adopting the notation in Theorem 11, for any $k\geq 2$,

$\displaystyle\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)=\frac{1}{n+1}\sum_{i=1}^{t_{n}}\left(-\log\left\\{\frac{i}{n+1}+b_{n}\right\\}\right)^{k}.$

Since the mapping $x\mapsto\log^{2}(x+b_{n})$ is decreasing,

$\displaystyle\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)$
$\displaystyle\in\left[\int_{1/(n+1)}^{t_{n}/(n+1)}\log^{2}(x+b_{n})dx,\int_{0}^{t_{n}/(n+1)}\log^{2}(x+b_{n})dx\right]$
$\displaystyle\in\left[\int_{b_{n}+1/(n+1)}^{b_{n}+t_{n}/(n+1)}\log^{2}xdx,\int_{b_{n}}^{b_{n}+t_{n}/(n+1)}\log^{2}xdx\right]$

Note that the indefinite integral of $\log^{2}x$ is

$\int\log^{2}xdx=x\log^{2}x-2x\log x+2x\triangleq h_{2}(x).$

It is easy to see that

$h_{2}\left(b_{n}\right),h_{2}\left(b_{n}+\frac{1}{n+1}\right)=O_{\delta}\left(\frac{\log^{2}n}{\sqrt{n}}\right),$

where we use $O_{\delta}$ herein to hide the dependence on $\delta$, and

$\bigg{|}h_{2}\left(b_{n}+\frac{t_{n}}{n+1}\right)-2\bigg{|}=O\left(1-b_{n}-\frac{t_{n}}{n+1}\right)=O\left(\frac{1}{n}\right).$

By Newton-Leibniz formula,

$\int_{b_{n}+1/(n+1)}^{b_{n}+t_{n}/(n+1)}\log^{2}xdx,\int_{b_{n}}^{b_{n}+t_{n}/(n+1)}\log^{2}xdx=2+O_{\delta}\left(\frac{\log^{2}n}{\sqrt{n}}\right).$

This implies

$\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)-2\bigg{|}=O_{\delta}\left(\frac{\log^{2}n}{\sqrt{n}}\right).$

We have shown in Theorem 11 that

$\bigg{|}\frac{1}{n+1}\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)-1\bigg{|}=O_{\delta}\left(\frac{\log
n}{\sqrt{n}}\right).$

Analogous to the proof of Lemma 9, on the event $\mathcal{E}_{n}$,

$\sum_{k=1}^{2}\bigg{|}\mathbb{E}_{H_{0}}\left[|-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})|^{k}\mid\mathcal{D}\right]-k\bigg{|}=O_{\delta}\left(\frac{\log^{2}n}{\sqrt{n}}\right)=O_{\delta}\left(\frac{\log^{6}n}{\sqrt{n}}\right).$

To prove the bound for higher-order moments, note that

$\displaystyle\frac{1}{n+1}\sum_{i=1}^{n+1}G^{k}\left(\frac{i}{n+1}\right)$
$\displaystyle=\frac{1}{n+1}\sum_{i=1}^{t_{n}}\left(-\log\left\\{\frac{i}{n+1}+b_{n}\right\\}\right)^{k}\leq\int_{0}^{1}(-\log
x)^{k}dx=k!.$

By (60) and the definition of $\mathcal{E}_{n}$, on the event
$\mathcal{E}_{n}$, for $k=3,4$,

$\mathbb{E}\left[\left(-\log(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})\right)^{k}\mid\mathcal{D}\right]\leq\frac{k!+\log^{6}n/\sqrt{n}}{1-\log^{6}n/\sqrt{n}}=O(1).$

∎

####  B.2.3 Tail approximation for Fisher’s combination statistic

######  Lemma 14.

Under the global null, there exists a universal constant $C>0$ and
$n_{0}(\delta)$ that only depends on $\delta$, such that for any $n\geq
n_{0}(\delta)$ and $t>0$,

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}\left\\{-\log\left(h^{\textnormal{d}}\circ\hat{u}^{\textnormal{(marg)}}_{i}\right)-\mathbb{E}\left[-\log\left(h^{\textnormal{d}}\circ\hat{u}^{\textnormal{(marg)}}\right)\right]\right\\}\geq
t\right)$ $\displaystyle\leq\exp\left\\{-C(\log
n)^{2}-C\min\left\\{\frac{n}{m},1\right\\}\min\left\\{\frac{t^{2}}{m},\frac{t}{\log
n}\right\\}\right\\}.$

###### Proof.

Let $G(p)=-\log(h^{\textnormal{d}}(p))$ and write $p_{i}$ for
$\hat{u}^{\textnormal{(marg)}}_{i}$. Throughout the proof we suppress $H_{0}$
from the expectation $\mathbb{E}_{H_{0}}$ and $\mathbb{P}_{H_{0}}$ because we
will only consider the global null. By (60) , we can write

$\mathbb{E}[G(p_{i})\mid\mathcal{D}]=\frac{\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)V_{i}}{\sum_{i=1}^{n+1}V_{i}}.$

Then,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})]\\}\geq
t\right)$
$\displaystyle\leq\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\\}\geq\frac{t}{3}\right)+\mathbb{P}\left(\mathbb{E}[G(p_{i})\mid\mathcal{D}]-\mathbb{E}[G(p_{i})]\geq\frac{2t}{3m}\right)$
$\displaystyle\leq\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\\}\geq\frac{t}{3}\right)+\mathbb{P}\left(\mathbb{E}[G(p_{i})\mid\mathcal{D}]-\mathbb{E}[G(p_{i})]\geq\frac{2t}{3m}\right)$
$\displaystyle\leq\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\\}\geq\frac{t}{3}\right)+\mathbb{P}\left(\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)(V_{i}-1)\geq\frac{t(n+1)}{3m}\right)$
$\displaystyle\qquad+\mathbb{P}\left(\sum_{i=1}^{n+1}V_{i}\leq\frac{n+1}{2}\right).$
(79)

By (78) and Bernstein’s inequality [111, e.g.,],

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\\}\geq\frac{t}{3}\mid\mathcal{D}\right)$
$\displaystyle\leq\exp\left\\{-\frac{t^{2}}{18(m\textnormal{Var}[G(p_{i})\mid\mathcal{D}]+t\log
n/9)}\right\\}$
$\displaystyle\leq\exp\left\\{-\frac{t^{2}}{18m\textnormal{Var}[G(p_{i})\mid\mathcal{D}]}\right\\}+\exp\left\\{-\frac{t}{2\log
n}\right\\}.$

By Lemma 9, with probability $1-\exp\\{-c(\log n)^{2}\\}$,

$\textnormal{Var}[G(p_{i})\mid\mathcal{D}]\leq 2,$

when $C(\delta)\log^{6}n/\sqrt{n}\leq 1$. Thus,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\\}\geq\frac{t}{3}\right)\leq\exp\\{-c(\log
n)^{2}\\}+\exp\left\\{-\frac{t^{2}}{36m}\right\\}+\exp\left\\{-\frac{t}{2\log
n}\right\\}.$ (80)

Moving to the second term of (79), we can use the fact that $V_{i}$ is sub-
exponential with parameters $(2,2)$ as shown in the proof of Lemma 9 and apply
Bernstein’s inequality for sums of exponential variables [109, e.g.,],

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)(V_{i}-1)\geq\frac{t(n+1)}{3m}\right)$
$\displaystyle\leq\exp\left\\{-\frac{n+1}{m^{2}}\frac{t^{2}}{36\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)}\right\\}+\exp\left\\{-\frac{n+1}{m}\frac{t}{4\log
n}\right\\}.$

By Lemma 13 and a similar argument for Lemma 10,

$\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)=\mathbb{E}[G(p_{i})^{2}]\leq
3,$

when $C(\delta)\log^{6}n/\sqrt{n}\leq 1$. Thus,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)(V_{i}-1)\geq\frac{t(n+1)}{3m}\right)\leq\exp\left\\{-\frac{n+1}{m^{2}}\frac{t^{2}}{108}\right\\}+\exp\left\\{-\frac{n+1}{m}\frac{t}{4\log
n}\right\\}.$ (81)

As for the third term of (79), we can apply Bernstein’s inequality for sums of
sub-exponential random variables again and obtain that

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n+1}V_{i}\leq\frac{n+1}{2}\right)\leq\mathbb{P}\left(\sum_{i=1}^{n+1}(1-V_{i})\geq\frac{n+1}{2}\right)\leq
2\exp\left\\{-\frac{n+1}{16}\right\\}.$ (82)

Piecing (80) - (82) together, the lemma is proved. ∎

######  Lemma 15.

Under the global null, as $m,n\rightarrow\infty$,

$\displaystyle\bigg{|}\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-\log\left(h^{\textnormal{d}}\circ\hat{u}^{\textnormal{(marg)}}_{i}\right)\geq\sqrt{m}\sqrt{1+\frac{m}{n}}z_{1-\alpha}+m\left\\{1-b_{n}\log\left(\frac{e}{b_{n}}\right)\right\\}\right)-\alpha\bigg{|}$
$\displaystyle\quad=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}\right).$

###### Proof.

Let $G(p)=-\log\left(h^{\textnormal{d}}(p)\right)$. Note that the proof of
Lemma 8 only replies on two facts that (1)
$-\log\left(h^{\textnormal{d}}\circ\hat{u}^{\textnormal{(marg)}}_{i}\right)\leq\log
n$, and (2) Lemma 9 holds for the first four conditional moments. Here, both
continue to hold for DKWM-adjusted p-values. Following the steps in Section
B.1.4, we can show that (76) continues to hold, i.e.,

$\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}_{H_{0}}\left(\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})]\\}\geq
t\right)-\bar{\Phi}\left(\frac{t}{\sqrt{1+\frac{m}{n+1}}}\right)\bigg{|}=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}\right).$
(83)

By Theorem 11,

$\mathbb{E}[G(p_{i})]=1-b_{n}\log\left(\frac{e}{b_{n}}\right)+O\left(\frac{\log
n}{n}\right).$

Using the same argument below (76) in the proof of Lemma 8, we can prove the
result. ∎

####  B.2.4 Effective $\alpha$-level

######  Theorem 12.

  1. (a)

Assume that $m=\gamma n$ for some constant $\gamma\in(0,\infty)$. The type-I
error of Fisher’s combination test applied to
$h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}}$’s

$\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)\leq\exp\left\\{-C(\gamma,\delta)\log^{2}n\right\\},$

for some constant $C(\gamma,\delta)>0$ that only depends on $\gamma$ and
$\delta$.

  2. (b)

Assume that $m\rightarrow\infty$ and $m=o(n/\log^{2}n)$. The type-I error of
Fisher’s combination test applied to
$h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}}$’s

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)=\alpha+o(1).$

###### Proof.

Throughout the proof we suppress $H_{0}$ from the expectation
$\mathbb{E}_{H_{0}}$ and $\mathbb{P}_{H_{0}}$ because we will only consider
the global null.

  1. (a)

Let

$t_{n,m}=\frac{\chi^{2}(2m;1-\alpha)}{2}-m\mathbb{E}[-\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})].$

Then, by Lemma 14,

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)$
$\displaystyle=\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}\\{-\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})-\mathbb{E}[-\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})]\\}\geq
t_{n,m}\right)$ $\displaystyle\leq\exp\left\\{-C(\log
n)^{2}-C\min\left\\{\frac{n}{m},1\right\\}\min\left\\{\frac{t_{n,m}^{2}}{m},\frac{t_{n,m}}{\log
n}\right\\}\right\\}.$

By (56),

$\frac{\chi^{2}(2m;1-\alpha)-2m}{2}=\sqrt{m}z_{1-\alpha}+O\left(1\right).$

By Theorem 11,

$\displaystyle t_{n,m}$
$\displaystyle=mb_{n}\log\left(\frac{e}{b_{n}}\right)+\sqrt{m}z_{1-\alpha}+O\left(1+\frac{m\log
n}{n}\right)$
$\displaystyle=mb_{n}\log\left(\frac{e}{b_{n}}\right)+\sqrt{m}z_{1-\alpha}+O\left(\log
n\right).$

Since $m=\gamma n$, there exists a constant $C(\gamma,\delta)>0$ that only
depends on $\gamma$ and $\delta$ such that

$t_{n,m}\geq C(\gamma,\delta)\sqrt{n}\log n.$

The proof is then completed.

  2. (b)

Choose $\alpha_{n}\in(0,1)$ such that

$\sqrt{1+\frac{m}{n}}z_{1-\alpha_{n}}-\sqrt{m}b_{n}\log\left(\frac{e}{b_{n}}\right)=\frac{\chi^{2}(2m;1-\alpha)-2m}{2\sqrt{m}}\triangleq
A_{m}.$

By Lemma 15,

$\displaystyle\bigg{|}\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)-\alpha_{n}\bigg{|}$
$\displaystyle=\bigg{|}\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\sqrt{m}\sqrt{1+\frac{m}{n}}z_{1-\alpha_{n}}+m\left\\{1-b_{n}\log\left(\frac{e}{b_{n}}\right)\right\\}\right)-\alpha_{n}\bigg{|}$
$\displaystyle=O\left(\frac{1}{\sqrt{m}}+\frac{\log^{6}n}{\sqrt{n}}\right)=o(1).$

Note that $A_{m}=z_{1-\alpha}+o(1)$ and $m=o(n/\log^{2}n)$,

$z_{1-\alpha_{n}}=z_{1-\alpha}+o(1)+O(\sqrt{m}b_{n}\log n)=z_{1-\alpha}+o(1).$

This implies $\alpha_{n}=\alpha+o(1)$ and hence

$\bigg{|}\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{d}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)-\alpha\bigg{|}=o(1).$

∎

###  B.3 Simes adjustment

####  B.3.1 Mean of Fisher’s combination statistic

######  Theorem 13 (Part (c) of Theorem 5).

Assume that $k=\lceil\zeta n\rceil$ for some $\zeta>0$. Then

$\mathbb{E}_{H_{0}}[-\log(h^{\textnormal{s}}\circ\hat{u}^{\textnormal{(marg)}})]\leq
1-\zeta-(1-\zeta)\log(1-\zeta)+O\left(\frac{\log n}{n}\right).$

###### Proof.

Since $(i-j+1)/(n-j+1)\leq i/n$ for any $j=1,\ldots,k$,

$h^{\textnormal{s}}\left(1-\frac{i}{n+1}\right)\geq
1-\delta^{1/k}\frac{i}{n}.$

Moreover,

$h^{\textnormal{s}}\left(1-\frac{i}{n+1}\right)=1\quad\text{if }i<k.$

Then

$\displaystyle\mathbb{E}_{H_{0}}[-\log(h^{\textnormal{s}}\circ\hat{u}^{\textnormal{(marg)}})]$
$\displaystyle\leq\frac{1}{n+1}\sum_{i=k}^{n}-\log\left(1-\delta^{1/k}\frac{i}{n}\right)\leq\frac{1}{n}\sum_{i=k}^{n}-\log\left(1-\delta^{1/k}\frac{i}{n}\right)$
$\displaystyle\leq\frac{\log(1-\delta^{1/k})}{n}+\frac{1}{n}\sum_{i=k}^{n-1}-\log\left(1-\frac{i}{n}\right),$

where the last line uses the fact that $\delta\leq 1$. Since the mapping
$x\mapsto-\log(1-x)$ is increasing,

$\displaystyle\frac{1}{n}\sum_{i=k}^{n-1}-\log\left(1-\frac{i}{n}\right)$
$\displaystyle\leq\int_{k/n}^{1}-\log(1-x)dx\leq\int_{\zeta}^{1}-\log(1-x)dx$
$\displaystyle\leq\int_{0}^{1-\zeta}(-\log
x)dx=1-\zeta-(1-\zeta)\log(1-\zeta).$

Thus,

$\mathbb{E}_{H_{0}}[-\log(h^{\textnormal{s}}\circ\hat{u}^{\textnormal{(marg)}})]\leq
1-\zeta-(1-\zeta)\log(1-\zeta)+O\left(\frac{\log(1-\delta^{1/k})}{n}\right).$

The proof is completed by noting that

$\displaystyle-\log\left(1-\delta^{1/k}\right)$
$\displaystyle=-\log\left(1-\exp\left\\{-\frac{\log(1/\delta)}{k}\right\\}\right)\leq-\log\left(\frac{\log(1/\delta)}{k}\right)\leq\log
n-\log\log\left(\frac{1}{\delta}\right)$ (84) $\displaystyle=O(\log n).$

∎

####  B.3.2 Conditional variance of adjusted p-values

######  Lemma 16.

There exist a universal constant $c>0$ and a constant $n_{0}(\delta)$ that
only depend on $\delta$ such that, for any $n\geq n_{0}(\delta)$,

$\mathbb{P}\left(\mathbb{E}_{H_{0}}[\log^{2}(h^{\textnormal{s}}\circ\hat{u}^{\textnormal{(marg)}})\mid\mathcal{D}]\leq\log
n\right)\leq 1-\exp\left\\{\frac{cn}{\log n}\right\\}.$

###### Proof.

Let $G(p)=-\log(h^{\textnormal{s}}(p))$. By (60),

$\mathbb{E}_{H_{0}}\left[\log^{2}(h^{\textnormal{a}}\circ\hat{u}^{\textnormal{(marg)}})\mid\mathcal{D}\right]=\frac{\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)V_{i}}{\frac{1}{n+1}\sum_{i=1}^{n+1}V_{i}}.$

By (84),

$G\left(\frac{i}{n+1}\right)\leq-\log(1-\delta^{1/k})\leq\log
n-\log\log\frac{1}{\delta}.$

Analogous to the proof of Theorem 13,

$\frac{1}{n+1}\sum_{i=1}^{n+1}G^{4}\left(\frac{i}{n+1}\right)\leq\frac{\log^{4}(1-\delta^{1/k})}{n}+\int_{0}^{1}(\log^{4}x)dx=24+O_{\delta}\left(\frac{\log^{4}n}{n}\right),$
(85)

where we use $O_{\delta}$ herein to hide the dependence on $\delta$. When
$n\geq n_{0}(\delta)$ for some sufficiently large $n_{0}(\delta)$ that only
depends on $\delta$,

$G\left(\frac{i}{n+1}\right)\leq-\log(1-\delta^{1/k})\leq 2\log
n,\quad\frac{1}{n+1}\sum_{i=1}^{n+1}G^{4}\left(\frac{i}{n+1}\right)\leq 25.$
(86)

By Bernstein’s inequality [109, e.g.,],

$\mathbb{P}\left(\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)(V_{i}-1)\geq
t\right)\leq\exp\left(-\min\left\\{\frac{(n+1)t^{2}}{50},\frac{(n+1)t}{8(\log
n)^{2}}\right\\}\right).$

Then, there exists a universal constant $c>0$ such that

$\mathbb{P}\left(\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)(V_{i}-1)\geq\frac{\log
n}{3}\right)\leq\exp\left\\{-\frac{cn}{\log n}\right\\}.$

By (85) and Cauchy-Schwarz inequality,

$\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)=O(1).$

Then, for any sufficiently large $n$,

$\mathbb{P}\left(\frac{1}{n+1}\sum_{i=1}^{n+1}G^{2}\left(\frac{i}{n+1}\right)V_{i}\geq\frac{\log
n}{2}\right)\leq\exp\left\\{-\frac{cn}{\log n}\right\\}.$

By (82),

$\mathbb{P}\left(\frac{1}{n+1}\sum_{i=1}^{n+1}V_{i}\leq\frac{n+1}{2}\right)\leq\exp\left(-\frac{n+1}{16}\right).$

The result is then proved by combining the above two inequalities. ∎

####  B.3.3 Effective $\alpha$-level

######  Lemma 17.

Under the global null, there exists a universal constant $C>0$ and
$n_{0}(\delta)$ that only depends on $\delta$, such that for any $n\geq
n_{0}(\delta)$ and $t>0$,

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}\left\\{-\log\left(h^{\textnormal{s}}\circ\hat{u}^{\textnormal{(marg)}}_{i}\right)-\mathbb{E}\left[-\log\left(h^{\textnormal{s}}\circ\hat{u}^{\textnormal{(marg)}}\right)\right]\right\\}\geq
t\right)$ $\displaystyle\leq\exp\left\\{-C\frac{n}{\log
n}-C\min\left\\{\frac{n}{m},1\right\\}\min\left\\{\frac{t^{2}}{m\log
n},\frac{t}{\log n}\right\\}\right\\}.$

###### Proof.

Let $G(p)=-\log(h^{\textnormal{s}}(p))$ and write $p_{i}$ for
$\hat{u}^{\textnormal{(marg)}}_{i}$. Throughout the proof we suppress $H_{0}$
from the expectation $\mathbb{E}_{H_{0}}$ and $\mathbb{P}_{H_{0}}$ because we
will only consider the global null. Analogous to (79),

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})]\\}\geq
t\right)\leq\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\\}\geq\frac{t}{3}\right)$
$\displaystyle\quad+\mathbb{P}\left(\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)(V_{i}-1)\geq\frac{t(n+1)}{3m}\right)+\mathbb{P}\left(\sum_{i=1}^{n+1}V_{i}\leq\frac{n+1}{2}\right).$
(87)

By Lemma 16, with probability $1-\exp\\{-cn/\log n\\}$,

$\textnormal{Var}[G(p_{i})\mid\mathcal{D}]\leq\log n,$

when $n$ is sufficiently large. By (86),

$G\left(\frac{i}{n+1}\right)\leq 2\log n,$

when $n$ is sufficiently large.

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{m}\\{G(p_{i})-\mathbb{E}[G(p_{i})\mid\mathcal{D}]\\}\geq\frac{t}{3}\right)\leq\exp\left\\{-\frac{cn}{\log
n}\right\\}+\exp\left\\{-\frac{t^{2}}{18m\log
n}\right\\}+\exp\left\\{-\frac{t}{4\log n}\right\\}.$

Similar to (81) and (82), we have

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n+1}G\left(\frac{i}{n+1}\right)(V_{i}-1)\geq\frac{t(n+1)}{3m}\right)+\mathbb{P}\left(\sum_{i=1}^{n+1}V_{i}\leq\frac{n+1}{2}\right)$
$\displaystyle\leq\exp\left\\{-c\frac{n}{m}\min\left\\{\frac{t^{2}}{m},\frac{t}{\log
n}\right\\}-cn\right\\},$

for some universal constant $c>0$. The result is then proved by (87). ∎

######  Theorem 14.

Assume $m/\log n\rightarrow\infty$. The type-I error of Fisher’s combination
test applied to $h^{\textnormal{s}}\circ\hat{u}_{i}^{\textnormal{(marg)}}$’s

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{s}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)\leq\exp\left\\{-C(\zeta,\delta)\frac{\min\\{m,n\\}}{\log
n}\right\\},$

for some constant $C(\zeta,\delta)>0$ that only depends on $\zeta$ and
$\delta$.

###### Proof.

Let

$t_{n,m}=\frac{\chi^{2}(2m;1-\alpha)}{2}-m\mathbb{E}[-\log(h^{\textnormal{s}}\circ\hat{u}_{i}^{\textnormal{(marg)}})].$

Then, by Lemma 17,

$\displaystyle\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{s}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)$
$\displaystyle=\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}\\{-\log(h^{\textnormal{s}}\circ\hat{u}_{i}^{\textnormal{(marg)}})-\mathbb{E}[-\log(h^{\textnormal{s}}\circ\hat{u}_{i}^{\textnormal{(marg)}})]\\}\geq
t_{n,m}\right)$ $\displaystyle\leq\exp\left\\{-C\frac{n}{\log
n}-C\min\left\\{\frac{n}{m},1\right\\}\min\left\\{\frac{t_{n,m}^{2}}{m\log
n},\frac{t_{n,m}}{\log n}\right\\}\right\\}.$

By (56),

$\frac{\chi^{2}(2m;1-\alpha)-2m}{2}=\sqrt{m}z_{1-\alpha}+O\left(1\right).$

By Theorem 13,

$\displaystyle t_{n,m}$ $\displaystyle=m(\zeta+(1-\zeta)\log(1-\zeta))+o(m)$

Thus, there exists $C(\zeta,\delta)>0$ such that

$\mathbb{P}_{H_{0}}\left(\sum_{i=1}^{m}-2\log(h^{\textnormal{s}}\circ\hat{u}_{i}^{\textnormal{(marg)}})\geq\chi^{2}(2m;1-\alpha)\right)\leq\exp\left\\{-C(\zeta,\delta)\left(\frac{n}{\log
n}+\min\left\\{\frac{n}{m},1\right\\}\frac{m}{\log n}\right)\right\\}.$

∎

##  Appendix C Numerical comparisons of different adjustment functions

In addition to the adjustment functions derived from the generalized Simes
inequality and the DKWM inequality, we consider here another class of
simultaneous bounds based on the so-called _boundary crossing probability_
[83, 112, 113, 114]—the probability that $F(z)$ ever crosses
$h(\hat{F}_{n}(z))$ for a fixed function $h(\cdot)$. This probability is
generally difficult to compute analytically, but the special case of a linear
$h(\cdot)$ is an exception. Assuming that $F$ is the CDF of
$\textnormal{Unif}([0,1])$, let $\hat{F}_{n}(z)$ is the empirical CDF of
$S_{1},\ldots,S_{n}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\textnormal{Unif}([0,1])$.
Then, [83] proved that

$\mathbb{P}\left[\hat{F}_{n}(z)\leq b+\frac{1-b}{1-a}z,\,\,\forall
z\in(0,1)\right]=1-\Delta_{\mathrm{Dempster}}(a,b;n),$

for any $a,b\in(0,1)$, where

$\Delta_{\mathrm{Dempster}}(a,b;n)\vcentcolon=a\sum_{j=0}^{\lfloor
n(1-b)\rfloor}\frac{n!}{j!(n-j)!}\left(a+\frac{1-a}{1-b}\frac{j}{n}\right)^{j-1}\left(1-a-\frac{1-a}{1-b}\frac{j}{n}\right)^{n-j}.$
(88)

If we replace $S_{i}$ with $1-S_{i}$, then $\hat{F}_{n}(z)$ becomes
$1-\hat{F}_{n}(1-z)$. Further, replacing $z$ by $1-z$ leads to

$\mathbb{P}\left[z\leq\frac{1-a}{1-b}\hat{F}_{n}(z)+a,\,\,\forall
z\in(0,1)\right]=1-\Delta_{\mathrm{Dempster}}(a,b;n).$ (89)

For any pair $(a,b)$ with $\Delta_{\mathrm{Dempster}}(a,b;n)=\delta$, we
obtain a function $h(z)=a+(1-a)z/(1-b)$ satisfying (21), which yields the
following sequence satisfying (10):

$b_{i}=a+\frac{1-a}{1-b}\frac{i}{n}.$

Given any $a$, it is easy to compute the corresponding $b$ such that
$\Delta_{\mathrm{Dempster}}(a,b;n)=\delta$ via a binary search. Note that this
leads to adjusted p-values that cannot be lower than $b_{1}=a+(1-a)/(1-b)n$.
To ensure a fair comparison with the method based on the generalized Simes
inequality, we choose $a$ via another binary search such that the resulting
$b_{1}$ matches that given by the Simes inequality for a particular value of
$k$. If there exists no value of $a$ yielding the same $b_{1}$ as the Simes
method, we set $a$ as to minimize $b_{1}$. Figure A2 compares the adjustment
functions yielded by the generalized Simes inequality, the DKWM inequality,
and the Dempster exact linear-boundary crossing probability with
$k\in\\{n/4,n/2\\}$ and $n\in\\{300,1000,3000,10000\\}$ for small marginal
p-values within $[0,0.05]$. It is clear that the Simes adjustment function is
the best option in most scenarios, except when $n=10000$ and
$\hat{u}^{\textnormal{(marg)}}(X)>0.03$, in which case the DKWM bound is
tighter. Nonetheless, for the purpose of multiple testing, we would rarely
expect p-values above $0.03$ to be significant.

Figure A2: Comparison of different adjustment functions, with $n=1000$ and
$\delta=0.1$.

Figure A3: Comparison of different adjustment functions, with $n=10000$ and
$\delta=0.1$. Other details are as in Figure A2. Figure A4: Comparison of
different adjustment functions, with $n=1000$ and $\delta=0.1$.

##  Appendix D Numerical outlier detection experiments

###  D.1 Outlier detection on simulated data

Figure A5: FDR and power in a simulated outlier detection problem as a
function of the number of samples in the data set (half of which are utilized
for calibration). Other details are as in Figure 7.  Figure A6: FDR and power
in a simulated outlier detection problem, using the BH procedure with Storey’s
correction. Other details are as in Figure A5.  Figure A7: FDR and power in a
simulated outlier detection problem, using the BH procedure with Storey’s
correction. Other details are as in Figure 7.  Figure A8: FDR and power in a
simulated outlier detection problem, using the BH procedure with Storey’s
correction. The conditional calibration method is applied with $\delta=0.25$
instead of $\delta=0.1$. Other details are as in Figure 7.  Figure A9:
Performance of simultaneously calibrated conformal p-values as a function of
the Simes parameter $n/k$. The signal strength is equal to 2. Other details
are as in Figure 7.  Figure A10: Performance of different methods for
calibrating conformal p-values in a simulated outlier batch detection problem,
for different values of the signal strength. Other details are as in Figure
A10.  Figure A11: Performance of different methods for combining p-values from
the same batch for the purpose of global testing. Other details are as in
Figure 8.

###  D.2 Outlier detection on real data

Table A1: Outlier detection performance on real data, using different data sets, machine learning models, and nominal FDR levels. The BH procedure is applied with Storey’s correction to control the FDR. Other details are as in Table 2.  | FDR | Power
---|---|---
| Mean | 90th percentile | Mean | 90-th quantile
Model | Nominal | Marg. | Cond. | Marg. | Cond. | Marg. | Cond. | Marg. | Cond.
ALOI
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.001 | 0 | 0 | 0 | 0 | 0 | 0 | 0
IForest | 0.20 | 0.025 | 0.001 | 0.048 | 0 | 0 | 0 | 0 | 0
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.005 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Neighbors | 0.20 | 0.059 | 0.008 | 0.245 | 0.01 | 0.002 | 0 | 0.007 | 0
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.006 | 0 | 0.006 | 0 | 0 | 0 | 0.001 | 0
SVM | 0.20 | 0.066 | 0.009 | 0.212 | 0.017 | 0.003 | 0 | 0.01 | 0.002
Cover
| 0.05 | 0.004 | 0.001 | 0 | 0 | 0.001 | 0 | 0 | 0
| 0.10 | 0.017 | 0.007 | 0.037 | 0.002 | 0.003 | 0.001 | 0.005 | 0
IForest | 0.20 | 0.099 | 0.044 | 0.297 | 0.148 | 0.012 | 0.006 | 0.038 | 0.02
| 0.05 | 0.047 | 0.038 | 0.067 | 0.054 | 0.948 | 0.935 | 0.964 | 0.957
| 0.10 | 0.096 | 0.081 | 0.124 | 0.106 | 0.972 | 0.968 | 0.98 | 0.976
Neighbors | 0.20 | 0.195 | 0.174 | 0.231 | 0.207 | 0.987 | 0.985 | 0.99 | 0.989
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Credit card
| 0.05 | 0.032 | 0.016 | 0.07 | 0.051 | 0.149 | 0.08 | 0.358 | 0.264
| 0.10 | 0.09 | 0.063 | 0.13 | 0.105 | 0.383 | 0.277 | 0.57 | 0.518
IForest | 0.20 | 0.191 | 0.162 | 0.228 | 0.202 | 0.679 | 0.611 | 0.782 | 0.746
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.005 | 0.001 | 0 | 0 | 0.001 | 0 | 0 | 0
Neighbors | 0.20 | 0.074 | 0.027 | 0.283 | 0.086 | 0.006 | 0.003 | 0.024 | 0.008
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
KDDCup99
| 0.05 | 0.039 | 0.02 | 0.076 | 0.047 | 0.359 | 0.216 | 0.51 | 0.465
| 0.10 | 0.096 | 0.059 | 0.129 | 0.098 | 0.598 | 0.452 | 0.715 | 0.644
IForest | 0.20 | 0.194 | 0.131 | 0.23 | 0.168 | 0.754 | 0.684 | 0.825 | 0.753
| 0.05 | 0.006 | 0 | 0 | 0 | 0.001 | 0 | 0 | 0
| 0.10 | 0.03 | 0.009 | 0.147 | 0 | 0.009 | 0.002 | 0.049 | 0
Neighbors | 0.20 | 0.125 | 0.042 | 0.274 | 0.17 | 0.033 | 0.011 | 0.068 | 0.056
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Mammography
| 0.05 | 0.011 | 0 | 0.037 | 0 | 0.01 | 0 | 0.023 | 0
| 0.10 | 0.076 | 0.002 | 0.171 | 0 | 0.059 | 0.004 | 0.146 | 0
IForest | 0.20 | 0.187 | 0.056 | 0.286 | 0.17 | 0.176 | 0.059 | 0.337 | 0.22
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.016 | 0 | 0.027 | 0 | 0.011 | 0 | 0.021 | 0
Neighbors | 0.20 | 0.155 | 0.023 | 0.263 | 0.084 | 0.175 | 0.024 | 0.285 | 0.078
| 0.05 | 0.007 | 0 | 0.018 | 0 | 0.003 | 0 | 0.008 | 0
| 0.10 | 0.066 | 0 | 0.168 | 0 | 0.04 | 0 | 0.09 | 0
SVM | 0.20 | 0.188 | 0.046 | 0.274 | 0.145 | 0.171 | 0.032 | 0.288 | 0.095
Digits
| 0.05 | 0.012 | 0 | 0.03 | 0 | 0.013 | 0 | 0.036 | 0
| 0.10 | 0.058 | 0.004 | 0.164 | 0 | 0.076 | 0.006 | 0.295 | 0
IForest | 0.20 | 0.202 | 0.052 | 0.266 | 0.173 | 0.417 | 0.096 | 0.629 | 0.355
| 0.05 | 0.006 | 0 | 0.028 | 0 | 0.033 | 0.002 | 0.049 | 0
| 0.10 | 0.059 | 0.006 | 0.135 | 0.01 | 0.273 | 0.035 | 0.752 | 0.03
Neighbors | 0.20 | 0.191 | 0.092 | 0.238 | 0.166 | 0.841 | 0.455 | 0.99 | 0.879
| 0.05 | 0.004 | 0 | 0.003 | 0 | 0.002 | 0 | 0.001 | 0
| 0.10 | 0.044 | 0 | 0.149 | 0 | 0.018 | 0 | 0.045 | 0
SVM | 0.20 | 0.175 | 0.018 | 0.264 | 0.066 | 0.227 | 0.017 | 0.468 | 0.048
Shuttle
| 0.05 | 0.047 | 0.031 | 0.068 | 0.049 | 0.936 | 0.889 | 0.975 | 0.972
| 0.10 | 0.096 | 0.072 | 0.122 | 0.097 | 0.974 | 0.965 | 0.981 | 0.979
IForest | 0.20 | 0.196 | 0.163 | 0.228 | 0.198 | 0.981 | 0.98 | 0.984 | 0.983
| 0.05 | 0.048 | 0.031 | 0.066 | 0.047 | 0.99 | 0.951 | 0.998 | 0.991
| 0.10 | 0.098 | 0.07 | 0.125 | 0.093 | 0.999 | 0.996 | 1 | 1
Neighbors | 0.20 | 0.199 | 0.151 | 0.231 | 0.193 | 1 | 1 | 1 | 1
| 0.05 | 0.043 | 0.021 | 0.066 | 0.045 | 0.814 | 0.486 | 0.998 | 0.993
| 0.10 | 0.096 | 0.069 | 0.127 | 0.093 | 0.999 | 0.997 | 1 | 0.999
SVM | 0.20 | 0.198 | 0.148 | 0.233 | 0.182 | 1 | 1 | 1 | 1
Table A1: Outlier detection performance on real data, using different data
sets, machine learning models, and nominal FDR levels. The BH procedure is
applied with Storey’s correction to control the FDR. Other details are as in
Table 2. (continued)

Table A2: Outlier detection performance on real data, using different data sets, machine learning models, and nominal FDR levels. The BH procedure is applied without Storey’s correction to control the FDR. Other details are as in Table LABEL:tab:data-bh-long-storey.  | FDR | Power
---|---|---
| Mean | 90th percentile | Mean | 90-th quantile
Model | Nominal | Marg. | Cond. | Marg. | Cond. | Marg. | Cond. | Marg. | Cond.
ALOI
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.001 | 0 | 0 | 0 | 0 | 0 | 0 | 0
IForest | 0.20 | 0.032 | 0.002 | 0.08 | 0 | 0 | 0 | 0 | 0
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.004 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Neighbors | 0.20 | 0.057 | 0.008 | 0.234 | 0.01 | 0.002 | 0 | 0.006 | 0
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.007 | 0 | 0.009 | 0 | 0 | 0 | 0.001 | 0
SVM | 0.20 | 0.076 | 0.012 | 0.231 | 0.019 | 0.003 | 0.001 | 0.011 | 0.002
Cover
| 0.05 | 0.004 | 0 | 0 | 0 | 0.001 | 0 | 0 | 0
| 0.10 | 0.014 | 0.006 | 0.026 | 0 | 0.002 | 0.001 | 0.003 | 0
IForest | 0.20 | 0.089 | 0.03 | 0.285 | 0.083 | 0.01 | 0.005 | 0.035 | 0.013
| 0.05 | 0.043 | 0.034 | 0.058 | 0.047 | 0.942 | 0.929 | 0.961 | 0.954
| 0.10 | 0.086 | 0.073 | 0.109 | 0.097 | 0.97 | 0.965 | 0.978 | 0.974
Neighbors | 0.20 | 0.176 | 0.158 | 0.211 | 0.191 | 0.985 | 0.983 | 0.989 | 0.987
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Credit card
| 0.05 | 0.027 | 0.013 | 0.065 | 0.047 | 0.125 | 0.066 | 0.332 | 0.248
| 0.10 | 0.082 | 0.057 | 0.122 | 0.099 | 0.351 | 0.249 | 0.542 | 0.482
IForest | 0.20 | 0.173 | 0.146 | 0.212 | 0.186 | 0.642 | 0.57 | 0.763 | 0.712
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.005 | 0.001 | 0 | 0 | 0 | 0 | 0 | 0
Neighbors | 0.20 | 0.072 | 0.021 | 0.292 | 0.062 | 0.006 | 0.002 | 0.024 | 0.006
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
KDDCup99
| 0.05 | 0.033 | 0.017 | 0.073 | 0.045 | 0.329 | 0.188 | 0.496 | 0.465
| 0.10 | 0.086 | 0.055 | 0.118 | 0.093 | 0.562 | 0.437 | 0.695 | 0.627
IForest | 0.20 | 0.174 | 0.124 | 0.209 | 0.159 | 0.736 | 0.673 | 0.796 | 0.745
| 0.05 | 0.006 | 0 | 0 | 0 | 0.001 | 0 | 0 | 0
| 0.10 | 0.028 | 0.008 | 0.136 | 0 | 0.008 | 0.002 | 0.05 | 0
Neighbors | 0.20 | 0.122 | 0.041 | 0.276 | 0.17 | 0.032 | 0.011 | 0.069 | 0.055
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Mammography
| 0.05 | 0.008 | 0 | 0.011 | 0 | 0.007 | 0 | 0.006 | 0
| 0.10 | 0.061 | 0.002 | 0.161 | 0 | 0.045 | 0.003 | 0.125 | 0
IForest | 0.20 | 0.167 | 0.054 | 0.269 | 0.169 | 0.156 | 0.058 | 0.305 | 0.217
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0.011 | 0 | 0.01 | 0 | 0.007 | 0 | 0.005 | 0
Neighbors | 0.20 | 0.126 | 0.021 | 0.241 | 0.078 | 0.14 | 0.022 | 0.272 | 0.088
| 0.05 | 0.003 | 0 | 0.004 | 0 | 0.001 | 0 | 0.003 | 0
| 0.10 | 0.053 | 0 | 0.155 | 0 | 0.033 | 0 | 0.077 | 0
SVM | 0.20 | 0.171 | 0.046 | 0.264 | 0.147 | 0.145 | 0.032 | 0.257 | 0.094
Digits
| 0.05 | 0.01 | 0 | 0.013 | 0 | 0.01 | 0 | 0.012 | 0
| 0.10 | 0.051 | 0.004 | 0.155 | 0 | 0.062 | 0.006 | 0.246 | 0
IForest | 0.20 | 0.182 | 0.054 | 0.248 | 0.174 | 0.357 | 0.099 | 0.59 | 0.326
| 0.05 | 0.005 | 0 | 0.008 | 0 | 0.027 | 0.002 | 0.025 | 0
| 0.10 | 0.044 | 0.005 | 0.123 | 0.008 | 0.202 | 0.031 | 0.667 | 0.027
Neighbors | 0.20 | 0.172 | 0.084 | 0.217 | 0.16 | 0.791 | 0.421 | 0.982 | 0.871
| 0.05 | 0.003 | 0 | 0 | 0 | 0.001 | 0 | 0 | 0
| 0.10 | 0.04 | 0 | 0.151 | 0 | 0.014 | 0 | 0.041 | 0
SVM | 0.20 | 0.158 | 0.021 | 0.255 | 0.097 | 0.154 | 0.019 | 0.39 | 0.043
Shuttle
| 0.05 | 0.042 | 0.029 | 0.06 | 0.044 | 0.926 | 0.88 | 0.975 | 0.972
| 0.10 | 0.086 | 0.066 | 0.11 | 0.09 | 0.972 | 0.961 | 0.981 | 0.978
IForest | 0.20 | 0.178 | 0.149 | 0.212 | 0.187 | 0.98 | 0.979 | 0.983 | 0.983
| 0.05 | 0.042 | 0.029 | 0.062 | 0.042 | 0.987 | 0.925 | 0.997 | 0.99
| 0.10 | 0.087 | 0.065 | 0.111 | 0.085 | 0.998 | 0.995 | 1 | 1
Neighbors | 0.20 | 0.178 | 0.139 | 0.208 | 0.174 | 1 | 0.999 | 1 | 1
| 0.05 | 0.038 | 0.019 | 0.06 | 0.045 | 0.792 | 0.462 | 0.997 | 0.993
| 0.10 | 0.087 | 0.064 | 0.112 | 0.086 | 0.999 | 0.996 | 1 | 0.999
SVM | 0.20 | 0.178 | 0.138 | 0.208 | 0.168 | 1 | 1 | 1 | 1
Table A2: Outlier detection performance on real data, using different data
sets, machine learning models, and nominal FDR levels. The BH procedure is
applied without Storey’s correction to control the FDR. Other details are as
in Table LABEL:tab:data-bh-long-storey. (continued)

Table A3: Outlier batch detection performance on real data, using Storey’s correction to control the FDR. Other details are as in Table LABEL:tab:data-global-long.  | FDR | Power
---|---|---
| Mean | 90th percentile | Mean | 90-th quantile
Model | Nominal | Marg. | Cond. | Marg. | Cond. | Marg. | Cond. | Marg. | Cond.
ALOI
| 0.05 | 0.029 | 0.008 | 0.1 | 0.003 | 0 | 0 | 0.002 | 0
| 0.10 | 0.07 | 0.016 | 0.2 | 0.081 | 0.001 | 0 | 0.004 | 0.002
IForest | 0.20 | 0.157 | 0.048 | 0.332 | 0.16 | 0.004 | 0.001 | 0.009 | 0.003
| 0.05 | 0.038 | 0.009 | 0.108 | 0.041 | 0.023 | 0.009 | 0.04 | 0.017
| 0.10 | 0.079 | 0.025 | 0.176 | 0.083 | 0.049 | 0.02 | 0.078 | 0.037
LOF | 0.20 | 0.167 | 0.069 | 0.288 | 0.156 | 0.109 | 0.045 | 0.154 | 0.073
| 0.05 | 0.035 | 0.006 | 0.1 | 0.006 | 0.003 | 0.001 | 0.007 | 0.003
| 0.10 | 0.069 | 0.025 | 0.173 | 0.09 | 0.006 | 0.003 | 0.012 | 0.007
SVM | 0.20 | 0.157 | 0.058 | 0.33 | 0.17 | 0.014 | 0.005 | 0.023 | 0.01
Cover
| 0.05 | 0.037 | 0.021 | 0.099 | 0.079 | 0.1 | 0.068 | 0.185 | 0.122
| 0.10 | 0.08 | 0.05 | 0.158 | 0.12 | 0.184 | 0.132 | 0.333 | 0.243
IForest | 0.20 | 0.176 | 0.118 | 0.277 | 0.206 | 0.332 | 0.253 | 0.535 | 0.451
| 0.05 | 0.046 | 0.029 | 0.074 | 0.056 | 1 | 1 | 1 | 1
| 0.10 | 0.096 | 0.068 | 0.138 | 0.109 | 1 | 1 | 1 | 1
LOF | 0.20 | 0.197 | 0.147 | 0.274 | 0.211 | 1 | 1 | 1 | 1
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Credit card
| 0.05 | 0.04 | 0.026 | 0.064 | 0.049 | 0.965 | 0.951 | 0.983 | 0.972
| 0.10 | 0.086 | 0.059 | 0.126 | 0.094 | 0.981 | 0.973 | 0.992 | 0.987
IForest | 0.20 | 0.179 | 0.131 | 0.251 | 0.184 | 0.992 | 0.988 | 0.998 | 0.996
| 0.05 | 0.039 | 0.022 | 0.1 | 0.085 | 0.034 | 0.022 | 0.055 | 0.037
| 0.10 | 0.081 | 0.048 | 0.179 | 0.11 | 0.062 | 0.043 | 0.097 | 0.066
LOF | 0.20 | 0.17 | 0.112 | 0.309 | 0.208 | 0.122 | 0.084 | 0.178 | 0.135
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
KDDCup99
| 0.05 | 0.044 | 0.019 | 0.077 | 0.043 | 0.998 | 0.993 | 1 | 0.999
| 0.10 | 0.091 | 0.044 | 0.145 | 0.08 | 1 | 0.998 | 1 | 1
IForest | 0.20 | 0.191 | 0.099 | 0.267 | 0.166 | 1 | 1 | 1 | 1
| 0.05 | 0.045 | 0.021 | 0.094 | 0.076 | 0.064 | 0.03 | 0.103 | 0.052
| 0.10 | 0.086 | 0.038 | 0.17 | 0.089 | 0.108 | 0.053 | 0.164 | 0.087
LOF | 0.20 | 0.182 | 0.074 | 0.287 | 0.165 | 0.19 | 0.096 | 0.266 | 0.146
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Mammography
| 0.05 | 0.034 | 0.005 | 0.066 | 0.019 | 0.476 | 0.228 | 0.628 | 0.394
| 0.10 | 0.069 | 0.014 | 0.116 | 0.03 | 0.599 | 0.334 | 0.742 | 0.521
IForest | 0.20 | 0.138 | 0.035 | 0.215 | 0.067 | 0.728 | 0.467 | 0.844 | 0.658
| 0.05 | 0.032 | 0.01 | 0.067 | 0.032 | 0.429 | 0.202 | 0.575 | 0.35
| 0.10 | 0.066 | 0.018 | 0.114 | 0.047 | 0.561 | 0.314 | 0.691 | 0.485
LOF | 0.20 | 0.14 | 0.04 | 0.201 | 0.087 | 0.697 | 0.457 | 0.814 | 0.619
| 0.05 | 0.008 | 0 | 0.022 | 0 | 0.34 | 0.144 | 0.437 | 0.225
| 0.10 | 0.02 | 0.002 | 0.048 | 0.005 | 0.451 | 0.228 | 0.546 | 0.332
SVM | 0.20 | 0.043 | 0.009 | 0.083 | 0.023 | 0.57 | 0.341 | 0.655 | 0.45
Digits
| 0.05 | 0.04 | 0.006 | 0.074 | 0.017 | 0.924 | 0.673 | 0.986 | 0.842
| 0.10 | 0.084 | 0.016 | 0.141 | 0.033 | 0.968 | 0.814 | 0.995 | 0.926
IForest | 0.20 | 0.176 | 0.038 | 0.268 | 0.075 | 0.991 | 0.911 | 1 | 0.981
| 0.05 | 0.045 | 0.007 | 0.082 | 0.019 | 0.999 | 0.977 | 1 | 1
| 0.10 | 0.093 | 0.019 | 0.151 | 0.038 | 1 | 0.994 | 1 | 1
LOF | 0.20 | 0.191 | 0.046 | 0.277 | 0.084 | 1 | 0.999 | 1 | 1
| 0.05 | 0.049 | 0.007 | 0.091 | 0.021 | 0.824 | 0.511 | 0.896 | 0.665
| 0.10 | 0.104 | 0.02 | 0.166 | 0.045 | 0.905 | 0.674 | 0.956 | 0.8
SVM | 0.20 | 0.206 | 0.049 | 0.302 | 0.098 | 0.957 | 0.81 | 0.985 | 0.9
Shuttle
| 0.05 | 0.046 | 0.021 | 0.077 | 0.04 | 1 | 1 | 1 | 1
| 0.10 | 0.094 | 0.047 | 0.142 | 0.087 | 1 | 1 | 1 | 1
IForest | 0.20 | 0.194 | 0.102 | 0.281 | 0.161 | 1 | 1 | 1 | 1
| 0.05 | 0.045 | 0.019 | 0.082 | 0.04 | 1 | 1 | 1 | 1
| 0.10 | 0.095 | 0.041 | 0.158 | 0.081 | 1 | 1 | 1 | 1
LOF | 0.20 | 0.193 | 0.094 | 0.287 | 0.166 | 1 | 1 | 1 | 1
| 0.05 | 0.038 | 0.013 | 0.066 | 0.026 | 1 | 1 | 1 | 1
| 0.10 | 0.085 | 0.034 | 0.121 | 0.059 | 1 | 1 | 1 | 1
SVM | 0.20 | 0.18 | 0.083 | 0.244 | 0.137 | 1 | 1 | 1 | 1
Table A3: Outlier batch detection performance on real data, using Storey’s
correction to control the FDR. Other details are as in Table LABEL:tab:data-
global-long. (continued)

Table A4: Outlier batch detection performance on real data, using different data sets, machine learning models, and nominal FDR levels. Other details are as in Table LABEL:tab:data-global-long-storey.  | FDR | Power
---|---|---
| Mean | 90th percentile | Mean | 90-th quantile
Model | Nominal | Marg. | Cond. | Marg. | Cond. | Marg. | Cond. | Marg. | Cond.
ALOI
| 0.05 | 0.027 | 0.009 | 0.1 | 0.034 | 0 | 0 | 0.002 | 0
| 0.10 | 0.067 | 0.021 | 0.191 | 0.096 | 0.001 | 0 | 0.004 | 0.002
IForest | 0.20 | 0.157 | 0.059 | 0.341 | 0.186 | 0.004 | 0.001 | 0.008 | 0.004
| 0.05 | 0.032 | 0.01 | 0.093 | 0.054 | 0.021 | 0.009 | 0.038 | 0.018
| 0.10 | 0.07 | 0.025 | 0.154 | 0.084 | 0.044 | 0.02 | 0.066 | 0.033
LOF | 0.20 | 0.152 | 0.07 | 0.279 | 0.154 | 0.097 | 0.045 | 0.138 | 0.069
| 0.05 | 0.034 | 0.006 | 0.1 | 0.001 | 0.003 | 0.001 | 0.007 | 0.004
| 0.10 | 0.07 | 0.027 | 0.186 | 0.096 | 0.006 | 0.003 | 0.012 | 0.007
SVM | 0.20 | 0.154 | 0.064 | 0.294 | 0.19 | 0.013 | 0.006 | 0.022 | 0.012
Cover
| 0.05 | 0.031 | 0.02 | 0.086 | 0.071 | 0.091 | 0.065 | 0.172 | 0.113
| 0.10 | 0.072 | 0.046 | 0.143 | 0.111 | 0.168 | 0.126 | 0.309 | 0.234
IForest | 0.20 | 0.155 | 0.109 | 0.243 | 0.189 | 0.304 | 0.24 | 0.506 | 0.427
| 0.05 | 0.04 | 0.027 | 0.067 | 0.05 | 1 | 1 | 1 | 1
| 0.10 | 0.086 | 0.063 | 0.121 | 0.095 | 1 | 1 | 1 | 1
LOF | 0.20 | 0.176 | 0.138 | 0.234 | 0.19 | 1 | 1 | 1 | 1
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Credit card
| 0.05 | 0.035 | 0.025 | 0.058 | 0.042 | 0.963 | 0.951 | 0.983 | 0.972
| 0.10 | 0.077 | 0.056 | 0.116 | 0.087 | 0.98 | 0.973 | 0.992 | 0.986
IForest | 0.20 | 0.16 | 0.124 | 0.223 | 0.17 | 0.992 | 0.988 | 0.998 | 0.995
| 0.05 | 0.035 | 0.021 | 0.097 | 0.085 | 0.031 | 0.022 | 0.047 | 0.037
| 0.10 | 0.072 | 0.047 | 0.168 | 0.107 | 0.057 | 0.04 | 0.087 | 0.062
LOF | 0.20 | 0.153 | 0.103 | 0.276 | 0.2 | 0.11 | 0.08 | 0.159 | 0.12
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
KDDCup99
| 0.05 | 0.039 | 0.019 | 0.067 | 0.043 | 0.998 | 0.994 | 1 | 0.999
| 0.10 | 0.08 | 0.043 | 0.126 | 0.079 | 0.999 | 0.998 | 1 | 1
IForest | 0.20 | 0.171 | 0.099 | 0.238 | 0.158 | 1 | 1 | 1 | 1
| 0.05 | 0.043 | 0.021 | 0.095 | 0.08 | 0.06 | 0.032 | 0.093 | 0.052
| 0.10 | 0.08 | 0.039 | 0.168 | 0.09 | 0.101 | 0.056 | 0.143 | 0.087
LOF | 0.20 | 0.165 | 0.075 | 0.267 | 0.158 | 0.176 | 0.1 | 0.246 | 0.148
| 0.05 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0.10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVM | 0.20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Mammography
| 0.05 | 0.035 | 0.007 | 0.066 | 0.022 | 0.482 | 0.259 | 0.63 | 0.433
| 0.10 | 0.069 | 0.018 | 0.111 | 0.044 | 0.606 | 0.376 | 0.736 | 0.56
IForest | 0.20 | 0.14 | 0.045 | 0.209 | 0.079 | 0.735 | 0.517 | 0.846 | 0.694
| 0.05 | 0.032 | 0.011 | 0.062 | 0.035 | 0.435 | 0.232 | 0.577 | 0.373
| 0.10 | 0.067 | 0.022 | 0.108 | 0.05 | 0.571 | 0.354 | 0.694 | 0.52
LOF | 0.20 | 0.142 | 0.05 | 0.194 | 0.093 | 0.705 | 0.505 | 0.803 | 0.656
| 0.05 | 0.012 | 0.001 | 0.028 | 0.002 | 0.382 | 0.189 | 0.472 | 0.272
| 0.10 | 0.027 | 0.004 | 0.056 | 0.013 | 0.497 | 0.29 | 0.585 | 0.39
SVM | 0.20 | 0.057 | 0.015 | 0.1 | 0.038 | 0.62 | 0.418 | 0.69 | 0.515
Digits
| 0.05 | 0.035 | 0.007 | 0.057 | 0.018 | 0.92 | 0.719 | 0.985 | 0.876
| 0.10 | 0.075 | 0.019 | 0.118 | 0.037 | 0.966 | 0.851 | 0.994 | 0.952
IForest | 0.20 | 0.156 | 0.047 | 0.223 | 0.081 | 0.99 | 0.935 | 1 | 0.987
| 0.05 | 0.04 | 0.008 | 0.071 | 0.02 | 0.999 | 0.984 | 1 | 1
| 0.10 | 0.083 | 0.022 | 0.137 | 0.041 | 1 | 0.996 | 1 | 1
LOF | 0.20 | 0.169 | 0.055 | 0.242 | 0.092 | 1 | 1 | 1 | 1
| 0.05 | 0.043 | 0.009 | 0.078 | 0.025 | 0.811 | 0.55 | 0.883 | 0.689
| 0.10 | 0.089 | 0.023 | 0.138 | 0.048 | 0.898 | 0.712 | 0.94 | 0.813
SVM | 0.20 | 0.179 | 0.056 | 0.251 | 0.104 | 0.953 | 0.841 | 0.979 | 0.912
Shuttle
| 0.05 | 0.041 | 0.02 | 0.068 | 0.042 | 1 | 1 | 1 | 1
| 0.10 | 0.084 | 0.046 | 0.131 | 0.084 | 1 | 1 | 1 | 1
IForest | 0.20 | 0.172 | 0.103 | 0.236 | 0.155 | 1 | 1 | 1 | 1
| 0.05 | 0.041 | 0.019 | 0.073 | 0.039 | 1 | 1 | 1 | 1
| 0.10 | 0.084 | 0.042 | 0.132 | 0.078 | 1 | 1 | 1 | 1
LOF | 0.20 | 0.17 | 0.095 | 0.237 | 0.161 | 1 | 1 | 1 | 1
| 0.05 | 0.034 | 0.014 | 0.056 | 0.027 | 1 | 1 | 1 | 1
| 0.10 | 0.074 | 0.035 | 0.11 | 0.059 | 1 | 1 | 1 | 1
SVM | 0.20 | 0.16 | 0.085 | 0.22 | 0.134 | 1 | 1 | 1 | 1
Table A4: Outlier batch detection performance on real data, using different
data sets, machine learning models, and nominal FDR levels. Other details are
as in Table LABEL:tab:data-global-long-storey. (continued)