# Adaptive Storey’s null proportion estimator

Zijun Gao Marshall Business School, University of Southern California, CA,
USA. Email<EMAIL_ADDRESS>
###### Abstract

False discovery rate (FDR) is a commonly used criterion in multiple testing
and the Benjamini-Hochberg (BH) procedure is arguably the most popular
approach with FDR guarantee. To improve power, the adaptive BH procedure has
been proposed by incorporating various null proportion estimators, among which
Storey’s estimator has gained substantial popularity. The performance of
Storey’s estimator hinges on a critical hyper-parameter, where a pre-fixed
configuration lacks power and existing data-driven hyper-parameters compromise
the FDR control. In this work, we propose a novel class of adaptive hyper-
parameters and establish the FDR control of the associated BH procedure using
a martingale argument. Within this class of data-driven hyper-parameters, we
present a specific configuration designed to maximize the number of rejections
and characterize the convergence of this proposal to the optimal hyper-
parameter under a commonly-used mixture model. We evaluate our adaptive
Storey’s null proportion estimator and the associated BH procedure on
extensive simulated data and a motivating protein dataset. Our proposal
exhibits significant power gains when dealing with a considerable proportion
of weak non-nulls or a conservative null distribution.

##  1 Introduction

The rapid advancement of data collection technologies, including high-
throughput experiments, has sparked strong interest in the multiple testing
problem over the past a few decades and led to various remarkable statistical
advancements. To fix notations, we suppose there are ${n}$ hypotheses $H_{i}$
associated with p-values $p_{i}\in(0,1)$, and $p_{i}\sim U(0,1)$ for
$H_{i}=0$. Provided with a multiple testing method, we use $V$ and $R$ to
represent the number of falsely rejected null hypotheses (false discoveries)
and the total number of rejections, respectively. In this paper, we focus on
the control of false discovery rate (FDR) [3] defined as the expected
proportion of false discoveries $\mathbb{E}[V/(R\vee 1)]$.

The Benjamini-Hochberg (BH) procedure [3] is a widely-used multiple testing
method to control FDR. The BH procedure applied to independent p-values at
level $q$ effectively controls the FDR at a lower level ${\pi_{0}}q$. Here
${n_{0}}$ denotes the number of null hypotheses and ${\pi_{0}}={n_{0}}/{n}$
denotes the proportion of nulls. The BH procedure might be overly conservative
when ${\pi_{0}}$ is small, a point reiterated in various papers, including [4,
11].

To mitigate the conservativeness, the adaptive BH has been proposed, which
takes an estimator of the null proportion $\hat{\pi}_{0}$ and applies the
standard BH procedure at the level $q/\hat{\pi}_{0}$, typically higher than
$q$. There are several null proportion estimators111We remark that estimating
$\pi_{0}$, also under the name prevalence estimation, is not limited to the
realm of FDR control. We refer readers to [9, Chapter 8] for an in-depth
review of this topic. whose associated adaptive BH procedure properly controls
the FDR. [4] apply the BH procedure at a reduced level $q/(1+q)$ in step one,
and estimate the null proportion by $(1+q)(1-R_{1}/{n})$ in step two, where
$R_{1}$ denotes the number of rejections from the first step. In situations
where the signals are weak, it’s possible that $R_{1}$ is close to zero and
the resulting null proportion estimator exceeds one, leading to the associated
adaptive BH procedure being more conservative than the standard counterpart.
Another popular null estimator, which we focus on in this paper, takes the
form

$\displaystyle\hat{\pi}_{0}^{\lambda}=\frac{1+\sum_{i=1}^{n}\mathbbm{1}_{\\{p_{i}\geq\lambda\\}}}{n(1-\lambda)}.$
(1)

Here $\lambda\in(0,1)$ is a pre-fixed hyper-parameter. The estimator appeared
in [17], acquired the unofficial name “Storey’s estimator” since [19], and has
gained significant recognition after [20] showing the adaptive BH procedure
with $\hat{\pi}_{0}^{\lambda}$ using a pre-fixed $\lambda$ controls FDR.

The performance of Storey’s estimator and the associated adaptive BH procedure
may depend heavily on the choice of $\lambda$, which we illustrate using a
motivating protein study. The protein dataset is collected in a study aiming
to identify cell membrane proteins that are labeled with biotin by horseradish
peroxidase (HRP). Before measuring the abundance of proteins by mass
spectrometry, a process is executed to capture the biotinylated proteins that
are likely to be enriched by streptavidin bead and to filter out the majority
of background proteins (proteins that are not affected by HRP) [18]. Figure 1
(a) shows the histogram of the p-values derived from the protein abundances:
there appear to be a few strong non-nulls with p-values very close to zero; a
substantial fraction of weak non-nulls with moderately small p-values; a
proportion of conservative nulls corresponding to p-values larger than $0.8$
which stochastically dominate $U(0.8,1)$. As the hyper-parameter $\lambda$
grows from $0.2$ to $1$, Storey’s estimator $\hat{\pi}_{0}^{\lambda}$ first
decreases then increases and eventually exceeds one (Figure 1 (b)). Meanwhile,
the number of rejections produced by the associated adaptive BH procedure at
the target FDR level $0.2$ increases from $16$ to over $30$, and subsequently
falls back to below $16$ (Figure 1 (c)).

Multiple ways have been suggested for choosing $\lambda$. For pre-fixed
$\lambda$, the configuration $\lambda=1/2$ is employed by [21], while [7]
suggest using a smaller $\lambda=q$. For data-driven options, [19] suggests to
tune $\lambda$ by bootstrap; [21] discuss applying spline smoothing to
$\hat{\pi}_{0}^{\lambda}$ computed with a sequence of $\lambda$ and evaluating
the fit at $\lambda=1$. Nevertheless, empirical evidence [5, 14] shows that
the data-driven null proportion estimators may be downward-biased and the
associated adaptive BH procedure may not control FDR.

In this paper, we propose a class of data-driven $\hat{\lambda}$ with the
desirable FDR guarantee. In particular, we introduce a filtration and let
$\hat{\lambda}$ be arbitrary stopping time with regard to the filtration. We
prove the associated adaptive BH procedure controls the FDR by constructing a
martingale adapted to the filtration and employing the optional stopping
theorem. Among this class of data-driven hyper-parameters, we provide a
concrete stopping time designed to yield the maximal number of rejections, and
establish its convergence to the optimal $\lambda$ maximizing the super-
population power under a mixture model. On the motivating protein dataset, a
pre-fixed $\lambda=q=0.2$ gives $\hat{\pi}_{0}^{0.2}=0.85$, and the
corresponding BH yields $16$ rejections; our method adaptively chooses
$\hat{\lambda}=0.68$, leading to $\hat{\pi}_{0}^{0.68}=0.62$ and $31$
rejections. In addition, extensive simulations have also demonstrated the
proposed data-driven $\hat{\lambda}$ consistently results in more rejections
than a pre-fixed $\lambda$ across various data generation mechanisms.

Below, we describe the class of data-driven $\hat{\lambda}$ in Section 2.1 and
prove the finite-sample FDR control in Section 2.2. We delve into a specific
stopping time devised to maximize the power in Section 2.3. Section 3, Section
4 contain the simulation studies, the analysis of the motivating protein
dataset, respectively. We conclude with discussions on future directions in
Section 5.

(a) (a)

(b) (b)

(c) (c)

Figure 1:  Motivating protein dataset. Panel (a) plots the p-value histogram
of $585$ proteins. Panel (b) plots Storey’s estimator (1) across $\lambda$,
and panel (c) shows the number of rejections of the associated adaptive BH
procedure.

##  2 A class of adaptive Storey’s null proportion estimators

###  2.1 Stopping time $\hat{\lambda}$

Our data-driven hyper-parameter hinges on the filtration defined as,

$\displaystyle\mathcal{G}_{t}:=\sigma\left(\sum_{i\in[n]}\mathbbm{1}_{\\{p_{i}\geq
s\\}}:q\leq s\leq t\right),\quad q\leq t\leq 1.$

The filtration is increasing and only depends on the p-values larger than $q$.
The increasing filtration is different from the decreasing filtration
$\mathcal{H}_{t}=\sigma\left(\sum_{i\in[n]}\mathbbm{1}_{\\{p_{i}\geq
s\\}}:s\geq t\right)$ used by [20] to show the BH procedure controls FDR.

We propose $\hat{\lambda}$ to be any stopping time with regard to
$\mathcal{G}_{t}$. For instance, $\hat{\lambda}$ can be a pre-fixed value
independent of the data, $\inf\\{t:\hat{\pi}_{0}^{t}\leq
0.8\hat{\pi}_{0}^{q}\\}$,
$\inf\\{t:\hat{\pi}_{0}^{t}\leq\hat{\pi}_{0}^{q}-0.2\\}$. In Section 2.3, we
describe a less ad-hoc stopping time with the aim to maximize the number of
rejections. Provided with a stopping time $\hat{\lambda}$, we further compute
$\hat{\pi}_{0}^{\hat{\lambda}}$, referred to as adaptive Storey (AS) estimator
below, by plugging $\hat{\lambda}$ in Eq. (1). Finally, we combine
$\hat{\pi}_{0}^{\hat{\lambda}}$ and the BH procedure as described in Algorithm
1.

Figure 2 provides an illustration of Algorithm 1: in step one, starting from
the FDR level $q$, we gradually increase the hyper-parameter $\lambda$, along
which the p-values $p_{i}\geq q$ are sequentially disclosed in ascending
order. Once a pre-defined stopping rule is satisfied, we stop and output the
hyper-parameter value $\hat{\lambda}$; in step two, also initiated at $q$, we
decrease the threshold $\tau$ of the BH procedure, and inspect $p_{i}<q$ in
descending order. The process is terminated when the estimated FDR augmented
by $\hat{\pi}_{0}^{\hat{\lambda}}$, i.e.,
$\widehat{\text{FDP}}(t;\hat{\pi}_{0}^{\hat{\lambda}}):=\hat{\pi}_{0}^{\hat{\lambda}}{n}t/{\sum_{i=1}^{{n}}\mathbbm{1}_{\\{p_{i}\leq
t\\}}}$, falls below the target level $q$. The value at which we stop is
reported as the rejection threshold of the adaptive BH procedure.

$0$$q$$\hat{\lambda}$$1$$p_{(1)}$$p_{(2)}$$p_{(3)}$$p_{(4)}$$p_{(5)}$$p_{(6)}$$p_{(7)}$$p_{(8)}$ASStep
1

$0$$\hat{\tau}$$q$$\hat{\lambda}$$1$$p_{(1)}$$p_{(2)}$$p_{(3)}$$p_{(4)}$$p_{(5)}$$p_{(6)}$$p_{(7)}$$p_{(8)}$BH
with $\hat{\pi}_{0}^{\hat{\lambda}}$Step 2

Figure 2: The step-up adaptive BH procedure combined with the step-down AS
null proportion estimator. Algorithm 1 Adaptive BH with the AS null proportion
estimator

Input: p-values $p_{i}$, $i\in[n]$, FDR level $q$, a stopping rule adapted to
$\mathcal{G}_{t}$.

1\. Compute the stopping time $\hat{\lambda}$ based on the stopping rule.
Calculate $\hat{\pi}_{0}^{\hat{\lambda}}$ as in Eq. (1).

2\. Compute the BH rejection threshold
$\displaystyle\hat{\tau}=\sup\left\\{t<q:\frac{\hat{\pi}_{0}^{\hat{\lambda}}nt}{\sum_{i=1}^{n}\mathbbm{1}_{\\{p_{i}\leq
t\\}}}\leq q\right\\}.$ Here we regard $\sup\emptyset=-\infty$.

Output: rejection set $\\{H_{i}:p_{i}\leq\hat{\tau}\\}$.

###  2.2 Theoretical FDR guarantee

####  2.2.1 Independent p-values

The following result demonstrates that the BH procedure combined with the AS
null proportion estimator controls the FDR when applied to independent
p-values.

######  Proposition 1.

Let $\hat{\lambda}$ be a stopping time with regard to $\mathcal{G}_{t}$.
Assume for all $i\in[{n}]$ such that $H_{i}=0$, we have $p_{i}\sim U(0,1)$ and
$p_{i}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\bm{(}p_{j})_{j\neq i}$. Then Algorithm 1
controls the FDR at the target level.

We provide an outline of the proof here and include the details in the
appendix. Define an extended increasing filtration
$\mathcal{F}_{t}:=\sigma\left(\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
s\\}},\sum_{i\in[n]}\mathbbm{1}_{\\{p_{i}\geq s\\}}:q\leq s\leq t\right)$,
$q\leq t\leq 1$, which satisfies $\mathcal{G}_{t}\subseteq\mathcal{F}_{t}$.
Any stopping time with regard to $\mathcal{G}_{t}$ is also a stopping time
regarding $\mathcal{F}_{t}$. We define a random process

$\displaystyle M_{t}:=\frac{1-t}{1+\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
t\\}}}\geq\frac{1-t}{1+\sum_{i=1}^{n}\mathbbm{1}_{\\{p_{i}\geq
t\\}}}=\frac{1}{{n}\hat{\pi}_{0}^{\hat{\lambda}}},\quad q\leq t\leq 1.$ (2)

A key observation is that $M_{t}$ is a non-negative super-martingale with
respect to $\mathcal{F}_{t}$. Then by the optional stopping time theorem,

$\displaystyle\mathbb{E}\left[\frac{1}{\hat{\pi}_{0}^{\hat{\lambda}}}\right]\leq\mathbb{E}\left[{n}M_{\hat{\lambda}}\right]\leq\mathbb{E}\left[{n}M_{q}\right]\leq\frac{{n}}{1+{n_{0}}},$
(3)

where the last inequality comes from a standard result of binomial
distribution. Finally, we combine (3) and a leave-one-out argument adapted
from [2] to prove the finite-sample FDR control of Algorithm 1.

######  Remark 1.

Proposition 1 holds for non-uniform null p-values whose marginal distribution
satisfies the conditional stochastic dominance property

$\displaystyle\mathbb{P}(p_{i}\geq t\mid p_{i}\geq s)\geq(1-t)/(1-s),\quad
q\leq s\leq t\leq 1.$ (4)

The conditional stochastic dominance property is met when the null p-values
admit an increasing density on $[q,1]$, such as Beta$(a,b)$ with $a\geq 1$,
$b\leq 1$, and the p-values of one-sided hypothesis testing based on a
distribution family with monotone likelihood ratio. See Section 3 for concrete
examples.

####  2.2.2 Dependent p-values based on exchangeable test statistics

As discussed in [4, 6], the BH procedure with Storey’s null proportion
estimator does not control FDR in general. Nevertheless, we prove the FDR
control extends to a class of dependent p-values considered by [1, 15, 12].
This type of p-values, also known as conformal p-values, are derived from
exchangeable test statistics described below. Their validity is robust to
model misspecifications, small sample sizes, batch effects, and only requires
an exchangeability condition that could be ensured by data generation or
domain knowledge.

We describe this type of p-values following the notations in [12]. Suppose
there are ${n}+m$ hypotheses. The first ${n}$ hypotheses
$\mathcal{I}:=\\{1,\dotsc,{n}\\}$ are under investigation, and the last $m$
hypotheses $\\{{n}+1,\dotsc,{n}+m\\}$ are true according to domain knowledge
and referred to as negative controls. We use
$\mathcal{I}_{0}\subseteq\mathcal{I}$ to denote the unknown null hypotheses
under investigation. Each hypothesis ${H_{i}}$ is associated with a test
statistic ${T_{i}}$, where a larger test statistic provides more evidence
against that hypothesis. The p-value is defined as the normalized rank of
${T_{i}}$ among ${T_{i}}$, ${T_{{n}+1}}$, $\ldots$, ${T_{{n}+m}}$,

$\displaystyle
p_{i}:=\frac{1+\sum_{j\in{\mathcal{I}_{\text{nc}}}}\mathbbm{1}_{\\{{T_{j}}\geq{T_{i}}\\}}}{1+m}.$
(5)

Because $p_{i}$, $i\in[n]$ are calculated using the same set of negative
controls, they are not independent even if the test statistics ${T_{i}}$,
$i\in[{n}+m]$ are themselves independent. Nevertheless, the BH procedure
combined with $p_{i}$ with independent or partially exchangeable (specified
below) test statistics has been proved to control FDR [1, 15, 12]. In this
paper, we extend this FDR control result to the BH procedure with the AS null
proportion estimator.

######  Proposition 2.

Let $\hat{\lambda}$ be a stopping time with regard to $\mathcal{G}_{t}$.
Assume the partial exchangeability: ${T_{i}}$,
$i\in\mathcal{I}_{0}\cup\mathcal{I}_{\text{nc}}$ is exchangeable given
${T_{j}}$, $j\in\mathcal{I}/\mathcal{I}_{0}$. Then Algorithm 1 applied to
$(p_{i})_{i\in{\mathcal{I}}}$ defined in Eq. (5) controls the FDR at the
target level.

To prove Proposition 2, we first employ combinatorial equations to show that
$M_{t}$ in (2) based on the p-values in (5) remains a super-martingale under
the partial exchangeability condition. We then provide a leave-one-out
argument for the FDR control of the adaptive BH procedure. This argument is
distinct from existing proofs for this type of p-values relying on martingales
[15, 12] or the PRDS property [1, 12]

###  2.3 A stopping time maximizing the number of rejections

The general AS method accommodates arbitrary stopping time. We provide a
concrete configuration with the goal to maximize the number of rejections, or
equivalently minimize $\hat{\pi}_{0}^{\hat{\lambda}}$.

Let $\lambda_{j}:=q+j\delta$, $j\in[(1-q)/\delta]$ for some $\delta>0$, we
consider the stopping time

$\displaystyle\hat{\lambda}=\inf\left\\{\lambda_{j},j\in[(1-q)/\delta]:\hat{\pi}_{0}^{\lambda_{j-1}}\leq\hat{\pi}_{0}^{\lambda_{j}}\right\\}.$
(6)

The stopping time compares the estimated null proportions of adjacent hyper-
parameters $\lambda_{j-1}$, $\lambda_{j}$, and terminates once the estimated
value stops to decrease, i.e.,
$\hat{\pi}_{0}^{\lambda_{j-1}}\leq\hat{\pi}_{0}^{\lambda_{j}}$. In Figure 1
(b) derived from the motivating protein dataset, the estimator
$\hat{\pi}_{0}^{\lambda}$ first decreases then increases in $\lambda$, and the
proposed stopping time is likely to stop around the global minimizer of
$\hat{\pi}_{0}^{\lambda}$. Regarding the selection of $\delta$, a small
$\delta$ is associated with $\lambda_{j}$ of higher resolution, but it may
lead to early termination of the descending trend of $\ell$ due to the
variability in $\hat{\pi}_{0}^{\lambda}$. In Proposition 3, we analyze the
asymptotic performance of $\hat{\lambda}$ considering a $\delta$ vanishing at
the rate $O({n}^{-1/3})$. In practice, we suggest using
$\delta=50/\sum_{i=1}^{{n}}\mathbbm{1}_{\\{p_{i}\geq q\\}}$ for ${n}\sim
10^{3}$ as a rule of thumb to balance the low resolution and the premature
termination.

(a) Few strong signals

(b) Many weak signals

(c) Conservative nulls

Figure 3: Comparison of $\hat{\lambda}$ and its robust version
$\hat{\lambda}^{\prime}$. We consider the three scenarios in Section 3 and
vary the total sample size from $40$ to $160$. We choose
$\delta=10/\sum_{i=1}^{{n}}\mathbbm{1}_{\\{p_{i}\geq q\\}}$. Each scenario is
repeated $4000$ times. We plot the median (solid), upper and lower quartiles
(dotted) of Storey’s estimator $\hat{\pi}_{0}^{\hat{\lambda}}$ (black),
$\hat{\pi}_{0}^{\hat{\lambda}^{\prime}}$ (blue). We also superimpose the
horizontal reference lines at the true $\pi_{0}$ (red, dashed) and $1$ (red,
dotted).

Next, we discuss a robust version of $\hat{\lambda}$ suitable for small sample
size. Define a loss that takes the variation of $\hat{\pi}_{0}^{\lambda}$ into
account,

$\displaystyle\ell({\lambda}):=\hat{\pi}_{0}^{\lambda}+\sqrt{\hat{V}^{\lambda}},\quad\hat{V}^{\lambda}:=\frac{1}{n}\cdot\hat{\pi}_{0}^{\lambda}\left(\frac{1}{1-\lambda}-\hat{\pi}_{0}^{\lambda}\right).$

Here $\hat{V}^{\lambda}$ estimates the variance of $\hat{\pi}_{0}^{\lambda}$
by plugging $\hat{\pi}_{0}^{\lambda}$ into the variance formula of Binomial
distribution. Close-to-one $\lambda$ is often associated with a large loss due
to the standard deviation term. We define a robust version of the stopping
time (6) based on the loss $\ell({\lambda})$,

$\displaystyle\hat{\lambda}^{\prime}=\inf\left\\{\lambda_{j},j\in[(1-q)/\delta]:\ell({\lambda}_{j-1})\leq\ell({\lambda}_{j})\right\\}.$
(7)

Figure 3 displays that the estimated null proportion with the robust version
of the stopping time could be more reliable when the sample size is small
(${n}\leq 100$).

Below we provide the asymptotic performance analysis of the proposed stopping
times under a frequently-used mixture model [20, 10]. Suppose
$({H_{i}})_{i\in[{n}]}\overset{\text{i.i.d.}}{\sim}\text{Bernoulli}(1-{\pi_{0}})$.
Given the hypothesis ${H_{i}}$, the p-value is generated independently as

$p_{i}\mid{H_{i}}=0\sim{F_{0}}\quad\text{and}\quad
p_{i}\mid{H_{i}}=1\sim{F_{1}}.$

Here $F_{0}$, $F_{1}$ denote the CDF of the unknown null222Here we allow an
unknown null distribution that conditionally stochastically dominates $U(0,1)$
as described in Remark 1. and non-null distributions. The marginal CDF of
$p_{i}$ is the mixture ${F}={\pi_{0}}{F_{0}}+(1-{\pi_{0}}){F_{1}}$. We denote
the density functions of ${F_{0}}$ and ${F_{1}}$ by $f_{0}$, $f_{1}$, and the
marginal density by $f=\pi_{0}f_{0}+(1-\pi_{0})f_{1}$. Let
$\pi^{\lambda}_{0,\infty}=(1-F(\lambda))/(1-\lambda)$, $0\leq\lambda<1$, and
$\pi^{1}_{0,\infty}=\overline{\lim}_{t\to 1}\pi^{t}_{0,\infty}$, which can be
considered as the null proportion estimator with the hyper-parameter $\lambda$
obtained from an infinite number of hypotheses drawn from the mixture model.
Define $\pi_{0}^{*}:=\inf_{q\leq\lambda\leq
1}\pi^{\lambda}_{0,\infty}\geq\pi_{0}$, and the optimal hyper-parameter
$\lambda^{*}:=\inf\\{q\leq\lambda\leq
1:\pi^{\lambda}_{0,\infty}=\pi^{*}_{0}\\}$. It is possible that the optimal
hyper-parameter $\lambda^{*}<1$, typically in the presence of conservative
nulls as in the motivating protein dataset.

Under the mixture model, Storey’s estimator with a fixed $\lambda<1$ is shown
to converge at the rate ${n}^{-1/2}$ to a Gaussian distribution with the mean
$\pi_{0,\infty}^{\lambda}\geq\pi_{0}^{*}$ [13]. [16] shows Storey’s estimator
with a hyper-parameter growing to $1$ converges at a rate slower than
${n}^{-1/2}$. In contrast, our analysis below deals with data-driven hyper-
parameters.

Let $\hat{\lambda}_{{n}}$, $\hat{\lambda}_{{n}}^{\prime}$ be the stopping time
defined in (6), (7) obtained from a sample of size ${n}$. The following
proposition characterizes the convergence of $\hat{\lambda}_{{n}}$,
$\hat{\lambda}_{{n}}^{\prime}$ to $\lambda^{*}$.

######  Proposition 3.

Assume $f$, $f^{\prime}$, $f^{\prime\prime}$ exist, are continuous on $[0,1]$,
and $f^{\prime\prime}>0$ on $[0,1)$.

  * (a)

If $\lambda^{*}=1$, then for $\delta={n}^{-1/3}\log({n})$,

$\displaystyle\mathbb{P}\left(\left|\hat{\lambda}_{{n}}-\lambda^{*}\right|\geq\varepsilon\right),~{}\mathbb{P}\left(\hat{\pi}_{0}^{\hat{\lambda}_{{n}}}-{\pi}_{0}^{*}\geq\varepsilon\right)\to
0.$

  * (b)

If $\lambda^{*}<1$, then for any $M>0$, there exists $N>0$ such that setting
$\delta=M{n}^{-1/3}$, with probability at least $1-C_{1}M^{-3/2}$,

$\displaystyle\left|\hat{\lambda}_{{n}}-\lambda^{*}\right|\leq
C_{2}M{{n}}^{-1/3},\quad\hat{\pi}_{0}^{\hat{\lambda}_{{n}}}\leq\pi_{0}^{*}+C_{2}M{{n}}^{-1/3},\quad\forall{n}\geq
N,$

where $C_{1}$, $C_{2}>0$ are independent of ${n}$ and $M$.

Both (a) and (b) apply to $\hat{\lambda}_{{n}}^{\prime}$.

The proof is provided in the appendix. Examples satisfying the conditions in
Proposition 3 include p-values derived from a family with monotone likelihood
ratio. If the condition is violated in the sense that $f^{\prime\prime}=0$ on
an interval contained in $(q,\lambda^{*})$, then $\hat{\lambda}_{{n}}$ is
likely to terminate within that interval before reaching $\lambda^{*}$ and is
thus not consistent.

##  3 Simulations

We compare the non-adaptive BH (std), the oracle BH (orc) with true
${\pi_{0}}$, and the adaptive BH with three types of null proportion
estimators: BY for [4], S for Storey’s estimator, and AS for the proposed
extension. For Storey’s estimator, we consider three variants: S.S (S for
small) with $\lambda=0.2$, S.M (M for medium) with $\lambda=0.5$, S.L (L for
large) with $\lambda=0.8$. In the AS method, we adopt a modified version of
the stopping time (7) by truncating it at $0.8$,

$\displaystyle\hat{\lambda}=\inf\left\\{\lambda_{j},j\in[(1-q)/\delta]:\lambda_{j}\leq
0.8,~{}{\ell}({\lambda}_{j-1})\leq{\ell}({\lambda}_{j})\right\\},$

and the suggested rule of thumb
$\delta=50/\sum_{i=1}^{{n}}\mathbbm{1}_{\\{p_{i}\geq q\\}}$. The FDR level is
set at $q=0.2$.

We consider four data generating mechanisms.

  1. (a)

Few strong signals. We set ${n}=500$ with ${n_{0}}=450$. The non-null p-values
are generated independently as $1-\Phi(Z+2)$, where $Z\sim\mathcal{N}(0,1)$
and $\Phi$ denotes the CDF of standard normal;

  2. (b)

Distributed weak signals. We consider ${n}=500$, ${n_{0}}=100$, and non-null
p-values $1-\Phi(Z+1.5\mu_{i})$ for $\mu_{i}=i/400$, $i\in[400]$;

  3. (c)

Screened using external data. We adopt ${n}=10^{4}$ with ${n_{0}}=9\times
10^{3}$. We generate two independent batches of p-values with non-null
p-values following $1-\Phi(Z+1.5)$ and $1-\Phi(Z+1)$, respectively. We use the
first batch to select the hypotheses with p-values no larger than $0.05$. We
then apply BH to the p-values of the selected hypotheses in the second batch,
whose null proportion is expected to be low due to the screening. This setting
is motivated by the cross-screening procedure in [8];

  4. (d)

Conservative nulls. We consider ${n}=500$, ${n_{0}}=250$, and null p-values
following Beta$(3,1)$, non-null p-values $1-\Phi(Z+2)$. We remark that
Proposition 1 holds for this null distribution.

(a) Few strong signals

(b) Many weak signals

(c) Screened

(d) Conservative nulls

Figure 4: Comparison of variants of the BH procedure regarding FDR and power.
The first panel provides the histogram of the p-values from a randomly
selected trial of each scenario. The second panel demonstrates the estimated
null proportion, which is one for the standard BH procedure and $\pi_{0}$ for
the oracle method. The third and the fourth panels display the FDP and the
proportion of correct rejections among non-nulls, respectively. We experiment
with the four scenarios described in Section 3, each repeated $1000$ times.

As depicted in Figure 4, all methods control FDR throughout the four settings.
Regarding power, our proposed method consistently demonstrates high levels of
power, while the performance of Storey’s method with different pre-fixed
$\lambda$ varies across settings, and BY, std generally make less rejections.
More explicitly, in (a), the proportion of null hypotheses is close to one,
and all methods perform approximately the same; in (b) and (c) with a
significant proportion of weak non-nulls, the proposed method exhibits higher
power than BY, S.S, and S.M with a small or medium $\lambda$; in (d), S.M, S.L
with a medium, large $\lambda$ only make a few rejections due to the
conservative null distribution (Beta$(3,1)$), while the proposed method
manages to maintain high power.

##  4 Real data analysis

We revisit the motivating dataset discussed in Section 1. The histogram of
p-values (Figure 1 (a)) displays two characteristics: there are a significant
proportion of weak signals, which contribute to the gradual decrease in
frequency for p-values in $[0.1,0.7]$. This pattern is reflected in the
simulation setting (b) where a large $\lambda$ is preferred; the null p-values
are conservative and result in an increase in frequency at the right end of
the p-values’ range ($p\in[0.8,1]$). This trend is reminiscent of the
simulation setting (d) where a small $\lambda$ is preferred. The presence of
two patterns, each favoring a different $\lambda$, adds the complexity to the
choice of an appropriate hyper-parameter.

We apply the six methods in Section 3 at the FDR level $q=0.2$ to the protein
dataset with all the hyper-parameters kept the same. In Table 1, we observe
that the proposed method with the proposed stopping time (6) adaptively
chooses ${\lambda}_{\text{AS}}=0.68$, close to the global minimizer of
$\hat{\pi}_{0}^{\lambda}$. In contrast, variants of Storey’s method with pre-
defined hyper-parameters $\lambda\in\\{0.2,0.5,0.8\\}$ miss the optimal hyper-
parameter. This leads to larger estimates of the null proportion and fewer
rejections. Finally, the BY procedure makes less rejections than the standard
BH since the signals are not sufficiently strong to be picked up by its null
proportion estimator. Furthermore, we perform gene ontology analysis of
cellular components [22] and among the $14$ proteins uniquely identified by
our proposed method, $8$ proteins—Scn2a1, Itgb1, Lrrc4b, Slc6a9, Kcna2,
Igsf21, Hapln4, Pde2a—are expected to be enriched.

| standard | BY | Storey | AS
---|---|---|---|---
|  |  | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.8$ |
$\hat{\pi}_{0}$ | $1$ | $1.17$ | $0.85$ | $0.69$ | $0.72$ | $0.62$
$R$ | $16$ | $12$ | $16$ | $17$ | $17$ | $31$
Table 1: Estimated null proportion $\hat{\pi}_{0}$ and the number of
rejections $R$ of variants of the BH procedure obtained from the motivating
protein dataset.

##  5 Discussions

In [4], it is noted that Storey’s method does not control FDR for dependent
p-values with $\lambda=0.5$, and [7] show that a smaller $\lambda$ controls
the FDR for equi-correlation model. It would be valuable to investigate
whether our adaptive extension is capable of handling dependent p-values
beyond the conformal p-values in Section 2.2.2.

Choosing the stopping time to maximize the power has connections to optimal
stopping time theory. However, in traditional optimal stopping problems, the
context, that is $F$, $F_{0}$, $F_{1}$, and ${\pi_{0}}$ in the two-component
mixture model, is typically known in advance, while such information is not
available and we learn it as we progress. It is of interest to investigate
whether an optimal stopping time exists in our setting and, if so, how to
construct it.

## Acknowledgement

We would like to express our sincere gratitude to Qingyuan Zhao for the
valuable and insightful suggestions regarding the statistical methodology. We
genuinely thank Zora Chan for generously providing the protein dataset and
assisting with the analysis therein.

## References

  * [1] Stephen Bates et al.  “Testing for Outliers With Conformal P-Values” to appear  In _Annals of Statistics_ , 2021
  * [2] Yoav Benjamini and Marina Bogomolov  “Selective inference on multiple families of hypotheses”  In _Journal of the Royal Statistical Society: Series B: Statistical Methodology_ JSTOR, 2014, pp. 297–318
  * [3] Yoav Benjamini and Yosef Hochberg  “Controlling the false discovery rate: a practical and powerful approach to multiple testing”  In _Journal of the Royal statistical society: series B (Methodological)_ 57.1 Wiley Online Library, 1995, pp. 289–300
  * [4] Yoav Benjamini, Abba M Krieger and Daniel Yekutieli  “Adaptive linear step-up procedures that control the false discovery rate”  In _Biometrika_ 93.3 Oxford University Press, 2006, pp. 491–507
  * [5] M. A. Black  “A Note on the Adaptive Control of False Discovery Rates” Publisher: [Royal Statistical Society, Wiley]  In _Journal of the Royal Statistical Society. Series B (Statistical Methodology)_ 66.2, 2004, pp. 297–304
  * [6] Gilles Blanchard and Etienne Roquain  “Two simple sufficient conditions for FDR control”  In _Electronic Journal of Statistics_ 2, 2008, pp. 963–992
  * [7] Gilles Blanchard and Étienne Roquain  “Adaptive False Discovery Rate Control under Independence and Dependence.”  In _Journal of Machine Learning Research_ 10.12, 2009
  * [8] Marina Bogomolov and Ruth Heller  “Assessing replicability of findings across two studies of multiple features”  In _Biometrika_ 105.3 Oxford University Press, 2018, pp. 505–516
  * [9] Xinping Cui, Thorsten Dickhaus, Ying Ding and Jason C. Hsu  “Handbook of Multiple Comparisons” Google-Books-ID: hdtKEAAAQBAJ  CRC Press, 2021
  * [10] Bradley Efron  “Empirical Bayes estimates for large-scale prediction problems”  In _Journal of the American Statistical Association_ 104.487 Taylor & Francis, 2009, pp. 1015–1028
  * [11] Helmut Finner and Veronika Gontscharuk  “Controlling the Familywise Error Rate with Plug-in Estimator for the Proportion of True Null Hypotheses”  In _Journal of the Royal Statistical Society Series B: Statistical Methodology_ 71.5, 2009, pp. 1031–1048
  * [12] Zijun Gao and Qingyuan Zhao  “Simultaneous Hypothesis Testing Using Internal Negative Controls with An Application to Proteomics”, 2023
  * [13] Christopher Genovese and Larry Wasserman  “A stochastic process approach to false discovery control” Publisher: Institute of Mathematical Statistics  In _The Annals of Statistics_ 32.3, 2004, pp. 1035–1061
  * [14] Hongmei Jiang and R.W. Doerge  “Estimating the Proportion of True Null Hypotheses for Multiple Comparisons”  In _Cancer Informatics_ 6, 2008, pp. 25–32
  * [15] David Mary and Etienne Roquain  “Semi-Supervised Multiple Testing”  In _Electronic Journal of Statistics_ 16.2, 2022
  * [16] Pierre Neuvial  “Asymptotic results on adaptive false discovery rate controlling procedures based on kernel estimators”  In _The Journal of Machine Learning Research_ 14.1 JMLR. org, 2013, pp. 1423–1459
  * [17] T. Schweder and E. Spjotvoll  “Plots of P-Values to Evaluate Many Tests Simultaneously” Publisher: [Oxford University Press, Biometrika Trust]  In _Biometrika_ 69.3, 1982, pp. 493–502
  * [18] S Andrew Shuster et al.  “In situ cell-type-specific cell-surface proteomic profiling in mice”  In _Neuron_ 110 Elsevier, 2022, pp. 1–14
  * [19] John D Storey  “A direct approach to false discovery rates”  In _Journal of the Royal Statistical Society Series B: Statistical Methodology_ 64.3 Oxford University Press, 2002, pp. 479–498
  * [20] John D Storey, Jonathan E Taylor and David Siegmund  “Strong control, conservative point estimation and simultaneous conservative consistency of false discovery rates: a unified approach”  In _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ 66.1 Wiley Online Library, 2004, pp. 187–205
  * [21] John D Storey and Robert Tibshirani  “Statistical significance for genomewide studies”  In _Proceedings of the National Academy of Sciences_ 100.16 National Acad Sciences, 2003, pp. 9440–9445
  * [22] Damian Szklarczyk et al.  “The STRING database in 2023: protein–protein association networks and functional enrichment analyses for any sequenced genome of interest”  In _Nucleic acids research_ 51.D1 Oxford University Press, 2023, pp. D638–D646

##  Appendix A Proofs

###  A.1 FDR control for independent p-values

###### Proof of Proposition 1.

Recall the filtration

$\displaystyle\mathcal{F}_{t}=\sigma\left(\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
s\\}},\sum_{i\in[n]}\mathbbm{1}_{\\{p_{i}\geq s\\}}:q\leq s\leq t\right),\quad
q\leq t\leq 1,$

and the random process

$\displaystyle M_{t}=\frac{1-t}{1+\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
t\\}}},\quad q\leq t\leq 1.$

which is non-negative and adapts to $\mathcal{F}_{t}$. Since
$p_{i}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\bm{p}_{-i}$ for $H_{i}=0$, then for $q\leq
s\leq t\leq 1$,

$\displaystyle\mathbb{E}\left[M_{t}\mid\mathcal{F}_{s}\right]$
$\displaystyle=\mathbb{E}\left[\frac{1-t}{1+\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
t\\}}}\mid\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq s\\}}\right].$

Under the condition (4),

$\displaystyle\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
t\\}}\mid\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
s\\}}=K~{}\succeq~{}\text{Binomial}\left(K,\frac{1-t}{1-s}\right),$

here $\succeq$ denotes stochastic dominance. Together with the fact that
$\mathbb{E}[1/(1+X)]\leq((1+K)p)^{-1}$ for $X\sim\text{Binomial}(K,p)$, we
obtain

$\displaystyle\mathbb{E}\left[M_{t}\mid\mathcal{F}_{s}\right]$
$\displaystyle\leq\frac{1-t}{\left(1+\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
s\\}}\right)\cdot({1-t})/({1-s})}=M_{s},$

which implies $M_{t}$ is a non-negative super-martingale w.r.t.
$\mathcal{F}_{t}$. By the optional stopping time theorem, for any stopping
time $\hat{\lambda}$ taking values in $[q,1]$,

$\displaystyle\mathbb{E}\left[M_{\hat{\lambda}}\right]\leq\mathbb{E}\left[M_{q}\right]\leq\frac{1-q}{(1+{n_{0}})\cdot(1-q)}=\frac{1}{1+{n_{0}}},$

where in the second inequality we again use the condition (4) and the property
of Binomial distribution. Finally,

$\displaystyle\mathbb{E}\left[\frac{1}{\hat{\pi}_{0}^{\hat{\lambda}}}\right]=\mathbb{E}\left[\frac{n\left(1-\hat{\lambda}\right)}{1+\sum_{i=1}^{n}\mathbbm{1}_{\\{p_{i}\geq\hat{\lambda}\\}}}\right]\leq\mathbb{E}\left[\frac{n\left(1-\hat{\lambda}\right)}{1+\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq\hat{\lambda}\\}}}\right]={n}\cdot\mathbb{E}\left[M_{\hat{\lambda}}\right]\leq\frac{n}{1+{n_{0}}}.$
(8)

Now we prove the BH procedure combined with $\hat{\pi}_{0}^{\hat{\lambda}}$
controls FDR by the leave-one-out argument. For $H_{i}=0$, we use $V_{i}=1$ to
denote $H_{i}$ being rejected. Define

$\displaystyle\hat{\pi}_{0}^{\hat{\lambda},-i}:=\inf\left\\{\hat{\pi}_{0}^{\hat{\lambda}}(\bm{p}^{\prime}):\bm{p}^{\prime}_{-i}=\bm{p}_{-i},p^{\prime}_{i}<q\right\\}.$

Notice that $\hat{\lambda}$ adapts to $\mathcal{F}_{t}$ and does not depend on
the p-values smaller than $q$, then
${n}\hat{\pi}_{0}^{\hat{\lambda},-i}=({n}-1)\hat{\pi}_{0}^{\hat{\lambda}}(\bm{p}_{-i})$.
Since $p_{i}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\bm{p}_{-i}$, Eq. (8) applied to
$\hat{\pi}_{0}^{\hat{\lambda}}(\bm{p}_{-i})$ implies

$\displaystyle\mathbb{E}\left[\frac{1}{\hat{\pi}_{0}^{\hat{\lambda},-i}}\right]=\frac{{n}}{{n}-1}\cdot\mathbb{E}\left[\frac{1}{\hat{\pi}_{0}^{\hat{\lambda}}(\bm{p}_{-i})}\right]\leq\frac{{n}}{{n}-1}\cdot\frac{n-1}{1+({n_{0}}-1)}=\frac{n}{{n_{0}}}.$
(9)

Define

$\displaystyle
R^{-i}(\bm{p}_{-i})=\sup\left\\{|R(\bm{p}^{\prime})|:\bm{p}^{\prime}_{-i}=\bm{p}_{-i},V_{i}=1\right\\},$

Then the adaptive BH procedure satisfies $R=R^{-i}$ given $V_{i}=1$,
$\bm{p}_{-i}$. Since $V_{i}=1$ implies $q_{i}<q$, we have
$\hat{\pi}_{0}^{\hat{\lambda}}=\hat{\pi}_{0}^{\hat{\lambda},-i}$ given
$V_{i}=1$, $\bm{p}_{-i}$. Therefore,

$\displaystyle\mathbb{E}\left[\frac{V_{i}}{R\vee 1}\right]$
$\displaystyle=\mathbb{E}\left[\frac{V_{i}\mathbbm{1}_{\left\\{p_{i}\leq{Rq}/{\left(n\hat{\pi}_{0}^{\hat{\lambda}}\right)},p_{i}<q\right\\}}}{R\vee
1}\right]$
$\displaystyle=\mathbb{E}\left[\frac{V_{i}\mathbbm{1}_{\left\\{p_{i}\leq{R^{-i}q}/{\left(n{\pi_{0}}^{\hat{\lambda},-i}\right)},p_{i}<q\right\\}}}{R^{-i}\vee
1}\right]\quad(R=R^{-i},\hat{\pi}_{0}^{\hat{\lambda}}=\hat{\pi}_{0}^{\hat{\lambda},-i}~{}\text{given}~{}V_{i}=1,\bm{p}_{-i})$
$\displaystyle\leq\frac{q}{n}\cdot\mathbb{E}\left[\frac{1}{{\pi_{0}}^{\hat{\lambda},-i}}\right]\quad(p_{i}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\bm{p}_{-i})$
$\displaystyle\leq\frac{q}{n}\cdot\frac{n}{{n_{0}}}=\frac{q}{{n_{0}}}.\quad(\text{Eq.}~{}\eqref{proof:eq:expectation.2})$

We sum over $H_{i}=0$ and finish the proof. ∎

###  A.2 FDR control for conformal p-values

###### Proof of Proposition 2.

We extend the definitions of $\mathcal{F}_{t}$ and $M_{t}$ in the proof of
Proposition 1 to $1/(m+1)\leq t\leq 1$. Let $t_{m-k}:=1-k/(m+1)$. Under the
partial exchangeability condition, for $q\leq t_{m-k}<t_{m-k+1}\leq 1$,

$\displaystyle\mathbb{E}\left[M_{t_{m-k+1}}\mid\mathcal{F}_{t_{m-k}}\right]$
$\displaystyle=\mathbb{E}\left[\frac{k/(m+1)}{1+\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
t_{m-k+1}\\}}}\mid\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq t_{m-k}\\}}\right].$

Conditional on $\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq t_{m-k}\\}}=K$, the
$(m-k+1)$-th smallest negative control test statistic ranks $r\in[K+1]$ among
the largest $K$ test statistics under investigation and itself with
probability

$\displaystyle{\binom{K+k-r}{k-1}}\cdot{\binom{K+k}{k}}^{-1}$ (10)

under the partial exchangeability. Therefore,

$\displaystyle\mathbb{E}\left[M_{t_{m-k+1}}\mid\sum_{H_{i}=0}\mathbbm{1}_{\\{p_{i}\geq
t_{m-k}\\}}=K\right]$
$\displaystyle=\sum_{r=1}^{K+1}\frac{(k-1)/(m+1)}{1+K-(r-1)}\cdot\frac{\binom{K+k-r}{k-1}}{\binom{K+k}{k}}$
$\displaystyle=\frac{1}{m+1}\cdot\frac{1}{\binom{K+k}{k}}\sum_{r=1}^{K+1}{\binom{K+k-r}{k-2}}$
$\displaystyle=\frac{1}{m+1}\cdot\frac{1}{\binom{K+k}{k}}\left(\binom{K+k}{k-1}-1\right)\quad\left(\sum_{a=b}^{B}\binom{a}{b}=\binom{B+1}{b+1}\right)$
$\displaystyle<\frac{1}{m+1}\cdot\frac{k}{K+1}=M_{t_{m-k}}.$

Together with the fact that $M_{s}\leq M_{t_{m-k}}$ for $t_{m-k}<s\leq
t_{m-k+1}$, we conclude $M_{t}$ is a non-negative super-martingale w.r.t.
$\mathcal{F}_{t}$. For $q\geq 1/(m+1)$,

$\displaystyle\mathbb{E}\left[M_{q}\right]\leq\mathbb{E}\left[M_{1/(m+1)}\right]<\frac{1}{m+1}\cdot\frac{m}{{n_{0}}+1}<\frac{1}{{n_{0}}+1}.$

From here, we can follow the proof of Proposition 1 and employ the optional
stopping theorem to show
$\mathbb{E}[{(\hat{\pi}_{0}^{\hat{\lambda}})^{-1}}]\leq{n}/{(1+{n_{0}})}$.

Now we extend the leave-one-out argument to $p_{i}$. For each
$i\in{\mathcal{I}}$, we define

$\displaystyle
p_{j}^{-i}(k;{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\})$
$\displaystyle:={p_{j}}\left({T_{i}}~{}\text{ranks the $(k+1)$-th
in}~{}\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\};{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right),~{}j\in{\mathcal{I}},$
$\displaystyle
R^{-i}(k;{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\})$
$\displaystyle:=R\left({T_{i}}~{}\text{ranks the $(k+1)$-th
in}~{}\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\};{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right),$
$\displaystyle\hat{\pi}_{0}^{\hat{\lambda},-i}(k;{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\})$
$\displaystyle:=\hat{\pi}_{0}^{\hat{\lambda}}\left({T_{i}}~{}\text{ranks the
$(k+1)$-th
in}~{}\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\};{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right),$
$\displaystyle\kappa_{i}({T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\})$
$\displaystyle:=\max\left\\{-1\leq
k<q(m+1)-1:\frac{1+k}{1+m}\leq\frac{qR^{-i}(0;{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\})}{{n}\hat{\pi}_{0}^{\hat{\lambda},-i}(0;{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\})}\right\\}.$

We drop ${T_{{\mathcal{I}}-\\{i\\}}}$,
$\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}$ and use $p_{j}^{-i}(k)$,
$R^{-i}(k)$, $\hat{\pi}_{0}^{\hat{\lambda},-i}(k)$, $\kappa_{i}$ for notation
simplicity. Notice that $\hat{\lambda}$ adapts to $\mathcal{F}_{t}$ and does
not depend on the p-values smaller than $q$, then
$\hat{\pi}_{0}^{\hat{\lambda}}=\hat{\pi}_{0}^{\hat{\lambda},-i}(0)\mid
V_{i}=1$,
${T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}$.
Under the partial exchangeability condition, given $p_{i}=1/(m+1)<q$, Eq. (10)
holds and
$\mathbb{E}[(\hat{\pi}_{0}^{\hat{\lambda},-i}(0))^{-1}]\leq{n}/{{n_{0}}}$. We
inherit the notation $V_{i}$. For $H_{i}=0$,

$\displaystyle\mathbb{E}\left[\frac{V_{i}}{R\vee 1}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\frac{V_{i}}{R\vee
1}\mid{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right]\right]\quad(\text{tower
property})$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\frac{V_{i}\mathbbm{1}_{\\{{p_{i}}<q,{p_{i}}\leq
qR/({n}\hat{\pi}_{0}^{\hat{\lambda},-i}(0))\\}}}{R\vee
1}\mid{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right]\right]\quad(\hat{\pi}_{0}^{\hat{\lambda},-i}(0)=\hat{\pi}_{0}^{\hat{\lambda}}~{}\text{if}~{}p_{i}<q)$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\frac{V_{i}\mathbbm{1}_{\\{{p_{i}}<q,{p_{i}}\leq
qR^{-i}(0)/({n}\hat{\pi}_{0}^{\hat{\lambda},-i}(0))\\}}}{R^{-i}(0)\vee
1}\mid{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right]\right]\quad(\text{\lx@cref{creftypecap~refnum}{lemm:RANC.stable}})$
$\displaystyle\leq\mathbb{E}\left[\mathbb{E}\left[\frac{\mathbbm{1}_{\\{{p_{i}}<q,{p_{i}}\leq
qR^{-i}(0)/({n}\hat{\pi}_{0}^{\hat{\lambda},-i}(0))\\}}}{R^{-i}(0)\vee
1}\mid{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right]\right]\quad(V_{i}\leq
1)$
$\displaystyle=\mathbb{E}\left[\frac{\mathbb{E}\left[\mathbbm{1}_{\\{k\leq\kappa_{i}\\}}\mid{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right]}{R^{-i}(0)\vee
1}\right]\quad(R^{-i}(0)\sim\sigma({T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\})).$

Since ${T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}$ is exchangeable conditional
on ${T_{{\mathcal{I}}-\\{i\\}}}$, then

$\displaystyle\mathbb{E}\left[\mathbbm{1}_{\\{k\leq\kappa_{i}\\}}\mid{T_{{\mathcal{I}}-\\{i\\}}},\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}\right]=\frac{1+\kappa_{i}}{1+m}\leq\frac{qR^{-i}(0)}{{n}\hat{\pi}_{0}^{\hat{\lambda},-i}(0)}.$

Finally we use the upper bound of
$\mathbb{E}[(\hat{\pi}_{0}^{\hat{\lambda},-i}(0))^{-1}]$ and sum over
$H_{i}=0$. ∎

######  Lemma A.1.

Given ${T_{{\mathcal{I}}-\\{i\\}}}$,
$\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}$, and suppose ${T_{i}}$
ranks the $(k+1)$-th in $\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}$,
then $H_{i}$ is rejected iff $k\leq\kappa_{i}$, and $R^{-i}(k)=R^{-i}(0)\mid
V_{i}=1$.

###### Proof of Lemma A.1.

If $p_{i}^{-i}(k)<q$,
$\hat{\pi}_{0}^{\hat{\lambda},-i}(0)=\hat{\pi}_{0}^{\hat{\lambda},-i}(k)$. As
$k$ increases, $p_{j}^{-i}(k)$ increases, and $R^{-i}(k)$ decreases. If
$R^{-i}(0)=0$, then $\kappa_{i}=-1$ and $H_{i}$ is never rejected. If
$R^{-i}(0)>0$, then

$\displaystyle\sum_{j\in{\mathcal{I}}}\mathbbm{1}_{\left\\{p_{j}^{-i}(0)\leq
R^{-i}(0)q/({n}\hat{\pi}_{0}^{\hat{\lambda},-i}(0)),p_{j}^{-i}(0)<q\right\\}}=R^{-i}(0)~{}\Longleftrightarrow~{}\sum_{j\in{\mathcal{I}}}\mathbbm{1}_{\\{{T_{j}}<C_{(\kappa_{i}+1)}\\}}=R^{-i}(0),$
(11)

where $C_{(j)}$ denotes the $j$-th smallest negative control test statistic.
Given ${T_{{\mathcal{I}}-\\{i\\}}}$,
$\\{{T_{{\mathcal{I}_{\text{nc}}}\cup\\{i\\}}}\\}$,

  * (a)

for $0\leq k\leq\kappa_{i}$, Eq. (11) holds. As a result, $R^{-i}(k)\geq
R^{-i}(0)$. Together with $R^{-i}(k)\leq R^{-i}(0)$, we have
$R^{-i}(k)=R^{-i}(0)$. Since
$p_{i}^{-i}(k)=(1+k)/(1+m)\leq(1+\kappa_{i})/(1+m)\leq
R^{-i}(k)q/({n}\hat{\pi}_{0}^{\hat{\lambda},-i}(k))$ and $p_{i}^{-i}(k)<q$,
then $H_{i}$ is rejected;

  * (b)

for any $k>\kappa_{i}$, $p_{i}^{-i}(k)\geq q$ or

$\displaystyle
p_{i}^{-i}(k)>\frac{qR^{-i}(0)}{{n}\hat{\pi}_{0}^{\hat{\lambda},-i}(0)}\geq\frac{qR^{-i}(k)}{{n}\hat{\pi}_{0}^{\hat{\lambda},-i}(0)}=\frac{qR^{-i}(k)}{{n}\hat{\pi}_{0}^{\hat{\lambda},-i}(k)},$

which implies $H_{i}$ is not rejected.

∎

###  A.3 Convergence rate of the proposed stopping time

###### Proof of Proposition 3.

For notation simplicity, we introduce $\bar{F}(t)=1-F(t)$, and we write
$g(t)=\pi^{t}_{0,\infty}=\bar{F}(t)/(1-t)$, $0\leq t<1$, and
$g(1)=\pi^{1}_{0,\infty}=\overline{\lim}_{t\to 1}\bar{F}(t)/(1-t)$. Since $f$,
$f^{\prime}$ are continuous on $[0,1]$, there exists $f_{\max}>0$ such that
$|f|$, $|f^{\prime}|\leq f_{\max}$ on $[0,1]$. In addition, $g$, $g^{\prime}$
exist and are continuous on $[0,1]$, and there exists $g_{\max}>0$ such that
$|g|$, $|g^{\prime}|\leq g_{\max}$ on $[0,1]$.

  * •

We first prove Proposition 3 for the stopping time $\hat{\lambda}_{n}$ in (6).
We discuss $q<\lambda^{*}<1$, $\lambda^{*}=q$, and $\lambda^{*}=1$,
respectively.

Case 1: $q<\lambda^{*}<1$. Since $f^{\prime\prime}$ is continuous on $[0,1]$
and $f^{\prime\prime}>0$ on $[0,1)$, then by Lemma A.2, $g^{\prime\prime}(t)$
exists and is continuous, positive on $[0,1)$. Therefore, there exists
$C_{L}$, $0<\eta<(1-\lambda^{*})/2$ such that $g^{\prime\prime}(t)\geq C_{L}$
on $[q,\lambda^{*}+\eta]$. Further, by the mean value theorem,

$\displaystyle g^{\prime}(t_{2})-g^{\prime}(t_{1})\geq
C_{L}(t_{2}-t_{1}),\quad q\leq t_{1}<t_{2}\leq\lambda^{*}+\eta.$ (12)

Define the events

$\displaystyle\mathcal{A}_{j+1}^{c}=\begin{cases}\left\\{\hat{\pi}_{0}^{\lambda_{j}}\leq\hat{\pi}_{0}^{\lambda_{j+1}}\right\\},\quad&q\leq\lambda_{j}\leq\lambda^{*}-2\delta,\\\
\left\\{\hat{\pi}_{0}^{\lambda_{j}}>\hat{\pi}_{0}^{\lambda_{j+1}}\right\\},\quad&\lambda^{*}+\delta\leq\lambda_{j}<\lambda^{*}+\eta-\delta.\end{cases}$

Notice that

$\displaystyle\left\\{\hat{\pi}_{0}^{\lambda_{j}}\leq\hat{\pi}_{0}^{\lambda_{j+1}}\right\\}$
$\displaystyle=\left\\{\left(\hat{\pi}_{0}^{\lambda_{j+1}}-g(\lambda_{j+1})\right)-\left(\hat{\pi}_{0}^{\lambda_{j}}-g(\lambda_{j})\right)\geq-\left(g(\lambda_{j+1})-g(\lambda_{j})\right)\right\\},$
$\displaystyle\left\\{\hat{\pi}_{0}^{\lambda_{j}}>\hat{\pi}_{0}^{\lambda_{j+1}}\right\\}$
$\displaystyle=\left\\{\left(\hat{\pi}_{0}^{\lambda_{j+1}}-g(\lambda_{j+1})\right)-\left(\hat{\pi}_{0}^{\lambda_{j}}-g(\lambda_{j})\right)<-\left(g(\lambda_{j+1})-g(\lambda_{j})\right)\right\\},$

and then we analyze $g(\lambda_{j+1})-g(\lambda_{j})$ and
$\left(\hat{\pi}_{0}^{\lambda_{j+1}}-g(\lambda_{j+1})\right)-\left(\hat{\pi}_{0}^{\lambda_{j}}-g(\lambda_{j})\right)$
separately.

Since $g^{\prime}(t)$ exists and is continuous on $[0,1]$, then
$g^{\prime}(\lambda^{*})=0$. For $q\leq\lambda_{j}\leq\lambda^{*}-2\delta$,

$\displaystyle\begin{split}g(\lambda_{j+1})-g(\lambda_{j})&=g^{\prime}(\lambda_{j}+\gamma\delta)\cdot\delta\quad(\text{for
some $\gamma\in[0,1]$ by the mean value theorem})\\\
&=\left(g^{\prime}(\lambda_{j}+\gamma\delta)-g^{\prime}(\lambda^{*})\right)\cdot\delta\quad(g^{\prime}(\lambda^{*})=0)\\\
&\leq-
C_{L}(\lambda^{*}-(\lambda_{j}+\gamma\delta))\cdot\delta\quad(\text{Condition}~{}\eqref{prop:slope.condition})\\\
&\leq-C_{L}(\lambda^{*}-\lambda_{j+1})\delta.\end{split}$ (13)

Similarly for $\lambda^{*}+\delta\leq\lambda_{j}\leq\lambda^{*}+\eta-\delta$,

$\displaystyle\begin{split}g(\lambda_{j+1})-g(\lambda_{j})>C_{L}(\lambda_{j}-\lambda^{*})\delta.\end{split}$
(14)

Next, for $q\leq\lambda_{j}\leq\lambda^{*}+\eta-\delta$,

$\displaystyle\quad\left(\hat{\pi}_{0}^{\lambda_{j+1}}-g(\lambda_{j+1})\right)-\left(\hat{\pi}_{0}^{\lambda_{j}}-g(\lambda_{j})\right)$
$\displaystyle=\frac{1+\sum_{i=1}^{{n}}\left(\mathbbm{1}_{\left\\{p_{i}\geq\lambda_{j+1}\right\\}}-\bar{F}(\lambda_{j+1})\right)}{{n}(1-\lambda_{j+1})}-\frac{1+\left(\mathbbm{1}_{\left\\{p_{i}\geq\lambda_{j}\right\\}}-\bar{F}(\lambda_{j})\right)}{{n}(1-\lambda_{j})}$
$\displaystyle=-\underbrace{\frac{\sum_{i=1}^{{n}}\mathbbm{1}_{\left\\{\lambda_{j}\leq
p_{i}<\lambda_{j+1}\right\\}}-\left(\bar{F}(\lambda_{j})-\bar{F}(\lambda_{j+1})\right)}{{n}(1-\lambda_{j})}}_{:=(\text{I})}+\underbrace{\frac{\delta+\delta\sum_{i=1}^{{n}}\left(\mathbbm{1}_{\left\\{p_{i}\geq\lambda_{j+1}\right\\}}-\bar{F}(\lambda_{j+1})\right)}{{n}(1-\lambda_{j})(1-\lambda_{j+1})}}_{:=(\text{II})}.$

For (II), since
$\mathbbm{1}_{\left\\{p_{i}\geq\lambda_{j+1}\right\\}}-\bar{F}(\lambda_{j+1})\in[-1,1]$
is zero mean, and its variance is upper bounded by
$\bar{F}(\lambda_{j+1})=\bar{F}(\lambda_{j+1})-\bar{F}(1)\leq
f_{\max}(1-\lambda_{j+1})$, then by Bernstein’s inequality and
$1-(\lambda^{*}+\eta)\geq(1-\lambda^{*})/2$,

$\displaystyle\quad~{}\mathbb{P}\left(\mathcal{B}_{j+1}^{c}:=\left\\{\left|\frac{\sum_{i=1}^{{n}}\mathbbm{1}_{\left\\{p_{i}\geq\lambda_{j+1}\right\\}}-\bar{F}(\lambda_{j+1})}{{n}(1-\lambda_{j+1})}\right|\geq(C_{L}(1-\lambda^{*})/8)\cdot\delta\right\\}\right)$
$\displaystyle\leq
2\exp\left\\{-\frac{\left((C_{L}(1-\lambda^{*})/8)(1-\lambda_{j+1}){n}\delta\right)^{2}/2}{{n}f_{\max}(1-\lambda_{j+1})+(C_{L}(1-\lambda^{*})/8)(1-\lambda_{j+1}){n}\delta/3}\right\\}$
$\displaystyle\leq
2\exp\left\\{-\frac{C_{L}^{2}(1-\lambda^{*})^{2}{n}\delta^{2}/128}{f_{\max}+C_{L}(1-\lambda^{*})\delta/24}\right\\}.$

Further by the union bound,

$\displaystyle\mathbb{P}\left(\mathcal{B}:=\cap_{q\leq\lambda_{j}\leq\lambda^{*}+\eta-\delta}~{}\mathcal{B}_{j+1}\right)$
$\displaystyle\geq
1-\sum_{q\leq\lambda_{j}\leq\lambda^{*}+\eta-\delta}\mathbb{P}\left(\mathcal{B}_{j+1}^{c}\right)$
$\displaystyle\geq
1-\frac{2}{\delta}\exp\left\\{-\frac{C_{L}^{2}(1-\lambda^{*})^{2}{n}\delta^{2}/128}{f_{\max}+C_{L}(1-\lambda^{*})\delta/24}\right\\}:=1-p_{\mathcal{B}^{c}}.$

There exists $N>0$ such that
$p_{\mathcal{B}^{c}}=O({n}^{1/3}e^{-{n}^{1/3}})\leq M^{-3/2}$ for ${n}\geq N$.
For (I), since $\mathbbm{1}_{\left\\{\lambda_{j}\leq
p_{i}<\lambda_{j+1}\right\\}}-\left(\bar{F}(\lambda_{j})-\bar{F}(\lambda_{j+1})\right)\in[-1,1]$
is zero mean, and its variance is upper bounded by
$\bar{F}(\lambda_{j})-\bar{F}(\lambda_{j+1})\leq
f_{\max}(\lambda_{j+1}-\lambda_{j})=f_{\max}\delta$. Again by Bernstein’s
inequality,

$\displaystyle\mathbb{P}\left(\mathcal{D}_{j+1}^{c}:=\left\\{|(\text{I})|\geq
C_{L}(\lambda^{*}-\lambda_{j+1})\delta/2\right\\}\right)\leq
2\exp\left\\{-\frac{C_{L}^{2}(\lambda^{*}-\lambda_{j+1})^{2}(1-\lambda_{j})^{2}{n}\delta/8}{f_{\max}+C_{L}(\lambda^{*}-\lambda_{j+1})(1-\lambda_{j})/6}\right\\},\quad\lambda_{j}\leq\lambda^{*}-2\delta,$
$\displaystyle\mathbb{P}\left(\mathcal{D}_{j+1}^{c}:=\left\\{|(\text{I})|\geq
C_{L}(\lambda_{j}-\lambda^{*})\delta/2\right\\}\right)\leq
2\exp\left\\{-\frac{C_{L}^{2}(\lambda_{j}-\lambda^{*})^{2}(1-\lambda_{j})^{2}{n}\delta/8}{f_{\max}+C_{L}(\lambda_{j}-\lambda^{*})(1-\lambda_{j})/6}\right\\},\quad\lambda_{j}\geq\lambda^{*}+\delta.$

Further by the union bound and $1-(\lambda^{*}+\eta)>(1-\lambda^{*})/2$,

$\displaystyle\quad~{}\mathbb{P}\left(\mathcal{D}:=\left(\cap_{q\leq\lambda_{j}\leq\lambda^{*}-2\delta}~{}\mathcal{D}_{j+1}\right)\cap\left(\cap_{\lambda^{*}+\delta\leq\lambda_{j}\leq\lambda^{*}+\eta-\delta}~{}\mathcal{D}_{j+1}\right)\right)$
$\displaystyle\geq
1-\sum_{q\leq\lambda_{j}\leq\lambda^{*}-2\delta}\exp\left\\{-\frac{C_{L}^{2}(\lambda^{*}-\lambda_{j+1})^{2}(1-\lambda_{j})^{2}{n}\delta/8}{f_{\max}+C_{L}(\lambda^{*}-\lambda_{j})(1-\lambda_{j})/6}\right\\}$
$\displaystyle\quad~{}-\sum_{\lambda^{*}+\delta\leq\lambda_{j}\leq\lambda^{*}+\eta-\delta}\exp\left\\{-\frac{C_{L}^{2}(\lambda_{j}-\lambda^{*})^{2}(1-\lambda_{j})^{2}{n}\delta/8}{f_{\max}+C_{L}(\lambda_{j}-\lambda^{*})(1-\lambda_{j})/6}\right\\}$
$\displaystyle\geq
1-\frac{1}{\delta}\int_{q}^{\lambda^{*}+\eta}\exp\left\\{-C_{L}^{\prime}(1-\lambda^{*})^{2}{n}\delta(\lambda^{*}-\lambda)^{2}\right\\}d\lambda\quad(C_{L}^{\prime}=C_{L}^{2}/8/4/(f_{\max}+C_{L}/6))$
$\displaystyle=1-\frac{1}{\delta}\int_{-\eta}^{\lambda^{*}-q}\exp\left\\{-C_{L}^{\prime}(1-\lambda^{*})^{2}{n}\delta\lambda^{2}\right\\}d\lambda\quad(\lambda\leftarrow\lambda^{*}-\lambda)$
$\displaystyle\geq
1-\frac{1}{\delta}\int_{-\infty}^{\infty}\exp\left\\{-C_{L}^{\prime}(1-\lambda^{*})^{2}{n}\delta\lambda^{2}\right\\}d\lambda$
$\displaystyle=1-\frac{1}{\delta}\sqrt{\frac{\pi}{C_{L}^{\prime}(1-\lambda^{*})^{2}{n}\delta}}=1-\sqrt{\frac{\pi}{C_{L}^{\prime}(1-\lambda^{*})^{2}M^{3}}}:=1-p_{\mathcal{D}^{c}}.\quad\left(\int_{-\infty}^{\infty}e^{-\lambda^{2}/2\sigma^{2}}d\lambda=\sqrt{2{\pi\sigma^{2}}}\right)$

Finally, there exists $N>0$ such that for ${n}\geq N$,

$\displaystyle
C_{L}(\lambda^{*}-\lambda_{j+1})\delta-\frac{\delta+(C_{L}(1-\lambda^{*})/8)\delta^{2}{n}(1-\lambda_{j+1})}{{n}(1-\lambda_{j})(1-\lambda_{j+1})}$
$\displaystyle\geq
C_{L}(\lambda^{*}-\lambda_{j+1})\delta/2,\quad\lambda_{j+1}\leq\lambda^{*}-\delta,$
$\displaystyle
C_{L}(\lambda_{j}-\lambda^{*})\delta-\frac{\delta+(C_{L}(1-\lambda^{*})/8)\delta^{2}{n}(1-\lambda_{j+1})}{{n}(1-\lambda_{j})(1-\lambda_{j+1})}$
$\displaystyle\geq
C_{L}(\lambda_{j}-\lambda^{*})\delta/2,\quad\lambda^{*}+\delta\leq\lambda_{j}\leq\lambda^{*}+2\delta.$

Then
$\mathcal{B}\cap\mathcal{D}\subseteq\cap_{q\leq\lambda_{j}\leq\lambda^{*}-2\delta}~{}\mathcal{A}_{j+1}\subseteq\\{\hat{\lambda}\geq\lambda^{*}-\delta\\}$
and
$\mathcal{B}\cap\mathcal{D}\subseteq\mathcal{A}_{\lceil\lambda^{*}-q\rceil/\delta+2}\subseteq\\{\hat{\lambda}\leq\lambda^{*}+3\delta\\}$
imply

$\displaystyle\mathbb{P}\left(\lambda^{*}-\delta\leq\hat{\lambda}\leq\lambda^{*}+3\delta\right)\geq\mathbb{P}\left(\mathcal{B}\cap\mathcal{D}\right)\geq
1-p_{\mathcal{B}^{c}}-p_{\mathcal{D}^{c}}.$

On $\mathcal{B}\cap\mathcal{D}$, we also obtain by $|g^{\prime}(t)|\leq
g_{\max}$,

$\displaystyle\hat{\pi}_{0}^{\hat{\lambda}}\leq\hat{\pi}_{0}^{{\lambda}_{\lceil\lambda^{*}-q\rceil/\delta-1}}\leq
g({\lambda}_{\lceil\lambda^{*}-q\rceil/\delta-1})+(C_{L}(1-\lambda^{*})/8)\cdot\delta\leq
g(\lambda^{*})+g_{\max}\delta+(C_{L}(1-\lambda^{*})/8)\cdot\delta.$

Case 2: $\lambda^{*}=q$. Notice that
$\mathcal{B}\cap\mathcal{D}\subseteq\mathcal{A}_{2}\subseteq\\{\hat{\lambda}\leq\lambda^{*}+3\delta\\}$
still holds, thus
$\mathbb{P}\left(\hat{\lambda}\leq\lambda^{*}+3\delta\right)\geq
1-p_{\mathcal{B}^{c}}-p_{\mathcal{D}^{c}}$. The analysis of
$\hat{\pi}_{0}^{\hat{\lambda}}$ is similar to that of case 1.

Case 3: $\lambda^{*}=1$. For any $0<\varepsilon<1$,

$\displaystyle\mathbb{P}(\hat{\lambda}\geq 1-\varepsilon)$
$\displaystyle\geq\mathbb{P}\left(\left(\cap_{q\leq\lambda_{j}\leq(1-\varepsilon)}~{}\mathcal{B}_{j+1}\right)\cap\left(\cap_{q\leq\lambda_{j}\leq(1-\varepsilon)}~{}\mathcal{D}_{j+1}\right)\right)$
$\displaystyle\geq
1-\frac{2}{\delta}\exp\left\\{-\frac{C_{L}^{2}(1-\varepsilon)^{2}{n}\delta^{2}/32}{f_{\max}+C_{L}(1-\varepsilon)\delta/12}\right\\}-\sqrt{\frac{\pi}{4C_{L}^{\prime}(1-\varepsilon)^{2}M^{3}}}$
$\displaystyle\to
1-\sqrt{\frac{\pi}{4C_{L}^{\prime}(1-\varepsilon)^{2}M^{3}}},\quad
n\to\infty.$

Let $M=\log({n})\to\infty$ and we have the consistency of $\hat{\lambda}$. On
$\left(\cap_{q\leq\lambda_{j}\leq(1-\varepsilon)}~{}\mathcal{B}_{j+1}\right)\cap\left(\cap_{q\leq\lambda_{j}\leq(1-\varepsilon)}~{}\mathcal{D}_{j+1}\right)$,

$\displaystyle\hat{\pi}_{0}^{\hat{\lambda}}\leq\hat{\pi}_{0}^{{\lambda}_{\lceil
1-\varepsilon-q\rceil/\delta-1}}\leq g({\lambda}_{\lceil
1-\varepsilon-q\rceil/\delta-1})+(C_{L}(1-\varepsilon)/4)\cdot\delta\leq
g(1)+g_{\max}(\varepsilon+\delta)+(C_{L}(1-\varepsilon)/4)\cdot\delta.$

  * •

We next prove Proposition 3 for the robust version stopping time
$\hat{\lambda}_{n}^{\prime}$ in (7). The proof largely follows that of the
non-robust version except that we need to additionally characterize the
estimated variance $\hat{V}^{\lambda}$.

Case 1: $q<\lambda^{*}<1$. Define the events

$\displaystyle\mathcal{A}_{j+1}^{c}=\begin{cases}\left\\{\hat{\pi}_{0}^{\lambda_{j}}+\hat{V}^{\lambda_{j}}\leq\hat{\pi}_{0}^{\lambda_{j+1}}+\hat{V}^{\lambda_{j+1}}\right\\},\quad&q\leq\lambda_{j}\leq\lambda^{*}-2\delta,\\\
\left\\{\hat{\pi}_{0}^{\lambda_{j}}+\hat{V}^{\lambda_{j}}\leq\hat{\pi}_{0}^{\lambda_{j+1}}+\hat{V}^{\lambda_{j+1}}\right\\},\quad&\lambda^{*}+\delta\leq\lambda_{j}<\lambda^{*}+\eta-\delta.\end{cases}$

Notice that

$\displaystyle\left\\{\hat{\pi}_{0}^{\lambda_{j}}+\hat{V}^{\lambda_{j}}\leq\hat{\pi}_{0}^{\lambda_{j+1}}+\hat{V}^{\lambda_{j+1}}\right\\}$
$\displaystyle\subseteq\left\\{\left(\hat{\pi}_{0}^{\lambda_{j+1}}-g(\lambda_{j+1})\right)-\left(\hat{\pi}_{0}^{\lambda_{j}}-g(\lambda_{j})\right)\geq-\left(g(\lambda_{j+1})-g(\lambda_{j})\right)-\hat{V}^{\lambda_{j+1}}\right\\},$
$\displaystyle\left\\{\hat{\pi}_{0}^{\lambda_{j}}+\hat{V}^{\lambda_{j}}\geq\hat{\pi}_{0}^{\lambda_{j+1}}+\hat{V}^{\lambda_{j+1}}\right\\}$
$\displaystyle~{}\subseteq\left\\{\left(\hat{\pi}_{0}^{\lambda_{j+1}}-g(\lambda_{j+1})\right)-\left(\hat{\pi}_{0}^{\lambda_{j}}-g(\lambda_{j})\right)\leq-\left(g(\lambda_{j+1})-g(\lambda_{j})\right)+\hat{V}^{\lambda_{j}}\right\\},$

and we only need to analyze $\hat{V}^{\lambda_{j}}$ additionally.

For $q\leq\lambda_{j}\leq\lambda^{*}+\eta$,

$\displaystyle\hat{V}^{\lambda_{j}}\leq\frac{1}{{n}}\cdot\frac{1}{4(1-\lambda_{j})^{2}}\leq\frac{1}{{n}}\cdot\frac{1}{(1-\lambda^{*})^{2}}.$
(15)

There exists $N>0$ such that for ${n}\geq N$,

$\displaystyle
C_{L}(\lambda^{*}-\lambda_{j+1})\delta-\frac{1}{{n}(1-\lambda^{*})^{2}}-\frac{\delta+(C_{L}(1-\lambda^{*})/8)\delta^{2}{n}(1-\lambda_{j+1})}{{n}(1-\lambda_{j})(1-\lambda_{j+1})}$
$\displaystyle\geq
C_{L}(\lambda^{*}-\lambda_{j+1})\delta/2,\quad\lambda_{j+1}\leq\lambda^{*}-\delta,$
$\displaystyle
C_{L}(\lambda_{j}-\lambda^{*})\delta-\frac{1}{{n}(1-\lambda^{*})^{2}}-\frac{\delta+(C_{L}(1-\lambda^{*})/8)\delta^{2}{n}(1-\lambda_{j+1})}{{n}(1-\lambda_{j})(1-\lambda_{j+1})}$
$\displaystyle\geq
C_{L}(\lambda_{j}-\lambda^{*})\delta/2,\quad\lambda_{j}\geq\lambda^{*}+\delta.$

Then
$\mathcal{B}\cap\mathcal{D}\subseteq\cap_{q\leq\lambda_{j}\leq\lambda^{*}-2\delta}~{}\mathcal{A}_{j+1}\subseteq\\{\hat{\lambda}^{\prime}\geq\lambda^{*}-\delta\\}$
and
$\mathcal{B}\cap\mathcal{D}\subseteq\mathcal{A}_{\lceil\lambda^{*}-q\rceil/\delta+2}\subseteq\\{\hat{\lambda}^{\prime}\leq\lambda^{*}+3\delta\\}$
imply

$\displaystyle\mathbb{P}\left(\lambda^{*}-\delta\leq\hat{\lambda}^{\prime}\leq\lambda^{*}+3\delta\right)\geq\mathbb{P}\left(\mathcal{B}\cap\mathcal{D}\right)\geq
1-p_{\mathcal{B}^{c}}-p_{\mathcal{D}^{c}}.$

On $\mathcal{B}\cap\mathcal{D}$, we also obtain

$\displaystyle\hat{\pi}_{0}^{\hat{\lambda}^{\prime}}$
$\displaystyle\leq\hat{\pi}_{0}^{{\lambda}_{\lceil\lambda^{*}-q\rceil/\delta-1}}+\hat{V}^{{\lambda}_{\lceil\lambda^{*}-q\rceil/\delta-1}}$
$\displaystyle\leq
g({\lambda}_{\lceil\lambda^{*}-q\rceil/\delta-1})+(C_{L}(1-\lambda^{*})/8)\cdot\delta+\frac{1}{{n}(1-\lambda^{*})^{2}}$
$\displaystyle\leq
g(\lambda^{*})+g_{\max}\delta+(C_{L}(1-\lambda^{*})/8)\cdot\delta+\frac{1}{{n}(1-\lambda^{*})^{2}}.\quad(|g^{\prime}(t)|\leq
g_{\max})$

Case 2: $\lambda^{*}=q$. The same argument as that of $\hat{\lambda}_{{n}}$.

Case 3: $\lambda^{*}=1$. For any $0<\varepsilon<1$,

$\displaystyle\mathbb{P}(\hat{\lambda}^{\prime}\geq 1-\varepsilon)$
$\displaystyle\geq\mathbb{P}\left(\left(\cap_{q\leq\lambda_{j}\leq(1-\varepsilon)}~{}\mathcal{B}_{j+1}\right)\cap\left(\cap_{q\leq\lambda_{j}\leq(1-\varepsilon)}~{}\mathcal{D}_{j+1}\right)\right)$
$\displaystyle\geq
1-\frac{2}{\delta}\exp\left\\{-\frac{C_{L}^{2}(1-\varepsilon)^{2}{n}\delta^{2}/32}{f_{\max}+C_{L}(1-\varepsilon)\delta/12}\right\\}-\sqrt{\frac{\pi}{4C_{L}^{\prime}(1-\varepsilon)^{2}M^{3}}}$
$\displaystyle\to
1-\sqrt{\frac{\pi}{4C_{L}^{\prime}(1-\varepsilon)^{2}M^{3}}},\quad
n\to\infty.$

Let $M\to\infty$ gives the consistency results. On
$\left(\cap_{q\leq\lambda_{j}\leq(1-\varepsilon)}~{}\mathcal{B}_{j+1}\right)\cap\left(\cap_{q\leq\lambda_{j}\leq(1-\varepsilon)}~{}\mathcal{D}_{j+1}\right)$,

$\displaystyle\hat{\pi}_{0}^{\hat{\lambda}^{\prime}}$
$\displaystyle\leq\hat{\pi}_{0}^{{\lambda}_{\lceil
1-\varepsilon-q\rceil/\delta-1}}+\hat{V}^{{\lambda}_{\lceil
1-\varepsilon-q\rceil/\delta-1}}$ $\displaystyle\leq g({\lambda}_{\lceil
1-\varepsilon-q\rceil/\delta-1})+(C_{L}(1-\varepsilon)/4)\cdot\delta+\frac{1}{4{n}(1-\varepsilon)^{2}}$
$\displaystyle\leq
g(1)+g_{\max}(\varepsilon+\delta)+(C_{L}(1-\varepsilon)/4)\cdot\delta+\frac{1}{4{n}(1-\varepsilon)^{2}}.$

∎

######  Lemma A.2.

Suppose for some $m\in\mathbb{N}$, $\frac{df^{k}}{dt^{k}}(t)$ exists and is
continuous on $[0,1]$, $0\leq k\leq m$. Then

$\displaystyle\frac{dg^{k}}{dt^{k}}(t)=\frac{k!}{(1-t)^{k+1}}\int_{t}^{1}\int_{t}^{t_{1}}\cdots\int_{t}^{t_{k}}\frac{df^{k}}{dt^{k}}(t_{k+1})~{}dt_{k+1}\cdots
dt_{2}dt_{1},\quad\forall~{}0\leq k\leq m.$ (16)

###### Proof of Lemma A.2.

We prove by induction. For $k=0$,

$\displaystyle
g(t)=\frac{\bar{F}(t)}{1-t}=\frac{\int_{t}^{1}f(t_{1})~{}dt_{1}}{1-t}.$

Assume Eq. (16) is true for $k$, then consider the case of $k+1$,

$\displaystyle\begin{split}\frac{dg^{k+1}}{dt^{k+1}}(t)&=\frac{d}{dt}\frac{dg^{k}}{dt^{k}}(t)\\\
&=\frac{(k+1)!}{(1-t)^{k+2}}\int_{t}^{1}\int_{t}^{t_{1}}\cdots\int_{t}^{t_{k}}\frac{df^{k}}{dt^{k}}(t_{k+1})~{}dt_{k+1}\cdots
dt_{2}dt_{1}\\\
&\quad~{}+\frac{k!}{(1-t)^{k+1}}\int_{t}^{1}\int_{t}^{t_{1}}\cdots\int_{t}^{t_{k-1}}\left(-\frac{df^{k}}{dt^{k}}(t)\right)dt_{k}\cdots
dt_{2}dt_{1}.\end{split}$ (17)

Notice that

$\displaystyle\begin{split}&\quad~{}\frac{k!}{(1-t)^{k+1}}\int_{t}^{1}\int_{t}^{t_{1}}\cdots\int_{t}^{t_{k-1}}\left(-\frac{df^{k}}{dt^{k}}(t)\right)dt_{k}\cdots
dt_{2}dt_{1}\\\
&=\frac{k!}{(1-t)^{k+1}}\cdot\left(-\frac{df^{k}}{dt^{k}}(t)\cdot\frac{(1-t)^{k}}{k!}\right)\\\
&=\frac{(k+1)!}{(1-t)^{k+2}}\cdot\left(-\frac{df^{k}}{dt^{k}}(t)\cdot\frac{(1-t)^{k+1}}{(k+1)!}\right)\\\
&=\frac{(k+1)!}{(1-t)^{k+2}}\int_{t}^{1}\int_{t}^{t_{1}}\cdots\int_{t}^{t_{k}}\left(-\frac{df^{k}}{dt^{k}}(t)\right)dt_{k+1}\cdots
dt_{2}dt_{1}.\end{split}$ (18)

Plug Eq. (18) into Eq. (17),

$\displaystyle\frac{dg^{k+1}}{dt^{k+1}}(t)$
$\displaystyle=\frac{(k+1)!}{(1-t)^{k+2}}\int_{t}^{1}\int_{t}^{t_{1}}\cdots\int_{t}^{t_{k}}\frac{df^{k}}{dt^{k}}(t_{k+1})-\frac{df^{k}}{dt^{k}}(t)~{}dt_{k+1}\cdots
dt_{2}dt_{1}$
$\displaystyle=\frac{(k+1)!}{(1-t)^{k+2}}\int_{t}^{1}\int_{t}^{t_{1}}\cdots\int_{t}^{t_{k}}\int_{t}^{t_{k+1}}\frac{df^{k+1}}{dt^{k+1}}(t_{k+2})~{}dt_{k+2}dt_{k+1}\cdots
dt_{2}dt_{1},$

and we have finished the proof. ∎