# Permutation-Based True Discovery Guarantee by Sum Tests

Anna<EMAIL_ADDRESS>Department of Statistical Sciences,
University of Padova Livio<EMAIL_ADDRESS>Department of
Developmental Psychology and Socialization, University of Padova  Jelle J.
<EMAIL_ADDRESS>Department of Biomedical Data Sciences, Leiden
University Medical Center

###### Abstract

Sum-based global tests are highly popular in multiple hypothesis testing. In
this paper we propose a general closed testing procedure for sum tests, which
provides lower confidence bounds for the proportion of true discoveries (TDP),
simultaneously over all subsets of hypotheses; these simultaneous inferences
come for free, i.e., without any adjustment of the alpha-level, whenever a
global test is used. Our method allows for an exploratory approach, as
simultaneity ensures control of the TDP even when the subset of interest is
selected post hoc. It adapts to the unknown joint distribution of the data
through permutation testing. Any sum test may be employed, depending on the
desired power properties. We present an iterative shortcut for the closed
testing procedure, based on the branch and bound algorithm, which converges to
the full closed testing results, often after few iterations; even if it is
stopped early, it controls the TDP. The feasibility of the method for high
dimensional data is illustrated on brain imaging data, then we compare the
properties of different choices for the sum test through simulations.

Keywords: closed testing, multiple testing, permutation test, selective
inference, sum test, true discovery proportion.

##  1 Introduction

In high-dimensional data analysis, researchers are often interested in
detecting subsets of features that are associated with a given outcome. For
instance, in functional magnetic resonance imaging (fMRI) data the objective
may be to identify a brain region that is activated by a stimulus; in genomics
data one may want to find a biological pathway that is differentially
expressed. In this context, global tests allow to make meaningful statements
at the set level. A diverse range of global tests has been proposed in
literature: well-known examples are p-value combinations, described and
compared in Pesarin [2001], Loughin [2004], Won et al. [2009] and Pesarin and
Salmaso [2010]; other popular methods are Simes’ test [Simes, 1986], the
global test of Goeman et al. [2006], the sequence kernel association test [Wu
et al., 2011] and higher criticism [Donoho and Jin, 2015]. Their main
characteristic is the ability to aggregate signal from multiple features. A
substantial proportion, including many of the above-mentioned methods, is sum-
based, meaning that the global test statistic may be written as a sum of
contributions per feature. In this paper we restrict to such sum-based tests.

The probability distribution of a global statistic depends not only on the
marginal distribution of the data, but also on the joint distribution; for
this reason, many sum tests only have a known null distribution under
independence. Approaches that deal with the a-priori unknown joint
distribution are worst-case distributions, defined either generally or under
restrictive assumptions [Vovk and Wang, 2020], and nonparametric permutation
testing [Fisher, 1936, Ernst, 2004]. As worst-case distributions tend to be
very conservative, the latter approach is preferable; it relies on minimal
assumptions [Hemerik and Goeman, 2018a], and generally offers an improvement
in power over the parametric approach, especially when multiple hypotheses are
considered [Westfall and Young, 1993, Pesarin, 2001, Hemerik and Goeman,
2018b, Hemerik et al., 2019].

Rejecting a null hypothesis, however, gives little information on the
corresponding set. A significant p-value only indicates that there is at least
one true discovery, i.e., one feature associated with the outcome, but does
not give any information on the proportion of true discoveries (TDP), nor
their localization. This becomes problematic especially for large sets [Woo et
al., 2014]. Moreover, since interest is usually not just in the set of all
features, but in several subsets, a multiple testing procedure is necessary
[Nichols, 2012, Meijer and Goeman, 2016]. Finally, when researchers do not
know a priori which subsets they are interested in, they may want to test many
and then make the selection post hoc. The case for the use of TDPs in large-
scale testing problems was argued by Rosenblatt et al. [2018] in neuroimaging
and by Ebrahimpoor et al. [2020] in genomics.

This paper presents a general approach for inference on the TDP. The method
allows any sum-based test, requiring only that critical values are determined
by permutations. It provides TDPs not only for the full testing problem, but
also simultaneously for all subsets, allowing subsets of interest to be chosen
post hoc.

We will solve this problem using the closed testing framework [Marcus et al.,
1976], which allows to construct confidence sets for the TDP simultaneously
over all possible subsets [Genovese and Wasserman, 2006, Goeman and Solari,
2011, Goeman et al., 2019]. These additional simultaneous inferences on all
subsets come for free, i.e., without any adjustment of the $\alpha$-level,
whenever a global test is applied. Simultaneity ensures that the procedure is
not compromised by post-hoc selection, therefore researchers can postpone the
choice of the subset until after seeing the data, while still obtaining valid
confidence sets; used in this way, closed testing allows a form of post-hoc
inference. Furthermore, closed testing has been proven to be the optimal way
to construct multiple testing procedures, as all multiple testing methods are
either equivalent to or can be improved by it [Goeman et al., 2021]. The main
challenge of this framework is the computational complexity, which is
extremely high when the multiple testing problem contists of many hypotheses,
and when using many permutations. Closed testing for the TDP so far mostly
focused on Simes-based test procedures, while sum-test-based closed testing
was done under independence or with worst-case distributions [Vovk and Wang,
2020, Wilson, 2019, Tian et al., 2021], simpler because critical values depend
only on the size of the subset.

We propose a general closed testing procedure for sum-based permutation tests,
which provides simultaneous confidence sets for the TDP of all subsets of the
testing problem. We develop two shortcuts to make this procedure feasible for
large-scale problems. First, we develop a quick shortcut that approximates
closed testing and has a complexity that is linearithmic in the number of
individual hypotheses, and linear in the number of permutations. Next, we
embed this shortcut within a branch and bound algorithm, obtaining an
iterative procedure that converges to full closed testing, often after few
iterations; even if it is stopped early, it still controls the TDP. The
resulting procedure is exact and extremely flexible, as it applies to any sum
test and adapts to the correlation structure of the data. It can be scaled up
to high-dimensional problems, such as fMRI data, whose typical dimension is of
order $10^{5}$. Finally, we show that particular choices of the sum test
statistic, namely statistics based on truncation, result in faster procedures.

The structure of the paper is as follows. First, we introduce sum tests in
Section 2, then we review the properties of permutation testing and closed
testing in Sections 3 and 4. We derive the single-step shortcut in Section 5,
and characterize when it is equivalent to closed testing in Section 6. In
Section 7 we define the iterative shortcut, and finally in Section 8 we
introduce truncation-based statistics. In the remaining Section we explore an
application to fMRI data, and compare the properties of different sum tests
through simulations. Proofs and some additional results are postponed to the
Appendix.

##  2 Sum Tests

We start with a general definition of a sum test statistic. Let $X$ be data,
taking values in a sample space $\mathcal{X}$. Assume we are interested in
studying $m$ univariate hypotheses $H_{1},\ldots,H_{m}$, having indices in
$M=\\{1,\ldots,m\\}$, with significance level $\alpha\in[0,1)$. Let
$N\subseteq M$ be the unknown subset of true hypotheses. A generic subset
$S\subseteq M$, with size $|S|=s$, defines an intersection hypothesis
$H_{S}=\bigcap_{i\in S}H_{i}$, which is true if and only if $S\subseteq N$. In
the particular case of $S=\emptyset$, we take $H_{\emptyset}$ as usual to be a
hypothesis that is always true.

For each univariate hypothesis $H_{i}$, let
$T_{i}:\mathcal{X}\rightarrow\mathbb{R}$ denote a test statistic. The general
form of a sum test statistic for $H_{S}$ is

$T_{S}=g\left(\sum_{i\in S}f_{i}(T_{i})\right),$

where $f_{i}:\mathbb{R}\rightarrow\mathbb{R}$ are generic functions, and
$g:\mathbb{R}\rightarrow\mathbb{R}$ is strictly monotone. Usually the
functions $f_{i}$ are also taken as monotone, so that high values of $T_{S}$
give evidence against $H_{S}$. Moreover, as $f_{i}$ may depend on $i$, the
contributions $f_{i}(T_{i})$ may have different distributions, as in the case
of weighted sums. Examples include p-value combinations such as Fisher [1925],
Pearson [1933], Liptak/Stouffer [Liptak, 1958], Lancaster [1961], Edgington
[1972], and Cauchy [Liu and Xie, 2020]. We mention especially the generalized
mean family [Vovk and Wang, 2020] with $f_{i}(x)=x^{r}$ and
$g(y)=(y/s)^{1/r}$, where $r\in\mathbb{R}$, for which Wilson [2019] studied
the harmonic mean ($r=-1$).

Since we can always re-write $\tilde{T}_{i}=f_{i}(T_{i})$ and
$\tilde{T}_{S}=g^{-1}(T_{S}),$ without loss of generality we can assume that
$f_{i}$ and $g$ are the identity, so that

$T_{S}=\sum_{i\in S}T_{i}.$

In particular, for the empty set we obtain $T_{\emptyset}=0$. Furthermore, we
assume that the signs are chosen in such a way that high values of $T_{i}$,
and therefore $T_{S}$, correspond to evidence against $H_{i}$ and $H_{S}$,
respectively.

##  3 Permutation Testing

To find the critical value for the test statistic $T_{S}$ we will use
permutations. Let $\mathcal{P}$ be a collection of transformations
$\pi:\mathcal{X}\rightarrow\mathcal{X}$ of the sample space; these may be
permutations, but also other transformations such as rotations [Langsrud,
2005, Solari et al., 2014] and sign flipping [Hemerik et al., 2020]. We assume
that $\mathcal{P}$ is an algebraic group with respect to the operation of
composition of functions. The group structure is important as, without it, the
resulting test may be highly conservative or anti-conservative [Hoeffding,
1952, Southworth et al., 2009].

Denote with $T_{i}=T_{i}(X)$ and $T_{i}^{\pi}=T_{i}(\pi X)$, with
$\pi\in\mathcal{P}$, the statistics computed on the observed and transformed
data, respectively. The main assumption of permutation testing is that the
joint distribution of the statistics $T_{i}^{\pi}$, with $i\in N$ and
$\pi\in\mathcal{P}$, is invariant under all transformations in $\mathcal{P}$
of $X$. This assumption is common to most permutation-based multiple-testing
methods, such as maxT-method [Westfall and Young, 1993, Meinshausen, 2006,
Goeman and Solari, 2010, Hemerik et al., 2019]. For some choices of the group
$\mathcal{P}$, the assumption holds only asymptotically [Winkler et al., 2014,
Solari et al., 2014, Hemerik et al., 2020]. Detailed illustration and examples
can be found in Pesarin [2001], Huang et al. [2006] and Hemerik and Goeman
[2018a]. Here, we consider a slightly stronger assumption that is easier to
check.

######  Assumption 1.

Given the partition $X=(X_{1},\ldots,X_{m})$, the statistic
$T_{S}=T_{S}(X_{S})$ is a function of $X_{S}=(X_{i}\,:\,i\in S)$ only.
Moreover, $X_{N}\overset{\text{d}}{=}\pi X_{N}$ for each $\pi\in\mathcal{P}$,
where $\overset{\text{d}}{=}$ denotes equality in distribution.

Note that Assumption 1 holds in the particular case when $H_{S}$ true implies
that $X_{S}\overset{\text{d}}{=}\pi X_{S}$ for each $\pi$.

If the cardinality of $\mathcal{P}$ is large, a valid $\alpha$-level test may
use $B$ randomly chosen elements [Hemerik and Goeman, 2018b]. The value of $B$
does not need to grow with $m$ or $s$; to have non-zero power we must only
have $B\geq 1/\alpha$, though larger values of $B$ give more power. For
$\alpha=0.05$, $B\geq 200$ is generally sufficient (see Section 9.1). Consider
a vector $\boldsymbol{\pi}=(\pi_{1},\ldots,\pi_{B})$, where
$\pi_{1}=\text{id}$ is the identity in $\mathcal{P}$, and
$\pi_{2},\ldots,\pi_{B}$ are random elements drawn with replacement from a
uniform distribution on $\mathcal{P}$. Then set
$\omega_{0}=\lceil(1-\alpha)B\rceil$, where $\lceil\cdot\rceil$ represents the
ceiling function. A critical value for the test statistic $T_{S}$ is given by
the quantile $T_{S}^{(\omega_{0})}$, where $T_{S}^{(1)}\leq\ldots\leq
T_{S}^{(B)}$ are the sorted statistics $T_{S}^{\pi}$, with
$\pi\in\boldsymbol{\pi}$. Then a permutation test may be defined as following.

######  Lemma 1.

Under Assumption 1, the test that rejects $H_{S}$ when
$T_{S}>T_{S}^{(\omega_{0})}$ is an $\alpha$-level test.

In permutation testing, both the test statistic and the critical value are
random variables. For our method it will be convenient to use an equivalent
characterization of the test with a non-random critical value. Therefore, we
define the centered statistic $C_{S}^{\pi}=T_{S}-T_{S}^{\pi}$ for each $\pi$,
so that the observed value $C_{S}=C_{S}^{\text{id}}$ is always zero, and all
variability in the critical value is incorporated into the test statistic. We
give a permutation test based on these new statistics, by using
$\omega=\lceil\alpha B\rceil$ to obtain the quantile.

######  Theorem 1.

Under Assumption 1, the test that rejects $H_{S}$ when $C_{S}^{(\omega)}>0$ is
an $\alpha$-level test.

For illustration, we introduce a recurring toy example with $m=5$ univariate
hypotheses and $B=6$ transformations (Table 1). Let $M=\\{1,2,3,4,5\\}$, and
suppose we are interested in testing subset $S=\\{1,2\\}$ at significance
level $\alpha=0.4$. The vectors of the corresponding statistics $T_{S}^{\pi}$
and $C_{S}^{\pi}$ are obtained by summing columns 1 and 2 by row. Since
$\omega=3$ and $C_{S}^{(\omega)}=2$, the permutation test rejects $H_{S}$.

Table 1: Toy example: original and centered test statistics. |  |  original $T_{i}^{\pi}$ |  |  centered $C_{i}^{\pi}$
---|---|---|---|---
|  | $H_{1}$ | $H_{2}$ | $H_{3}$ | $H_{4}$ | $H_{5}$ |  | $H_{1}$ | $H_{2}$ | $H_{3}$ | $H_{4}$ | $H_{5}$
id |  | 6 | 5 | 4 | 1 | 1 |  | 0 | 0 | 0 | 0 | 0
$\pi_{2}$ |  | 1 | 2 | 1 | 0 | 4 |  | 5 | 3 | 3 | 1 | -3
$\pi_{3}$ |  | 8 | 3 | 0 | 2 | 1 |  | -2 | 2 | 4 | -1 | 0
$\pi_{4}$ |  | 8 | 1 | 0 | 1 | 0 |  | -2 | 4 | 4 | 0 | 1
$\pi_{5}$ |  | 0 | 6 | 1 | 1 | 2 |  | 6 | -1 | 3 | 0 | -1
$\pi_{6}$ |  | 7 | 0 | 1 | 2 | 1 |  | -1 | 5 | 3 | -1 | 0

##  4 True Discovery Guarantee

Based on the notation introduced above, consider the number of true
discoveries $\delta(S)=|S\setminus N|$ made when rejecting $H_{S}$. We are
interested in deriving simultaneous ($1-\alpha$)-confidence sets for this
number, so that the simultaneity makes their coverage robust against post-hoc
selection. This way, the rejected hypothesis can be selected after reviewing
all confidence sets, while still keeping correct ($1-\alpha$)-coverage of the
corresponding confidence set [Goeman and Solari, 2011].

Let $d:2^{M}\rightarrow\mathbb{R}$ be a random function, where $2^{M}$ is the
power set of $M$. With the same notation of Goeman et al. [2021], we say that
$d$ has true discovery guarantee if $d(S)$ are simultaneous lower
($1-\alpha$)-confidence bounds for $\delta(S)$, i.e.,

$P\left(\delta(S)\geq d(S)\;\text{for each }S\subseteq M\right)\geq 1-\alpha.$

An equivalent condition is that $\\{d(S),\ldots,s\\}$ is a
($1-\alpha$)-confidence set for $\delta(S)$, simultaneously for all
$S\subseteq M$. Notice that the resulting confidence sets are one-sided, since
hypothesis testing is focused on rejecting, not accepting. From $d(S)$
simultaneous ($1-\alpha$)-confidence sets can be immediately derived for other
quantities of interest such as the TDP and the number or proportion of false
discoveries [Goeman and Solari, 2011].

A general way to construct procedures with true discovery guarantee is
provided by closed testing, based on the principle of testing different
subsets by means of a valid $\alpha$-level local test, which in this case is
the permutation test. Throughout this paper, we will loosely say that a set
$S$ is rejected when the corresponding hypothesis $H_{S}$ is. Hence denote the
collection of sets rejected by the permutation test by

$\mathcal{R}=\left\\{S\subseteq M\,:\,C_{S}^{(\omega)}>0\right\\}.$

Genovese and Wasserman [2006] and Goeman and Solari [2011] defined a procedure
$d$ with true discovery guarantee as

$d(S)=s-q(S),$

where

$\displaystyle q(S)=\max\left\\{|V\cap S|\,:\,V\subseteq
M,\,V\notin\mathcal{R}\right\\}.$ (1)

The main challenge of this method is its exponential complexity in the number
of hypotheses. Indeed, the number of tests that must be evaluated to determine
$d(S)$ may be up to order $2^{m}$. In the toy example, where $m=5$, this
number is $32$; it is immediate that it quickly grows to an infeasible size as
$m$ increases.

##  5 Shortcut

Fix the set of interest $S$, so that any dependence on it may be omitted in
the notation. We propose a shortcut that quickly evaluates whether $q<z$, for
any value $z$. This will allow to approximate $q$, and eventually define a
procedure with true discovery guarantee.

First, we will re-write $q$ as the unique change-poiny of an increasing
function:

$\displaystyle\phi:\\{0,\ldots,s+1\\}\longrightarrow\\{0,1\\},\qquad\phi(z)=1\quad\text{if
and only if}\quad q<z$ (2) $\displaystyle
q=\max\left\\{z\in\\{0,\ldots,s+1\\}\,:\,\phi(z)=0\right\\}.$ (3)

Then we will approximate $q$ from above with the change point $q^{(0)}$ of a
second increasing function:

$\displaystyle\underline{\phi}:\\{0,\ldots,s+1\\}\longrightarrow\\{0,1\\},\qquad\underline{\phi}(z)\leq\phi(z)$
(4) $\displaystyle
q^{(0)}=\max\left\\{z\in\\{0,\ldots,s+1\\}\,:\,\underline{\phi}(z)=0\right\\}.$
(5)

We start by giving an equivalent characterization of the quantity of interest
$q$. For any $z\in\\{0,\ldots,s+1\\}$, we define the collection

$\mathcal{V}_{z}=\\{V\subseteq M\,:\,|V\cap S|\geq z\\}$

of sets that have at least size $z$ overlap with $S$, and investigate whether
all its elements are rejected. We define $\phi$ as in (2) so that it
represents such rejection, taking

$\displaystyle\phi(z)=\mathbf{1}\\{\mathcal{V}_{z}\subseteq\mathcal{R}\\}\quad(z\in\\{0,\ldots,m\\}),$
(6)

where $\mathbf{1}\\{\cdot\\}$ denotes the indicator function.

######  Lemma 2.

$\phi(0)=0$ and $\phi(s+1)=1$. Moreover, $\phi(z)=0$ if and only if
$z\in\\{0,\ldots,q\\}$.

Now we fix a value $z\in\\{1,\ldots,s\\}$ and derive the shortcut to make
statements on $\phi(z)$ without testing all the sets contained in
$\mathcal{V}_{z}$. We do this by partitioning $\mathcal{V}_{z}$ by the size of
its elements, obtaining

$\displaystyle\mathcal{V}_{z}=\bigcap_{v=z}^{m}\mathcal{V}_{z}(v),\qquad\mathcal{V}_{z}(v)=\\{V\in\mathcal{V}_{z}\,:\,|V|=v\\}.$
(7)

Each $\mathcal{V}_{z}(v)$ is the sub-collection of all sets of size $v$ that
have at least size $z$ overlap with $S$. We can analyze these sub-collections
separately and combine the results, noting that $\phi(z)=1$ if and only if
$\mathcal{V}_{z}(v)\subseteq\mathcal{R}$ for all $v\in\\{z,\ldots,m\\}$.

By definition, $\mathcal{V}_{z}(v)\subseteq\mathcal{R}$ when all sets in the
sub-collection have positive quantiles, i.e., $C_{V}^{(\omega)}>0$ for each
$V\in\mathcal{V}_{z}(v)$. The main idea of the shortcut is to obtain
information on each sub-collection $\mathcal{V}_{z}(v)$ by bounding the
corresponding quantiles from below. In particular, we will construct a bound

$\displaystyle\ell_{z}\,:\,\\{z,\ldots,m\\}\longrightarrow\mathbb{R},\qquad\ell_{z}(v)\leq
C_{V}^{(\omega)}\quad\text{for each }V\in\mathcal{V}_{z}(v).$ (8)

This way, if $\ell_{z}(v)>0$, we know that all sets in $\mathcal{V}_{z}(v)$
have positive quantiles. If $\ell_{z}$ is positive in its entire domain, then
$\mathcal{V}_{z}(v)\subseteq\mathcal{R}$ for each $v$, and so $\phi(z)=1$.
Figure 1 displays the bound, which we will define in the following paragraphs,
in the toy example for $z=1$ and $z=2$. Note that indeed all quantiles lie on
it or above; the bound can be loose, as seen with $\ell_{1}(3)$. Since
$\ell_{2}$ lies entirely in the positive half-space, we know that $\phi(2)=1$.
In contrast, we cannot make a statement on $\phi(1)$ based on $\ell_{1}$.

Figure 1: Toy example with $S=\\{1,2\\}$: shortcut to evaluate $\phi(z)$ in
$z=1$ and $z=2$. Points denote the quantiles for the sets in
$\mathcal{V}_{z}$. The dashed line represents the bound $\ell_{z}$.

Fix a size $v\in\\{z,\ldots,m\\}$. To define an $\ell_{z}(v)$ that does not
exceed the minimum quantile over all sets in $\mathcal{V}_{z}(v)$, as required
in (8), we approximate the minimum quantile from below with the quantile of
the minimum. We do this by taking the smallest centered statistics for each
transformation $\pi$, with some constraints from the structure of
$\mathcal{V}_{z}(v)$.

In the toy example, choose $z=1$, and let $V$ be any set in the sub-collection
$\mathcal{V}_{1}(v)$ of interest. Note that $V$ must contain $v$ indices, at
least $z=1$ of which is in $S$. Consider the centered statistics
$C_{i}^{\pi_{2}}$ for transformation $\pi_{2}$ (second row in Table 1, right).
First, we select the lowest value in $S$, then we sort the remaining values in
ascending order, as in the second row of Table 2. If $b_{v}^{\pi_{2}}$ is the
sum of the first $v$ elements of the row, we know that $b_{v}^{\pi_{2}}\leq
C_{V}^{\pi_{2}}$. After constructing the other rows of Table 2 according to
the same principle, we define $\ell_{1}(v)=b_{v}^{(\omega)}$; since
$b_{v}^{\pi}\leq C_{V}^{\pi}$ for each $\pi$, we obtain $\ell_{1}(v)\leq
C_{V}^{(\omega)}$.

Table 2: Toy example with $S=\\{1,2\\}$: matrix of the sorted centered statistics to compute the bound $\ell_{1}$. The value $\ell_{1}(v)$ is obtained by summing the first $v$ columns by row, and then taking the quantile. |  |  selected in $S$ |  | remaining
---|---|---|---|---
|  | $i_{1}(\pi)$ |  | $j_{1}(\pi)$ | $j_{2}(\pi)$ | $j_{3}(\pi)$ | $j_{4}(\pi)$
id |  |  0 ($H_{1}$) |  |  0 ($H_{2}$) |  0 ($H_{3}$) |  0 ($H_{4}$) |  0 ($H_{5}$)
$\pi_{2}$ |  |  3 ($H_{2}$) |  |  -3 ($H_{5}$) |  1 ($H_{4}$) |  3 ($H_{3}$) |  5 ($H_{1}$)
$\pi_{3}$ |  |  -2 ($H_{1}$) |  |  -1 ($H_{4}$) |  0 ($H_{5}$) |  2 ($H_{2}$) |  4 ($H_{3}$)
$\pi_{4}$ |  |  -2 ($H_{1}$) |  |  0 ($H_{4}$) |  1 ($H_{5}$) |  4 ($H_{2}$) |  4 ($H_{3}$)
$\pi_{5}$ |  |  -1 ($H_{2}$) |  |  -1 ($H_{5}$) |  0 ($H_{4}$) |  3 ($H_{3}$) |  6 ($H_{1}$)
$\pi_{6}$ |  |  -1 ($H_{1}$) |  |  -1 ($H_{4}$) |  0 ($H_{5}$) |  3 ($H_{3}$) |  5 ($H_{2}$)

In general, for each $\pi\in\boldsymbol{\pi}$, we select the $z$ smallest
centered statistics in $S$, and then the $v-z$ remaining smallest statistics.
We define two permutations of the indices:

$\displaystyle S=\\{i_{1}(\pi),\ldots,i_{s}(\pi)\\}\quad:\quad$ $\displaystyle
C_{i_{1}(\pi)}^{\pi}\leq\ldots\leq C_{i_{s}(\pi)}^{\pi}$ $\displaystyle
M\setminus\\{i_{1}(\pi),\ldots,i_{z}(\pi)\\}=\\{j_{1}(\pi),\ldots,j_{m-z}(\pi)\\}\quad:\quad$
$\displaystyle C_{j_{1}(\pi)}^{\pi}\leq\ldots\leq C_{j_{m-z}(\pi)}^{\pi}.$

The set $\\{i_{1}(\pi),\ldots,i_{z}(\pi)\\}$ is a subset of $S$, containing
the indices of the $z$ smallest values in $S$ (for transformation $\pi$). For
instance, in the toy example we have $S=\\{2,1\\}$, and
$M\setminus\\{2\\}=\\{5,4,3,1\\}$. Then the value of the bound is defined as

$\displaystyle\ell_{z}(v)=b_{v}^{(\omega)}\quad\text{where}\quad
b_{v}^{\pi}=\sum_{h=1}^{z}C_{i_{h}}^{\pi}+\sum_{h=1}^{v-z}C_{j_{h}}^{\pi}\quad(\pi\in\boldsymbol{\pi}).$
(9)

######  Lemma 3.

$\ell_{z}(v)\leq C_{V}^{(\omega)}$ for all $V\in\mathcal{V}_{z}(v)$. Hence
$\min_{v}\ell_{z}(v)>0$ implies $\phi(z)=1$.

Now we use the bound to define a function $\underline{\phi}$ as in (4). In the
extremes, where the value of $\phi$ is known, we set
$\underline{\phi}(0)=\phi(0)=0$ and $\underline{\phi}(s+1)=\phi(s+1)=1$ (see
Lemma 2). Elsewhere, we set

$\displaystyle\underline{\phi}(z)=\mathbf{1}\left\\{\min_{v}\ell_{z}(v)>0\right\\}\quad(z\in\\{1,\ldots,s\\}).$
(10)

This function may not be monotonic, but we are only interested in its smallest
change point; indeed, if $\underline{\phi}(z)=1$ for a value $z$, we know that
$q<z$. We make it increasing and obtain a single change point in $q^{(0)}$, as
defined in (5), by imposing

$\displaystyle\underline{\phi}(z)=1\quad\text{if}\quad\underline{\phi}(z^{*})=1\text{
for some }z^{*}\in\\{0,\ldots,z\\}\quad(z\in\\{1,\ldots,s\\}).$ (11)

######  Proposition 1.

As $\underline{\phi}(z)\leq\phi(z)$ for each $z\in\\{0,\ldots,s+1\\}$,
$q^{(0)}\geq q$.

For instance, in the toy example of Figure 1, $\underline{\phi}(1)=0$ and
$\underline{\phi}(2)=1$, and so $q^{(0)}=1$. Finally, from this result we can
approximate $d$ from below with

$d^{(0)}=s-q^{(0)}.$

######  Theorem 2.

$d^{(0)}\leq d$.

In conclusion, Proposition 1 represents the basis of the shortcut, which
allows to make statements on the value of $\phi(z)$ for any $z$ by
constructing $\underline{\phi}(z)\leq\phi(z)$; it requires to evaluate a
number of tests which is linear in the total number $m$ of hypotheses, in
contrast to the exponential number required by closed testing. Subsequently,
Theorem 2 employs the shortcut to provide a lower ($1-\alpha$)-confidence
bound $d^{(0)}$ for the number of true discoveries $\delta$. The Theorem holds
for all $S\subseteq M$, hence the procedure $d^{(0)}$ has true discovery
guarantee; this means that $d^{(0)}(S)$ are lower ($1-\alpha$)-confidence
bounds for $\delta(S)$, simultaneously for all $S\subseteq M$.

In Appendix A we propose an algorithm for the shortcut, which requires
$Bm\log(m)$ operations in the worst case; then we embed it into a binary
search to approximate $q$ with reduced complexity. Moreover, we show how the
method can be combined with an algorithm of Tian et al. [2021] to find the
largest set with given TDP among a collection of incremental sets.

##  6 Equivalence to Closed Testing

The shortcut of Proposition 1 defines $\underline{\phi}(z)\leq\phi(z)$ for any
$z$. For those values of $z$ for which $\underline{\phi}(z)=1$, we know that
also $\phi(z)=1$. Where $\underline{\phi}(z)=0$, however, there are two
distinct cases. If $\phi(z)=0$, the shortcut is equivalent to closed testing;
otherwise, if $\phi(z)=1$, it is conservative, as it does not reject all sets
in $\mathcal{V}_{z}$ while closed testing does. In the toy example with $z=1$
we are in the first case (Figure 1, left), but we cannot see that from the
bound only. Now we propose a sufficient condition to state that
$\underline{\phi}(z)=\phi(z)$. This will play an important role in the
iterative shortcut of Section 7.

We will define an increasing function

$\displaystyle\overline{\phi}:\\{0,\ldots,s+1\\}\longrightarrow\\{0,1\\},\qquad\underline{\phi}(z)\leq\phi(z)\leq\overline{\phi}(z).$
(12)

This way, if $\underline{\phi}(z)=\overline{\phi}(z)$ for a value $z$, we know
that $\underline{\phi}(z)=\phi(z)$. Note that this holds in particular when
either $\underline{\phi}(z)=1$ or $\overline{\phi}(z)=0$.

Fix $z\in\\{1,\ldots,s\\}$. Based on partition (7) of $\mathcal{V}_{z}$, the
main idea is to construct a greedy path of sets $V_{z}\subset\cdots\subset
V_{m}$, with $V_{v}\in\mathcal{V}_{z}(v)$ for each $v$, and check whether
their quantiles are all strictly positive. If we find a non-positive quantile,
then we have established that $\mathcal{V}_{z}\not\subseteq\mathcal{R}$, and
so $\underline{\phi}(z)=\phi(z)=0$; the shortcut is equivalent to closed
testing for this value of $z$. We will define the path

$\displaystyle u_{z}\,:\,\\{z,\ldots,m\\}\longrightarrow\mathbb{R},\qquad
u_{z}(v)=C_{V_{v}}^{(\omega)}\quad\text{with}\quad V_{v}\in\mathcal{V}_{z}(v)$
(13)

that connects these quantiles. This way, if $u_{z}(v)\leq 0$, we know that
$\mathcal{V}_{z}(v)$ contains a non-rejected set, and so we conclude that
$\phi(z)=0$. Figure 2 displays the bound $\ell_{z}$ and the path $u_{z}$,
which we will define in the next paragraphs, for the toy example with $z=1$
and $z=2$. The path connects some of the quantiles, one for each size $v$, and
so is never smaller than the bound. From $\ell_{2}$ we already had
$\phi(2)=1$; as $u_{1}$ is entirely positive, results on $\phi(1)$ are still
unsure.

Figure 2: Toy example with $S=\\{1,2\\}$: shortcut to evaluate $\phi(z)$ in
$z=1$ and $z=2$. Points denote the quantiles for the sets in
$\mathcal{V}_{z}$. The solid and dashed lines represent the path $u_{z}$ and
the bound $\ell_{z}$, respectively.

Fix a size $v\in\\{z,\ldots,m\\}$. We define $u_{z}(v)$ as the quantile of a
set $V_{v}\in\mathcal{V}_{z}(v)$, as required in (13), choosing $V_{v}$ such
that it is unlikely to be rejected. We take $V_{v}$ as the set containing the
smallest observed non-centered statistics, with the constraint that $V_{v}$
must be an element of $\mathcal{V}_{z}(v)$. This is a heuristic choice: the
observed value of a test statistic $T_{i}$ by itself does not provide full
information on the rejection of $H_{i}$; still, if $T_{i}$ is small, generally
$H_{i}$ is less likely to be rejected.

In the toy example, choose $z=1$. The set $V_{v}\in\mathcal{V}_{1}(v)$ must
contain $v$ indices, at least $z=1$ of which is in $S$. Consider the observed
statistics $T_{i}$ (first row in Table 1, left). First, we select the column
of the smallest value in $S$, then sort the remaining columns so that their
values are in ascending order. Table 3 presents the centered statistics
$C_{i}^{\pi}$ according to this new order. We define $V_{v}$ as the set of the
indices of the first $v$ columns, obtaining $V_{1}=\\{2\\}$,
$V_{2}=\\{2,4\\}$, $V_{3}=\\{2,4,5\\}$, $V_{4}=\\{2,4,5,3\\}$ and $V_{5}=M$.

Table 3: Toy example with $S=\\{1,2\\}$: matrix of the sorted centered statistics to compute the path $u_{1}$. The value $u_{1}(v)$ is obtained by summing the first $v$ columns by row, and then taking the quantile. |  |  selected in $S$ |  | remaining
---|---|---|---|---
|  |  $i_{1}$ ($H_{2}$) |  |  $j_{1}$ ($H_{4}$) |  $j_{2}$ ($H_{5}$) |  $j_{3}$ ($H_{3}$) |  $j_{4}$ ($H_{1}$)
id |  | 0 |  | 0 | 0 | 0 | 0
$\pi_{2}$ |  | 3 |  | 1 | -3 | 3 | 5
$\pi_{3}$ |  | 2 |  | -1 | 0 | 4 | -2
$\pi_{4}$ |  | 4 |  | 0 | 1 | 4 | -2
$\pi_{5}$ |  | -1 |  | 0 | -1 | 3 | 6
$\pi_{6}$ |  | 5 |  | -1 | 0 | 3 | -1

In general, we select the $z$ smallest observed non-centered statistics in
$S$, and then the $v-z$ remaining smallest statistics. We define two
permutations of the indices:

$\displaystyle S=\\{i_{1},\ldots,i_{s}\\}\quad:\quad$ $\displaystyle
T_{i_{1}}\leq\ldots\leq T_{i_{s}}$ (14) $\displaystyle
M\setminus\\{i_{1},\ldots,i_{z}\\}=\\{j_{1},\ldots,j_{m-z}\\}\quad:\quad$
$\displaystyle T_{j_{1}}\leq\ldots\leq T_{j_{m-z}}.$ (15)

The set $\\{i_{1},\ldots,i_{z}\\}$ is a subset of $S$, containing the indices
of the $z$ smallest values in $S$. For instance, in the toy example we have
$S=\\{2,1\\}$, and $M\setminus\\{2\\}=\\{4,5,3,1\\}$. The value of the path is
then defined as

$\displaystyle u_{z}(v)=C_{V_{v}}^{(\omega)}\quad\text{where}\quad
V_{v}=\\{i_{1},\ldots,i_{z}\\}\cup\\{j_{1},\ldots,j_{v-z}\\}.$ (16)

It is immediate that $V_{v}\in\mathcal{V}_{z}(v)$, and
$u_{z}(v)\geq\ell_{z}(v)$.

######  Lemma 4.

$\min_{v}u_{z}(v)\leq 0$ implies $\phi(z)=0$.

The path is used to define a function $\overline{\phi}$ as in (12). Similarly
to the definition of $\underline{\phi}$ in the previous Section, first we set
$\overline{\phi}(0)=\phi(0)=0$, $\overline{\phi}(s+1)=\phi(s+1)=1$, and

$\displaystyle\overline{\phi}(z)=\mathbf{1}\left\\{\min_{v}u_{z}(v)>0\right\\}\quad(z\in\\{1,\ldots,s\\}).$
(17)

Then we make the function increasing by taking only its largest change point,
imposing

$\displaystyle\overline{\phi}(z)=0\quad\text{if}\quad\overline{\phi}(z^{*})=0\text{
for some }z^{*}\in\\{z,\ldots,s+1\\}\quad(z\in\\{1,\ldots,s\\}).$ (18)

######  Proposition 2.

$\underline{\phi}(z)\leq\phi(z)\leq\overline{\phi}(z)$ for each
$z\in\\{0,\ldots,s+1\\}$. Hence $\underline{\phi}(z)=\overline{\phi}(z)$
implies $\underline{\phi}(z)=\phi(z)$, i.e., equivalence between the shortcut
and closed testing.

For instance, in the toy example of Figure 2 we obtain
$\underline{\phi}(1)=0<\overline{\phi}(1)=1$ and
$\underline{\phi}(2)=\overline{\phi}(2)=1$. Hence the shortcut is equivalent
to closed testing for $z=2$, as we already observed, but we cannot establish
equivalence for $z=1$.

To summarize, the shortcut of Proposition 1 compares $q$ with any value $z$,
then Proposition 2 studies whether this shortcut is equivalent to closed
testing or conservative. The following Section shows how to improve the
shortcut in case it is conservative.

##  7 Iterative Shortcut

The shortcut we have described in Section 5 approximates closed testing and
computes $q^{(0)}\geq q$ with a number of tests that is linear in the number
of hypotheses instead of exponential. However, as seen in Section 6, it may be
conservative. In this Section we improve this single-step shortcut by
embedding it into a branch and bound algorithm; we obtain an iterative
shortcut which defines closer approximations of $q$, and thus smaller
confidence sets for $\delta$, as the number of steps increases. Eventually,
after a finite number of steps, it reaches the same results as full closed
testing.

At each step $n\in\mathbb{N}$, we will define two increasing functions

$\displaystyle\underline{\phi}^{(n)},\,\overline{\phi}^{(n)}:\\{0,\ldots,s+1\\}\longrightarrow\\{0,1\\},\qquad\underline{\phi}^{(n)}(z)\leq\phi(z)\leq\overline{\phi}^{(n)}(z).$
(19)

We will approximate $q$ from above with the change point of the first
function,

$\displaystyle
q^{(n)}=\max\left\\{z\in\\{0,\ldots,s+1\\}\,:\,\underline{\phi}^{(n)}(z)=0\right\\}.$
(20)

Then we will use the second to assess possible equivalence to closed testing.
If $\underline{\phi}^{(n)}(z)=\overline{\phi}^{(n)}(z)$ for a value $z$, then
$\underline{\phi}^{(n)}(z)=\phi(z)$ and so results cannot be further improved.
Moreover, these functions will be defined so that $q^{(n)}$ becomes a better
approximation of $q$ as $n$ increases, and finally converges to it after at
most $m$ steps:

$\displaystyle q^{(n)}\geq q^{(n+1)}\geq q^{(m)}=q\quad(n\in\mathbb{N}).$ (21)

In the next Sections we introduce the structure of the branch and bound
algorithm, then use it to construct the functions $\underline{\phi}^{(n)}$ and
$\overline{\phi}^{(n)}$ with the desired properties.

###  7.1 Branch and Bound

The branch and bound algorithm [Land and Doig, 1960, Mitten, 1970] is used
when exploring a space of elements in search of a solution, and is based on
the following principle. The space is partitioned into two subspaces, and each
subspace is systematically evaluated; the procedure can be iterated until the
best solution is found. Hence the algorithm consists of a branching rule,
which defines how to generate subspaces, and a bounding rule, which gives
bounds on the solution. This way, one can discard entire subspaces that,
according to the bounding rule, cannot contain the solution.

Here, we want to evaluate $\phi(z)$ for any value $z$, i.e., determine whether
the space $\mathcal{V}_{z}$ contains a non-rejected set (see definition (6)).
The bounding rule that allows to make statements on the existence of such a
set is the single-step shortcut of Propositions 1 and 2. If the shortcut is
equivalent to closed testing, meaning that we are able to determine $\phi(z)$,
the procedure stops; otherwise, we partition $\mathcal{V}_{z}$, and apply the
shortcut within each resulting subspace. This procedure may be iterated as
needed.

For instance, in the toy example, the single-step shortcut gives $\phi(2)=1$
but cannot determine $\phi(1)$ (Figure 2). At step $n=1$, we partition
$\mathcal{V}_{1}$ into two subspaces $\mathcal{V}_{1}^{-}$ and
$\mathcal{V}_{1}^{+}$, according to the inclusion of index $j^{*}=1$:
$\mathcal{V}_{1}^{-}$ contains all sets that do not include $j^{*}$, and
$\mathcal{V}_{1}^{+}$ contains the others. We choose $j^{*}\in M$ as the index
of the hypothesis that we believe we have most evidence against, i.e., having
the greatest observed statistic $T_{i}$ (first row in Table 1, left).
Subsequently, we use the shortcut to examine each subspace. Figure 3 shows the
bound $\ell_{1}$ and the path $u_{1}$ in the two subspaces; the path indicates
that $\mathcal{V}_{1}^{+}$ contains a non-rejected set, therefore we conclude
that $\phi(1)=0$.

Figure 3: Toy example with $S=\\{1,2\\}$: iterative shortcut at step $n=1$ to
evaluate $\phi(z)$ in $z=1$. Points denote the quantiles for the sets in
$\mathcal{V}^{-}_{1}$ and $\mathcal{V}^{+}_{1}$. The solid and dashed lines
represent the path and the bound, respectively.

In general, the branching rule is chosen to find an eventual non-rejected set
with the smallest number of steps. Fix $z\in\\{1,\ldots,s\\}$, as by Lemma 2
there is no need to partition $\mathcal{V}_{0}$ or $\mathcal{V}_{s+1}$. The
space $\mathcal{V}_{z}$ of interest is partitioned into

$\mathcal{V}_{z}^{-}=\\{V\in\mathcal{V}_{z}\,:\,j^{*}\notin
V\\},\qquad\mathcal{V}_{z}^{+}=\\{V\in\mathcal{V}_{z}\,:\,j^{*}\in V\\}$

where $j^{*}$ is the index of the greatest observed non-centered statistic,
with the constraint that the procedure cannot generate empty subspaces. Recall
that any set $V\in\mathcal{V}_{z}$ has at least size $z$ overlap with $S$.
Hence, with the notation of (14) and (15), we fix the indices
$\\{i_{1},\ldots,i_{z}\\}$ of the $z$ smallest observed statistics in $S$,
then we take $j^{*}=j_{m-z}$ as the index of the greatest remaining observed
statistic. The same principle may be applied to partition any subspace.

At any step $n\in\mathbb{N}$, the procedure partitions $\mathcal{V}_{z}$ into
$K_{n,z}$ subspaces $\mathcal{V}_{z}^{1},\ldots,\mathcal{V}_{z}^{K_{n,z}}$
without any successors, where $K_{n,z}\in\\{1,\ldots,2^{n}\\}$. Suppose to
apply the single-step shortcut within a subspace $\mathcal{V}_{z}^{k}$. If the
result is $\phi(z)=0$, then $\mathcal{V}_{z}^{k}$ contains a non-rejected set,
and we stop with $\phi(z)=0$. In contrast, if the shortcut determines that
$\phi(z)=1$, all sets in $\mathcal{V}_{z}^{k}$ are rejected, and we may
explore other subspaces. Finally, if the shortcut produces an unsure outcome,
i.e., $\phi(z)$ is still unknown, $\mathcal{V}_{z}^{k}$ can be partitioned
again.

###  7.2 Structure of the Iterative Shortcut

Fix a step $n\in\mathbb{N}$. For every $z$, the branching rule partitions
$\mathcal{V}_{z}$ into $K_{n,z}$ subspaces
$\mathcal{V}_{z}^{1},\ldots,\mathcal{V}_{z}^{K_{n,z}}$, and the bounding rule
applies the shortcut within them. We use this structure to define the
functions $\underline{\phi}^{(n)}$ and $\overline{\phi}^{(n)}$ introduced in
(19). We consider the point-wise minimums of $\underline{\phi}$ and
$\overline{\phi}$ within the different subspaces, and so we take

$\underline{\phi}^{(n)}(z)=\min_{k}\left\\{\underline{\phi}(z)\text{ in
}\mathcal{V}_{z}^{k}\right\\},\qquad\overline{\phi}^{(n)}(z)=\min_{k}\left\\{\overline{\phi}(z)\text{
in }\mathcal{V}_{z}^{k}\right\\}.$

Since $\underline{\phi}$ and $\overline{\phi}$ are increasing functions, also
$\underline{\phi}^{(n)}$ and $\overline{\phi}^{(n)}$ are increasing. The
following Proposition shows that property (19) holds, so that we can
approximate $q$ from above with $q^{(n)}$, and we can assess possible
equivalence to closed testing for any $z$. Moreover, the Proposition gives
property (21) by showing that $\underline{\phi}^{(n)}$ and
$\overline{\phi}^{(n)}$ become closer to $\phi$ as $n$ increases, and finally
converge to it after at most $m$ steps.

######  Proposition 3.

For any $n\in\mathbb{N}$ and any $z\in\\{0,\ldots,s+1\\}$,

$\underline{\phi}^{(n)}(z)\leq\underline{\phi}^{(n+1)}(z)\leq\underline{\phi}^{(m)}(z)=\phi(z)=\overline{\phi}^{(m)}(z)\leq\overline{\phi}^{(n+1)}(z)\leq\overline{\phi}^{(n)}(z).$

Hence $\underline{\phi}^{(n)}(z)=\overline{\phi}^{(n)}(z)$ implies
$\underline{\phi}^{(n)}(z)=\phi(z)$, i.e., equivalence between the iterative
shortcut and closed testing. Moreover, $q^{(n)}\geq q^{(n+1)}\geq q^{(m)}=q$.

In the toy example, consider step $n=1$ of the iterative shortcut. For $z=2$,
from results of the single-step shortcut we have
$\underline{\phi}^{(1)}(2)=\overline{\phi}^{(1)}(2)=\phi(2)=1$ without
partitioning $\mathcal{V}_{2}$. For $z=1$, from Figure 3 we have
$\underline{\phi}^{(1)}(1)=\overline{\phi}^{(1)}(1)=\phi(1)=0$. After one step
we obtain the same results as full closed testing, with $q^{(1)}=q=1$. Then,
similarly to Theorem 2, at each step $n$ we may approximate $d$ from below
with

$d^{(n)}=s-q^{(n)}.$

######  Theorem 3.

$d^{(n)}\leq d^{(n+1)}\leq d^{(m)}=d$ for each $n\in\mathbb{N}$.

Proposition 3 is the basis of the iterative shortcut. At any step $n$ and for
any $z$, it allows to make statements on the value of $\phi(z)$ by applying
the single-step shortcut within at most $2^{n}$ subspaces. Then Theorem 3
gives lower ($1-\alpha$)-confidence bounds for the number of true discoveries
$\delta$. Even if the iterative shortcut is stopped early, before reaching
convergence, $d^{(n)}$ is always a valid lower confidence bound; we have
increasingly better approximations of $d$ as $n$ increases, and obtain full
closed testing results after at most $m$ steps. As the Theorem may be applied
to any $S\subseteq M$, the procedure $d^{(n)}$ has true discovery guarantee,
meaning that $d^{(n)}(S)$ are simultaneous lower ($1-\alpha$)-confidence
bounds for $\delta(S)$.

In Appendix A we provide an algorithm for the iterative shortcut, which
converges to full closed testing results after applying the single-step
shortcut a finite, but possibly exponential, number of times.

##  8 Truncation

In the worst case, the single-step shortcut has a complexity of order
$Bm\log(m)$, and the iterative shortcut converges to closed testing after $m$
steps. In this Section, we argue that this complexity is much reduced if the
method is applied to truncated statistics, as it allows to shrink the
effective total number of hypotheses from $m$ to
$m^{\prime}\in\\{s,\ldots,m\\}$. In practice, with large $B$, $m^{\prime}$ is
obtained by taking all statistics in $S$, and only the non-truncated observed
statistics in $M\setminus S$.

Truncation-based statistics were advocated in the truncation product method of
Zaykin et al. [2002], in the context of p-value combinations. The main idea
was to emphasize smaller p-values, which are more likely to correspond to
false hypotheses, by taking into account only p-values smaller than a certain
threshold, and setting to 1 the others; a natural, common choice for the
threshold is the significance level $\alpha$. A similar procedure, the rank
truncation product [Dudbridge and Koeleman, 2003, Kuo and Zaykin, 2011], takes
into account only the $k$-th smallest p-values, for a given $k$. Eventually,
weights can be incorporated into both analyses. Such procedures provide an
increased power in many scenarios, and in particular for signal detection,
when there is a predominance of near-null effects. They have been widely
applied in literature [Yu et al., 2009, Li and Tseng, 2011, Biernacka et al.,
2012, Dai et al., 2014]; refer to Zaykin et al. [2007], Finos [2003] and Zhang
et al. [2020] for a review of the methods and their applications.

With our notation, we can define a truncation-based statistic for $H_{S}$ as
following. For each hypothesis $H_{i}$, we set to a common ground value
$t^{0}$ all statistics $T^{\pi}_{i}$ smaller than a threshold $t^{*}_{i}$. The
threshold $t^{*}_{i}$ may depend on $i$, or be a prefixed value, or be the
$k$-th greatest statistic $T_{i}^{\pi}$ ($i\in M$, $\pi\in\boldsymbol{\pi}$)
for a given $k$. The ground value must be $t^{0}\leq\min_{i}t^{*}_{i}$; it may
be chosen, for instance, as the minimum possible value of the test statistics,
or set equal to the smallest threshold $\min_{i}t^{*}_{i}$. Then

$T_{S}=\sum_{i\in S}f_{i}(T_{i}),\qquad
f_{i}(T_{i})=t^{0}\cdot\mathbf{1}\\{T_{i}<t^{*}_{i}\\}+T_{i}\cdot\mathbf{1}\\{T_{i}\geq
t^{*}_{i}\\}.$

For simplicity of notation, let $t^{*}_{i}=t^{*}$ be independent of $i$, and
$t^{0}=0$, so that

$T_{S}=\sum_{i\in S}f(T_{i}),\qquad f(T_{i})=T_{i}\cdot\mathbf{1}\\{T_{i}\geq
t^{*}\\}.$

Table 4 shows the statistics $f(T_{i})$ in the toy example after truncation
with $t^{*}=2$. Here, $t^{*}$ is set as the $k$-th greatest statistic, where
$k=\lceil Bm\alpha\rceil$ is chosen so that the proportion of non-null
contributions $f(T_{i}^{\pi})$ is approximately $\alpha$. Observe that $H_{3}$
is such that the observed truncated statistic is the greatest over all
permutations, i.e., $f(T_{3})=\max_{\pi}f(T_{3}^{\pi})$; as a consequence,
adding $\\{3\\}$ to any set $V$ can only increase the number of rejections. On
the contrary, $H_{4}$ and $H_{5}$ are such that the observed statistics are
the smallest over all permutations, and so adding $\\{4\\}$ or $\\{5\\}$ to
any set can only decrease rejections. Truncation makes those two particular
cases more common as well as easier to check, through the following
conditions:

$\displaystyle f(T_{i}^{\pi})$ $\displaystyle=0\quad\text{for all
}\pi\in(\boldsymbol{\pi}\setminus\\{\text{id}\\})$ (22) $\displaystyle
f(T_{i})$ $\displaystyle=0$ (23)

Table 4: Toy example with $S=\\{1,2\\}$: test statistics after truncation of elements smaller than $t^{*}=2$, and after dimensionality reduction. |  |  truncated $f(T_{i}^{\pi})$ |  | dim. reduction
---|---|---|---|---
|  | $H_{1}$ | $H_{2}$ | $H_{3}$ | $H_{4}$ | $H_{5}$ |  | $H_{1}$ | $H_{2}$ | $H_{4,5}$
id |  | 6 | 5 | 4 | 0 | 0 |  | 6 | 5 | 0
$\pi_{2}$ |  | 0 | 2 | 0 | 0 | 4 |  | 0 | 2 | 4
$\pi_{3}$ |  | 8 | 3 | 0 | 2 | 0 |  | 8 | 3 | 2
$\pi_{4}$ |  | 8 | 0 | 0 | 0 | 0 |  | 8 | 0 | 0
$\pi_{5}$ |  | 0 | 6 | 0 | 0 | 2 |  | 0 | 6 | 2
$\pi_{6}$ |  | 7 | 0 | 0 | 2 | 0 |  | 7 | 0 | 2

######  Proposition 4.

Let $V\subseteq M$ and $i\in M$. If $i$ satisfies condition (22), then
$V\in\mathcal{R}$ implies $(V\cup\\{i\\})\in\mathcal{R}$. If $i$ satisfies
condition (23), then $(V\cup\\{i\\})\in\mathcal{R}$ implies $V\in\mathcal{R}$.

The shortcut examines the collection $\mathcal{V}_{z}$ of sets that have at
least size $z$ overlap with $S$, searching for a set $V\notin\mathcal{R}$. In
this case, the focus is on the number of indices in $S$, hence we may reduce
the dimensionality of the problem by applying Proposition 4 to the remaining
indices. If an index $i\in M\setminus S$ satisfies condition (22), then it is
of no use in finding a non-rejected set, and so can be removed from $M$. If
two indices $i,j\in M\setminus S$ satisfy condition (23), they may be
collapsed into a new index $h$, so that $H_{h}=H_{\\{i,j\\}}$ can only
decrease the number of rejections. This allows to reduce the total number of
hypotheses from $m$ for computational purposes to a substantially lower
$m^{\prime}\in\\{s,\ldots,m\\}$. In the toy example column 3 is removed, while
columns 4 and 5 are collapsed into a single column, reducing the number of
hypotheses from $m=5$ to $m^{\prime}=3$.

##  9 Applications

In this Section, we use the iterative shortcut of Section 7 to analyze real
and simulated data. For both analyses we use the sumSome package [Vesely,
2020] developed in R [R Core Team, 2017], with underlying code in C++.

###  9.1 fMRI Data

We apply the shortcut to fMRI brain imaging data, demonstrating feasibility of
the method on large datasets, adaptation to the correlation structure and
post-hoc flexibility. In fMRI imaging, Blood Oxygen Level Dependent (BOLD)
response is measured, i.e., changes in blood flow in the brain induced by a
sequence of stimuli, at the level of small volume units called voxels. Brain
activation is then inferred as correlation between the stimuli and the BOLD
response. Researchers are interested in studying this activation within
different clusters, brain regions of connected voxels.

Typically, voxels are highly correlated. This is usually taken into account by
means of cluster extent thresholding [Nichols, 2012, Woo et al., 2014,
Rosenblatt et al., 2018]. However, when the method finds activation in a given
cluster, it only indicates that the cluster contains at least one active
voxel, but does not provide any information on the proportion of active voxels
(TDP) nor their spatial location. This leads to the spatial specificity
paradox, the counter-intuitive property that activation in a large cluster is
a weaker finding than in a small cluster [Woo et al., 2014]. Moreover, follow-
up inference inside a cluster leads to inflated Type I error rates
[Kriegeskorte et al., 2009]. In contrast, our approach not only adapts to the
high correlation, but also provides confidence sets for the TDP, and allows
for post-hoc selection and follow-up inference inside clusters.

We analyze data collected by Pernet et al. [2015], available at
https://openneuro.org/datasets/ds000158/versions/1.0.0, which compares
subjects examined while listening to vocal and non-vocal sounds. Data consists
of brain images for 140 subjects, each composed of $168{,}211$ voxels. As for
any standard fMRI analysis [Lindquist, 2008], as first-level analysis for each
subject we estimate the contrast map that describes the difference in
activation during vocal and non-vocal stimuli, with the same procedure of
Andreella et al. [2020]. Then these contrast maps are used to run the second-
level analysis; for each voxel we compute a test statistic by means of a two-
sided one-sample t-test, with the null hypothesis that the voxel’s mean
contrast between subjects is zero. Finally, we define the global test
statistic for a cluster as the sum of its voxels’ t-statistics.

We examine supra-threshold clusters with threshold 3.2, and then we make
follow-up inference inside those by studying clusters with threshold 4. The
significance level is taken as $\alpha=0.05$. We construct statistics for the
permutation test by using $B$ elements from the group of sign-flipping
transformations, which satisfies Assumption 1 [Winkler et al., 2014].
Moreover, we employ truncation as in Section 8 by setting to $t^{0}=0$ any
statistic smaller than $t^{*}=3.2$; this way, we take into account only
statistics at least as extreme as the cluster-defining threshold. We use two
settings. First, we apply a ‘quick’ analysis, fast and feasible on a standard
machine, by using $B=200$ transformations and stopping after 50 iterations of
the single-step shortcut. Subsequently, we consider a ‘long’ analysis, run on
the platform CAPRI [University of Padova, 2017], that employs $B=1000$
transformations and stops after 1000 iterations. Computation time for the
‘quick’ setting is less than 10 minutes on a standard PC, while the ‘long’
setting requires around 10 hours for clusters with threshold 3.2, and 27 hours
for follow-up inference on clusters with threshold 4.

Table 5: fMRI data: analysis of supra-threshold clusters with thresholds 3.2
and 4. Clusters with no discoveries are not shown.

cluster threshold size TDP RFT p-value coordinates $S$ $thr$ $s$ $d(S)/s$
$p_{FWER}$ $x$ $y$ $z$ quick long FP/CG/SFG/TOF/LO/LG 3.2 40094 $98.21\%$
$98.07\%$ $<0.0001$ -30 -34 -16 OFG/ITG/SG/AG/NA Left LO/TOF 4 8983 $94.79\%$
$93.86\%$ - -30 -34 -16 Right LO/LG/ITG 4 7653 $93.85\%$ $92.73\%$ - 28 -30
-18 Left SFG/FP 4 1523 $69.67\%$ $65.92\%$ - -28 34 42 CG 4 1341 $65.62\%$
$61.45\%$ - 6 40 -2 Right FP 4 1327 $66.01\%$ $61.34\%$ - 30 56 28 Left SG/AG
4 859 $47.85\%$ $41.09\%$ - -50 -56 36 Right STG/PT/MTG 3.2 12540 $95.41\%$
$94.76\%$ $<0.0001$ 60 -10 0 HG/PrG/T STG/PT/MTG/HG 4 9533 $95.17\%$ $94.59\%$
- 60 -10 0 PrG 4 485 $25.15\%$ $17.94\%$ - 52 0 48 Left STG/PT/MTG/ 3.2 10833
$94.66\%$ $93.93\%$ $<0.0001$ -60 -12 2 HG/IFG/T HG/PT/MTG/STG 4 7894
$94.20\%$ $93.46\%$ - -60 -12 2 IFG 4 667 $38.98\%$ $32.53\%$ - -40 14 26

Results are shown in Table 5, which contains the lower confidence bound for
the TDP of each cluster, as well as the size, the FWER-corrected p-value based
on random field theory (RFT), and the coordinates of the maximum t-statistic;
as RFT does not allow for follow-up inference, p-values are computed only for
clusters with threshold 3.2. Moroever, Figure 4 contains the map of the TDP
lower confidence bounds obtained from the ‘quick’ setting. Our method finds
activation in concordance with previous studies. An extensive comparison with
other methods is beyond the scope of this paper, however our results can be
immediately compared to those in Andreella et al. [2020], since the same data
was used.

Figure 4: fMRI data: map of the TDP lower confidence bounds for supra-
threshold clusters with thresholds 3.2 and 4.

Results indicate that the setting of the ‘long’ analysis did not provide
larger TDP values than the ‘quick’. While ‘quick’ calculation settings tend to
give better results on average, the difference is dominated by the variability
due to the random permutations. In Appendix B.1 we further investigate the
role of the number of iterations and permutations, confirming that the ‘quick’
setting provides suitable power.

###  9.2 Simulations

In this Section, we use the shortcut to compare the performance of different
p-value combinations through simulations. When using p-value combinations, the
unknown joint distribution of the data is often managed through worst-case
distributions, defined either generally or under restrictive assumptions [Vovk
and Wang, 2020]. However, this approach makes comparisons difficult, since
different tests have different worst cases. In contrast, our method adapts to
the unknown distribution through permutations, and thus allows to compare the
tests on equal footing. Determining which test has the highest power in
different settings is a major issue, for which a full treatment is out of the
scope of the paper; we present a first exploration.

We simulate $n$ independent observations from a multivariate normal
distribution with $m$ variables. We assume the model
$\mathbf{Y}=\boldsymbol{\mu}+\boldsymbol{\epsilon}$, with
$\mathbf{Y},\boldsymbol{\mu},\epsilon\in\mathbb{R}^{m}$. The signal
$\boldsymbol{\mu}$ is non-null for a proportion $a$ of variables, and its
value is computed so that the two-sided one-sample t-test with significance
level $\alpha$ has a given power $\beta$. The noise is
$\boldsymbol{\epsilon}\sim\text{MVN}(0,\Sigma_{\rho^{2}})$, where $\rho$ is
the level of equi-correlation between pairs of variables.

From the resulting data, we obtain p-values by applying a two-sided one-sample
t-test for each variable $i\in\\{1,\ldots,m\\}$, with null hypothesis
$H_{i}:\,\mu_{i}\neq 0$. P-values are computed for $B$ random permutations.
Moreover, we employ truncation by setting to a common ground value $t^{0}$ any
p-value greater than a threshold $t^{*}$.

We analyze the subset $S$ of false hypotheses (active variables), and the
complementary subset $M\setminus S$ of true hypotheses (inactive variables),
by means of different p-value combinations: Pearson [1933], Liptak [1958],
Cauchy [Liu and Xie, 2020], and generalized means with parameter
$r\in\\{-2,-1,-0.5,0,1,2\\}$ [Vovk and Wang, 2020]. The latter will be denoted
by VW($r$). Notice that VW(0) corresponds to Fisher [1925], and VW(1) to
Edgington [1972]. As a comparison, we also apply the maxT-method of Westfall
and Young [1993], corresponding to the limit of VW($r$) when $r$ tends to
$-\infty$; we apply the usual algorithm for the maxT.

We fix $n=50$, $m=1000$, $\alpha=0.05$, $B=200$ and $t^{0}=0.5$, then we
consider $a\in\\{0,0.01,0.02,0.05,0.1,0.2,0.5,0.9\\}$,
$\beta\in\\{0.5,0.8,0.95\\}$, $\rho\in\\{0,0.3,0.6,0.9\\}$, and
$t^{*}\in\\{0.005,0.01,0.05,0.1,1\\}$, where $t^{*}=1$ leads to no truncation.
For each setting, we simulate data 1000 times, and compute the TDP lower
confidence bound for the set $S$ as the mean of $d(S)/s$ over the simulations.
Furthermore, we compute the FWER as the proportion of simulations where
$d(M\setminus S)>0$, meaning that the method finds at least one discovery
among the true hypotheses. The algorithm is run until convergence.

Figure 5 shows the average TDP lower confidence bounds obtained in different
scenarios. Results are shown only for $\beta=0.95$ and
$t^{*}\in\\{0.005,0.05,1\\}$. Moreover, certain groups of tests have similar
performances: $(1)$ VW(1), VW(2) and Pearson; $(2)$ VW(-1) and Cauchy. For
clarity, among these tests, only VW(1) and VW(-1) are displayed in the plots.
Results indicate that the intensity of the signal, determined by the parameter
$\beta$, does not significantly affect the behavior of the tests;
nevertheless, differences between tests are amplified when the signal is high.
Furthermore, results suggest that truncation is generally advisable, unless
the signal is very dense, i.e., $a$ is high. Indeed, in most cases tests tend
to be more powerful when $t^{*}$ is low, and thus more statistics are
truncated; the improvement is stronger for sparse signal, and when considering
VW(0), VW(1) and Liptak.

Figure 5: Simulated data: TDP lower confidence bounds for the set $S$ of
active variables, by active proportion $a$ (log scale) and for different
p-value combinations. Variables have equi-correlation $\rho$. P-values smaller
than $t^{*}$ are truncated.

When the signal is sparse, VW($r$) with $r<0$ performs best; the most powerful
test is VW(-1) for low correlation, and VW(-2) for high correlation. The
remaining tests perform well when the signal is dense; among those, in the
considered scenarios VW(0) is the most powerful, but the powers of these tests
become more and more similar as the signal becomes denser. These results
confirm that when the individual contributions, i.e., the transformed
p-values, have heavy-tailed distributions, the test is more directed towards
sparse alternatives; on the contrary, when distributions are not heavy-tailed,
the test is more directed towards dense alternatives [Vovk and Wang, 2020].

The computation time is less than a minute in most scenarios, with a maximum
of around 5 minutes. Finally, simulations confirm that the method controls the
FWER. Plots for both the computation time and the FWER are provided in
Appendix B.2.

##  10 Discussion

We have proposed a new perspective on the age-old subject of global testing,
arguing that all global tests automatically come with an inbuilt selective
inference method, allowing many additional inferences to be made without
paying a price in terms of the global test’s $\alpha$-level. Our proposed
approach provides not just p-values but gives a confidence bound for the TDP,
which is considerably more informative; indeed, reporting a p-value only
infers the presence of some discoveries, while the TDP allows to quantify the
proportion of these discoveries. Moreover, such TDP confidence bounds come not
just for the full testing problem, but also simultaneously for all subsets of
hypotheses; this way, subsets of interest may be chosen post hoc, without
compromising the validity of the method. Examples of methods that make this
type of inference on the TDP are Rosenblatt et al. [2018] and Ebrahimpoor et
al. [2020], which allow to analyze brain imaging and genomics data,
respectively.

To construct simultaneous confidence bounds for the TDP of all subsets, we
have provided a general closed testing procedure for sum tests, a broad class
of global tests that includes many p-value combinations and other popular
multiple testing methods. The procedure uses permutation testing to adapt to
the unknown joint distribution of the data, avoiding strong assumptions or
potential loss of power due to worst-case distributions.

We have presented an iterative shortcut for this procedure, where the
complexity of each iteration is linearithmic in the number of hypotheses and
linear in the number of permutations. It converges to full closed testing
results after a finite, but possibly exponential, number of iterations;
furthermore, it may be stopped at any time while still providing control of
the TDP. The method is feasible in high-dimensional settings, as shown in an
application on fMRI data, where the analysis required less than 10 minutes on
a standard PC. Moreover, as shown in simulations, when studying fewer
hypotheses, in most cases the procedure converged to closed testing in
seconds. An implementation is available in the sumSome package [Vesely, 2020]
in R, with underlying code in C++.

Our method is extremely flexible, allowing any sum test of choice; different
choices of the sum test have very different power properties, as we have
illustrated. More research is needed on the performance of different sum tests
in different scenarios. Moreover, permutations are known to have a better
performance than worst-case distributions under general dependence structure,
but we have not performed a systematic investigation to quantify the
improvement given by permutations in the case of sum tests. Finally, these sum
tests procedures may be compared with other permutation-based procedures that
rely on bounding functions [Andreella et al., 2020, Blanchard et al., 2020].
However, these comparisons are beyond the scope of this paper.

## References

  * Andreella et al. [2020] A. Andreella, J. Hemerik, W. Weeda, L. Finos, and J. J. Goeman.  Permutation-based true discovery proportions for fMRI cluster analysis.  Unpublished, 2020.  URL https://arxiv.org/abs/2012.00368.
  * Biernacka et al. [2012] J. M. Biernacka, G. D. Jenkins, L. Wang, A. M. Moyer, and B. L. Fridley.  Use of the gamma method for self-contained gene-set analysis of snp data.  _European Journal of Human Genetics_ , 20:565–571, 2012\.  doi: 10.1038/ejhg.2011.236.
  * Blanchard et al. [2020] G. Blanchard, P. Neuvial, and E. Roquain.  Post hoc confidence bounds on false positives using reference families.  _Annals of Statistics_ , 48(3):1281–1303, 2020\.  doi: 10.1214/19-AOS1847.
  * Dai et al. [2014] H. Dai, J. S. Leeder, and Y. Cui.  A modified generalized fisher method for combining probabilities from dependent tests.  _Frontiers in Genetics_ , 5, 2014.  doi: 10.3389/fgene.2014.00032.
  * Donoho and Jin [2015] D. Donoho and J. Jin.  Higher criticism for large-scale inference, especially for rare and weak effects.  _Statistical Science_ , 30(1):1–25, 2015.  doi: 10.1214/14-STS506.
  * Dudbridge and Koeleman [2003] F. Dudbridge and B. P. C. Koeleman.  Rank truncated product of p-values, with application to genomewide association scans.  _Genetic Epidemiology_ , 25(4):360–366, 2003\.  doi: 10.1002/gepi.10264.
  * Ebrahimpoor et al. [2020] M. Ebrahimpoor, P. Spitali, K. Hettne, R. Tsonaka, and J. Goeman.  Simultaneous enrichment analysis of all possible gene-sets: unifying self-contained and competitive methods.  _Briefings in Bioinformatics_ , 21(4):1302–1312, 2020.  doi: 10.1093/bib/bbz074.
  * Edgington [1972] E. S. Edgington.  An additive method for combining probability values from independent experiments.  _The Journal of Psychology_ , 80(2):351–363, 1972\.  doi: 10.1080/00223980.1972.9924813.
  * Ernst [2004] M. D. Ernst.  Permutation methods: a basis for exact inference.  _Statistical Science_ , 19(4):676–685, 2004.  doi: 10.1214/088342304000000396.
  * Finos [2003] L. Finos.  _Metodi Non Parametrici per l’Analisi Multi-Focus e per il Controllo della Molteplicità con Applicazioni in Ambito Biomedico_.  PhD thesis, Department of Statistical Sciences, University of Padova, 2003\.
  * Fisher [1925] R. A. Fisher.  _Statistical Methods for Research Workers_.  Oliver and Boyd, Edinburgh, 1925.
  * Fisher [1936] R. A. Fisher.  ”the coefficient of racial likeness” and the future of craniometry.  _The Journal of the Royal Anthropological Institute of Great Britain and Ireland_ , 66:57–63, 1936.  doi: 10.2307/2844116.
  * Genovese and Wasserman [2006] C. R. Genovese and L. Wasserman.  Exceedance control of the false discovery proportion.  _Journal of the American Statistical Association_ , 101(476):1408–1417, 2006.  doi: 10.1198/016214506000000339.
  * Goeman and Solari [2010] J. J. Goeman and A. Solari.  The sequential rejection principle of familywise error control.  _Annals of Statistics_ , 38(6):3782–3810, 2010\.  doi: 10.1214/10-AOS829.
  * Goeman and Solari [2011] J. J. Goeman and A. Solari.  Multiple testing for exploratory research.  _Statistical Science_ , 26(4):584–597, 2011.  doi: doi:10.1214/11-STS356.
  * Goeman et al. [2006] J. J. Goeman, S. A. van de Geer, and H. C. van Houwelingen.  Testing against a high dimensional alternative.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 68(3):477–493, 2006.  doi: 10.1111/j.1467-9868.2006.00551.x.
  * Goeman et al. [2019] J. J. Goeman, R. J. Meijer, T. J. P. Krebs, and A. Solari.  Simultaneous control of all false discovery proportions in large-scale multiple hypothesis testing.  _Biometrika_ , 106(4):841–856, 2019.  doi: 10.1093/biomet/asz041.
  * Goeman et al. [2021] J. J. Goeman, J. Hemerik, and A. Solari.  Only closed testing procedures are admissible for controlling false discovery proportions.  _The Annals of Statistics_ , 49(2):1218–1238, 2021.
  * Hemerik and Goeman [2018a] J. Hemerik and J. J. Goeman.  Exact testing with random permutations.  _TEST_ , 27:811–825, 2018a.  doi: 10.1007/s11749-017-0571-1.
  * Hemerik and Goeman [2018b] J. Hemerik and J. J. Goeman.  False discovery proportion estimation by permutations: confidence for significance analysis of microarrays.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 80(1):137–155, 2018b.  doi: 10.1111/rssb.12238.
  * Hemerik et al. [2019] J. Hemerik, A. Solari, and J. J. Goeman.  Permutation-based simultaneous confidence bounds for the false discovery proportion.  _Biometrika_ , 106(3):635–649, 2019.  doi: 10.1093/biomet/asz021.
  * Hemerik et al. [2020] J. Hemerik, J. J. Goeman, and L. Finos.  Robust testing in generalized linear models by sign flipping score contributions.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 82(3):841–864, 2020.  doi: 10.1111/rssb.12369.
  * Hoeffding [1952] W. Hoeffding.  The large-sample power of tests based on permutations of observations.  _The Annals of Mathematical Statistics_ , 23(2):169–192, 1952.  doi: 10.1214/aoms/1177729436.
  * Huang et al. [2006] Y. Huang, H. Xu, V. Calian, and J. C. Hsu.  To permute or not to permute.  _Bioinformatics_ , 22(18):2244–2248, 2006.  doi: 10.1093/bioinformatics/btl383.
  * Knuth [1998] D. Knuth.  _The Art of Computer Programming_ , volume 3.  Addison-Wesley, Boston, 1998.
  * Kriegeskorte et al. [2009] N. Kriegeskorte, W. K. Simmons, P. S. F. Bellgowan, and C. I. Baker.  Circular analysis in systems neuroscience: the dangers of double dipping.  _Nature Neuroscience_ , 12:535–540, 2009.  doi: 10.1038/nn.2303.
  * Kuo and Zaykin [2011] C.-L. Kuo and D. V. Zaykin.  Novel rank-based approaches for discovery and replication in genomewide association studies.  _Genetics_ , 189(1):329–340, 2011.  doi: 10.1534/genetics.111.130542.
  * Lancaster [1961] H. O. Lancaster.  The combination of probabilities: an application of orthonormal functions.  _Australian Journal of Statistics_ , 3:20–33, 1961.  doi: 10.1111/j.1467-842X.1961.tb00058.x.
  * Land and Doig [1960] A. H. Land and A. G. Doig.  An automatic method of solving discrete programming problems.  _Econometrica_ , 28(3):497–520, 1960.  doi: 10.2307/1910129.
  * Langsrud [2005] Ø. Langsrud.  Rotation tests.  _Statistics and Computing_ , 15:53–60, 2005.  doi: 10.1007/s11222-005-4789-5.
  * Li and Tseng [2011] J. Li and G. C. Tseng.  An adaptively weighted statistic for detecting differential gene expression when combining multiple transcriptomic studies.  _Annals of Applied Statistics_ , 5(2A):994–1019, 2011.  doi: 10.1214/10-AOAS393.
  * Lindquist [2008] M. A. Lindquist.  The statistical analysis of fMRI data.  _Statistical Science_ , 23(4):439–464, 2008.  doi: 10.1214/09-STS282.
  * Liptak [1958] T. Liptak.  On the combination of independent tests.  _Magyar Tudományos Akadémia Matematikai Kutató Intezetenek Kozlemenyei_ , 3:1971–1977, 1958.
  * Liu and Xie [2020] Y. Liu and J. Xie.  Cauchy combination test: a powerful test with analytic p-value calculation under arbitrary dependency structures.  _Journal of the American Statistical Association_ , 115(529):393–402, 2020.  doi: 10.1080/01621459.2018.1554485.
  * Loughin [2004] T. M. Loughin.  A systematic comparison of methods for combining p-values from independent tests.  _Computational Statistics & Data Analysis_, 47(3):467 485, 2004.  doi: 10.1016/j.csda.2003.11.020.
  * Marcus et al. [1976] R. Marcus, E. Peritz, and K. R. Gabriel.  On closed testing procedures with special reference to ordered analysis of variance.  _Biometrika_ , 63(3):655–660, 1976.  doi: 10.2307/2335748.
  * Meijer and Goeman [2016] R. J. Meijer and J. J. Goeman.  Multiple testing of gene sets from gene ontology: possibilities and pitfalls.  _Briefings in Bioinformatics_ , 17(5):808–818, 2016.  doi: 10.1093/bib/bbv091.
  * Meinshausen [2006] N. Meinshausen.  False discovery control for multiple tests of association under general dependence.  _Scandinavian Journal of Statistics_ , 33(2):227–237, 2006.  doi: 10.1111/j.1467-9469.2005.00488.x.
  * Mitten [1970] L. G. Mitten.  Branch-and-bound methods: general formulation and properties.  _Operations Research_ , 18(1):24–34, 1970.  doi: 10.1287/opre.18.1.24.
  * Nichols [2012] T. E. Nichols.  Multiple testing corrections, nonparametric methods, and random field theory.  _NeuroImage_ , 62(2):811–815, 2012.  doi: 10.1016/j.neuroimage.2012.04.014.
  * Pearson [1933] K. Pearson.  On a method of determining whether a sample of size n supposed to have been drawn from a parent population having a known probability integral has probably been drawn at random.  _Biometrika_ , 25(3-4):379–410, 1933.  doi: 10.1093/biomet/25.3-4.379.
  * Pernet et al. [2015] C. R. Pernet, P. McAleer, M. Latinus, K. J. Gorgolewski, I. Charest, P. E. G. Bestelmeyer, R. H. Watson, D. Fleming, F. Crabbe, M. Valdes-Sosa, and P. Belin.  The human voice areas: Spatial organization and inter-individual variability in temporal and extra-temporal cortices.  _NeuroImage_ , 119:164–174, 2015.  doi: 10.1016/j.neuroimage.2015.06.050.
  * Pesarin [2001] F. Pesarin.  _Multivariate Permutation Tests: with Applications in Biostatistics_.  Wiley, New York, 2001.
  * Pesarin and Salmaso [2010] F. Pesarin and L. Salmaso.  _Permutation Tests for Complex Data: Theory, Applications and Software_.  Wiley, New York, 2010.
  * R Core Team [2017] R Core Team.  _R: A Language and Environment for Statistical Computing_.  R Foundation for Statistical Computing, 2017.  URL https://www.R-project.org/.
  * Rosenblatt et al. [2018] J. D. Rosenblatt, L. Finos, W. D. Weeda, A. Solari, and J. J. Goeman.  All-resolutions inference for brain imaging.  _NeuroImage_ , 181:786–796, 2018.  doi: 10.1016/j.neuroimage.2018.07.060.
  * Simes [1986] R. J. Simes.  An improved Bonferroni procedure for multiple tests of significance.  _Biometrika_ , 73(3):751–754, 1986.  doi: 10.1093/biomet/73.3.751.
  * Solari et al. [2014] A. Solari, L. Finos, and J. J. Goeman.  Rotation‐based multiple testing in the multivariate linear model.  _Biometrics_ , 70(4):954–961, 2014.  doi: 10.1111/biom.12238.
  * Southworth et al. [2009] L. K. Southworth, S. K. Kim, and A. B. Owencorresponding.  Properties of balanced permutations.  _Journal of Computational Biology_ , 16(4):625–638, 2009.  doi: 10.1089/cmb.2008.0144.
  * Tian et al. [2021] J. Tian, X. Chen, E. Katsevich, J. Goeman, and A. Ramdas.  Large-scale simultaneous inference under dependence.  Unpublished, 2021.  URL https://arxiv.org/abs/2102.11253.
  * University of Padova [2017] University of Padova.  _CAPRI: Calcolo ad Alte Prestazioni per la Ricerca e l’Innovazione_.  Strategic Research Infrastructure Grant, 2017.  URL https://capri.dei.unipd.it/.
  * Vesely [2020] A. Vesely.  _sumSome: Permutation true discovery guarantee by sum-based tests_ , 2020.  URL https://github.com/annavesely/sumSome.  R package version 4.0.3.
  * Vovk and Wang [2020] V. Vovk and R. Wang.  Combining p-values via averaging.  _Biometrika_ , asaa027, 2020.  doi: 10.1093/biomet/asaa027.
  * Westfall and Young [1993] P. H. Westfall and S. S. Young.  _Resampling-Based Multiple Testing: Examples and Methods for p-Value Adjustment_.  Wiley, New York, 1993.
  * Wilson [2019] D. J. Wilson.  The harmonic mean p-value for combining dependent tests.  _Proceedings of the National Academy of Sciences_ , 116(4):1195–1200, 2019.  doi: 10.1073/pnas.1814092116.
  * Winkler et al. [2014] A. M. Winkler, G. R. Ridgway, M. A. Webster, S. M. Smith, and T. E. Nichols.  Permutation inference for the general linear model.  _NeuroImage_ , 92(6):381–397, 2014.  doi: 10.1016/j.neuroimage.2014.01.060.
  * Won et al. [2009] S. Won, N. Morris, Q. Lu, and R. C. Elston.  Choosing an optimal method to combine p-values.  _Statistics in Medicine_ , 28(11):1537–1553, 2009\.  doi: 10.1002/sim.3569.
  * Woo et al. [2014] C.-W. Woo, A. Krishnan, and T. D. Wager.  Cluster-extent based thresholding in fmri analyses: pitfalls and recommendations.  _Neuroimage_ , 33:412–419, 2014.  doi: 10.1016/j.neuroimage.2013.12.058.
  * Wu et al. [2011] M. C. Wu, S. Lee, T. Cai, Y. Li, M. Boehnke, and X. Lin.  Rare-variant association testing for sequencing data with the sequence kernel association test.  _The American Journal of Human Genetics_ , 89(1):82–93, 2011.  doi: 10.1016/j.ajhg.2011.05.029.
  * Yu et al. [2009] K. Yu, Q. Li, A. W. Bergen, R. M. Pfeiffer, P. S. Rosenberg, N. Caporaso, P. Kraft, and N. Chatterjee.  Pathway analysis by adaptive combination of p‐values.  _Genetical Epidemiology_ , 33:700–709, 2009.  doi: 10.1002/gepi.20422.
  * Zaykin et al. [2002] D. V. Zaykin, L. A. Zhivotovsky, P. H. Westfall, and B. S. Weir.  Truncated product method for combining p‐values.  _Genetic Epidemiology_ , 22:170–185, 2002.  doi: 10.1002/gepi.0042.
  * Zaykin et al. [2007] D. V. Zaykin, L. A. Zhivotovsky, W. Czika, S. Shao, and R. D. Wolfinger.  Combining p‐values in large‐scale genomics experiments.  _Pharmaceutical Statististics_ , 6:217–226, 2007.  doi: 10.1002/pst.304.
  * Zhang et al. [2020] H. Zhang, T. Tong, J. Landers, and Z. Wu.  TFisher: a powerful truncation and weighting procedure for combining p-values.  _The Annals of Applied Statistics_ , 14(1):178–201, 2020.  doi: 10.1214/19-AOAS1302.

##  Appendix A Algorithmic Implementation

In this Appendix we provide an outline and pseudocode for the full method. In
Section A.1 we give the algorithms that evaluate $\phi(z)$ for a value $z$
through the single-step and the iterative shortcut; then in Section A.2 we
approximate $q$ by embedding these algorithms into a binary search method.
Moreover, in Section A.3 we show how the method can be employed to find the
largest subset with a given TDP. Finally, in Section A.4 we give an improved
version of the algorithms of Section A.1.

###  A.1 Algorithms for the Shortcut

Algorithm 1 implements the single-step shortcut of Propositions 1 and 2,
evaluating $\phi(z)$ for any given $z$ by constructing the bound $\ell_{z}$
and the path $u_{z}$. Recall that $\ell_{z}(v)\leq u_{z}(v)$ for each size
$v$. By Lemmas 3 and 4, we have $\phi(z)=1$ if $\ell_{z}$ is entirely
positive, and $\phi(z)=0$ if $u_{z}$ is not; in the intermediate case where
$u_{z}$ lays in the positive half-space but $\ell_{z}$ does not, the value of
$\phi(z)$ remains unsure.

Data: $z\in\\{0,\ldots,s+1\\}$

Result: $\phi(z)$ (0, 1 or unsure)

if  _$z=0$_ then return 0;

if  _$z=s+1$_ then return 1;

Unsures = FALSE;

for  _$v=z,\ldots,m$_ do

compute $\ell_{z}(v)$ as in (9);

if  _$\ell_{z}(v)\leq 0$_ then

Unsures = TRUE;

compute $u_{z}(v)$ as in (16);

if  _$u_{z}(v)\leq 0$_ then return 0;

end if

end for

if  _Unsures_ then return unsure;

return 1;

Algorithm 1 Single-step shortcut to evaluate $\phi(z)$ for any $z$.

From the result, we may obtain $\underline{\phi}(z)$ and $\overline{\phi}(z)$
as in (10) and (17), respectively. We do this by taking
$\underline{\phi}(z)=1$ if and only if the algorithm returns $\phi(z)=1$, and
$\overline{\phi}(z)=0$ if and only if it returns $\phi(z)=0$.

The procedure requires to evaluate at most $2(m-z+1)$ tests, but this number
may be smaller. The computational complexity is linearithmic in the number $m$
of hypotheses, and linear in the number $B$ of permutations; in the worst
case, when $S=M$ and $z=1$, the total number of operations is of order
$Bm\log(m)$. Recall that the choice of $B$ does not depend on $m$ or $s$.

Subsequently, Algorithm 2 implements the iterative shortcut of Proposition 3,
embedding Algorithm 1 into a branch and bound method. First, we apply the
single-step shortcut on $\mathcal{V}_{z}$; if it returns an unsure outcome,
$\mathcal{V}_{z}$ is partitioned into $\mathcal{V}_{z}^{-}$ and
$\mathcal{V}_{z}^{+}$ as in Section 7.1. Since $\mathcal{V}_{z}^{-}$ does not
include the index $j^{*}$ of the hypothesis that we believe we have most
evidence against, it appears more likely to contain a non-rejected set. With
this reasoning, the subspaces are analyzed by means of a depth-first search,
meaning that the algorithm starts by exploring $\mathcal{V}_{z}^{-}$, and
explores as far as needed along the branch where indices are removed. The user
can set a maximum number $h_{\max}$ of iterations, where each iteration
represents the analysis of a subspace by means of the single-step shortcut.
The procedure stops when it converges to closed testing results or when the
number of iterations reaches $h_{\max}$.

Data: $z\in\\{0,\ldots,s+1\\}$; $h_{\max}\in\mathbb{N}$ (maximum number of
iterations)

Result: $\phi(z)$ (0, 1 or unsure)

$X=\mathcal{V}_{z}$;

shortcut on $X$ from Algorithm 1;

if  _shortcut returns 0_ then return 0;

if  _shortcut returns 1_ then return 1;

$h=0$;

Stack = empty list;

while  _$h <h_{\text{max}}$_ do

while  _shortcut returns unsure and $h<h_{\text{max}}$_ do

$++h$;

partition $X$ into $\mathcal{V}_{z}^{-}$ and $\mathcal{V}_{z}^{+}$ as in
Section 7.1;

add $\mathcal{V}_{z}^{+}$ to Stack;

$X=\mathcal{V}_{z}^{-}$;

shortcut on $X$ from Algorithm 1;

if  _shortcut returns 0_ then return 0;

end while

while  _Stack is not empty and shortcut returns 1 and $h<h_{\text{max}}$_ do

$++h$;

$X$ = last element added in Stack;

remove last element from Stack;

shortcut on $X$ from Algorithm 1;

if  _shortcut returns 0_ then return 0;

end while

end while

if  _Stack is empty and shortcut returns 1_ then return 1;

return unsure

Algorithm 2 Iterative shortcut to evaluate $\phi(z)$ for any $z$.

Similarly to the single-step shortcut, we obtain $\underline{\phi}^{(n)}(z)$
and $\overline{\phi}^{(n)}(z)$ by taking $\underline{\phi}^{(n)}(z)=1$ if and
only if the algorithm returns $\phi(z)=1$, and $\overline{\phi}^{(n)}(z)=0$ if
and only if it returns $\phi(z)=0$.

In the worst case, $S=M$, $z=1$, and all subspaces containing more than one
set need to be partitioned; after $m$ steps, the procedure generates $2^{m}-1$
subspaces, each of them containing exactly one set. In this case, the total
number of iterations of the single-step shortcut is of order $2^{m+1}$. Even
if in the worst case the complexity is exponential in the number of
hypotheses, in many cases it is lower; moreover, by Theorem 3 we obtain a
valid lower ($1-\alpha$)-confidence bound for $\delta$ even if the algorithm
is stopped early.

###  A.2 Binary Search Method

Algorithms 1 and 2 evaluate $\phi(z)$ for a single fixed $z$, but we are
interested in the change point $q$ of the function
$\phi:\,\\{0,\ldots,s+1\\}\rightarrow\\{0,1\\}$, given in (3). In this
Section, we show how to approximate $q$ without studying all values
$z\in\\{0,\ldots,s+1\\}$.

By Lemma 2, $\phi$ has a single change point in $q$, and takes opposite values
in the extremes of its domain. Therefore $q$ may be found by embedding the
shortcut within a binary search algorithm [Knuth, 1998]. The procedure
consists of iteratively bisecting the domain of $\phi$ and selecting the
subset that must contain the change point, based on the values that the
function takes in the extremes and the bisection point. In the worst case, $q$
is determined after a number of steps of order $\log_{2}(s)$.

Even if stopped early, this procedure provides an approximation from above of
$q$, and thus a valid lower ($1-\alpha$)-confidence bound for the number of
true discoveries $\delta$. For instance, if we stop after finding that
$q\in\\{z_{1},\ldots,z_{2}\\}$, we know that $q\leq z_{2}$, and so $d\geq
s-z_{2}$. As a result, $s-z_{2}$ is a lower ($1-\alpha$)-confidence bound for
$\delta$.

###  A.3 Largest Subset with Given TDP

In this Section we show how the shortcut can be used to study incremental sets
in any desired ordering, and quickly determine the largest set having TDP at
least equal to a given value $\gamma$. This is achieved by combining the
binary search of Section A.2 with an algorithm of Tian et al. [2021].

In the toy example, suppose we want to study the incremental sets
$S_{1}=\\{1\\}$, $S_{2}=\\{1,2\\}$, $S_{3}=\\{1,2,3\\}$, $S_{4}=\\{1,2,3,4\\}$
and $S_{5}=M$, with the aim of finding the largest one having TDP lower
confidence bound at least equal to $0.5$. This means finding the greatest size
$s$ such that $d(S_{s})/s\geq 0.5$; the values $d(S_{s})$ can be computed by
means of the binary search.

In general, let $S_{1}\subset\ldots\subset S_{m}=M$ be a collection of
incremental sets, with size $|S_{s}|=s$ for each $s$, and fix
$\gamma\in[0,1]$. Then Algorithm 3 finds the greatest size $s$ with
$d(S_{s})/s\geq\gamma$. From the result, we know that the TDP of the selected
set is at least $\gamma$ with confidence $1-\alpha$.

Data: $S_{1}\subseteq\ldots\subseteq S_{m}$ (incremental sets with $|S_{s}|=s$
for each $s$); $\gamma\in[0,1]$

Result: $\max\left\\{s\in\\{1,\ldots,m\\}\,:\,d(S_{s})/s\geq\gamma\right\\}$
if the maximum exists, 0 otherwise

if  _$\gamma=0$_ then return m;

s = m;

while  _$s >0$_ do

binary search on $S_{s}$ to compute $d(S_{s})$;

if  _$d(S_{s})/s\geq\gamma$_ then return s;

$s=\lfloor d(S_{s})/\gamma\rfloor$;

end while

return 0

Algorithm 3 Procedure to study a collection of incremental sets, and determine
the size of the largest set with TDP lower confidence bound at least equal to
$\gamma$.

###  A.4 Algorithms for the Shortcut with Reduced Complexity

In this Section, we provide improved versions of Algorithms 1 and 2, which
require fewer computations. Algorithms 4 and 5 evaluate $\phi(z)$ for any $z$,
using the single-step shortcut of Propositions 1 and 2 and the iterative
shortcut of Proposition 3, respectively. The number of computations is reduced
by exploiting some properties of the bound and the path.

Data: $z\in\\{0,\ldots,s+1\\}$; $v_{1},v_{2}\in\\{z,\ldots,m\\}$ (smallest and
greatest sizes to check); get_path (TRUE to compute the path)

Result: $\phi(z)$ (0, 1 or unsure); if $\phi(z)$ is unsure, $v_{1}$ and
$v_{2}$ are updated

if  _$z=0$_ then return 0;

if  _$z=s+1$_ then return 1;

compute $c_{1}$ and $c_{2}$ as in (24) and (25);

Unsures = empty list;

for  _$v=c_{1},c_{1}-1\ldots,v_{1}$_ do

compute $\ell_{z}(v)$ as in (9);

if  _$\ell_{z}(v) >0$_ then break ;

add $v$ to Unsures;

if  _get_path_ then

compute $u_{z}(v)$ as in (16);

if  _$u_{z}(v)\leq 0$_ then return 0;

end if

end for

for  _$v=v_{1}+1,v_{1}+2,\ldots,v_{2}$_ do

compute $\ell_{z}(v)$ as in (9);

if  _$\ell_{z}(v) >0$ and $v\geq c_{2}$_ then break ;

else if  _$\ell_{z}(v)\leq 0$_ then

add $v$ to Unsures;

if  _get_path_ then

compute $u_{z}(v)$ as in (16);

if  _$u_{z}(v)\leq 0$_ then return 0;

end if

end for

if  _Unsures is empty_ then return 1;

update $v_{1}=\min\text{Unsures}$ and $v_{2}=\max\text{Unsures}$;

return unsure;

Algorithm 4 Single-step shortcut to evaluate $\phi(z)$ for any $z$ (algorithm
with reduced complexity).

Data: $z\in\\{0,\ldots,s+1\\}$; $h_{\max}$ (maximum number of iterations)

Result: $\phi(z)$ (0, 1 or unsure)

$X=\mathcal{V}_{z}$;

$v_{1}=z$; $v_{2}=m$;

get_path = TRUE;

shortcut on $X$ from Algorithm 4;

if  _shortcut returns 0_ then return 0;

if  _shortcut returns 1_ then return 1;

$h=0$;

Stack = empty list;

while  _$h <h_{\text{max}}$_ do

get_path = FALSE;

while  _shortcut returns unsure and $h<h_{\text{max}}$_ do

$++h$;

partition $X$ into $\mathcal{V}_{z}^{-}$ and $\mathcal{V}_{z}^{+}$ as in
Section 7.1;

add ($\mathcal{V}_{z}^{+}$, $v_{1}$, $v_{2}$) to Stack;

$X=\mathcal{V}_{z}^{-}$;

shortcut on $X$ from Algorithm 4;

if  _shortcut returns 0_ then return 0;

end while

get_path = TRUE;

while  _Stack is not empty and shortcut returns 1 and $h<h_{\text{max}}$_ do

$++h$;

($X$, $v_{1}$, $v_{2}$) = last element added in Stack;

remove last element from Stack;

shortcut on $X$ from Algorithm 4;

if  _shortcut returns 0_ then return 0;

end while

end while

if  _Stack is empty and shortcut returns 1_ then return 1;

return unsure

Algorithm 5 Iterative shortcut to evaluate $\phi(z)$ for any $z$ (algorithm
with reduced complexity).

The structure of Algorithm 4 is constructed so that it will be useful for
Algorithm 5. The user can define for which sizes
$v\in\\{v_{1},\ldots,v_{2}\\}\subseteq\\{z,\ldots,m\\}$ they need to check
whether $\mathcal{V}_{z}(v)\subseteq\mathcal{R}$ (see partition (7)),
supposing this is already known to be true for the remaining sizes. The
Algorithm not only evaluates $\phi(z)$, but also updates the values of $v_{1}$
and $v_{2}$, keeping track of the new set, possibly empty, of sizes that need
to be further examined. Moreover, the user can state whether they already know
that the path $u_{z}$ is entirely positive; in this case, it is not computed.

We reduce the number of computations needed by Algorithm 4 as follows. In
Lemma 5 we will show that there exist $c_{1},c_{2}\in\\{z,\ldots,m\\}$ such
that the bound $\ell_{z}(v)$ is decreasing for $v\leq c_{1}$, and increasing
for $v\geq c_{2}$. Since the single-step shortcut only uses the sign of
$\min_{v}\ell_{z}(v)$ (Lemma 3), it is not always necessary to compute
$\ell_{z}(v)$ for all sizes $v$. For instance, in the toy example with $z=1$
(Figure 1, left), we have $c_{1}=c_{2}=2$; since $\ell_{1}(4)>0$ and $4\geq
c_{2}$, we know that $\ell_{1}(5)>0$ without computing it.

We find $c_{1}$ and $c_{2}$ as following. Consider the toy example with $z=1$,
and recall definition (9). The value $\ell_{1}(v)$ is computed by summing by
row the first $v$ columns of Table 2, and then taking the quantile. Note that
the elements of column 3 are all non-negative; as a consequence,
$b_{2}^{\pi}\leq b_{3}^{\pi}$ for each $\pi$, and so
$\ell_{1}(2)\leq\ell_{1}(3)$. Moreover, since the statistics are sorted so
that $C_{j_{1}(\pi)}^{\pi}\leq\ldots\leq C_{j_{4}(\pi)}^{\pi}$ for each $\pi$,
all elements of columns 4 and 5 must be non-negative, and so
$\ell_{1}(2)\leq\ldots\leq\ell_{1}(5)$. A similar argument may be used to show
that, since all elements of column 2 are non-positive,
$\ell_{1}(1)\geq\ell_{1}(2)$.

In general, fix $z\in\\{1,\ldots,s\\}$, and consider the statistics
$C_{j_{h}(\pi)}^{\pi}$, with $h\in\\{1,\ldots,m-z\\}$, that remain after
selecting the $z$ smallest statistics in $S$ for each $\pi$. We identify the
last column where these statistics are all non-positive, taking

$\displaystyle
c_{1}=z+\max\left\\{h\in\\{1,\ldots,m-z\\}\,:\,C_{j_{h}(\pi)}^{\pi}\leq
0\;\text{for all }\pi\in\boldsymbol{\pi}\right\\}$ (24)

if the maximum exists, and $c_{1}=z$ otherwise. Similarly, we identify the
last column before these statistics become all non-negative, taking

$\displaystyle
c_{2}=z+\max\left\\{h\in\\{1,\ldots,m-z\\}\,:\,C_{j_{h}(\pi)}^{\pi}<0\;\text{for
some }\pi\in\boldsymbol{\pi}\right\\}$ (25)

if the maximum exists, and $c_{2}=z$ otherwise.

######  Lemma 5.

Define $c_{1}$ as in (24), and $c_{2}$ as in (25). Then
$\ell_{z}(z)\geq\ell_{z}(z+1)\geq\ldots\geq\ell_{z}(c_{1})$, and
$\ell_{z}(c_{2})\leq\ell_{z}(c_{2}+1)\ldots\leq\ell_{z}(m)$.

Subsequently, Algorithm 5 embeds Algorithm 4 within a branch and bound method.
With respect to Algorithm 2, the number of computations is reduced as
following. First, Lemma 6 shows that it is not necessary to compute the path
$u_{z}$ when we apply the single-step shortcut within $\mathcal{V}_{z}^{-}$;
where it is defined, it coincides with the path in $\mathcal{V}_{z}$ (e.g.,
compare Figures 2 and 3). The same argument applies any time an index is
removed.

######  Lemma 6.

$u_{z}(v)$ is the same in $\mathcal{V}_{z}$ and $\mathcal{V}_{z}^{-}$ for each
$v\in\\{z,\ldots,m-1\\}$.

Moreover, when studying subspaces it is only necessary to further examine
those sizes $v$ for which we are unsure whether
$\mathcal{V}_{z}(v)\subseteq\mathcal{R}$. For instance, in the toy example
with $z=1$, the single-step shortcut gives $\ell_{1}(4),\,\ell_{1}(5)>0$
(Figure 2, left), and so we only need to further examine $v\in\\{1,2,3\\}$
when applying the single-step shortcut within $\mathcal{V}_{1}^{-}$ and
$\mathcal{V}_{1}^{+}$.

##  Appendix B Applications

In this Appendix, we provide additional information on the applications of
Section 9. First, we investigate the impact of the number of iterations and
permutations on power in the application to fMRI data. Subsequently, we give
results on the computation time and the FWER for the analysis of simulated
data.

###  B.1 fMRI Data

We investigate the role of the number of iterations of the single-step
shortcut and the number of permutations. We do this by examining two clusters:
$(1)$ the biggest cluster with threshold 3.2 (FP/CG/SFG/TOF/LO/LG); $(2)$ its
smallest sub-cluster with non-null activation (Left SG/AG).

First, we analyze these two clusters, stopping the algorithm at different
times; the number of permutations is fixed at $B=200$. Figure 6 shows the
number of rejected, non-rejected and unsure hypotheses by the number of
iterations. As expected, the number of unsure hypotheses quickly decreases,
and becomes less than $0.5\%$ of the total after only 20 iterations. A high
number of iterations is required only for the very last unsure hypotheses.

Figure 6: fMRI data: rejected, non-rejected and unsure hypotheses by number of
iterations, for clusters (1) FP/CG/SFG/TOF/LO/LG; (2) Left SG/AG.

Subsequently, to investigate the impact of the number $B$ of permutations on
power, we study the clusters with different values $B$. Figure 7 shows the
mean TDP lower confidence bound by $B$, obtained by performing each analysis
1000 times and using at most 50 iterations. The power is increasing for $B\leq
300$, and then becomes approximately constant; from $B=200$ to $300$, the gain
is very small. Notice that the power peaks when $B$ is a multiple of
$1/\alpha$, since the permutation test is exact only for these values of $B$
[Hemerik and Goeman, 2018a]. Aside from a lower mean power, another drawback
of using few permutations is that results may be variable, due to the
randomness of the permutations.

Figure 7: fMRI data: TDP lower confidence bounds by number of permutations,
for clusters (1) FP/CG/SFG/TOF/LO/LG; (2) Left SG/AG.

###  B.2 Simulations

In this Appendix, we provide additional information on the simulations of
Section 9.2; we give results on the computation time and the FWER in different
settings and for different p-value combinations. These are shown for the
scenarios with $\beta=0.95$ and $t^{*}\in\\{0.005,0.05,1\\}$, but other values
of $\beta$ and $t^{*}$ lead to analogous results.

Figure 8 displays the computation time needed to analyze the set $S$ of false
hypotheses. Time increases with the density of the signal and when less
p-values are truncated, i.e., when $a$ and $t^{*}$ are high. In most
scenarios, the method converges in less than a minute; the maximum time is
around 4 minutes and 40 seconds, obtained when applying VW(1) in a scenario
with dense signal ($a=0.9$), medium-low correlation ($\rho=0.3$) and no
truncation ($t^{*}=1$).

Figure 8: Simulated data: computation time (log scale) for the analysis of the
set $S$ of active variables, by active proportion $a$ (log scale) and for
different p-value combinations. Variables have equi-correlation $\rho$.
P-values smaller than $t^{*}$ are truncated.

Figure 9 shows the FWER, computed as the proportion of times when the method
finds at least one discovery among the set $M\setminus S$ of true hypotheses.
Results confirm that the procedure controls the FWER; indeed, the FWER never
exceeds the significance level $\alpha$ by more than two standard deviations,
i.e., it is never higher than $0.063$.

Figure 9: Simulated data: FWER computed on the set $M\setminus S$ of inactive
variables, by inactive proportion $1-a$ (log scale) and for different p-value
combinations. Variables have equi-correlation $\rho$. P-values smaller than
$t^{*}$ are truncated.

##  Appendix C Proofs

#### Lemma 1.

Under Assumption 1, the test that rejects $H_{S}$ when
$T_{S}>T_{S}^{(\omega_{0})}$ is an $\alpha$-level test.

###### Proof.

From Assumption 1, $X_{N}\overset{\text{d}}{=}\pi X_{N}$ for each
$\pi\in\mathcal{P}$. If $H_{S}$ is true, i.e., if $S\subseteq N$, then the
joint distribution of the test statistics $T_{S}^{\pi}=T_{S}(\pi X_{S})$, with
$\pi\in\mathcal{P}$, is invariant under all transformations in $\mathcal{P}$.
Then proof of Lemma 1 is in Hemerik and Goeman [2018b] (see Theorem 1). ∎

#### Theorem 1.

Under Assumption 1, the test that rejects $H_{S}$ when $C_{S}^{(\omega)}>0$ is
an $\alpha$-level test.

###### Proof.

The $k$-th smallest centered statistic is $C_{S}^{(k)}=T_{S}-T_{S}^{(B-k+1)}$,
for any $k\in\\{1,\ldots,B\\}$. In particular, since $\omega=B-\omega_{0}+1$,
we obtain $C_{S}^{(\omega)}=T_{S}-T_{S}^{(\omega_{0})}$. Then

$T_{S}>T_{S}^{(\omega_{0})}\quad\text{if and only if}\quad
T_{S}-T_{S}^{(\omega_{0})}>0\quad\text{if and only if}\quad
C_{S}^{(\omega)}>0.$

By Lemma 1, under Assumption 1 the test that rejects $H_{S}$ when
$C_{S}^{(\omega)}>0$ is an $\alpha$-level test. ∎

#### Lemma 2.

$\phi(0)=0$ and $\phi(s+1)=1$. Moreover, $\phi(z)=0$ if and only if
$z\in\\{0,\ldots,q\\}$.

###### Proof.

When $z=0$, we have $\mathcal{V}_{0}=2^{M}$ and
$\emptyset\in(\mathcal{V}_{0}\setminus\mathcal{R})$, so $\phi(0)=0$. When
$z=s+1$, we have $\mathcal{V}_{s+1}=\emptyset\subseteq\mathcal{R}$, therefore
$\phi(s+1)=1$.

Fix a generic $z\in\\{0,\ldots,s+1\\}$. By definition (6), $\phi(z)=0$ if and
only if there exists a set $V\subseteq M$ such that $|V\cap S|\geq z$ and
$V\notin\mathcal{R}$. By definition (1) of $q$, this is true if and only if
$z\leq q$. ∎

#### Lemma 3.

$\ell_{z}(v)\leq C_{V}^{(\omega)}$ for all $V\in\mathcal{V}_{z}(v)$. Hence
$\min_{v}\ell_{z}(v)>0$ implies $\phi(z)=1$.

###### Proof.

Fix a set $V\in\mathcal{V}_{z}(v)$, so that $|V|=v$ and $|V\cap S|\geq z$, and
a transformation $\pi$. The corresponding centered statistic may be written as

$C_{V}^{\pi}=\sum_{h=1}^{z}C_{\hat{i}_{h}}^{\pi}+\sum_{h=1}^{v-z}C_{\hat{j}_{h}}^{\pi}$

where, similarly to definition (9) of $b^{\pi}_{v}$, we have

$\displaystyle V\cap S=\\{\hat{i}_{1}(\pi),\ldots,\hat{i}_{|V\cap
S|}(\pi)\\}\quad:\quad$ $\displaystyle
C_{\hat{i}_{1}(\pi)}^{\pi}\leq\ldots\leq C_{\hat{i}_{|V\cap S|}(\pi)}^{\pi}$
$\displaystyle
V\setminus\\{\hat{i}_{1}(\pi),\ldots,\hat{i}_{z}(\pi)\\}=\\{\hat{j}_{1}(\pi),\ldots,\hat{j}_{v-z}(\pi)\\}\quad:\quad$
$\displaystyle C_{\hat{j}_{1}(\pi)}^{\pi}\leq\ldots\leq
C_{\hat{j}_{v-z}(\pi)}^{\pi}.$

We compare the definitions of $b_{v}^{\pi}$ and $C_{V}^{\pi}$, starting with
the elements in $S$. Since $(V\cap S)\subseteq S$, the statistics in $V\cap S$
cannot be smaller than the first smallest statistics in $S$, i.e.,

$\displaystyle C_{\hat{i}_{h}(\pi)}^{\pi}\geq
C_{i_{h}(\pi)}^{\pi}\quad(h\in\\{1,\ldots,|V\cap S|\\}).$ (26)

A similar comparison can be made for the elements outside $S$. Write

$\displaystyle\\{\hat{j}_{1}(\pi),\ldots,\hat{j}_{v-z}(\pi)\\}$
$\displaystyle=\\{\hat{i}_{z+1}(\pi),\ldots,\hat{i}_{|V\cap
S|}(\pi)\\}\cup(V\setminus S)$
$\displaystyle\\{j_{1}(\pi),\ldots,j_{m-z}(\pi)\\}$
$\displaystyle=\\{i_{z+1}(\pi),\ldots,i_{s}(\pi)\\}\cup(M\setminus S).$

As $(V\setminus S)\subseteq(M\setminus S)$, the statistics in $V\setminus S$
cannot be smaller than the first smallest statistics in $M\setminus S$. By
combining this result with (26), we obtain

$C_{\hat{j}_{h}(\pi)}^{\pi}\geq
C_{j_{h}(\pi)}^{\pi}\quad(h\in\\{1,\ldots,v-z\\}).$

As a consequence, $C_{V}^{\pi}\geq b_{v}^{\pi}$. Since the inequality holds
for any transformation $\pi\in\boldsymbol{\pi}$, it holds also for the
quantile, so that $C_{V}^{(\omega)}\geq b_{v}^{(\omega)}=\ell_{z}(v)$.

If $\ell_{z}(v)>0$, then $C_{V}^{(\omega)}>0$ for all
$V\in\mathcal{V}_{z}(v)$, and so $\mathcal{V}_{z}(v)\subseteq\mathcal{R}$.
Finally, if $\min_{v}\ell_{z}(v)>0$, then
$\mathcal{V}_{z}(v)\subseteq\mathcal{R}$ for each $v\in\\{z,\ldots,m\\}$, and
so $\mathcal{V}_{z}\subseteq R$; by definition, $\phi(z)=1$. ∎

#### Proposition 1.

As $\underline{\phi}(z)\leq\phi(z)$ for each $z\in\\{0,\ldots,s+1\\}$,
$q^{(0)}\geq q$.

###### Proof.

Fix a value $z\in\\{0,\ldots,s+1\\}$, and suppose that
$\underline{\phi}(z)=1$. By definitions (10) and (11), this means that there
exists $z^{*}\in\\{0,\ldots,z\\}$ with $\min_{v}\ell_{z^{*}}>0$. By Lemma 3,
this implies that $\phi(z^{*})=1$ and, since $\phi$ is increasing,
$\phi(z)=1$. As $\underline{\phi}(z)=1$ implies $\phi(z)=1$, we have
$\underline{\phi}(z)\leq\phi(z)$. When comparing the change points of
$\underline{\phi}$ and $\phi$, we obtain $q^{(0)}\geq q$. ∎

#### Theorem 2.

$d^{(0)}\leq d$.

###### Proof.

From Proposition 1 we have $q^{(0)}\geq q$. Since $d^{(0)}=s-q^{(0)}$ and
$d=s-q$, we obtain $d^{(0)}\leq d$. ∎

#### Lemma 4.

$\min_{v}u_{z}(v)\leq 0$ implies $\phi(z)=0$.

###### Proof.

Suppose that $\min_{v}u_{z}(v)\leq 0$. This means that there exists
$v\in\\{z,\ldots,m\\}$ with $u_{z}(v)\leq 0$. Since
$u_{z}(v)=C_{V_{v}}^{(\omega)}$ with $V_{v}\in\mathcal{V}_{z}(v)$, we have
that $\mathcal{V}_{z}(v)\not\subseteq\mathcal{R}$. Hence
$\mathcal{V}_{z}\not\subseteq\mathcal{R}$, and so $\phi(z)=0$. ∎

#### Proposition 2.

$\underline{\phi}(z)\leq\phi(z)\leq\overline{\phi}(z)$ for each
$z\in\\{0,\ldots,s+1\\}$. Hence $\underline{\phi}(z)=\overline{\phi}(z)$
implies $\underline{\phi}(z)=\phi(z)$, i.e., equivalence between the shortcut
and closed testing.

###### Proof.

Fix a value $z\in\\{0,\ldots,s+1\\}$, and suppose that $\overline{\phi}(z)=0$.
By definitions (17) and (18), this means that there exists
$z^{*}\in\\{z,\ldots,s+1\\}$ with $\min_{v}u_{z^{*}}\leq 0$. By Lemma 3, this
implies that $\phi(z^{*})=0$ and, since $\phi$ is increasing, $\phi(z)=0$.
From the result of Proposition 1, and since $\overline{\phi}(z)=0$ implies
$\phi(z)=0$, we have $\underline{\phi}(z)\leq\phi(z)\leq\overline{\phi}(z)$.
As a consequence, if $\underline{\phi}(z)=\overline{\phi}(z)$, then
$\underline{\phi}(z)=\phi(z)=\overline{\phi}(z)$. ∎

#### Proposition 3.

For any $n\in\mathbb{N}$ and any $z\in\\{0,\ldots,s+1\\}$,

$\underline{\phi}^{(n)}(z)\leq\underline{\phi}^{(n+1)}(z)\leq\underline{\phi}^{(m)}(z)=\phi(z)=\overline{\phi}^{(m)}(z)\leq\overline{\phi}^{(n+1)}(z)\leq\overline{\phi}^{(n)}(z).$

Hence $\underline{\phi}^{(n)}(z)=\overline{\phi}^{(n)}(z)$ implies
$\underline{\phi}^{(n)}(z)=\phi(z)$, i.e., equivalence between the iterative
shortcut and closed testing. Moreover, $q^{(n)}\geq q^{(n+1)}\geq q^{(m)}=q$.

###### Proof.

Fix $n\in\mathbb{N}$ and $z\in\\{0,\ldots,s+1\\}$. First, we prove that
$\underline{\phi}^{(n)}(z)\leq\phi(z)\leq\overline{\phi}^{(n)}(z)$; as a
consequence, $\underline{\phi}^{(n)}(z)=\overline{\phi}^{(n)}(z)$ implies
$\underline{\phi}^{(n)}(z)=\phi(z)$. When we apply the shortcut within a
subspace $\mathcal{V}_{z}^{k}$ of $\mathcal{V}_{z}$, by Proposition 2 we
obtain $\underline{\phi}(z)\leq\phi(z)\leq\overline{\phi}(z)$. Since this
property holds for any subspace, it holds also when we take the minimum of
$\underline{\phi}(z)$ and $\overline{\phi}(z)$ over all subspaces, and so
$\underline{\phi}^{(n)}(z)\leq\phi(z)\leq\overline{\phi}^{(n)}(z)$.

Subsequently, we prove that

$\underline{\phi}^{(n)}(z)\leq\underline{\phi}^{(n+1)}(z)\leq\phi(z)\leq\overline{\phi}^{(n+1)}(z)\leq\overline{\phi}(z),$

and so $q^{(n)}\geq q^{(n+1)}\geq q$. The single-step shortcut examines
$\mathcal{V}_{z}$. If it determines that
$\underline{\phi}(z)=\phi(z)=\overline{\phi}(z)$, the procedure does not
partition $\mathcal{V}_{z}$, and trivially we have
$\underline{\phi}^{(n)}(z)=\phi(z)=\overline{\phi}^{(n)}(z)$ for any
$n\in\mathbb{N}$. Otherwise, if $\underline{\phi}(z)=0<\overline{\phi}(z)=1$,
at step $n=1$ we partition $\mathcal{V}_{z}$. By Proposition 3, and since
$\underline{\phi}^{(1)}$ and $\overline{\phi}^{(1)}$ take values in
$\\{0,1\\}$, we must have
$\underline{\phi}(z)\leq\underline{\phi}^{(1)}(z)\leq\phi(z)\leq\overline{\phi}^{(1)}(z)\leq\overline{\phi}(z)$.
The same argument may be applied for any subsequent step $n\in\mathbb{N}$.

Finally we prove that
$\underline{\phi}^{(m)}(z)=\phi(z)=\overline{\phi}^{(m)}(z)$, and thus
$q^{(m)}=q$. When a subspace contains a single set $V$, both the bound (9) and
the path (16) coincide with its quantile $C_{V}^{(\omega)}$, and so the
shortcut in the subspace must be equivalent to closed testing. Assume the
worst case, where $S=M$ and $z=1$, and where the shortcut is not equivalent to
closed testing in any subspace containing more than one set. The space of
interest is $\mathcal{V}_{1}=2^{M}\setminus\\{\emptyset\\}$, with size
$|\mathcal{V}_{1}|=2^{m}-1$. After $m$ steps, the procedure generates
$2^{m}-1$ subspaces, each of them containing exactly one set, and so the
shortcut is equivalent to closed testing within each one. As a consequence,
$\underline{\phi}^{(m)}(z)=\phi(z)=\overline{\phi}^{(m)}(z)$. ∎

#### Theorem 3.

$d^{(n)}\leq d^{(n+1)}\leq d^{(m)}=d$ for each $n\in\mathbb{N}$.

###### Proof.

From Proposition 3, for each $n\in\mathbb{N}$ we have $q^{(n)}\geq
q^{(n+1)}\geq q^{(m)}=q$, and so $d^{(n)}\leq d^{(n+1)}\leq d^{(m)}=d$. ∎

#### Proposition 4.

Let $V\subseteq M$ and $i\in M$. If $i$ satisfies condition (22), then
$V\in\mathcal{R}$ implies $(V\cup\\{i\\})\in\mathcal{R}$. If $i$ satisfies
condition (23), then $(V\cup\\{i\\})\in\mathcal{R}$ implies $V\in\mathcal{R}$.

###### Proof.

Recall that $V\subseteq\mathcal{R}$ if and only if
$T_{V}>T_{V}^{(\omega_{0})}$ (equivalence between Lemma 1 and Theorem 1). Fix
an index $i\in M$, and define $Q=S\cup\\{i\\}$. If $i\in S$, we obtain the
trivial case where $Q=S$, hence suppose that $i\in M\setminus S$. In this
case, $T_{Q}^{\pi}=T_{S}^{\pi}+f(T_{i}^{\pi})$, with $f(T_{i}^{\pi})\geq 0$,
for each $\pi$.

First, assume that $S\in\mathcal{R}$ and that property (22) holds. Since
$f(T_{i})\geq 0$, we have $T_{Q}\geq T_{S}$. For $\pi\neq\text{id}$, we have
$f(T_{i}^{\pi})=0$, and so $T_{Q}^{\pi}=T_{S}^{\pi}$. Hence all test
statistics for $Q$ and $S$ coincide, with the exception of the observed
statistic. Since $S\in\mathcal{R}$, $T_{S}>T_{S}^{(\omega_{0})}$, and so when
ordering the statistics we obtain $T_{Q}^{(k)}=T_{S}^{(k)}$ for all
$k\leq\omega_{0}$. Therefore $T_{Q}\geq
T_{S}>T_{S}^{(\omega_{0})}=T_{Q}^{(\omega_{0})}$, and thus $Q\in\mathcal{R}$.

Subsequently, assume that $Q\in\mathcal{R}$ and that property (23) holds.
Since $f(T_{i})=0$, we have $T_{S}=T_{Q}$. For $\pi\neq\text{id}$, since
$f(T_{i}^{\pi})\geq 0$, we have $T_{Q}^{\pi}\geq T_{S}^{\pi}$ and so
$T_{Q}^{(\omega_{0})}\geq T_{S}^{(\omega_{0})}$. We obtain
$T_{S}=T_{Q}>T_{Q}^{(\omega_{0})}\geq T_{S}^{(\omega_{0})}$, and thus
$S\in\mathcal{R}$. ∎

#### Lemma 5.

Define $c_{1}$ as in (24), and $c_{2}$ as in (25). Then
$\ell_{z}(z)\geq\ell_{z}(z+1)\geq\ldots\geq\ell_{z}(c_{1})$, and
$\ell_{z}(c_{2})\leq\ell_{z}(c_{2}+1)\ldots\leq\ell_{z}(m)$.

###### Proof.

For any $v\in\\{z+1,\ldots,m\\}$, we have

$\ell_{z}(v-1)=b_{v-1}^{(\omega)}\quad\text{where}\quad
b_{v-1}^{\pi}=b_{v}^{\pi}-C_{j_{v-z}}^{\pi}\quad(\pi\in\boldsymbol{\pi}).$

If $v\leq c_{1}$, then $C_{j_{v-z}(\pi)}^{\pi}\leq 0$ for all $\pi$, and so
$\ell_{z}(v-1)\geq\ell_{z}(v)$; as a consequence,
$\ell_{z}(z)\geq\ell_{z}(z+1)\ldots\geq\ell_{z}(c_{1})$. Similarly, if
$v>c_{2}$, then $C_{j_{v-z}(\pi)}^{\pi}\geq 0$ for all $\pi$, and so
$\ell_{z}(v-1)\leq\ell_{z}(v)$; therefore
$\ell_{z}(c_{2})\leq\ell_{z}(c_{2}+1)\leq\ldots\leq\ell_{z}(m)$. ∎

#### Lemma 6.

$u_{z}(v)$ is the same in $\mathcal{V}_{z}$ and $\mathcal{V}_{z}^{-}$ for each
$v\in\\{z,\ldots,m-1\\}$.

###### Proof.

By definition (16), in $\mathcal{V}_{z}$ the path is
$u_{z}(v)=C_{V_{v}}^{(\omega)}$ with
$V_{v}=\\{i_{1},\ldots,i_{z}\\}\cup\\{j_{1},\ldots,j_{v-z}\\}$ for any
$v\in\\{z,\ldots,m\\}$. Recall that
$\mathcal{V}_{z}^{-}=\\{V\in\mathcal{V}_{z}\,:\,j^{*}\notin V\\}$, where
$j^{*}=j_{m-z}$ (see Section 7.1). Therefore in $\mathcal{V}_{z}^{-}$ the
greatest set is $M\setminus\\{j^{*}\\}$, and so the path $u_{z}$ is defined
for sizes $v\in\\{z,\ldots,m-1\\}$. Moreover, $j^{*}\notin V_{v}$ for all
$v\in\\{z,\ldots,m-1\\}$, hence in $\mathcal{V}_{z}^{-}$ the path is defined
as in $\mathcal{V}_{z}$. ∎