1

arXiv:1803.06790v2 [] 28 Mar 2018

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion
Eugene Katsevich
Department of Statistics
Stanford University
ekatsevi@stanford.edu

Aaditya Ramdas
Departments of Statistics and EECS
University of California, Berkeley
aramdas@berkeley.edu
03.30.18
Abstract

The false discovery rate (FDR) has become a popular Type-I error criterion for multiple testing, but it is not
without its flaws. Indeed, (a) controlling the mean of the false discovery proportion (FDP) does not preclude large
FDP variability, and (b) committing to an error level q before observing the data limits its use in exploratory data
analysis. In this paper, we take a step towards addressing both of the above drawbacks by proving uniform FDP
bounds for a variety of existing FDR procedures. In particular, many such procedures proceed by examining a
path of potential rejection sets ∅ = R0 ⊆ R1 ⊆ · · · ⊆ Rn ⊆ [n], assigning some algorithm-dependent estimate
d k ) to each one, and choosing the final rejection set Rk∗ via k∗ = max{k : FDP(R
d k ) ≤ q}. The resulting
FDP(R
∗
inferential guarantee applies only to the set Rk , guaranteeing the FDP of this set will be small on average. In
this paper, we prove that for a wide variety of such procedures (including Benjamini-Hochberg, accumulation
d bounds the FDP to within a small explicit
tests, knockoffs, AdaPT, and STAR), under independent p-values, FDP
constant factor calg (α), uniformly across the entire path, with probability 1 − α. In each case calg (α) scales
FDP(Rk )
has exponentially decaying tails. The consequences of this
like log( α1 ), meaning that the quantity supk FDP(R
d
k)
statement are two-fold. First of all, they imply that existing FDR procedures also have FDP bounded with high
probability by a small constant multiple of the target FDR level q. This constant is close to 2 for several procedures
at the 95% confidence level. Secondly, our bounds open up a middle ground between fully simultaneous inference
(guarantees for all 2n possible rejection sets), and fully selective inference (guarantees only for Rk∗ ). They allow
the scientist to spot one or more suitable rejection sets (select post-hoc on the algorithm’s trajectory) by picking
d k ) and the uniform upper band on
data-dependent sizes or error-levels, after examining the entire path of FDP(R
FDP. This post hoc mode of inference addresses both aforementioned drawbacks of FDR. Our bounds apply to
online FDR procedures as well, providing simultaneous high-probability uniform FDP bounds at arbitrary datadependent query times for arbitrary online procedures, including alpha-investing, LORD and SAFFRON. Our
analysis unifies existing martingale and empirical process viewpoints on FDR algorithms.

Keywords: false discovery rate, FDR, multiple testing, post hoc confidence bounds, false discovery exceedence, FDX, simultaneous selective inference, optional spotting, uniform martingale concentration.

1

Introduction

The false discovery rate (FDR) [1] is a popular Type-I error criterion for multiple testing problems. Given a set
of hypotheses H1 , . . . , Hn and a rejection set R ⊂ [n] obtained based on a set of p-values p1 , . . . , pn , the false
discovery proportion is defined by
V
|R ∩ H0 |
FDP(R) ≡
≡ ,
(1)
|R|
R
where H0 ⊂ [n] is the set of nulls. By convention, FDP ≡ 0 when R = ∅ (we use the ≡ symbol for definitions).
The false discovery rate is defined as the expectation of the false discovery proportion: FDR ≡ E [FDP].

2

1.1

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

Offline versus online multiple testing

Multiple testing may occur in a batch (or offline) context, where all p-values are available ahead of time, or in an
online context, where p-values arrive in a (potentially infinite) stream. Given an FDR target level q, e.g. q = 0.1,
the usual goal in the offline context is to find one set of rejections R for which
FDR ≡ E [FDP(R)] ≤ q.

(2)

In the online context, one tests a possibly infinite sequence of hypotheses, maintaining a rejection set Rk ⊇
Rk−1 at each time k, by irrevocably deciding whether to reject Hk immediately after seeing pk , but before seeing
pk+1 , . . . . These decision are made to ensure that for any k ∈ N, we have
FDRk ≡ E [FDP(Rk )] ≤ q.

(3)

In the batch setting, the most widely adopted FDR procedure is the Benjamini-Hochberg procedure [1], which
guarantees the desired bound (2) if the p-values are independent or positively dependent [2]. While the BH procedure satisfies certain optimality criteria when the hypotheses are treated as exchangable and there is no structure
to exploit [3], this fact is not true in the presence of prior information or structural constraints. Recognition of this
fact has led to the development of more powerful procedures that are applicable in a wide variety of settings, and
we will discuss many such examples in this work, like ForwardStop for sequential model selection [4], Selective
SeqStep for variable selection using knockoffs [5], multilayer grouped constructions like p-filter [6, 7, 8], accumulation tests for ordered testing [9], and interactive human-in-the-loop protocols like AdaPT [10] and STAR [11].
The online FDR literature began with Foster and Stine’s alpha-investing algorithm [12], with more recent work
proposing some generalizations [13], and also more powerful alternatives like LORD [14, 15] and SAFFRON [16].

1.2

Criticism of the FDR, and alternatives

The FDR and associated methodologies have gained broad acceptance across many application domains. This approach is attractive compared to controlling the family-wise error rate (FWER), defined as FWER = Pr{V > 0},
because it often affords more power while retaining a meaningful type-I error guarantee. Especially in modern
large-scale testing applications, requiring the absence of false discoveries with high probability is much too stringent. Despite the advantages of FDR, this error rate is not without its pitfalls. Its two primary weaknesses, which
several authors have highlighted already, are as follows.
FDR control gives no guarantee on FDP variability. The FDR by definition only controls the expectation of
the FDP. Hence, the data set at hand might have an FDP much higher than the nominal FDR target level. In this
paper, we show that even for independent p-values, some FDR procedures may exhibit high FDP variability. This
criticism also applies to the online context.
In order to remedy this issue, it has been proposed that the FDP be controlled with high probability, instead of
just on average:
Pr{FDP > γ} ≤ α.
The quantity on the left hand side is sometimes called the false discovery exceedance (FDX). Bounding the FDP
with high probability provides a high-confidence guarantee for a given dataset as opposed to a guarantee on average
across potential data sets. Several related step-down procedures have been proposed for FDX control in the offline
setting [17, 18, 19, 20, 21, 22], and a rather conservative Bonferroni-like approach by Javanmard and Montanari
(JM) [14] has been proposed in the online setting.
The standard multiple testing paradigm, and FDR control in particular, provides little or no flexibility.
Whether controlling FDR or FDX, the standard multiple testing paradigm involves choosing a target level q (or
bound γ) before looking at the data and formally cannot be changed afterwards. Even for a prespecified target
level q, FDR procedures do not allow for post hoc analyses. In the offline context, the rejection set R cannot be
modified (shrunk or expanded or altered otherwise) in a post hoc fashion without invalidating the guarantee. In the

3

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

online setting, we have no guarantees on FDPk at random times in the past, since the FDR guarantee (3) holds at
all fixed times but not uniformly over time.
This rigid multiple testing paradigm has limited applicability for exploratory data analysis, in which additional
flexibility is desirable, as eloquently argued by Goeman and Solari (GS) [23], as well as by earlier authors [24, 25].
GS argue that this inflexibility clashes with the practice of exploratory data analysis, where it is common to re-run
the algorithm with multiple target levels to get a set of the desired size, or to choose a subset of the rejection set
that makes sense based on the user’s domain knowledge.
To allow more flexibility in multiple testing, procedures have been designed [26, 27, 28, 29, 23, 30] to provide
high-probability bounds FDPα simultaneously for all subsets R ⊂ [n]:

Pr FDP(R) ≤ FDPα (R) for all R ≥ 1 − α.
(4)
While FDR and FDX are instances of selective inference, where inferential guarantees are made only on the
selected (i.e. rejected) set of hypotheses, statement (4) represents simultaneous inference, providing guarantees
on all 2n possible rejection sets. Goeman and Solari (GS) [23] argue that simultaneous inference paves the way
for a more flexible paradigm for multiple testing, called exploratory multiple testing. This paradigm reverses the
traditional roles of the data analyst and multiple testing algorithm. Instead of the data analyst providing an FDR
target level and the algorithm returning a rejection set, the algorithm provides simultaneous FDP bounds for all
sets, and then the data analyst may choose a rejection set however she wishes. For this reason, bounds like (4)
are also called post hoc bounds, bringing multiple testing procedures more in line with the practice of exploratory
data analysis. In addition to resolving the issue of a priori selection of the target level, exploratory multiple testing
allows data analysts to apply their domain knowledge, intuition, or any other outside information to examine
multiple candidate rejection sets and choose the one that makes the most sense for the given application.

1.3

Preview: Uniform FDP bounds for existing FDR procedures

Despite the weaknesses of FDR, this criterion and procedures controlling it are used widely in practice. Moreover, as described in Section 1.1, much progress has been made in designing FDR procedures in a variety of
settings. Moreover, while the FDR criterion itself does not provide any guarantees on FDP variability, at least
under independent (or weakly dependent) p-values, many of these procedures have been empirically found to have
well-behaved FDP. In particular, it is well-known the the BH procedure has a tight FDP histogram under independence. Hence, one of the goals of this paper is to formally study the FDX performance of existing FDR procedures
under independent p-values.
To get a handle on this question, we study a construction common to many offline FDR procedures, including
BH and nearly all others mentioned in Section 1.1. These procedures can be each viewed as constructing a path of
rejection sets
∅ = R0 ⊆ R1 ⊆ · · · ⊆ Rn ⊆ [n].
(5)
d k ) of false discovery proportion in Rk is defined. FiThen, for each k, an algorithm-dependent estimate FDP(R
nally, the algorithm rejects the set Rk∗ , where
d k ) ≤ q}.
k ∗ = max{k : FDP(R

(6)

It turns out that for all these procedures, when the p-values are independent, one can summarize a proof that they
control the FDR in a single line. One begins by constructing an appropriate backwards filtration Ωk with respect
to which k ∗ can be viewed as a stopping time, and then identifying a nonnegative backwards supermartingale Mk
with E [Mn ] ≤ 1, such that
FDP(Rk )
V (Rk )
=
≤ Mk .
(7)
d k)
FDP(R
Vb (Rk )
It is often an art to identify Mk , Ωk , but after doing so, the proof of the fact that FDR = E [FDP(Rk∗ )] ≤ q reduces
to the following simple argument that applies inequality (7) at stopping time k ∗ :
"
#


(ii)
FDP(Rk∗ ) (i)
FDP(Rk∗ )
≤E
≤ E [Mk∗ ] ≤ 1,
(8)
E
d k∗ )
q
FDP(R

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

4

03.30.18

where inequality (i) follows by definiton of k ∗ , and inequality (ii) follows by the optional stopping theorem. One
take-away message from the above proof is that, for a variety of existing procedures, proving that FDR ≤ q actually
amounts to establishing the fact that
"
#
FDP(Rk∗ )
E
≤ 1.
(9)
d k∗ )
FDP(R
The central technical claim of this paper is that, in fact, a similar kind of statement can be made uniformly over
the entire path.
Main result: For a variety of FDR procedures working with independent p-values, FDP(Rk ) is only a constant
d k ) (or a small variant thereof), uniformly over k with high probability. More precisely,
factor larger than FDP(R
we prove for several FDR algorithms that
(
)
FDP(Rk )
≤ calg (α) ≥ 1 − α,
Pr sup
(10)
d k)
k FDP(R
where calg (α) are explicit algorithm-dependent constants.
By integrating the bound (10) across α, we also obtain results of the form
"
#
FDP(Rk )
E sup
≤ Calg .
d k)
k FDP(R

(11)

Here, Calg are algorithm-dependent constants that are not only independent of the number of hypotheses n, but
remarkably, are less than 2 in most cases. If we compare inequality (11) with statement (9), we find that by paying
a factor of about 2 or less, we move from a bound at the point k ∗ to a uniform bound across the whole path.

1.4

Towards “simultaneous selective inference”: from stopping times to spotting times

Here, we briefly summarize some interpretations and implications of our bounds. To begin, it is possible to interpret
the bounds (10) and (11) in the context of the stopping time k ∗ in definition (6), or in fact also for any other post
d k∗ ) ≤ q. For such an index k ∗ , our bounds imply that
hoc means of selecting k ∗ for which FDP(R
Pr{FDP(Rk∗ ) ≤ calg (α) · q} ≥ 1 − α,

(12)

E [FDP(Rk∗ )] ≤ Calg · q.

(13)

and also that
For this reason, we call calg (α) an “FDP multiplier” and Calg an “FDR multiplier”. Note that inequality (12) states
something slightly surprising about existing FDR procedures: though designed to control the expected FDP at one
point, they automatically control FDX uniformly to within a multiplicative factor of the nominal level. In addition,
inequality (13) is useful for proving FDR guarantees in contexts where k ∗ has a complex definition (e.g. cannot be
described as the stopping time with respect to a backwards filtration). This partially alleviates the FDP variability
issue for FDR procedures, at least under independence.
Note that statements (12) and (13) apply to the context where a target FDR level q is specified in advance.
However, an equally important interpretation of the claim (10) is to view it as a uniform upper confidence bound
(or confidence envelope) for the unknown FDP along the path of the algorithm:
n
o
d k ) for all k ≥ 1 − α.
Pr FDP(Rk ) ≤ calg (α)FDP(R
(14)
d k ), we see that inequality (14) is similar to inequality (4), except it is a
Defining FDPα (Rk ) = calg (α)FDP(R
uniform statement over the path of an FDR procedure instead of over all subsets. Hence, statement (14) also
represents a solution to the issues concerning FDR laid out in Section 1.2: the uniformity of the bound provides
flexibility and its FDX formulation avoids the FDP variability problem of traditional FDR methods.

5

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

For these reasons, we refer to statements (10) and (11) as “optional spotting” bounds, where to spot is to Select
Posthoc On the Trajectory of the algorithm (the last term refers to the fact that each FDR algorithm effectively
uses the information available at hand to pick sets of shrinking sizes from the full set to the empty set, carving out
a trajectory of at most n + 1 sets out of the 2n possible sets).
Spotting is a variant of GS’s vision for exploratory multiple testing, where the user is first presented with the
d k ), calg (α)FDP(R
d k )) and the user has the option of “spotting” one
full trajectory of n + 1 triplets (Rk , FDP(R
or more sets whose combination of size, content, and high-probability FDP bound is to their liking. Reporting
the results on only some spotted triplets is statistically valid and mathematically principled, since the underlying
bounds are uniform and simultaneous over all n + 1 sets. The term optional spotting is also used to explicitly
contrast of our bounds (10) and (11) to the standard FDR guarantee (9), usually proved via optional stopping
arguments. Moving from stopping to spotting resolves both aforementioned drawbacks of FDR procedures at
the cost of a small multiplicative constant. Since this approach represents a middle path between fully selective
inference (guarantees on the single rejection set Rk∗ ) and fully simultaneous inference (guarantees for all possible
2n rejection sets), we term our approach as “simultaneous selective inference”. Indeed, the FDP is controlled
simultaneously, but only over the sets that were selected by the FDR algorithm. This approach is a promising path
towards flexible, powerful, and computationally tractable multiple testing procedures.

1.5

Summary of contributions and paper outline

Some contributions of our paper are briefly summarized below, after which we briefly describe the organization of
the rest of this paper.
• For several existing FDR procedures (or minor modifications thereof), we find tight and explicit constants
d process, assuming
bounding with high probability the extent to which the FDP process exceeds the FDP
independent p-values.
• We accomplish this by developing a simple yet versatile proof technique to obtain tight non-asymptotic
bounds for the probability that the stochastic process V (Rk ) hits the boundary c(α)Vb (Rk ).
• In the batch context, the corollary (12) shows that existing FDR procedures (or minor modifications thereof)
also control FDX to within a constant factor c(α) of the nominal target level q. For BH, c(α) ≈ 2.1
for α = 0.05, justifying theoretically the common observation that the FDP of BH is well-behaved under
independent p-values.
• In the online context, we prove statement (10) for a broad class of online procedures, covering all existing
online FDR algorithms and more. This provides high-probability bounds on FDP for any data-dependent
query times in the present or past.
• The reformulation (14) provides a uniform confidence envelope for the FDP process, echoing prior works
like GS [23] and GW [29]. This points towards an “optional spotting” approach to multiple testing that
addresses three common criticisms of traditional FDR methods.
• Since our bounds are fairly tight, the differences in FDP multipliers across procedures reflects differences in
the inherent variability of FDP for these procedures. Using this observation, we can quantitatively study the
trade-off between power and FDP quantiles.
Having overviewed our results and their implications, the remainder of the paper will focus on describing
the corresponding multiple testing procedures in more detail (Section 2), formally stating these results (Section 3),
discussing their implications for multiple testing (Section 4) and beyond (Section 5), exploring potential extensions
to the correlated setting (Section 6), and proving these results (Section 7). We conclude the paper in Section 8.

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

6

2

03.30.18

FDR controlling procedures: a unified review

The purpose of this section is two-fold: (a) to recap existing classes of FDR procedures for the uninitiated (especially since much rapid progress has been made in the past few years), and (b) to present the variety of procedures
using a somewhat unified viewpoint. Readers that are familiar with the literature may still benefit from the unified
view that we present here, which has not been provided elsewhere to the best of our knowledge. The impatient
reader may skip to Section 3, where we present our main results.
To begin, we note that in both the batch and the online contexts, a path (5) of rejection sets is constructed.
This path may be finite or infinite, depending on the context. For batch multiple testing, the path represents a
sequence of increasingly liberal rejection sets, among which one member (indexed by k ∗ ) is finally chosen as the
reported rejection set Rk∗ that satisfies the desired FDR bound (2). In this setting, the path is based on an ordering
π(1), . . . , π(n) of the hypotheses, constructed so that non-nulls are more likely to occur early in the ordering.
This ordering may be specified in advance or constructed data-adaptively. On the other hand, in the case of online
testing, the FDR guarantee is on each set Rk on the path (recall the definition (3)), and the ordering π is dictated
by the order in which hypotheses arrive in the stream, which might not be in the user’s control.
In the batch setting, in order to choose which set to reject, several algorithms adopt a common paradigm: the
FDP for each set Rk is estimated via
b
d k ) ≡ V (Rk ) ,
(15)
FDP(R
|Rk |
where Vb is a (possibly data-dependent) estimate of Vk ≡ |H0 ∩ Rk |. Then, the rejection set Rk∗ is defined via
d k ) ≤ q}.
k ∗ ≡ max{k : FDP(R

(16)

d Several
Batch FDR procedures vary based on the definitions of the ordering π, the path Rk and the estimate FDP.
examples are detailed in this section, and our theoretical guarantees will apply to all of them, such as
(a) Benjamini-Hochberg (BH) [1],
(b) accumulation tests [9], Selective SeqStep [5], and Adaptive SeqStep [31] for ordered testing, or
(c) AdaPT [10] and STAR [11] for interactive testing.
We first discuss batch procedures mentioned in items (a), (b) and (c), and then the case of online testing.

2.1

The BH procedure

In this procedure, π is the ascending ordering of the p-values, i.e. hypotheses are considered in order of increasing
p-value. Despite the discreteness of the path, it is easier to parameterize it using a continuous p-value threshold
t ∈ [0, 1]. Then, the rejection set corresponding to t is
Rt ≡ {j ∈ [n] : pj ≤ t},
d is based on the estimate
and FDP
Vb (Rt ) ≡ nt.
P

Note that E [Vt ] ≡ E [Rt ∩ H0 ] = j∈H0 Pr{pj ≤ t} = |H0 |t. Hence, Vb (Rt ) is an upwardly biased estimate of
Vt , the bias being fairly small if |H0 | ≈ n.

2.2

Ordered testing with a fixed, pre-defined order

As in BH, the hypothesis order π for ordered testing is chosen so that non-nulls are likely to occur near the
beginning of the ordering. However, unlike BH, the ordering π is specified in advance based on prior knowledge,

7

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

meaning that the hypotheses are ordered as Hπ(1) , Hπ(2) , . . . , Hπ(n) . Given such a predefined ordering π, two
kinds of rejection sets have been considered:
Rk ≡ {π(j) : j ≤ k};

(R1)

Rk ≡ {π(j) : j ≤ k, pπ(j) ≤ p∗ },

(R2)

for some pre-specified constant p∗ . The first choice corresponds to rejecting the first k hypotheses in the ordering
regardless of p-value, whereas the second corresponds to rejecting those among the first k with p-values below
a threshold p∗ . The definition of Rk clearly impacts the choice of Vb , so the two choices above lead to different
constructions of Vb .
Case (R1). For this choice of rejection sets, a family of accumulation tests has been proposed [9]. An accumulation function is a nondecreasing function h : [0, 1] → [0, ∞) that integrates to 1:
Z 1
h(u)du = 1.
0

For example, for λ ∈ (0, 1), the SeqStep [5] accumulation function is
h(pj ) ≡

I(pj > λ)
.
1−λ

1
Other choices include ForwardStop [4], which used h(u) = log( 1−p
), and HingeExp [9], which used h(pj ) =


1
1−λ
1−λ log 1−pj I(pj > λ)). In all cases, we note that Eu∼U [0,1] [h(u)] = 1, which inspires the definition

Vb (Rk ) ≡ B +

k
X

h(pπ(j) ),

(17)

j=1

for some constant B, often chosen as B = supu∈[0,1] h(u) if the latter quantity is finite. From the defining
properties of h, it follows that Vb (Rk ) is an upwardly biased estimator for Vb . The extra additive term B is a
regularization employed to ensure exact finite-sample FDR control. This FDR control does not hold without
regularization due to the unstable behavior of Vb near the beginning of the path; we return to this issue in Section
3. As a minor note, the original work on accumulation tests [9] required a slight modification of the definition
(15): they use the denominator 1 + |Rk | instead of |Rk |. For consistency with the other procedures discussed in
this paper, we deviate from the original authors’ proposal, and refer to the accumulation test as the procedure with
d defined via equations (15) and (17). We explicitly specify if we wish to refer to the original accumulation test
FDP
with 1 + |Rk | in the denominator.
Case (R2). The first procedure proposed for this case was Selective SeqStep [5], and a generalization called
Adaptive SeqStep [31] was later proposed. Selective SeqStep is defined via


k
X
p∗ 
Vb (Rk ) ≡
1+
I(pπ(j) > p∗ ) .
(18)
1 − p∗
j=1
Note that if p∗ is small, then even non-nulls are likely to contribute to Vb (Rk ), making the procedure more conservative. To fix this issue, Adaptive SeqStep [31] instead defines


k
X
p
∗ 
Vb (Rk ) ≡
1+
I(pπ(j) > λ) ,
(19)
1−λ
j=1
where λ > p∗ . For example, we might define p∗ = 0.1 and λ = 0.5.

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

8

2.3

03.30.18

Interactive algorithms (ordered testing with an adaptive order)

Recently, it was noted that ordered testing procedures described in the previous subsection can be improved and
generalized to a variety of settings, by constructing the ordering π data-adaptively, and possibly interactively with
a scientist-in-the-loop. Two examples are noted below.
AdaPT. Working in the context of definitions (R2) and (18) with p∗ = 0.5, Lei and Fithian note that only part
of the information in the p-values is being used at the inference step (namely I(p > 1/2)), so the “left over”
information may be used to help construct the ordering. This idea was inspired by the concept of data carving
[32]. More precisely, this left over information is captured by the masking function g(p) = min(p, 1 − p). Indeed,
note that min(u, 1 − u) and I(u > 1/2) are independent for uniformly distributed u. They showed that this
information g(pj ) can be used freely in order to determine the ordering π while maintaining the FDR guarantee
based on definition (18). Based on this idea, they proposed AdaPT (adaptive p-value thresholding), where the
ordering is constructed based on g(pj ) as well as arbitrary side information xj attached to each hypothesis. AdaPT
builds up the ordering π backwards, starting from π(n), at each step k using the information
Gk ≡ σ({xj , g(pj )}j∈[n] , {pπ(j) }j>k ),

(20)

to determine π(k). Note that in addition to the masked p-values and the side information, the AdaPT algorithm
gives access to unmasked p-values as well for hypotheses that have been excluded from the rejection set.
STAR. Despite the many benefits of AdaPT, it cannot guarantee that the final rejection set obeys any userspecified constraints or desired structural properties, and further, one was restricted to using the pair min(p, 1 − p)
and I(p > 1/2). This motivated the development of STAR (selectively traversed accumulation rules) [11], that
generalized the notion of data carving to any accumulation function (17), by showing that for any non-decreasing
h, a corresponding masking function g may be constructed. Like AdaPT, STAR also builds up the ordering from
back to front, using the information in the filtration (20), and also guaranteeing access to unmasked p-values for
hypotheses outside the rejection set. However, unlike AdaPT which uses definition (R2), the STAR procedure uses
definition (R1), allowing it to guarantee arbitrary user-defined structural constraints on the rejected sets (in fact,
these constraints can themselves be data-dependent).
We refer the reader to the original works for more intuition for how interaction is enabled by masking p-values.
In particular, the original authors describe many new problems for which we can control the FDR while having a
human-in-the-loop, possibly gaining power due to the human’s ability to use their intuition, prior knowledge and
flexible modeling capabilities. Here, we just point out that our bounds and resulting implications apply to both
AdaPT and STAR.

2.4

Online testing

Batch ordered testing procedures attempt to ensure that non-nulls occur early in the ordering (either using just
the raw p-values like in BH, or using just prior information like in ordered testing, or using a combination of
prior information, covariates and masked p-values in the case of AdaPT and STAR). In the online context, two
distinct situations can arise. If the order of the hypotheses is in the experimenter’s control, then once more it is
advantageous to attempt to use any available side information to have the non-nulls appear early in the ordering.
However, if the entire order of hypotheses is not in the experimenter’s control, then non-nulls might not necessarily
occur early, and further the rejection decision for the Hk must be made without knowing the outcomes of future
experiments. Hence, in general, online multiple testing procedures must proceed differently from aforementioned
batch experiments, since they may prefer not to reject most of the first k hypotheses while accepting the rest, and
may not wish to test all hypotheses at a fixed level. Instead, online procedures produce a sequence of levels αj at
which to test hypotheses, resulting in rejection sets of the form
Rk ≡ {π(j) : j ≤ k, pπ(j) ≤ αj }.

(21)

9

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

These levels αj are chosen based on the outcomes of past experiments. Foster and Stine’s alpha-investing procedure [12] and follow-up works [13, 14] are built on the analogy of testing a hypothesis at level αj as spending
wealth. One pays a price to test each hypothesis, and gets rewarded for each rejected hypothesis. In particular,
generalized alpha-investing (GAI) [13] is defined as follows. The procedure begins with wealth W0 ≤ α. At step
j, the algorithm pays a price of ϕj to test the jth hypothesis, and gets a reward ψj if this hypothesis is rejected:
Wj ≡ Wj−1 − ϕj + Rj ψj , where Rj = I(pj ≤ αj ). The rules for defining ϕj and ψj must be chosen so that
Wj ≥ 0 at all times j. A particular GAI procedure called LORD [14] chooses ϕj = αj , and ψj ≤ α.
Until recently, online FDR procedures were formulated without reference to an estimate of FDP. However, it
d defined by
was recently noted [15] that LORD implicitly keeps track of an FDP
Vb (Rk ) ≡

k
X

αj ,

(22)

j=1

d j ) ≤ q for all j. This places
reformulating the requirement that Wj ≥ 0 for all j as the requirement that FDP(R
LORD in the same framework as the batch algorithms considered in this paper. Moving beyond LORD, an adaptive
algorithm called SAFFRON [16] was recently proposed, which is defined by equation (21) and
Vb (Rk ) ≡

k
X
j=1

αj
I(pπ(j) > λj ).
1 − λj

(23)

SAFFRON improves upon the naive estimate (22) by correcting for the proportion of nulls, making it the online
analog of the Storey-BH procedure [33], or of Adaptive SeqStep (19). Like the levels αj , the constants λj may
also be chosen based on the outcomes of prior experiments. Interestingly, the original alpha-investing algorithm
is recovered by picking λj = αj , and the LORD estimate (22) is recovered by choosing λj = 0 (however, the
SAFFRON algorithm does not reduce to the LORD algorithm when λj → 0, because for nonzero λj , SAFFRON
requires λj ≥ αj for all j). Simulations [16] demonstrate that SAFFRON with constant λ = 1/2 successfully
adapts to the null proportion and enjoys higher power than LORD as a result.

2.5

Tying together ordered, interactive and online testing algorithms

By examining the procedures in the preceding sections, it is clear that they share many similar features. Here, we
make these similarities explicit by situating all ordered, interactive, and online testing algorithms in a common
framework. The first part of the framework is the definition (21) of the rejection sets, considered before in the
online context. Next, we note that (R1) and (R2) are recovered as special cases of definition (21), corresponding
to αk = 1 and αk = p∗ respectively. Lastly, we note that each definition of Vb can be written as
Vb (Rk ) ≡ a +

k
X

hj (pπ(j) )

(24)

j=1

for some additive regularization a and some functions hj . We call hj generalized accumulation functions, because
for uniform [0, 1] random variables U , they satisfy
Z

1

hk (u)du = αk = Pr{U ≤ αk } .

E [h(U )] = Eu∼U [0,1] [hk (u)] =

(25)

0

The above property allows us to generalize all earlier constructions, which satisfy the intuitive property of hk
obtained by comparing the leftmost and rightmost expressions in equation (25). Table 1 summarizes how the
different ordered, interactive and online testing procedures fall into this framework.
Having introduced several different classes of FDR procedures and presented them in a unified fashion, we
now turn to stating our uniform FDP bounds for these procedures.

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

10

Algorithm
Accumulation test
STAR
Selective SeqStep
AdaPT
Adaptive SeqStep
LORD
SAFFRON

a
a ≡ supu h(u)
a ≡ supu h(u)
p∗
a ≡ 1−p
∗
p∗
a ≡ 1−p
∗
p∗
a ≡ 1−λ
a≡0
a≡0

αk
αk ≡ 1
αk ≡ 1
αk ≡ p∗
αk ≡ p∗
αk ≡ p∗
(defined via GAI)
(defined via GAI)

hk
hk ≡ h
hk ≡ h
p∗
hk (pk ) ≡ 1−p
I(pk > p∗ )
∗
p∗
I(pk > p∗ )
hk (pk ) ≡ 1−p
∗
p∗
hk (pk ) ≡ 1−λ
I(pk > λ)
hk (pk ) ≡ αk
αk
hk (pk ) ≡ 1−λ
I(pk > λk )
k

03.30.18

π
fixed
adaptive
fixed
adaptive
fixed
(stream)
(stream)

Table 1: Ordered, interactive and online testing algorithms.

3

Main results

Before presenting our central theorems, we briefly discuss three subtle issues: additive regularization, reversal of
interactive procedures, and the use of arbitrary online rules. We will return to the first issue in more detail in the
next section, after presenting the main results.
Regularization. As noted earlier, past work has often used some additional regularization (denoted by the additive quantity a in the definition of Vb ) to ensure exact FDR control for many of the procedures under consideration.
Despite the fact that regularization is not necessary for FDR control for the other procedures—BH, LORD, and
SAFFRON—the behavior of Vb is nevertheless unstable near the beginning of the path. For example, consider BH
under the global null. Then,
(
)
)
(
Pn
FDP(Rt )
1
j=1 I(pj ≤ t)
Pr sup
>x = ,
> x = Pr sup
d
nt
x
t∈[0,1] FDPa=0 (Rt )
t∈[0,1]
as shown by Robbins in 1954 [34], which is in sharp contrast to the exponentially decaying tails that we derive
below using regularization. Without regularization, we would achieve an impractical
and nearly trivial
h
i confidence
FDP(Rt )
bound of c(α) = 20 for α = 0.05. Moreover, integrating across x gives E supt∈[0,1] FDP
d a=0 (Rt ) = ∞. This
motivates us to consider all procedures with regularization. In fact, we will prove bounds for Vb defined in equation
(24) with arbitrary a > 0, not just those dictated by Table 1. The only exception is BH, for which we will
take a = 1 by default. Let BH+, LORD+, and SAFFRON+ denote the regularized counterparts of the original
procedures. Specifically, note that
VbBH+ (Rt ) = 1 + nt.

(26)

Reversal of STAR and AdaPT. As discussed in Section 2.3, STAR and AdaPT build up the ordering π from
back to front, at each step choosing the least promising hypothesis to remove from the rejection set. The p-values
are masked until they are removed from the rejection set, at which point they are unmasked. We find reversed
versions of STAR and AdaPT more amenable to our theoretical analysis. Let rSTAR and rAdaPT be procedures
analogous to STAR and AdaPT, but which build up the ordering π from front to back; i.e. π must be predictable
with respect to the filtration
Gkr ≡ σ({xj , g(pj )}j∈[n] , {pπ(j) }j≤k ).
(27)
Hence, rAdaPT and rSTAR begin with R0 = ∅, and then at each step choose the most promising hypothesis to
add to the ordering. In this case, p-values are masked until they are added to the ordering, after which they are
unmasked. Note the difference between the filtrations (27) and (20); the p-values are unmasked upon entering the
path, rather than upon exiting the path. We do not anticipate this to change the behavior of these procedures by
much at all, and neither the original nor reversed procedures will uniformly dominate each other from the perspective of power. Indeed, as discussed in the original papers, the masked p-values contain most of the information in
the p-values, and the additional information obtained from unmasking a p-value is fairly incremental (to see this,

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

11

03.30.18

note that in the special case of h(pj ) = I(pj > 1/2), only a single bit per p-value is hidden at the start, and this is
all that is gained by unmasking). It is unlikely that there is a major difference between a top-down (full to empty)
and a bottom-up (empty to full) ordering, since the original and the reversed procedures both receive all masked
p-values right at the start, and both learn one unmasked p-value per step.
Arbitrary levels αk for online procedures. Whereas alpha-investing, LORD and SAFFRON each correspond
to a particular prescribed set of rules that decide the levels αk , our theoretical results hold whenever αk is any
predictable sequence, whether or not it was derived from any of the aforementioned online FDR algorithms. A
particularly extreme example would occur when αk is set to an absolute constant for all k; such a rule will not
guarantee control of the FDR, but our results will provide uniform bounds on the achieved FDP of such an online
algorithm at any time.

3.1

Optional spotting theorems

We first state our results for BH+, and then for ordered testing, interactive testing, and online testing. The results
below are illustrated in Figure 1, which shows the FDP multipliers (with α = 0.05) from Theorems 1, 2, 3, and 4
as well as the FDR multipliers from Corollary 1.
Theorem 1. (FDP multipliers; BH+). Suppose the null p-values are independent and uniformly distributed. Then,
the BH+ procedure (26) satisfies statement (10) for all α ≤ 0.31, with
cBH+ (α) ≡

log( α1 )
.
log 1 + log( α1 )

(28)

We remark that the range α ≤ 0.31 covers most practically relevant choices, but we conjecture that the bound
actually holds for all α. Next, we state the bounds for ordered testing procedures.
Theorem 2. (FDP multipliers; ordered testing). Suppose the null p-values are independent and superuniformly
distributed, i.e. Pr{pj ≤ s} ≤ s for all j ∈ H0 and s ∈ [0, 1].
1. Accumulation test: Given any (possibly unbounded) accumulation function h, and any additive regularization a, statement (10) holds for all α, with
log( α1 )

chacc (α) ≡
a log


R

1
0

−1  .

(29)

αh(u)/a du

Moreover, for any accumulation function bounded by B, we have
log( α1 )

chacc (α) ≤ cB
acc (α) ≡
a log



1−

1−αB/a
B

−1  .

(30)

For the original formulation of the accumulation test (additive regularization B, with 1 + |Rk | in the ded we have
nominator of FDP),


1
log(
)
1
1 +
 α  .
c̃B
(31)
acc (α) ≡
B
log B−α
B−1

2. Adaptive SeqStep, Selective SeqStep: Noting that the generalized accumulation function used by Adaptive
p∗
p∗
, statement (10)
SeqStep is bounded by B = 1−λ
, and that of Selective SeqStep is bounded by B = 1−p
∗
holds for all α, with:
log( α1 )

.
(32)
cB
(α)
≡
AS
B/a
a log 1 + 1−αB

12

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

When the ordering is not fixed, but is interactively determined, we have the following result.
Theorem 3. (FDP multipliers; interactive setting). If the null p-values are independent of each other and of the
non-null p-values, and the null p-values have nondecreasing densities, then statement (10) holds for all α with
B
B
B
cB
rAdaPT (α) ≡ cAS (α) and crSTAR (α) ≡ cacc (α). The definitions of B for rAdaPT and rSTAR mimic those for
Selective SeqStep and accumulation test respectively.
Lastly, shifting to the online FDR setting, we derive the following guarantee.
Theorem 4. (FDP multipliers; online setting). Let p1 , p2 , . . . be a stream of p-values adapted to a filtration Gk .
If the null p-values are superuniformly distributed conditional on the past, meaning that
Pr{pk ≤ s|Gk−1 } ≤ s for each k ∈ H0 and each s ∈ [0, 1],

(33)

then the bound (10) holds with the following constants:
1. LORD+. If αk is predictable with respect to Gk , then we have
cLORD+ (α) ≡

log( 1 )
 α 1 .
log( )
a log 1 + a α

2. SAFFRON+. If αk and λk are predictable with respect to Gk , with αk ≤ λk for all k, and supk
B < ∞, then we have cSAFFRON+ (α) ≡ cB
AS (α).

(34)

αk
1−λk

≤

d and not necessarily
Importantly, the names LORD+ and SAFFRON+ refer to the formulae used to calculate FDP,
to the rule used to derive the sequence αk . Indeed, one can theoretically use the LORD (or any other) rule to
d
derive αk , but give a post hoc uniform guarantee on the achieved FDP using the SAFFRON+ formula for FDP.
The following FDR multipliers can be calculated by integrating the above high-probabilty tail bounds.
Corollary 1. (FDR multipliers). For each of the above procedures except BH+, the bound (11) holds with
Z 1
Calg ≡
calg (α)dα.
0

R 0.31

For BH+, we instead have CBH+ = 0 cBH+ (α)dα + 0.69cBH+ (0.31). The above calculations typically yield
constants smaller than 2; for example CBH+ = 1.62, CLORD+ = 1.42 for a = 1, and CAS = 1.92 for B = 2 and
a = 1. See Figure 1 for more examples of FDR multipliers.
Remark 1 (A connection to prior work). A bound of the kind stated in Corollary 1 was first proved by [8] for
Selective SeqStep, with a = 1 and p∗ = 0.5, in the context of the multilayer knockoff filter. The goal of that
work was to prove FDR control for a predefined target level q with respect to multiple hypothesis groupings;
the uniform bound was necessary because the more complicated form of k ∗ in that context precluded the use of
standard martingale arguments.
Remark 2 (Assumptions for different procedures). The optional spotting theorems rely on slightly different assumptions on the distributions of the p-values. Note that Theorems 1 and 2 make assumptions only on the distribution (pj )j∈H0 , not requiring independence between null and non-null p-values. This is in contrast to FDR
results established before [1, 9] for the corresponding procedures, which do require independence between null
and non-null p-values. On the other hand, our results for ordered, interactive and online procedures result assume
dependence conditions that are nearly identical to the conditions that appear in the original works. Further, note
that Theorem 1 requires uniform null p-values, whereas the other theorems have looser restrictions on the distributions of null p-values. For ordered testing, we allow superuniform null p-values, an assumption that is at least
as general as those made for the original methods. For the interactive methods, we assume that null p-values have
an increasing density, which is the same assumption made by STAR and similar to the one made by AdaPT. Finally, our assumption of superuniformity conditional on the past for online procedures is similar to those made in
previous works [12, 14, 16].

13

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

Remark 3 (The constants for BH+). In Theorem 1, we require that α ≤ 0.31. However, strong numerical evidence
shows that the bound (10) is valid for BH+ with cBH+ (α) for all α. The restriction on α is an artifact of our proof
and does not represent an intrinsic breaking point of the bound. Despite this limitation in our proof, the range
α ≤ 0.31 comfortably includes any confidence level that would be used in practice. This limitation leads to an
estimate of CBH+ = 1.62, that is slightly more conservative compared to what we observed in simulations, which
suggest that in reality, CBH+ ≈ 1.35. Independently, we note that our constant being smaller than 2 seems morally
related to Eq. (12) in work by Goeman et al. [35], where the authors were interested specifically in FDP-quantiles
of BH (but did not derive any closed form bounds).

Figure 1: FDP multipliers for α = 0.05 (red) and FDR multipliers (salmon) for each method for a = 1. Where
applicable, multipliers for original regularizations shown using dashed lines.

3.2

Tightness of the bounds

Here, we investigate the tightness of our bounds using numerical simulations. For all simulations, we chose
n = 500. We simulated independent test statistics Xj = µj +j , where j ∼ N (0, 1), for j = 1, . . . , n, and derived
p-values pj = 1 − Φ(Xj ). Here, µj = µI(j ∈ H1 ). We chose a signal strength of µ = 4; other signal strengths
produced qualitatively similar figures. We simulated four sparsity settings, corresponding to |H1 | = 0, 10, 25, 50.
The locations of the signals were either chosen randomly, or biased towards the beginning. For each simulation
k)
setting, we generated 10,000 Monte Carlo realizations of supk FDP(R
.
d
FDP(R
k)
Figure 2 shows the theoretical FDP multipliers (in black) and empirical realizations (in shades of blue) for four
batch procedures: BH+, accumulation test with SeqStep accumulation function (p∗ = 0.5), Selective SeqStep with
p∗ = 0.5, and Adaptive SeqStep with p∗ = 0.05 and λ = 0.5. The regularization was chosen to be a = 1 for
each method. We generated the signals to be biased towards the beginning, because the three ordered methods are
designed with this assumption built in and for BH the order does not matter anyways.
We find that across the range of sparsity settings, the bounds are fairly tight. For BH+, the bounds get looser
as the number of non-nulls increases, which reflects the fact that the BH method does not correct for the non-null
proportion. For relatively small non-null proportions (common in modern large-scale testing applications), this

14

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

Figure 2: (Batch) The theoretically derived FDP bounds are generally tight for all four batch procedures considered.
does not have a large effect. For the other three methods, the performance is not affected much by the sparsity
level, because the SeqStep accumulation function and its variants are relatively insensitive to non-nulls as long
as their p-values are small enough. While our bounds c(α) are smooth in all cases, we see that the Monte Carlo
curves can be jagged, especially for SeqStep and Selective SeqStep. In these cases, this jaggedness reflects the
d
discreteness of FDP.
Figure 3 shows the results of a similar simulation for the online FDR methods considered here: LORD+
and SAFFRON+. For both LORD+ and SAFFRON+, we choose αk = 0.05 for all k, and for SAFFRON+ we
additionally set λk = 0.5 for all k. Again, we choose a = 1. Unlike batch ordered testing, the signals for online
testing do not necessarily occur near the beginning, so in addition we considered the situation when signals are
randomly located. Like BH+, we find that the bounds for LORD+ get looser as the sparsity fraction increases.
While for randomly located signals the difference is not very large, for signals near the beginning we see that the
LORD+ bound becomes quite conservative. This is because the “local” non-null fraction near the beginning is
large even if the overall non-null fraction is not, resulting in much looser bounds. On the other hand, we find that
the SAFFRON+ bounds are fairly tight across sparsity levels and signal locations.

4

Implications for existing FDR procedures and new spotting methods

The optional spotting theorems allow us to view existing FDR procedures in a new light. In addition, they point the
way towards a new spotting paradigm for exploratory multiple testing. In this section, we consider both of these
implications of our results.

15

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

Figure 3: (Online) The theoretically derived FDP bounds are generally tight, except for LORD+ when signals are
near the beginning. SAFFRON+ adapts to the non-null proportion and thus does not suffer from this issue.

4.1

New FDX bounds for existing FDR procedures

d k∗ ) ≤ q. As discussed in the introduction, the
Batch FDR procedures choose the rejection set Rk∗ so that FDP(R
optional stopping theorems immediately imply that in this setting,
Pr{FDP(Rk∗ ) ≤ calg (α) · q} ≥ 1 − α.

(35)

Hence, existing FDR procedures also control FDX at level calg (α) · q. To our knowledge, these are the first finitesample FDX bounds for FDR procedures.
Of course, the practical implications of this result depend on the multipliers calg (α). Figure 1 depicts these
multipliers for regularization a = 1 at confidence α = 0.05. We see from the figure that the constants are
remarkably small for BH+, SAFFRON+, and LORD+, all near 2. Hence, under independent p-values, the FDP of
BH+ is at most about twice the nominal level q with probability 95%. This provides a theoretical foundation for the
common knowledge that the FDP distribution of BH is tightly concentrated around its mean under independence.
On the other hand, note that the multipliers are somewhat larger for accumulation test and Selective SeqStep, both
being slightly larger than 4. As we discuss below, this reflects the fact that these procedures have intrinsically more
variable FDP than BH.
We must bear in mind that the aforementioned multipliers are obtained for regularization a = 1, which is
not necessarily the same as the original regularization. For those procedures where regularization was originally
employed, the corresponding multipliers are depicted in Figure 1 using dashed lines. We see from the discrepancies
between the multipliers for original regularization and a = 1 that the regularization necessary for FDR control says

16

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

little about the consequences for FDX control. For BH, LORD, and SAFFRON, no regularization is necessary for
FDR control, so we do not have FDP or FDR multipliers for those procedures. For Adaptive SeqStep, only a small
amount of regularization is necessary, so the resulting multipliers are very large. On the other hand, accumulation
tests require the most regularization for FDR control, and thus the multipliers are small. For both FDR and FDX
control, regularization is especially necessary for the case when few rejections are made. Our results suggest that
FDR methods with little or no regularization should be used with extreme caution (or not at all) in low-signal
scenarios. On the other hand, regularization does not have a large effect on an FDR procedure if the signal is
strong enough that there are many discoveries (which is anyways the case in which FDR is most applicable as an
error criterion). Hence, in many cases our results are relevant even for procedures like BH defined originally with
no regularization.

4.2

Quantifying FDP variability using the constants c(α)

As we have observed, different FDR procedures have different FDP multipliers. For example, the multiplier for
Selective SeqStep (for p∗ = 0.5) is about twice as large as the multiplier for BH+. Moreover, as demonstrated in
Section 3.2, our bounds are fairly tight. Hence, examining how calg (α) behaves for different procedures can help
provide insight about the intrinsic variability of FDP for these procedures. More precisely, (35) shows that calg (α)
is related to the quantiles of FDP. However, especially when comparing FDP quantiles between two procedures
controlling FDR at the same level (thus with roughly similar FDP means), the FDP quantiles are directly tied to
FDP variability. To illustrate this, consider the case of accumulation tests.
Li and Barber [9] show that any accumulation function bounded by B leads to the same FDR guarantee.
However, there are many accumulation functions with the same value of B. For example, the left panel of Figure
4 shows three such functions (truncated and renormalized if necessary to have B = 2). The right panel of this
figure has the corresponding FDP multipliers, and we observe that steeper accumulation functions have larger FDP
multipliers. This reflects the fact that for a uniform random variable U , h(U ) is more variable if h is steeper,
d
since this random variable has more mass at its extremes. This translates to an increase in the variance of FDP.
d
Since accumulation tests stop when FDP(Rk ) ≤ q, this in turn increases FDP variance. In particular, the SeqStep
accumulation function is the “steepest" among all accumulation functions with a fixed maximum B, corresponding
to the fact that
hSeqStep = arg max Var[h(U )].
h:h≤B

Hence, the SeqStep accumulation function leads to the highest-variance accumulation test. On the other hand,
Li and Barber showed that the SeqStep accumulation function also leads to the highest-power accumulation test!
Indeed, they proved that the asymptotic power of an accumulation test increases as the quantity Epj ∼F1 [h(pj )]
decreases, where F1 is the distribution of non-null p-values (assuming a two-groups model). Since non-null pvalues tend to be smaller, accumulation tests will be powerful to the extent that their accumulation functions put
d This makes steeper accumulation functions more powerful.
little mass near the origin, resulting in a smaller FDP.
This demonstrates that for accumulation tests controlling FDR at a fixed level, there exists a trade-off between
FDP variability and power. This is not surprising if we recall that the FDP variability in this context is a proxy
for FDP quantiles. It is well known that there is a trade-off between mean FDP and power; a similar trade-off
exists involving FDP quantiles, which are simply another way to measure the location of the FDP distribution.
This conclusion adds more nuance to Li and Barber’s conclusion that SeqStep accumulation functions are the most
powerful for a fixed FDR level. If we switch from considering the mean of the FDP to its upper quantiles, then
other accumulation functions are likely to more favorably trade off FDP with power. We leave this direction of
inquiry for future work.
We have used accumulation tests as a case study for what insight we can glean by inspecting the bounds calg (α).
The same approach can be used to make other comparisons between either different settings of the same method or
between different methods. As another example of the former, note that several of the methods under consideration
are indexed by a parameter B. If we inspect each of the FDP multipliers c(α) for these methods, we see that these
multipliers are all increasing in B. Hence, B can be interpreted as a parameter controlling the FDP variability for a
given method. In parallel to what we saw above, increasing B also has the dual effect of increasing power. Hence,
choosing B involves a trade-off as well. For brevity’s sake, we do not elaborate on this in detail but encourage

17

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

Figure 4: Three accumulation functions and the corresponding FDP multipliers. Note that the steeper the accumulation function, the larger the FDP multiplier.
the reader to think about B in the context of accumulation tests and Adaptive SeqStep. We can also use the
multipliers c(α) to make comparisons across procedures. For example, we saw that Selective SeqStep has a larger
FDP multiplier than BH. This reflects the fact that Selective SeqStep relies on “one-bit p-values" I(pj > 0.5) to
d This results in a coarse estimate of FDP, which we see reflected in the increased multiplier.
define FDP.

4.3

“Simultaneous selective inference” via spotting

Our optional spotting theorems can provide more information than just about FDP(Rk∗ ) for k ∗ defined using
d k ) is a confidence envelope for the entire FDP
a fixed q. Indeed, we have proved that FDP(Rk ) = c(α)FDP(R
curve; recall (14). This puts our bounds into the realm of the uniform FDX literature, where many other confidence
envelopes for FDP have been proposed, including [26, 27, 29, 23, 30]. Some works [26, 29, 23] directly construct
bounds on the FDP of all subsets, whereas other [27] bound FDP only across a path of candidate rejection sets.
The latter kind of FDP bounds can be extended to any other sets, as pointed out implicitly by GW [29] and GS
[23], and explicitly by more recent work [30]. In particular, this implies that our uniform bounds on FDP(Rk ) can
also be extended to uniform bounds on all subsets.
Most of the existing literature on uniform bounds for FDP takes place in the unstructured setting, where hypotheses are considered in order of increasing p-values. Hence, the existing confidence envelopes are most comparable with our confidence envelope for BH+. We have found that confidence envelopes like those of [29] can
be competitive with or even tighter than those we derive for BH+. We do not show these comparisons here, since
it is not the goal of this work to derive the tightest possible confidence envelopes for FDP. As another point of
comparison, the closest result in the online setting is that of Javanmard and Montanari (JM) [14]. JM consider a
truncated version of GAI rules that satisfy a uniform FDX bound like Pr{supk FDPk ≥ γ} ≤ α. Their result is
similar in spirit to our result in Theorem 4 about LORD+, but there are some subtle differences. Their results, like
most other FDX bounds, are pre-hoc, meaning that given a γ, α ∈ (0, 1), their procedure produces a sequence of
rejections satisfying the desired FDX guarantee. Our guarantees are post hoc, meaning that they would apply to
any sequence of rejections produced by any online algorithm, that may or may not have been designed for FDR or
FDP control.
On the other hand, we are not currently aware of confidence envelopes that explicitly leverage side information

18

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

in the form of covariates, a priori hypothesis orderings, and so on. If this side information is informative, we expect
that better confidence envelopes can be developed than those derived in the unstructured setting. From this point
d k ) we derived for all procedures except BH represent the first
of view, the envelopes FDP(Rk ) = c(α)FDP(R
uniform FDX bounds in structured settings. We leave the uniform FDX performance of these envelopes for future
work.
As observed by Goeman and Solari before us, uniform bounds on FDP open up the possibility to reconcile data
exploration with multiple testing, via post hoc inference. Our bounds suggest that FDR procedures themselves
d Using prior information
can be reinterpreted as vehicles for simultaneous inference based on the path of FDP.
if applicable, the FDR procedures we analyze can be viewed as carving out a path of candidate rejection sets,
d is small. We hope that
from which the user can spot a set of appropriate size and content, while keeping FDP
restricting the user’s attention to a smaller collection of promising candidate rejection sets (simultaneous selective
inference) can keep the exploration more focused while enjoying better statistical and computational properties
than simultaneous inference.
In the previous section, we found trade-offs between power and FDP variability. For a procedure controlling
d (lower FDP
d permits more discoveries), and the
FDR at a fixed target level q, the power is represented by FDP
FDP variability is represented by c(α). The same trade-off is present in the confidence envelope FDP(Rk ) =
d k ), where these two quantities come together. Hence, good confidence envelopes must also navigate
c(α)FDP(R
d
the trade-off between c(α) and FDP.
To investigate this phenomenon further, we conducted a numerical experiment to examine the effect of accumulation function on the FDP confidence envelope. We consider the same simulation setup as in Section 3.2, with
50 non-nulls, except we decrease the signal amplitude to µ = 2.5. The reason for this is that the differences in
d are more pronounced when the signal is weaker, so there is a nontrivial trade-off between power and FDP
FDP
variability. To consider an extreme case, if the non-null p-values all equaled zero, then the accumulation function
h(pj ) = I(pj > 0) would simultaneously maximize power and minimize FDP variability.

d and FDP for three accumulation functions. In the left panel, the three paths of FDP
d
Figure 5: Comparing FDP
d
are plotted, along with the mean FDP. Flatter accumulation functions lead to larger FDP estimates. In the right
d k ) are shown for the three accumulation functions, along with the pointwise FDP
panel, FDP(Rk ) = c(α)FDP(R
d with HingeExp providing the best FDP curve.
quantiles. We see the nontrivial trade-off between c(α) and FDP,
In Figure 5, we compare the SeqStep, HingeExp, and ForwardStop accumulation functions. The first panel
d curves, averaged over 10,000 simulations. For comparison, the black curve is the average true
depicts the FDP

19

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

d then HingeExp in a close second,
FDP. As expected, the SeqStep accumulation function leads to the smallest FDP,
d
and then ForwardStop has the largest FDP. This trend reflects how steep each accumulation function is. The second
d k ). As a reference, the black curve represents the pointwise 1−α
panel shows the average FDP bounds c(α)FDP(R
d but the largest c(α),
quantiles for the true FDP. Here, we see the trade-off in action. SeqStep has the smallest FDP
and as a result leads to the worst FDP bound. ForwardStop and HingeExp both give better bounds than SeqStep,
with HingeExp being a little better over the most interesting range of k, around 25-50. Hence, HingeExp strikes
the best balance between power and FDP variability.

5
5.1

Implications beyond standard multiple testing
From multiple testing to model selection

All of the results presented here have been formulated in the multiple testing context, where we have p-values
available for a set of hypotheses. However, these results also apply to model selection and variable selection
contexts as well. In particular, G’Sell et. al. [4] proposed the ForwardStop accumulation function as a means to
the end of model selection with FDR control. Using selective inference techniques, valid p-values may be obtained
at each step of forward step-wise regression, and thus an accumulation test may be applied to select a model. As
another example, the knockoff filter [5] is a recent proposal for FDR control in the variable selection context.
Their idea is to create a knockoff variable for each original variable, and then use these knockoffs as controls for
the originals. Instead of p-values, the knockoff filter produces knockoff statistics Wj for each variable j. However,
the methodology is based on the fact that sign(Wj ) are independent fair coin flips for null j, in effect producing a
set of “one-bit p-values”. Then, Selective SeqStep with p∗ = 0.5 may be applied to these one-bit p-values to select
a set of variables with FDR control. Hence, our uniform FDX bounds apply to the knockoff filter as well.
It is interesting to note that the knockoff filter has been observed to produce somewhat highly variable results,
due to the coarse nature of one-bit p-values. We encountered this phenomenon in our theoretical results, since the
FDP multiplier c(α) for Selective SeqStep was one of the largest among the procedures considered.

5.2

Extensions to the multilayer setting using the p-filter

An intermediate statistical guarantee between FDR control and uniform FDX control is multilayer FDR control,
introduced by Barber and Ramdas [6]. This criterion applies when the rejected set R will be interpreted according
to multiple groupings (or layers) that are specified in advance. For example, these authors consider an application to
neuroscience, in which the hypotheses are indexed by brain location and by time. Then, specific voxels discovered
to be activated at specific times may be interpreted by grouping by time (finding voxels activated at any time
during the experiment) or by location (finding times at which any voxels were active). Multilayer FDR control is
the requirement that FDRm ≤ qm for each layer m, where qm are pre-specified FDR target levels.
Barber and Ramdas proposed the p-filter methodology, where p-value thresholds at each layer are chosen such
that an estimate of FDP at each layer m is below the target threshold qm , with extensions [7] proposed to handle
weights, adaptivty, overlapping or incomplete groups, etc.
Porting the p-filter into the variable selection setting, Katsevich and Sabatti introduce the multilayer knockoff
filter [8], which allows (group) knockoff statistics to be used at each layer instead of p-values. The proof of the
multilayer knockoff filter proceeds by decoupling the layers from each other via supremum bounds like inequality
(11), which was proved for Selective SeqStep and conjectured for BH+. However, the purpose of these bounds
was, like in most classical settings, as a tool to guarantee FDR control of the underlying procedure. In this paper,
we prove the conjecture for BH+, extend our proof technique to a multitude of other procedures and settings,
provide the post hoc spotting interpretation of these bounds in terms of uniform guarantees on the FDP, and more.
Now that our paper derives such supremum bounds for a much larger variety of procedures, we note that one
may use the same p-filter framework to arbitrarily “stack" any of these FDR procedures at different layers (meaning
that we could apply a different procedure at each layer) while maintaining multilayer FDR control.

20

6

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

Future work: the effect of correlation

Note that all of the results in this paper have assumed independence of p-values in one form or another. Many of
the procedures considered here also only have guarantees under independence, though BH is a notable exception.
Aside from online testing applications, independent p-values are hard to come by in practice, so more robust
guarantees are necessary. BH is known to control FDR under the PRDS criterion [2], a form of positive dependence
that contains no information about the strength of the dependence. Indeed, a set of p-values that are all equal to
each other almost surely satisfy the PRDS condition. However, it is known that while the mean of FDP might not
change much as dependence increases, the variance of the FDP will increase [36, 37]. Hence, high-probability
bounds on FDP under dependence are likely to use criteria other than PRDS to capture this dependence.

Figure 6: FDP multipliers under local correlation are displayed for several algorithms. For all subplots, negative
correlation does not seem to hurt, but strong positive correlations violate our theoretical bounds.
As a first step in this direction, Figure 6 shows the result of numerical simulations under AR(1) dependence for
the six procedures considered before, all with a = 1. These curves all correspond to the global null case, which
leads to the largest FDP multipliers. As we vary the correlation parameter ρ from −0.9 to 0.9, we can see how the
empirical quantiles change. We observe that higher correlations lead to larger FDP quantiles, as expected, but under
moderate correlations these quantiles are still below or at least near the theoretical bounds under independence.
Figure 7 shows how the expectation bounds change with ρ. Interestingly, for all methods besides Selective
SeqStep and accumulation test, the FDR multipliers are U-shaped, whereas for the two aforementioned methods,
the empirical quantiles are monotonically increasing in ρ. The bounds for BH+ and LORD+ are remarkably robust
to local correlation, whereas the other bounds grow somewhat more rapidly for large ρ. Investigating theoretically
how our bounds change under correlation (and how to precisely quantify correlation) is left for future work.

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

21

03.30.18

Figure 7: FDR bounds under local correlation are displayed for several algorithms. Most procedures seem less
affected by negative correlation than by strong positive correlations. Crosses indicate multipliers for ρ = 0, the
case with independent p-values as considered in the theorems of this paper.

7

Proofs of the four optional spotting theorems

The method we employ to obtain all our FDP multipliers is to investigate the properties of the stochastic process
FDP(Rk ). Below, we prove the optional spotting theorems; the proof of Corollary 1 will follow from the fact that
the expectation of a random variable is the integral of its quantile function. We start with the BH+ procedure, for
which we must proceed differently since the hypotheses are ordered according to the p-values, while for all other
d
settings, the hypothesis order is either pre-specified or is in some sense “orthogonal” to FDP.

7.1

FDP multipliers for BH+

Proof of Theorem 1. Let Vt ≡
(

P

FDP(Rk )
Pr sup
≥x
d k)
k FDP(R

j∈H0

)

I(pj ≤ t). Then, for any fixed x > 1 we have
(

Vt
= Pr sup
≥x
1
+
nt
t∈[0,1]

)
= Pr{Vt ≥ x + xnt, for some t ∈ [0, 1]} .

(36)

Hence, the quantity of interest is the probability that the stochastic process Vt hits the linear boundary x + xnt.
This event is illustrated in Figure 8.

22

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

Figure 8: Stochastic process view of (36), with the solid black line representing Vt , the dashed red line representing
the linear boundary x + xnt, and the dashed black line being the diagonal that emphasizes our knowledge that
V (0) = 0 and V (1) = n.
Since the null p-values were assumed to be independent and uniformly distributed, we deduce that the distribution of Vt is that of an unscaled empirical process for n0 = |H0 | uniform random variables. If we were to
replace Vt by the unscaled empirical process of n ≥ n0 uniform random variables, denoted Vt0 , it can only increase
the probability in equation (36). However, it is somewhat difficult to obtain non-asymptotic bounds for hitting
probabilities of empirical processes like Vt0 . Instead, we claim that for x ≥ 1.5, replacing Vt0 with a rate n Poisson
process Nt only further increases the hitting probability:
Pn
i.i.d.
Lemma 1. Let Vt0 ≡ j=1 I(pj ≤ t) for pj ∼ U [0, 1]. Let Nt be a rate n Poisson process. Then, for x ≥ 1.5,
Pr{Vt0 ≥ x + xnt, for some t ∈ [0, 1]} ≤ Pr{Nt ≥ x + xnt, for some t ∈ [0, 1]} .

(37)
d

See the appendix for the proof of this lemma. To understand why the lemma holds, note that Vt0 = Nt |N1 = n;
i.e. the distribution of the empirical process is the same as that of the Poisson process, conditioned on observing
exactly n events at time t = 1. Hence, Lemma 1 states that for sufficiently large x, a Poisson process is less likely
to hit the line t 7→ x + xnt if we know that it is equal to its mean at time t = 1. This makes intuitive sense because
the process needs to be far above its mean to hit this line for large x, which is less likely to happen if it must be
equal to its mean at time t = 1.
Now, we may use the martingale properties of Poisson processes to bound the probability a Poisson process
hits a linear boundary:
Lemma 2 ([8]). If Nt is a rate n Poisson process, then for any x > 1, we have
Pr{Nt ≥ x + xnt for some t ∈ [0, 1]} ≤ exp(−xθx ),
where θx is the unique positive root of the equation
eθ = 1 + θx.

(38)

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

23

03.30.18

To complete the derivation of the FDP multiplier for BH+, suppose we choose x such that α = exp(−xθx ).
Then, plugging this choice of x into the definition of θx implies that
x=

− log α
− log α
− log α
=
=
= cBH+ (α),
θx
log(1 + θx x)
log(1 − log α)

(39)

which proves the bound (28). Hence, statement (10) holds for all α corresponding to x ≥ 1.5, which translates to
holding for all α ≤ 0.31, since cBH+ (0.31) = 1.5.

7.2

An exponential tail inequality lemma

The optional spotting theorems for each of the ordered, interactive and online testing procedures will be derived in
the next subsection, as consequences of the following lemma.
Lemma 3. Consider an ordered testing procedure (batch or online), as described in Section 2.5. Suppose there
exists a filtration
Fk ⊇ σ(H0 , {π(j)}j≤k , {pπ(j) , αj }j≤k,π(j)∈H0 ).
(40)
such that for all π(k) ∈ H0 , we have



Pr pπ(k) ≤ αk Fk−1 ≤ αk and E hk (pπ(k) ) Fk−1 ≥ αk

almost surely.

(41)

Then, for each x > 1,
(

FDP(Rk )
Pr sup
≥x
d k)
k FDP(R

)
≤ exp(−aθx x),

(42)

where θx is defined in the following four cases:
1. If hk = h for some accumulation function h, αk = 1, π(k) is pre-specified (i.e. nonrandom), and pπ(k) ⊥
⊥
Fk−1 for all π(k) ∈ H0 , then θx is the unique positive root of the equation
Z 1
exp(−θxh(u))du = exp(−θ).
(43)
0

2. If hk = h for some accumulation function h bounded by B and αk = 1, then θx is the unique positive root
of the equation
1 − exp(−θxB)
= 1.
(44)
exp(−θ) +
B
3. If hk (p) = 0 for all p ≤ αk , and hk (p) ≤ B for all k, p, then θx is the unique positive root of the equation
exp(θ) −

1 − exp(−θxB)
= 1.
B

(45)

4. If hk (pk ) = αk , then θx is the unique positive root of equation (38).
Proof. Fix any arbitrary x > 1 and θ > 0. Since we make no assumptions whatsoever on the non-null p-values,
we first restrict our attention to only the nulls as follows:
(
)
(
)
FDP(Rk )
V (Rk )
Pr sup
≥ x = Pr sup
≥x
b (Rk )
d k)
k FDP(R
k V


k
k
X

X
= Pr
I(pπ(j) ≤ αj )I(π(j) ∈ H0 ) ≥ ax + x
hj (pπ(j) ), for some k


j=1
j=1


k
k
X

X
≤ Pr
I(pπ(j) ≤ αj )I(π(j) ∈ H0 ) ≥ ax + x
hj (pπ(j) )I(π(j) ∈ H0 ), for some k .


j=1

j=1

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

24

03.30.18

Now, we may rearrange terms and employ the Chernoff exponentiation trick, to conclude that:


 

(
)
k


X
FDP(Rk )
Pr sup
≥ x = Pr sup exp θ  [I(pπ(j) ≤ αj ) − xhj (pπ(j) )]I(π(j) ∈ H0 ) ≥ exp(aθx)
d k)
 k

k FDP(R
j=1


≡ Pr sup Zk ≥ exp(aθx) .
k

We claim that if θ = θx , then Zk is a supermartingale with respect to Fk . Note that this supermartingale and
filtration is unrelated to the supermartingale Mk and filtration Ωk mentioned in the introduction of this paper
that are typically used to prove FDR control for these procedures (indeed, Zk , Fk are forward supermartingales
and filtrations, while Mk , Ωk are backwards supermartingales and filtrations). If Zk is indeed a supermartingale as
claimed, then the conclusion of the lemma would follow from the maximal inequality for positive supermartingales:


Pr sup Zk ≥ exp(aθx) ≤ exp(−aθx)E [Z0 ] = exp(−aθx),
(46)
k

as desired. Hence the rest of this proof will focus on showing the supermartingale property of Zk . Note first of all
that Zk is adapted to Fk by assumption (40). Hence, it suffices to show that





Zk
Fk−1 = E exp [θ(I(pπ(k) ≤ αk ) − xhk (pπ(k) ))]I(π(k) ∈ H0 ) Fk−1 ≤ 1.
E
Zk−1
Clearly, this inequality holds for any k such that π(k) 6∈ H0 . For k such that π(k) ∈ H0 , we find that



E exp θ(I(pπ(k) ≤ αk ) − xhk (pπ(k) )) Fk−1



= E I(pπ(k) ≤ αk ) exp θ(1 − xhk (pπ(k) )) Fk−1



+ E I(pπ(k) > αk ) exp −θxhk (pπ(k) )) Fk−1 .

(47)

To show that the above quantity is at most one, we consider the four cases defined in the statement of the lemma.
Case 1:
Since αk = 1, the second term of equation (47) equals zero. Since hk = h, π(k) is fixed, and
pπ(k) ⊥
⊥ Fk−1 , the first term simplifies to






E exp θx (1 − xh(pπ(k) )) Fk−1 = E exp θx (1 − xh(pπ(k) ))
≤ exp(θx )EU ∼U [0,1] [exp(−θx xh(U ))]
= 1,
The inequality holds because pπ(k) is superuniformly distributed by assumption and u 7→ exp(−θx xh(u)) is
a nonincreasing function (since h is nondecreasing by definition), and the last step holds because θx satisfies
equation (43) by definition.
Case 2:

Again, the second term of equation (47) equals zero because αk = 1. We may bound the first term as:





1 − exp(−θx xB)
E exp θx (1 − xh(pπ(k) )) Fk−1 ≤ exp(θx )E 1 −
h(pπ(k) ) Fk−1
B


1 − exp(−θx xB)
≤ exp(θx ) 1 −
B
= 1.

In the first line, we used the fact that hk (pπ(k) ) = h(pπ(k) ) ≤ B, and we bounded the convex function z 7→
1−exp(−θx xB)
exp(−θ
z. In the second step, we used the assumption
x xz) on [0,B] with the line z 7→ 1 −
B

E h(pπ(k) ) Fk−1 ≥ αk = 1, and in the third line we used the definition of θx .

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

25

03.30.18

Because hk (p)I(p ≤ αk ) = 0, the first term of equation (47) simplifies to




E I(pπ(k) ≤ αk ) exp θx (1 − xhk (pπ(k) )) Fk−1 = exp(θx )Pr pπ(k) ≤ αk Fk−1 .

Case 3:

To bound the second term, we write



E I(pπ(k) > αk ) exp −θx xhk (pπ(k) )) Fk−1




1 − exp(−θx xB)
Fk−1
≤ E I(pπ(k) > αk ) 1 −
hk (pπ(k) )
B


1 − exp(−θx xB) 
= Pr pπ(k) > αk Fk−1 −
E hk (pπ(k) )I(pπ(k) > αk ) Fk−1
B


1 − exp(−θx xB) 
= Pr pπ(k) > αk Fk−1 −
E hk (pπ(k) ) Fk−1
B

1 − exp(−θx xB)
αk .
≤ Pr pπ(k) > αk Fk−1 −
B
The inequality in the second line follows from the same convexity argument as in Case 2, the fourth
 line is a
consequence of the fact that hk (p)I(p ≤ αk ) = 0, and the last line follows from E hk (pπ(k) ) Fk−1 ≥ αk .
Combining the results of the previous two equations, we obtain that






E I(pπ(k) ≤ αk ) exp θx (1 − xhk (pπ(k) )) Fk−1 + E I(pπ(k) > αk ) exp −θx xhk (pπ(k) )) Fk−1


1 − exp(−θx xB)
≤ exp(θx )Pr pπ(k) ≤ αk Fk−1 + Pr pπ(k) > αk Fk−1 −
αk
B

1 − exp(−θx xB)
= (exp(θx ) − 1)Pr pπ(k) ≤ αk Fk−1 + 1 −
αk
B
1 − exp(−θx xB)
αk
≤ (exp(θx ) − 1)αk + 1 −
B


1 − exp(−θx xB)
= αk exp(θx ) − 1 −
+1
B
= 1.
The inequality in the fourth line follows from the first part of assumption (41), and the last equality follows from
the definition of θx .
Case 4:

Since hk (p) = αk , equation (47) simplifies to:


exp(θx (1 − xαk ))Pr pπ(k) ≤ αk Fk−1 + exp(−θx xαk )Pr pπ(k) > αk Fk−1

= exp(−θx xαk )((exp(θx ) − 1)Pr pπ(k) ≤ αk Fk−1 + 1)
≤ exp(−θx xαk )((exp(θx ) − 1)αk + 1).

Noting that θx satisfies (38), we see that the above expression can be bounded by one:
exp(−θx xαk ) (θx xαk + 1) ≤ 1,
as desired, where the inequality follows because the function z 7→ e−z (z + 1) is decreasing and takes the value 1
at z = 0.

7.3

Proofs of Theorems 2, 3, and 4

Now, we may derive Theorems 2, 3, and 4 as corollaries of Lemma 3.

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

26

03.30.18

Proof of Theorem 2. For all ordered procedures, the ordering π is pre-specified, so we may assume without loss of
generality that π(j) = j. First we note that the filtration
Fk = σ(H0 , {pj }j≤k,j∈H0 )

(48)

satisfies the required condition (40). Next, we consider accumulation tests and Adaptive SeqStep separately. Since
Selective SeqStep is a special case of Adaptive SeqStep, the corresponding bound will follow.
1. Accumulation test: For any k ∈ H0 , since αk = 1, the first part of the requirement (41) is trivially
satisfied. To show the second part, we use the independence assumption in Theorem 2 and the assumed
superuniformity of null p-values to derive
Z 1
E [hk (pk ) | Fk−1 ] = E [h(pk )] ≥ EU ∼U [0,1] [h(U )] =
h(u)du = 1 = αk .
0

The inequality follows because pk is superuniform and h is nondecreasing.
Hence, the assumptions of Lemma 3, case 1 are satisfied. Hence, the bound (42) holds with θx satisfying
equation (43). In order to prove the bound (29), we simply note that for any α ∈ (0, 1), we may choose x
such that exp(−aθx x) = α, from which it follows that
x=

log α
log α
− log α
=
=
= chacc (α),
R1
R1
aθx
a log 0 exp(−θx xh(u))du
a log 0 αh(u)/a du

as desired.
If the accumulation function is bounded by B, then the assumptions of Lemma 3, case 2 are also satisfied,
so the bound (42) holds with θx satisfying equation (44). In order to prove the bound (30), we note that for
any α ∈ (0, 1), we may choose x such that exp(−aθx x) = α, from which it follows that
x=

log α
log α
− log α

=

 = cB
=
acc (α),
1−exp(−θx xB)
1−αB/a
aθx
a log 1 −
a
log
1
−
B
B

as desired. The proof of bound (31) is similar to that of (30), so we omit it here for brevity.
2. Adaptive SeqStep: We claim that the assumptions of Lemma 3 are satisfied with Fk defined as in equation
(48). Indeed, fix k ∈ H0 . Then, the assumed superuniformity of null p-values implies that
Pr{pk ≤ αk | Fk−1 } = Pr{pk ≤ p∗ } ≤ p∗ = αk
and




p∗
E [hk (pk ) | Fk−1 ] = E
I(p > λ) ≥ p∗ = αk .
1−λ

Hence, by case 3 of Lemma 3, it follows that (42) holds for θx satisfying (45). For fixed α ∈ (0, 1), define
x such that exp(−aθx x) = α. Then,
x=

− log α
− log α
− log α

=

 = cB
=
AS (α),
1−exp(−θ
xB)
1−αB/a
x
aθx
a log 1 +
a log 1 + B
B

which proves the bound (32).

Proof of Theorem 3. This proof is similar to that of Theorem 2, exception the filtrations must be somewhat more
complicated to accommodate the interactivity of rAdaPT and rSTAR. For both of these procedures, define the
filtration
Fk = σ(H0 , {xj , g(pj )}j∈[n] , {pπ(j) }j≤k ).

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

27

03.30.18

Since π is predictable with respect to the filtration Gkr (27) by the definition of rSTAR and Fk ⊃ Grk , it follows
that π is also predictable with respect to Fk . Hence, requirement (40) holds for Fk as defined above. Now, let
π(k) ∈ H0 .
For rAdaPT, the first part of condition (41) holds because


 
Pr pπ(k) ≤ αk Fk−1 = E Pr pπ(k) ≤ p∗ g(pπ(k) ), π(k) π(k) ≤ PrU ∼U [0,1] {U ≤ p∗ | g(U )} = p∗ = αk .
The first equality follows from the independence assumption on the p-values, the first inequality follows from the
predictability of π(k) and from the assumption that the null p-values have increasing densities (see the proof of
[11, Proposition 1]). Similarly,


 


p∗
E hk (pπ(k) ) Fk−1 = E E
I(pπ(k) > p∗ ) g(pπ(k) ), π(k) π(k)
1 − p∗
p∗
≥
PrU ∼U [0,1] {U > p∗ | g(U )} = p∗ = αk .
1 − p∗
For rSTAR, the first part of condition (41) is trivially satisfied. To derive the second part, we write



 

E hk (pπ(k) ) Fk−1 = E E h(pπ(k) ) g(pπ(k) ), π(k) π(k) ≥ EU ∼U [0,1] [h(U )|g(U )] = 1 = αk .
The justification for this derivation is similar to that for rAdaPT, noting in addition that EU ∼U [0,1] [h(U )|g(U )] = 1
by construction.
Having established that the assumptions of Lemma 3 are satisfied for rAdaPT and rSTAR, the rest of the proof
is as in the proof of Theorem 2.
Proof of Theorem 4. Let Gk be the filtration defined in the statement of Theorem 4. Define
Fk ≡ σ(Gk , H0 ).

(49)

Then, assumption (40) holds for LORD+ and SAFFRON+ because pk are adapted to Fk and αk are predictable
with respect to Fk by assumption. The first part of (41) holds for both online procedures considered by assumption
(33). For LORD+, the second part holds because hk (pk ) = αk . For SAFFRON+, the second part holds because
for k ∈ H0 ,


αk
E [hk (pk ) | Fk−1 ] = E
I(pk > λk ) Fk−1 ≤ αk ,
1 − λk
where the last step follows from the predictability of αk and λk and the assumption (33).
Hence, LORD+ and SAFFRON+ satisfy the assumptions of Lemma 3. The remainder of the proof corresponds
exactly to analogous parts of the earlier proofs described for BH+ and Adaptive SeqStep, respectively.

8

Conclusion

We have shown in this paper that under independence, for a variety of procedures in the literature, the estimated
d (or a minor variant thereof) actually bounds the unknown FDP not just on average for the rejected set, but also
FDP
up to a small constant factor with high probability over the entire path of rejected sets proposed by each procedure.
This nontrivial and somewhat surprising result gives new guarantees for old procedures and sheds light on their
performance in terms of FDX. In particular, we can interpret c(α) as quantitative reflections of the variability in
FDP because our bounds are fairly tight. For example, our results support the empirical observations that BH has
a tight FDP distribution under independence, while echoing the fact that knockoff filter (i.e. Selective SeqStep)
can suffer from high FDP variance. In addition, our bounds have produced new insights into how the behavior
of accumulation tests’ FDP depends on the accumulation function. The FDP and FDR multipliers are only one
d By investigating this
half of the story, since decreasing these multipliers comes at a cost of increasing FDP.
trade-off, we have added nuance to Li and Barber’s [9] conclusion that the SeqStep accumulation function has the
highest asymptotic power by pointing out that it also has the highest-variance FDP, and hence that other choices of
accumulation function might better navigate this trade-off.

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

28

03.30.18

In addition to helping us understand existing FDR procedures, our results also open up a new perspective on
these procedures as tools for “simultaneous selective inference”. Instead of picking a single rejected set out of
2n , we can use the same machinery to computationally-efficiently carve out a path of n + 1 rejected sets based
d for each of them, along with a uniform
on structural constraints or prior knowledge, provide an estimated FDP
confidence band for the unknown FDP, and allow the user to choose one or more rejection sets in hindsight,
providing simultaneous guarantees over all such rejection sets.
Exploring such bounds and trade-offs is an important direction, since we believe that control of the FDP is as
important or more so than control of the FDR. Procedures with FDX control provide more interpretable guarantees
in practice, and those with uniform FDX control may pave the way to a new exploratory paradigm of multiple
testing à la Goeman and Solari.
Finally, the proof technique we developed in this paper is versatile enough to cover a large portion of the
currently available FDR procedures. Like Genovese and Wasserman [28], we employ a stochastic process approach
to analyze the FDP. However, while GW’s bounds are asymptotic, we have used martingale arguments instead to
obtain tight, non-asymptotic bounds. Perhaps these proof techniques may be extended further to apply to other
multiple testing scenarios as well.

9

Acknowledgements

E.K. would like to thank Chiara Sabatti for her generous and valuable feedback on this work and on the manuscript
itself. E.K. also thanks David Siegmund, Emmanuel Candes, Anya Katsevich, and Michael Sklar for helpful
discussions. E.K.’s work was supported by the Fannie and John Hertz Foundation. A.R. acknowledges several
fruitful conversations and email exchanges with Ohad Feldheim, Jim Pitman and Jon Wellner. Both authors are
also grateful to the organizers of the MCP 2017 conference, where this collaboration began.

References
[1] Y. Benjamini and Y. Hochberg. Controlling the false discovery rate: a practical and powerful approach to
multiple testing. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 57(1):289–300,
1995.
[2] Y. Benjamini and D. Yekutieli. The control of the false discovery rate in multiple testing under dependency.
The Annals of Statistics, 29(4):1165–1188, 2001.
[3] E. Arias-Castro and S. Chen. Distribution-free multiple testing. Electronic Journal of Statistics, 11(1):1983–
2001, 2017.
[4] M. G. G’Sell, S. Wager, A. Chouldechova, and R. Tibshirani. Sequential selection procedures and false discovery rate control. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 78(2):423–
444, 2016.
[5] R. F. Barber, E. J. Candès, et al. Controlling the false discovery rate via knockoffs. The Annals of Statistics,
43(5):2055–2085, 2015.
[6] R. F. Barber and A. Ramdas. The p-filter: multilayer false discovery rate control for grouped hypotheses.
Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2016.
[7] A. Ramdas, R. F. Barber, M. J. Wainwright, and M. I. Jordan. A unified treatment of multiple testing with
prior knowledge. arXiv preprint arXiv:1703.06222, 2017.
[8] E. Katsevich and C. Sabatti. Multilayer knockoff filter: Controlled variable selection at multiple resolutions.
arXiv preprint arXiv:1706.09375, 2017.
[9] A. Li and R. F. Barber. Accumulation tests for FDR control in ordered hypothesis testing. Journal of the
American Statistical Association, pages 1–13, 2017.

29

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

03.30.18

[10] L. Lei and W. Fithian. AdaPT: An interactive procedure for multiple testing with side information. arXiv
preprint arXiv:1609.06035, 2016.
[11] L. Lei, A. Ramdas, and W. Fithian. STAR: A general interactive framework for FDR control under structural
constraints. arXiv preprint arXiv:1710.02776, 2017.
[12] D. P. Foster and R. A. Stine. α-investing: a procedure for sequential control of expected false discoveries.
Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(2):429–444, 2008.
[13] E. Aharoni and S. Rosset. Generalized α-investing: definitions, optimality results and application to public
databases. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(4):771–794, 2014.
[14] A. Javanmard and A. Montanari. Online rules for control of false discovery rate and false discovery exceedance. The Annals of Statistics, 2017.
[15] A. Ramdas, F. Yang, M. J. Wainwright, and M. I. Jordan. Online control of the false discovery rate with
decaying memory. In Advances In Neural Information Processing Systems, 2017.
[16] A. Ramdas, T. Zrnic, M. J. Wainwright, and M. I. Jordan. SAFFRON: an adaptive algorithm for online
control of the false discovery rate. arXiv preprint arXiv:1802.09098, 2018.
[17] E. L. Korn, J. F. Troendle, L. M. McShane, and R. Simon. Controlling the number of false discoveries:
application to high-dimensional genomic data. Journal of Statistical Planning and Inference, 124(2):379–
398, 2004.
[18] E. L. Lehmann and J. Romano. Generalizations of the familywise error rate. The Annals of Statistics, pages
1138–1154, 2005.
[19] J. Romano and A. Shaikh. On stepdown control of the false discovery proportion. In Optimality, pages
33–50. Institute of Mathematical Statistics, 2006.
[20] J. P. Romano and M. Wolf. Control of generalized error rates in multiple testing. The Annals of Statistics,
pages 1378–1408, 2007.
[21] W. Guo, L. He, and S. K. Sarkar. Further results on controlling the false discovery proportion. The Annals of
Statistics, 42(3):1070–1101, 2014.
[22] S. Delattre and E. Roquain. New procedures controlling the false discovery proportion via Romano-Wolf’s
heuristic. The Annals of Statistics, 43(3):1141–1177, 2015.
[23] J. Goeman and A. Solari. Multiple testing for exploratory research. Statistical Science, pages 584–597, 2011.
[24] J. F. Troendle. Stepwise normal theory multiple test procedures controlling the false discovery rate. Journal
of Statistical Planning and Inference, 84(1-2):139–158, 2000.
[25] H. Finner and M. Roters. On the false discovery rate and expected type I errors. Biometrical Journal,
43(8):985–1005, 2001.
[26] M. J. van der Laan, S. Dudoit, and K. S. Pollard. Multiple testing. Part III. Procedures for control of the
generalized family-wise error rate and proportion of false positives. 2004.
[27] N. Meinshausen. False discovery control for multiple tests of association under general dependence. Scandinavian Journal of Statistics, 33(2):227–237, 2006.
[28] C. Genovese and L. Wasserman. A stochastic process approach to false discovery control. The Annals of
Statistics, pages 1035–1061, 2004.
[29] C. R. Genovese and L. Wasserman. Exceedance control of the false discovery proportion. Journal of the
American Statistical Association, 101(476):1408–1417, 2006.

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

30

03.30.18

[30] G. Blanchard, P. Neuvial, and E. Roquain. Post hoc inference via joint family-wise error rate control. arXiv
preprint arXiv:1703.02307, 2017.
[31] L. Lei and W. Fithian. Power of ordered hypothesis testing. In International Conference on Machine Learning, pages 2924–2932, 2016.
[32] W. Fithian, D. Sun, and J. Taylor. Optimal inference after model selection. arXiv preprint arXiv:1410.2597,
2014.
[33] J. Storey, J. Taylor, and D. Siegmund. Strong control, conservative point estimation and simultaneous conservative consistency of false discovery rates: a unified approach. Journal of the Royal Statistical Society:
Series B (Statistical Methodology), 66(1):187–205, 2004.
[34] H. Robbins. A one-sided confidence interval for an unknown distribution function. In Annals of Mathematical
Statistics, volume 25, pages 409–409, 1954.
[35] J. Goeman, R. Meijer, T. Krebs, and A. Solari. Simultaneous control of all false discovery proportions in
large-scale multiple hypothesis testing. arXiv preprint arXiv:1611.06739, 2016.
[36] A. B. Owen. Variance of the number of false discoveries. Journal of the Royal Statistical Society: Series B
(Statistical Methodology), 67(3):411–426, 2005.
[37] B. Efron. Large-scale inference, volume 1 of Institute of Mathematical Statistics (IMS) Monographs. Cambridge University Press, Cambridge, 2010. Empirical Bayes methods for estimation, testing, and prediction.
[38] G. D. Anderson, R. W. Barnard, K. C. Richards, M. K. Vamanamurthy, and M. Vuorinen. Inequalities for
zero-balanced hypergeometric functions. Transactions of the American Mathematical Society, pages 1713–
1723, 1995.

A

Technical lemmas: From empirical to Poisson processes

Lemma 4. Let {Nt }t≥0 be a Poisson process with rate n. For x ≥ 1.5,
#
"
#
"
Nt
Nt
≥ x N1 = n ≤ P sup
≥x .
P sup
t∈[0,1] 1 + nt
t∈[0,1] 1 + nt

(50)

Proof. Let us define

τ = inf t :


Nt
≥x .
1 + nt

We claim that it suffices to show that for x ≥ 1.5,
P[N1 = n|τ ] ≤ P[N1 = n] for all τ ≥ 0.
Indeed, it would then follow that
"

#
Nt
P sup
≥ x N1 = n = P [τ ≤ 1|N1 = n]
t∈[0,1] 1 + nt
P[τ ≤ 1]P[N1 = n|τ ≤ 1]
P[N1 = n]
≤ P[τ ≤ 1]
"
#
Nt
= P sup
≥x .
t∈[0,1] 1 + nt
=

(51)

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

31

Note that for a given x, x(1 + nt) > n for t >
only consider

1
x

− n1 . Hence, statement (51) is trivial for τ >
τ≤

03.30.18

1
x

− n1 , so we need

1
1
− .
x n

Define
f (λ, y) = e−λ

λy
.
Γ(y + 1)

(52)
(53)

This function f : [0, ∞) → R is equal to the probability mass function of the Poisson with parameter λ when
y ∈ {0, 1, 2, . . . }. We have
P[N1 = n|τ ] = P[N1 = n|Nτ = dx(1 + nτ )e]
= P[N1−τ = n − dx(1 + nτ )e]
= f (n(1 − τ ), n − dx(1 + nτ )e)

(54)

≤ f (n(1 − τ ), n − x(1 + nτ ))
≡ g(τ, x).
The inequality follows by Lemma 6 because n − x(1 + nτ ) ≤ n(1 − τ ) − x ≤ n(1 − τ ) − 1.5. Define


(n(1 − τ ))n−x(1+nτ )
h(τ, x) = log g(τ, x) = log exp(−n(1 − τ ))
Γ(1 + n − x(1 + nτ ))

(55)

= −n(1 − τ ) + (n − x(1 + nτ )) log(n(1 − τ )) − log Γ(1 + n − x(1 + nτ )).
Note that
∂
n − x(1 + nτ )
h(τ, x) = n − xn log(n(1 − τ )) −
+ xnψ(1 + n − x(1 + nτ ))
∂τ
1−τ


1
n − x(1 + nτ )
+ xn log(1.5 + n − x(1 + nτ )) −
≤ n − xn log(n(1 − τ )) −
1−τ
1.5 + n − x(1 + nτ )
≡ r(τ, x).
(56)
The inequality follows by Lemma 5.
To prove the inequality (51), it suffices to show that
(a) g(0, x) ≤ P[N1 = n] for all x ≥ 1.5;
(b) r(τ, 1.5) ≤ 0 for each τ ≤
(c)

∂
∂x r(τ, 1.5)

1
1.5

≤ 0 for each τ ≤

− n1 ;
1
1.5

− n1 ;

(d) r(τ, x) is concave in x for each τ .
1
Indeed, note that (c) and (d) imply that for each τ ≤ 1.5
− n1 , r(τ, x) is a decreasing function of x for x ≥ 1.5.
Hence, for each x ≥ 1.5 and each τ , we have r(τ, x) ≤ r(τ, 1.5) ≤ 0, where the last inequality follows from (b).
Hence, by inequality (56), ∂h
∂τ (τ, x) ≤ r(τ, x) ≤ 0 for each x ≥ 1.5. This means that h(τ, x) is decreasing in τ
for each x ≥ 1.5, so g(τ, x) is decreasing in τ for each x ≥ 1.5, from which it follows that g(τ, x) ≤ g(0, x) ≤
P[N1 = n], where the last inequality follows by (a).

Proof of (a).

We have
g(0, x) = f (n, n − x) ≤ f (n, n − 1) = f (n, n) = P[N1 = n].

where the inequality follows by Lemma 6 and the equality f (n − 1, n) = f (n, n) holds because
f (n, n − 1)
=
f (n, n)

nn−1
Γ(n)
nn
Γ(n+1)

=

Γ(n + 1)
= 1.
nΓ(n)

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

32

03.30.18

Proof of (b). We have
n − 1.5(1 + nτ )
r(τ, 1.5) = n − 1.5n log(n(1 − τ )) −
1−τ


1
+ 1.5n log(1.5 + n − 1.5(1 + nτ )) −
1.5 + n − 1.5(1 + nτ )


n − nτ − 1.5 − 0.5nτ
1
= n − 1.5n log(n(1 − τ )) −
+ 1.5n log(n(1 − 1.5τ )) −
1−τ
n(1 − 1.5τ )


1 − 1.5τ
1.5 + 0.5nτ
1.5
= 1.5n log
+
−
1−τ
1−τ
1 − 1.5τ






1 − 1.5τ
0.5τ
1
1
= n 1.5 log
+
+ 1.5
−
1−τ
1−τ
1−τ
1 − 1.5τ




1 − 1.5τ
0.5τ
≤ n 1.5 log
+
1−τ
1−τ




0.5τ
0.5τ
= n 1.5 log 1 −
+
1−τ
1−τ


0.5τ
0.5τ
≤ n −1.5
+
1−τ
1−τ
0.25τ
= −n
1−τ
≤ 0.
Proof of (c).

We have
∂r
1 + nτ
(τ, x) = −n log(n(1 − τ )) +
+ n log(1.5 + n − x(1 + nτ ))
∂x
1−τ
1.5 + n − x(1 + nτ ) + x(1 + nτ )
(1 + nτ )xn
−n
−
1.5 + n − x(1 + nτ )
(1.5 + n − x(1 + nτ ))2
1 + nτ
= −n log(n(1 − τ )) +
+ n log(1.5 + n − x(1 + nτ ))
1−τ
(1 + nτ )xn
1.5 + n
−
−n
.
1.5 + n − x(1 + nτ )
(1.5 + n − x(1 + nτ ))2

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

33

03.30.18

Plugging in x = 1.5, we have
∂r
1 + nτ
1.5(1 + nτ )n
1.5 + n
(τ, 1.5) = −n log(n(1 − τ )) +
+ n log(n(1 − 1.5τ )) −
−n
∂x
1−τ
n(1 − 1.5τ )
(n(1 − 1.5τ ))2


1 − 1.5τ
1.5
1
τ
1.5
1
1.5
= n log
−
+
+n
−
(1 + nτ ) −
2
1−τ
1−τ
1−τ
1 − 1.5τ
n (1 − 1.5τ )
(1 − 1.5τ )2
 

 

1 − 1.5τ
τ
1.5τ
1
1.5
≤ n log
+
−
+
−
1−τ
1−τ
1 − 1.5τ
1−τ
1 − 1.5τ
 


1 − 1.5τ
τ
1.5τ
≤ n log
+
−
1−τ
1−τ
1 − 1.5τ


−0.5τ
τ
1.5τ
≤n
+
−
.
1−τ
1−τ
1 − 1.5τ


1.5τ
0.5τ
−
.
=n
1−τ
1 − 1.5τ
τ (0.75τ − 1)
≤n
(1 − τ )(1 − 1.5τ )
≤ 0,
where the last inequality follows because τ ≤
Proof of (d).

1
1.5

−

1
n

≤ 4/3.

Modulo terms linear in x and the scaling factor n, r(τ, x) is equal to
x
x log (1.5 + n − x(1 + nτ )) −
.
1.5 + n − x(1 + nτ )

We claim that the first term is concave in x and the second term is convex, from which it will follow that their
difference is concave. By linear transformations, the concavity of the first term will follow from the concavity
x
of x log(1 − x), which follows because its first derivative log(1 − x) − 1−x
is decreasing in x. Again by linear
x
1
transformations, the convexity of the second term will follow from the convexity of 1−x
= −1 + 1−x
on x < 1,
which is clear.
Lemma 5. Let ψ(x) = Γ0 (x)/Γ(x) be the digamma function. Then, ψ is increasing, and for x ≥ 1,
ψ(x) ≤ log(x) −

1
1
≤ log(x + 0.5) −
≤ log x.
2x
x + 0.5

(57)

Proof. The fact that ψ is increasing is well-known. The first inequality follows directly from [38, Theorem 3.1].
To prove the second inequality, write



2
0.5
0.5 1 0.5
log(x + 0.5) − log(x) = log 1 +
≥
−
,
x
x
2 x
and the conclusion follows because

2
0.5 1 0.5
1
1
1
1
x − 0.5
−
≥
−
⇐⇒
−
≥
⇐⇒ x ≥ 1/6.
x
2 x
x + 0.5 2x
2x 8x2
2x(x + 0.5)
To prove the third inequality, write


0.5
0.5
log(x + 0.5) − log(x) = log 1 +
≤
,
x
x
and the conclusion follows because

0.5
1
≤
⇐⇒ x ≥ 0.5.
x
x + 0.5

Towards “simultaneous selective inference”:
post hoc bounds on the false discovery proportion

34

Lemma 6. Let f be as defined in equation (53). Then,
∂
f (λ, y) ≥ 0
∂y

for all y ≤ λ − 1.

Proof. To prove this, it suffices to show that for y ≤ λ − 1,
0≤

∂
∂
log f (λ, y) =
(−λ + y log λ − log Γ(y + 1)) = log λ − ψ(y + 1).
∂y
∂y

Indeed, by Lemma 5, for y ≤ λ − 1 we have ψ(y + 1) ≤ ψ(λ) ≤ log λ.

03.30.18

