We now conduct the exact computation. For $t=9/10$, when $W_{1}<W_{2}$, we
note that it must be
$p_{2}=\frac{W_{1}+W_{2}+U_{2}\widetilde{W}_{2}}{W_{1}+W_{2}+\widetilde{W}_{2}}$,
i.e., $\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1}$. Therefore,

$\displaystyle\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq 9/10,W_{1}<W_{2})$
$\displaystyle=\mathbb{P}\big{(}p_{1}\leq 1/10,p_{2}\geq
9/10,\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1}\big{)}$
$\displaystyle=\mathbb{P}\Bigg{(}\frac{U_{1}\cdot\widetilde{W}_{1}}{W_{1}+W_{2}+\widetilde{W}_{1}}\leq\frac{1}{10},~{}\frac{W_{1}+W_{2}+U_{2}\widetilde{W}_{2}}{W_{1}+W_{2}+\widetilde{W}_{2}}\geq\frac{9}{10},~{}\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1}\Bigg{)}$
$\displaystyle=\mathbb{P}\Bigg{(}\frac{U_{1}\cdot\widetilde{W}_{1}}{W_{1}+W_{2}+\widetilde{W}_{1}}\leq\frac{1}{10},~{}\frac{W_{1}+W_{2}+U_{2}\widetilde{W}_{2}}{W_{1}+W_{2}+\widetilde{W}_{2}}\geq\frac{9}{10},~{}\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1}\Bigg{)}$
$\displaystyle=\mathbb{P}\Bigg{(}U_{1}\leq\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}},~{}1-U_{2}\geq\frac{W_{1}+W_{2}+\widetilde{W}_{2}}{10\widetilde{W}_{2}},~{}\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1}\Bigg{)}.$
(20)

We note that in this case
$\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}},\frac{W_{1}+W_{2}+\widetilde{W}_{2}}{10\widetilde{W}_{2}}\in[0,1]$
deterministically. Since $U_{1},U_{2}$ are mutually independent, and also
independent of everything else, by the tower property,

$\displaystyle\eqref{eq:prob1}=\mathbb{E}\Bigg{[}\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}}\cdot\frac{W_{1}+W_{2}+\widetilde{W}_{2}}{10\widetilde{W}_{2}}\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1}\\}\Bigg{]}.$

By the symmetry of $W_{1},W_{2}$, we know

$\displaystyle\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq
9/10)=2\times\eqref{eq:prob1}$
$\displaystyle=\mathbb{E}\Bigg{[}\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}}\cdot\frac{W_{1}+W_{2}+\widetilde{W}_{2}}{10\widetilde{W}_{2}}\cdot\operatorname{\mathds{1}}\\{W_{1},W_{2}\in[\widetilde{W}_{2},\widetilde{W}_{1}],\widetilde{W}_{2}<\widetilde{W}_{1}]\\}\Bigg{]}.$
(21)

Note that conditional on $\widetilde{W}_{2},\widetilde{W}_{1}$ and the event
$\\{W_{1},W_{2}\in[\widetilde{W}_{2},\widetilde{W}_{1}]\\}$, one has
$W_{1},W_{2}\sim\textrm{Unif}([\widetilde{W}_{1},\widetilde{W}_{2}])$ and are
mutually independent. Applying tower property again, we have

$\displaystyle\eqref{eq:prob12}$
$\displaystyle=\mathbb{E}\Bigg{[}\frac{13\widetilde{W}_{1}^{2}/6+13\widetilde{W}_{2}^{2}/6+14\widetilde{W}_{1}\widetilde{W}_{2}/3}{100\widetilde{W}_{1}\cdot\widetilde{W}_{2}}\cdot\mathbb{P}\big{(}W_{1},W_{2}\in[\widetilde{W}_{2},\widetilde{W}_{1}]\,\big{|}\,\widetilde{W}_{1},\widetilde{W}_{2}\big{)}\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<\widetilde{W}_{1}\\}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\frac{13\widetilde{W}_{1}^{2}/6+13\widetilde{W}_{2}^{2}/6+14\widetilde{W}_{1}\widetilde{W}_{2}/3}{100\widetilde{W}_{1}\cdot\widetilde{W}_{2}}\cdot(\widetilde{W}_{1}-\widetilde{W}_{1})^{2}\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<\widetilde{W}_{1}\\}\Bigg{]}=\frac{547}{72000},$

where the exact number can be computed using the distribution of
$\widetilde{W}_{1}$ and $\widetilde{W}_{2}$. We thus have

$\displaystyle F(1/10,9/10)=\frac{547}{7200}.$

For $t=3/5$, when $p_{2}\geq t$ it could either be case (i) or (ii). Thus

$\displaystyle\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq 3/5,W_{1}<W_{2})$
$\displaystyle=\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq
3/5,\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1})$
$\displaystyle\qquad+\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq
3/5,W_{1}<\widetilde{W}_{2}<W_{2}<\widetilde{W}_{1}).$

For the first case,

$\displaystyle\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq
3/5,\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1})$
$\displaystyle=\mathbb{P}\Bigg{(}U_{1}\leq\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}},~{}1-U_{2}\geq\frac{2W_{1}+2W_{2}+2\widetilde{W}_{2}}{5\widetilde{W}_{2}},~{}\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1}\Bigg{)}.$
(22)

One can check that
$\frac{2W_{1}+2W_{2}+2\widetilde{W}_{2}}{5\widetilde{W}_{2}}\geq\frac{6}{5}$
when $\widetilde{W}_{2}<W_{1}<W_{2}$, and that
$\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}}\in[0,1]$, hence by
the tower property and the symmetry of $W_{1},W_{2}$, we know

$\displaystyle\eqref{eq:prob2}$
$\displaystyle=\mathbb{E}\Bigg{[}\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}}\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<W_{1}<W_{2}<\widetilde{W}_{1}\\}\Bigg{]}$
$\displaystyle=\frac{1}{2}\cdot\mathbb{E}\Bigg{[}\mathbb{E}\bigg{[}\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}}\,\bigg{|}\,W_{1},W_{2}\in[\widetilde{W}_{2},\widetilde{W}_{1}],\widetilde{W}_{1},\widetilde{W}_{2}\bigg{]}\cdot\mathbb{P}\big{(}W_{1},W_{2}\in[\widetilde{W}_{2},\widetilde{W}_{1}]\,\big{|}\,\widetilde{W}_{1},\widetilde{W}_{2}\big{)}\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<\widetilde{W}_{1}\\}\Bigg{]}$
$\displaystyle=\frac{1}{2}\cdot\mathbb{E}\Bigg{[}\mathbb{E}\bigg{[}\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}}\,\bigg{|}\,W_{1},W_{2}\in[\widetilde{W}_{2},\widetilde{W}_{1}],\widetilde{W}_{1},\widetilde{W}_{2}\bigg{]}\cdot(\widetilde{W}_{1}-\widetilde{W}_{2})^{2}\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<\widetilde{W}_{1}\\}\Bigg{]}$

Conditional on $\widetilde{W}_{1},\widetilde{W}_{2}$ and the event
$\\{W_{1},W_{2}\in[\widetilde{W}_{2},\widetilde{W}_{1}]\\}$, we know
$W_{1},W_{2}\sim\textrm{Unif}([\widetilde{W}_{2},\widetilde{W}_{1}])$, and are
mutually independent. Applying the tower property again, we have

$\displaystyle\eqref{eq:prob2}$
$\displaystyle=\frac{1}{2}\cdot\mathbb{E}\Bigg{[}\frac{2\widetilde{W}_{1}+\widetilde{W}_{2}}{10\widetilde{W}_{1}}\cdot(\widetilde{W}_{1}-\widetilde{W}_{2})^{2}\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<\widetilde{W}_{1}\\}\Bigg{]}=\frac{47}{4800}.$

For the second case,

$\displaystyle\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq
3/5,W_{1}<\widetilde{W}_{2}<W_{2}<\widetilde{W}_{1})$
$\displaystyle=\mathbb{P}\Bigg{(}U_{1}\leq\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}},~{}1-U_{2}\geq\frac{-3W_{1}+2W_{2}+2\widetilde{W}_{2}}{5\widetilde{W}_{2}},~{}W_{1}<\widetilde{W}_{2}<W_{2}<\widetilde{W}_{1}\Bigg{)}.$
(23)

One can check that
$\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}},\frac{-3W_{1}+2W_{2}+2\widetilde{W}_{2}}{5\widetilde{W}_{2}}\in[0,1]$.
The tower property thus implies

$\displaystyle\eqref{eq:prob3}$
$\displaystyle=\mathbb{E}\Bigg{[}\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}}\cdot\frac{-3W_{1}+2W_{2}+2\widetilde{W}_{2}}{5\widetilde{W}_{2}}\cdot\operatorname{\mathds{1}}\\{W_{1}<\widetilde{W}_{2}<W_{2}<\widetilde{W}_{1}\\}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\mathbb{E}\bigg{[}\frac{W_{1}+W_{2}+\widetilde{W}_{1}}{10\widetilde{W}_{1}}\cdot\frac{-3W_{1}+2W_{2}+2\widetilde{W}_{2}}{5\widetilde{W}_{2}}\,\bigg{|}\,W_{1}<\widetilde{W}_{2}<W_{2}<\widetilde{W}_{1},\widetilde{W}_{1},\widetilde{W}_{2}\bigg{]}$
$\displaystyle\qquad\qquad\cdot\mathbb{P}\big{(}W_{1}<\widetilde{W}_{2}<W_{2}<\widetilde{W}_{1}\,\big{|}\,\widetilde{W}_{1},\widetilde{W}_{2}\big{)}\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<\widetilde{W}_{1}\\}\Bigg{]}=$

Note that conditional on $\widetilde{W}_{1},\widetilde{W}_{2}$ and the event
$\\{W_{1}<\widetilde{W}_{2}<W_{2}<\widetilde{W}_{1}\\}$, $W_{1}$ and $W_{2}$
are mutually independent with
$W_{1}\sim\textrm{Unif}([1/2,\widetilde{W}_{2}])$ and
$W_{2}\sim\textrm{Unif}([\widetilde{W}_{2},\widetilde{W}_{1}])$. We thus have

$\displaystyle\eqref{eq:prob3}$
$\displaystyle=\mathbb{E}\Bigg{[}\frac{5\widetilde{W}_{1}^{2}+35\widetilde{W}_{1}\widetilde{W}_{2}/12+17\widetilde{W}_{2}^{2}/12-7\widetilde{W}_{1}/8-\widetilde{W}_{2}/8-1/4}{50\widetilde{W}_{1}\cdot\widetilde{W}_{2}}\cdot(\widetilde{W}_{2}-1/2)\cdot(\widetilde{W}_{1}-\widetilde{W}_{2})\cdot\operatorname{\mathds{1}}\\{\widetilde{W}_{2}<\widetilde{W}_{1}\\}\Bigg{]}.$

Using the distribution of $\widetilde{W}_{1},\widetilde{W}_{2}$, we have
$\eqref{eq:prob3}=\frac{361}{72000}$. Combining the two cases, we have

$\displaystyle\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq
3/5)=2\cdot\mathbb{P}(p_{1}\leq 1/10,p_{2}\geq 3/5,W_{1}<W_{2})=\frac{2\cdot
47}{4800}+\frac{2\cdot 361}{72000}=\frac{533}{18000}.$

We thus have

$\displaystyle F(1/10,3/5)=\frac{533}{7200}<\frac{547}{7200}=F(1/10,9/10).$

Therefore, $p_{1}$ and $p_{2}$ are not PRDS, concluding the proof of
Proposition 2.4. ∎

###  B.4 Proof of Theorem 2.5

###### Proof of Theorem 2.5.

We use a representation of the BH($q$) procedure communicated in [STS04]: the
rejection set of BH($q$) procedure is $\mathcal{R}=\\{j\colon
p_{j}\leq\widehat{\tau}\\}$, where

$\displaystyle\widehat{\tau}=\sup\bigg{\\{}t\in[0,1]\colon\frac{mt}{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}\leq
t\\}}\leq q\bigg{\\}}.$ (24)

To clarify the dependence on the calibration data, we denote the $p$-values as
$p_{j}=\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j}),$ where for simplicity we denote
$V_{j}^{0}=\widehat{V}_{n+j}=V(X_{n+j},C_{n+j})$ and $W_{j}=w(X_{n+j})$. As we
suppose $\\{C_{n+j}\\}_{j=1}^{n}$ are i.i.d. random varibles, here
$\\{V_{j}^{0}\\}_{j=1}^{m}$ are also i.i.d. random variables. Finally, we
define

$\displaystyle\widehat{F}_{n}(v,u,w)=\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<v\\}}+(w+\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}=v\\}})\cdot
u}{\sum_{i=1}^{n}w(X_{i})+w}$

for any $(v,u,w)\in\mathbb{R}\times[0,1]\times\mathbb{R}^{+}$. Note that
conditional on the training process, $\\{(V_{j}^{0},U_{j},W_{j})\colon 1\leq
j\leq m\\}$ are i.i.d., and independent of $\mathcal{D}_{\textnormal{calib}}$.
We first show the uniform concentration of $\widehat{F}_{n}$ to $F$ defined in
(15).

######  Lemma B.1.

Let $\widehat{F}_{n}$ and $F$ defined as above. Then for any fixed constant
$M>0$, as $n\to\infty$, we have

$\displaystyle\sup_{v\in\mathbb{R},u\in[0,1],w\in[0,M]}\big{|}\widehat{F}_{n}(v,u,w)-F(v,u)\big{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$

###### Proof of Lemma B.1.

The strong law of large numbers ensures
$\frac{1}{n}\sum_{i=1}^{n}w(X_{i})~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}1$.
Thus by definition,

$\displaystyle\bigg{|}\widehat{F}_{n}(v,u,w)-\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<v\\}}+(\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}=v\\}})\cdot
u}{\sum_{i=1}^{n}w(X_{i})}\bigg{|}$
$\displaystyle\leq\frac{w}{\sum_{i=1}^{n}w(X_{i})+w}+w\cdot\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<v\\}}+(w+\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}=v\\}})\cdot
u}{(\sum_{i=1}^{n}w(X_{i}))\cdot(\sum_{i=1}^{n}w(X_{i})+w)}$
$\displaystyle\leq\frac{w}{\sum_{i=1}^{n}w(X_{i})}+\frac{w}{\sum_{i=1}^{n}w(X_{i})},\quad\forall
v\in\mathbb{R},u\in[0,1],w\in[0,M].$

This implies

$\displaystyle\sup_{v\in\mathbb{R},u\in[0,1],w\in[0,M]}\bigg{|}\widehat{F}_{n}(v,u,w)-\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<v\\}}+(\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}=v\\}})\cdot
u}{\sum_{i=1}^{n}w(X_{i})}\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$

On the other hand, the uniform law of large numbers in Lemma D.1 implies

$\displaystyle\sup_{v\in\mathbb{R},u\in[0,1],w\in[0,M]}\bigg{|}\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<v\\}}+(\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}=v\\}})\cdot
u}{\sum_{i=1}^{n}w(X_{i})}-F(v,u)\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$

Putting this two almost sure convergence together completes the proof of Lemma
B.1. ∎

Lemma B.1 forms the basis of proving asymptotic results. In the following, we
study the two asymptotic regimes (i) $n\to\infty$ with $m$ fixed and (ii)
$m,n\to\infty$, separately.

##### Case (i): $m$ fixed, $n\to\infty$.

By Lemma B.1, we know that $\\{p_{j}\\}$ converges almost surely (and
uniformly over all $j=1,\dots,m$) to $\\{p_{j}^{\infty}\\}$, where we define

$\displaystyle p_{j}^{\infty}:=F(V_{j}^{0},U_{j}),$

with $F$ defined in (15) of Theorem 2.5. Note that $\\{p_{j}^{\infty}\\}$ are
i.i.d., and all of them have no point mass since $\\{U_{j}\\}\sim$ Unif([0,1])
are independent of the observations. In the following, we denote as
$\mathcal{R}$ the rejection set $\mathcal{R}$ of BH($q$) with $\\{p_{j}\\}$.
We are to show that $\mathcal{R}$ is asymptotically the same as
$\mathcal{R}^{\infty}$, the rejection set obtained from BH($q$) with
$\\{p_{j}^{\infty}\\}$, in the sense that
$\limsup_{n\to\infty}\mathbb{P}(\mathcal{R}\neq\mathcal{R}^{\infty})=0$. Note
that

$\displaystyle\mathbb{P}(\mathcal{R}\neq\mathcal{R}^{\infty})$
$\displaystyle\leq\sum_{j=1}^{m}\mathbb{P}(j\in\mathcal{R},j\notin\mathcal{R}^{\infty})+\sum_{j=1}^{m}\mathbb{P}(j\notin\mathcal{R},j\in\mathcal{R}^{\infty})$
$\displaystyle\leq\sum_{j=1}^{m}\sum_{\ell=0}^{m}\mathbb{P}(p_{j}\leq\ell
k/m,~{}p_{j}^{\infty}>\ell
k/m)+\sum_{j=1}^{m}\sum_{\ell=0}^{m}\mathbb{P}(p_{j}>\ell
k/m,~{}p_{j}^{\infty}\leq\ell k/m).$

For any fixed $\delta>0$, we have

$\displaystyle\limsup_{n\to\infty}\mathbb{P}(p_{j}\leq\ell
k/m,~{}p_{j}^{\infty}>\ell k/m)$
$\displaystyle\leq\limsup_{n\to\infty}\mathbb{P}(p_{j}\leq\ell
k/m,~{}p_{j}^{\infty}>\ell k/m+\delta)+\limsup_{n\to\infty}\mathbb{P}(\ell
k/m<p_{j}^{\infty}\leq\ell k/m+\delta)$
$\displaystyle=\limsup_{n\to\infty}\mathbb{P}(\ell k/m<p_{j}^{\infty}\leq\ell
k/m+\delta).$

Taking $\delta\to 0$ and noting that $p_{j}^{*}$ does not have point mass at
$\\{\ell k/m\\}$, we have $\limsup_{n\to\infty}\mathbb{P}(p_{j}\leq\ell
k/m,~{}p_{j}^{\infty}>\ell k/m)=0$. Similar arguments also yield
$\limsup_{n\to\infty}\mathbb{P}(p_{j}>\ell k/m,~{}p_{j}^{\infty}\leq\ell
k/m)=0$. Summing over finitely many terms $1\leq j\leq m$ and $0\leq\ell\leq
m$ leads to

$\displaystyle\mathbb{P}(\mathcal{R}\neq\mathcal{R}^{\infty})\to 0.$ (25)

Let $\textnormal{FDR}(\mathcal{R})$, $\textnormal{FDR}(\mathcal{R}^{\infty})$
denote the FDR for $\mathcal{R}$ and $\mathcal{R}^{\infty}$, respectively. As
a result of (25), we have

$\displaystyle\limsup_{n\to\infty}\textnormal{FDR}(\mathcal{R})$
$\displaystyle\leq\limsup_{n\to\infty}\mathbb{E}\big{[}\textnormal{FDP}(\mathcal{R})\cdot\operatorname{\mathds{1}}\\{\mathcal{R}=\mathcal{R}^{\infty}\\}\big{]}+\limsup_{n\to\infty}\mathbb{E}\big{[}\textnormal{FDP}(\mathcal{R})\cdot\operatorname{\mathds{1}}\\{\mathcal{R}\neq\mathcal{R}^{\infty}\\}\big{]}$
$\displaystyle\leq\mathbb{E}\big{[}\textnormal{FDP}(\mathcal{R}^{\infty})\big{]}+\limsup_{n\to\infty}\mathbb{E}\big{[}\operatorname{\mathds{1}}\\{\mathcal{R}\neq\mathcal{R}^{\infty}\\}\big{]}\leq\textnormal{FDR}(\mathcal{R}^{\infty}),$

where the second inequality uses the fact that
$\textnormal{FDP}(\mathcal{R})\leq 1$, and the last inequality uses
$\mathbb{E}\big{[}\textnormal{FDP}(\mathcal{R}^{\infty})\big{]}=\textnormal{FDR}(\mathcal{R}^{\infty})$.
For each $j$, we let $\mathcal{R}_{j\to 0}^{\infty}$ denote the rejection set
of BH($q$) applied to the set of p-values
$\\{p_{1}^{\infty},\dots,p_{j-1}^{\infty},0,p_{j+1}^{\infty},\dots,p_{m}^{\infty}\\}$,
i.e., when we set $p_{j}^{\infty}$ to $0$ while keeping others
$\\{p_{\ell}^{\infty}\\}_{\ell\neq j}$ fixed. Then we know that
$\mathcal{R}^{\infty}=\mathcal{R}_{j\to 0}^{\infty}$ on the event
$\\{j\in\mathcal{R}^{\infty}\\}$. Therefore, the FDR for
$\mathcal{R}^{\infty}$ can be bounded as

$\displaystyle\textnormal{FDR}(\mathcal{R}^{\infty})$
$\displaystyle=\mathbb{E}\bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{j\in\mathcal{R}^{\infty},j\in\mathcal{H}_{0}\\}}{1\vee|\mathcal{R}^{\infty}|}\bigg{]}=\sum_{j=1}^{m}\mathbb{E}\bigg{[}\frac{\operatorname{\mathds{1}}\\{j\in\mathcal{R}^{\infty},j\in\mathcal{H}_{0}\\}}{1\vee|\mathcal{R}^{\infty}_{j\to
0}|}\bigg{]}.$

By the definition of BH($q$) procedure, we know $j\in\mathcal{R}^{\infty}$
implies $p_{j}^{\infty}\leq q|\mathcal{R}^{\infty}|/m$. In the right-handed
side of the above equation, each term can be decomposed as

$\displaystyle\mathbb{E}\bigg{[}\frac{\operatorname{\mathds{1}}\\{j\in\mathcal{R}^{\infty},j\in\mathcal{H}_{0}\\}}{1\vee|\mathcal{R}^{\infty}_{j\to
0}|}\bigg{]}$
$\displaystyle=\sum_{k=1}^{m}\mathbb{E}\bigg{[}\operatorname{\mathds{1}}\\{|\mathcal{R}^{\infty}|=k\\}\frac{\operatorname{\mathds{1}}\\{j\in\mathcal{R}^{\infty},j\in\mathcal{H}_{0}\\}}{k}\bigg{]}$
$\displaystyle\leq\sum_{k=1}^{m}\mathbb{E}\bigg{[}\operatorname{\mathds{1}}\\{|\mathcal{R}_{j\to
0}^{\infty}|=k\\}\frac{\operatorname{\mathds{1}}\\{p_{j}^{\infty}\leq\frac{qk}{m},Y_{n+j}\leq
C_{n+j}\\}}{k}\bigg{]}$
$\displaystyle=\sum_{k=1}^{m}\mathbb{P}\big{(}|\mathcal{R}_{j\to
0}^{\infty}|=k\big{)}\cdot\frac{1}{k}\mathbb{P}\Big{(}p_{j}^{\infty}\leq\frac{qk}{m},Y_{n+j}\leq
C_{n+j}\Big{)},$

where the first equality uses the fact that $(p_{j}^{\infty},Y_{n+j},C_{n+j})$
are independent of all other samples and hence also independent of
$\mathcal{R}_{j\to 0}^{\infty}$; the second line uses the fact that
$\\{|\mathcal{R}^{\infty}|=k,~{}j\in\mathcal{R}^{\infty}\\}$ implies
$\\{|\mathcal{R}_{j\to 0}^{\infty}|=k,~{}p_{j}^{\infty}\leq qk/m\\}$. Due to
the monotonicity of $V(x,y)$ in $y$ and the monotonicity of $F(v,u)$ in $v$,

$\displaystyle\mathbb{P}\Big{(}p_{j}^{\infty}\leq\frac{qk}{m},Y_{n+j}\leq
C_{n+j}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}F\big{(}V(X_{n+j},C_{n+j}),U_{j}\big{)}\leq\frac{qk}{m},Y_{n+j}\leq
C_{n+j}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}F\big{(}V(X_{n+j},Y_{n+j}),U_{j}\big{)}\leq\frac{qk}{m},Y_{n+j}\leq
C_{n+j}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}F\big{(}V(X_{n+j},Y_{n+j}),U_{j}\big{)}\leq\frac{qk}{m}\Big{)}=\frac{qk}{m},$

where the last equality uses the fact that $F(V(X_{n+j},Y_{n+j}),U)\sim$
Unif[0,1] from the definition of $F$, as all the probabilities are taken with
respect to the test distribution $\mathbb{Q}_{X,Y,C}$ and an independent
random variable $U\sim$ Unif([0,1]). Therefore, we obtain

$\displaystyle\textnormal{FDR}(\mathcal{R}^{\infty})\leq\sum_{j=1}^{m}\sum_{k=1}^{m}\mathbb{P}\big{(}|\mathcal{R}_{j\to
0}^{\infty}|=k\big{)}\cdot\frac{q}{m}\leq q,$

which completes the proof of this case.

##### Case (ii): $m,n\to\infty$.

In this case, we are to repeatedly employ the (uniform) strong law of large
numbers to show the asymptotic behavior of the testing procedure. Based on
Lemma B.1, we show the uniform convergence of the criterion in (24).

######  Lemma B.2.

Under the above setup, suppose $\sup_{x\in\mathcal{X}}w(x)\leq M$ for some
constant $M>0$. Then

$\displaystyle\sup_{t\in[0,1]}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t\\}-\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq
t\big{)}\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0,$

as $m,n\to\infty$, where $\mathbb{P}$ is taken with respect to
$V_{j}^{0}=V(X_{n+j},C_{n+j})$ and an independent $U_{j}\sim$ Unif$([0,1])$.

###### Proof of Lemma B.2.

Let $0=t_{0}<t_{1}<\cdots<t_{K}=1$ be a partition of $[0,1]$. Then for each
$t\in[0,1]$, there exists some $k$ such that $t_{k}\leq t<t_{k+1}$, hence

$\displaystyle\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}$ (26)
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t\\}$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k+1}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k}\\}.$ (27)

The upper bound (27) above can be further bounded as

$\displaystyle\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k+1}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k}\\}\bigg{|}$
$\displaystyle\leq\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k+1}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}\bigg{|}$
$\displaystyle\quad+\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k}\\}\bigg{|}.$ (28)

For any fixed $\delta>0$, we have

$\displaystyle\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k+1}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}\bigg{|}$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}\Big{(}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k+1},F(V_{j}^{0},U_{j})>t_{k+1}\\}+\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})>t_{k+1},F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}\Big{)}$
$\displaystyle\leq\operatorname{\mathds{1}}\big{\\{}\sup_{j}\big{|}\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})-F(V_{j}^{0},U_{j})\big{|}\geq\delta\big{\\}}+\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k+1},t_{k+1}+\delta\geq F(V_{j}^{0},U_{j})>t_{k+1}\\}$
$\displaystyle\quad+\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})>t_{k+1},t_{k+1}-\delta<F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}$
$\displaystyle\leq\operatorname{\mathds{1}}\big{\\{}\sup_{j}\big{|}\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})-F(V_{j}^{0},U_{j})\big{|}\geq\delta\big{\\}}+\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{t_{k+1}-\delta\leq
F(V_{j}^{0},U_{j})\leq t_{k+1}+\delta\\}.$

Lemma B.1 implies
$\limsup_{n\to\infty}\operatorname{\mathds{1}}\big{\\{}\sup_{j}\big{|}\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})-F(V_{j}^{0},U_{j})\big{|}\geq\delta\big{\\}}=0$
almost surely. Combining this observation with the decomposition (B.4), we
have

$\displaystyle\limsup_{n\to\infty}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k+1}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k}\\}\bigg{|}$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{t_{k+1}-\delta\leq
F(V_{j}^{0},U_{j})\leq
t_{k+1}+\delta\\}+\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{t_{k}<F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}$

almost surely. Again invoking the (uniform) law of large numbers (c.f. Lemma
D.1 applied without weights to i.i.d. random variables $F(V_{j}^{0},U_{j})$),

$\displaystyle\limsup_{m\to\infty}\sup_{k}$
$\displaystyle\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{t_{k+1}-\delta\leq
F(V_{j}^{0},U_{j})\leq t_{k+1}+\delta\\}-\mathbb{P}\big{(}t_{k+1}-\delta\leq
F(V_{j}^{0},U_{j})\leq t_{k+1}+\delta\big{)}$
$\displaystyle\quad+\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{t_{k}<F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}-\mathbb{P}\big{(}t_{k}<F(V_{j}^{0},U_{j})\leq
t_{k+1}\big{)}\bigg{|}=0$

with probability one. We thus have

$\displaystyle\limsup_{m,n\to\infty}\sup_{k}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k+1}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k}\\}\bigg{|}$
$\displaystyle\leq\sup_{k}\Big{|}\mathbb{P}\big{(}t_{k+1}-\delta\leq
F(V_{j}^{0},U_{j})\leq
t_{k+1}+\delta\big{)}+\mathbb{P}\big{(}t_{k}<F(V_{j}^{0},U_{j})\leq
t_{k+1}\big{)}\Big{|}$ (29)

for any partition $\\{t_{k}\\}$ and $\delta>0$. On the other hand, we note
that since $U_{j}\sim$ Unif[0,1] is independent of the observations,
$F(V_{j}^{0},U_{j})$ are i.i.d. with continuous distributions. Letting
$\delta\to 0$ so that $\\{t_{k}\\}$ be fine enough sends the supremum in (B.4)
to zero. With similar arguments, we can show for the lower bound (26) that

$\displaystyle\limsup_{m,n\to\infty}\sup_{k}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t_{k}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t_{k+1}\\}\bigg{|}=0$

almost surely. Combining the above two results, we have

$\displaystyle\sup_{t\in[0,1]}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t\\}\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$ (30)

Invoking the uniform strong law of large numbers to i.i.d. random variables
$\\{F(V_{j}^{0},U_{j})\\}_{j=1}^{m}$, we have

$\displaystyle\sup_{t\in[0,1]}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t\\}-\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq
t\big{)}\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0,$

hence by the triangular inequality we complete the proof of Lemma B.2. ∎

Recall that in Theorem 2.5, we assumed that there exists some
$t^{\prime}\in(0,1]$ such that

$\displaystyle\frac{\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq
t^{\prime}\big{)}}{t^{\prime}}>\frac{1}{q}.$

We then define

$\displaystyle
t^{*}=\sup\bigg{\\{}t\in[0,1]\colon\frac{\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq
t\big{)}}{t}\geq\frac{1}{q}\bigg{\\}}=\sup\big{\\{}t\in[0,1]\colon
G_{\infty}(t)\leq q\big{\\}},$

where $G_{\infty}(\cdot)$ is defined in Theorem 2.5. It is well-defined and
$t^{*}\geq t^{\prime}$. Fix any $\delta\in(0,t^{\prime})$. By Lemma B.2,

$\displaystyle\sup_{t\in[\delta,1]}\bigg{|}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t\\}}{mt}-\frac{\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq
t\big{)}}{t}\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$
(31)

In particular,
$\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j})\leq
t^{\prime}\\}}{mt^{\prime}}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}\frac{\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq
t^{\prime}\big{)}}{t^{\prime}}>\frac{1}{q}$, hence $\widehat{\tau}\geq
t^{\prime}\geq\delta$ eventually as $m,n\to\infty$. As a result, by the
definition of $\widehat{\tau}$ and Fatou’s lemma, we have

$\displaystyle\limsup_{m,n\to\infty}\textnormal{FDR}$
$\displaystyle=\limsup_{m,n\to\infty}\mathbb{E}\Bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau},j\in\mathcal{H}_{0}\\}}{1\vee\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau}\\}}\Bigg{]}$
$\displaystyle\leq
q\cdot\mathbb{E}\Bigg{[}\limsup_{m,n\to\infty}\frac{1}{m\widehat{\tau}}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau},j\in\mathcal{H}_{0}\\}\Bigg{]}.$

The uniform concentration result (30) in the proof of Lemma B.2 implies

$\displaystyle\limsup_{m,n\to\infty}\bigg{|}\frac{1}{m\widehat{\tau}}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau},j\in\mathcal{H}_{0}\\}-\frac{1}{m\widehat{\tau}}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau},j\in\mathcal{H}_{0}\\}\bigg{|}=0$

almost surely. By the monotonicity of the nonconformity score $V$, we know

$\displaystyle\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{F(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau},j\in\mathcal{H}_{0}\\}$
$\displaystyle=\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}F(V(X_{n+j},C_{n+j}),U_{j})\leq\widehat{\tau},~{}Y_{n+j}\leq
C_{n+j}\big{\\}}$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}F(V(X_{n+j},Y_{n+j}),U_{j})\leq\widehat{\tau}\big{\\}}.$

The uniform strong law of large numbers applied to
$F(V(X_{n+j},Y_{n+j}),U_{j})$ implies

$\displaystyle\limsup_{m,n\to\infty}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}F(V(X_{n+j},Y_{n+j}),U_{j})\leq\widehat{\tau}\big{\\}}-Q\big{(}F(V(X,Y),U)\leq\widehat{\tau}\big{)}\bigg{|}=0$

almost surely, where $Q$ is taken with respect to a new pair of $(X,Y)\sim Q$
and an independent $U\sim$ Unif([0,1]) while viewing $\widehat{\tau}$ as
fixed. Consequently, we have

$\displaystyle\limsup_{m,n\to\infty}\textnormal{FDR}$ $\displaystyle\leq
q\cdot\mathbb{E}\Bigg{[}\limsup_{m,n\to\infty}\frac{Q\big{(}F(V(X,Y),U)\leq\widehat{\tau}\big{)}}{\widehat{\tau}}\Bigg{]}.$

Note that by definition of $F(u,v)$, for any $t\in[0,1]$, we have

$\displaystyle Q\big{(}F(V(X,Y),U)\leq t\big{)}=t.$

This concludes that $\limsup_{m,n\to\infty}\textnormal{FDR}\leq q$.

Furthermore, since $F(V_{j}^{0},U_{j})$ admits a continuous distribution, the
function $t\mapsto\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq t\big{)}$ is
continuous in $t\in[0,1]$. Under the assumption that for any $\epsilon>0$,
there exists some $|t-t^{*}|\leq\epsilon$ such that
$\frac{\mathbb{P}(F(V_{j}^{0},U_{j})\leq t)}{t}>1/q$, the uniform convergence
in (31) implies
$\widehat{\tau}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}t^{*}$.
Let $\delta\in(0,t^{*})$ be any fixed value such that
$\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq\delta\big{)}>0$. Lemma B.2, equation
(30), the uniform strong law of large numbers, together with the lower
boundedness of $\mathbb{P}\big{(}F(V_{j}^{0},U_{j})\leq t\big{)}$ for
$t\geq\delta$ thus ensures

$\displaystyle\sup_{t\in[\delta,1]}\Bigg{|}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t,j\in\mathcal{H}_{0}\\}}{1\vee\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq
t\\}}-\frac{Q\\{F(V(X,C),U)\leq t,Y\leq C\\}}{Q\\{F(V(X,C),U)\leq
t\\}}\Bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$

Since
$\widehat{\tau}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}t^{*}$
and the distribution functions are continuous, the asymptotic FDR is

$\displaystyle\limsup_{m,n\to\infty}\textnormal{FDR}$
$\displaystyle=\limsup_{m,n\to\infty}\mathbb{E}\Bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau},j\in\mathcal{H}_{0}\\}}{1\vee\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau}\\}}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\limsup_{m,n\to\infty}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau},j\in\mathcal{H}_{0}\\}}{1\vee\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau}\\}}\Bigg{]}$
$\displaystyle=\frac{Q\\{F(V(X,C),U)\leq t^{*},Y\leq C\\}}{Q\\{F(V(X,C),U)\leq
t^{*}\\}},$

where the second line follows from the Dominated Convergence Theorem. With
similar arguments, we can show that the asymptotic power of the procedure is

$\displaystyle\limsup_{m,n\to\infty}\text{Power}$
$\displaystyle=\limsup_{m,n\to\infty}\mathbb{E}\Bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{F}_{n}(V_{j}^{0},U_{j},W_{j})\leq\widehat{\tau},j\notin\mathcal{H}_{0}\\}}{1\vee\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{Y_{n+j}>C_{n+j}\\}}\Bigg{]}$
$\displaystyle=\frac{Q\\{F(V(X,C),U)\leq t^{*},Y>C\\}}{Q\\{Y>C\\}}.$

This concludes the proof for the case $m,n\to\infty$. Therefore, we complete
the proof of Theorem 2.5. ∎

##  Appendix C Proofs for finite-sample FDR control

###  C.1 Proof of Theorem 3.1

###### Proof of Theorem 3.1.

We first reduce the FDR for the three choices of $\mathcal{R}$ using the
following lemma. Its proof is deferred to Appendix C.2.

######  Lemma C.1.

Let $\mathcal{R}=\mathcal{R}_{\textnormal{hete}}$ or
$\mathcal{R}=\mathcal{R}_{\textnormal{homo}}$ or
$\mathcal{R}=\mathcal{R}_{\textnormal{dtm}}$ in Algorithm 1. Then
$\mathcal{R}$ satisfies

$\displaystyle{\textnormal{{FDR}}}=\mathbb{E}\Bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}{\\{j\in\mathcal{R},Y_{n+j}\leq
c_{n+j}\\}}}{1\vee|\mathcal{R}|}\Bigg{]}\leq\sum_{j=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j},Y_{n+j}\leq c_{n+j}\\}}}{|\widehat{\mathcal{R}}_{j\to 0}|}\Bigg{]},$
(32)

where $s_{j}=q|\widehat{\mathcal{R}}_{j\to 0}|/m$, and
$\widehat{\mathcal{R}}_{j\to 0}$ is the rejection set we compute in Line 6 of
Algorithm 1.

We now show that each term in the summation (32) is upper bounded by $q/m$.
For convenience, we will call BH($q$) as the BH procedure at nominal level
$q$. Recall that $\widehat{\mathcal{R}}_{j\to 0}$ is the rejection set of
BH($q$) applied to
$\\{p_{1}^{(j)},\dots,p_{j-1}^{(j)},0,p_{j+1}^{(j)},\dots,p_{m}^{(j)}\\}$. For
clarity, we define $\widehat{\mathcal{R}}_{j}$ as the rejection set of BH($q$)
applied to
$\\{p_{1}^{(j)},\dots,p_{j-1}^{(j)},p_{j},p_{j+1}^{(j)},\dots,p_{m}^{(j)}\\}$,
which differs from $\widehat{\mathcal{R}}_{j\to 0}$ in that we use $p_{j}$
instead of $0$ in the $j$-th p-value. By the definition of BH procedure, we
note that

$\displaystyle j\in\widehat{\mathcal{R}}_{j}\quad\textrm{if and only if}\quad
p_{j}\leq s_{j}=\frac{q|\widehat{\mathcal{R}}_{j\to 0}|}{m}.$ (33)

We now define the oracle counterparts of these $p$-values as

$\displaystyle\bar{p}_{j}=\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<{V}_{n+j}\\}}+w(X_{n+j})}{\sum_{i=1}^{n}w(X_{i})+w(X_{n+j})},$
(34)

and

$\displaystyle\bar{p}_{\ell}^{(j)}:=\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<\widehat{V}_{n+\ell}\\}}+w(X_{n+j})\operatorname{\mathds{1}}{\\{{V}_{n+j}<\widehat{V}_{n+\ell}\\}}}{\sum_{i=1}^{n}w(X_{i})+w(X_{n+j})}.$
(35)

These p-values are not computable and are only for the purpose of analysis.
The difference between $\\{p_{j}\\}$ and $\\{\bar{p}_{j}\\}$ (similarly
$\\{p_{\ell}^{(j)}\\}$ versus $\\{\bar{p}_{\ell}^{(j)}\\}$) is only in whether
we use the observed score $\widehat{V}_{n+j}=V(X_{n+j},c_{n+j})$ or the oracle
score $V_{n+j}=V(X_{n+j},Y_{n+j})$; on the other hand, $\widehat{V}_{n+\ell}$
for $\ell\neq j$ are used in both constructions.

Now let $\bar{\mathcal{R}}_{j}$ be the rejection set of BH($q$) procedure
applied to
$\\{\bar{p}_{1}^{(j)},\dots,\bar{p}_{j-1}^{(j)},\bar{p}_{j},\bar{p}_{j+1}^{(j)},\dots,\bar{p}_{m}^{(j)}\\}$.
In the following, we are to show that if $j\in\widehat{\mathcal{R}}_{j}$
(i.e., $p_{j}\leq s_{j}=q|\widehat{\mathcal{R}}_{j\to 0}|/m$) and
$j\in\mathcal{H}_{0}$ (recall that $\mathcal{H}_{0}$ is the random set of null
hypotheses), then $\widehat{\mathcal{R}}_{j}=\bar{\mathcal{R}}_{j}$, i.e.,
changing $p_{j}$ and $\\{p_{\ell}^{(j)}\\}$ to their oracle counterparts
$\bar{p}_{j}$ and $\\{\bar{p}_{\ell}^{(j)}\\}$ does not change the rejection
set of BH($q$).

To see this, the monotinicity of nonconformity scores implies that
$\bar{p}_{j}\leq p_{j}$ on the event $\\{j\in\mathcal{H}_{0}\\}=\\{Y_{n+j}\leq
c_{n+j}\\}$. We then consider two cases for $\ell\neq j$ on the event
$\\{j\in\mathcal{H}_{0},j\in\widehat{\mathcal{R}}_{j}\\}$.

  1. (a)

if $\widehat{V}_{n+\ell}>\widehat{V}_{n+j}$, then
$\bar{p}_{\ell}^{(j)}=p_{\ell}^{(j)}$; this is because in this case
$\operatorname{\mathds{1}}\\{\widehat{V}_{n+j}<\widehat{V}_{n+\ell}\\}=\operatorname{\mathds{1}}\\{{V}_{n+j}<\widehat{V}_{n+\ell}\\}=1$.

  2. (b)

if $\widehat{V}_{n+\ell}\leq\widehat{V}_{n+j}$, from the step-up nature of
BH($q$), we know ${p}_{\ell}^{(j)}\leq{p}_{j}$, hence
$\ell\in\widehat{\mathcal{R}}_{j}$ as well. Therefore, it always holds that

$\displaystyle\bar{p}_{\ell}^{(j)}\leq\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<\widehat{V}_{n+\ell}\\}}+w(X_{n+j})}{\sum_{i=1}^{n}w(X_{i})+w(X_{n+j})}\leq\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<\widehat{V}_{n+j}\\}}+w(X_{n+j})}{\sum_{i=1}^{n}w(X_{i})+w(X_{n+j})}=p_{j}.$

Thus, after modifying $\widehat{V}_{n+j}$ to $V_{n+j}$, the oracle
$\bar{p}_{\ell}^{(j)}$ still does not exceed the observable $p_{j}$.

Summarizing the above two cases, for $\ell\neq j$ such that
$p_{\ell}^{(j)}>p_{j}$, we have $\bar{p}_{\ell}^{(j)}=p_{\ell}^{j}$, while for
$p_{\ell}^{(j)}\leq p_{j}$, we have $\bar{p}_{\ell}^{(j)}\leq p_{j}$. As a
result, the step-up nature of BH($q$) leads to the fact that

$\displaystyle
j\in\mathcal{H}_{0}~{}\text{and}~{}j\in\widehat{\mathcal{R}}_{j}\quad\Rightarrow\quad
j\in\bar{\mathcal{R}}_{j}~{}\text{and}~{}\widehat{\mathcal{R}}_{j}=\bar{\mathcal{R}}_{j}.$
(36)

Finally, we let $\bar{\mathcal{R}}_{j\to 0}$ be the rejection set of BH($q$)
applied to p-values
$\\{\bar{p}_{1}^{(j)},\dots,\bar{p}_{j-1}^{(j)},0,\bar{p}_{j+1}^{j},\dots,\bar{p}_{m}^{(j)}\\}$,
so that $j\in\bar{\mathcal{R}}_{j\to 0}$ determinisitically by default. Then
we have

$\displaystyle\big{\\{}j\in\mathcal{H}_{0},p_{j}\leq
s_{j}=q|\widehat{\mathcal{R}}_{j\to 0}|/m\big{\\}}$
$\displaystyle=\big{\\{}j\in\mathcal{H}_{0},j\in\widehat{\mathcal{R}}_{j}\big{\\}}$
$\displaystyle\subseteq\big{\\{}j\in\mathcal{H}_{0},j\in\bar{\mathcal{R}}_{j}\big{\\}}$
(37)
$\displaystyle=\big{\\{}j\in\mathcal{H}_{0},j\in\bar{\mathcal{R}}_{j},p_{j}\leq
q|\bar{\mathcal{R}}_{j\to 0}|/m\big{\\}},$

where the first line is due to (33), the second line is due to (36), and the
last equality follows from the oracle counterpart to (33). The above inclusion
then implies

$\displaystyle\frac{\operatorname{\mathds{1}}\\{j\in\mathcal{H}_{0},p_{j}\leq
s_{j}\\}}{|\widehat{\mathcal{R}}_{j\to 0}|}$
$\displaystyle\leq\frac{\operatorname{\mathds{1}}\\{j\in\mathcal{H}_{0},\bar{p}_{j}\leq
q|\bar{\mathcal{R}}_{j\to 0}|/m\\}}{|\bar{\mathcal{R}}_{j\to 0}|}.$

Consequently,

$\displaystyle\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j},j\in\mathcal{H}_{0}\\}}}{|\widehat{\mathcal{R}}_{j\to
0}|}\Bigg{]}\leq\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{\bar{p}_{j}\leq\frac{q|\bar{\mathcal{R}}_{j\to
0}|}{m},j\in\mathcal{H}_{0}\\}}}{|\bar{\mathcal{R}}_{j\to
0}|}\Bigg{]}\leq\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{\bar{p}_{j}\leq\frac{q|\bar{\mathcal{R}}_{j\to
0}|}{m}\\}}}{|\bar{\mathcal{R}}_{j\to 0}|}\Bigg{]}.$ (38)

On the right-handed side, $\bar{\mathcal{R}}_{j\to 0}$ only depends on the
oracle p-values $\\{\bar{p}_{\ell}^{(j)}\colon\ell\neq j\\}$ but not
$\bar{p}_{j}$.

We define the event
$\mathcal{E}_{z,j}=\big{\\{}[Z_{1},\dots,Z_{n},Z_{n+j}]=[z_{1},\dots,z_{n},z_{n+j}]\big{\\}}$,
where $Z:=[Z_{1},\dots,Z_{n},Z_{n+j}]$ is an unordered set of all calibration
data $Z_{i}=(X_{i},Y_{i})$, $i=1,\dots,n$ and the unobserved test sample
$n+j$, and $z:=[z_{1},\dots,z_{n},z_{n+j}]$ is the unordered set of their
realized values.

Conditional on $\mathcal{E}_{z,j}$, the only randomness is only with regard to
which sample takes on which value among $[z_{1},\dots,z_{n},z_{n+j}]$. Now
conditional on $\mathcal{E}_{z,j}$, let $I_{j}$ be the index in
$\\{1,\dots,n,n+j\\}$ such that $Z_{n+j}=z_{I_{j}}$. Then $\bar{p}_{j}$ is
measurable with respect to $I_{j}$. On the other hand, due to the independence
among
$\\{Z_{1},\dots,Z_{n},Z_{n+j}\\}\cup\\{\widetilde{Z}_{n+\ell}\\}_{\ell\neq j}$
for $\widetilde{Z}_{n+\ell}=(X_{n+\ell},c_{n+\ell})$ in Theorem 3.1, we know
that $\\{\widetilde{Z}_{n+\ell}\\}_{\ell\neq j}$ is independent of $I_{j}$
given $\mathcal{E}_{z,j}$. Meanwhile, the values of
$\\{\bar{p}_{\ell}^{(j)}\colon\ell\neq j\\}$ are fully decided by the
unordered set $Z$ and $\\{\widetilde{Z}_{n+\ell}\\}_{\ell\neq j}$, which means
$\\{\bar{p}_{\ell}^{(j)}\colon\ell\neq j\\}$ is measurable with respect to
$\mathcal{E}_{z,j}$ and $\\{\widetilde{Z}_{n+\ell}\\}_{\ell\neq j}$. As
$\bar{\mathcal{R}}_{j\to 0}$ is determined by
$\\{\bar{p}_{\ell}^{(j)}\colon\ell\neq j\\}$, we know
$|\bar{\mathcal{R}}_{j\to 0}|$ is measurable with respect to
$\mathcal{E}_{z,j}$ and $\\{\widetilde{Z}_{n+\ell}\\}_{\ell\neq j}$. Putting
these arguments together, we have the following conditional independence
structure:

$\displaystyle\bar{p}_{j}\perp\\!\\!\\!\perp\big{|}\bar{\mathcal{R}}_{j\to
0}\big{|}~{}\,\Big{|}\,~{}\mathcal{E}_{z,j},\quad\forall j.$

This implies

$\displaystyle\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{\bar{p}_{j}\leq\frac{q|\bar{\mathcal{R}}_{j\to
0}|}{m}\\}}}{|\bar{\mathcal{R}}_{j\to
0}|}\,\Big{|}\,\mathcal{E}_{z,j}\Bigg{]}=\frac{F_{z,j}(\frac{q|\bar{\mathcal{R}}_{j\to
0}|}{m})}{|\bar{\mathcal{R}}_{j\to 0}|},$

where $F_{z,j}(t)=\mathbb{P}(p_{j}\leq t{\,|\,}\mathcal{E}_{z,j})$ for
$t\in\mathbb{R}$. We consider the randomized weighted conformal p-value

$\displaystyle{p}_{j}^{*}=\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<{V}_{n+j}\\}}+U_{j}\cdot(w(X_{n+j})+\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}\\{V_{i}=V_{n+j}\\})}{\sum_{i=1}^{n}w(X_{i})+w(X_{n+j})},$

where $p_{j}^{*}{\,|\,}\mathcal{E}_{z}\sim\textrm{Unif}[0,1]$ by the weighted
exchangeability [TFBCR19, HL20]. Since $p_{j}^{*}\leq\bar{p}_{j}$
determinisitically, we have $F_{z,j}(t)\leq\mathbb{P}(p_{j}^{*}\leq
t{\,|\,}\mathcal{E}_{z,j})=t$ for all $t\in\mathbb{R}$. By the tower property,

$\displaystyle\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
c_{n+j},j\in\mathcal{H}_{0}\\}}}{|\widehat{\mathcal{R}}_{j\to
0}|}\Bigg{]}\leq\mathbb{E}\Bigg{[}\frac{F_{z,j}(\frac{q|\bar{\mathcal{R}}_{j\to
0}|}{m})}{|\bar{\mathcal{R}}_{j\to
0}|}\Bigg{]}\leq\mathbb{E}\Bigg{[}\frac{q|\bar{\mathcal{R}}_{j\to
0}|}{m|\bar{\mathcal{R}}_{j\to 0}|}\Bigg{]}=\frac{q}{m}.$

Summing over all $j\in\\{1,\dots,m\\}$ concludes the proof of Theorem 3.1. ∎

###  C.2 Proof of Lemma C.1

###### Proof of Lemma C.1.

We prove the lemma for the three cases separately.

##### Case 1: $\mathcal{R}=\mathcal{R}_{\textnormal{hete}}$.

The arguments for this case resemble the idea of [FL22]. We include the proof
for completeness since here we deal with random hypotheses. By definition,
$r_{\textnormal{hete}}^{*}=|\mathcal{R}|$. Then

$\displaystyle\textnormal{FDR}=\mathbb{E}\Bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}{\\{j\in\mathcal{R},Y_{n+j}\leq
c_{n+j}\\}}}{1\vee|\mathcal{R}|}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\frac{\sum_{j\in\mathcal{H}_{0}}\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j},Y_{n+j}\leq
c_{n+j}\\}}\operatorname{\mathds{1}}{\\{\xi_{j}\leq\frac{|\mathcal{R}|}{|\widehat{\mathcal{R}}_{j\to
0}|}\\}}}{1\vee|\mathcal{R}|}\Bigg{]}.$

Fix any $j\in\\{1,\dots,m\\}$. Once $j\in\mathcal{R}$, in our pruning method,
sending $\xi_{j}\to 0$ while keeping other $\xi$’s unchanged does not change
the rejection set. Therefore, letting $\mathcal{R}_{\xi_{j}\to 0}$ denote the
rejection set obtained by replacing $\xi_{j}$ by $0$ in the pruning step, we
have

FDR
$\displaystyle=\sum_{j=1}^{m}\sum_{k=1}^{m}\mathbb{E}\bigg{[}\frac{\operatorname{\mathds{1}}{\\{|\mathcal{R}|=k\\}}}{k}\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j},Y_{n+j}\leq
c_{n+j}\\}}\operatorname{\mathds{1}}{\\{\xi_{j}\leq{\textstyle\frac{k}{|\widehat{\mathcal{R}}_{j\to
0}|}}\\}}\bigg{]}$
$\displaystyle=\sum_{j=1}^{m}\sum_{k=1}^{m}\mathbb{E}\bigg{[}\frac{\operatorname{\mathds{1}}{\\{|\mathcal{R}_{\xi_{j}\to
0}|=k\\}}}{k}\operatorname{\mathds{1}}{\\{p_{j}\leq s_{j},Y_{n+j}\leq
c_{n+j}\\}}\operatorname{\mathds{1}}{\\{\xi_{j}\leq{\textstyle\frac{k}{|\widehat{\mathcal{R}}_{j\to
0}|}}\\}}\bigg{]}$
$\displaystyle=\sum_{j=1}^{m}\sum_{k=1}^{m}\mathbb{E}\bigg{[}\frac{\operatorname{\mathds{1}}{\\{|\mathcal{R}_{\xi_{j}\to
0}|=k\\}}}{|\widehat{\mathcal{R}}_{j\to
0}|}\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}\bigg{]}=\sum_{j=1}^{m}\mathbb{E}\bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j},Y_{n+j}\leq c_{n+j}\\}}}{|\widehat{\mathcal{R}}_{j\to 0}|}\bigg{]},$

where the third line follows from the fact that $\xi_{j}$ are independent of
$\mathcal{R}_{\xi_{j}\to 0}$, $p_{j}$ and $\widehat{\mathcal{R}}_{j\to 0}$.
This concludes the proof of the heterogeneous case.

##### Case 2: $\mathcal{R}=\mathcal{R}_{\textnormal{homo}}$.

This case uses a conditional PRDS property of
$\\{\xi|\widehat{\mathcal{R}}_{j\to 0}|\\}_{j=1}^{m}$ which we will specify
later. We let $\mathbb{E}_{\mathcal{D}}$ be the conditional expectation given
all the data, so that only the randomness in $\xi$ remains. Also, one still
has $\xi\sim\textrm{Unif}([0,1])$ after conditioning. The tower property
implies $\textnormal{FDR}=\mathbb{E}[\textnormal{FDR}(\mathcal{D})]$, where we
define the conditional FDR

$\displaystyle\textnormal{FDR}(\mathcal{D}):=\mathbb{E}_{\mathcal{D}}\Bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}{\\{j\in\mathcal{R},Y_{n+j}\leq
c_{n+j}\\}}}{1\vee|\mathcal{R}|}\Bigg{]},$

and $\mathbb{E}_{\mathcal{D}}$ is with respect to the randomness in $\xi$
conditional on
$\mathcal{D}=\\{(X_{i},Y_{i})\\}_{i=1}^{n}\cup\\{(X_{n+j},c_{n+j})\\}_{j=1}^{m}$.
Note that $\operatorname{\mathds{1}}\\{p_{j}\leq s_{j}\\}$ are deterministic
conditional on the data. We let $\mathcal{R}^{(1)}=\\{j\colon p_{j}\leq
s_{j}\\}$ be the first-step rejection set, and $\mathcal{H}_{0}=\\{j\colon
Y_{n+j}\leq c_{n+j}\\}$ be the set of null hypotheses, both being
deterministic given the data. Then we have the decomposition

$\displaystyle\textnormal{FDR}(\mathcal{D})$
$\displaystyle=\sum_{k=1}^{m}\mathbb{E}_{\mathcal{D}}\bigg{[}\operatorname{\mathds{1}}\\{|\mathcal{R}|=k\\}\frac{\sum_{j\in\mathcal{R}_{0}\cap\mathcal{H}_{0}}\operatorname{\mathds{1}}{\\{\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k\\}}}{k}\bigg{]}$
$\displaystyle=\sum_{j\in\mathcal{R}^{(1)}\cap\mathcal{H}_{0}}\sum_{k=1}^{m}\mathbb{E}_{\mathcal{D}}\bigg{[}\frac{\operatorname{\mathds{1}}{\\{\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k\\}}}{k}\left(\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq
k\\}-\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq k-1\\}\right)\bigg{]}.$

Fix any $j\in\mathcal{R}^{(1)}\cap\mathcal{H}_{0}$, and let
$m_{1}=|\mathcal{R}^{(1)}|$. Then we know $|\mathcal{R}|\leq m_{1}$
deterministically, and thus

$\displaystyle\operatorname{\mathds{1}}{\\{\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k\\}}\left(\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq
k\\}-\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq k-1\\}\right)=0$

for any $k\geq m_{1}+1$. We then have

$\displaystyle\textnormal{FDR}(\mathcal{D},j)$
$\displaystyle:=\sum_{k=1}^{m}\frac{1}{k}\mathbb{E}_{\mathcal{D}}\big{[}\operatorname{\mathds{1}}{\\{\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k\\}}\left(\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq
k\\}-\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq k-1\\}\right)\big{]}$
$\displaystyle=\sum_{k=1}^{m_{1}}\frac{1}{k}\mathbb{E}_{\mathcal{D}}\big{[}\operatorname{\mathds{1}}{\\{\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k\\}}\left(\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq
k\\}-\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq k-1\\}\right)\big{]}$
$\displaystyle\leq\frac{1}{m_{1}}+\sum_{k=1}^{m_{1}-1}\frac{1}{k}\mathbb{E}_{\mathcal{D}}\big{[}\operatorname{\mathds{1}}{\\{\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k\\}}\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq k\\}\big{]}$
$\displaystyle\qquad\qquad-\sum_{k=1}^{m_{1}-1}\frac{1}{k+1}\mathbb{E}_{\mathcal{D}}\big{[}\operatorname{\mathds{1}}{\\{\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k+1\\}}\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq k\\}\big{]}$
$\displaystyle\leq\frac{1}{m_{1}}+\sum_{k=1}^{m_{1}-1}\bigg{\\{}\frac{\mathbb{P}_{\mathcal{D}}(\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k)}{k}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k\Big{)}$
$\displaystyle\qquad\qquad\qquad\qquad-\frac{\mathbb{P}_{\mathcal{D}}(\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k+1)}{k+1}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k+1\Big{)}\bigg{\\}}.$
(39)

Here $\mathbb{P}_{\mathcal{D}}$ is with respect to the conditional
distribution of $\xi$ given $\mathcal{D}$. We would rely on the PRDS property
of $\xi|\widehat{\mathcal{R}}_{j\to 0}|$ as follows to control
$\textnormal{FDR}(\mathcal{D},j)$.

######  Lemma C.2.

Let $a_{1},\dots,a_{k}\in\mathbb{R}$ be nonnegative fixed constants, and let
$\xi\sim\textnormal{Unif}[0,1]$. Then the random variables
$\\{a_{1}\xi,\dots,a_{j-1}\xi,a_{j+1}\xi,\dots,a_{k}\xi\\}$ are PRDS in
$a_{j}\xi$ for any $j\in\\{1,\dots,k\\}$.

###### Proof of Lemma C.2.

We denote $x_{j}=a_{j}\xi$, and $a_{j}\geq 0$ for all $j=1,\dots,k$. Fix any
$j\in\\{1,\dots,k\\}$. If $a_{j}=0$, then $x_{j}\equiv 0$ hence the
distribution of $X=(x_{1},\dots,x_{k})$ conditional on $x_{j}$ is invatiant to
the value of $\xi$, and the PRDS property naturally follows. If $a_{j}>0$,
then conditional on $x_{j}$, other $p$-values are deterministic with
$x_{\ell}=x_{j}\cdot a_{\ell}/a_{j}$. Now let $D$ be any increasing set, then
for any $x\in[0,a_{j}]$, we have

$\displaystyle\mathbb{P}(X\in
D{\,|\,}x_{j}=x)=\operatorname{\mathds{1}}\big{\\{}(xa_{1}/a_{j},\dots,xa_{k}/a_{j})\in
D\big{\\}},$

which is increasing in the whole range $x\in[0,a_{j}]$. We thus complete the
proof of Lemma C.2. ∎

By Lemma C.2 and the construction of
$\mathcal{R}=\mathcal{R}_{\textnormal{homo}}$, we see that

$\displaystyle\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq
k\Big{)}\leq\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k+1\Big{)},$

hence since $\xi$ is independent of everything else,

$\displaystyle\textnormal{FDR}(\mathcal{D},j)$
$\displaystyle\leq\frac{1}{m_{1}}+\sum_{k=1}^{m_{1}-1}\bigg{\\{}\frac{\mathbb{P}_{\mathcal{D}}(\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k)}{k}-\frac{\mathbb{P}_{\mathcal{D}}(\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k+1)}{k+1}\bigg{\\}}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k\Big{)}$
$\displaystyle=\frac{1}{m_{1}}+\sum_{k=1}^{m_{1}-1}\bigg{\\{}\frac{\min\\{1,k/|\widehat{\mathcal{R}}_{j\to
0}|\\}}{k}-\frac{\min\\{1,(k+1)/|\widehat{\mathcal{R}}_{j\to
0}|\\}}{k+1}\bigg{\\}}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k\Big{)}.$ (40)

If $|\widehat{\mathcal{R}}_{j\to 0}|\geq m_{1}$, then the above inequality
leads to
$\textnormal{FDR}(\mathcal{D},j)\leq\frac{1}{m_{1}}\leq\frac{1}{|\widehat{\mathcal{R}}_{j\to
0}|}$. Otherwise

$\displaystyle\textnormal{FDR}(\mathcal{D},j)$
$\displaystyle\leq\frac{1}{m_{1}}+\sum_{k=|\widehat{\mathcal{R}}_{j\to
0}|}^{m_{1}-1}\bigg{\\{}\frac{1}{k}-\frac{1}{k+1}\bigg{\\}}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k\Big{)}$
$\displaystyle\leq\frac{1}{m_{1}}+\sum_{k=|\widehat{\mathcal{R}}_{j\to
0}|}^{m_{1}-1}\bigg{\\{}\frac{1}{k}-\frac{1}{k+1}\bigg{\\}}\leq\frac{1}{|\widehat{\mathcal{R}}_{j\to
0}|}.$

Putting the above bounds together, we have

$\displaystyle\textnormal{FDR}(\mathcal{D})\leq\sum_{j\in\mathcal{R}^{(1)}\cap\mathcal{H}_{0}}\frac{1}{|\widehat{\mathcal{R}}_{j\to
0}|}=\sum_{j=1}^{m}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j},Y_{n+j}\leq c_{n+j}\\}}}{|\widehat{\mathcal{R}}_{j\to 0}|}.$

Marginalizing over the randomness in $\mathcal{D}$ concludes the proof of the
homogeneous case.

##### Case 3: $\mathcal{R}=\mathcal{R}_{\textnormal{dtm}}$.

Finally we show the deterministic case. Let $m_{1}=|\mathcal{R}_{0}|$ for
$\mathcal{R}_{0}=\\{j\colon p_{j}\leq c_{n+j}\\}$ and let
$[1],[2],\dots,[m_{1}]$ be a reorder of $\mathcal{R}_{0}$ such that
$|\widehat{\mathcal{R}}_{[1]\to 0}|\leq|\widehat{\mathcal{R}}_{[2]\to
0}|\leq\cdots\leq|\widehat{\mathcal{R}}_{[m_{1}]\to 0}|$. Then by definition,
we know $m_{2}:=|\mathcal{R}|$ is the largest index $k$ such that
$|\widehat{\mathcal{R}}_{[k]\to 0}|\leq k$ and
$\mathcal{R}=\\{[1],[2],\dots,[m_{2}]\\}$. Put another way, we have
$|\widehat{\mathcal{R}}_{j\to 0}|\leq|\mathcal{R}|$ for all $j\in\mathcal{R}$.
Thus,

$\displaystyle\mathbb{E}\Bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}{\\{j\in\mathcal{R},Y_{n+j}\leq
c_{n+j}\\}}}{1\vee|\mathcal{R}|}\Bigg{]}$
$\displaystyle\leq\sum_{j=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{j\in\mathcal{R},Y_{n+j}\leq
c_{n+j}\\}}}{1\vee|\widehat{\mathcal{R}}_{j\to
0}|}\Bigg{]}\leq\sum_{j=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j},Y_{n+j}\leq c_{n+j}\\}}}{1\vee|\widehat{\mathcal{R}}_{j\to
0}|}\Bigg{]}.$

This concludes the proof of the third case, and therefore also concludes the
proof of Lemma C.1. ∎

###  C.3 Proof of Proposition 3.4

###### Proof of Proposition 3.4.

We start by describing the BH procedure and our procedure using a similar
characterization as in [STS04]. First, our first-step rejection set computed
in Line 8 of Algorithm 1 can be written as $\widehat{\mathcal{R}}_{j\to
0}=\\{j\\}\cup\\{\ell\colon p_{\ell}^{(j)}\leq\widehat{\tau}_{j}\\}$, where

$\displaystyle\widehat{\tau}_{j}=\sup\bigg{\\{}t\in[0,1]\colon\frac{mt}{1+\sum_{\ell\neq
j}\operatorname{\mathds{1}}\\{p_{\ell}^{(j)}\leq t\\}}\leq q\bigg{\\}}.$ (41)

The rejection set of BH($q$) is $\mathcal{R}_{\textnormal{BH}}=\\{j\colon
p_{j}\leq\widehat{\tau}\\}$, where $\\{p_{j}\\}$ are defined in (4), and

$\displaystyle\widehat{\tau}=\sup\bigg{\\{}t\in[0,1]\colon\frac{mt}{\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{\ell}\leq
t\\}}\leq q\bigg{\\}}.$ (42)

Also, under the conditions of Proposition 3.4, there are no ties within
$\\{V(X_{i},Y_{i})\\}_{i=1}^{n}\cup\\{V(X_{n+j},Y_{j})\\}_{j=1}^{m}$ or
$\\{V(X_{i},Y_{i})\\}_{i=1}^{n}\cup\\{V(X_{n+j},c_{n+j})\\}_{j=1}^{m}$ almost
surely. Thus, the p-values (4) can be written as

$\displaystyle
p_{j}=\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<\widehat{V}_{n+j}\\}}+w(X_{n+j})\cdot
U_{j}}{\sum_{i=1}^{n}w(X_{i})+w(X_{n+j})}.$ (43)

To proceed, with a slight abuse of notation, we define the cumulative
distribution function of $V(X,Y)$ under the target distribution:

$\displaystyle F(v)=Q(V(X,Y)\leq v)=Q(V(X,Y)<v),\quad v\in\mathbb{R},$

with the probability over $(X,Y)\sim Q$. Because the distribution of $V(X,Y)$
under $Q$ has no point mass, $F(\cdot)$ is continuous and increasing in $v$.
For convenience, in the following we denote $p_{j}^{(j)}:=p_{j}$, and define

$\displaystyle V_{j}^{0}:=V(X_{n+j},c_{n+j})=\widehat{V}_{n+j},\quad
p_{j}^{\infty}:=F(V_{j}^{0}).$

The following lemma can be derived similarly as Lemma B.1, whose proof is
omitted for brevity.

######  Lemma C.3.

For any fixed constant $M>0$, as $n\to\infty$ and possibly $m\to\infty$, we
have

$\displaystyle\limsup_{n\to\infty}\sup_{j\geq
1}\big{|}p_{j}-p_{j}^{\infty}\big{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0,\quad\limsup_{n\to\infty}\sup_{j\geq
1,\ell\geq
1}\big{|}p_{\ell}^{(j)}-p_{\ell}^{\infty}\big{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$

In particular, the almost sure convergence in Lemma C.3 is uniform over all
observed p-values, which can be countably many when we consider $m\to\infty$.
We then prove the two cases separately.

##### Case (i): $m$ fixed, $n\to\infty$.

We let $\mathcal{R}^{\infty}$ be the rejection set of BH($q$) with
$\\{p_{j}^{\infty}\\}$. Then by the uniform convergence of $\\{p_{j}\\}$ to
$\\{p_{j}^{\infty}\\}$ and the no-point-mass condition on the distribution of
$V_{j}^{0}$ (and hence $p_{j}^{\infty}$), the same arguments as in the proof
of case (i) in Theorem 2.5 yield

$\displaystyle\lim_{n\to\infty}\mathbb{P}(\mathcal{R}_{\textnormal{BH}}\neq\mathcal{R}^{\infty})=1.$

We let $\widehat{\mathcal{R}}_{j}$ be the rejection set of BH($q$) from
$\\{p_{\ell}^{(j)}\\}_{1\leq\ell\leq m}$, with the convention that
$p_{j}^{(j)}=p_{j}$. We also denote $\widehat{\mathcal{R}}_{j\to 0}$ as the
rejection set of BH($q$) applied to
$\\{p_{1}^{(j)},\dots,p_{j-1}^{(j)},0,p_{j+1}^{(j)},\dots,p_{m}^{(j)}$. Then
by the property of the BH procedure, we know

$\displaystyle p_{j}\leq s_{j}=q|\widehat{\mathcal{R}}_{j\to
0}|/m\quad\Leftrightarrow\quad j\in\widehat{\mathcal{R}}_{j}.$ (44)

For each $j\in\\{1,\dots,m\\}$, due to the uniform convergence of
$\\{p_{\ell}^{(j)}\\}$ to $\\{p_{j}^{\infty}\\}$, we similarly have
$\lim_{n\to\infty}\mathbb{P}(\widehat{\mathcal{R}}_{j}\neq\mathcal{R}^{\infty})=1.$
Then taking a union bound over $j\in\\{1,\dots,m\\}$ yields

$\displaystyle\lim_{n\to\infty}\mathbb{P}(\widehat{\mathcal{R}}_{j}=\mathcal{R}^{\infty}~{}\text{for
all }j)=1.$ (45)

Recall that $\mathcal{R}^{(1)}=\\{j\colon p_{j}\leq s_{j}\\}$ is first-step
selection set. Thus

$\displaystyle\mathbb{P}\big{(}\mathcal{R}^{(1)}=\mathcal{R}^{\infty}\big{)}=\mathbb{P}\big{(}\\{j\colon
p_{j}\leq
s_{j}\\}=\\{j\in\widehat{\mathcal{R}}_{j}\\}=\mathcal{R}^{\infty}\big{)}\to 1$

as $n\to\infty$, where the first equality uses (44), and the last convergence
uses (45). We then have

$\displaystyle\lim_{n\to\infty}\mathbb{P}(E_{n})=1,\quad\textrm{where}\quad
E_{n}:=\big{\\{}\mathcal{R}^{(1)}=\mathcal{R}^{\infty}=\widehat{\mathcal{R}}_{j}~{}\text{for
all }j\big{\\}}.$

On the event $E_{n}$, we know that $|\widehat{\mathcal{R}}_{j\to
0}|=|\widehat{\mathcal{R}}_{j}|=|\mathcal{R}^{\infty}|=|\mathcal{R}^{(1)}|$
for any $j\in\mathcal{R}^{\infty}$. Therefore, for heterogeneous pruning, we
have

$\displaystyle\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},\xi_{j}|\widehat{\mathcal{R}}_{j\to
0}|\leq|\mathcal{R}^{\infty}|\big{\\}}=\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}j\in\mathcal{R}^{\infty},\xi_{j}|\mathcal{R}^{\infty}|\leq|\mathcal{R}^{\infty}|\big{\\}}=|\mathcal{R}^{\infty}|$

since $\xi_{j}\in[0,1]$; second, if we adopt the homogeneous pruning,

$\displaystyle\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq|\mathcal{R}^{\infty}|\big{\\}}=\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}j\in\mathcal{R}^{\infty},\xi|\mathcal{R}^{\infty}|\leq|\mathcal{R}^{\infty}|\big{\\}}=|\mathcal{R}^{\infty}|$

since $\xi\in[0,1]$; finally, if we adopt the determinisitic pruning,

$\displaystyle\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},|\widehat{\mathcal{R}}_{j\to
0}|\leq|\mathcal{R}^{\infty}|\big{\\}}=\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}j\in\mathcal{R}^{\infty},|\mathcal{R}^{\infty}|\leq|\mathcal{R}^{\infty}|\big{\\}}=|\mathcal{R}^{\infty}|.$

At the same time, for any $r\in\mathbb{N}$, the heterogeneous pruning
satisfies

$\displaystyle\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},\xi_{j}|\widehat{\mathcal{R}}_{j\to 0}|\leq
r\big{\\}}\leq\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}\leq
s_{j}\\}=|\mathcal{R}^{(1)}|=|\mathcal{R}^{\infty}|,$

and similarly the homogeneous pruning satisfies
$\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}\leq
s_{j},\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq
r\\}\leq|\mathcal{R}^{(1)}|=|\mathcal{R}^{\infty}|,$ and the deterministic
pruning satisfies $\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}\leq
s_{j},|\widehat{\mathcal{R}}_{j\to 0}|\leq
r\\}\leq|\mathcal{R}^{(1)}|=|\mathcal{R}^{\infty}|.$ Thus, by definition we
have
$r_{\textnormal{hete}}^{*}=r_{\textnormal{homo}}^{*}=r_{\textnormal{dtm}}^{*}=|\mathcal{R}^{\infty}|$
and

$\displaystyle\mathcal{R}_{\textnormal{hete}}=\big{\\{}j\colon p_{j}\leq
s_{j},~{}\xi_{j}|\widehat{\mathcal{R}}_{j\to 0}|\leq
r_{\textnormal{hete}}^{*}\big{\\}}=\mathcal{R}^{(1)}=\mathcal{R}^{\infty}=\mathcal{R}_{\textnormal{homo}}=\mathcal{R}_{\textnormal{dtm}}$

on the event $E_{n}$, hence completing the proof of case (i).

##### Case (ii): $m,n\to\infty$.

Our first result is the convergence of the rejection threshold
$\widehat{\tau}_{j}$ and $\tau$ (c.f. (41) and (42)) depending on the
following lemma.

######  Lemma C.4.

Under the conditions of Proposition 3.4,

$\displaystyle\sup_{t\in[0,1]}\sup_{j\geq
1}\bigg{|}\frac{1}{m}\sum_{\ell=1}^{n}\operatorname{\mathds{1}}\\{p_{\ell}^{(j)}\leq
t\\}-\mathbb{P}(F(V_{j}^{0})\leq
t)\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0,\quad\sup_{t\in[0,1]}\bigg{|}\frac{1}{m}\sum_{\ell=1}^{n}\operatorname{\mathds{1}}\\{p_{\ell}\leq
t\\}-\mathbb{P}(F(V_{j}^{0})\leq
t)\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0,$

as $m,n\to\infty$, where the supremum is over countably many $j$, and
$\mathbb{P}$ is over the distribution of test samples.

The proof of Lemma C.4 follows exactly the same argument as Lemma B.2 in the
proof of Theorem 2.5, relying on the uniform convergence of
$\\{p_{\ell}^{(j)}\\}_{\ell\neq j}$ and $\\{p_{j}\\}$ to
$\\{p_{j}^{\infty}\\}$ as well as the continuous distribution of
$p_{j}^{\infty}$. We omit the proof here for brevity.

Given that there exists some $t^{\prime}\in(0,1]$ such that
$\frac{\mathbb{P}(F(V_{j}^{0})\leq t)}{t}>1/q$, taking any fixed
$\delta\in(0,1)$, we have

$\displaystyle\sup_{t\in[\delta,1]}\bigg{|}\frac{\sum_{\ell=1}^{n}\operatorname{\mathds{1}}\\{p_{\ell}\leq
t\\}}{mt}-\frac{\mathbb{P}(F(V_{j}^{0})\leq
t)}{t}\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0$

and

$\displaystyle\sup_{t\in[\delta,1]}\sup_{j\geq
1}\bigg{|}\frac{1+\sum_{\ell\neq
j}\operatorname{\mathds{1}}\\{p_{\ell}^{(j)}\leq
t\\}}{mt}-\frac{\mathbb{P}(F(V_{j}^{0})\leq
t)}{t}\bigg{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$

Since $t^{*}=\sup\\{t\colon\frac{t}{\mathbb{P}(F(V_{j}^{0})\leq t)}\leq q\\}$
is not an isolated point of this set, we know that both $\widehat{\tau}_{j}$
and $\widehat{\tau}$ are eventually within a neighborhood around $t^{*}$; to
be specific, the above uniform convergence result guarantees the uniform
convergence of the criteria:

$\displaystyle\widehat{\tau}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}t^{*},\quad\sup_{j\geq
1}\big{|}\widehat{\tau}_{j}-t^{*}\big{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$
(46)

Therefore, we have

$\displaystyle\limsup_{m,n\to\infty}\sup_{j\geq
1}\bigg{|}\frac{|\widehat{\mathcal{R}}_{j\to
0}|}{m}-\mathbb{P}\big{(}F(V_{j}^{0})\leq t^{*}\big{)}\bigg{|}$
$\displaystyle=\limsup_{m,n\to\infty}\sup_{j\geq
1}\bigg{|}\frac{1}{m}+\frac{1}{m}\sum_{\ell\neq
j}\operatorname{\mathds{1}}\\{p_{\ell}^{(j)}\leq\widehat{\tau}_{j}\\}-\mathbb{P}\big{(}F(V_{j}^{0})\leq
t^{*}\big{)}\bigg{|}$ $\displaystyle\leq\limsup_{m,n\to\infty}\sup_{j\geq
1}\bigg{|}\frac{1}{m}\sum_{\ell=1}^{m}\operatorname{\mathds{1}}\\{p_{\ell}^{\infty}\leq\widehat{\tau}_{j}\\}-\mathbb{P}\big{(}F(V_{j}^{0})\leq
t^{*}\big{)}\bigg{|}$ $\displaystyle=\limsup_{m,n\to\infty}\sup_{j\geq
1}\bigg{|}\mathbb{P}\big{(}F(V_{j}^{0})\leq\widehat{\tau}_{j}\big{)}-\mathbb{P}\big{(}F(V_{j}^{0})\leq
t^{*}\big{)}\bigg{|}=0,$ (47)

where the second line uses the uniform convergence in Lemma C.4, the third
line uses the uniform law of large numbers for distribution functions of
i.i.d. random variables $p_{\ell}^{\infty}=F(V_{\ell}^{0})$, and the last
equality follows from the uniform convergence of $\widehat{\tau}_{j}$ to
$t^{*}$ in (46) as well as the continuity of the distribution function of
$F(V_{j}^{0})$. For the convenience of reference, with a slight abuse of
notation, we denote $G_{\infty}(t)=\mathbb{P}(F(V_{j}^{0})\leq t)$, so that
(C.3) implies $|\widehat{\mathcal{R}}_{j\to 0}|/m$ converges to
$G_{\infty}(t^{*})$ uniformly, and as $m,n\to\infty$,

$\displaystyle\sup_{j\geq 1}\big{|}c_{n+j}-q\cdot
G_{\infty}(t^{*})\big{|}=q\cdot\sup_{j\geq
1}\big{|}|\widehat{\mathcal{R}}_{j\to
0}|/m-G_{\infty}(t^{*})\big{|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$

From the definition of $t^{*}$ and the continuity of $G_{\infty}$, we have
$G_{\infty}(t^{*})/t^{*}=1/q$.

In the following, we show that the first-step rejection set
$\mathcal{R}^{(1)}:=\\{j\colon p_{j}\leq s_{j}\\}$ is asymptotically the same
as $\mathcal{R}_{\textnormal{BH}}$, i.e.,
$\limsup_{m,n\to\infty}\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{BH}}|}{m}=0$
almost surely. We define ${d}_{j}^{\textnormal{CC}}=p_{j}-s_{j}$,
$d_{j}^{\textnormal{BH}}=p_{j}-\widehat{\tau}$ and
$d_{j}^{\infty}=p_{j}^{\infty}-t^{*}$ for $j\in\\{1,\dots,m\\}$, for which
we’ve shown that $\sup_{j\geq
1}\big{|}{d}_{j}^{\textnormal{CC}}-d_{j}^{\infty}\big{|}\to 0$ and
$\sup_{j\geq 1}\big{|}d_{j}^{\textnormal{BH}}-d_{j}^{\infty}\big{|}\to 0$
almost surely. We also define

$\displaystyle\delta_{n}=\sup_{j\geq
1}\big{\\{}|{d}_{j}^{\textnormal{CC}}-d_{j}^{\infty}|\big{\\}}\vee\sup_{j\geq
1}\big{\\{}|d_{j}^{\textnormal{BH}}-d_{j}^{\infty}|\big{\\}},$

which obeys $\delta_{n,m}\to 0$ almost surely as $m,n\to\infty$. Therefore,
for any fixed $\delta>0$,

$\displaystyle\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{BH}}|}{m}$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}\big{|}\operatorname{\mathds{1}}\\{p_{j}\leq
s_{j}\\}-\operatorname{\mathds{1}}\\{p_{j}\leq\widehat{\tau}\\}\big{|}$ (48)
$\displaystyle\leq\operatorname{\mathds{1}}\\{\delta_{n}>\delta\\}+\frac{\operatorname{\mathds{1}}\\{\delta_{n}\leq\delta\\}}{m}\sum_{j=1}^{m}\big{|}\operatorname{\mathds{1}}\\{d_{j}^{\textnormal{CC}}\leq
0,d_{j}^{\textnormal{BH}}>0\\}+\operatorname{\mathds{1}}\\{d_{j}^{\textnormal{CC}}>0,d_{j}^{\textnormal{BH}}\leq
0\\}\big{|}$
$\displaystyle\leq\operatorname{\mathds{1}}\\{\delta_{n}>\delta\\}+\frac{\operatorname{\mathds{1}}\\{\delta_{n}\leq\delta\\}}{m}\sum_{j=1}^{m}\big{|}\operatorname{\mathds{1}}\\{-\delta<d_{j}^{\infty}\leq\delta\\}+\operatorname{\mathds{1}}\\{-\delta<d_{j}^{\infty}\leq\delta\\}\big{|}$
$\displaystyle\leq\operatorname{\mathds{1}}\\{\delta_{n}>\delta\\}+\frac{2}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{-\delta<d_{j}^{\infty}\leq\delta\\},$

where the third line uses the fact that $\delta_{n}\leq\delta$,
$d_{j}^{\textnormal{CC}}\leq 0$ and $d_{j}^{\textnormal{BH}}>0$ implies
$d_{j}^{\infty}\in(-\delta,\delta]$, and similarly for the other term. Above,
we know
$\operatorname{\mathds{1}}\\{\delta_{n}>\delta\\}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0$
since $\delta_{n}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0$
as $m,n\to\infty$. By the strong law of large numbers, we have

$\displaystyle\frac{2}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{-\delta<d_{j}^{\infty}\leq\delta\\}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}\mathbb{P}\big{(}F(V_{j}^{0})\in(-\delta+t^{*},\delta+t^{*}]\big{)}.$

Since the distribution of $F(V_{j}^{0})$ is continuous, the arbitrariness of
$\delta>0$ yields
$\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{BH}}|}{m}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0.$

We then proceed to show that the proportion of the hypotheses filterd out in
the second step is negligible, i.e.,
$\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{homo}}|}{m}~{}{\stackrel{{\scriptstyle\textrm{P}}}{{\to}}}~{}0$,
and
$\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{homo}}|}{|\mathcal{R}^{(1)}|}~{}{\stackrel{{\scriptstyle\textrm{P}}}{{\to}}}~{}0$.
For any fixed $\delta>0$,

$\displaystyle\limsup_{m,n\to\infty}\bigg{|}\frac{|\mathcal{R}^{(1)}|}{m}-\mathbb{P}\big{(}F(V_{j}^{0})\leq
t^{*}\big{)}\bigg{|}$
$\displaystyle\leq\limsup_{m,n\to\infty}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}\leq
s_{j}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}^{\infty}\leq
t^{*}\\}\bigg{|}+\limsup_{m,n\to\infty}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}^{\infty}\leq
t^{*}\\}-\mathbb{P}\big{(}F(V_{j}^{0})\leq t^{*}\big{)}\bigg{|}$
$\displaystyle=\limsup_{m,n\to\infty}\bigg{|}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}\leq
s_{j}\\}-\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{p_{j}^{\infty}\leq
t^{*}\\}\bigg{|}$
$\displaystyle\leq\limsup_{m,n\to\infty}\operatorname{\mathds{1}}\\{\delta_{n}>\delta\\}+\limsup_{m,n\to\infty}\frac{\operatorname{\mathds{1}}\\{\delta_{n}\leq\delta\\}}{m}\sum_{j=1}^{m}\big{|}\operatorname{\mathds{1}}\\{p_{j}\leq
s_{j}\\}-\operatorname{\mathds{1}}\\{p_{j}^{\infty}\leq t^{*}\\}\big{|}$
$\displaystyle\leq\limsup_{m,n\to\infty}\operatorname{\mathds{1}}\\{\delta_{n}>\delta\\}+\limsup_{m,n\to\infty}\frac{\operatorname{\mathds{1}}\\{\delta_{n}\leq\delta\\}}{m}\sum_{j=1}^{m}\big{|}\operatorname{\mathds{1}}\\{-\delta<d_{j}^{\infty}\leq\delta\\}+\operatorname{\mathds{1}}\\{-\delta<d_{j}^{\infty}\leq\delta\\}\big{|}$
$\displaystyle\leq\limsup_{m,n\to\infty}\frac{1}{m}\sum_{j=1}^{m}\big{|}\operatorname{\mathds{1}}\\{-\delta<d_{j}^{\infty}\leq\delta\\}+\operatorname{\mathds{1}}\\{-\delta<d_{j}^{\infty}\leq\delta\\}\big{|}$
$\displaystyle\leq 2\mathbb{P}\big{(}t^{*}-\delta\leq F(V_{j}^{0})\leq
t^{*}+\delta\big{)},$

where the first equality uses the strong law of large numbers; the arguments
starting from the third line follow similar ideas as those in (48); the
second-last inequality uses
$\operatorname{\mathds{1}}\\{\delta_{n}>\delta\\}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0$,
and the last inequality again uses the strong law of large numbers. Therefore,
by the arbitrariness of $\delta>0$, we have

$\displaystyle\limsup_{m,n\to\infty}\bigg{|}\frac{|\mathcal{R}^{(1)}|}{m}-\mathbb{P}\big{(}F(V_{j}^{0})\leq
t^{*}\big{)}\bigg{|}=0$ (49)

almost surely. Combined with the previous result that
$\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{BH}}|}{m}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0$,
we also have
$\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{BH}}|}{|\mathcal{R}^{(1)}|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0$
and
$\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{BH}}|}{|\mathcal{R}_{\textnormal{BH}}|}~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}0$,
hence proving the first two parts in case (ii) of Proposition 3.4.

We now fix any $\delta\in(0,1)$, and denote the event

$\displaystyle
E(\delta)=\Bigg{\\{}\sup_{j}\bigg{|}\frac{|\widehat{\mathcal{R}}_{j\to
0}|}{m}-G_{\infty}(t^{*})\bigg{|}>\delta\Bigg{\\}}\bigcup\Bigg{\\{}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j}\big{\\}}<(1-\delta/2)G_{\infty}(t^{*})\Bigg{\\}}.$

Then the uniform concentration (C.3) and (49) implies
$\mathbb{P}(E(\delta))\to 0$ as $m,n\to\infty$. Let $r=\lfloor(1-\delta)\cdot
m\cdot G_{\infty}(t^{*})\rfloor\geq(1-2\delta)\cdot m\cdot G_{\infty}(t^{*})$
when $m$ is sufficiently large. Then

$\displaystyle\mathbb{P}\Bigg{(}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq r\big{\\}}\geq r\Bigg{)}$
$\displaystyle\geq\mathbb{P}\big{(}E(\delta)^{c}\big{)}\cdot\mathbb{P}\Bigg{(}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq r\big{\\}}\geq
r\,\Big{|}\,E(\delta)^{c}\Bigg{)}$
$\displaystyle\geq\mathbb{P}\big{(}E(\delta)^{c}\big{)}\cdot\mathbb{P}\Bigg{(}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},\xi\leq{\textstyle\frac{r}{|\widehat{\mathcal{R}}_{j\to
0}|}}\big{\\}}\geq(1-\delta/2)G_{\infty}(t^{*})\,\Big{|}\,E(\delta)^{c}\Bigg{)}$
$\displaystyle\geq\mathbb{P}\big{(}E(\delta)^{c}\big{)}\cdot\mathbb{P}\Bigg{(}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},\xi\leq{\textstyle\frac{(1-2\delta)mG_{\infty}(t^{*})}{(1+\delta)mG_{\infty}(t^{*})}}\big{\\}}\geq(1-\delta/2)G_{\infty}(t^{*})\,\Big{|}\,E(\delta)^{c}\Bigg{)}$
$\displaystyle=\mathbb{P}\big{(}E(\delta)^{c}\big{)}\cdot\mathbb{P}\Bigg{(}\xi\leq{\textstyle\frac{(1-2\delta)mG_{\infty}(t^{*})}{(1+\delta)mG_{\infty}(t^{*})}},~{}\text{and}~{}\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j}\big{\\}}\geq(1-\delta/2)G_{\infty}(t^{*})\,\Big{|}\,E(\delta)^{c}\Bigg{)}$

when $m$ is sufficiently large, where the second inequality uses
$r\leq(1-\delta/2)\cdot m\cdot G_{\infty}(t)$, and the third inequality
follows from $|\widehat{\mathcal{R}}_{j\to 0}|\leq(1+\delta)\cdot m\cdot
G_{\infty}(t^{*})$ and
$\frac{1}{m}\sum_{j=1}^{m}\operatorname{\mathds{1}}\\{\widehat{p}_{j}\leq
s_{j}\\}=|\mathcal{R}^{(1)}|/m\geq(1-\delta/2)G_{\infty}(t^{*})$ on the event
$E(\delta)^{c}$. Since $\xi$ is independent of $E(\delta)$, we have

$\displaystyle\mathbb{P}\Bigg{(}\sum_{j=1}^{m}\operatorname{\mathds{1}}\big{\\{}p_{j}\leq
s_{j},\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq r\big{\\}}\geq
r\Bigg{)}\geq\mathbb{P}\big{(}E(\delta)^{c}\big{)}\cdot\mathbb{P}\Big{(}\xi\leq{\textstyle\frac{(1-2\delta)mG_{\infty}(t^{*})}{(1+\delta)mG_{\infty}(t^{*})}}\,\Big{|}\,E(\delta)^{c}\Big{)}\geq\mathbb{P}\big{(}E(\delta)^{c}\big{)}\cdot\frac{1-2\delta}{1+\delta}.$

By the definition of $r^{*}_{\textnormal{homo}}$, for any $\delta\in(0,1/2)$,
we have

$\displaystyle\limsup_{m,n\to\infty}\mathbb{P}\Big{(}r_{\textnormal{homo}}^{*}\geq\lfloor(1-\delta)mG_{\infty}(t^{*})\rfloor\Big{)}\geq\frac{1-\delta}{1+\delta}.$

Since
$|\mathcal{R}^{(1)}|/m~{}{\stackrel{{\scriptstyle\textnormal{a.s.}}}{{\to}}}~{}G_{\infty}(t^{*})>0$,
we have

$\displaystyle\limsup_{m,n\to\infty}\mathbb{P}\bigg{(}\frac{r_{\textnormal{homo}}^{*}}{|\mathcal{R}^{(1)}|}\geq
1-\delta\bigg{)}\geq\frac{1-2\delta}{1+\delta}.$

Finally, for any $0<\gamma<\delta$, applying the above inequality leads to

$\displaystyle\limsup_{m,n\to\infty}\mathbb{P}\bigg{(}\frac{r_{\textnormal{homo}}^{*}}{|\mathcal{R}^{(1)}|}\geq
1-\delta\bigg{)}\geq\limsup_{m,n\to\infty}\mathbb{P}\bigg{(}\frac{r_{\textnormal{homo}}^{*}}{|\mathcal{R}^{(1)}|}\geq
1-\gamma\bigg{)}\geq\frac{1-2\gamma}{1+\gamma}.$

Note that $r_{\textnormal{homo}}^{*}=|\mathcal{R}_{\textnormal{homo}}|$, and
that $\mathcal{R}_{\textnormal{homo}}\subset\mathcal{R}^{(1)}$. Thus,

$\displaystyle\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{homo}}|}{|\mathcal{R}^{(1)}|}=\frac{|\mathcal{R}^{(1)}|-|\mathcal{R}_{\textnormal{homo}}|}{|\mathcal{R}^{(1)}|}=1-\frac{r_{\textnormal{homo}}^{*}}{|\mathcal{R}^{(1)}|}.$

Sending $\gamma\to 0$, we conclude the proof of
$\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{homo}}|}{|\mathcal{R}^{(1)}|}~{}{\stackrel{{\scriptstyle\textrm{P}}}{{\to}}}~{}0$
and
$\frac{|\mathcal{R}^{(1)}\bigtriangleup\mathcal{R}_{\textnormal{homo}}|}{m}~{}{\stackrel{{\scriptstyle\textrm{P}}}{{\to}}}~{}0$.
∎

###  C.4 Proof of Theorem 3.5

###### Proof of Theorem 3.5.

For clarity, throughout this proof, we denote the p-values used in the
algorithm as

$\displaystyle\widehat{p}_{j}$
$\displaystyle=\frac{\sum_{i=1}^{n}\widehat{w}(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<\widehat{V}_{n+j}\\}}+\widehat{w}(X_{n+j})}{\sum_{i=1}^{n}\widehat{w}(X_{i})+\widehat{w}(X_{n+j})},$
$\displaystyle\widehat{p}_{\ell}^{(j)}$
$\displaystyle=\frac{\sum_{i=1}^{n}\widehat{w}(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<\widehat{V}_{n+\ell}\\}}+\widehat{w}(X_{n+j})\operatorname{\mathds{1}}{\\{\widehat{V}_{n+j}<\widehat{V}_{n+\ell}\\}}}{\sum_{i=1}^{n}\widehat{w}(X_{i})+\widehat{w}(X_{n+j})},\quad\ell\neq
j,$

which uses the estimated weights $\widehat{w}(\cdot)$. We keep the definition
of $p_{j}$ and $p_{\ell}^{(j)}$ which uses the ground truth $w(\cdot)$ and are
not available. We call BH($q$) the BH procedure at nominal level $q$. We also
define

$\displaystyle\widetilde{p}_{j}$
$\displaystyle=\frac{\sum_{i=1}^{n}\widehat{w}(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<{V}_{n+j}\\}}+\widehat{w}(X_{n+j})}{\sum_{i=1}^{n}\widehat{w}(X_{i})+\widehat{w}(X_{n+j})},$
$\displaystyle\widetilde{p}_{\ell}^{(j)}$
$\displaystyle=\frac{\sum_{i=1}^{n}\widehat{w}(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<\widehat{V}_{n+\ell}\\}}+\widehat{w}(X_{n+j})\operatorname{\mathds{1}}{\\{{V}_{n+j}<\widehat{V}_{n+\ell}\\}}}{\sum_{i=1}^{n}\widehat{w}(X_{i})+\widehat{w}(X_{n+j})},\quad\ell\neq
j$

as the counterparts of $\\{\bar{p}_{j}\\}$ and $\\{\bar{p}_{j}^{\ell}\\}$ we
used in the proof of Theorem 3.1 (c.f. (34) and (35) for their definitions).
Accordingly, we let $\widetilde{\mathcal{R}}_{j}$ be the rejection set from
BH($q$) procedure with
$\\{\widetilde{p}_{1}^{(j)},\dots,\widetilde{p}_{j-1}^{(j)},\widetilde{p}_{j},\widetilde{p}_{j+1}^{(j)},\dots,\widetilde{p}_{m}^{(j)}\\}$,
and let $\widetilde{\mathcal{R}}_{j\to 0}$ be the rejection set from BH($q$)
procedure with
$\\{\widetilde{p}_{1}^{(j)},\dots,\widetilde{p}_{j-1}^{(j)},0,\widetilde{p}_{j+1}^{(j)},\dots,\widetilde{p}_{m}^{(j)}\\}$.

Since $\widehat{w}(\cdot)$ is independent of the calibration and test sample,
we view it as a fixed function throughout. The following Lemma C.5 is parallel
to Lemma C.1 in the proof of Theorem 3.1 (c.f. Appendix C.1). The only
difference between Lemma C.1 and Lemma C.5 is that we replace $w(\cdot)$ with
$\widehat{w}(\cdot)$. Since the proof of Lemma C.1 only uses the randomness in
$\\{\xi_{j}\\}$ and $\xi$, which are independent of the observations, it still
goes through for estimated weights. We thus omit the proof of Lemma C.5 for
brevity.

######  Lemma C.5.

Let $\mathcal{R}=\mathcal{R}_{\textnormal{hete}}$ or
$\mathcal{R}=\mathcal{R}_{\textnormal{homo}}$ or
$\mathcal{R}=\mathcal{R}_{\textnormal{dtm}}$ in Algorithm 1 with estimated
weights. Then

$\displaystyle\mathbb{E}\Bigg{[}\frac{\sum_{j=1}^{m}\operatorname{\mathds{1}}{\\{j\in\mathcal{R},Y_{n+j}\leq
c_{n+j}\\}}}{1\vee|\mathcal{R}|}\Bigg{]}\leq\sum_{j=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{\widehat{p}_{j}\leq
s_{j},Y_{n+j}\leq c_{n+j}\\}}}{|\widehat{\mathcal{R}}_{j\to 0}|}\Bigg{]},$
(50)

where $c_{n+j}=q|\widehat{\mathcal{R}}_{j\to 0}|/m$, and
$\widehat{\mathcal{R}}_{j\to 0}$ is the rejection set in Line 8 of Algorithm 1
computed with $\widehat{p}_{j}$ and $\widehat{p}_{\ell}^{(j)}$.

To bound the right-handed side of (50), we note that the arguments up to (38)
in the proof of Theorem 3.1 do not rely on $w(\cdot)$ being the true covariate
shift function. Thus, exactly the same arguments imply

$\displaystyle\textnormal{FDR}\leq\sum_{j=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{\widetilde{p}_{j}\leq\frac{q|\widetilde{\mathcal{R}}_{j\to
0}|}{m}\\}}}{|\widetilde{\mathcal{R}}_{j\to 0}|}\Bigg{]}.$ (51)

Define the event
$\mathcal{E}_{z,j}=\big{\\{}[Z_{1},\dots,Z_{n},Z_{n+j}]=[z_{1},\dots,z_{n},z_{n+j}]\big{\\}}$,
where $[Z_{1},\dots,Z_{n},Z_{n+j}]$ is an unordered set of all calibration
data $Z_{i}=(X_{i},Y_{i})$, $i=1,\dots,n$ and the unobserved test sample
$n+j$, and $z:=[z_{1},\dots,z_{n},z_{n+j}]$ is the unordered set of their
currently realized values. Since $\widehat{w}(\cdot)$ is fixed and
$\widetilde{\mathcal{R}}_{j\to 0}$ only depends on
$\\{\widetilde{p}_{1}^{(j)},\dots,\widetilde{p}_{j-1}^{(j)},0,\widetilde{p}_{j+1}^{(j)},\dots,\widetilde{p}_{m}^{(j)}\\}$,
we note that $\widetilde{\mathcal{R}}_{j\to 0}$ is invariant up to permutation
of $\\{(X_{i},Y_{i})\\}_{i=1}^{n}\cup\\{(X_{n+j},Y_{n+j})\\}$. That is,
$\widetilde{\mathcal{R}}_{j\to 0}$ is fully determined by $\mathcal{E}_{z,j}$.
Then for each $j$, we have

$\displaystyle\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{\widetilde{p}_{j}\leq\frac{q|\widetilde{\mathcal{R}}_{j\to
0}|}{m}\\}}}{|\widetilde{\mathcal{R}}_{j\to 0}|}\Bigg{]}$
$\displaystyle=\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\operatorname{\mathds{1}}\\{|\widetilde{\mathcal{R}}_{j\to
0}|=k\\}\frac{\operatorname{\mathds{1}}{\\{\widetilde{p}_{j}\leq\frac{qk}{m}\\}}}{k}\Bigg{]}$
$\displaystyle=\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}\\{|\widetilde{\mathcal{R}}_{j\to
0}|=k\\}}{k}\cdot\mathbb{P}\Big{(}\widetilde{p}_{j}\leq\frac{qk}{m}\,\Big{|}\,\mathcal{E}_{z,j}\Big{)}\Bigg{]}$
(52)

In what follows, we are to bound the FDR by studying the difference between
$\widetilde{p}_{j}$ with estimated weights versus $\bar{p}_{j}$, i.e., what we
would have should $w(\cdot)$ be available. For simplicity, we write

$\displaystyle\widehat{W}_{-}$
$\displaystyle=\sum_{i=1}^{n}\widehat{w}(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<{V}_{n+j}\\}}+\widehat{w}(X_{n+j}),\quad\widehat{W}_{+}=\sum_{i=1}^{n}\widehat{w}(X_{i})\operatorname{\mathds{1}}{\\{V_{i}>{V}_{n+j}\\}},$
$\displaystyle W_{-}$
$\displaystyle=\sum_{i=1}^{n}{w}(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<{V}_{n+j}\\}}+{w}(X_{n+j}),\quad
W_{+}=\sum_{i=1}^{n}{w}(X_{i})\operatorname{\mathds{1}}{\\{V_{i}>{V}_{n+j}\\}}.$

Then
$\widehat{W}_{-}+\widehat{W}_{+}=\sum_{i=1}^{n}\widehat{w}(X_{i})+\widehat{w}(X_{n+j})$
and $W_{-}+W_{+}=\sum_{i=1}^{n}{w}(X_{i})+{w}(X_{n+j})$. Recall that
$\widehat{\gamma}:=\sup_{x}\\{\frac{\widehat{w}(x)}{w(x)}\vee\frac{w(x)}{\widehat{w}(x)}\\}$
is independent of all the data hence can be viewed as fixed. Since
$\widehat{\gamma}^{-1}\leq\widehat{w}(x)/w(x)\leq\widehat{\gamma}$, we know
$W_{-}\leq\widehat{\gamma}\widehat{W}_{-}$ and
$W_{+}\geq\widehat{\gamma}^{-1}\widehat{W}_{+}$. Also, recall that
$\bar{p}_{j}=\frac{\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}{\\{V_{i}<{V}_{n+j}\\}}+w(X_{n+j})}{\sum_{i=1}^{n}w(X_{i})+w(X_{n+j})}$
is the counterpart with the true weight function. Thus, on the event
$\big{\\{}\widetilde{p}_{j}=\frac{\widehat{W}_{-}}{\widehat{W}_{-}+\widehat{W}_{+}}\leq\frac{qk}{m}\big{\\}}$,
it holds that

$\displaystyle\bar{p}_{j}=\frac{W_{-}}{W_{-}+W_{+}}\leq\frac{\widehat{\gamma}^{2}}{\widehat{\gamma}^{2}+\widehat{W}_{+}/\widehat{W}_{-}}\leq\frac{\widehat{\gamma}^{2}}{\widehat{\gamma}^{2}+\frac{m}{qk}-1}.$

We have shown in the proof of Theorem 3.1 (c.f. Appendix C.1) that
$\mathbb{P}(\bar{p}_{j}\leq t{\,|\,}\mathcal{E}_{z,j})\leq t$ for all
$t\in\mathbb{R}$ that is adapted to $\mathcal{E}_{z,j}$. Thus

$\displaystyle\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}\\{|\widetilde{\mathcal{R}}_{j\to
0}|=k\\}}{k}\cdot\mathbb{P}\Big{(}\widetilde{p}_{j}\leq\frac{qk}{m}\,\Big{|}\,\mathcal{E}_{z,j}\Big{)}\Bigg{]}$
$\displaystyle\leq\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}\\{|\widetilde{\mathcal{R}}_{j\to
0}|=k\\}}{k}\cdot\mathbb{P}\Big{(}\bar{p}_{j}\leq\frac{\widehat{\gamma}^{2}}{\widehat{\gamma}^{2}+\frac{m}{qk}-1}\,\Big{|}\,\mathcal{E}_{z,j}\Big{)}\Bigg{]}$
$\displaystyle\leq\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}\\{|\widetilde{\mathcal{R}}_{j\to
0}|=k\\}}{k}\cdot\frac{\widehat{\gamma}^{2}}{\widehat{\gamma}^{2}+\frac{m}{qk}-1}\Bigg{]}\leq\max_{k=1,\dots,m}\bigg{\\{}\frac{\widehat{\gamma}^{2}/k}{\widehat{\gamma}^{2}+\frac{m}{qk}-1}\bigg{\\}}=\frac{q}{m}\cdot\frac{\widehat{\gamma}^{2}}{1+q(\widehat{\gamma}^{2}-1)/m}.$

Finally, combining (51), (C.4) and the above bound, we have

$\displaystyle\textnormal{FDR}\leq
q\cdot\mathbb{E}\bigg{[}\frac{\widehat{\gamma}^{2}}{1+q(\widehat{\gamma}^{2}-1)/m}\bigg{]},$

which completes the proof of Theorem 3.1. ∎

###  C.5 Proof of Theorem 6.5

###### Proof of Theorem 6.5.

Similar to Lemma C.1, we use the following lemma as an intermediate step. Its
proof is in Appendix C.6.

######  Lemma C.6.

Let $\mathcal{R}=\mathcal{R}_{\textnormal{hete}}$ or
$\mathcal{R}=\mathcal{R}_{\textnormal{homo}}$ or
$\mathcal{R}=\mathcal{R}_{\textnormal{dtm}}$ in Algorithm 1. Then

$\displaystyle\mathbb{E}\bigg{[}\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{1\vee|\mathcal{R}|}\,\big{|}\,\mathcal{H}_{0}\bigg{]}\leq\sum_{j\in\mathcal{H}_{0}}\mathbb{E}\bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}}{|\widehat{\mathcal{R}}_{j\to
0}|}\,\bigg{|}\,\mathcal{H}_{0}\bigg{]},$ (53)

where $s_{j}=q|\widehat{\mathcal{R}}_{j\to 0}|/m$, and
$\widehat{\mathcal{R}}_{j\to 0}$ is the first-step rejection set we obtain in
Line 8 of Algorithm 2.

Throughout this proof, we always condition on $\mathcal{H}_{0}$ and omit such
dependence in our notations for simplicity. Note that
$\widehat{\mathcal{R}}_{j\to 0}$ only depends on
$\\{p_{\ell}^{(j)}\\}_{\ell\neq j}$, which is measurable with respect to the
unordered set $Z=[Z_{1},\dots,Z_{n},Z_{n+j}]$ and $\\{X_{n+\ell}\\}_{\ell\neq
j}$, where $Z_{i}=(X_{i},Y_{i})$ for $i=1,\dots,n+m$. We denote

$\displaystyle\mathcal{E}_{z,j}:=\big{\\{}[Z_{1},\dots,Z_{n},Z_{n+j}]=z\big{\\}},\quad
z=[z_{1},\dots,z_{n},z_{n+j}]$

as the event that the unordered set $[Z_{1},\dots,Z_{n},Z_{n+j}]$ takes on
(the unordered set of) their realized values $z=[z_{1},\dots,z_{n},z_{n+j}]$.
Thus, conditional on the event $\mathcal{E}_{z,j}$, the only randomness in
$p_{j}$ is which values among $z_{1},\dots,z_{n},z_{n+j}$ that
$Z_{1},\dots,Z_{n},Z_{n+j}$ take; such information, on the other hand, does
not affect $\\{p_{\ell}^{(j)}\\}_{\ell\neq j}$. As a result, we have the
conditional independence

$\displaystyle\operatorname{\mathds{1}}{\\{p_{j}\leq
c_{n+j}\\}}\perp\\!\\!\\!\perp|\widehat{\mathcal{R}}_{j\to
0}|~{}\,\big{|}\,~{}\mathcal{E}_{z,j},\quad\forall j\in\mathcal{H}_{0}.$ (54)

Therefore, by the tower property,

$\displaystyle\mathbb{E}\bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}}{|\widehat{\mathcal{R}}_{j\to
0}|}\,\Big{|}\,\mathcal{E}_{z,j}\bigg{]}=\mathbb{E}\Bigg{[}\frac{\mathbb{P}\big{(}p_{j}\leq
s_{j}\,\big{|}\,\mathcal{E}_{z,j},|\widehat{\mathcal{R}}_{j\to
0}|\big{)}}{|\widehat{\mathcal{R}}_{j\to
0}|}\,\Big{|}\,\mathcal{E}_{z,j}\Bigg{]}=\mathbb{E}\Bigg{[}\frac{F_{j}(s_{j})}{|\widehat{\mathcal{R}}_{j\to
0}|}\,\Big{|}\,\mathcal{E}_{z,j}\Bigg{]},$

where we denote $F_{j}(t)=\mathbb{P}(p_{j}\leq t{\,|\,}\mathcal{E}_{z,j})$ for
any fixed $t\in[0,1]$. Finally, by the covariate shift condition in Assumption
6.1, for any $j\in\mathcal{H}_{0}$ and any $i=1,\dots,n,n+j$, we have the
weighted exchangeability similar to (18), which implies

$\displaystyle\mathbb{P}(Z_{n+j}=z_{i}{\,|\,}\mathcal{E}_{z,j})=\frac{w(z_{i})}{\sum_{i=1}^{n}w(x_{i})+w(x_{n+j})}.$

Let $[1],[2],\dots,[n+1]$ be a permutation of $1,\dots,n,n+j$ such that
$V_{[1]}\leq V_{[2]}\leq\cdots V_{[n+1]}$. By the definition of $p_{j}$, we
know that conditional on $\mathcal{E}_{z,j}$,

$\displaystyle
F_{j}(t)=\sum_{k=1}^{n}\frac{w(z_{[k]})}{\sum_{i=1}^{n}w(x_{i})+w(x_{n+j})}\operatorname{\mathds{1}}\bigg{\\{}\sum_{j=1}^{k}\frac{w(z_{[j]})}{\sum_{i=1}^{n}w(x_{i})+w(x_{n+j})}\leq
t\bigg{\\}}\leq t$

for any $t\in[0,1]$. Invoking Lemma C.6, we thus have

$\displaystyle\textnormal{FDR}\leq\sum_{j\in\mathcal{H}_{0}}\mathbb{E}\Bigg{[}\frac{s_{j}}{|\widehat{\mathcal{R}}_{j\to
0}|}\,\Big{|}\,\mathcal{E}_{z,j}\Bigg{]}\leq
q\cdot\frac{|\mathcal{H}_{0}|}{m},$

which concludes the proof of Theorem 6.5. ∎

###  C.6 Proof of Lemma C.6

###### Proof of Lemma C.6.

We prove the three pruning methods using similar arguments as the proof of
Lemma C.1.

##### Case 1: $\mathcal{R}=\mathcal{R}_{\textnormal{hete}}$.

By definition, we know that
$r^{*}_{\textnormal{hete}}=|\mathcal{R}_{\textnormal{hete}}|=|\mathcal{R}|$.
Then

$\displaystyle\mathbb{E}\bigg{[}\frac{|\mathcal{R}\cap\mathcal{H}_{0}|}{1\vee|\mathcal{R}|}\,\big{|}\,\mathcal{H}_{0}\bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\frac{\sum_{j\in\mathcal{H}_{0}}\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}\operatorname{\mathds{1}}{\\{\xi_{j}\leq\frac{|\mathcal{R}|}{|\widehat{\mathcal{R}}_{j\to
0}|}\\}}}{1\vee|\mathcal{R}|}\,\Bigg{|}\,\mathcal{H}_{0}\Bigg{]}.$

Note that once $j\in\mathcal{R}$, sending $\xi_{j}\to 0$ while keeping
$\\{\xi_{\ell}\\}_{\ell\neq j}$ unchanged does not change the rejection set.
That is, $\mathcal{R}=\mathcal{R}_{\xi_{j}\to 0}$ if $j\in\mathcal{R}$, where

$\displaystyle\mathcal{R}_{\xi_{j}\to 0}$
$\displaystyle=\\{j\\}\cup\Big{\\{}\ell\colon p_{\ell}\leq
s_{\ell},~{}\xi_{\ell}|\widehat{\mathcal{R}}_{\ell\to 0}|\leq
r_{j,\textnormal{hete}}^{*}\Big{\\}},~{}~{}r_{j,\textnormal{hete}}^{*}:=\max\Big{\\{}r\colon
1+\sum_{\ell\neq j}\operatorname{\mathds{1}}{\\{p_{\ell}\leq
s_{\ell},\,\xi_{\ell}|\widehat{\mathcal{R}}_{\ell\to 0}|\leq r\\}}\geq
r\Big{\\}}.$

and we recall that $\widehat{\mathcal{R}}_{\ell\to 0}$ is the first-step
rejection set. We then have

FDR
$\displaystyle=\sum_{j\in\mathcal{H}_{0}}\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{|\mathcal{R}|=k\\}}}{k}\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}\operatorname{\mathds{1}}\big{\\{}\xi_{j}\leq{\textstyle\frac{k}{|\widehat{\mathcal{R}}_{j\to
0}|}}\big{\\}}\Bigg{]}$
$\displaystyle=\sum_{j\in\mathcal{H}_{0}}\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{|\mathcal{R}_{\xi_{j}\to
0}|=k\\}}}{k}\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}\operatorname{\mathds{1}}\big{\\{}\xi_{j}\leq{\textstyle\frac{k}{|\widehat{\mathcal{R}}_{j\to
0}|}}\big{\\}}\Bigg{]}$
$\displaystyle\leq\sum_{j\in\mathcal{H}_{0}}\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{|\mathcal{R}_{\xi_{j}\to
0}|=k\\}}}{k}\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}\cdot\frac{k}{|\widehat{\mathcal{R}}_{j\to 0}|}\Bigg{]}$
$\displaystyle=\sum_{j\in\mathcal{H}_{0}}\sum_{k=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{|\mathcal{R}_{\xi_{j}\to
0}|=k\\}}}{|\widehat{\mathcal{R}}_{j\to
0}|}\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}\Bigg{]}=\sum_{j\in\mathcal{H}_{0}}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}}{|\widehat{\mathcal{R}}_{j\to 0}|}\Bigg{]},$

where the third line follows from the tower property, and that $\xi_{j}$ are
independent of $\mathcal{R}_{\xi_{j}\to 0}$, $p_{j}$,
$\widehat{\mathcal{R}}_{j\to 0}$.

##### Case 2: $\mathcal{R}=\mathcal{R}_{\textnormal{homo}}$.

We will again use the conditional PRDS property of
$\\{\xi|\widehat{\mathcal{R}}_{j\to 0}|\\}_{j=1}^{m}$ which we proved in Lemma
C.2. We let $\mathbb{E}_{\mathcal{D}}$ be the conditional expectation given
all the calibration and test data (and $\mathcal{H}_{0}$), so that only the
randomness in $\xi$ remains, under which one still has
$\xi\sim\textrm{Unif}[0,1]$. The tower property implies
$\textnormal{FDR}=\mathbb{E}[\textnormal{FDR}(\mathcal{D}){\,|\,}\mathcal{H}_{0}]$,
where we define the conditional FDR as

$\displaystyle\textnormal{FDR}(\mathcal{D}):=\mathbb{E}_{\mathcal{D}}\Bigg{[}\frac{\sum_{j\in\mathcal{H}_{0}}\operatorname{\mathds{1}}{\\{j\in\mathcal{R}\\}}}{1\vee|\mathcal{R}|}\,\Big{|}\,\mathcal{H}_{0}\Bigg{]}.$

Note that $\operatorname{\mathds{1}}\\{p_{j}\leq s_{j}\\}$ are deterministic
conditional on the data. Recall that $\mathcal{R}^{(1)}=\\{j\colon p_{j}\leq
s_{j}\\}$ and $\mathcal{H}_{0}$ are both deterministic given the data. Using
the same arguments as in the proof of Lemma C.1 up to (C.2),

$\displaystyle\textnormal{FDR}(\mathcal{D},j)$
$\displaystyle:=\sum_{k=1}^{m}\frac{1}{k}\mathbb{E}_{\mathcal{D}}\big{[}\operatorname{\mathds{1}}{\\{\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k\\}}\left(\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq
k\\}-\operatorname{\mathds{1}}\\{|\mathcal{R}|\leq k-1\\}\right)\big{]}$
$\displaystyle\leq\frac{1}{m_{1}}+\sum_{k=1}^{m_{1}-1}\bigg{\\{}\frac{\mathbb{P}_{\mathcal{D}}(\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k)}{k}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k\Big{)}$
$\displaystyle\qquad\qquad\qquad\qquad-\frac{\mathbb{P}_{\mathcal{D}}(\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k+1)}{k+1}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k+1\Big{)}\bigg{\\}}$

By Lemma C.2, we know that conditioning on all the data,
$\\{\xi|\widehat{\mathcal{R}}_{\ell\to 0}|\\}_{\ell\neq j}$ is PRDS in
$\xi|\widehat{\mathcal{R}}_{j\to 0}|$. Then by the construction of
$\mathcal{R}=\mathcal{R}_{\textnormal{homo}}$, we see that

$\displaystyle\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq
k\Big{)}\leq\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k+1\Big{)},$

hence since $\xi$ is independent of everything else,

$\displaystyle\textnormal{FDR}(\mathcal{D},j)$
$\displaystyle\leq\frac{1}{m_{1}}+\sum_{k=1}^{m_{1}-1}\bigg{\\{}\frac{\mathbb{P}_{\mathcal{D}}(\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k)}{k}-\frac{\mathbb{P}_{\mathcal{D}}(\xi|\widehat{\mathcal{R}}_{j\to
0}|\leq k+1)}{k+1}\bigg{\\}}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k\Big{)}$
$\displaystyle=\frac{1}{m_{1}}+\sum_{k=1}^{m_{1}-1}\bigg{\\{}\frac{\min\\{1,k/|\widehat{\mathcal{R}}_{j\to
0}|\\}}{k}-\frac{\min\\{1,(k+1)/|\widehat{\mathcal{R}}_{j\to
0}|\\}}{k+1}\bigg{\\}}\mathbb{P}_{\mathcal{D}}\Big{(}|\mathcal{R}|\leq
k\,\Big{|}\,\xi|\widehat{\mathcal{R}}_{j\to 0}|\leq k\Big{)}.$

This is exactly the same as (C.2). Hence following the same arguments as in
the proof of Lemma C.1, we conclude the proof of the homogeneous case.

##### Case 3: $\mathcal{R}=\mathcal{R}_{\textnormal{dtm}}$.

In this case, similar to the proof of Lemma C.1, we know that
$|\widehat{\mathcal{R}}_{j\to 0}|\leq|\mathcal{R}|$ deterministically for all
$j\in\mathcal{R}$. Thus,

$\displaystyle\mathbb{E}\Bigg{[}\frac{\sum_{j\in\mathcal{H}_{0}}\operatorname{\mathds{1}}{\\{j\in\mathcal{R}\\}}}{1\vee|\mathcal{R}|}\Bigg{]}$
$\displaystyle\leq\sum_{j\in\mathcal{H}_{0}}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{j\in\mathcal{R}\\}}}{1\vee|\widehat{\mathcal{R}}_{j\to
0}|}\Bigg{]}\leq\sum_{j=1}^{m}\mathbb{E}\Bigg{[}\frac{\operatorname{\mathds{1}}{\\{p_{j}\leq
s_{j}\\}}}{1\vee|\widehat{\mathcal{R}}_{j\to 0}|}\Bigg{]},$

where the last inequality uses the fact that $j\in\mathcal{R}$ implies
$p_{j}\leq s_{j}$ for any $j$. This concludes the proof of the third case, and
therefore the proof of Lemma C.6. ∎

##  Appendix D Supporting lemmas

The following lemma establishes the uniform strong law of large numbers with
weights. The proof is standard which we include here for completeness.

######  Lemma D.1 (Uniform strong law of large numbers).

Let $P$ and $\widetilde{P}$ be two distributions over
$\mathcal{X}\times\mathcal{Y}$, related by a covariate shift
$\frac{{\,\mathrm{d}}\widetilde{P}}{{\,\mathrm{d}}P}(x,y)=w(x)$ for some
function $w\colon\mathcal{X}\to\mathbb{R}^{+}$, and
$\frac{{\,\mathrm{d}}\widetilde{\mathbb{P}}}{{\,\mathrm{d}}\mathbb{P}}$ is the
Radon–Nikodym derivative. Let $\\{(X_{i},Y_{i})_{i=1}^{n}\\}$ be a sequence of
i.i.d. samples from $P$, and
$f\colon\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ be any fixed function. Then
it holds almost surely that

$\displaystyle\limsup_{n\to\infty}\sup_{t\in\mathbb{R}}~{}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}\\{f(X_{i},Y_{i})\leq
t\\}-\widetilde{P}\big{(}f(X,Y)\leq t\big{)}\bigg{|}=0.$

###### Proof of Lemma D.1.

For simplicity, we denote

$\displaystyle\widetilde{F}_{n}(t)=\frac{1}{n}\sum_{i=1}^{n}w(X_{i})\operatorname{\mathds{1}}\\{f(X_{i},Y_{i})\leq
t\\},\quad\widetilde{F}(t)=\widetilde{P}(f(X,Y)\leq t),\quad t\in\mathbb{R}.$

Then by the law of large numbers, for any fixed $t\in\mathbb{R}$,
$\widetilde{F}_{n}(t)\to\widetilde{F}(t)$ almost surely as $n\to\infty$.

Let $\epsilon>0$ be any fixed constant. Then we can pick a finite sequence of
real numbers $t_{1}<t_{2}<\cdots<t_{m}$ such that
$\widetilde{F}(t_{1})\leq\epsilon$, $\widetilde{F}(t_{m})\geq 1-\epsilon$, and
$\widetilde{F}(t_{k+1})-\widetilde{F}(t_{k})\leq\epsilon$. For any
$t\in[t_{1},t_{m})$, there exists some $1\leq k\leq m$ such that
$t\in[t_{k},t_{k+1})$. Then we know
$\widetilde{F}_{n}(t_{k})\leq\widetilde{F}_{n}(t)\leq\widetilde{F}_{n}(t_{k+1})$
and $\widetilde{F}(t_{k})\leq\widetilde{F}(t)\leq\widetilde{F}(t_{k+1})$. This
implies

$\displaystyle\widetilde{F}_{n}(t)-\widetilde{F}(t)$
$\displaystyle\leq\widetilde{F}_{n}(t_{k+1})-\widetilde{F}(t_{k})\leq\big{|}\widetilde{F}_{n}(t_{k+1})-\widetilde{F}(t_{k+1})\big{|}+\widetilde{F}(t_{k+1})-\widetilde{F}(t_{k})\leq\big{|}\widetilde{F}_{n}(t_{k+1})-\widetilde{F}(t_{k+1})\big{|}+\epsilon,$

where we use the triangular inequality in the second inequality. Similarly

$\displaystyle\widetilde{F}_{n}(t)-\widetilde{F}(t)\geq\widetilde{F}_{n}(t_{k})-\widetilde{F}(t_{k+1})\geq\widetilde{F}_{n}(t_{k})-\widetilde{F}(t_{k})+\widetilde{F}(t_{k})-\widetilde{F}(t_{k+1})\geq-\big{|}\widetilde{F}_{n}(t_{k})-\widetilde{F}(t_{k})\big{|}-\epsilon.$

They together lead to
$|\widetilde{F}_{n}(t)-\widetilde{F}(t)|\leq\big{|}\widetilde{F}_{n}(t_{k})-\widetilde{F}(t_{k})\big{|}\vee\big{|}\widetilde{F}_{n}(t_{k+1})-\widetilde{F}(t_{k+1})\big{|}+\epsilon$
for all $t\in[t_{k},t_{k+1})$. Also, for $t<t_{1}$, since
$\widetilde{F}_{n}(t)\geq 0$ and $\widetilde{F}(t)\leq\epsilon$, we have

$\displaystyle-\epsilon\leq\widetilde{F}_{n}(t)-\widetilde{F}(t)\leq\widetilde{F}_{n}(t_{1})-\widetilde{F}(t)\leq\widetilde{F}_{n}(t_{1})-\widetilde{F}(t_{1})+\epsilon.$

Similarly, for $t>t_{m}$, since $\widetilde{F}_{n}(t)\leq 1$ and
$\widetilde{F}(t)\geq\widetilde{F}(t_{m})\geq 1-\epsilon$, we have

$\displaystyle\epsilon\geq\widetilde{F}_{n}(t)-\widetilde{F}(t)\geq\widetilde{F}_{n}(t_{m})-\widetilde{F}(t)\geq\widetilde{F}_{n}(t_{m})-\widetilde{F}(t_{m})-\epsilon.$

Putting the above cases together yields

$\displaystyle\sup_{t\in\mathbb{R}}\big{|}\widetilde{F}_{n}(t)-\widetilde{F}(t)\big{|}\leq\sup_{1\leq
k\leq m}\big{|}\widetilde{F}_{n}(t_{k})-\widetilde{F}(t_{k})\big{|}+\epsilon.$

By the strong law of large numbers for $t_{1},\dots,t_{m}$ and the
arbitrariness of $\epsilon>0$, we conclude the proof of Lemma D.1. ∎