Journal of the Royal Statistical Society Series B: Statistical Methodology \-
Advance Access Publication Date: - Original Article

Müller et al.

[$\ast$]Corresponding author<EMAIL_ADDRESS>(MM: need full mailing address
and email address of one corresponding author

0Year 0Year 0Year

# Isotonic subgroup selection

Manuel M. Müller  Henry W. J. Reeve  Timothy I. Cannings  Richard J. Samworth
Statistical Laboratory, University of Cambridge, Cambridge, UK  School of
Mathematics, University of Bristol, Bristol, UK  School of Mathematics,
University of Edinburgh, Edinburgh, UK

(2023; 2023; Date; Date; Date)

###### Abstract

Given a sample of covariate-response pairs, we consider the subgroup selection
problem of identifying a subset of the covariate domain where the regression
function exceeds a pre-determined threshold. We introduce a computationally-
feasible approach for subgroup selection in the context of multivariate
isotonic regression based on martingale tests and multiple testing procedures
for logically-structured hypotheses. Our proposed procedure satisfies a non-
asymptotic, uniform Type I error rate guarantee with power that attains the
minimax optimal rate up to poly-logarithmic factors. Extensions cover
classification, isotonic quantile regression and heterogeneous treatment
effect settings. Numerical studies on both simulated and real data confirm the
practical effectiveness of our proposal, which is implemented in the R package
ISS.(MM: need to shorten abstract by 12 words down to 100 words for JRSSB
submission.) (MM: need to include: “a short running head of 50 characters or
less to ensure that a Discussion Paper manuscript is flagged on submission for
consideration for reading at a Discussion Meeting of the Society, the author
should mention this in the title page/covering note”(MM: more things to note,
although I am not sure if we have to worry about these (based on
https://academic.oup.com/jrsssb/pages/general-instructions):

  * •

All tables must be placed at the end of the main text — does not seem
reasonable to me nor does it seem to be enforced? Not sure are relevant for us
(since we were told we can submit in any format).

  * •

Specific requirements for figures, which I am not sure are relevant for us
(since we were told we can submit in any format).

  * •

Supplementary material files should be no larger than 2MB each.

  * •

Source code for any specialized, in-house scripts or programs, that are
necessary for the reproduction of results, must be deposited in a public
repository (e.g., GitHub), or uploaded as Supplementary material.

  * •

Text lists of items should be identified as sequences (a), (b), (c), ….
Further itemization within these should be denoted by (i), (ii), (iii), ….
‘Bullet’ points, (A), (B), (C), …, (I), (II), (III), … or other symbols are
not used.

  * •

Online, I find “Statements of theorems, lemmas, corollaries, propositions,
remarks etc. should be numbered sequentially and individually by type and not
by section, e.g., theorem 1, theorem 2, proposition 1, proposition 2 …, not
theorem 1, proposition 2, theorem 3, proposition 4 …, or theorem 2.1, theorem
3.1, …”, but this contradicts the style file.

  * •

Mathematical equations or complicated expressions should be typed on lines
separate from the text (‘displayed’).

  * •

Matrixes should be indicated by italics and vectors by bold.

  * •

The order of brackets in nested expressions is [()].

  * •

Figure 1 currently only has resolution for digital viewing, not print.

)

###### keywords:

isotonic regression, multiple testing, post-selection inference, subgroup
selection, super-level set estimation (MM: need 5-6, alphabetically ordered)

##  1 Introduction

In regression settings, _subgroup selection_ refers to the challenge of
identifying a subset of the covariate domain on which the regression function
satisfies a particular property of interest. This is a post-selection
inference problem, since the region is to be selected after seeing the data,
and yet we still wish to claim that with high probability, the regression
function satisfies this property on the selected set. Important applications
can be found in precision medicine, for instance, where the chances of a
desirable health outcome may be highly heterogeneous across a population, and
hence the risk for a particular individual may be masked in a study
representing the entire population.

A natural strategy for identifying such group-specific effects is to divide a
study into two stages, where the first stage is used to identify a potentially
interesting subset of the covariate domain, and the second attempts to verify
that it does indeed have the desired property (stallard2014adaptive). However,
such a two-stage process may often be both time-consuming and potentially
expensive due to the inefficient use of the data, and moreover the binary
second stage verification may fail. In such circumstances, we are unable to
identify a further subset of the original selected set on which the property
does hold.

In many applications, heterogeneity across populations may be characterised by
monotonicity of a regression function in individual covariates. For instance,
age, smoking, hypertension and obesity are among known risk factors for
coronary heart disease (torpy2009coronary), while for individuals with
hypertrophic cardiomyopathy, risk factors for sudden cardiac death (SCD)
include family history of SCD, maximal heart wall thickness and left atrial
diameter (omahony2014novel). It is frequently of interest to identify a subset
of the population deemed to be at low or high risk, for instance to determine
an appropriate course of treatment. This amounts to identifying an appropriate
superlevel set of the regression function.

In this paper, we introduce a framework that allows the identification of the
$\tau$-superlevel set of an isotonic regression function, for some pre-
determined level $\tau$. A key component of our formulation of the problem is
to recognise that often there is an asymmetry to the two errors of including
points that do not belong to the superlevel set, and failing to include points
that do. For instance, in the case of hypertrophic cardiomyopathy, a false
conclusion that an individual is at low risk of sudden cardiac death within
five years, and hence does not require an implantable cardioverter
defibrillator (omahony2014novel), is more serious than the opposite form of
error, which obliges a patient to undergo surgery and deal with the
inconveniences of the implanted device.

To introduce our isotonic subgroup selection setting, suppose that we are
given $n$ independent copies of a covariate-response pair $(X,Y)$ having a
distribution on $\mathbb{R}^{d}\times\mathbb{R}$ with coordinate-wise
increasing regression function $\eta$ given by $\eta(x):=\mathbb{E}(Y|X=x)$
for $x\in\mathbb{R}^{d}$. Given a threshold $\tau\in\mathbb{R}$, and writing
$\mathcal{X}_{\tau}(\eta):=\\{x\in\mathbb{R}^{d}:\eta(x)\geq\tau\\}$ for the
$\tau$-superlevel set of $\eta$, we seek to output an estimate $\hat{A}$ of
$\mathcal{X}_{\tau}(\eta)$ with the first priority that it guards against the
more serious of the two errors mentioned above. Without loss of generality, we
take this more serious error to be including points in $\hat{A}$ that do not
belong to $\mathcal{X}_{\tau}(\eta)$, and we therefore require Type I error
control in the sense that $\hat{A}\subseteq\mathcal{X}_{\tau}(\eta)$ with
probability at least $1-\alpha$, for some pre-specified $\alpha\in(0,1)$.
Subject to this constraint, we would like $\mu(\hat{A})$ to be as large as
possible, where $\mu$ denotes the marginal distribution of $X$.

Figure 1: A visualisation with $d=2$ and $n=1000$. The unknown regression
function is $(x^{(1)},x^{(2)})^{\top}\mapsto\lceil
6x^{(1)}\rceil/6+\bigl{(}x^{(2)}\bigr{)}^{2}$ rescaled to the interval
$[0,1]$, depicted by the multi-coloured surface. The unknown grey surface
gives the $0.5$-super-level set, of which the red area is selected by our
proposed procedure $\hat{A}^{\mathrm{ISS}}$.

One plausible strategy to achieve this goal is to construct a one-sided,
uniform confidence band for $\eta$, and output the set on which the lower
confidence limit is at least $\tau$. Unfortunately, however, such an approach
tends to have sub-optimal empirical performance (see Section 5), because the
lower confidence bound is required to protect against exceeding $\eta(x)$ at
all points $x$ in the covariate domain, whereas it is only points close to the
boundary of the $\tau$-superlevel set for which there is significant doubt
about their inclusion. We therefore adopt a different approach, and seek to
compute at each observation a $p$-value for the null hypothesis that the
regression function is below $\tau$ based on an anytime-valid martingale
procedure (duan2020interactive; howard2021uniform). The monotonicity of the
regression function implies logical relationships between these hypotheses,
but it is far from obvious how to combine these $p$-values effectively,
particularly in the multivariate case, where we do not have a natural total
ordering on $\mathbb{R}^{d}$. Our strategy is to introduce a tailored multiple
testing procedure with familywise error rate control, building on ideas of
goeman2010sequential and meijer2015multiple. This allows us to construct our
final output set $\hat{A}^{\mathrm{ISS}}$ as the upper hull of the
observations corresponding to the rejected hypotheses; see Section 2 for a
more formal description of our proposed procedure, which is both
computationally feasible and does not require the choice of any smoothing
parameters. Our methodology is implemented in the R package ISS
(Mueller2023ISS); an illustration in a bivariate example is given in Figure 1.

Our first theoretical result, in Section 3.1, verifies that
$\hat{A}^{\mathrm{ISS}}$ does indeed control Type I error in the sense
outlined above. We then turn our attention to power in Section 3.2, and
provide both high-probability and expectation bounds on
$\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}\bigr{)}$.
Our bound decomposes as a sum of two terms, where the first reflects the error
incurred in determining whether each data point belongs to
$\mathcal{X}_{\tau}(\eta)$, and depends on the growth rate of the regression
function as we move further into the $\tau$-superlevel set from its boundary.
The second term represents the error arising from the uncertainty of whether
or not regions between the data points belong to this superlevel set. Our
final theoretical contribution, in Section 3.3, reveals that
$\hat{A}^{\mathrm{ISS}}$ attains the optimal power in the sense of minimising
$\mathbb{E}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}\bigr{)}\bigr{\\}}$
up to poly-logarithmic factors, among all procedures that control the Type I
error.

In Section 4, we present various extensions that broaden the scope of our
methodology. First, in Section 4.1, we describe alternative $p$-values that
can be used, and that may yield more power for small and moderate sample
sizes. Section 4.2 introduces three variants of $\hat{A}^{\mathrm{ISS}}$ that
are tailored to specific settings including homoscedastic Gaussian errors,
classification and heavy-tailed errors. Finally, in Section 4.3, we show how
our proposal can be extended to cover heterogeneous treatment effect settings.

Section 5 is devoted to a study of the empirical performance of
$\hat{A}^{\mathrm{ISS}}$ in a wide range of settings, with 14 regression
functions chosen to illustrate different characteristics of interest, as well
as different sample sizes and dimensions. The broad conclusion across these
many scenarios is that, compared with various alternative approaches,
$\hat{A}^{\mathrm{ISS}}$ has the most power for isotonic subgroup selection.
In Section 6, we illustrate the performance of $\hat{A}^{\mathrm{ISS}}$ on two
real datasets, the first of which is taken from the AIDS Clinical Trials Group
Study 175 (ACTG 175) (speff2trial). Here, we consider two problems: first, we
seek to identify a low-risk subgroup and, second, in the context of
heterogeneous treatment effects we aim to identify a subgroup of patients for
whom a new therapy is at least as effective as the baseline medication. The
second dataset concerns fuel consumption (quinlan1993combining), where we seek
to identify fuel-efficient cars based on their weight and engine displacement.
The appendix consists of proofs of all of our main results, as well as
statements and proofs of auxiliary results, further simulations and a
discussion of an alternative and general approach to combining the $p$-values
due to meijer2015multiple. Although this strategy is often highly effective in
multiple testing problems, we show that, surprisingly, it has sub-optimal
worst-case performance in our isotonic subgroup selection setting.

Isotonic regression has a long history dating back to ayer1955empirical,
brunk1955maximum and vaneeden1956maximum. Much recent interest has focused on
risk bounds and oracle inequalities, which have been derived by
meyer2000degrees, zhang2002risk, chatterjee2014new, chatterjee2015risk,
bellec2018sharp, han2019isotonic, deng2020isotonic, fokianos2020integrated and
pananjady2022isotonic. Pointwise asymptotic confidence intervals in
multivariate isotonic regression have been proposed by deng2021confidence,
while confidence bands in the univariate case have been studied by
yang2019contraction.

In the clinical trials community, the dangers of the naive approach to
subgroup selection that ignores the key post-selection inference issue have
been well understood for many years (senn1997wisdom; feinstein1998problem;
rothwell2005subgroup; wang2007Statistics; kaufman2013these;
altman2015subgroup; zhang2015subgroup; gabler2016no; lipkovich2017tutorial;
watson2020machine). Valid approaches that control Type I error in the sense
above have been proposed by ballarini2018subgroup and wan2022confidence in the
context of linear regression, and reeve2021optimal for a smoothly-varying
regression function.

The asymmetry of the two losses in our framework has some similarities with
that of Neyman–Pearson classification (cannon2002learning; scott2005neyman;
tong2016survey; xia2021intentional). There, covariate-response pairs $(X,Y)$
take values in $\mathbb{R}^{d}\times\\{0,1\\}$, and we seek a classifier
$C:\mathbb{R}^{d}\rightarrow\\{0,1\\}$ that minimises
$\mathbb{P}\bigl{(}C(X)=0|Y=1\bigr{)}$ subject to an upper bound on
$\mathbb{P}\bigl{(}C(X)=1|Y=0\bigr{)}$. In addition to allowing continuous
responses, another key difference of our paradigm is that we incur a Type I
error whenever our selected set $\hat{A}$ contains a single point that does
not belong to the $\tau$-superlevel set of the regression function. In other
words, instead of controlling averages over sub-populations, our framework
provides guarantees at an individual level, which is ethically advantageous,
e.g. in medical contexts.

To conclude the introduction, we collect some notation used throughout the
paper.

##### Notation.

For any $n\in\mathbb{N}$, let $[n]:=\\{1,\ldots,n\\}$ and let
$[0]:=\emptyset$. Write $x\wedge y:=\min(x,y)$ and $x\vee y:=\max(x,y)$ for
$x,y\in\mathbb{R}$. Further, let $x_{+}:=x\vee 0$ and $\log_{+}x:=\log(x\vee
e)$ for any $x\in\mathbb{R}$. Denote by $\|\cdot\|_{\infty}$ the supremum norm
on $\mathbb{R}^{d}$, and given $x\in\mathbb{R}^{d}$ and $r>0$, define the
closed supremum norm ball by
${B}_{\infty}(x,r):=\\{z\in\mathbb{R}^{d}:\|z-x\|_{\infty}\leq r\\}$. For
$x_{1}=(x_{1}^{(1)},\ldots,x_{1}^{(d)})^{\top},x_{2}=(x_{2}^{(1)},\ldots,x_{2}^{(d)})^{\top}\in\mathbb{R}^{d}$,
we write $x_{1}\preccurlyeq x_{2}$ (or, equivalently, $x_{2}\succcurlyeq
x_{1}$) if $x_{1}^{(j)}\leq x_{2}^{(j)}$ for all $j\in[d]$. A function
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is said to be (coordinate-wise)
_increasing_ if $f(x_{0})\leq f(x_{1})$ whenever $x_{0}\preccurlyeq x_{1}$. A
set $U\subseteq\mathbb{R}^{d}$ is called an _upper set_ if, whenever $x\in U$
and $x\preccurlyeq x^{\prime}$, we have $x^{\prime}\in U$. Given any
$A\subseteq\mathbb{R}^{d}$, the _upper hull_ of $A$ is the intersection of all
upper sets that contain $A$. Finally, for a Borel probability measure $\mu$ on
$\mathbb{R}^{d}$, we let $\mathrm{supp}(\mu)$ denote the _support_ of $\mu$,
i.e., the intersection of all closed sets $C\subseteq\mathbb{R}^{d}$ with
$\mu(C)=1$. For $\tau\in\mathbb{R}$, and
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ we let
$\mathcal{X}_{\tau}(f):=\\{x\in\mathbb{R}^{d}:f(x)\geq\tau\\}$.

A _graph_ $G=(I,E)$ consists of a non-empty, finite set $I$ of _vertices_ and
a set $E\subseteq I\times I$ of _edges_. We say $G$ is _directed_ if $(i,j)\in
E$ does not imply $(j,i)\in E$. A _directed path_ from $i\in I$ to $j\in I$ is
a collection of distinct vertices $i_{0},i_{1},\ldots,i_{m}\in I$ for some
$m\in\mathbb{N}$ with $i_{0}=i$ and $i_{m}=j$ such that $(i_{k-1},i_{k})\in E$
for all $k\in[m]$. A _cycle_ is a directed path from $i\in I$ to itself. A
_directed acyclic graph (DAG)_ is a directed graph that does not contain any
cycles. Given a DAG $G=(I,E)$, we write $L(G):=\\{i\in I:(i,i^{\prime})\notin
E\text{ for all }i^{\prime}\in I\\}$ for the set of its _leaf_ nodes and
$\\{i\in I:(i^{\prime},i)\notin E\text{ for all }i^{\prime}\in I\\}$ for its
_root_ nodes. For $i\in I$, let
$\operatorname{\mathrm{pa}}_{G}(i):=\\{i^{\prime}\in I:(i^{\prime},i)\in E\\}$
denote the set of _parents_ of node $i$ and, similarly, write
$\operatorname{\mathrm{ch}}_{G}(i):=\\{i^{\prime}\in
I:i\in\operatorname{\mathrm{pa}}_{G}(i^{\prime})\\}$ for the set of _children_
of node $i$. Further, defining
$\operatorname{\mathrm{an}}^{1}_{G}(i):=\operatorname{\mathrm{pa}}_{G}(i)$ and
$\operatorname{\mathrm{an}}^{k+1}_{G}(i):=\bigcup_{j\in\operatorname{\mathrm{an}}^{k}_{G}(i)}\operatorname{\mathrm{pa}}_{G}(j)$
for $k\in\mathbb{N}$, we can define
$\operatorname{\mathrm{an}}_{G}(i):=\bigcup_{k\in\mathbb{N}}\operatorname{\mathrm{an}}^{k}_{G}(i)$
to be the set of _ancestors_ of node $i$. Similarly, let
$\operatorname{\mathrm{de}}_{G}(i):=\\{i^{\prime}\in
I:i\in\operatorname{\mathrm{an}}_{G}(i^{\prime})\\}$ denote the set of
_descendants_ of node $i$. A _reverse topological ordering_ of a DAG $G=(I,E)$
with $I=[m]$ is a permutation $\pi_{G}:I\rightarrow I$ such that if $i\in I$
and $i^{\prime}\in\operatorname{\mathrm{an}}_{G}(i)$, then
$\pi_{G}(i)<\pi_{G}(i^{\prime})$. Any directed graph is acyclic if and only if
it has a reverse topological ordering. We remark that all of these definitions
remain unchanged when applied to a _weighted DAG_ $G=(I,E,\bm{w})$, i.e. a DAG
$(I,E)$ equipped with edge weights $\bm{w}=(w_{e}\geq 0:e\in E)$, and that any
unweighted DAG may implicitly be assumed to be a weighted DAG with unit
weights. A DAG $G=(I,E)$ is a _polyforest_ if
$|\operatorname{\mathrm{pa}}_{G}(i)|\leq 1$ for all $i\in I$, and a weighted
DAG $G=(I,E,\bm{w})$ is a _polyforest-weighted DAG_ if $F:=(I,\\{e\in
E:w_{e}>0\\})$ is a polyforest.

##  2 Methodology

Let $P$ denote a distribution on $\mathbb{R}^{d}\times\mathbb{R}$, and let
$(X,Y)\sim P$. Suppose that the regression function
$\eta:\mathbb{R}^{d}\rightarrow\mathbb{R}$, defined by
$\eta(x):=\mathbb{E}(Y|X=x)$, is increasing, and that the conditional
distribution of $Y-\eta(X)$ given $X$ is sub-Gaussian111Recall that a random
variable $Z$ is _sub-Gaussian with variance parameter $\sigma^{2}$_ if
$\mathbb{E}(e^{tZ})\leq e^{\sigma^{2}t^{2}/2}$ for every $t\in\mathbb{R}$.
with variance parameter $\sigma^{2}$. Given an independent and identically
distributed sample $(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\sim P$, a threshold
$\tau\in\mathbb{R}$ and a nominal Type I error rate $\alpha\in(0,1)$, we would
like to identify a Borel measurable set $\hat{A}\subseteq\mathbb{R}^{d}$ such
that with probability at least $1-\alpha$, we have $\eta(x)\geq\tau$ for all
$x\in\hat{A}$. Subject to this constraint, we would like $\mu(\hat{A})$ to be
as large as possible, where $\mu$ denotes the marginal distribution of $X$. An
important observation is that, since $\mathcal{X}_{\tau}(\eta)$ is an upper
set, replacing $\hat{A}$ with its upper hull does not increase the Type I
error probability, and may increase its $\mu$-measure.

Our general strategy is initially to focus on a subset of observations, and
seek to compute a $p$-value at each of these observations for the null
hypothesis that the regression function is below $\tau$. We can then carefully
combine these $p$-values using a multiple testing procedure having familywise
error rate control over our structured hypotheses, and finally output the
upper hull of the covariate observations corresponding to the rejected
hypotheses. More precisely, for $m\in[n]$, and writing
$\mathcal{D}_{X,m}:=(X_{1},\ldots,X_{m})$ for our reduced sample with the
shorthand $\mathcal{D}_{X}:=\mathcal{D}_{X,n}$, we will construct $p$-values
$\bm{p}:=(p_{i})_{i\in[m]}$ having the property that $\mathbb{P}(p_{i}\leq
t|\mathcal{D}_{X})\leq t$ for every $t\in[0,1]$ whenever $\eta(X_{i})<\tau$.
Next, we show how to exploit these $p$-values to obtain a set
$\mathcal{R}_{\alpha}(\mathcal{D}_{X,m},\bm{p})\subseteq[m]$ of rejected
hypotheses having the familywise error control property that with probability
at least $1-\alpha$, we have $\eta(X_{i})\geq\tau$ for every
$i\in\mathcal{R}_{\alpha}(\mathcal{D}_{X,m},\bm{p})$. Our final output set,
$\hat{A}$, is the upper hull of
$\\{X_{i}:i\in\mathcal{R}_{\alpha}(\mathcal{D}_{X,m},\bm{p})\\}$.

It remains to describe how we propose to construct the $p$-values, and to
control the familywise error, and to this end, we first focus on the case
$d=1$ for simplicity of exposition. One difference between the univariate and
multivariate cases is that we take $m=n$ in the former. Consider the null
hypothesis that $\eta(x)<\tau$ for some $x\in\mathbb{R}$, so that
$\eta(X_{i})<\tau$ whenever $X_{i}\leq x$. Write
$\mathcal{I}(x):=\\{i\in[n]:X_{i}\leq x\\}$ and $n(x):=|\mathcal{I}(x)|$, and,
for $j\in[n(x)]$, let $X_{(j)}(x)$ denote the $j$th nearest neighbour of $x$
among $\\{X_{i}:i\in\mathcal{I}(x)\\}$, where for definiteness ties are broken
by retaining the original ordering. Writing $Y_{(1)}(x),\ldots,Y_{(n)}(x)$ for
the concomitant responses, under the null and conditional on
$\mathcal{D}_{X}$, the process

$S_{k}\equiv
S_{k}(x,\sigma,\tau,\mathcal{D}):=\sum_{j=1}^{k}\frac{Y_{(j)}(x)-\tau}{\sigma}$
(1)

for $k\in[n(x)]$ is a supermartingale with negative mean. Thus, large values
of $S_{k}$ for some $k\in[n(x)]$ provide evidence against the null. One could
also consider the alternative supermartingale
$S_{k}^{\prime}:=\sum_{j=1}^{k}\bigl{(}Y_{(n(x)+1-j)}(x)-\tau\bigr{)}/\sigma$
for $k\in[n(x)]$, but our approach has the advantage that $S_{k}$
stochastically dominates $S_{k}^{\prime}$, so will have at least the same
power. Tests based on supermartingales such as $(S_{k})$ are known as
_martingale tests_ (duan2020interactive) and time-uniform upper boundaries
$(v_{k})$ are known for a variety of families of increment distributions
(howard2021uniform); thus, $v_{k}\equiv v_{k}(\alpha)$ has the property that
$\mathbb{P}\bigl{(}\max_{k\in[n(x)]}(S_{k}-v_{k})\geq 0\bigr{)}\leq\alpha$
under the null hypothesis $\eta(x)<\tau$. These inequalities can be inverted
to yield a $p$-value; see Figure LABEL:fig:martingale_test. Definition 1 below
extends these ideas to the general multivariate case.

Turning now to familywise error rate (FWER) control, and working conditional
on $\mathcal{D}_{X}$ with $d=1$, consider $p$-values
$\bm{p}:=(p_{i})_{i\in[n]}$ constructed as above for testing the null
hypotheses $H_{i}:\eta(X_{i})<\tau$ for $i\in[n]$. One approach to controlling
the FWER at level $\alpha$ is to reject only hypotheses $H_{i}$ with
$i\in\\{j\in[n]:p_{k}\leq\alpha\text{ for all }k\text{ with either
}X_{k}>X_{j}\text{ or both }X_{k}=X_{j}\text{ and }k\leq
j\\}=:\mathcal{R}^{\mathrm{FS}}_{\alpha}(\mathcal{D}_{X},\bm{p})$. Controlling
the FWER by employing an a priori ordering is known as a _fixed sequence
procedure_ (westfall2001optimally; hsu1999stepwise), and explains the
superscript $\mathrm{FS}$ in the notation
$\mathcal{R}^{\mathrm{FS}}_{\alpha}(\mathcal{D}_{X},\bm{p})$. Writing
$H_{(i)}:\eta\bigl{(}X_{(i)}(\max_{j\in[n]}X_{j})\bigr{)}<\tau$ and $p_{(i)}$
for the corresponding $p$-value, this approach can be seen as a sequential
procedure that, starting with $i=1$, stops and does not reject $H_{(i)}$ if
$p_{(i)}>\alpha$ and otherwise rejects $H_{(i)}$ before proceeding to $i+1$,
where the step is repeated. Here, the order in which we decide whether
hypotheses should be rejected is motivated by the fact that $H_{(i)}\subseteq
H_{(i+1)}$ for $i\in[n-1]$. A computationally-efficient implementation of this
procedure only needs to calculate $p_{(i+1)}$ if $H_{(i)}$ has been rejected.

We now extend the presented ideas to the general case $d\in\mathbb{N}$. The
construction of the $p$-values follows a similar approach as above, but the
order in which the responses enter the supermartingale sequence is now
determined by the supremum norm distance of the corresponding covariates from
$x$.

######  Definition 1.

Given $x\in\mathbb{R}^{d}$, $\tau\in\mathbb{R}$, $\sigma>0$ and
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\in(\mathbb{R}^{d}\times\mathbb{R})^{n}$
write
$\mathcal{I}(x)\equiv\mathcal{I}(x,\mathcal{D}_{X}):=\\{i\in[n]:X_{i}\preccurlyeq
x\\}$ and again $n(x)\equiv
n(x,\mathcal{D}_{X}):=|\mathcal{I}(x,\mathcal{D}_{X})|$. Further, for
$j\in[n(x)]$, let $X_{(j)}(x)$ denote the $j$th nearest neighbour in
$\\{X_{i}:i\in\mathcal{I}(x)\\}$ of $x$ in supremum norm, with ties broken by
retaining the original ordering of the indices, and let
$Y_{(1)}(x),\ldots,Y_{(n(x))}(x)$ denote the concomitant responses. Defining
$S_{k}\equiv S_{k}(x,\sigma,\tau,\mathcal{D})$ for $k\in[n(x)]$ as in (1), we
then set

$\displaystyle\hat{p}_{\sigma,\tau}(x)\equiv\hat{p}_{\sigma,\tau}(x,\mathcal{D}):=1\wedge\min_{k\in[n(x)]}5.2\exp\biggl{\\{}-\frac{(S_{k}\vee
0)^{2}}{2.0808k}+\frac{\log\log(2k)}{0.72}\biggr{\\}},$

whenever $n(x)>0$, and $\hat{p}_{\sigma,\tau}(x,\mathcal{D}):=1$ otherwise.

Lemma 1 below shows that $\hat{p}_{\sigma,\tau}(x,\mathcal{D})$ is indeed a
$p$-value for the null hypothesis $\eta(x)<\tau$. We now proceed to the issue
of FWER control in the multivariate setting, where we again condition on
$\mathcal{D}_{X}$. Recall that we are interested in testing the hypotheses
$H_{i}:\eta(X_{i})<\tau$ for $i\in[m]$ and a pre-specified $m\in[n]$. The fact
that $\preccurlyeq$ induces only a partial order on $\mathbb{R}^{d}$ when
$d>1$ means that there is no natural generalisation of the univariate fixed
sequence testing procedure. Instead, we structure the hypotheses in a directed
acyclic graph (DAG), with the edges in the graph representing logical
relationships between hypotheses; such an approach has been studied in the
literature to control both the FWER (meijer2015multiple) and the false
discovery rate (ramdas2019sequential)222In a different but related approach, a
graph structure can be used to encode a ranking of hypotheses beyond a strict
logical ordering (bretz2009graphical).. The following definitions will be
useful in the construction of an efficient multiple testing procedure.

######  Definition 2 (Induced DAGs and polyforests).

Let $\bm{z}=(z_{1},\ldots,z_{m})\in(\mathbb{R}^{d})^{m}$.

  1. (i)

The _induced DAG_
$\mathcal{G}(\bm{z})=\bigl{(}[m],\mathcal{E}(\bm{z})\bigr{)}$ is the graph
with nodes $[m]$ and edges

$\displaystyle\mathcal{E}(\bm{z}):=\bigl{\\{}(i_{0},i_{1})\in[m]^{2}:i_{0}$
$\displaystyle\neq i_{1}\text{ and }z_{i_{1}}\preccurlyeq z_{i_{0}}\text{, and
if }z_{i_{1}}\preccurlyeq z_{i_{2}}\preccurlyeq z_{i_{0}}\text{ then either }$
$\displaystyle z_{i_{2}}$ $\displaystyle=z_{i_{0}}\text{ and }i_{0}\leq
i_{2}\text{, or }z_{i_{2}}=z_{i_{1}}\text{ and }i_{2}\leq i_{1}\bigr{\\}}.$

  2. (ii)

The _induced polyforest_
$\mathcal{G}_{\mathrm{F}}(\bm{z})=\bigl{(}[m],\mathcal{E}_{\mathrm{F}}(\bm{z})\bigr{)}$
is the subgraph of $\mathcal{G}(\bm{z})$ with nodes $[m]$ and edges333Here,
$\operatorname*{sargmin}$ refers to the smallest element of the
$\operatorname*{argmin}$ set.

$\displaystyle\mathcal{E}_{\mathrm{F}}(\bm{z}):=\Bigl{\\{}(i_{0},i_{1})\in\mathcal{E}(\bm{z}):i_{0}=\operatorname*{sargmin}_{i:(i,i_{1})\in\mathcal{E}(\bm{z})}\|X_{i}-X_{i_{1}}\|_{\infty}\Bigr{\\}}.$

  3. (iii)

The _induced polyforest-weighted DAG_ is
$\mathcal{G}_{\mathrm{W}}(\bm{z}):=\bigl{(}[m],\mathcal{E}(\bm{z}),\bm{w}(\bm{z})\bigr{)}$,
where $\bm{w}(\bm{z})=(w_{e})_{e\in\mathcal{E}(\bm{z})}$ is given by
$w_{e}:=\mathbbm{1}_{\\{e\in\mathcal{E}_{\mathrm{F}}(\bm{z})\\}}$.

From the definition, we see that the induced polyforest-weighted DAG encodes
the complete information of both $\mathcal{G}(\bm{z})$ and
$\mathcal{G}_{\mathrm{F}}(\bm{z})$, as illustrated by Figure 2(a), where $d=2$
and each node represents the hypothesis corresponding to the observation at
its location.

######  Definition 3 (DAG testing procedure).

A _DAG testing procedure_ $\mathcal{R}$ is a function that takes as input a
significance level $\alpha\in(0,1]$, a weighted DAG $G=(I,E,\bm{w})$ and
$\bm{p}=(p_{i})_{i\in I}\in(0,1]^{I}$, and outputs a subset
$\mathcal{R}_{\alpha}(G,\bm{p})\subseteq I$.

The fixed sequence procedure presented for $d=1$ is a DAG testing procedure
since it only exploits the natural ordering information in $\mathcal{D}_{X}$,
though in that case we wrote the first argument of
$\mathcal{R}_{\alpha}^{\mathrm{FS}}$ as the set of nodes in the DAG rather
than the full DAG for simplicity. In arbitrary dimensions, the methods
proposed by bretz2009graphical, meijer2015multiple and ramdas2019sequential
are DAG testing procedures. While the meijer2015multiple procedure both
controls the FWER and accounts for logical relationships between the
hypotheses, theoretical and empirical power considerations lead us to propose
a new approach that can be regarded as a sparsified version of the
meijer2015multiple procedure or as an extension of the sequential rejection
procedures of bretz2009graphical.

In order to describe our proposed iterative DAG testing procedure
$\mathcal{R}^{\mathrm{ISS}}$, write $G:=\mathcal{G}(\mathcal{D}_{X,m})$ for
the induced DAG and $F:=\mathcal{G}_{\mathrm{F}}(\mathcal{D}_{X,m})$ for the
induced polyforest. We begin by splitting our $\alpha$-budget across the root
nodes, with each such node receiving budget proportional to its number of leaf
node descendants in $F$ (including the node itself if it is a leaf node). We
reject each root node hypothesis whose $p$-value is at most its
$\alpha$-budget, and whenever we do so, we also reject its ancestors in the
original $G$ (which does not inflate the Type I error, by the logical ordering
of the hypotheses). The rejected root nodes are then removed from $F$, and we
repeat the process iteratively, stopping when either we have rejected all
hypotheses, or if we fail to reject any additional hypotheses at a given
iteration. Formal pseudocode to compute $\mathcal{R}^{\mathrm{ISS}}$ is given
in Algorithm 1; see also Figure 2 for an illustration.

((a)) In the first iteration, no hypothesis has been rejected yet and only
root nodes are assigned positive $\alpha$-budget. Here, nodes $1,6$ and $7$
are current rejection candidates, and $1$ will be rejected, as $p_{1}=0.01\leq
0.0125$.

((b)) After rejection of node $1$ in the first step, we reallocate the
$\alpha$-budget, which allows us to reject node $7$.

((c)) Now that node $7$ has been rejected, its child $5$ receives
$\alpha$-budget sufficiently large for it to be rejected. Although $p_{6}$ is
quite large, $6$ is an ancestor of $5$ in the induced DAG and will hence also
be rejected.

((d)) None of the remaining three nodes, which happen to be the leaf nodes,
have a $p$-value smaller than their respective $\alpha$-budgets. Hence, no
further rejection is made and the procedure terminates. Nodes $1$, $5$, $6$
and $7$ have been rejected.

Figure 2: Illustration of Algorithm 1 with $\alpha=0.05$. Nodes are numbered
according to one potential reverse topological ordering of the induced
weighted DAG. The $p$-value for each hypothesis is given in round brackets.
Solid arrows represent edges with weight $1$ in the induced polyforest-
weighted DAG, whereas dashed arrows represent those with weight $0$. Each
iteration of the procedure corresponds to one panel. A filled circle indicates
that the hypothesis has been rejected in a previous step. If a node is
assigned positive $\alpha$-budget at the current iteration, then its (rounded)
budget is given in purple to the top left.

The DAG testing procedure $\mathcal{R}^{\mathrm{ISS}}$ allows us to define the
corresponding isotonic subgroup selection set

$\displaystyle\hat{A}^{\mathrm{ISS}}\equiv\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D}):=\bigl{\\{}x\in\mathbb{R}^{d}:\\!X_{i_{0}}\preccurlyeq
x\text{ for some
}i_{0}\in\mathcal{R}_{\alpha}^{\mathrm{ISS}}\bigl{(}\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m}),\bigl{(}\hat{p}_{\sigma,\tau}(X_{i},\mathcal{D})\bigr{)}_{i\in[m]}\bigr{)}\bigr{\\}}.$

Pseudocode for computing $\hat{A}^{\mathrm{ISS}}$ is given in Algorithm 2. In
Section 3 below, we establish that $\hat{A}^{\mathrm{ISS}}$ controls the Type
I error uniformly over appropriate distributional classes, and moreover has
optimal worst-case power up to poly-logarithmic factors.

Input:  $\alpha\in(0,1)$, polyforest-weighted DAG $(I,E,\bm{w})$,
$\bm{p}=(p_{i})_{i\in I}\in(0,1]^{I}$

$G\leftarrow(I,E)$ // $G$ gives the logical structure of the hypotheses

$F\leftarrow(I,\\{e\in E:w_{e}=1\\})$ // $F$ determines the allocation of the
$\alpha$-budget

$R_{0}\leftarrow\emptyset$

for  _$\ell\in[|I|]$_ do

$S_{\mathrm{L}}\leftarrow L(F)\setminus R_{\ell-1}$ // currently unrejected
$F$-leaf nodes

$S_{\mathrm{C}}\leftarrow\\{i\in I:i\notin
R_{\ell-1},\operatorname{\mathrm{pa}}_{F}(i)\subseteq R_{\ell-1}\\}$ //
current rejection candidates

$\alpha_{i}\leftarrow\mathbbm{1}_{\\{i\in
S_{\mathrm{C}}\\}}\cdot\bigl{|}\bigl{(}\\{i\\}\cup\operatorname{\mathrm{de}}_{F}(i)\bigr{)}\cap
S_{\mathrm{L}}\bigr{|}\cdot\alpha/|S_{\mathrm{L}}|$ for all $i\in I$

$I_{\ell}\leftarrow\\{i\in I:p_{i}\leq\alpha_{i}\\}$

if  _$I_{\ell}=\emptyset$_ then

$R_{|I|}\leftarrow R_{\ell-1}$ // will not make any further rejections

break

$R_{\ell}\leftarrow R_{\ell-1}\cup I_{\ell}\cup\bigcup_{i\in
I_{\ell}}\operatorname{\mathrm{an}}_{G}(i)$ // reject $I_{\ell}$ and its
ancestors in $G$

if  _$R_{\ell}=I$_ then

$R_{|I|}\leftarrow R_{\ell}$ // everything has been rejected

break

end for

Result: The set of rejected hypotheses
$\mathcal{R}_{\alpha}^{\mathrm{ISS}}\bigl{(}(I,E,\bm{w}),\bm{p}\bigr{)}:=R_{|I|}$

Algorithm 1 The DAG testing procedure $\mathcal{R}^{\mathrm{ISS}}$.

Input:
$\mathcal{D}=(X_{i},Y_{i})_{i\in[n]}\in(\mathbb{R}^{d}\times\mathbb{R})^{n}$,
$\tau\in\mathbb{R}$, $\alpha\in(0,1)$, $\sigma>0$, $m\in[n]$

$\mathcal{D}_{X,m}\leftarrow(X_{1},\ldots,X_{m})$ // subsample the first $m$
covariate points in $\mathcal{D}$

$p_{i}\leftarrow\hat{p}_{\sigma,\tau}(X_{i})$ for $i\in[m]$ // calculate
$p$-values as in Definition 1

$G\leftarrow\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m})$ // construct induced
polyforest-weighted DAG

$R\leftarrow\mathcal{R}^{\mathrm{ISS}}_{\alpha}\bigl{(}G,(p_{1},\ldots,p_{m})\bigr{)}$
// combine $p$-values via Algorithm 1

$\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\leftarrow\\{x\in\mathbb{R}^{d}:X_{i}\preccurlyeq
x\text{ for some }i\in R\\}$ // select upper hull of $(X_{i})_{i\in R}$

Result: The selected set
$\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})$.

Algorithm 2 The subgroup selection algorithm $\hat{A}^{\mathrm{ISS}}$.

##  3 Theory

###  3.1 Type I error control

We first introduce the class of distributions over which we prove the Type I
error control of $\hat{A}^{\mathrm{ISS}}$.

######  Definition 4.

Given $\sigma>0$, let $\mathcal{P}_{\mathrm{Mon},d}(\sigma)$ denote the class
of all distributions $P$ on $\mathbb{R}^{d}\times\mathbb{R}$ with increasing
regression function $\eta:\mathbb{R}^{d}\rightarrow\mathbb{R}$, and for which,
when $(X,Y)\sim P$, the conditional distribution of $Y-\eta(X)$ given $X$ is
sub-Gaussian with variance parameter $\sigma^{2}$.

Our Type I error control relies on showing first that
$\hat{p}_{\sigma,\tau}(x,\mathcal{D})$ is indeed a $p$-value for testing the
null hypothesis $\eta(x)<\tau$ when $P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)$
and then that the DAG testing procedure $\mathcal{R}^{\mathrm{ISS}}$ controls
the familywise error rate (FWER) in the sense defined in Definition 6 below.
The next lemma accomplishes the first of these tasks (in fact, it shows that
$\hat{p}_{\sigma,\tau}(x,\mathcal{D})$ is a $p$-value even conditional on
$\mathcal{D}_{X}$). We write $P^{n}$ for the $n$-fold product measure
corresponding to $P$.

######  Lemma 1.

Given any $x\in\mathbb{R}^{d}$, $\tau\in\mathbb{R}$, $\sigma>0$,
$P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)$ such that $\eta(x)<\tau$ and
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$, we
have
$\mathbb{P}_{P}\bigl{\\{}\hat{p}_{\sigma,\tau}(x,\mathcal{D})\leq\alpha|\mathcal{D}_{X}\bigr{\\}}\leq\alpha$
for all $\alpha\in(0,1)$.

We now direct our attention towards the DAG testing procedure
$\mathcal{R}^{\mathrm{ISS}}$. Here, it is convenient to introduce the
following terminology.

######  Definition 5.

Given a weighted, directed graph $G=(I,E,\bm{w})$, we say that a subset
$I_{0}\subseteq I$ is _$G$ -lower_ if whenever $i_{0}\in I_{0}$ we have
$\operatorname{\mathrm{de}}_{G}(i_{0})\subseteq I_{0}$. Conversely,
$I_{0}\subseteq I$ is called _$G$ -upper_ if $I\setminus I_{0}$ is $G$-lower.

Given a finite set $I$, a family of distributions $\mathcal{Q}$ on $(0,1]^{I}$
and a finite collection of null hypotheses $H_{i}\subseteq\mathcal{Q}$ for
$i\in I$, let $G_{0}:=(I,E_{0})$ with $E_{0}:=\\{(i_{0},i_{1})\in
I^{2}:H_{i_{0}}\subseteq H_{i_{1}}\\}$ be the directed graph that encodes all
logical relationships between hypotheses. Then for any $Q\in\mathcal{Q}$, the
true null index set $I_{0}(Q):=\\{i\in I:Q\in H_{i}\\}$ is necessarily a
$G_{0}$-lower set. Conversely, the index set of false null hypotheses must be
a $G_{0}$-upper set. We say that a polyforest-weighted DAG $(I,E,\bm{w})$ is
_$G_{0}$ -consistent_ if $E\subseteq E_{0}$. Multiple testing procedures that
reject hypotheses corresponding to a $G_{0}$-upper set are called _coherent_
(gabriel1969, p. 229), and by construction, $\mathcal{R}^{\mathrm{ISS}}$ is
indeed coherent when applied to a $G_{0}$-consistent polyforest-weighted DAG.

We are now in a position to formalise the concept of FWER control for DAG
testing procedures.

######  Definition 6.

A DAG testing procedure $\mathcal{R}$ _controls the FWER_ if given any finite
set $I$, a family of distributions $\mathcal{Q}$ on $(0,1]^{I}$, a collection
of random variables $\bm{p}=(p_{i})_{i\in I}$ taking values in $(0,1]^{I}$, as
well as hypotheses $H_{i}\subseteq\\{Q\in\mathcal{Q}:\mathbb{P}_{Q}(p_{i}\leq
t)\leq t,\forall t\in(0,1]\\}$ for $i\in I$ and any $G_{0}$-consistent
polyforest-weighted DAG $G^{\prime}=(I,E,\bm{w})$, we have
$\mathbb{P}_{Q}\bigl{(}\mathcal{R}_{\alpha}(G^{\prime},\bm{p})\cap
I_{0}(Q)\neq\emptyset\bigr{)}\leq\alpha$ for all $\alpha\in(0,1)$ and
$Q\in\mathcal{Q}$.

######  Lemma 2.

The DAG testing procedure $\mathcal{R}^{\mathrm{ISS}}$ defined by Algorithm 1
controls the FWER.

The strategy of the proof of Lemma 2 is based on ideas in the proof of
goeman2010sequential. Combining Lemmas 1 and 2 yields our Type I error
guarantee.

######  Theorem 3.

For any $d\in\mathbb{N}$, $n\in\mathbb{N}$, $m\in[n]$, $\alpha\in(0,1)$,
$\tau\in\mathbb{R}$, $\sigma>0$, and
$P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)$, along with
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$, we
have

$\mathbb{P}_{P}\bigl{(}\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\subseteq\mathcal{X}_{\tau}(\eta)\bigm{|}\mathcal{D}_{X}\bigr{)}\geq
1-\alpha.$

Let $\hat{\mathcal{A}}_{n}(\tau,\alpha,\mathcal{P})$ denote the family of
_data-dependent selection sets_ $\hat{A}$ (i.e. Borel measurable functions
from $(\mathbb{R}^{d}\times\mathbb{R})^{n}$ to the set of Borel subsets of
$\mathbb{R}^{d}$) that control the Type I error rate at level $\alpha\in(0,1)$
over the family $\mathcal{P}$ of distributions on
$\mathbb{R}^{d}\times\mathbb{R}$. In other words, we write
$\hat{A}\in\hat{\mathcal{A}}_{n}(\tau,\alpha,\mathcal{P})$ if

$\mathbb{P}_{P}\bigl{(}\hat{A}(\mathcal{D})\subseteq\mathcal{X}_{\tau}(\eta)\bigr{)}\geq
1-\alpha$ (2)

for all $P\in\mathcal{P}$ with $\mathcal{D}\sim P^{n}$. An immediate
consequence of Theorem 3 is that
$\hat{A}_{\sigma,\tau,\alpha,m}^{\mathrm{ISS}}\in\hat{\mathcal{A}}_{n}\bigl{(}\tau,\alpha,\mathcal{P}_{\mathrm{Mon},d}(\sigma)\bigr{)}$.
In fact, an inspection of the proof of Theorem 3 (see also Lemma 13) reveals
that $\hat{A}_{\sigma,\tau,\alpha,m}^{\mathrm{ISS}}$ controls the Type I error
over a larger class. Indeed, writing
$\mathcal{P}_{\mathrm{Upp},d}(\tau,\sigma)$ for the class of distributions of
pairs $(X,Y)$ such that the $\tau$-superlevel set of the regression function
$\eta:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is an upper set and, again, the
conditional distribution of $Y-\eta(X)$ given $X$ is sub-Gaussian with
variance parameter $\sigma^{2}$, it follows from the proof that
$\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}\in\hat{\mathcal{A}}_{n}\bigl{(}\tau,\alpha,\mathcal{P}_{\mathrm{Upp},d}(\tau,\sigma)\bigr{)}$.
We have
$\mathcal{P}_{\mathrm{Mon},d}(\sigma)=\bigcap_{\tau^{\prime}\in\mathbb{R}}\mathcal{P}_{\mathrm{Upp},d}(\tau^{\prime},\sigma)$,
but the regression functions of distributions in
$\mathcal{P}_{\mathrm{Upp},d}(\tau,\sigma)$ for a fixed $\tau\in\mathbb{R}$
may deviate from monotonicity as long as the $\tau$-superlevel set remains an
upper set. In this sense, our procedure
$\hat{A}_{\sigma,\tau,\alpha,m}^{\mathrm{ISS}}$ is robust to misspecification
of the monotonicity of the regression function.

###  3.2 Power

Classical results on Gaussian testing reveal that merely asking for
$P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)$ is insufficient to be able to
provide non-trivial uniform power guarantees for data-dependent selection sets
with Type I error control (see Proposition 14 in Appendix 7.2 for details).
The main issue here is that the marginal distribution $\mu$ may place a lot of
mass in regions where $\eta$ is only slightly above $\tau$, and these regions
will be hard for a data-dependent selection set to include if it has Type I
error control. In this section, therefore, we introduce a margin condition
that controls the $\mu$-measure of these difficult regions.

######  Definition 7.

For $d\in\mathbb{N}$, $\tau\in\mathbb{R}$, $\beta>0$ and $\nu>0$, let
$\mathcal{P}_{\mathrm{Mar},d}(\tau,\beta,\nu)$ denote the class of
distributions $P$ on $\mathbb{R}^{d}\times\mathbb{R}$ for which the marginal
$\mu$ on $\mathbb{R}^{d}$ and the regression function
$\eta:\mathbb{R}^{d}\rightarrow\mathbb{R}$ satisfy
$\mu\bigl{(}\eta^{-1}([\tau,\tau+\nu\xi^{\beta}])\bigr{)}\leq\xi$ for all
$\xi\in(0,1]$.

######  Example 1.

Let $d=1$ and let $P\in\mathcal{P}_{\mathrm{Mon},1}(\sigma)$ have uniform
marginal distribution $\mu$ on $[0,1]$ and regression function $\eta$. We then
have
$P\in\mathcal{P}_{\mathrm{Mon},1}(\sigma)\cap\mathcal{P}_{\mathrm{Mar},1}(\tau,\beta,\nu)$
if $\eta(x+\xi)\geq\tau+\nu\xi^{\beta}$ for all $\xi\in(0,1]$ and
$x\in\mathcal{X}_{\tau}(\eta)$.

We now divide our power analysis for $\hat{A}^{\mathrm{ISS}}$ into univariate
and multivariate cases, since the natural total order on $\mathbb{R}$ means
that our results simplify a little when $d=1$. Theorem 4 below provides high-
probability and expectation upper bounds on the _regret_
$\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}\bigr{)}$
for
$P\in\mathcal{P}_{\mathrm{Mon},1}(\sigma)\cap\mathcal{P}_{\mathrm{Mar},1}(\tau,\beta,\nu)$.

######  Theorem 4.

Let $\sigma,\beta,\nu>0$ and $\alpha\in(0,1)$. There exists a universal
constant $C>0$ such that for any distribution
$P\in\mathcal{P}_{\mathrm{Mon},1}(\sigma)\cap\mathcal{P}_{\mathrm{Mar},1}(\tau,\beta,\nu)$
and $\delta\in(0,1)$, we have

$\displaystyle\mathbb{P}_{P}\biggl{[}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,n}(\mathcal{D})\bigr{)}>1\wedge
C\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\nu^{2}}\log_{+}\Bigl{(}\frac{\log_{+}n}{\alpha\wedge\delta}\Bigr{)}\biggr{)}^{1/(2\beta+1)}+\frac{\log_{+}(1/\delta)}{n}\biggr{\\}}\biggr{]}\leq\delta,$

and

$\mathbb{E}_{P}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,n}(\mathcal{D})\bigr{)}\bigr{\\}}\leq
1\wedge
C\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\nu^{2}}\log_{+}\Bigl{(}\frac{\log_{+}n}{\alpha}\Bigr{)}\biggr{)}^{1/(2\beta+1)}+\frac{1}{n}\biggr{\\}}.$

From Theorem 4, we see that the regret of $\hat{A}^{\mathrm{ISS}}$ decomposes
as a sum of two terms: the first reflects the error incurred in determining
whether each data point belongs to $\mathcal{X}_{\tau}(\eta)$, while the
second represents the error arising from the uncertainty of whether or not
regions between the data points belong to this superlevel set. The combination
of Theorem 4 with Proposition 6 below and Theorem 9 in Section 3.3 reveals
that the dependence of our bound on the parameters $n$, $\alpha$, $\sigma$,
$\beta$ and $\nu$ is optimal up to an iterated logarithmic factor in $n$.

In the proof of Theorem 4, we exploit the fact that $\mathcal{D}_{X}$ has a
total order in the univariate case, so the corresponding induced polyforest-
weighted DAG forms a chain in which each edge has weight $1$. Since in our
algorithm, the $p$-values $\hat{p}_{\sigma,\tau}$ for coinciding hypotheses
are equal, $\mathcal{R}^{\mathrm{ISS}}$ is equivalent to the fixed sequence
procedure $\mathcal{R}^{\mathrm{FS}}$.

Turning now to the multivariate case, we begin with a negative result, which
reveals that we can find distributions in our class for which no data-
dependent selection set with Type I error control performs better than the
trivial procedure that ignores the data, and selects the entire domain with
probability $\alpha$ and the empty set otherwise.

######  Proposition 5.

Let $d\geq 2$, $\tau\in\mathbb{R}$, $\sigma,\beta,\nu>0$ and $\alpha\in(0,1)$.
Then, writing
$\mathcal{P}^{\prime}:=\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Mar},d}(\tau,\beta,\nu)$,
we have for any $n\in\mathbb{N}$ that

$\sup_{P\in\mathcal{P}^{\prime}}\inf_{\hat{A}\in\hat{\mathcal{A}}_{n}(\tau,\alpha,\mathcal{P}^{\prime})}\mathbb{E}_{P}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}\geq
1-\alpha.$

An interesting feature of Proposition 5 is the ordering of the supremum over
distributions in our class and the infimum over data-dependent selection sets.
Usually, with minimax lower bounds, these would appear in the opposite order,
but here we are able to establish the stronger conclusion, because it is the
same subfamily of
$\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Mar},d}(\tau,\beta,\nu)$
that causes the poor performance of any data-dependent selection set with Type
I error control. In fact, by examining the proof, we see that the issue is
caused by constructing a marginal distribution $\mu$ that concentrates its
mass around a large antichain444Recall that an _antichain_ in $\mathbb{R}^{d}$
is a set $\mathbb{W}$ such that we do not have $x\preccurlyeq x^{\prime}$ for
any $x,x^{\prime}\in\mathbb{W}$. It is the fact that antichains of arbitrary
size exist in $[0,1]^{d}$ when $d\geq 2$ that is essential to this
construction; when $d=1$, any antichain must be a singleton. in $[0,1]^{d}$,
which constitutes the boundary of $\mathcal{X}_{\tau}(\eta)$. This motivates
us to regulate the extent to which this is allowed to happen.

######  Definition 8.

Given $d\in\mathbb{N}$, $\tau\in\mathbb{R}$, $\theta>1$, $\gamma,\lambda>0$,
we let $\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)$ denote the
class of all distributions $P$ on $\mathbb{R}^{d}\times\mathbb{R}$ with
marginal $\mu$ on $\mathbb{R}^{d}$ and associated regression function $\eta$
such that

  1. (i)

$\theta^{-1}\cdot
r^{d}\leq\mu\bigl{(}{B}_{\infty}(x,r)\bigr{)}\leq\theta\cdot(2r)^{d}$ for all
$x\in\mathcal{X}_{\tau}(\eta)\cap\mathrm{supp}(\mu)$ and $r\in(0,1]$;

  2. (ii)

${B}_{\infty}(x,r)\cap\mathcal{X}_{\tau+\lambda\cdot
r^{\gamma}}(\eta)\neq\emptyset$ for all
$x\in\mathcal{X}_{\tau}(\eta)\cap\mathrm{supp}(\mu)$ and $r\in(0,1]$.

For distributions in the $\mathcal{P}_{\mathrm{Mon},d}(\sigma)$ class,
Definition 8 represents a slight strengthening of the margin condition used in
our univariate analysis, as made precise by Proposition 6 below.

######  Proposition 6.

Let $d\in\mathbb{N}$, $\tau\in\mathbb{R}$, $\sigma,\gamma,\lambda>0$ and
$\theta>1$. There exists $C\geq 1$, depending only on $(d,\theta)$, such that

$\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)\subseteq\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Mar},d}(\tau,\gamma,\lambda/C^{\gamma}).$

Thus, $(\gamma,\lambda)$ in the class
$\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)$ play a similar but
not identical role to $(\beta,\nu)$ in
$\mathcal{P}_{\mathrm{Mar},d}(\tau,\beta,\nu)$, in controlling the way in
which the regression function is required to grow as we move away from the
boundary of the $\tau$-superlevel set. We are now in a position to state our
main result concerning the power of our proposed procedure; the result holds
in all dimensions but our primary interest here is in the multivariate case.

######  Theorem 7.

Let $d\in\mathbb{N}$, $\tau\in\mathbb{R}$, $\sigma,\gamma,\lambda>0$ and
$\theta>1$. There exists $C\geq 1$, depending only on $(d,\theta)$, such that
for any
$P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)$,
$n\in\mathbb{N}$, $\alpha\in(0,1)$ and $\delta\in(0,1)$, along with
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$, we
have for $m\in[n]$ that

$\displaystyle\mathbb{P}_{P}\biggl{[}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\bigr{)}>1\wedge
C\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha\wedge\delta}\Bigr{)}\biggr{)}^{\frac{1}{2\gamma+d}}+\biggl{(}\frac{\log_{+}(m/\delta)}{m}\biggr{)}^{\frac{1}{d}}\biggr{\\}}\biggr{]}\leq\delta,$

and

$\displaystyle\mathbb{E}_{P}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\bigr{)}\bigr{\\}}$
$\displaystyle\leq 1\wedge
C\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha}\Bigr{)}\biggr{)}^{1/(2\gamma+d)}+\biggl{(}\frac{\log_{+}m}{m}\biggr{)}^{1/d}\biggr{\\}}.$

The terms in the bound in Theorem 7 are similar to those in Theorem 4, and
exhibit the trade-off in the choice of $m$: if we choose it to be small, then
there are fewer data points in our subsample that belong to
$\mathcal{X}_{\tau}(\eta)$ and moreover these are less likely to be excluded
from $\hat{A}^{\mathrm{ISS}}$ because they are typically assigned greater
budget in our DAG testing procedure. On the other hand, we incur a greater
loss in excluding regions between data points in our subsample that belong to
this superlevel set. By specialising Theorem 7 via a particular choice of $m$,
we obtain the following almost immediate corollary. It is this upper bound to
which we will compare our minimax lower bound in Theorem 9.

######  Corollary 8.

Under the conditions of Theorem 7, if we take $m_{0}:=n\wedge\lceil
n\lambda^{2}/\sigma^{2}\rceil$, then

$\displaystyle\mathbb{E}_{P}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m_{0}}(\mathcal{D})\bigr{)}\bigr{\\}}$
$\displaystyle\leq 1\wedge
4C\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{n\lambda^{2}\log_{+}n}{\sigma^{2}\alpha}\Bigr{)}\biggr{)}^{1/(2\gamma+d)}+\biggl{(}\frac{\log_{+}n}{n}\biggr{)}^{1/d}\biggr{\\}}.$

As is apparent from the proof of Corollary 8, a high-probability bound
analogous to that in Theorem 7 also holds, but this is omitted for brevity.
Theorem 7 and Corollary 8 suggest a curse of dimensionality effect in isotonic
subgroup selection; this is confirmed as an essential price to pay by Theorem
9 below.

###  3.3 Main lower bound

In order to discuss the optimality of our data-dependent selection set
$\hat{A}^{\mathrm{ISS}}$, we present a minimax lower bound that provides a
benchmark on the regret that is achievable by any data-dependent selection set
with Type I error control.

######  Theorem 9.

Let $d\in\mathbb{N}$, $\tau\in\mathbb{R}$, $\sigma,\gamma,\lambda>0$ and
$\theta>1$. Then, writing
$\mathcal{P}^{\prime}:=\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)$,
there exists $c\in(0,1)$, depending only on $(d,\gamma)$, such that for any
$n\in\mathbb{N}$ and $\alpha\in(0,1/4]$, we have

$\inf_{\hat{A}\in\hat{\mathcal{A}}_{n}(\tau,\alpha,\mathcal{P}^{\prime})}\sup_{P\in\mathcal{P}^{\prime}}\mathbb{E}_{P}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}\geq
c\biggl{[}1\wedge\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{1}{5\alpha}\Bigr{)}\biggr{)}^{1/(2\gamma+d)}+\frac{1}{n^{1/d}}\biggr{\\}}\biggr{]}.$
(3)

By comparing the rate in Theorem 9 with those in Theorem 4 and Corollary 8, we
see that $\hat{A}^{\mathrm{ISS}}$ attains the optimal regret among procedures
with Type I error control, up to poly-logarithmic factors. In particular, up
to such factors, these results reveal the optimal dependence of the regret not
only on $n$, but also on $\sigma$, $\lambda$ and $\alpha$. It is interesting
to note that Theorem 9 incorporates procedures that are only required to
control Type I error over
$\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)$,
whereas $\hat{A}^{\mathrm{ISS}}$ has Type I error control over the larger
class $\mathcal{P}_{\mathrm{Mon},d}(\sigma)$, by Theorem 3. Thus,
$\hat{A}^{\mathrm{ISS}}$ suffers no deterioration in performance for this
stronger validity guarantee, at least up to poly-logarithmic factors.

The proof of Theorem 9 combines two minimax lower bounds, given in
Propositions 19 and 21, which provide the different terms in the sum in (3).
The main idea in both cases is to divide $[0,1]^{d}$ into a hypercube lattice,
and to construct pairs of distributions where either the regression function
(Proposition 19) or the marginal distribution (Proposition 21) only differ in
a single hypercube among a collection whose centres lie on a large antichain
in $\mathbb{R}^{d}$. Observations outside these critical hypercubes therefore
do not help to distinguish between the distributions in a pair, so by choosing
the number of hypercubes and the difference in the regression function levels
appropriately, we obtain a non-trivial probability of failing to include them
in a data-dependent selection set. Our formal constructions, together with
illustrations, are given in Section 7.3.

##  4 Extensions

###  4.1 Choice of $p$-value construction

Recall that in our isotonic subgroup selection procedure
$\hat{A}^{\mathrm{ISS}}$, we propose a $p$-value based on a martingale test in
combination with a _finite law of the iterated logarithm (LIL) bound_ (Lemma
32 _(a)_). The following definition gives an alternative $p$-value
construction that uses a different bound and includes a hyperparameter
$\rho>0$.

######  Definition 9.

In the setting of Definition 1, for $\rho>0$, we define

$\displaystyle\tilde{p}^{\rho}_{\sigma,\tau}(x)\equiv\tilde{p}^{\rho}_{\sigma,\tau}(x,\mathcal{D}):=1\wedge\min_{k\in[n(x)]}\sqrt{\frac{k+\rho}{4\rho}}\biggl{\\{}\exp\biggl{(}\frac{(S_{k}\vee
0)^{2}}{2(k+\rho)}\biggr{)}-1\biggr{\\}}^{-1}$

whenever $n(x)>0$, and $\tilde{p}^{\rho}_{\sigma,\tau}(x,\mathcal{D}):=1$
otherwise.

By Lemma 32 _(b)_ , which is due to howard2021uniform, in combination with the
proof technique of Lemma 1, $\tilde{p}^{\rho}_{\sigma,\tau}(x)$ is indeed a
$p$-value for the null hypothesis $\eta(x)<\tau$ (even conditional on
$\mathcal{D}_{X}$). It follows that if we modify our procedure to use these
$p$-values instead of those in Definition 1, then the Type I error guarantee
in Theorem 3 is unaffected. The objective function being minimised over
$k\in[n(x)]$ is a little smaller for the original $p$-value definition when
$k$ is sufficiently large, and this therefore leads to a stronger power bound
in Theorem 7. Nevertheless, for appropriate values of $\rho>0$, Definition 9
may yield a slightly smaller objective for small and moderate values of $k$,
and hence may be preferable in practice. Based on some preliminary
simulations, we found that the power of our approach varied very little over
choices of $\rho\in(0,1]$, and that $\rho=1/2$ was a robust choice that we
used throughout our experiments in Section 5 and recommend for practical use.

###  4.2 Alternative distributional assumptions

In this subsection, we introduce three variants of $\hat{A}^{\mathrm{ISS}}$,
each of which is able to control Type I error over appropriate classes without
knowledge of any nuisance parameter and without the need for sample splitting.
In each case, we retain the same multiple testing component
$\mathcal{R}^{\mathrm{ISS}}$ to our procedure, but construct the $p$-values in
different ways. Power results analogous to Theorem 7 also hold for these
versions of $\hat{A}^{\mathrm{ISS}}$, but are omitted for brevity.

####  4.2.1 Gaussian noise with unknown variance

Since Algorithm 2 takes the sub-Gaussian variance parameter $\sigma^{2}$ as an
input, we present here an adaptive approach for a Gaussian error setting. More
precisely, for $\sigma>0$, let $\mathcal{P}_{\mathrm{N},d}(\sigma)$ denote the
subset of $\mathcal{P}_{\mathrm{Mon},d}(\sigma)$ with
$Y-\eta(X)|X\sim\mathcal{N}(0,\sigma^{2})$.

######  Definition 10.

In the setting of Definition 1, let
$\hat{\sigma}^{2}_{0,k}:=k^{-1}\sum_{j=1}^{k}\bigl{(}Y_{(j)}(x)-\tau\bigr{)}_{+}^{2}$
and $\bar{Y}_{1,k}:=k^{-1}\sum_{j=1}^{k}Y_{(j)}(x)$ for $k\in[n(x)]$ and
$\hat{\sigma}^{2}_{1,k}:=k^{-1}\sum_{j=1}^{k}\bigl{(}Y_{(j)}(x)-\bar{Y}_{1,k}\bigr{)}^{2}$
for $k\in\\{2,\ldots,n(x)\\}$. Moreover, we denote $\bar{Y}_{1,0}:=0$, and
$\hat{\sigma}^{2}_{1,k}:=1$ for $k\in\\{0,1\\}$. For $k\in[n(x)]$, define

$\bar{p}^{k}_{\tau}(x)\equiv\bar{p}^{k}_{\tau}(x,\mathcal{D}):=\frac{1}{\hat{\sigma}^{k}_{0,k}e^{k/2}}\cdot\prod_{j=1}^{k}\hat{\sigma}_{1,j-1}\exp\biggl{\\{}\frac{\bigl{(}Y_{(j)}(x)-\bar{Y}_{1,j-1}\bigr{)}^{2}}{2\hat{\sigma}^{2}_{1,j-1}}\biggr{\\}},$

where for definiteness $\bar{p}^{k}_{\tau}(x):=1$ if $\hat{\sigma}_{0,k}=0$,
and
$\bar{p}_{\tau}(x)\equiv\bar{p}_{\tau}(x,\mathcal{D}):=1\wedge\min_{k\in[n(x)]}\bar{p}^{k}_{\tau}(x)$.

The idea here is that $\bar{p}^{k}_{\tau}(x)$ exploits the sequential
likelihood ratio test principle developed by wasserman2020universal, applied
to a notion of a $t$-test for a stream of independent normal random variables
with varying means. In particular, $\hat{\sigma}_{0,k}^{2}$ and
$\hat{\sigma}_{1,k}^{2}$ are maximum likelihood estimators of $\sigma^{2}$
under the null hypothesis that
$\max_{j\in[k]}\eta\bigl{(}X_{(j)}(x)\bigr{)}<\tau$ and without this
constraint respectively. The next lemma is analogous to Lemma 1 and guarantees
that $\bar{p}_{\tau}(x)$ is a $p$-value.

######  Lemma 10.

Let $x\in\mathbb{R}^{d}$, $\tau\in[0,1)$,
$P\in\cup_{\sigma\in(0,\infty)}\mathcal{P}_{\mathrm{N},d}(\sigma)$ with
$\eta(x)<\tau$ and
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$.
Then
$\mathbb{P}_{P}\bigl{\\{}\bar{p}_{\tau}(x,\mathcal{D})\leq\alpha|\mathcal{D}_{X}\bigr{\\}}\leq\alpha$
for all $\alpha\in(0,1)$.

It is worth highlighting that the proof of Lemma 10 relies on the fact that
$\\{x\in\mathbb{R}^{d}:\eta(x)<\tau\\}$ is a lower set, but otherwise does not
use the monotonicity of $\eta$. From this, we can deduce that an analogous
robustness to misspecification holds to that presented at the end of Section
3.1.

####  4.2.2 Classification

Our second variant is tailored to the case of bounded responses, which in
particular includes classification settings. Suppose that $(X,Y)\sim P$ for
some distribution $P$ on $\mathbb{R}^{d}\times[0,1]$ with increasing
regression function $\eta$ on $\mathbb{R}^{d}$. By Hoeffding’s lemma, the sub-
Gaussianity condition of Definition 4 is satisfied with $\sigma=1/2$, so that
$\hat{A}^{\mathrm{ISS}}$ may be used to control the Type I error over
$\mathcal{P}_{\mathrm{Mon},d}(1/2)$. However, in this context, it suffices to
control the Type I error over the subclass $\mathcal{P}_{\mathrm{Bdd},d}$ of
$\mathcal{P}_{\mathrm{Mon},d}(1/2)$ consisting of distributions $P$ on
$\mathbb{R}^{d}\times[0,1]$ with increasing regression function. In such a
setting, we may combine our procedure with the following modified $p$-value
construction. Recall that for $z\in(0,1)$ and $a,b>0$, the _incomplete beta
function_ is defined by
$\mathrm{B}(z;a,b):=\int_{0}^{z}t^{a-1}(1-t)^{b-1}\,dt$.

######  Definition 11.

In the setting of Definition 1, let
$\check{S}_{k}\equiv\check{S}_{k}(x,\mathcal{D}):=\sum_{j=1}^{k}Y_{(j)}(x)$
and define

$\displaystyle\check{p}_{\tau}(x)\equiv\check{p}_{\tau}(x,\mathcal{D}):=1\wedge\min_{k\in[n(x)]}\frac{\tau^{\check{S}_{k}}(1-\tau)^{n-\check{S}_{k}+1}}{\mathrm{B}(1-\tau;n-\check{S}_{k}+1,\check{S}_{k}+1)}.$

The following lemma confirms that this indeed defines a $p$-value (even
conditional on $\mathcal{D}_{X}$). Its proof proceeds via a one-sided version
of the time-uniform confidence sequence construction of
robbins1970statistical, which is itself based on earlier work by
ville1939etude and wald1947sequential.

######  Lemma 11.

Let $x\in\mathbb{R}^{d}$, $\tau\in[0,1)$, $P\in\mathcal{P}_{\mathrm{Bdd},d}$
with $\eta(x)<\tau$ and
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$.
Then
$\mathbb{P}_{P}\bigl{\\{}\check{p}_{\tau}(x,\mathcal{D})\leq\alpha|\mathcal{D}_{X}\bigr{\\}}\leq\alpha$
for all $\alpha\in(0,1)$.

As a consequence of Lemma 11, combining $\hat{A}^{\mathrm{ISS}}$ with the
$p$-values $\check{p}_{\tau}$ still controls the Type I error over
$\mathcal{P}_{\mathrm{Bdd},d}$. In a similar spirit to the discussion at the
end of Section 3.1, both this conclusion and Lemma 11 hold over the even
larger class
$\mathcal{P}_{\mathrm{BddUpp},d}(\tau)\supseteq\mathcal{P}_{\mathrm{Bdd},d}$
of distributions $P$ on $\mathbb{R}^{d}\times[0,1]$ with regression function
$\eta$ such that $\mathcal{X}_{\tau}(\eta)$ is an upper set (see Lemma 23).

####  4.2.3 Increasing conditional quantiles

Finally in this subsection, we present an alternative assumption on the
conditional response distribution that motivates a version of
$\hat{A}^{\mathrm{ISS}}$ that is robust to heavy tails.

######  Definition 12.

Given $\theta\in(0,1)$, a distribution $P$ on $\mathbb{R}^{d}\times\mathbb{R}$
and $(X,Y)\sim P$, let $\zeta_{\theta}:\mathbb{R}^{d}\rightarrow\mathbb{R}$
denote the conditional $\theta$-quantile given by
$\zeta_{\theta}(x):=\inf\\{y\in\mathbb{R}:\mathbb{P}_{P}\bigl{(}Y\leq
y|X=x\bigr{)}\geq\theta\\}$ for $x\in\mathbb{R}^{d}$. Now let
$\mathcal{P}_{\mathrm{Q},d}(\theta)$ denote the class of all such
distributions $P$ for which $\zeta_{\theta}$ is increasing.

######  Lemma 12.

Given $\alpha\in(0,1)$, $\theta\in(0,1)$, $\tau\in\mathbb{R}$,
$P\in\mathcal{P}_{\mathrm{Q},d}(\theta)$,
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$ and
writing
$\mathcal{D}^{\tau}=\bigl{(}(X_{1},\mathbbm{1}_{\\{Y_{1}>\tau\\}}),\ldots,(X_{n},\mathbbm{1}_{\\{Y_{n}>\tau\\}})\bigr{)}$,
we have whenever $x\notin\mathcal{X}_{\tau}(\zeta_{\theta})$ that
$\mathbb{P}_{P}\bigl{\\{}\hat{p}_{1/2,1-\theta}(x,\mathcal{D}^{\tau})\leq\alpha|\mathcal{D}_{X}\bigr{\\}}\leq\alpha$
and
$\mathbb{P}_{P}\bigl{\\{}\check{p}_{1-\theta}(x,\mathcal{D}^{\tau})\leq\alpha|\mathcal{D}_{X}\bigr{\\}}\leq\alpha$
for all $\alpha\in(0,1)$.

In particular, if $\eta$ is increasing and the conditional distribution of
$Y-\eta(X)$ given $X$ is symmetric about zero, then the distribution of
$(X,Y)$ belongs to $\mathcal{P}_{\mathrm{Q},d}(1/2)$. As such, the
modification of $\hat{A}^{\mathrm{ISS}}$ with the $p$-values
$\check{p}_{1/2}(x,\mathcal{D}^{\tau})$ in place of
$\hat{p}_{\sigma,\tau}(x,\mathcal{D})$ controls the Type I error at the
nominal level.

###  4.3 Application to heterogeneous treatment effects

We now describe how our proposed procedure can be used to identify subsets of
the covariate domain with high treatment effects in randomised controlled
trials. As a model for such a setting, we assume that we observe independent
copies $(X_{1},T_{1},\tilde{Y}_{1}),\ldots,(X_{n},T_{n},\tilde{Y}_{n})$ of the
triple $(X,T,\tilde{Y})$, where $X$ is the covariate vector, $T$ takes values
in $\\{0,1\\}$ and encodes the assignment to one of two treatment arms, and
$\tilde{Y}$ gives the corresponding response. For $\ell\in\\{0,1\\}$, denote
by $\tilde{P}^{\ell}$ the conditional distribution of $(X,\tilde{Y})$ given
that $T=\ell$ and define corresponding regression functions
$\tilde{\eta}^{\ell}$ by
$\tilde{\eta}^{\ell}(x):=\mathbb{E}(\tilde{Y}|X=x,T=\ell)$ for
$x\in\mathbb{R}^{d}$. We are interested in identifying the $\tau$-superlevel
set of the _heterogeneous treatment effect_ $\eta$, where
$\eta(x):=\tilde{\eta}^{1}(x)-\tilde{\eta}^{0}(x)$ for $x\in\mathbb{R}^{d}$.
To this end, observe that writing $\pi(x):=\mathbb{P}(T=1|X=x)$ for the
_propensity score_ , and considering the _inverse propensity weighted
response_

$\displaystyle
Y:=\frac{T-\pi(X)}{\pi(X)\bigl{(}1-\pi(X)\bigr{)}}\cdot\tilde{Y},$ (4)

we have $\mathbb{E}(Y|X=x)=\eta(x)$ for all $x\in\mathbb{R}^{d}$. Hence,
writing $P$ for the distribution of $(X,Y)$ and with
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$,
where $Y_{1},\ldots,Y_{n}$ are the inverse propensity weighted responses
obtained from
$(X_{1},T_{1},\tilde{Y}_{1}),\ldots,(X_{n},T_{n},\tilde{Y}_{n})$, we have for
any $\alpha\in(0,1)$ and any $m\in[n]$ that
$\mathbb{P}_{P}\bigl{(}\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\subseteq\mathcal{X}_{\tau}(\eta)\bigr{)}\geq
1-\alpha$ whenever $P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)$, by Theorem 3.

####  4.3.1 Conditional treatment ranking

Under assumptions that are in spirit similar to those in Section 4.2.3, we can
use $\hat{A}^{\mathrm{ISS}}$ to establish non-inferiority of a treatment on a
subgroup. Suppose that for $x\in\mathbb{R}^{d}$, $y\in\mathbb{R}$ and
$\ell\in\\{0,1\\}$, we have
$\mathbb{P}\bigl{(}\tilde{Y}-\tilde{\eta}^{\ell}(x)\leq
y|X=x,T=\ell\bigr{)}=F(y)$ for some continuous distribution function $F$ with
the symmetry property $F(t)=1-F(-t)$ for all $t\in\mathbb{R}$. In particular,
this includes the case where $\eta$ is increasing and we have homoscedastic
Gaussian errors with unknown variance. Let $Y$ be as in (4) and observe that
whenever $\pi(x)=1/2$,

$\displaystyle\mathbb{P}(Y\geq 0\mid X=x)$
$\displaystyle=\frac{1}{2}\mathbb{P}\bigl{(}Y\geq 0\mid
T=1,X=x\bigr{)}+\frac{1}{2}\mathbb{P}\bigl{(}Y\geq 0\mid T=0,X=x\bigr{)}$
$\displaystyle=\frac{1}{2}\mathbb{P}\bigl{(}\tilde{Y}\geq 0\mid
T=1,X=x\bigr{)}+\frac{1}{2}\mathbb{P}\bigl{(}\tilde{Y}\leq 0\mid
T=0,X=x\bigr{)}$
$\displaystyle=\frac{1}{2}\bigl{\\{}1-F\bigl{(}-\tilde{\eta}^{1}(x)\bigr{)}\bigr{\\}}+\frac{1}{2}F\bigl{(}-\tilde{\eta}^{0}(x)\bigr{)}$
$\displaystyle=\frac{1}{2}F\bigl{(}\tilde{\eta}^{1}(x)\bigr{)}+\frac{1}{2}F\bigl{(}-\tilde{\eta}^{0}(x)\bigr{)}.$

Writing $Y^{*}:=\mathbbm{1}_{\\{Y\geq 0\\}}$ and
$\eta^{*}(x):=\mathbb{E}(Y^{*}|X=x)=\mathbb{P}(Y\geq 0|X=x)$ for
$x\in\mathbb{R}^{d}$, we have $\eta^{*}(x)\geq 1/2$ if and only if
$\eta(x)=\tilde{\eta}^{1}(x)-\tilde{\eta}^{0}(x)\geq 0$, so
$\mathcal{X}_{1/2}(\eta^{*})=\mathcal{X}_{0}(\eta)$. Moreover, when $\eta$ is
increasing on $\mathbb{R}^{d}$, the distribution of $(X,Y^{*})$ belongs to
$\mathcal{P}_{\mathrm{BddUpp},d}(1/2)$. Hence, in order to estimate
$\mathcal{X}_{0}(\eta)$, we may use $\hat{A}^{\mathrm{ISS}}$ with either
$\hat{p}_{1/2,1/2}$ or $\check{p}_{1/2}$ and retain Type I error control (see
the discussions at the end of Section 3.1 and 4.2.2 respectively). An
application of this procedure is presented in Section 6.1.2.

##  5 Simulations

The aim of this section is to explore the empirical performance of
$\hat{A}^{\mathrm{ISS}}$ in a wide range of settings. Throughout, we took
independent pairs $(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})$, where
$X_{1},\ldots,X_{n}\sim\mathrm{Unif}\bigl{(}[0,1]^{d}\bigr{)}=:\mu$ with
$d\in\\{2,3,4\\}$ and $n\in\\{500,1000,2000,5000\\}$. Rescaled versions of the
six functions $f$ in Table 1 serve as our main regression functions; see
Appendix 8 for eight further examples. More specifically, we let
$\eta(x):=\\{f(x)-f(0)\\}/\\{f(\bm{1}_{d})-f(0)\\}$ for each choice of $f$, as
illustrated in Figure 3. Further, we let $Y_{i}|X_{i}\sim
N\bigl{(}\eta(X_{i}),\sigma^{2}\bigr{)}$ for $i\in[n]$ with $\sigma=1/4$ when
$d=2$, $\sigma=1/16$ when $d=3$ and $\sigma=1/64$ when $d=4$. We set
$\alpha=0.05$ and the thresholds $\tau\equiv\tau(\eta)$ were chosen such that
$\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\bigr{)}=1/2$; see Table 1. Finally, in
this table we also provide

$\gamma(P):=\inf\biggl{\\{}\gamma>0:P\in\bigcup_{\lambda>0}\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)\biggr{\\}}$

for the distribution $P$ associated with each choice of $\mu$ and $\eta$.
Since for $\gamma,\gamma^{\prime}>0$ and $\lambda,\lambda^{\prime}>0$ such
that $\gamma\leq\gamma^{\prime}$ and $\lambda\geq\lambda^{\prime}$, we have
$\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)\subseteq\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma^{\prime},\lambda^{\prime})$,
this is a natural choice to illustrate the effect of the exponent in
Definition 8 _(ii)_ on the rate of convergence.

Label | Function $f$ | $\tau$ | $\gamma(P)$
---|---|---|---
(a) | $\sum_{j=1}^{d}x^{(j)}$ | $1/2$ | $1$
(b) | $\max_{1\leq j\leq d}x^{(j)}$ | $1/2^{1/d}$ | $1$
(c) | $\min_{1\leq j\leq d}x^{(j)}$ | $1-1/2^{1/d}$ | $1$
(d) | $\mathbbm{1}_{(0.5,1]}\bigl{(}x^{(1)}\bigr{)}$ | $1/2$ | $0$
(e) | $\sum_{j=1}^{d}\bigl{(}x^{(j)}-0.5\bigr{)}^{3}$ | $1/2$ | $3$
(f) | $x^{(1)}$ | $1/2$ | $1$
Table 1: Definition of the functions used in the simulations. Here,
$x=(x^{(1)},\ldots,x^{(d)})^{\top}\in[0,1]^{d}$.(MM: no lines allowed in the
body of the table) Figure 3: For $d=2$, the contour lines (red) of the
regression functions corresponding to the functions $f$ in Table 1 at the
levels $k/6$ for $k\in[5]$ are shown. The fill colour indicates the function
value at the respective position from $0$ (purple) to $1$ (yellow).

Although we are not aware of other proposed methods for isotonic subgroup
selection, there are alternative ways in which we could combine our $p$-values
with different DAG testing procedures to form a data-dependent selection set.
For instance, one could apply Holm’s procedure (holm1979simple) to ensure FWER
control on the data points, and then take our data-dependent selection set to
be the upper hull of the set of points in $\mathcal{D}_{X,m}$ corresponding to
rejected hypotheses. This simple procedure is already a uniform improvement
(in terms of the size of the selected set) on the Bonferroni approach to
constructing a one-sided confidence band for $\eta$ that was mentioned in the
introduction. Alternatively, one could combine our $p$-values with either the
all-parent or any-parent version of the DAG testing procedure due to
meijer2015multiple, which is described in detail in Section 9.1, and which we
applied with uniform weights on the leaf nodes. Although we are able to prove
in Section 9.2 that these latter procedures have sub-optimal worst-case
performance, they remain a natural approach to controlling the FWER for DAG-
structured hypotheses. We refer to these three alternative versions of our
procedure as $\hat{A}^{\mathrm{ISS},\mathrm{H}}$,
$\hat{A}^{\mathrm{ISS},\mathrm{All}}$ and
$\hat{A}^{\mathrm{ISS},\mathrm{Any}}$ respectively. In all cases, we took
$m=n$, used $\tilde{p}^{1/2}$ given in Definition 9 as $p$-values and for each
data-dependent selection set $\hat{A}$ we estimated
$\mathbb{E}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}\bigr{)}\bigr{\\}}$
using a Monte Carlo approximation based on $10^{5}$ independent draws from
$\mu$ for each data realisation, averaged over 100 repetitions of each
experiment. A comparison of the running times given in Appendix 8.2 shows that
$\hat{A}^{\mathrm{ISS}}$ can be as much as 10 times faster to compute than
$\hat{A}^{\mathrm{ISS},\mathrm{All}}$ and
$\hat{A}^{\mathrm{ISS},\mathrm{Any}}$, though it is not as fast as the more
naive $\hat{A}^{\mathrm{ISS},\mathrm{H}}$.

The results for regression functions (a)–(f) are presented in Figures 4, 5 and
6 respectively. Corresponding results for the other eight regression functions
defined in Appendix 8, which are qualitatively similar, are given in Figures
12, 13 and 14. Moreover, in Figures 15 and 16, we compare
$\hat{A}^{\mathrm{ISS}}$ with two different possible approaches based on
sample splitting that are of a similar flavour to the two-stage approaches
mentioned in the introduction. These were omitted from our earlier comparisons
for visual clarity, and because their performance turns out not to be
competitive. From all of these figures, we see that $\hat{A}^{\mathrm{ISS}}$
is the most effective of these approaches for combining our $p$-values with a
DAG testing procedure. The differences between $\hat{A}^{\mathrm{ISS}}$ and
the other approaches are more marked when $d=2$ than in higher dimensions. It
is also notable that regression functions with smaller values of $\gamma(P)$
such as (d) yield much smaller estimates of
$\mathbb{E}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}\bigr{)}\bigr{\\}}$
that decay more rapidly with the sample size. Conversely, for settings with
larger values of $\gamma(P)$, such as (e), the decay of our estimates of
$\mathbb{E}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}\bigr{)}\bigr{\\}}$
is much slower. These observations are in agreement with our theory in Section
3.2. Finally, we remark that our procedures appear to adapt well to settings
where the regression function depends only on a subset of the $d$ variables,
as can be seen for instance by comparing the results in (a) and (f).

Figure 4: Estimates of
$\mathbb{E}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}\bigr{)}\bigr{\\}}$
for $d=2$ and $\sigma=1/4$. Figure 5: Estimates of
$\mathbb{E}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}\bigr{)}\bigr{\\}}$
for $d=3$ and $\sigma=1/16$. Figure 6: Estimates of
$\mathbb{E}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}\bigr{)}\bigr{\\}}$
for $d=4$ and $\sigma=1/64$.

##  6 Real data applications

###  6.1 ACTG 175

As a first illustration of our procedure on real data, we consider the AIDS
Clinical Trials Group Study 175 (ACTG 175) data. This was a randomised
controlled trial in which HIV-1 patients whose CD4 cell counts at screening
were between 200 to 500 cells per cubic millimetre and who had no history of
AIDS-defining events were randomly assigned to one of four treatment groups
(hammer1996trial). We restrict our attention to two of these four treatment
arms, comparing the effects of monotherapy through the antiretroviral
medication zidovudine against the effects of a combination therapy of
zidovudine together with zalcitabine. At the time, patient heterogeneity with
respect to the response to zidovudine was not well understood
(burger1994pharmacokinetic). Moreover, prior studies suggested that the
beneficial effects of zidovudine fade with time and that this could be
remedied with multitherapy (hammer1996trial). ACTG 175 aimed to investigate
treatment effect heterogeneity, in particular with respect to prior drug
exposure, among patients with less advanced HIV disease. Besides relevant
parts of their medical records, covariates including age, weight and ethnicity
were recorded. The primary end point of the study was defined as a reduction
of the CD4 cell count by at least 50%, development of AIDS, or death, with a
median follow-up duration of 143 weeks (hammer1996trial). The data for 2139
patients are freely available in the R package speff2trial (speff2trial).

####  6.1.1 Risk group estimation

We first consider the task of identifying the patient subgroup whose
probability of not reaching the primary endpoint when receiving zidovudine
alone (532 patients in total) is at least $\tau=0.5$ based on their age, which
the study’s eligibility criteria required to be at least $12$ years. To that
end, for $i\in[n]$, let $Y_{i}=1$ if the $i$th patient did not reach the
primary endpoint and $Y_{i}=0$ otherwise. Furthermore, let $X_{i}$ denote the
$i$th patient’s age (multiplied by $-1$), since a decrease in age is expected
to correspond to an increased probability of avoiding the primary end point
across the eligible age range. Under the assumption that
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$, we
then have that $P\in\mathcal{P}_{\mathrm{Mon},1}(1/2)$, so Type I error
control for our procedure $\hat{A}^{\mathrm{ISS}}$ is guaranteed by Theorem 3.
The left panel of Figure 7 illustrates the data-dependent selection set that
we output with $\alpha=0.05$, indicating that not reaching the primary
endpoint is the more likely outcome for patients aged 39 and under.

For a bivariate illustration, we use age multiplied by $-1$ and CD4 cell count
at the trial onset as covariates. A high initial CD4 cell count is expected to
be associated with a lower risk of reaching the primary endpoint. Thus, we
assume that $\mathcal{D}\sim P^{n}$ for some
$P\in\mathcal{P}_{\mathrm{Mon},2}(1/2)$, and the right panel of Figure 7
illustrates the output $\hat{A}^{\mathrm{ISS}}$ for $\tau=0.5$ and
$\alpha=0.05$. The fact that the left-hand extreme of this selected set is
slightly below 39 years is a reflection of the stronger form of Type I error
control sought in the larger dimension.

Figure 7: Left: Each black dot represents one patient in $\mathcal{D}$ (with
the response jittered vertically for clarity) and the red line gives the lower
bound of $\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})$ when
applied with the $p$-values $\tilde{p}^{1/2}$, for $\sigma=1/2$, $\tau=1/2$,
$\alpha=0.05$, $m=n=532$. The black line shows the isotonic least squares
regression estimator and the blue dashed line indicates the level $\tau$.
Right: corresponding bivariate illustration, where the red region indicates
$\hat{A}^{\mathrm{ISS}}$.

####  6.1.2 Heterogeneous treatment effects

To illustrate an application of the methodology of Section 4.3.1, we take the
change in CD4 cell count from trial onset to week 20 ($\pm$5 weeks) as the
measured response $\tilde{Y}_{i}$ for the $i$th patient. We further set
$T_{i}=0$ if the $i$th patient was in the control group receiving monotherapy
with zidovudine (532 patients) and $T_{i}=1$ if they were assigned to receive
multitherapy with zidovudine and zalcitabine (524 patients). We are interested
in identifying the subgroup for which multitherapy is at least as good as
monotherapy, in the sense that the CD4 cell count is decreased by less, based
on each patient’s age (again multiplied by $-1$) given by $X_{i}$. This means
that, conditional on treatment $T_{i}$ and age $X_{i}$,
$\tilde{\eta}^{T_{i}}(X_{i})$ is the expected change in CD4 cell count in the
first 20 weeks, and we assume that the observed response $\tilde{Y}_{i}$ is
conditionally symmetrically distributed around $\tilde{\eta}^{T_{i}}(X_{i})$.
Thus $\eta(x):=\tilde{\eta}^{1}(x)-\tilde{\eta}^{0}(x)$ gives the
heterogeneous treatment effect on the change in CD4 cell count for patients of
$x$ years of age, and we are interested in identifying $\mathcal{X}_{0}(\eta)$
under the assumption that this is an upper set. Here, $\pi(x)=1/2$ for all
$x$, so that from (4), $Y_{i}=(4T_{i}-2)\cdot\tilde{Y}_{i}$ for all $i$.
Defining now $Y^{*}_{i}:=\mathbbm{1}_{\\{Y_{i}\geq 0\\}}$ and assuming
$\mathcal{D}^{0}=\bigl{(}(X_{1},Y^{*}_{1}),\ldots,(X_{n},Y^{*}_{n})\bigr{)}\sim
P^{n}$, we have $P\in\mathcal{P}_{\mathrm{Upp},1}(1/2,1/2)$, so that
$\hat{A}^{\mathrm{ISS}}$ when applied with $\check{p}_{1/2}$ controls the Type
I error by the discussion in Section 4.3.1. See Figure 8 for a visualisation
of the result. We conclude that among patients aged 25 or younger, replacing
monotherapy by multitherapy is uniformly associated with a neutral or
beneficial effect on the stability of CD4 cell count.

Figure 8: Each black dot represents one patient in $\mathcal{D}$ (with
$Y_{i}^{*}$ jittered vertically for clarity) and the red line gives the lower
bound of $\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})$ when
applied with $\check{p}_{\tau}$, $\tau=1/2$, $\alpha=0.05$, $m=n=1056$.
Further, the black line shows the isotonic least squares regression estimator.
The blue dashed line indicates the level $\tau$.

###  6.2 Fuel consumption dataset

Here we consider the Auto MPG dataset555See
https://archive.ics.uci.edu/ml/datasets/auto+mpg. that was popularised by
quinlan1993combining and that is available through the UCI Machine Learning
Repository (dua2019UCI). This dataset contains information on $n=398$ cars,
including their urban fuel consumption, weight and engine displacement. We
would like to identify the combinations of car weight and engine displacement
for which the probability of fuel efficiency being at least 15mpg is at least
$\tau=0.5$. To this end, we set $Y_{i}=1$ if the $i$th car’s fuel efficiency
is at least 15mpg and $Y_{i}=0$ otherwise. Since increases in weight and
engine displacement can be assumed to decrease the conditional probability of
high fuel efficiency, we let the two components of $X_{i}\in(-\infty,0)^{2}$
give the $i$th car’s weight and engine displacement (multiplied by $-1$). We
then have that
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots(X_{n},Y_{n})\bigr{)}\sim P^{n}$ with
$P\in\mathcal{P}_{\mathrm{Mon,2}}(1/2)$, so Type I error control for our
procedure $\hat{A}^{\mathrm{ISS}}$ is guaranteed by Theorem 3. The output set
from the $\hat{A}^{\mathrm{ISS}}$ algorithm is shown in Figure 9. The strong
sample correlation of 0.93 between weight and engine displacement contributes
to the data-dependent selection set being almost rectangular, with a weight of
under 3400lbs and an engine displacement of under 250 cubic inches being
sufficient to be fairly confident that the fuel consumption is more likely
than not to be at least 15mpg.

Figure 9: Each black dot represents one car in $\mathcal{D}_{X}$ and the red
area gives the output of
$\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})$ applied with
$\tilde{p}_{\sigma,\tau}^{1/2}$ for $\sigma=1/2$, $\tau=1/2$, $\alpha=0.05$,
$m=n=398$.

##  7 Proofs

We begin with some additional notation used in the appendix. For a set
$A\subseteq\mathbb{R}^{d}$, let $\mathrm{Pow}(A)$ denote the power set of $A$.
Denote by $\|\cdot\|_{2}$ the Euclidean norm on $\mathbb{R}^{d}$ and for
$x\in\mathbb{R}^{d}$ and $r>0$, define the closed Euclidean norm ball by
${B}_{2}(x,r):=\\{z\in\mathbb{R}^{d}:\|z-x\|_{2}\leq r\\}$. Given $A_{0}$,
$A_{1}\subseteq\mathbb{R}^{d}$, we write $A_{0}\preccurlyeq A_{1}$ if
$x_{0}\preccurlyeq x_{1}$ for every pair $(x_{0},x_{1})\in A_{0}\times A_{1}$.
We write $\mathcal{L}_{d}$ for Lebesgue measure on $\mathbb{R}^{d}$. Finally,
for $r\geq 0$ and $x\in\mathbb{R}^{d}$, we denote
$\mathcal{I}_{r}(x)\equiv\mathcal{I}_{r}(x,\mathcal{D}_{X}):=\\{i\in[n]:X_{i}\preccurlyeq
x,\|X_{i}-x\|_{\infty}\leq r\\}$.

###  7.1 Proofs from Section 3.1

In order to verify Lemma 1 it will be convenient to prove the following small
generalisation.

######  Lemma 13.

Let $\sigma>0$, $\tau\in\mathbb{R}$ and let $P$ be a distribution on
$\mathbb{R}^{d}\times\mathbb{R}$ with regression function $\eta$ such that if
$(X,Y)\sim P$, then $Y-\eta(X)$ is conditionally sub-Gaussian with variance
parameter $\sigma^{2}$ given $X$. Fix $x\in\mathbb{R}^{d}$ and suppose that
$\eta(x^{\prime})\leq\tau$ for all $x^{\prime}\preccurlyeq x$. Given
$\mathcal{D}=\bigl{(}(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\bigr{)}\sim P^{n}$, we
have
$\mathbb{P}_{P}\bigl{\\{}\hat{p}_{\sigma,\tau}(x,\mathcal{D})\leq\alpha|\mathcal{D}_{X}\bigr{\\}}\leq\alpha$
for all $\alpha\in(0,1)$.

###### Proof of Lemma 13 (and hence Lemma 1).

Throughout the proof, we operate conditional on $\mathcal{D}_{X}$ and consider
the setting of Definition 1. If $\mathcal{I}(x)=\emptyset$, then
$\hat{p}_{\sigma,\tau}(x,\mathcal{D})=1$ and the result follows, so suppose
henceforth that $n(x)\geq 1$. Define the $\sigma$-algebra $\mathcal{F}_{0}$
generated by $\\{(X_{i})_{i\in\mathcal{I}(x)}\\}$ and the $\sigma$-algebras
$\mathcal{F}_{k}$ generated by
$\bigl{\\{}\bigl{(}Y_{(j)}(x)\bigr{)}_{j\in[k]}\cup\mathcal{F}_{0}\bigr{\\}}$
for $k\in[n(x)]$. Similarly to the proof of duan2020interactive, we first show
that $(S_{k})_{k\in\\{0\\}\cup[n(x)]}$,where $S_{0}:=0$, is a supermartingale
with respect to the filtration $(\mathcal{F}_{k})_{k\in\\{0\\}\cup[n(x)]}$.
Since for $k\in[n(x)]$, $S_{k-1}$ is measurable with respect to
$\mathcal{F}_{k-1}$ and the ordering $Y_{(1)},\ldots,Y_{(n(x))}$ is fixed
conditional on $\mathcal{D}_{X}$, we have for any $k\in[n(x)]$ that

$\displaystyle\mathbb{E}(S_{k}\mid\mathcal{F}_{k-1})$
$\displaystyle=S_{k-1}+\frac{1}{\sigma}\bigl{\\{}\mathbb{E}\bigl{(}Y_{(k)}(x)\mid\mathcal{F}_{k-1}\bigr{)}-\tau\bigr{\\}}$
$\displaystyle=S_{k-1}+\frac{1}{\sigma}\bigl{\\{}\eta\bigl{(}X_{(k)}(x)\bigr{)}-\tau\bigr{\\}}\leq
S_{k-1},$

where in the last step we used the fact that $\eta(X_{i})\leq\eta(x)\leq\tau$
for $i\in\mathcal{I}(x)$. Since the integrability of $S_{k}$ follows from the
sub-Gaussianity of the increments, the sequence
$(S_{k})_{k\in\\{0\\}\cup[n(x)]}$ is a supermartingale. Moreover, its
increments satisfy
$Z^{\prime}_{k}:=S_{k}-S_{k-1}=\bigl{(}Y_{(k)}(x)-\tau\bigr{)}/\sigma\leq\bigl{\\{}Y_{(k)}(x)-\eta\bigl{(}X_{(k)}(x)\bigr{)}\bigr{\\}}/\sigma=:Z_{k}$
for $k\in[n(x)]$ and the random variables $(Z^{\prime}_{k})_{k\in[n(x)]}$ are
independent conditional on $\mathcal{D}_{X}$, as are $(Z_{k})_{k\in[n(x)]}$.
Thus, we have by Lemma 32 _(a)_ and with $u_{\alpha}(\cdot)$ as defined there
that

$\displaystyle\mathbb{P}\biggl{(}\bigcup_{k=1}^{n(x)}\bigl{\\{}S_{k}\geq
u_{\alpha}(k)\\}\,\biggm{|}\,\mathcal{D}_{X}\biggr{)}$
$\displaystyle=\mathbb{P}\biggl{(}\bigcup_{k=1}^{n(x)}\biggl{\\{}\sum_{j=1}^{k}Z^{\prime}_{j}\geq
u_{\alpha}(k)\biggr{\\}}\,\biggm{|}\,\mathcal{D}_{X}\biggr{)}$
$\displaystyle\leq\mathbb{P}\biggl{(}\bigcup_{k=1}^{n(x)}\biggl{\\{}\sum_{j=1}^{k}Z_{j}\geq
u_{\alpha}(k)\biggr{\\}}\,\biggm{|}\,\mathcal{D}_{X}\biggr{)}\leq\alpha.$

Hence, for $\alpha\in(0,1)$,

$\displaystyle\mathbb{P}\bigl{(}\hat{p}_{\sigma,\tau}(x,\mathcal{D})\leq\alpha\mid\mathcal{D}_{X}\bigr{)}$
$\displaystyle=\mathbb{P}\bigl{(}\hat{p}_{\sigma,\tau}(x,\mathcal{D})\leq\alpha,n(x)>0\mid\mathcal{D}_{X}\bigr{)}$
$\displaystyle=\mathbb{P}\biggl{(}\max_{k\in[n(x)]}\frac{S_{k}}{u_{\alpha}(k)}\geq
1,n(x)>0\Bigm{|}\mathcal{D}_{X}\biggr{)}\leq\alpha,$

as required. ∎

###### Proof of Lemma 2.

Fix a finite set $I$, a family of distributions $\mathcal{Q}$ on $(0,1]^{I}$,
a collection of random variables $\bm{p}=(p_{i})_{i\in I}$ taking values in
$(0,1]^{I}$, as well as hypotheses
$H_{i}\subseteq\\{Q\in\mathcal{Q}:\mathbb{P}_{Q}(p_{i}\leq t)\leq t,\forall
t\in(0,1]\\}$ for $i\in I$ and any $G_{0}$-consistent polyforest-weighted DAG
$G^{\prime}=(I,E,\bm{w})$. Throughout this proof, define $G:=(I,E)$ and
$F:=(I,\\{e\in E:w_{e}=1\\})$ as in Algorithm 1, and write $J^{c}:=I\setminus
J$ for any $J\subseteq I$. Fix $Q_{0}\in\mathcal{Q}$, so that $I_{0}\equiv
I_{0}(Q_{0})\subseteq I$ is a $G$-lower set giving the indices of true null
hypotheses. If $I_{0}=\emptyset$, then no Type I error can be made and the
proof is complete. We therefore suppose henceforth that $|I_{0}|>0$. For a
proper subset $J$ of $I$, it is convenient to define

$\displaystyle\alpha(i,J)\equiv\alpha(i,J,F):=\begin{cases}\frac{|(\\{i\\}\cup\operatorname{\mathrm{de}}_{F}(i))\cap
L(F)\cap J^{c}|}{|L(F)\cap J^{c}|}\cdot\alpha\quad&\text{if $i\notin J$,
$\operatorname{\mathrm{pa}}_{F}(i)\subseteq J$}\\\
0&\text{otherwise.}\end{cases}$ (5)

Thus, given a set of rejected hypotheses $J$ at a particular iteration of
Algorithm 1 and writing $\mathcal{N}_{0}(J):=\\{i\in
J^{c}:p_{i}\leq\alpha(i,J)\\}$, the hypotheses in
$\mathcal{N}(J):=\mathcal{N}_{0}(J)\cup\bigcup_{j\in\mathcal{N}_{0}(J)}\operatorname{\mathrm{an}}_{G}(j)$
will be rejected at the next iteration. Hence, the set of rejected hypotheses
at the $\ell$-th iteration in Algorithm 1 can be written as
$R_{\ell}=R_{\ell-1}\cup\mathcal{N}(R_{\ell-1})$ with $R_{0}=\emptyset$. We
first claim that

$\displaystyle\mathcal{N}(I_{1})\subseteq\mathcal{N}(I_{2})\cup I_{2}$ (6)

for all $G$-upper proper subsets $I_{1}\subseteq I_{2}$ of $I$. To see this,
fix such $I_{1},I_{2}$ and any $i\in\mathcal{N}(I_{1})$. The result is
immediate if $i\in I_{2}$, so suppose that $i\in I_{2}^{c}$. If
$i\in\mathcal{N}_{0}(I_{1})$, then $\alpha(i,I_{1})>0$, so
$\operatorname{\mathrm{pa}}_{F}(i)\subseteq I_{1}$. Since $I_{1}$ and $I_{2}$
are $G$-upper, they are also $F$-upper. Hence
$\\{i\\}\cup\operatorname{\mathrm{de}}_{F}(i)\subseteq I^{c}_{2}\subseteq
I^{c}_{1}$, so that

$\alpha(i,I_{1})=\frac{\bigl{|}\bigl{(}\\{i\\}\cup\operatorname{\mathrm{de}}_{F}(i)\bigr{)}\cap
L(F)\bigr{|}}{|L(F)\cap
I_{1}^{c}|}\cdot\alpha\leq\frac{\bigl{|}\bigl{(}\\{i\\}\cup\operatorname{\mathrm{de}}_{F}(i)\bigr{)}\cap
L(F)\bigr{|}}{|L(F)\cap I_{2}^{c}|}\cdot\alpha=\alpha(i,I_{2}),$ (7)

and we deduce that $i\in\mathcal{N}_{0}(I_{2})\subseteq\mathcal{N}(I_{2})$. If
instead $i\in\operatorname{\mathrm{an}}_{G}(j_{0})$ for some
$j_{0}\in\mathcal{N}_{0}(I_{1})$, then since $I_{2}$ is $G$-upper and $i\in
I_{2}^{c}$, we have $j_{0}\in I_{2}^{c}$. Following the same line of reasoning
as in (7), we see that $0<\alpha(j_{0},I_{1})\leq\alpha(j_{0},I_{2})$, so that
$j_{0}\in\mathcal{N}_{0}(I_{2})$ and consequently
$i\in\operatorname{\mathrm{an}}_{G}(j_{0})\subseteq\mathcal{N}(I_{2})$. This
establishes the claim in (6).

Our second claim is that

$\displaystyle\mathbb{P}_{Q_{0}}\bigl{(}\mathcal{N}(I^{c}_{0})=\emptyset\bigr{)}\geq
1-\alpha.$ (8)

To see this, first note that since $I_{0}^{c}$ is $G$-upper, it is $F$-upper.
Moreover, for any $i\in I_{0}$, we have $\alpha(i,I_{0}^{c})>0$ only if
$\operatorname{\mathrm{pa}}_{F}(i)\subseteq I_{0}^{c}$, so the ancestors of
any element of $I_{*}:=\\{i\in I_{0}:\alpha(i,I_{0}^{c})>0\\}$ belong to
$I_{0}^{c}$, and we deduce that $I_{*}$ is an antichain in $F$. Combining this
with the fact that $F$ is a polyforest in which each node has at most one
parent, we see that if $i_{1},i_{2}\in I_{*}$ are distinct, then
$\\{i_{1}\\}\cup\operatorname{\mathrm{de}}_{F}(i_{1})$ and
$\\{i_{2}\\}\cup\operatorname{\mathrm{de}}_{F}(i_{2})$ are disjoint. Hence,

$\displaystyle\mathbb{P}_{Q_{0}}\bigl{(}\mathcal{N}(I^{c}_{0})\neq\emptyset\bigr{)}$
$\displaystyle=\mathbb{P}_{Q_{0}}\biggl{(}\bigcup_{i\in
I_{0}}\bigl{\\{}p_{i}\leq\alpha(i,I_{0}^{c})\bigr{\\}}\biggr{)}\leq\sum_{i\in
I_{0}}\mathbb{P}_{Q_{0}}\bigl{(}p_{i}\leq\alpha(i,I_{0}^{c})\bigr{)}$
$\displaystyle\leq\sum_{i\in I_{0}}\alpha(i,I_{0}^{c})=\sum_{i\in
I_{*}}\frac{\bigl{|}\bigl{(}\\{i\\}\cup\operatorname{\mathrm{de}}_{F}(i)\bigr{)}\cap
L(F)\bigr{|}}{|L(F)\cap I_{0}|}\cdot\alpha\leq\alpha,$

as required. Writing $\Omega_{0}:=\bigl{\\{}\mathcal{N}(I_{0}^{c})\cap
I_{0}=\emptyset\bigr{\\}}$ and using (6), we see that
$\mathcal{N}(R_{\ell-1})\subseteq\mathcal{N}(I_{0}^{c})\cup I_{0}^{c}$, so on
$\Omega_{0}$, we have $\mathcal{N}(R_{\ell-1})\subseteq I_{0}^{c}$. We deduce
that

$\Omega_{0}\cap\\{R_{\ell-1}\cap
I_{0}=\emptyset\\}=\Omega_{0}\cap\\{\mathcal{N}(R_{\ell-1})\cap
I_{0}=\emptyset\\}\cap\\{R_{\ell-1}\cap
I_{0}=\emptyset\\}=\Omega_{0}\cap\\{R_{\ell}\cap I_{0}=\emptyset\\}.$

Since $R_{0}=\emptyset$, we have $\Omega_{0}=\Omega_{0}\cap\\{R_{0}\cap
I_{0}=\emptyset\\}$, which yields by induction that
$\Omega_{0}=\Omega_{0}\cap\\{R_{|I|}\cap
I_{0}=\emptyset\\}\subseteq\\{R_{|I|}\cap I_{0}=\emptyset\\}$. Combining this
with (8) we conclude that

$\mathbb{P}_{Q_{0}}\bigl{(}R_{|I|}\cap
I_{0}=\emptyset\bigr{)}\geq\mathbb{P}_{Q_{0}}(\Omega_{0})=\mathbb{P}_{Q_{0}}\bigl{(}\mathcal{N}(I_{0}^{c})=\emptyset\bigr{)}\geq
1-\alpha,$

as required. ∎

###### Proof of Theorem 3.

If $(\mathcal{X},\mathcal{A})$ and $(\mathcal{Y},\mathcal{B})$ are measurable
spaces, $f:\mathcal{X}\rightarrow\mathcal{Y}$ is measurable and $\pi$ is a
distribution on $\mathcal{X}$, let $f\sharp\pi$ denote the pushforward measure
on $\mathcal{Y}$ of $\pi$ under $f$; i.e., if $Z\sim\pi$ then $f(Z)\sim
f\sharp\pi$. We condition on $\mathcal{D}_{X}$ throughout this proof and
denote
$\hat{\bm{p}}^{*}\equiv\hat{\bm{p}}^{*}(\cdot)=\bigl{(}\hat{p}_{i}^{*}(\cdot)\bigr{)}_{i\in[m]}:=\bigl{(}\hat{p}_{\sigma,\tau}(X_{i},\cdot)\bigr{)}_{i\in[m]}$.
Write
$\mathcal{Q}:=\\{\hat{\bm{p}}^{*}\sharp\tilde{P}^{n}:\tilde{P}\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)\\}$
for a family of distributions over $(0,1]^{m}$ induced by
$\mathcal{P}_{\mathrm{Mon},d}(\sigma)$. Further, for $i\in[m]$, let
$H^{*}_{i}:=\\{\tilde{P}\in\mathcal{P}_{\mathrm{Mon},d}(\sigma):\mathbb{E}_{\tilde{P}}(Y_{i}|X_{i})<\tau\\}$
and $H_{i}:=\\{\hat{\bm{p}}^{*}\sharp\tilde{P}^{n}:\tilde{P}\in
H_{i}^{*}\\}\subseteq\mathcal{Q}$, so that for $Q:=\hat{\bm{p}}^{*}\sharp
P^{n}$ we have $I_{0}(P):=\\{i\in[m]:P\in H^{*}_{i}\\}\subseteq\\{i\in[m]:Q\in
H_{i}\\}=:I_{0}(Q)$. Lemma 1 then shows that
$H_{i}\subseteq\\{\tilde{Q}\in\mathcal{Q}:\mathbb{P}_{\tilde{Q}}(\hat{p}^{*}_{i}\leq
t|\mathcal{D}_{X})\leq t\ \forall t\in(0,1]\\}$. Now define
$G_{0}^{*}:=([m],E_{0}^{*})$, where
$E_{0}^{*}:=\\{(i_{0},i_{1})\in[m]^{2}:H_{i_{0}}^{*}\subseteq
H_{i_{1}}^{*}\\}$ and $G_{0}:=([m],E_{0})$, where
$E_{0}:=\\{(i_{0},i_{1})\in[m]^{2}:H_{i_{0}}\subseteq H_{i_{1}}\\}$. We claim
that $E_{0}^{*}\subseteq E_{0}$. To see this, fix $(i_{0},i_{1})\in
E_{0}^{*}$, so that $H_{i_{0}}^{*}\subseteq H_{i_{1}}^{*}$, and suppose that
$Q_{0}\in H_{i_{0}}$. Then we can find $P_{0}\in H_{i_{0}}^{*}$ such that
$Q_{0}=\hat{\bm{p}}^{*}\sharp P_{0}^{n}$. But since $P_{0}\in H_{i_{1}}^{*}$,
we must have that $Q_{0}\in H_{i_{1}}$, and this establishes our claim. By
construction, $\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m})$ is a
$G_{0}^{*}$-consistent polyforest-weighted DAG, and we can therefore deduce
from our claim that it is also a $G_{0}$-consistent polyforest-weighted DAG.
Hence, by Lemma 2,

$\displaystyle\mathbb{P}_{P}\bigl{\\{}\mathcal{R}_{\alpha}^{\mathrm{ISS}}\bigl{(}\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m}),$
$\displaystyle\hat{\bm{p}}^{*}(\mathcal{D})\bigr{)}\cap
I_{0}(P)=\emptyset\bigm{|}\mathcal{D}_{X}\bigr{\\}}$
$\displaystyle\geq\mathbb{P}_{Q}\bigl{\\{}\mathcal{R}_{\alpha}^{\mathrm{ISS}}\bigl{(}\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m}),\hat{\bm{p}}^{*}\bigr{)}\cap
I_{0}(Q)=\emptyset\bigm{|}\mathcal{D}_{X}\bigr{\\}}\geq 1-\alpha.$

Moreover, $\mathcal{X}_{\tau}(\eta)$ is an upper set because
$P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)$, and we conclude that

$\mathbb{P}_{P}\bigl{(}\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\subseteq\mathcal{X}_{\tau}(\eta)\bigm{|}\mathcal{D}_{X}\bigr{)}\geq\mathbb{P}_{P}\bigl{\\{}\mathcal{R}_{\alpha}^{\mathrm{ISS}}\bigl{(}\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m}),\hat{\bm{p}}^{*}(\mathcal{D})\bigr{)}\cap
I_{0}(P)=\emptyset\bigm{|}\mathcal{D}_{X}\bigr{\\}}\geq 1-\alpha,$

as required. ∎

###  7.2 Proofs from Section 3.2

The following proposition shows that if we only know that
$P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)$, then it is impossible to provide
non-trivial uniform power guarantees for data-dependent selection sets with
Type I error control.

######  Proposition 14.

Let $d\in\mathbb{N}$, $\tau\in\mathbb{R}$, $\sigma>0$ and $\alpha\in(0,1)$.
Then, for any $n\in\mathbb{N}$,

$\sup_{P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)}\inf_{\hat{A}\in\hat{\mathcal{A}}_{n}(\tau,\alpha,\mathcal{P}_{\mathrm{Mon},d}(\sigma))}\mathbb{E}_{P}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}\geq
1-\alpha.$

###### Proof of Proposition 14.

Fix a Borel probability measure $\mu$ on $\mathbb{R}^{d}$. For
$\Delta\in\mathbb{R}$, let $\eta_{\Delta}:\mathbb{R}^{d}\rightarrow\mathbb{R}$
denote the constant function satisfying $\eta_{\Delta}(x):=\tau+\Delta$ for
all $x\in\mathbb{R}^{d}$, and let $P_{\Delta}$ denote the distribution on
$\mathbb{R}^{d}\times\mathbb{R}$ of $(X,Y)$, where $X\sim\mu$ and
$Y|X\sim\mathcal{N}\bigl{(}\eta_{\Delta}(X),\sigma^{2}\bigr{)}$. Thus
$\\{P_{\Delta}:\Delta\in\mathbb{R}\\}\subseteq\mathcal{P}_{\mathrm{Mon},d}(\sigma)$.
Moreover, for any $\Delta>0$, we have by Pinsker’s inequality that

$\displaystyle\mathrm{TV}(P_{-\Delta}^{n},P_{0}^{n})$
$\displaystyle\leq\sqrt{\frac{n}{2}\cdot\mathrm{KL}(P_{-\Delta},P_{0})}=\sqrt{\frac{n}{2}\cdot\mathrm{KL}\bigr{(}\mathcal{N}(\tau-\Delta,\sigma^{2}),\mathcal{N}(\tau,\sigma^{2})\bigr{)}}\leq\frac{\sqrt{n}\Delta}{2\sigma}.$

Now fix $\Delta>0$, and suppose that
$\hat{A}\in\hat{\mathcal{A}}_{n}\bigl{(}\tau,\alpha,\mathcal{P}_{\mathrm{Mon},d}(\sigma)\bigr{)}$.
Since $\mathcal{X}_{\tau}(\eta_{-\Delta})=\emptyset$, we have for every
$x\in\mathbb{R}^{d}$ that

$\displaystyle\mathbb{P}_{P_{0}}\bigl{(}x\in\hat{A}(\mathcal{D})\bigr{)}$
$\displaystyle\leq\mathbb{P}_{P_{-\Delta}}\bigl{(}x\in\hat{A}(\mathcal{D})\bigr{)}+\mathrm{TV}\bigl{(}P_{-\Delta}^{n},P_{0}^{n}\bigr{)}$
$\displaystyle\leq\mathbb{P}_{P_{-\Delta}}\bigl{(}\hat{A}(\mathcal{D})\nsubseteq\mathcal{X}_{\tau}(\eta_{-\Delta})\bigr{)}+\frac{\sqrt{n}\Delta}{2\sigma}\leq\alpha+\frac{\sqrt{n}\Delta}{2\sigma}.$

Hence, by Fubini’s theorem,

$\displaystyle\mathbb{E}_{P_{0}}\bigl{\\{}\mu\bigl{(}\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}=\mathbb{E}_{P_{0}}\biggl{(}\int_{\mathbb{R}^{d}}\mathbbm{1}_{\\{x\in\hat{A}(\mathcal{D})\\}}\,d\mu(x)\biggr{)}=\int_{\mathbb{R}^{d}}\mathbb{P}_{P_{0}}\bigl{(}x\in\hat{A}(\mathcal{D})\bigr{)}\,d\mu(x)\leq\alpha+\frac{\sqrt{n}\Delta}{2\sigma}.$

Moreover, by our choice of $\eta_{0}$, we have
$\mathcal{X}_{\tau}(\eta_{0})=\mathbb{R}^{d}$, and hence

$\displaystyle\mathbb{E}_{P_{0}}\bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta_{0})\setminus\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}$
$\displaystyle=1-\mathbb{E}_{P_{0}}\bigl{\\{}\mu\bigl{(}\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}\geq
1-\alpha-\frac{\sqrt{n}\Delta}{2\sigma}.$

The result follows by taking an infimum over
$\hat{A}\in\hat{\mathcal{A}}_{n}\bigl{(}\tau,\alpha,\mathcal{P}_{\mathrm{Mon},d}(\sigma)\bigr{)}$,
and then letting $\Delta\rightarrow 0$. ∎

###### Proof of Theorem 4.

Let us define $C_{0}:=962\geq 2\\{16\vee 481^{1/(2\beta+1)}\\}$ and
$C:=3C_{0}$. Further, let

$\xi:=\frac{C_{0}}{2}\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\nu^{2}}\log_{+}\Bigl{(}\frac{\log_{+}n}{\alpha\wedge\delta}\Bigr{)}\biggr{)}^{1/(2\beta+1)}+\frac{\log_{+}(1/\delta)}{n}\biggr{\\}}.$

By the choice of $\xi$, the result holds if
$\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\bigr{)}\leq 2\xi$. We therefore suppose
henceforth that $\xi$ is such that $\xi<1/2$ and
$\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\bigr{)}>2\xi$. Then, since
$P\in\mathcal{P}_{\mathrm{Mar},d}(\tau,\beta,\nu)$, we have that
$\mu\bigl{(}\mathcal{X}_{\tau+\nu\xi^{\beta}}(\eta)\bigr{)}>\xi$, so
$x_{0}:=\inf\\{x\in\mathcal{X}_{\tau+\nu\xi^{\beta}}(\eta):\mu\bigl{(}\mathcal{X}_{\tau+\nu\xi^{\beta}}(\eta)\cap(-\infty,x]\bigr{)}\geq\xi\\}$
is finite. For
$I_{\xi}:=\mathcal{X}_{\tau+\nu\xi^{\beta}}(\eta)\cap(-\infty,x_{0}]$, it then
holds that $\mu(I_{\xi})\geq\xi$. Further, by Lemma 36 _(i)_ and the fact that
$C_{0}\geq 32$,

$n\xi\geq 16\log_{+}\Bigl{(}\frac{1}{\delta}\Bigr{)}\geq
8\log\Bigl{(}\frac{2}{\delta}\Bigr{)}.$

Writing $\Omega_{0}:=\bigl{\\{}n^{-1}\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}\in
I_{\xi}\\}}\geq\xi/2\bigr{\\}}$, it follows by a multiplicative Chernoff bound
(mcdiarmid1998concentration, Theorem 2.3(c)) that

$\mathbb{P}_{P}\bigl{(}\Omega_{0}^{c}\bigr{)}\leq\exp\biggl{(}-\frac{n\xi}{8}\biggr{)}\leq\frac{\delta}{2}.$

By the choice of $\xi$, it holds on $\Omega_{0}$ that

$\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}\in
I_{\xi}\\}}\geq\frac{n\xi}{2}\geq\frac{1}{2}\cdot\Bigl{(}\frac{C_{0}}{2}\Bigr{)}^{2\beta+1}\cdot\frac{\sigma^{2}}{\nu^{2}\xi^{2\beta}}\log_{+}\Bigl{(}\frac{\log_{+}n}{\alpha\wedge\delta}\Bigr{)};$

in particular, since $n\xi\geq 8\log(2/\delta)$, it holds on this event that
$\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}\in I_{\xi}\\}}\geq 1$. Thus, we can fix
any $i_{1}\in[n]$ such that $X_{i_{1}}=\max(\mathcal{D}_{X}\cap I_{\xi})$.
Furthermore, let $i_{1},\ldots,i_{K}\in[n]$ with $K:=|\\{i\in[n]:X_{i}\geq
X_{i_{1}}\\}|$ be the maximal set of indices such that $X_{i_{k}}\geq
X_{i_{1}}$ for all $k\in[K]$. Writing
$r_{k}:=X_{i_{k}}-\min(\mathcal{D}_{X}\cap I_{\xi})$ and noting that
$\mathcal{I}_{r}(x)=\\{i\in[n]:x-r\leq X_{i}\leq x\\}$ for $r\geq 0$ and
$x\in\mathbb{R}$, we have on $\Omega_{0}$ that for all $k\in[K]$,

$n\geq|\mathcal{I}_{r_{k}}(X_{i_{k}})|\geq|\mathcal{I}_{r_{1}}(X_{i_{1}})|\geq\frac{1}{2}\cdot\Bigl{(}\frac{C_{0}}{2}\Bigr{)}^{2\beta+1}\cdot\frac{\sigma^{2}}{\nu^{2}\xi^{2\beta}}\log_{+}\Bigl{(}\frac{\log_{+}n}{\alpha\wedge\delta}\Bigr{)}.$

Hence, writing
$u_{\delta^{\prime}}(\ell):=1.7\sqrt{\ell\bigl{\\{}0.72\log(5.2/\delta^{\prime})+\log\log(2\ell)\bigr{\\}}}$
for $\delta^{\prime}\in(0,1)$ and $\ell\in\mathbb{N}$ as in Lemma 32 _(a)_ ,
we have for all $k\in[K]$ that

$\displaystyle\biggl{(}\frac{u_{\alpha}(|\mathcal{I}_{r_{k}}(X_{i_{k}})|)+u_{\delta/2}(|\mathcal{I}_{r_{k}}(X_{i_{k}})|)}{|\mathcal{I}_{r_{k}}(X_{i_{k}})|}\biggr{)}^{2}$
$\displaystyle\leq\frac{2\cdot 1.7^{2}\cdot
0.72\cdot\bigl{\\{}\log(5.2/\alpha)+\log(10.4/\delta)\bigr{\\}}+2\cdot 2\cdot
1.7^{2}\cdot\log\log\bigl{(}2\cdot|\mathcal{I}_{r_{k}}(X_{i_{k}})|\bigr{)}}{|\mathcal{I}_{r_{k}}(X_{i_{k}})|}$
$\displaystyle\leq\frac{2\cdot 1.7^{2}\cdot 0.72\cdot
2\cdot\log\bigl{(}\frac{10.4}{\alpha\wedge\delta}\bigr{)}+4\cdot
1.7^{2}\cdot\log\bigl{\\{}2\log_{+}\bigl{(}|\mathcal{I}_{r_{k}}(X_{i_{k}})|\bigr{)}\bigr{\\}}}{|\mathcal{I}_{r_{k}}(X_{i_{k}})|}$
$\displaystyle\leq
11.56\cdot\frac{\log\bigl{(}\frac{20.8\log_{+}n}{\alpha\wedge\delta}\bigr{)}}{|\mathcal{I}_{r_{1}}(X_{i_{1}})|}\leq
11.56\cdot
20.8\cdot\frac{\log_{+}\bigl{(}\frac{\log_{+}n}{\alpha\wedge\delta}\bigr{)}}{|\mathcal{I}_{r_{1}}(X_{i_{1}})|}$
$\displaystyle\leq
481\cdot\Bigl{(}\frac{2}{C_{0}}\Bigr{)}^{2\beta+1}\cdot\frac{\nu^{2}\xi^{2\beta}}{\sigma^{2}}\leq\frac{\nu^{2}\xi^{2\beta}}{\sigma^{2}},$

where we used the inequality $(a+b)^{2}\leq 2(a^{2}+b^{2})$ for $a,b\geq 0$,
Lemma 36 _(i)_ and the fact that $C_{0}\geq 2\cdot 481^{1/(2\beta+1)}$. For

$\Omega_{1}\bigl{(}X_{i_{1}}\bigr{)}:=\bigcap_{k=1}^{K}\biggl{\\{}\sum_{i\in\mathcal{I}_{r_{k}}(X_{i_{k}})}\frac{Y_{i}-\tau}{\sigma}\geq
u_{\alpha}\bigl{(}|\mathcal{I}_{r_{k}}(X_{i_{k}})|\bigr{)}\biggr{\\}},$

we therefore have on $\Omega_{0}$ that

$\displaystyle\mathbb{P}_{P}\Bigl{(}\Omega_{1}\bigl{(}X_{i_{1}}\bigr{)}^{c}$
$\displaystyle\bigm{|}\mathcal{D}_{X}\Bigr{)}$
$\displaystyle=\mathbb{P}_{P}\biggl{(}\bigcup_{k=1}^{K}\biggl{\\{}\sum_{i\in\mathcal{I}_{r_{k}}(X_{i_{k}})}\frac{Y_{i}-(\tau+\nu\xi^{\beta})}{\sigma}<u_{\alpha}\bigl{(}|\mathcal{I}_{r_{k}}(X_{i_{k}})|\bigr{)}-|\mathcal{I}_{r_{k}}(X_{i_{k}})|\frac{\nu\xi^{\beta}}{\sigma}\biggr{\\}}\Bigm{|}\mathcal{D}_{X}\biggr{)}$
$\displaystyle\leq\mathbb{P}_{P}\biggl{(}\bigcup_{k=1}^{K}\biggl{\\{}\sum_{i\in\mathcal{I}_{r_{k}}(X_{i_{k}})}\frac{Y_{i}-(\tau+\nu\xi^{\beta})}{\sigma}<-u_{\delta/2}\bigl{(}|\mathcal{I}_{r_{k}}(X_{i_{k}})|\bigr{)}\Bigm{|}\mathcal{D}_{X}\biggr{\\}}\biggr{)}\leq\frac{\delta}{2},$

where the last inequality follows from Lemma 32 _(a)_. Let $n(x)$ and
$\bigl{(}Y_{(j)}(x)\bigr{)}_{j\in[n(x)]}$ be as in Definition 1. For
$k\in[K]$, write $n_{k}\equiv
n_{k}(x,\mathcal{D}_{X}):=|\mathcal{I}_{r_{k}}(x)|$ and

$\hat{p}^{r_{k}}_{\sigma,\tau}(x,\mathcal{D}):=5.2\exp\biggl{\\{}-\frac{\max\bigl{(}\sum_{j=1}^{n_{k}}Y_{(j)}(x)-\tau
n_{k},0\bigr{)}^{2}}{2.0808\sigma^{2}n_{k}}+\frac{\log\log(2n_{k})}{0.72}\biggr{\\}}.$

We have on $\Omega_{0}\cap\Omega_{1}\bigl{(}X_{i_{1}}\bigr{)}$ that

$\max_{k\in[K]}\hat{p}_{\sigma,\tau}(X_{i_{k}},\mathcal{D})\leq\max_{k\in[K]}\hat{p}_{\sigma,\tau}^{r_{k}}(X_{i_{k}},\mathcal{D})\leq\alpha,$

so that
$\\{i_{k}:k\in[K]\\}\subseteq\mathcal{R}^{\mathrm{ISS}}_{\alpha}\bigl{(}\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X}),\bigl{(}\hat{p}_{\sigma,\tau}(X_{i},\mathcal{D})\bigr{)}_{i\in[n]}\bigr{)}$.
Since $X_{i_{1}}\in I_{\xi}$, we have on
$\Omega_{0}\cap\Omega_{1}\bigl{(}X_{i_{1}}\bigr{)}$ that

$[x_{0},\infty)\subseteq\bigl{[}X_{i_{1}},\infty\bigr{)}\subseteq\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,n}(\mathcal{D}).$

It follows that

$\displaystyle\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,n}(\mathcal{D})\bigr{)}$
$\displaystyle\leq\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\mathcal{X}_{\tau+\nu\xi^{\beta}}(\eta)\bigr{)}+\mu\bigl{(}\mathcal{X}_{\tau+\nu\xi^{\beta}}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,n}(\mathcal{D})\bigr{)}$
$\displaystyle\leq\xi+\mu\bigl{(}\mathcal{X}_{\tau+\nu\xi^{\beta}}(\eta)\cap(-\infty,X_{i_{1}})\bigr{)}$
$\displaystyle\leq\xi+\mu\bigl{(}\mathcal{X}_{\tau+\nu\xi^{\beta}}(\eta)\cap(-\infty,x_{0})\bigr{)}\leq
2\xi,$

since $P\in\mathcal{P}_{\mathrm{Mar},1}(\tau,\beta,\nu)$. We conclude that

$\displaystyle\mathbb{P}_{P}\biggl{[}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,n}(\mathcal{D})\bigr{)}$
$\displaystyle>1\wedge
C_{0}\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\nu^{2}}\log_{+}\Bigl{(}\frac{\log_{+}n}{\alpha\wedge\delta}\Bigr{)}\biggr{)}^{1/(2\beta+1)}+\frac{\log_{+}(1/\delta)}{n}\biggr{\\}}\biggr{]}$
$\displaystyle=\mathbb{P}_{P}\Bigl{(}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,n}(\mathcal{D})\bigr{)}>2\xi\Bigr{)}\leq\mathbb{P}_{P}\bigl{(}\Omega_{0}^{c}\cup\Omega_{1}(X_{i_{1}})^{c}\bigr{)}\leq\delta.$

This proves the first statement in the theorem, and we deduce the second
result by integrating our tail bound over $\delta\in(0,1)$. Since this part of
the calculation is an identical argument to that in the multivariate case, we
refer the reader to (7.2), (11) and (7.2) in the proof of Theorem 7 for
details. Since $C=3C_{0}$, the result follows. ∎

###### Proof of Proposition 5.

Take $q\in\mathbb{N}$ and let $\mathbb{W}_{q,d}\subseteq[q]^{d}$ and
$(\mathcal{H}_{\bm{j}}^{q}:\bm{j}\in\mathbb{W}_{q,d})$ be as in Section 3.3.
Let $\mu_{q}$ denote the uniform distribution on
$\bigcup_{\bm{j}\in\mathbb{W}_{q,d}}\mathcal{H}_{\bm{j}}^{q}$. For each
$\bm{j}=(j_{1},\ldots,j_{d})\in\mathbb{W}_{q,d}$, we define
$\eta_{q,\bm{j}}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ by

$\displaystyle\eta_{q,\bm{j}}(x)\equiv\eta_{q,\bm{j}}(x_{1},\ldots,x_{d}):=\begin{cases}\tau-\nu&\text{
if }x_{\ell}<j_{\ell}/q\text{ for all }\ell\in[d]\\\ \tau+\nu&\text{
otherwise. }\end{cases}$

We also define $\eta_{q,\ast}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ to be the
constant function $\eta_{q,\ast}(x):=\tau+\nu$. For
$\bm{j}\in\mathbb{W}_{q,d}\cup\\{\ast\\}$, let
$P_{q,\bm{j}}\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)$ denote the distribution
on $[0,1]^{d}\times\mathbb{R}$ of $(X,Y)$, where $X\sim\mu_{q}$ and
$Y|X\sim\mathcal{N}\bigl{(}\eta_{q,\bm{j}}(X),\sigma^{2}\bigr{)}$. Moreover,
$\mu_{q}\bigl{(}\eta_{q,\bm{j}}^{-1}([\tau,\tau+\nu\xi^{\beta}])\bigr{)}=\mu_{q}(\emptyset)=0\leq\xi$
for all $\xi<1$. On the other hand, if $\xi=1$ then
$\mu_{q}\bigl{(}\eta_{q,\bm{j}}^{-1}([\tau,\tau+\nu\xi^{\beta}])\bigr{)}\leq
1=\xi$. Thus,
$P_{q,\bm{j}}\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Mar},d}(\tau,\beta,\nu)$
for all $\bm{j}\in\mathbb{W}_{q,d}\cup\\{\ast\\}$. In addition, given any
$\bm{j}=(j_{1},\ldots,j_{d})\in\mathbb{W}_{q,d}$, and
$\bm{j}^{\prime}=(j^{\prime}_{1},\ldots,j^{\prime}_{d})\in\mathbb{W}_{q,d}\setminus\\{\bm{j}\\}$
we must have $j^{\prime}_{\ell^{\prime}}>j_{\ell^{\prime}}$ for some
$\ell^{\prime}\in[d]$ by the antichain property. Hence
$x_{\ell^{\prime}}\geq(j^{\prime}_{\ell^{\prime}}-1)/q\geq
j_{\ell^{\prime}}/q$ for all
$x=(x_{1},\ldots,x_{d})^{\top}\in\mathcal{H}_{\bm{j}^{\prime}}^{q}$, so
$\eta_{q,\bm{j}}(x)=\tau+\nu=\eta_{q,\ast}(x)$ for such $x$. Consequently, for
each $\bm{j}\in\mathbb{W}_{q,d}$, we have

$\displaystyle\mathrm{KL}(P_{q,\ast},P_{q,\bm{j}})$
$\displaystyle=\int_{\mathbb{R}^{d}}\mathrm{KL}\bigl{\\{}\mathcal{N}\bigl{(}\eta_{q,\ast}(x),\sigma^{2}\bigr{)},\mathcal{N}\bigl{(}\eta_{q,\bm{j}}(x),\sigma^{2}\bigr{)}\bigr{\\}}\,d\mu_{q}(x)$
$\displaystyle=\mu_{q}(\mathcal{H}_{\bm{j}}^{q})\cdot\frac{2\nu^{2}}{\sigma^{2}}=\frac{1}{|\mathbb{W}_{q,d}|}\cdot\frac{2\nu^{2}}{\sigma^{2}}\leq\frac{2\nu^{2}d}{q^{d-1}\sigma^{2}}.$

Hence, by Pinsker’s inequality,

$\displaystyle\mathrm{TV}\bigl{(}P_{q,\ast}^{n},P_{q,\bm{j}}^{n}\bigr{)}\leq\sqrt{\frac{1}{2}\cdot\mathrm{KL}\bigl{(}P_{q,\ast}^{n},P_{q,\bm{j}}^{n}\bigr{)}}=\sqrt{\frac{n}{2}\cdot\mathrm{KL}\bigl{(}P_{q,\ast},P_{q,\bm{j}}\bigr{)}}\leq\sqrt{\frac{n\nu^{2}d}{q^{d-1}\sigma^{2}}}.$

To complete the proof, consider
$\hat{A}\in\hat{\mathcal{A}}_{n}(\tau,\alpha,\mathcal{P}^{\prime})$. Let
$x\in\bigcup_{\bm{j}\in\mathbb{W}_{q,d}}\mathcal{H}_{\bm{j}}^{q}$, so we can
find $\bm{j}_{x}\in\mathbb{W}_{q,d}$ such that
$x\in\mathcal{H}_{\bm{j}_{x}}^{q}$. Then
$x\notin\mathcal{X}_{\tau}(\eta_{q,\bm{j}_{x}})$, so

$\displaystyle\mathbb{P}_{P_{q,\ast}}\bigl{(}x\in\hat{A}(\mathcal{D})\bigr{)}$
$\displaystyle\leq\mathbb{P}_{P_{q,\bm{j}_{x}}}\bigl{(}x\in\hat{A}(\mathcal{D})\bigr{)}+\mathrm{TV}\bigl{(}P_{q,\ast}^{n},P_{q,\bm{j}_{x}}^{n}\bigr{)}$
$\displaystyle\leq\mathbb{P}_{P_{q,\bm{j}_{x}}}\bigl{(}\hat{A}\nsubseteq\mathcal{X}_{\tau}(\eta_{q,\bm{j}_{x}})\bigr{)}+\sqrt{\frac{n\nu^{2}d}{q^{d-1}\sigma^{2}}}\leq\alpha+\sqrt{\frac{n\nu^{2}d}{q^{d-1}\sigma^{2}}}.$

Hence, by Fubini’s theorem,

$\displaystyle\mathbb{E}_{P_{q,\ast}}\bigl{\\{}\mu_{q}\bigl{(}\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}$
$\displaystyle=\mathbb{E}_{P_{q,\ast}}\biggl{(}\int_{\mathbb{R}^{d}}\mathbbm{1}_{\\{x\in\hat{A}(\mathcal{D})\\}}\,d\mu_{q}(x)\biggr{)}$
$\displaystyle=\int_{\mathbb{R}^{d}}\mathbb{P}_{P_{q,\ast}}\bigl{(}x\in\hat{A}(\mathcal{D})\bigr{)}\,d\mu_{q}(x)\leq\alpha+\sqrt{\frac{n\nu^{2}d}{q^{d-1}\sigma^{2}}}.$

By our choice of $\eta_{q,\ast}$, we have
$\mathcal{X}_{\tau}(\eta_{q,\ast})=\mathbb{R}^{d}$, and hence

$\displaystyle\mathbb{E}_{P_{q,\ast}}\bigl{\\{}\mu_{q}\bigl{(}\mathcal{X}_{\tau}(\eta_{\ast})\setminus\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}$
$\displaystyle=1-\mathbb{E}_{P_{q,\ast}}\bigl{\\{}\mu_{q}\bigl{(}\hat{A}(\mathcal{D})\bigr{)}\bigr{\\}}\geq
1-\alpha-\sqrt{\frac{n\nu^{2}d}{q^{d-1}\sigma^{2}}}.$

The result follows by taking an infimum over
$\hat{A}\in\hat{\mathcal{A}}_{n}(\tau,\alpha,\mathcal{P}^{\prime})$, and then
letting $q\rightarrow\infty$. ∎

###### Proof of Proposition 6.

Fix
$P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)$
with marginal distribution $\mu$ on $\mathbb{R}^{d}$ and regression function
$\eta$, and let $C:=2\cdot 3^{3d+1}\cdot(1+d^{1/2})^{d+1}\cdot\theta^{2}\geq
1$. Fix $\xi\in(0,1]$, and let $r:=2\xi/C\in(0,1]$. Let
$T\subseteq\mathcal{X}_{\tau+\lambda r^{\gamma}}(\eta)$ be as in Lemma 15, so
that, by that same lemma,

$\displaystyle\mu\bigl{(}\eta^{-1}([\tau,\tau+\lambda\xi^{\gamma}/C^{\gamma}])\bigr{)}$
$\displaystyle=\mu\bigl{(}\eta^{-1}([\tau,\tau+\lambda(r/2)^{\gamma}])\bigr{)}\leq\mu\bigl{(}\eta^{-1}\bigl{(}[\tau,\tau+\lambda
r^{\gamma})\bigr{)}\bigr{)}$
$\displaystyle=\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\mathcal{X}_{\tau+\lambda
r^{\gamma}}(\eta)\bigr{)}\leq\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus
T\bigr{)}$ $\displaystyle\leq
3^{3d+1}\cdot(1+d^{1/2})^{d+1}\cdot\theta^{2}\cdot r=\xi,$

as required. ∎

###### Proof of Theorem 7.

Let us define $C:=3^{3d+1+1/d}\cdot(1+d^{1/2})^{d+1}\cdot\theta^{2}\cdot
C_{\circ}$, where

$\displaystyle C_{\circ}$ $\displaystyle:=\bigl{(}2^{6}\theta\log(4\cdot
9^{d}\cdot\theta)\bigr{)}^{1/d}\geq\bigl{(}2^{4}\theta\cdot\log(4\cdot
9^{d}\cdot\theta)\bigr{)}^{1/d}\vee(175\cdot\theta)^{1/(2\gamma+d)}.$

Further, let

$r:=C_{\circ}\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha\wedge\delta}\Bigr{)}\biggr{)}^{1/(2\gamma+d)}+\biggl{(}\frac{\log_{+}(m/\delta)}{m}\biggr{)}^{1/d}\biggr{\\}}.$

Since $C\geq C_{\circ}$, the first result is immediate if $r>1$. We therefore
assume henceforth that $r\leq 1$ (so in particular,
$n\lambda^{2}\geq\sigma^{2}$). Observe that

$\displaystyle m\cdot r^{d}\geq C_{\circ}^{d}\cdot\log_{+}(m/\delta)$
$\displaystyle\geq 2^{4}\theta\cdot\log(4\cdot
9^{d}\cdot\theta)\cdot\log_{+}(m^{(d-1)/d}/\delta)$ $\displaystyle\geq
8\theta\bigl{\\{}\log(4\cdot
9^{d}\cdot\theta)+\log(r^{-(d-1)}/\delta)\bigr{\\}}=8\theta\log(4\cdot
9^{d}\cdot\theta\cdot r^{-(d-1)}/\delta),$

since $r\geq m^{-1/d}$ and so $m^{(d-1)/d}\geq r^{-(d-1)}$. Now, let
$\bigl{(}(S^{0}_{j},S^{1}_{j})\bigr{)}_{j\in[q]}$ be the hypercubes in Lemma
15 and let $(\Omega_{0,j,k})_{j\in[q],k\in\\{0,1\\}}$ be the events in Lemma
16. Then on $\bigcap_{j\in[q]}\Omega_{0,j,1}$, we have for each $j\in[q]$ that
there exists $i_{j}\in[m]$ with $X_{i_{j}}\in S_{j}^{1}$. We extend
$\\{X_{i_{1}},\ldots,X_{i_{q}}\\}$ to a maximal set
$\\{X_{i_{1}},\ldots,X_{i_{\ell}}\\}$ with $\ell\in\\{q,q+1,\ldots,m\\}$ such
that
$X_{i_{q+1}},\ldots,X_{i_{\ell}}\in\bigcup_{j=1}^{q}\bigl{\\{}x\in\mathbb{R}^{d}:X_{i_{j}}\preccurlyeq
x\bigr{\\}}$. Note that since $S_{j}^{1}\succcurlyeq S_{j}^{0}$ for every
$j\in[q]$, for every $s\in[\ell]$ there exists $j_{s}\in[q]$ such that
$\\{X_{i_{s}}\\}\succcurlyeq S_{j_{s}}^{0}$. For $s\in[\ell]$ and
$x\in\mathbb{R}$, write $r_{s}:=\sup_{x^{\prime}\in
S_{j_{s}}^{0}}\|x^{\prime}-X_{i_{s}}\|_{\infty}$,
$\mathcal{I}_{r_{s}}(x):=\\{i\in[n]:X_{i}\preccurlyeq
x,\|X_{i}-x\|_{\infty}\leq r_{s}\\}$, $n_{s}:=|\mathcal{I}_{r_{s}}(x)|$ and

$\hat{p}^{r_{s}}_{\sigma,\tau}(x,\mathcal{D}):=5.2\exp\biggl{\\{}-\frac{\max\bigl{(}\sum_{i\in\mathcal{I}_{r_{s}}(x)}Y_{i}-\tau
n_{s},0\bigr{)}^{2}}{2.0808\sigma^{2}n_{s}}+\frac{\log\log(2n_{s})}{0.72}\biggr{\\}}.$

By the choice of $r$, we have on
$\bigcap_{j\in[q],k\in\\{0,1\\}}\Omega_{0,j,k}$ that

$\displaystyle\min_{s\in[\ell]}|\mathcal{I}_{r_{s}}(X_{i_{s}})|=\min_{j\in[q]}|\mathcal{I}_{r_{j}}(X_{i_{j}})|$
$\displaystyle\geq\min_{j\in[q]}\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}\in
S_{j}^{0}\\}}\geq\frac{nr^{d}}{2\theta}$
$\displaystyle\geq\frac{C_{\circ}^{2\gamma+d}\cdot\sigma^{2}}{2\cdot\theta\cdot\lambda^{2}\cdot
r^{2\gamma}}\cdot\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha\wedge\delta}\Bigr{)}$
$\displaystyle\geq\frac{2\cdot\sigma^{2}}{\lambda^{2}\cdot r^{2\gamma}}\cdot
4.2\cdot 5.2\cdot
2\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha\wedge\delta}\Bigr{)}$
$\displaystyle\geq\frac{2\sigma^{2}}{\lambda^{2}\cdot
r^{2\gamma}}\biggl{\\{}4.2\log\Bigl{(}\frac{5.2m}{\alpha\wedge\delta}\Bigr{)}+3\log(2\log_{+}n)\biggr{\\}}$
$\displaystyle\geq\frac{2\sigma^{2}}{\lambda^{2}\cdot
r^{2\gamma}}\biggl{\\{}2\log\Bigl{(}\frac{2m}{\delta}\Bigr{)}+2.0808\log\Bigl{(}\frac{5.2m}{\alpha}\Bigr{)}+3\log\log(2n)\biggr{\\}},$

where the last two inequalities follow from Lemma 36 _(i)_. Let
$\bigl{(}\Omega_{1,s}(\cdot)\bigr{)}_{s\in[\ell]}$ be as in Lemma 17. Then, on
$\Omega_{*}:=\bigcap_{j\in[q],k\in\\{0,1\\}}\Omega_{0,j,k}\cap\bigcap_{s\in[\ell]}\Omega_{1,s}(X_{i_{s}})$,
we have

$\max_{s\in[\ell]}\hat{p}_{\sigma,\tau}(X_{i_{s}},\mathcal{D})\leq\max_{s\in[\ell]}\hat{p}_{\sigma,\tau}^{r_{s}}(X_{i_{s}},\mathcal{D})\leq\frac{\alpha}{m}.$
(9)

We claim that on $\Omega_{*}$, we have
$I_{1}:=\\{i_{1},\ldots,i_{\ell}\\}\subseteq\mathcal{R}^{\mathrm{ISS}}_{\alpha}\bigl{(}\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m}),\bigl{(}\hat{p}_{\sigma,\tau}(X_{i},\mathcal{D})\bigr{)}_{i\in[m]}\bigr{)}$,
and prove this by contradiction. First, for
$([m],E,\bm{w}):=\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m})$, denote for
brevity $G:=([m],E)=\mathcal{G}(\mathcal{D}_{X,m})$ and $F:=([m],\\{e\in
E:w_{e}=1\\})=\mathcal{G}_{\mathrm{F}}(\mathcal{D}_{X,m})$ as in Algorithm 1.
Moreover, define $\alpha(\cdot,\cdot)$ as in (5) in the proof of Lemma 2 and
write
$R:=\mathcal{R}^{\mathrm{ISS}}_{\alpha}\bigl{(}\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m}),\bigl{(}\hat{p}_{\sigma,\tau}(X_{i},\mathcal{D})\bigr{)}_{i\in[m]}\bigr{)}$.
Suppose now for a contradiction that there exists $s\in[\ell]$ such that
$i_{s}\notin R$ and write
$I_{*}:=\\{i\in[m]:\alpha(i,R)>0\\}\subseteq[m]\setminus R$. Now $I_{1}$ is
$G$-upper by construction and hence also $F$-upper. Consequently, there exists
$s^{\prime}\in[\ell]$ with $i_{s^{\prime}}\in
I_{*}\cap\bigl{(}\\{i_{s}\\}\cup\operatorname{\mathrm{an}}_{F}(i_{s})\bigr{)}\subseteq
I_{1}\setminus R$ which in turn necessitates by Algorithm 1 that
$\hat{p}_{\sigma,\tau}(X_{i_{s^{\prime}}},\mathcal{D})>\alpha(i_{s^{\prime}},R)$.
Moreover, as $R$ is also $G$-upper by construction and therefore $F$-upper, we
deduce that
$\bigl{(}\\{i_{s^{\prime}}\\}\cup\operatorname{\mathrm{de}}_{F}(i_{s^{\prime}})\bigr{)}\cap
R=\emptyset$ while
$\bigl{(}\\{i_{s^{\prime}}\\}\cup\operatorname{\mathrm{de}}_{F}(i_{s^{\prime}})\bigr{)}\cap
L(F)\neq\emptyset$, so that
$\bigl{|}\bigl{(}\\{i_{s^{\prime}}\\}\cup\operatorname{\mathrm{de}}_{F}(i_{s^{\prime}})\bigr{)}\cap
L(F)\setminus R\bigr{|}\geq 1$. Thus, by (9),

$\alpha(i_{s^{\prime}},R)=\frac{\bigl{|}\bigl{(}\\{i_{s^{\prime}}\\}\cup\operatorname{\mathrm{de}}_{F}(i_{s^{\prime}})\bigr{)}\cap
L(F)\setminus R\bigr{|}}{|L(F)\setminus
R|}\cdot\alpha\geq\frac{\alpha}{m}\geq\hat{p}_{\sigma,\tau}(X_{i_{s^{\prime}}},\mathcal{D}),$

which establishes our contradiction and therefore proves the claim. It follows
that on $\Omega_{*}$, we have
$\\{i_{1},\ldots,i_{q}\\}\subseteq\mathcal{R}^{\mathrm{ISS}}_{\alpha}\bigl{(}\mathcal{G}_{\mathrm{W}}(\mathcal{D}_{X,m}),\bigl{(}\hat{p}_{\sigma,\tau}(X_{i},\mathcal{D})\bigr{)}_{i\in[m]}\bigr{)}$,
so taking the Borel measurable
$T\subseteq\mathcal{X}_{\tau}(\eta)\cap\mathrm{supp}(\mu)$ from Lemma 15, we
have

$T\subseteq\bigcup_{j=1}^{q}\bigl{\\{}x\in\mathbb{R}^{d}:X_{i_{j}}\preccurlyeq
x\bigr{\\}}\subseteq\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D}).$

Hence, on $\Omega_{*}$,

$\displaystyle\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\bigr{)}\leq\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus
T\bigr{)}\leq 3^{3d+1}\cdot(1+d^{1/2})^{d+1}\cdot\theta^{2}\cdot r,$

where the second inequality follows from Lemma 15. Thus, for any $m\in[n]$, we
conclude by Lemmas 16 and 17 that

$\displaystyle\mathbb{P}_{P}\biggl{[}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)$
$\displaystyle\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\bigr{)}\\!>1\wedge\frac{C}{3^{1/d}}\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha\wedge\delta}\Bigr{)}\biggr{)}^{1/(2\gamma+d)}\\!\\!\\!+\biggl{(}\frac{\log_{+}(m/\delta)}{m}\biggr{)}^{1/d}\biggr{\\}}\biggr{]}$
$\displaystyle=\mathbb{P}_{P}\Bigl{\\{}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m}(\mathcal{D})\bigr{)}>3^{3d+1}\cdot(1+d^{1/2})^{d+1}\cdot\theta^{2}\cdot
r\Bigr{\\}}\leq\mathbb{P}_{P}(\Omega_{*}^{c})\leq\delta.$

This proves the tail bound in the first part of the theorem. We deduce the
bound in expectation by integrating over $\delta\in(0,1)$. First observe that

$\displaystyle\int_{0}^{1}\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha\wedge\delta}\Bigr{)}\,d\delta\leq\int_{0}^{1}\log\biggl{(}\frac{(m\log_{+}n)\vee
e}{\alpha\wedge\delta}\biggr{)}\,d\delta$
$\displaystyle=\log\biggl{(}\frac{(m\log_{+}n)\vee e}{\alpha}\biggr{)}+\alpha$
$\displaystyle\leq 3\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha}\Bigr{)}.$ (10)

Hence, by Jensen’s inequality,

$\displaystyle\int_{0}^{1}\biggl{\\{}\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha\wedge\delta}\Bigr{)}\biggr{\\}}^{1/(2\gamma+d)}\,d\delta\leq
3^{1/(2\gamma+d)}\biggl{\\{}\log_{+}\Bigl{(}\frac{m\log_{+}n}{\alpha}\Bigr{)}\biggr{\\}}^{1/(2\gamma+d)}.$
(11)

At the same time, by Jensen’s inequality again,

$\displaystyle\int_{0}^{1}\log^{1/d}_{+}\Bigl{(}\frac{m}{\delta}\Bigr{)}\,d\delta$
$\displaystyle\leq\biggl{\\{}\int_{0}^{1}\log_{+}\Bigl{(}\frac{m}{\delta}\Bigr{)}\,d\delta\biggr{\\}}^{1/d}\leq\biggl{\\{}\int_{0}^{1}\log\Bigl{(}\frac{m\vee
e}{\delta}\Bigr{)}\,d\delta\biggr{\\}}^{1/d}$
$\displaystyle=\bigl{(}\log_{+}m+1\bigr{)}^{1/d}\leq 2^{1/d}\log^{1/d}_{+}m,$
(12)

whence the result follows as $3^{1/(2\gamma+d)}\vee 2^{1/d}\leq 3^{1/d}$. ∎

###### Proof of Corollary 8.

If $\lambda\geq\sigma$, then $m_{0}=n$, and the result follows from Theorem 7.
On the other hand, if $\lambda<\sigma$, then $m_{0}=\lceil
n\lambda^{2}/\sigma^{2}\rceil\leq n$. As in the proof of Theorem 7, we may
assume that $n\lambda^{2}\geq\sigma^{2}$, so that

$\biggl{(}\frac{\log_{+}(m_{0}/\delta)}{m_{0}}\biggr{)}^{1/d}\leq\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{2n\lambda^{2}\log_{+}n}{\sigma^{2}(\alpha\wedge\delta)}\Bigr{)}\biggr{)}^{1/d}\leq
2\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{n\lambda^{2}\log_{+}n}{\sigma^{2}(\alpha\wedge\delta)}\Bigr{)}\biggr{)}^{1/d}.$

Since the result is clear if
$\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\bigl{(}\frac{n\lambda^{2}\log_{+}n}{\sigma^{2}(\alpha\wedge\delta)}\bigr{)}>1$,
we may further assume that this quantity is at most 1. But then

$\biggl{(}\frac{\log_{+}(m_{0}/\delta)}{m_{0}}\biggr{)}^{1/d}\leq
2\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{n\lambda^{2}\log_{+}n}{\sigma^{2}(\alpha\wedge\delta)}\Bigr{)}\biggr{)}^{1/(2\gamma+d)}.$

The $\log_{+}\bigl{(}m_{0}/(\alpha\wedge\delta)\bigr{)}$ term can be handled
similarly (in fact, in a slightly simpler way), so

$\displaystyle\mathbb{P}_{P}\biggl{[}\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus\hat{A}^{\mathrm{ISS}}_{\sigma,\tau,\alpha,m_{0}}(\mathcal{D})\bigr{)}$
$\displaystyle>1\wedge\frac{4C}{3^{1/d}}\biggl{\\{}\biggl{(}\frac{\sigma^{2}}{n\lambda^{2}}\log_{+}\Bigl{(}\frac{n\lambda^{2}\log_{+}n}{\sigma^{2}(\alpha\wedge\delta)}\Bigr{)}\biggr{)}^{1/(2\gamma+d)}$
$\displaystyle\hskip
142.26378pt+\biggl{(}\frac{\log_{+}(n/\delta)}{n}\biggr{)}^{1/d}\biggr{\\}}\biggr{]}\leq\delta.$

We can then deduce the expectation bound using the same techniques as in the
proof of Theorem 7, and the result follows. ∎

######  Lemma 15.

Let $d\in\mathbb{N}$, $\tau\in\mathbb{R}$, $\sigma,\gamma,\lambda>0$,
$\theta\in(1,\infty)$ and take
$P\in\mathcal{P}_{\mathrm{Mon},d}(\sigma)\cap\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)$.
Given $r\leq 1$, there exist $q\leq\lfloor 9^{d}\cdot\theta\cdot
r^{-(d-1)}\rfloor\in\mathbb{N}$ and pairs of hypercubes
$\bigl{(}(S^{0}_{j},S^{1}_{j})\bigr{)}_{j\in[q]}\in\bigl{(}\mathrm{Pow}(\mathbb{R}^{d})\times\mathrm{Pow}(\mathbb{R}^{d})\bigr{)}^{q}$
such that $S^{0}_{j}\preccurlyeq S^{1}_{j}$,
$S^{0}_{j}\subseteq\mathcal{X}_{\tau+\lambda\cdot r^{\gamma}}(\eta)$,
$\mu(S^{0}_{j})\wedge\mu(S^{1}_{j})\geq\theta^{-1}\cdot r^{d}$, along with a
Borel measurable set $T\subseteq\mathcal{X}_{\tau+\lambda
r^{\gamma}}(\eta)\cap\mathrm{supp}(\mu)\subseteq\mathcal{X}_{\tau}(\eta)\cap\mathrm{supp}(\mu)$
such that for every $x\in T$ there exists $j_{x}\in[q]$ with
$S^{1}_{j_{x}}\preccurlyeq\\{x\\}$, and

$\displaystyle\mu\bigl{(}\mathcal{X}_{\tau}(\eta)\setminus T\bigr{)}\leq
3^{3d+1}\cdot(1+d^{1/2})^{d+1}\cdot\theta^{2}\cdot r.$

###### Proof.

Without loss of generality, assume that
$\mathrm{supp}(\mu)\cap\mathcal{X}_{\tau}(\eta)\neq\emptyset$. Write
$V_{1}:=\\{s\cdot\bm{1}_{d}:s\in\mathbb{R}\\}$ with orthogonal complement
$V_{1}^{\perp}$, and write $\Pi_{V_{1}}:\mathbb{R}^{d}\rightarrow V_{1}$ and
$\Pi_{V_{1}^{\perp}}:\mathbb{R}^{d}\rightarrow V_{1}^{\perp}$ for the
orthogonal projections onto $V_{1}$ and $V_{1}^{\perp}$ respectively. Fix
$r\leq 1$. We begin by showing that
$\Pi_{V_{1}^{\perp}}\bigl{(}\mathrm{supp}(\mu)\cap\mathcal{X}_{\tau}(\eta)\bigr{)}$
can be covered by $q\leq\lfloor 3^{d-1}\cdot 2^{3d/2}\cdot\theta\cdot
r^{-(d-1)}\rfloor$ closed Euclidean balls of radius $r$. To see this, first
let $(z_{\ell})_{\ell\in[p]}$ with $p\in\mathbb{N}\cup\\{\infty\\}$ be a
maximal sequence in $\mathrm{supp}(\mu)\cap\mathcal{X}_{\tau}(\eta)$ with
$\|z_{j}-z_{j^{\prime}}\|_{\infty}>2^{-1/2}$ for $j\neq j^{\prime}$. Then

$\mathrm{supp}(\mu)\cap\mathcal{X}_{\tau}(\eta)\subseteq\bigcup_{j=1}^{p}{B}_{\infty}(z_{j},2^{-1/2})\subseteq\bigcup_{j=1}^{p}{B}_{2}(z_{j},(d/2)^{1/2}).$

Moreover, since $\bigl{(}{B}_{\infty}(z_{j},2^{-3/2})\bigr{)}_{j\in[p]}$ are
disjoint and $P\in\mathcal{P}_{\mathrm{Reg},d}(\tau,\theta,\gamma,\lambda)$,
we have

$1\geq\sum_{j=1}^{p}\mu\bigl{(}{B}_{\infty}(z_{j},2^{-3/2})\bigr{)}\geq\frac{p}{2^{3d/2}\theta},$

so $p\leq 2^{3d/2}\theta$. Each projected Euclidean ball
$\Pi_{V_{1}^{\perp}}\bigl{(}{B}_{2}(z_{j},(d/2)^{1/2})\bigr{)}$ can in turn be
covered by $(3/r)^{d-1}$ closed Euclidean balls666Here we use the fact that
given any $d^{\prime}\in\mathbb{N}$ and $\epsilon\in(0,1]$, the closed
Euclidean unit ball in $\mathbb{R}^{d^{\prime}}$ may be covered by at most
$(3/\epsilon)^{d^{\prime}}$ closed Euclidean balls of radius $\epsilon$.
Indeed, if $w_{1},\ldots,w_{M}\in B_{2,d^{\prime}}(0,1)$ satisfy
$\|w_{j}-w_{j^{\prime}}\|_{2}>\epsilon$ for $j\neq j^{\prime}$, then
$\cup_{j\in M}B_{2,d^{\prime}}(w_{j},\epsilon/2)\subseteq
B_{2,d^{\prime}}(0,1+\epsilon/2)\subseteq B_{2,d^{\prime}}(0,3/2)$, so
$M(\epsilon/2)^{d^{\prime}}\leq(3/2)^{d^{\prime}}$, and the result follows. of
radius $(d/2)^{1/2}r\leq(d/2)^{1/2}$. It follows that we can find a sequence
$x_{1},\ldots,x_{q}\in V_{1}^{\perp}$ with $q\leq 3^{d-1}\cdot
2^{3d/2}\cdot\theta\cdot r^{-(d-1)}$ and
$\Pi_{V_{1}^{\perp}}\bigl{(}\mathrm{supp}(\mu)\cap\mathcal{X}_{\tau}(\eta)\bigr{)}\subseteq\bigcup_{j\in[q]}\Pi_{V_{1}^{\perp}}\bigl{(}{B}_{2}(x_{j},(d/2)^{1/2}r)\bigr{)}$.
We deduce that

$\displaystyle\mathrm{supp}(\mu)\cap\mathcal{X}_{\tau}(\eta)$
$\displaystyle\subseteq\bigcup_{j\in[q]}\Pi_{V_{1}^{\perp}}\bigl{(}{B}_{2}(x_{j},(d/2)^{1/2}r)\bigr{)}\oplus\bigcup_{\ell\in\mathbb{Z}}\Pi_{V_{1}}\bigl{(}{B}_{2}(\ell
r\cdot\bm{1}_{d},(d/2)^{1/2}r)\bigr{)}$
$\displaystyle\subseteq\bigcup_{(j,\ell)\in[q]\times\mathbb{Z}}{B}_{2}(x_{j}+\ell
r\cdot\bm{1}_{d},d^{1/2}r)$
$\displaystyle\subseteq\bigcup_{(j,\ell)\in[q]\times\mathbb{Z}}{B}_{\infty}(x_{j}+\ell
r\cdot\bm{1}_{d},d^{1/2}r).$

Now, for each $j\in[q]$, choose

$\displaystyle\ell_{0,j}$
$\displaystyle:=\min\bigl{\\{}\ell\in\mathbb{Z}:{B}_{\infty}(x_{j}+\ell
r\cdot\bm{1}_{d},d^{1/2}r)\cap\mathcal{X}_{\tau}(\eta)\cap\mathrm{supp}(\mu)\neq\emptyset\bigr{\\}},$

with the convention that $\min\emptyset:=\infty$, and the minimum of a set
with no lower bound is $-\infty$. Note that since
$\mathrm{supp}(\mu)\cap\mathcal{X}_{\tau}(\eta)\subseteq\bigcup_{j^{\prime}\in[p]}{B}_{\infty}(z_{j^{\prime}},2^{-1/2})$,
we must have $\ell_{0,j}\in\mathbb{Z}\cup\\{\infty\\}$. Let
$\mathcal{J}_{0}:=\\{j\in[q]:\ell_{0,j}\in\mathbb{Z}\\}$. By construction, for
each $j\in\mathcal{J}_{0}$ there exists
$z_{0,j}\in{B}_{\infty}(x_{j}+\ell_{0,j}r\cdot\bm{1}_{d},d^{1/2}r)\cap\mathcal{X}_{\tau}(\eta)\cap\mathrm{supp}(\mu)$.
Hence
$z_{0,j}+r\cdot\bm{1}_{d}\in{B}_{\infty}(z_{0,j},r)\cap\mathcal{X}_{\tau+\lambda\cdot