# Inference in high-dimensional online changepoint detection

Yudong Chen∗,†, Tengyao Wang† and Richard J. Samworth∗
∗ Statistical Laboratory, University of Cambridge
† Department of Statistics, London School of Economics

(())

###### Abstract

We introduce and study two new inferential challenges associated with the
sequential detection of change in a high-dimensional mean vector. First, we
seek a confidence interval for the changepoint, and second, we estimate the
set of indices of coordinates in which the mean changes. We propose an online
algorithm that produces an interval with guaranteed nominal coverage, and
whose length is, with high probability, of the same order as the average
detection delay, up to a logarithmic factor. The corresponding support
estimate enjoys control of both false negatives and false positives.
Simulations confirm the effectiveness of our methodology, and we also
illustrate its applicability on both US excess deaths data from 2017–2020 and
S&P 500 data from the 2007–2008 financial crisis.

##  1 Introduction

The real-time monitoring of evolving processes has become a characteristic
feature of 21st century life. Watches and defibrillators track health data,
Covid-19 case numbers are reported on a daily basis and financial decisions
are made continuously based on the latest market movements. Given that changes
in the dynamics of such processes are frequently of great interest, it is
unsurprising that the area of changepoint detection has undergone a
renaissance over the last 5–10 years.

One of the features of modern datasets that has driven much of the recent
research in changepoint analysis is high dimensionality, where we monitor many
processes simultaneously, and seek to borrow strength across the different
series to identify changepoints. The nature of series that are tracked in
applications, as well as the desire to evade to the greatest extent possible
the curse of dimensionality, means that it is commonly assumed that the signal
of interest is relatively sparse, in the sense that only a small proportion of
the constituent series undergo a change. Furthermore, the large majority of
these works have focused on the retrospective (or _offline_) challenges of
detecting and estimating changes after seeing all of the available data (e.g.
Chan and Walther, 2015; Cho and Fryzlewicz, 2015; Jirak, 2015; Cho, 2016; Soh
and Chandrasekaran, 2017; Wang and Samworth, 2018; Enikeeva and Harchaoui,
2019; Padilla et al., 2019; Kaul et al., 2021; Follain et al., 2021; Liu et
al., 2021; Londschien et al., 2021; Rinaldo et al., 2021). Nevertheless, the
related problem where one observes data sequentially and seeks to declare
changes as soon as possible after they have occurred, is nowadays receiving
increasing attention (e.g. Kirch and Stoehr, 2019; Dette and Gösmann, 2020;
Gösmann et al., 2020; Chen et al., 2021; Yu et al., 2021b). Although the focus
of our review here has been on recent developments, including finite-sample
results in multivariate and high-dimensional settings, we also mention that
changepoint analysis has a long history (e.g. Page, 1954). Entry points to
this classical literature include Csörgő and Horváth (1997) and Horváth and
Rice (2014). For univariate data, sequential changepoint detection is also
studied under the banner of statistical process control (Duncan, 1952;
Tartakovsky et al., 2014). In the field of high-dimensional statistical
inference more generally, uncertainty quantification has become a major theme
over the last decade, originating with influential work on the debiased Lasso
in (generalised) linear models (Javanmard and Montanari, 2014; van de Geer et
al., 2014; Zhang and Zhang, 2014), and subsequently developed in other
settings (e.g. Janková and van de Geer, 2015; Yu et al., 2021a).

The aim of this paper is to propose methods to address two new inferential
challenges associated with the high-dimensional, sequential detection of a
sparse change in mean. The first is to provide a confidence interval for the
location of the changepoint, while the second is to estimate the signal set of
indices of coordinates that undergo the change. Despite the importance of
uncertainty quantification and signal support recovery in changepoint
applications, neither of these problems has previously been studied in the
multivariate sequential changepoint detection literature, to the best of our
knowledge. Of course, one option here would be to apply an offline confidence
interval construction after a sequential procedure has declared a change.
However, this would be to ignore the essential challenge of the sequential
nature of the problem, whereby one wishes to avoid storing all historical
data, to enable inference to be carried out in an _online_ manner. By this we
mean that the computational complexity for processing each new observation, as
well as the storage requirements, should depend only on the number of bits
needed to represent the new data point observed111Here, we ignore the errors
in rounding real numbers to machine precision; thus, we do not distinguish
between continuous random variables and quantised versions where the data have
been rounded to machine precision.. The online requirement turns out to impose
severe restrictions on the class of algorithms available to the practitioner,
and lies at the heart of the difficulty of the problem.

To give a brief outline of our construction of a confidence interval with
guaranteed $(1-\alpha)$-level coverage, consider for simplicity the univariate
setting, where $(X_{n})_{n\in\mathbb{N}}$ form a sequence of independent
random variables with
$X_{1},\ldots,X_{z}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathcal{N}(0,1)$
and
$X_{z+1},X_{z+2},\ldots\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathcal{N}(\theta,1)$.
Without loss of generality, we assume that $\theta>0$. Suppose that $\theta$
is known to be at least $b>0$ and, for $n\in\mathbb{N}$, let222In the case of
a tie, we choose the smallest $h$ achieving the minimum.

$t_{n,b}:=\operatorname*{argmax}_{0\leq h\leq
n}\sum_{i=n-h+1}^{n}(X_{i}-b/2).$ (1)

Since $\sum_{i=n-h+1}^{n}(X_{i}-b/2)$ can be viewed as the likelihood ratio
statistic for testing the null of $\mathcal{N}(0,1)$ against the alternative
of $\mathcal{N}(b,1)$ using $X_{n-h+1},\ldots,X_{n}$, the quantity $t_{n,b}$
is the tail length for which the likelihood ratio statistic is maximised. If
$N$ is the stopping time defining a good sequential changepoint detection
procedure, then, intuitively, $N-t_{N,b}$ should be close to the true
changepoint location $z$, and almost pivotal. This motivates the construction
of a confidence interval of the form
$\bigl{[}\max\bigl{\\{}N-t_{N,b}-g(\alpha,b),0\bigr{\\}},N\bigr{]}$, where we
control the tail probability of the distribution of $N-t_{N,b}$ to choose
$g(\alpha,b)$ so as to ensure the desired coverage. In the multivariate case,
considerable care is required to handle the post-selection nature of the
inferential problem, as well as to determine an appropriate left endpoint for
the confidence interval. For this latter purpose, we only assume a lower bound
on the Euclidean norm of the vector of mean change, and employ a delicate
multivariate and multiscale aggregation scheme; see Section 2 for details.

In terms of the base sequential changepoint detection procedures, we focus on
the ocd algorithm (short for online changepoint detection) introduced by Chen
et al. (2021), as well as its variant ocd′, which provides guarantees on both
the average and worst-case detection delays, subject to a guarantee on the
_patience_ , or average false alarm rate under the null hypothesis of no
change. Crucially, these are both online algorithms. Our confidence intervals,
which we correspondingly denote ocd_CI and ocd_CI′, inherit this same online
property, thereby making them applicable even in very high-dimensional
settings and where changes may be rare, so that we may need to see many new
data points before declaring a change.

In Section 3 we study the theoretical performance of the ocd_CI′ procedure. In
particular, we prove in Theorem 1 that, for a suitable choice of input
parameters, the confidence interval has at least nominal coverage. Moreover,
Theorem 2 ensures that, with high probability, its length is of the same order
as the average detection delay for the base ocd′ procedure, up to a
logarithmic factor. This is remarkable in view of the intrinsic challenge that
the better such a changepoint detection procedure performs, the fewer post-
change observations are available for inferential tasks.

A very useful byproduct of our ocd_CI methodology is that we obtain a natural
estimate of the set of signal coordinates (i.e. those that undergo change). In
Theorem 3, we prove that, with high probability, it is able both to recover
the effective support of the signal (see Section 3.1 for a formal definition),
and avoids noise coordinates.

Section 4 is devoted to a study of the numerical performance of our
methodological proposals. Our simulations confirm that the ocd_CI methodology
attains the desired coverage level across a wide range of parameter settings,
that the average confidence interval length is of comparable order to the
average detection delay and that our support recovery guarantees are validated
empirically. Moreover, in Sections 4.4.1 and 4.4.2, we illustrate the
practical utility of our methods by applying them to both excess death data
during the Covid-19 pandemic in the US and S&P 500 data during the 2007–2008
financial crisis.

Proofs are given in Section 5, with auxiliary results deferred to Section 6.
An R implementation of our methodology is available at
github.com/yudongchen88/ocd_CI.

We conclude this introduction with some notation used throughout the paper. We
write $\mathbb{N}_{0}$ for the set of all non-negative integers. For
$d\in\mathbb{N}$, we write $[d]:=\\{1,\ldots,d\\}$. Given $a,b\in\mathbb{R}$,
we denote $a\vee b:=\max(a,b)$ and $a\wedge b:=\min(a,b)$. For a set $S$, we
use $\mathbbm{1}_{S}$ and $|S|$ to denote its indicator function and
cardinality respectively. For a real-valued function $f$ on a totally ordered
set $S$, we write $\operatorname*{sargmax}_{x\in
S}f(x):=\min\operatorname*{argmax}_{x\in S}f(x)$ and
$\operatorname*{largmax}_{x\in S}f(x):=\max\operatorname*{argmax}_{x\in
S}f(x)$ for the smallest and largest maximisers of $f$ in $S$, and define
$\operatorname*{sargmin}_{x\in S}f(x)$ and $\operatorname*{largmin}_{x\in
S}f(x)$ analogously. For a vector
$v=\bigl{(}v^{1},\ldots,v^{M}\bigr{)}^{\top}\in\mathbb{R}^{M}$, we define
$\|v\|_{0}:=\sum_{i=1}^{M}\mathbbm{1}_{\\{v^{i}\neq 0\\}}$,
$\|v\|_{2}:=\bigl{\\{}\sum_{i=1}^{M}(v^{i})^{2}\bigr{\\}}^{1/2}$ and
$\|v\|_{\infty}:=\max_{i\in[M]}|v^{i}|$. In addition, for $j\in[M]$, we define
$\|v^{-j}\|_{2}:=\bigl{\\{}\sum_{i:i\neq j}(v^{i})^{2}\bigr{\\}}^{1/2}$. For a
matrix $A=(A^{i,j})\in\mathbb{R}^{d_{1}\times d_{2}}$ and $j\in[d_{2}]$, we
write
$A^{\bm{\cdot},j}:=\bigl{(}A^{1,j},\ldots,A^{d_{1},j}\bigr{)}^{\top}\in\mathbb{R}^{d_{1}}$
and
$A^{-j,j}:=\bigl{(}A^{1,j},\ldots,A^{j-1,j},A^{j+1,j}\ldots,A^{d_{1},j}\bigr{)}^{\top}\in\mathbb{R}^{d_{1}-1}$.
We use $\Phi(\cdot)$, $\bar{\Phi}(\cdot)$ and $\phi(\cdot)$ to denote the
distribution function, survivor function and density function of the standard
normal distribution respectively. For two real-valued random variables $U$ and
$V$, we write $U\geq_{\mathrm{st}}V$ or $V\leq_{\mathrm{st}}U$ if
$\mathbb{P}(U\leq x)\leq\mathbb{P}(V\leq x)$ for all $x\in\mathbb{R}$. We
adopt conventions that an empty sum is $0$ and that $\min\emptyset:=\infty$,
$\max\emptyset:=-\infty$.

##  2 Confidence interval construction and support estimation methodology

In the multivariate sequential changepoint detection problem, we observe
$p$-variate observations $X_{1},X_{2},\ldots$ in turn, and seek to report a
stopping time333Here and throughout, a stopping time is understood to be with
respect to the natural filtration, so that the event $\\{N=n\\}$ belongs to
the $\sigma$-algebra generated by $X_{1},\ldots,X_{n}$. $N$ by which we
believe a change has occurred. The focus of this work is on changes in the
mean of the underlying process, and we denote the time of the changepoint by
$z$. Moreover, since our primary interest is in high-dimensional settings, we
will also seek to exploit sparsity in the vector of mean change. Given
$\alpha\in(0,1)$, then, our primary goal is to construct a confidence interval
$\mathcal{C}\equiv\mathcal{C}(X_{1},\ldots,X_{N},\alpha)$ with the property
that $z\in\mathcal{C}$ with probability at least $1-\alpha$.

For $i\in\mathbb{N}$ and $j\in[p]$, let $X_{i}^{j}$ denote the $j$th
coordinate of $X_{i}$. The ocd algorithm of Chen et al. (2021), which forms
part of Algorithm 1, relies on a lower bound $\beta>0$ for the $\ell_{2}$-norm
of the vector of mean change and sets of signed scales $\mathcal{B}$ and
$\mathcal{B}_{0}$ defined in terms of $\beta$. From our perspective, the key
aspects of this multiscale algorithm are that, in addition to returning a
stopping time $N$ as output, it produces a matrix of residual tail lengths
$(t_{N,b}^{j})_{j\in[p],b\in\mathcal{B}\cup\mathcal{B}_{0}}$ with
$t_{N,b}^{j}:=\operatorname*{sargmax}_{0\leq h\leq
N}\sum_{i=N-h+1}^{N}(X_{i}^{j}-b/2)$ (similarly to (1)), an ‘anchor’
coordinate $\hat{j}\in[p]$, a signed anchor scale $\hat{b}\in\mathcal{B}$ and
a tail partial sum vector $A_{N,\hat{b}}^{\cdot,\hat{j}}\in\mathbb{R}^{p}$
with $j$th component
$A_{N,\hat{b}}^{j,\hat{j}}:=\sum_{i=N-t_{N,\hat{b}}^{\hat{j}}+1}^{N}X_{i}^{j}$.
The intuition is that the anchor coordinate and signed scale are chosen so
that the final $t_{N,\hat{b}}^{\hat{j}}$ observations provide the best
evidence among all of the residual tail lengths against the null hypothesis of
no change. Meanwhile, $A_{N,\hat{b}}^{\cdot,\hat{j}}$ aggregates the last
$t_{N,\hat{b}}^{\hat{j}}$ observations in each coordinate, thereby providing a
measure of the strength of this evidence against the null.

The main idea of our confidence interval construction is to seek to identify
coordinates with large post-change signal. To this end, observe when
$t_{N,\hat{b}}^{\hat{j}}$ is not too much larger than $N-z$, the quantity
$E_{N,\hat{b}}^{j,\hat{j}}:=A_{N,{\hat{b}}}^{j,\hat{j}}/(t_{N,{\hat{b}}}^{\hat{j}}\vee
1)^{1/2}$ should be centred close to
$\theta^{j}(t_{N,{\hat{b}}}^{\hat{j}})^{1/2}$ for
$j\in[p]\setminus\\{\hat{j}\\}$, with variance close to 1. Indeed, if
$\hat{j}$, $\hat{b}$, $N$ and $t_{N,\hat{b}}^{\hat{j}}$ were fixed, and if
$0<t_{N,\hat{b}}^{\hat{j}}\leq N-z$, then the former quantity would be
normally distributed around this centering value, with unit variance. The
random nature of these quantities, however, introduces a post-selection
inference aspect to the problem. Nevertheless, by choosing an appropriate
threshold value $d_{1}>0$, we can ensure that with high probability, when
$j\neq\hat{j}$ is a noise coordinate, we have
$|E_{N,\hat{b}}^{j,\hat{j}}|<d_{1}$, and when $j\neq\hat{j}$ is a coordinate
with sufficiently large signal, there exists a signed scale
$b\in(\mathcal{B}\cup\mathcal{B}_{0})\cap[-|\theta^{j}|,|\theta^{j}|]$, having
the same sign as $\theta^{j}$, for which
$\bigl{|}E_{N,\hat{b}}^{j,\hat{j}}\bigr{|}-|b|(t_{N,{\hat{b}}}^{\hat{j}})^{1/2}\geq
d_{1}$. In fact, such a signed scale, if it exists, can always be chosen to be
from $\mathcal{B}_{0}$. As a convenient byproduct, the set of indices $j$ for
which the latter inequality holds, which we denote as $\hat{\mathcal{S}}$,
forms a natural estimate of the set of coordinates in which the mean change is
large.

For each $j\in\hat{\mathcal{S}}$, there exists a largest scale
$b\in(\mathcal{B}\cup\mathcal{B}_{0})\cap(0,\infty)$ for which
$\bigl{|}E_{N,\hat{b}}^{j,\hat{j}}\bigr{|}-b(t_{N,{\hat{b}}}^{\hat{j}})^{1/2}\geq
d_{1}$. We denote the signed version of this quantity, where the sign is
chosen to agree with that of $E_{N,\hat{b}}^{j,\hat{j}}$, by $\tilde{b}^{j}$;
this can be regarded as a shrunken estimate of $\theta^{j}$, and therefore
plays the role of the lower bound $b$ from the univariate problem discussed in
the introduction. Finally, then, our confidence interval can be constructed as
the intersection over indices $j\in\hat{\mathcal{S}}$ of the confidence
interval from the univariate problem in coordinate $j$, with signed scale
$\tilde{b}^{j}$.

Pseudo-code for this ocd_CI confidence interval construction is given in
Algorithm 1, where we suppress the $n$ dependence on quantities that are
updated at each time step. The computational complexity per new observation,
as well as the storage requirements, of this algorithm are
$O\bigl{(}p^{2}\log(ep)\bigr{)}$ regardless of the observation history, so it
satisfies the condition to be an online algorithm, as discussed in the
introduction.

Input: $X_{1},X_{2},\ldots\in\mathbb{R}^{p}$ observed sequentially, $\beta>0$,
$a\geq 0$, $T^{\mathrm{diag}},T^{\mathrm{off}}>0$, $d_{1},d_{2}>0$

Set:
$b_{\min}=\frac{\beta}{\sqrt{2^{\lfloor\log_{2}(2p)\rfloor}\log_{2}(2p)}}$,
$\mathcal{B}_{0}=\\{\pm b_{\min}\\}$, $\mathcal{B}=\bigl{\\{}\pm
2^{\ell/2}b_{\min}:\ell=1,\ldots,\lfloor\log_{2}(2p)\rfloor\bigr{\\}}$, $n=0$,
$A_{b}=\mathbf{0}\in\mathbb{R}^{p\times p}$ and $t_{b}=0\in\mathbb{R}^{p}$ for
all $b\in\mathcal{B}\cup\mathcal{B}_{0}$

repeat

$n\leftarrow n+1$

observe new data vector $X_{n}$

for  _$(j,b)\in[p]\times(\mathcal{B}\cup\mathcal{B}_{0})$_ do

$t^{j}_{b}\leftarrow t^{j}_{b}+1$

$A^{\bm{\cdot},j}_{b}\leftarrow A^{\bm{\cdot},j}_{b}+X_{n}$

if  _$bA^{j,j}_{b}-b^{2}t^{j}_{b}/2\leq 0$_ then

$t^{j}_{b}\leftarrow 0$ and $A^{\bm{\cdot},j}_{b}\leftarrow 0$

$E_{b}^{\bm{\cdot},j}\leftarrow A^{\bm{\cdot},j}_{b}/\bigl{(}t^{j}_{b}\vee
1\bigr{)}^{1/2}$

$Q^{j}_{b}\leftarrow\sum_{j^{\prime}\in[p]\setminus\\{j\\}}(E_{b}^{j^{\prime},j})^{2}\mathbbm{1}_{\\{|E_{b}^{j^{\prime},j}|\geq
a\\}}$

$S^{\mathrm{diag}}\leftarrow\max_{(j,b)\in[p]\times(\mathcal{B}\cup\mathcal{B}_{0})}\bigl{(}bA^{j,j}_{b}-b^{2}t^{j}_{b}/2\bigr{)}$

$S^{\mathrm{off}}\leftarrow\max_{(j,b)\in[p]\times\mathcal{B}}Q_{b}^{j}$

until  _$S^{\mathrm{diag}}\geq T^{\mathrm{diag}}$ or $S^{\mathrm{off}}\geq
T^{\mathrm{off}}$_;

$(\hat{j},\hat{b})\leftarrow\operatorname*{argmax}_{(j,b)\in[p]\times\mathcal{B}}Q_{b}^{j}$

$\hat{\mathcal{S}}\leftarrow\Bigl{\\{}j\in[p]\setminus\\{\hat{j}\\}:\bigl{|}E_{\hat{b}}^{j,\hat{j}}\bigr{|}-b_{\min}(t_{\hat{b}}^{\hat{j}})^{1/2}\geq
d_{1}\Bigr{\\}}$

for  _$j\in\hat{\mathcal{S}}$_ do

$\tilde{b}^{j}\leftarrow\mathrm{sgn}\bigl{(}E_{\hat{b}}^{j,\hat{j}}\bigr{)}\max\Bigl{\\{}b\in(\mathcal{B}\cup\mathcal{B}_{0})\cap(0,\infty):\bigl{|}E_{\hat{b}}^{j,\hat{j}}\bigr{|}-b(t_{\hat{b}}^{\hat{j}})^{1/2}\geq
d_{1}\Bigr{\\}}$

Output: Confidence interval
$\mathcal{C}=\Bigl{[}\max\Bigl{\\{}n-\min_{j\in\hat{\mathcal{S}}}\Bigl{\\{}t_{\tilde{b}^{j}}^{j}+\frac{d_{2}}{(\tilde{b}^{j})^{2}}\Bigr{\\}},0\Bigr{\\}},n\Bigr{]}$

Algorithm 1 Pseudo-code for the confidence interval construction algorithm
ocd_CI

###  2.1 A slight variant of the ocd_CI algorithm

While our experience is that ocd_CI performs very well empirically, in our
theoretical analysis it turns out to be easier to study a slight variant of
this algorithm, denoted ocd_CI′. There are two main differences between the
algorithms. First, in ocd_CI, the base changepoint detection procedure is ocd,
while in ocd_CI′, we use the ocd′ procedure of Chen et al. (2021) instead.
This latter algorithm is designed to avoid difficulties caused by adversarial
pre-change observations that may lead to lengthy response delays for the ocd
procedure. In particular, for each $j\in[p]$ and $b\in\mathcal{B}$, instead of
using the final $t_{n,b}^{j}$ observations at time $n$ to construct test
statistics based on $A_{n,b}^{\bm{\cdot},j}$, the ocd′ procedure aggregates
over a reduced number $\tau_{n,b}^{j}$ of observations to obtain test
statistics based on $\Lambda_{n,b}^{\bm{\cdot},j}$, where $\tau_{n,b}^{j}$ is
constructed in an online manner to lie in the interval
$[t_{n,b}^{j}/2,3t_{n,b}^{j}/4]$ for $t_{n,b}^{j}\geq 2$. Even though the
reduced tail lengths may lead to a slight deterioration in empirical
performance, provided no change has been declared by time $z$, they guarantee
that from a later time of the form $z+O(b^{-2})$, the last $\tau_{n,b}^{j}$
observations consist entirely of post-change data.

Second, in ocd_CI′, we allow the practitioner to observe a further $\ell$
observations after the time of changepoint declaration, before constructing
the confidence interval. The additional observations are used to determine the
anchor coordinate $\hat{j}$ and scale $\hat{b}$, as well as the estimated
support $\hat{\mathcal{S}}$ and the estimated scale $\tilde{b}^{j}$ for each
$j\in\hat{\mathcal{S}}$. Thus, the extra sampling is used to guard against an
unusually early changepoint declaration that leaves very few post-change
observations for inference. Nevertheless, we will see in Theorem 1 below that
the ocd_CI′ confidence interval has guaranteed nominal coverage even with
$\ell=0$, so that additional observations are only used to control the length
of the interval. In fact, even for this latter aspect, the numerical evidence
presented in Section 4 indicates that $\ell=0$ provides confidence intervals
of reasonable length in practice. Similarly, Theorem 3 ensures that with high
probability, our support estimate $\hat{\mathcal{S}}$ contains no noise
coordinates (i.e. has false positive control) even with $\ell=0$, so that the
extra sampling is only used to provide false negative control. Pseudo-code for
the ocd_CI′ algorithm is given in Algorithm 2; its computational complexity
per new observation, and storage requirements, remain
$O\bigl{(}p^{2}\log(ep)\bigr{)}$.

Input: $X_{1},X_{2}\ldots\in\mathbb{R}^{p}$ observed sequentially, $\beta>0$,
$a\geq 0$, $T^{\mathrm{diag}},T^{\mathrm{off}}>0$, $d_{1},d_{2}>0$ and
$\ell\in\mathbb{N}_{0}$

Set:
$b_{\min}=\frac{\beta}{\sqrt{2^{\lfloor\log_{2}(2p)\rfloor}\log_{2}(2p)}}$,
$\mathcal{B}_{0}=\\{\pm b_{\min}\\}$, $\mathcal{B}=\bigl{\\{}\pm
2^{\ell/2}b_{\min}:\ell=1,\ldots,\lfloor\log_{2}(2p)\rfloor\bigr{\\}}$, $n=0$,
$A_{b}=\Lambda_{b}=\tilde{\Lambda}_{b}=\mathbf{0}\in\mathbb{R}^{p\times p}$
and $t_{b}=\tau_{b}=\tilde{\tau}_{b}=0\in\mathbb{R}^{p}$ for all
$b\in\mathcal{B}\cup\mathcal{B}_{0}$

repeat

$n\leftarrow n+1$

observe new data vector $X_{n}$

for  _$(j,b)\in[p]\times(\mathcal{B}\cup\mathcal{B}_{0})$_ do

$t^{j}_{b}\leftarrow
t^{j}_{b}+1\;\;\text{and}\;\;A^{\bm{\cdot},j}_{b}\leftarrow
A^{\bm{\cdot},j}_{b}+X_{n}$

set $\delta=0$ if $t_{b}^{j}$ is a power of 2 and $\delta=1$ otherwise.

$\tau_{b}^{j}\leftarrow\tau_{b}^{j}\delta+\tilde{\tau}_{b}^{j}(1-\delta)+1\;\;\text{and}\;\;\Lambda_{b}^{\bm{\cdot},j}\leftarrow\Lambda_{b}^{\bm{\cdot},j}\delta+\tilde{\Lambda}_{b}^{\bm{\cdot},j}(1-\delta)+X_{n}$

$\tilde{\tau}_{b}^{j}\leftarrow(\tilde{\tau}_{b}^{j}+1)\delta\;\;\text{and}\;\;\tilde{\Lambda}_{b}^{\bm{\cdot},j}\leftarrow(\tilde{\Lambda}_{b}^{\bm{\cdot},j}+X_{n})\delta.$

if  _$bA^{j,j}_{b}-b^{2}t^{j}_{b}/2\leq 0$_ then

$t_{b}^{j}\leftarrow\tau_{b}^{j}\leftarrow\tilde{\tau}_{b}^{j}\leftarrow 0$

$A_{b}^{\bm{\cdot},j}\leftarrow\Lambda_{b}^{\bm{\cdot},j}\leftarrow\tilde{\Lambda}_{b}^{\bm{\cdot},j}\leftarrow
0$

$E_{b}^{\bm{\cdot},j}\leftarrow\Lambda_{b}^{\bm{\cdot},j}/(\tau_{b}^{j}\vee
1)^{1/2}$

$Q^{j}_{b}\leftarrow\sum_{j^{\prime}\in[p]\setminus\\{j\\}}(E_{b}^{j^{\prime},j})^{2}\mathbbm{1}_{\\{|E_{b}^{j^{\prime},j}|\geq
a\\}}$

$S^{\mathrm{diag}}\leftarrow\max_{(j,b)\in[p]\times(\mathcal{B}\cup\mathcal{B}_{0})}\bigl{(}bA^{j,j}_{b}-b^{2}t^{j}_{b}/2\bigr{)}$

$S^{\mathrm{off}}\leftarrow\max_{(j,b)\in[p]\times\mathcal{B}}Q_{b}^{j}$

until  _$S^{\mathrm{diag}}\geq T^{\mathrm{diag}}$ or $S^{\mathrm{off}}\geq
T^{\mathrm{off}}$_;

Observe $\ell$ new data vectors $X_{n+1},\ldots,X_{n+\ell}$

Set
$\Xi_{b}^{j^{\prime},j}\leftarrow\frac{\Lambda_{b}^{j^{\prime},j}+\sum_{i=n+1}^{n+\ell}X_{i}^{j^{\prime}}}{\sqrt{(\tau_{b}^{j}+\ell)\vee
1}}$ for $j^{\prime},j\in[p]$, $b\in\mathcal{B}\cup\mathcal{B}_{0}$

Compute
$\tilde{Q}_{b}^{j}\leftarrow\sum_{j^{\prime}\in[p]\setminus\\{j\\}}(\Xi_{b}^{j^{\prime},j})^{2}\mathbbm{1}_{\\{|\Xi_{b}^{j^{\prime},j}|\geq
a\\}}$ for $j\in[p]$, $b\in\mathcal{B}$

$(\hat{j},\hat{b})\leftarrow\operatorname*{argmax}_{j\in[p],b\in\mathcal{B}}\tilde{Q}_{b}^{j}$

$\hat{\mathcal{S}}\leftarrow\bigl{\\{}j\in[p]\setminus\\{\hat{j}\\}:|\Xi_{\hat{b}}^{j,\hat{j}}|-b_{\min}(\tau_{\hat{b}}^{\hat{j}}+\ell)^{1/2}\geq
d_{1}\bigr{\\}}$

for  _$j\in\hat{\mathcal{S}}$_ do

$\tilde{b}^{j}\leftarrow\mathrm{sgn}(\Xi_{\hat{b}}^{j,\hat{j}})\max\bigl{\\{}b\in(\mathcal{B}\cup\mathcal{B}_{0})\cap(0,\infty):|\Xi_{\hat{b}}^{j,\hat{j}}|-b(\tau_{\hat{b}}^{\hat{j}}+\ell)^{1/2}\geq
d_{1}\bigr{\\}}$

Output: Confidence interval
$\mathcal{C}=\Bigl{[}\max\Bigl{\\{}n-\min_{j\in\hat{\mathcal{S}}}\Bigl{\\{}t_{\tilde{b}^{j}}^{j}+\frac{d_{2}}{(\tilde{b}^{j})^{2}}\Bigr{\\}},0\Bigr{\\}},n\Bigr{]}$

Algorithm 2 Pseudo-code for the ocd_CI′ algorithm, a slight variant of ocd_CI

##  3 Theoretical analysis

Throughout this section, we will assume that the sequential observations
$X_{1},X_{2},\ldots$ are independent, and that there exist
$z\in\mathbb{N}_{0}$ and $\theta=(\theta^{1},\ldots,\theta^{p})^{\top}\neq 0$
for which $X_{1},\ldots,X_{z}\sim\mathcal{N}_{p}(0,I_{p})$ and
$X_{z+1},X_{z+2},\ldots\sim\mathcal{N}_{p}(\theta,I_{p})$. We let
$\vartheta:=\|\theta\|_{2}$, and write $\mathbb{P}_{z,\theta}$ for
probabilities computed under this model, though in places we omit the
subscripts for brevity. Define the _effective sparsity_ of $\theta$, denoted
$s(\theta)$, to be the smallest
$s\in\bigl{\\{}2^{0},2^{1},\ldots,2^{\lfloor\log_{2}(p)\rfloor}\bigr{\\}}$
such that the corresponding _effective support_
$\mathcal{S}(\theta):=\bigl{\\{}j\in[p]:|\theta^{j}|\geq\|\theta\|_{2}/\sqrt{s\log_{2}(2p)}\bigr{\\}}$
has cardinality at least $s(\theta)$. Thus, the sum of squares of coordinates
in the effective support of $\theta$ has the same order of magnitude as
$\|\theta\|_{2}^{2}$, up to logarithmic factors. Moreover, if at most $s$
components of $\theta$ are non-zero, then $s(\theta)\leq s$, and the equality
is attained when, for example, all non-zero coordinates have the same
magnitude.

###  3.1 Coverage probability and length of the confidence interval

The following theorem shows that the confidence interval constructed in the
ocd_CI′ algorithm has the desired coverage level.

######  Theorem 1.

Let $p\geq 2$. Fix $\alpha\in(0,1)$ and $\gamma\geq 1$ and assume that $z\leq
2\alpha\gamma$. Then there exist universal constants $C_{1},C_{2}>0$, such
that with inputs $(X_{t})_{t\in\mathbb{N}}$, $0<\beta\leq\vartheta$,
$a=C_{1}\sqrt{\log\\{p\gamma(\beta^{-2}\vee 1)\alpha^{-1}\\}}$,
$T^{\mathrm{diag}}=\log\\{16p\gamma\log_{2}(4p)\\}$,
$T^{\mathrm{off}}=8\log\\{16p\gamma\log_{2}(2p)\\}$, $\ell\geq 0$,
$d_{1}=C_{2}a$ and $d_{2}=4d_{1}^{2}$ in Algorithm 2, the output confidence
interval $\mathcal{C}$ satisfies

$\displaystyle\mathbb{P}_{z,\theta}(z\in\mathcal{C})\geq 1-\alpha.$

As mentioned in Section 2.1, our coverage guarantee in Theorem 1 holds even
with $\ell=0$, i.e. with no additional sampling. The condition $z\leq
2\alpha\gamma$ ensures that the probability of a false alarm is at most
$\alpha/2$, so that $\mathbb{P}_{z,\theta}(N\leq z)\leq\alpha/2$.

We now provide a guarantee on the length of the ocd_CI′ confidence interval.

######  Theorem 2.

Assume that $\theta$ has an effective sparsity of $s:=s(\theta)\geq 2$. Fix
$\alpha\in(0,1)$ and $\gamma\geq 1$, and assume that $z\leq 2\alpha\gamma$.
Then there exist universal constants $C_{1},C_{2},C_{3},C_{4}>0$ such that,
with inputs $(X_{t})_{t\in\mathbb{N}}$, $0<\beta\leq\vartheta$,
$a=C_{1}\sqrt{\log\\{p\gamma(\beta^{-2}\vee 1)\alpha^{-1}\\}}$,
$T^{\mathrm{diag}}=\log\\{16p\gamma\log_{2}(4p)\\}$,
$T^{\mathrm{off}}=8\log\\{16p\gamma\log_{2}(2p)\\}$, $d_{1}=C_{2}a$,
$d_{2}=4d_{1}^{2}$ and $\ell\geq
C_{3}\bigl{(}\frac{a^{2}s\log_{2}(2p)}{\beta^{2}}+1\bigr{)}$ in Algorithm 2,
the length $L$ of the output confidence interval $\mathcal{C}$ satisfies

$\mathbb{P}_{z,\theta}\biggl{\\{}L>C_{4}\biggl{(}\frac{s\log_{2}(2p)\log\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}}{\beta^{2}}+1\biggr{)}\biggr{\\}}\leq\alpha.$ (2)

The main conclusion of Theorem 2 is that, with high probability, the length of
the confidence interval is of the same order, up to a logarithmic factor, as
the average detection delay guarantee for the ocd′ procedure (Chen et al.,
2020, Theorem 4). Note that the choices of inputs in Theorem 2 are identical
to those in Theorem 1, except that we now ask for some additional observations
after the changepoint declaration, the number of which is of the same order of
magnitude as the length of the interval.

###  3.2 Support recovery

Recall the definition of $\mathcal{S}(\theta)$ from the beginning of this
section, and denote
$\mathcal{S}_{\beta}(\theta):=\bigl{\\{}j\in[p]:|\theta^{j}|\geq
b_{\min}\bigr{\\}}$, where $b_{\min}$, defined in Algorithm 2, is the smallest
positive scale in $\mathcal{B}\cup\mathcal{B}_{0}$, We will suppress the
dependence on $\theta$ of both these quantities in this subsection. Theorem 3
below provides a support recovery guarantee for $\hat{\mathcal{S}}$, defined
in Algorithm 2. Since neither $\hat{\mathcal{S}}$ nor the anchor coordinate
$\hat{j}$ defined in the algorithm depend on $d_{2}$, we omit its
specification; the choices of other tuning parameters mimic those in Theorems
1 and 2.

######  Theorem 3.

Assume the conditions of Theorem 1.

(a) There exist universal constants $C_{1},C_{2}>0$, such that with inputs
$(X_{t})_{t\in\mathbb{N}}$, $0<\beta\leq\vartheta$,
$a=C_{1}\sqrt{\log\\{p\gamma(\beta^{-2}\vee 1)\alpha^{-1}\\}}$,
$T^{\mathrm{diag}}=\log\\{16p\gamma\log_{2}(4p)\\}$,
$T^{\mathrm{off}}=8\log\\{16p\gamma\log_{2}(2p)\\}$, $\ell\geq 0$ and
$d_{1}=C_{2}a$ in Algorithm 2, we have

$\mathbb{P}_{z,\theta}(\hat{\mathcal{S}}\subseteq\mathcal{S}_{\beta})\geq
1-\alpha.$

(b) Assume further that $\theta$ has effective sparsity $s:=s(\theta)\geq 2$.
There exist universal constants $C_{1},C_{2},C_{3}>0$ such that, with inputs
$(X_{t})_{t\in\mathbb{N}}$, $0<\beta\leq\vartheta$,
$a=C_{1}\sqrt{\log\\{p\gamma(\beta^{-2}\vee 1)\alpha^{-1}\\}}$,
$T^{\mathrm{diag}}=\log\\{16p\gamma\log_{2}(4p)\\}$,
$T^{\mathrm{off}}=8\log\\{16p\gamma\log_{2}(2p)\\}$, $d_{1}=C_{2}a$ and
$\ell\geq C_{3}\bigl{(}\frac{a^{2}s\log_{2}(2p)}{\beta^{2}}+1\bigr{)}$ in
Algorithm 2, we have

$\mathbb{P}_{z,\theta}(\hat{\mathcal{S}}\cup\\{\hat{j}\\}\supseteq\mathcal{S})\geq
1-\alpha.$

Note that
$\mathcal{S}\subseteq\mathcal{S}_{\beta}\subseteq\\{j\in[p]:\theta^{j}\neq
0\\}$. Thus, part (a) of the theorem reveals that with high probability, our
support estimate $\hat{\mathcal{S}}$ does not contain any noise coordinates.
Part (b) offers a complementary guarantee on the inclusion of all ‘big’ signal
coordinates, provided we augment our support estimate with the anchor
coordinate $\hat{j}$.

##  4 Numerical studies

In this section, we study the empirical performance of the ocd_CI algorithm.
Recall that in ocd_CI, the off-diagonal statistics $Q_{b}^{j}$ are computed
using tail partial sums of length $t_{b}^{j}$ and that we do not have any
extra sampling beyond the time of declaration that a change has occurred.

###  4.1 Tuning parameters

Chen et al. (2021) found that the theoretical choices of thresholds
$T^{\mathrm{diag}}$ and $T^{\mathrm{off}}$ for the ocd procedure were a little
conservative, and therefore recommended determining these thresholds via Monte
Carlo simulation; we replicate the method for choosing these thresholds
described in their Section 4.1. Likewise, as in Chen et al. (2021), we take
$a=\sqrt{2\log p}$ in our simulations.

This leaves us with the choice of tuning parameters $d_{1}$ and $d_{2}$. As
suggested by Theorems 1 and 2, we take $d_{2}=4d_{1}^{2}$. Finally, again as
suggested by our theory, we take $d_{1}$ to be of the form
$d_{1}=c\sqrt{\log(p/\alpha)}$, and then tune the parameter $c>0$ through
Monte Carlo simulation, as we now describe. We considered the parameter
settings $p\in\\{100,500\\}$, $s\in\\{2,\lfloor\sqrt{p}\rfloor,p\\}$,
$\vartheta\in\\{2,1,1/2\\}$, $\alpha=0.05$,
$\beta\in\\{2\vartheta,\vartheta,\vartheta/2\\}$, $\gamma=30000$ and $z=500$.
Then, with $\theta$ generated as $\vartheta U$, where $U$ is uniformly
distributed on the union of all $s$-sparse unit spheres in $\mathbb{R}^{p}$
(independent of our data), we studied the coverage probabilities, estimated
over 2000 repetitions as $c$ varies, of the ocd_CI confidence interval for
data generated according to the Gaussian model defined at the beginning of
Section 3. Figure 1 displays a subset of the results (the omitted curves were
qualitatively similar). On this basis, we recommend $c=0.5$ as a safe choice
across a wide range of data generating mechanisms, and we used this value of
$c$ throughout our confidence interval simulations.

Figure 1: Coverage probabilities of the ocd_CI confidence interval as the
parameter $c$, involved in the choice of tuning parameter $d_{1}$, varies.

###  4.2 Coverage probability and interval length

In Table 1, we present the detection delay of the ocd procedure, as well as
the coverage probabilities and average confidence interval lengths of the
ocd_CI procedure, all estimated over 2000 repetitions, with the same set of
parameter choices and data generating mechanism as in Section 4.1. From this
table, we see that the coverage probabilities are at least at the nominal
level (up to Monte Carlo error) across all settings considered.
Underspecification of $\beta$ means that the grid of scales that can be chosen
for indices in $\hat{\mathcal{S}}$ is shifted downwards, and therefore
increases the probability that $\tilde{b}^{j}$ will significantly
underestimate $\theta^{j}$ for $j\in\hat{\mathcal{S}}$. In turn, this leads to
a slight conservativeness for the coverage probability (and corresponding
increased average confidence interval length). On the other hand,
overspecification of $\beta$ yields a shorter interval on average, though
these were nevertheless able to retain the nominal coverage in all cases
considered.

Another interesting feature of Table 1 is to compare the average confidence
interval lengths with the corresponding average detection delays. Theorem 2,
as well as Chen et al. (2021, Theorem 4), indicate that both of these
quantities are of order $(s/\beta^{2})\vee 1$, up to polylogarithmic factors
in $p$ and $\gamma$, but of course whenever the confidence interval includes
the changepoint, its length must be at least as long as the detection delay.
Nevertheless, in most settings, it is only 2 to 3 times longer on average, and
in all cases considered was less than 7 times longer on average. Moreover, we
can also observe that the confidence interval length increases with $s$ and
decreases with $\beta$, as anticipated by our theory.

$p$ | $s$ | $\vartheta$ | $\beta$ | Detection Delay | Coverage (%) | CI Length
---|---|---|---|---|---|---
$100$ | $2$ | $2$ | $4$ | $9.8_{(0.1)}$ | $96.2_{(0.4)}$ | $20.1_{(0.7)}$
$100$ | $2$ | $2$ | $2$ | $12.6_{(0.1)}$ | $97.0_{(0.4)}$ | $33.7_{(0.7)}$
$100$ | $2$ | $2$ | $1$ | $14.1_{(0.1)}$ | $97.9_{(0.3)}$ | $80.8_{(1.0)}$
$100$ | $2$ | $1$ | $2$ | $34.2_{(0.3)}$ | $95.8_{(0.4)}$ | $66.1_{(1.0)}$
$100$ | $2$ | $1$ | $1$ | $44.2_{(0.3)}$ | $97.5_{(0.4)}$ | $122.0_{(1.4)}$
$100$ | $2$ | $1$ | $0.5$ | $52.0_{(0.4)}$ | $97.4_{(0.4)}$ | $309.1_{(2.0)}$
$100$ | $10$ | $2$ | $4$ | $14.7_{(0.1)}$ | $96.0_{(0.4)}$ | $32.5_{(0.8)}$
$100$ | $10$ | $2$ | $2$ | $15.7_{(0.1)}$ | $97.4_{(0.4)}$ | $38.4_{(0.8)}$
$100$ | $10$ | $2$ | $1$ | $15.9_{(0.1)}$ | $97.0_{(0.4)}$ | $80.2_{(1.1)}$
$100$ | $10$ | $1$ | $2$ | $52.6_{(0.5)}$ | $96.2_{(0.4)}$ | $114.0_{(1.5)}$
$100$ | $10$ | $1$ | $1$ | $56.9_{(0.4)}$ | $97.1_{(0.4)}$ | $142.5_{(1.8)}$
$100$ | $10$ | $1$ | $0.5$ | $60.2_{(0.4)}$ | $98.2_{(0.3)}$ | $301.1_{(1.6)}$
$100$ | $100$ | $2$ | $4$ | $27.2_{(0.2)}$ | $96.1_{(0.4)}$ | $77.6_{(0.9)}$
$100$ | $100$ | $2$ | $2$ | $27.7_{(0.2)}$ | $96.0_{(0.4)}$ | $81.8_{(1.0)}$
$100$ | $100$ | $2$ | $1$ | $28.2_{(0.2)}$ | $97.5_{(0.3)}$ | $99.4_{(1.3)}$
$100$ | $100$ | $1$ | $2$ | $100.7_{(0.8)}$ | $94.7_{(0.5)}$ | $292.8_{(3.5)}$
$100$ | $100$ | $1$ | $1$ | $100.5_{(0.9)}$ | $96.3_{(0.4)}$ | $296.0_{(3.4)}$
$100$ | $100$ | $1$ | $0.5$ | $103.2_{(0.8)}$ | $97.3_{(0.4)}$ | $365.9_{(2.8)}$
$500$ | $2$ | $2$ | $4$ | $11.3_{(0.1)}$ | $97.2_{(0.4)}$ | $23.1_{(0.7)}$
$500$ | $2$ | $2$ | $2$ | $15.8_{(0.1)}$ | $97.7_{(0.3)}$ | $45.2_{(0.9)}$
$500$ | $2$ | $2$ | $1$ | $17.7_{(0.1)}$ | $97.5_{(0.4)}$ | $117.3_{(1.0)}$
$500$ | $2$ | $1$ | $2$ | $41.5_{(0.3)}$ | $97.3_{(0.4)}$ | $81.8_{(1.2)}$
$500$ | $2$ | $1$ | $1$ | $55.0_{(0.4)}$ | $96.8_{(0.4)}$ | $168.9_{(1.5)}$
$500$ | $2$ | $1$ | $0.5$ | $64.6_{(0.5)}$ | $98.1_{(0.3)}$ | $445.0_{(1.7)}$
$500$ | $22$ | $2$ | $4$ | $23.6_{(0.2)}$ | $96.3_{(0.4)}$ | $55.4_{(1.0)}$
$500$ | $22$ | $2$ | $2$ | $25.0_{(0.2)}$ | $97.0_{(0.4)}$ | $60.3_{(0.8)}$
$500$ | $22$ | $2$ | $1$ | $25.5_{(0.2)}$ | $98.1_{(0.3)}$ | $119.7_{(0.8)}$
$500$ | $22$ | $1$ | $2$ | $88.1_{(0.7)}$ | $97.0_{(0.4)}$ | $203.5_{(2.1)}$
$500$ | $22$ | $1$ | $1$ | $91.9_{(0.6)}$ | $97.8_{(0.3)}$ | $229.7_{(2.2)}$
$500$ | $22$ | $1$ | $0.5$ | $94.9_{(0.6)}$ | $98.3_{(0.3)}$ | $462.8_{(1.4)}$
$500$ | $500$ | $2$ | $4$ | $79.8_{(0.6)}$ | $95.0_{(0.5)}$ | $238.9_{(2.7)}$
$500$ | $500$ | $2$ | $2$ | $80.3_{(0.6)}$ | $95.8_{(0.4)}$ | $245.7_{(2.6)}$
$500$ | $500$ | $2$ | $1$ | $80.9_{(0.6)}$ | $97.5_{(0.4)}$ | $250.2_{(2.5)}$
$500$ | $500$ | $1$ | $2$ | $290.5_{(2.3)}$ | $94.5_{(0.5)}$ | $819.7_{(7.9)}$
$500$ | $500$ | $1$ | $1$ | $291.4_{(2.3)}$ | $95.2_{(0.5)}$ | $831.1_{(7.5)}$
$500$ | $500$ | $1$ | $0.5$ | $297.3_{(2.3)}$ | $98.1_{(0.3)}$ | $875.0_{(6.7)}$
Table 1:  Estimated coverage, average length of the ocd_CI confidence interval
and average detection delay over 2000 repetitions, with standard errors in
brackets. Other parameters: $\gamma=30000$, $z=1000$, $\alpha=0.05$,
$a=\sqrt{2\log p}$, $c=0.5$, $d_{1}=c\sqrt{\log(p/\alpha)}$,
$d_{2}=4d_{1}^{2}$.

###  4.3 Support recovery

We now turn our attention to the empirical support recovery properties of the
quantity $\hat{\mathcal{S}}$ (in combination with the anchor coordinate
$\hat{j}$) computed in the ocd_CI algorithm. In Table 2, we present the
probabilities, estimated over 500 repetitions, that
$\hat{\mathcal{S}}\subseteq\mathcal{S}_{\beta}$ and that
$\hat{\mathcal{S}}\cup\\{\hat{j\\}}\supseteq\mathcal{S}$ for $p=100$,
$s\in\\{5,50\\}$, $\vartheta\in\\{1,2\\}$, and for three different signal
shapes: in the uniform, inverse square root and harmonic cases, we took
$\theta\propto(\mathbbm{1}_{\\{j\in[s]\\}})_{j\in[p]}$,
$\theta\propto(j^{-1/2}\mathbbm{1}_{\\{j\in[s]\\}})_{j\in[p]}$ and
$\theta\propto(j^{-1}\mathbbm{1}_{\\{j\in[s]\\}})_{j\in[p]}$ respectively. As
inputs to the algorithm, we set $a=\sqrt{2\log p}$, $\alpha=0.05$,
$d_{1}=\sqrt{2\log(p/\alpha)}$, $\beta=\vartheta$, and, motivated by Theorem
3, took an additional $\ell=\lceil a^{2}s\beta^{-2}\log_{2}(2p)\rceil$ post-
declaration observations in constructing the support estimates. The results
reported in Table 2 provide empirical confirmation of the support recovery
properties claimed in Theorem 3.

$s$ | $\vartheta$ | Signal Shape |  $\hat{\mathcal{S}}\subseteq\mathcal{S}_{\beta}$ (%) |  $\hat{\mathcal{S}}\cup{\\{\hat{j}\\}}\supseteq\mathcal{S}$ (%)
---|---|---|---|---
$5$ | $2$ | uniform | $99.8_{(0.2)}$ | $97.6_{(0.7)}$
$5$ | $1$ | uniform | $100.0_{(0.0)}$ | $97.6_{(0.7)}$
$50$ | $2$ | uniform | $100.0_{(0.0)}$ | $95.6_{(0.9)}$
$50$ | $1$ | uniform | $100.0_{(0.0)}$ | $97.8_{(0.7)}$
$5$ | $2$ | inv sqrt | $99.6_{(0.3)}$ | $96.6_{(0.8)}$
$5$ | $1$ | inv sqrt | $100.0_{(0.0)}$ | $98.8_{(0.5)}$
$50$ | $2$ | inv sqrt | $100.0_{(0.0)}$ | $99.8_{(0.2)}$
$50$ | $1$ | inv sqrt | $100.0_{(0.0)}$ | $100.0_{(0.0)}$
$5$ | $2$ | harmonic | $100.0_{(0.0)}$ | $97.6_{(0.7)}$
$5$ | $1$ | harmonic | $99.6_{(0.3)}$ | $97.8_{(0.7)}$
$50$ | $2$ | harmonic | $100.0_{(0.0)}$ | $99.4_{(0.3)}$
$50$ | $1$ | harmonic | $100.0_{(0.0)}$ | $100.0_{(0.0)}$
Table 2:  Estimated support recovery probabilities (with standard errors in
brackets). Other settings: $p=100$, $a=\sqrt{2\log p}$, $\alpha=0.05$,
$d_{1}=\sqrt{2\log(p/\alpha)}$, $\beta=\vartheta$, and with an additional
$\ell=\lceil a^{2}s\beta^{-2}\log_{2}(2p)\rceil$ post-declaration
observations.

Finally in this section, we consider the extent to which the additional
observations are necessary in practice to provide satisfactory support
recovery. In the left panel of Figure 2, we plot Receiver Operating
Characteristic (ROC) curves to study the estimated support recovery
probabilities with $\ell=0$ (i.e., no additional sampling) as a function of
the input parameter $d_{1}$, which can be thought of as controlling the trade-
off between
$\mathbb{P}(\hat{\mathcal{S}}\cup\\{\hat{j}\\}\supseteq\mathcal{S})$ and
$\mathbb{P}(\hat{\mathcal{S}}\subseteq\mathcal{S}_{\beta})$. The fact that the
triangles in this plot are all to the left of the dotted vertical line
confirms the theoretical guarantee provided in Theorem 3(a), which holds with
$d_{1}=\sqrt{2\log(p/\alpha)}$, and even with $\ell=0)$; the less conservative
choice $d_{1}=\sqrt{2\log p}$, which roughly corresponds to an average of one
noise coordinate included in $\hat{\mathcal{S}}$, allows us to capture a
larger proportion of the signal. From this panel, we also see that additional
sampling is needed to ensure that, with high probability, we recover all of
the true signals. This is unsurprising: for instance, with a uniform signal
shape and $s=50$, it is very unlikely that all 50 signal coordinates will have
accumulated such similar levels of evidence to appear in
$\hat{\mathcal{S}}\cup\\{\hat{j}\\}$ by the time of declaration. The right
panel confirms that, with an inverse square root signal shape, the probability
that we capture each signal increases with the signal magnitude, and that even
small signals tend to be selected with higher probability than noise
coordinates.

Figure 2: Support recovery properties of ocd_CI. In the left panel, we plot
ROC curves for three different signal shapes and for sparsity levels
$s\in\\{5,50\\}$. The triangles and circles correspond to points on the curves
with $d_{1}=\sqrt{2\log(p/\alpha)}$ (with $\alpha=0.05$), and
$d_{1}=\sqrt{2\log p}$ respectively. The dotted vertical line corresponds to
$\mathbb{P}(\hat{\mathcal{S}}\subseteq\mathcal{S}_{\beta})=1-\alpha$. In the
right panel, we plot the proportion of 500 repetitions for which each
coordinate belongs to $\hat{S}\cup\\{\hat{j}\\}$ with $d_{1}=\sqrt{2\log p}$;
here, the $s=20$ signals have an inverse square root shape, and are plotted in
red; noise coordinates are plotted in black. Other parameters for both panels:
$p=100$, $\beta=\vartheta=2$, $\ell=0$, $a=\sqrt{2\log p}$.

###  4.4 Real data examples

####  4.4.1 US Covid-19 data

In this section, we apply ocd_CI to a dataset of weekly deaths in the United
States between January 2017 and June 2020444Available at:
https://www.cdc.gov/nchs/nvss/vsrr/covid19/excess_deaths.htm.. The data up to
29 June 2019 are treated as our training data. For each of the 50 states, as
well as Washington, D.C. ($p=51$), we pre-process the data as follows. To
remove the seasonal effect, we first estimate the ‘seasonal death curve’, i.e.
the mean death numbers for each day of the year, for each state. The seasonal
death curve is estimated by first splitting the weekly death numbers evenly
across the seven relevant days, and then estimating the average number of
deaths on each day of the year from these derived daily death numbers using a
Gaussian kernel with a bandwidth of 20 days. As the death numbers follow an
approximate Poisson distribution, we apply a square-root transformation to
stabilise the variance; more precisely, the transformed weekly excess deaths
are computed as the difference of the square roots of the weekly deaths and
the predicted weekly deaths from the seasonal death curve. Finally, we
standardise the transformed weekly excess deaths using the mean and standard
deviation of the transformed data over the training period. The standardised,
transformed data are plotted in Figure 3 for 12 states. When applying ocd_CI
to these data, we take $a=\sqrt{2\log p}$,
$T^{\mathrm{diag}}=\log\\{16p\gamma\log_{2}(4p)\\}$,
$T^{\mathrm{off}}=8\log\\{16p\gamma\log_{2}(2p)\\}$,
$d_{1}=0.5\sqrt{\log(p/\alpha)}$ and $d_{2}=4d_{1}^{2}$, with $\alpha=0.05$,
$\beta=50$ and $\gamma=1000$. On the monitoring data (from 30 June 2019), the
ocd_CI algorithm declares a change on the week ending 28 March 2020, and
provides a confidence interval from the week ending 21 March 2020 to the week
ending 28 March 2020. This coincides with the beginning of the first wave of
Covid-19 deaths in the United States. The algorithm also identifies New York,
New Jersey, Connecticut, Michigan and Louisiana as the estimated support of
the change. Interestingly, if we run the ocd_CI procedure from the beginning
of the training data period (while still standardising as before, due to the
lack of available data prior to 2017), it identifies a subtler change on the
week ending 6 January 2018, with a confidence interval of [17 December 2017, 6
January 2018]. This corresponds to a bad influenza season at the end of
2017555See https://www.cdc.gov/flu/about/season/flu-season-2017-2018.htm.

Figure 3: Standardised, transformed weekly excess death data from 12 states
(including Washington, D.C.). The monitoring period starts from 30 June 2019
(dashed line). The data from the states in the support estimate are shown in
red. The confidence interval [8 March 2020, 28 March 2020] is shown in the
light blue shaded region.

####  4.4.2 S&P 500 data

We now use ocd_CI to study market movements leading up to the financial crisis
of 2007–2008. We selected the $p=254$ stocks that were both in the S&P 500
listing and were traded throughout the period from 1 January 2006 to 31
December 2007. The historical price data were downloaded from
finance.yahoo.com using the quantmod R package (Ryan et al., 2020); a similar
dataset was studied by Cai and Wang (2021). For each stock, we compute the
daily logarithmic returns from the adjusted closing prices. We use the data
from 2006 as the training data and standardise the entire data according to
the mean and variance over the training period. Since these logarithmic
returns have a heavy-tailed distribution, we clip the standardised data at
$\pm 3$.

When applying the ocd_CI procedure to this dataset, we used the same input
parameters as in Section 4.4.1. So as to be able to use ocd_CI repeatedly to
identify multiple changes, we also set a cool-down period of 10 trading days
(i.e. the monitoring resets and restarts 10 trading days after a change is
declared). This allows the market to recover from any loss (or gain) from the
previous change so that the same market movement is not identified as more
than one changepoint. The first four changes were declared on 27 February
2007, 24 May 2007, 24 July 2007 and 8 August 2007, with corresponding
confidence intervals shown in Figure 4. This figure also depicts the relative
sector impact of each change by showing the percentage of stocks in each
sector (according to the Global Industry Classification Standard666See
https://www.msci.com/our-solutions/indexes/gics) that belongs to the estimated
support of a changepoint. In particular, the first and last identified
changepoints are primarily associated with changes in Real Estate stocks;
these correspond to an HSBC announcement indicating loan losses on subprime
mortgages in February 2007, and American Home Mortgage Investment Corporation
filing for bankruptcy in August 2007 respectively (Hausman and Johnston,
2014).

Figure 4: Heatmap of sector impact of the four changepoints in the S&P 500
data identified by ocd_CI, measured as a proportion of the stocks in a sector
that appear in the support estimate of the changepoint. The confidence
intervals for each of the changepoints are given on the left.

##  5 Proofs of main results

###### Proof of Theorem 1.

Fix $n>z,j\in[p]$, $b\in\mathcal{B}$ and $j^{\prime}\in[p]\setminus\\{j\\}$.
We assume, without loss of generality, that $\theta^{j^{\prime}}\geq 0$. The
case $\theta^{j^{\prime}}<0$ can be analysed similarly. Recall that
$b_{\min}$, defined in Algorithm 2, is the smallest positive scale in
$\mathcal{B}\cup\mathcal{B}_{0}$, and write
$b_{\mathrm{aux}}^{j^{\prime}}:=\min\bigl{\\{}b\in(\mathcal{B}\cup\mathcal{B}_{0})\cap(0,\infty):b\geq\theta^{j^{\prime}}\bigr{\\}}$.
Then we have
$\Lambda_{n,b}^{j^{\prime},j}+\sum_{i=n+1}^{n+\ell}X_{i}^{j^{\prime}}\mid\tau_{n,b}^{j}\sim\mathcal{N}\bigl{(}\theta^{j^{\prime}}\min\\{n+\ell-z,\tau_{n,b}^{j}+\ell\\},\,\tau_{n,b}^{j}+\ell\bigr{)}$.
Thus, recalling the definition of $\hat{\mathcal{S}}$ and
$\tilde{b}^{j^{\prime}}$ from Algorithm 2, we have

$\displaystyle\mathbb{P}\bigl{(}\\{j^{\prime}\in\hat{\mathcal{S}}\\}$
$\displaystyle\cap\\{\tilde{b}^{j^{\prime}}\notin(0,\theta^{j^{\prime}})\\}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\bigr{)}$
$\displaystyle=\mathbb{E}\Bigl{\\{}\mathbb{P}\Bigl{(}\\{j^{\prime}\in\hat{\mathcal{S}}\\}\cap\\{\tilde{b}^{j^{\prime}}\notin(-b_{\min},b^{j^{\prime}}_{\mathrm{aux}})\\}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\Bigm{|}\tau_{n,b}^{j}\Bigr{)}\Bigr{\\}}$
$\displaystyle\leq\mathbb{E}\biggl{\\{}\mathbb{P}\biggl{(}\Lambda_{n,b}^{j^{\prime},j}+\sum_{i=n+1}^{n+\ell}X_{i}^{j^{\prime}}\geq
b_{\mathrm{aux}}^{j^{\prime}}(\tau_{n,b}^{j}+\ell)+d_{1}\bigl{(}\tau_{n,b}^{j}+\ell)^{1/2}\biggm{|}\tau_{n,b}^{j}\biggr{)}\biggr{\\}}$
$\displaystyle\hskip
56.9055pt+\mathbb{E}\biggl{\\{}\mathbb{P}\biggl{(}\Lambda_{n,b}^{j^{\prime},j}+\sum_{i=n+1}^{n+\ell}X_{i}^{j^{\prime}}\leq-
b_{\min}(\tau_{n,b}^{j}+\ell)-d_{1}\bigl{(}\tau_{n,b}^{j}+\ell\bigr{)}^{1/2}\biggm{|}\tau_{n,b}^{j}\biggr{)}\biggr{\\}}$
$\displaystyle\leq\mathbb{E}\bigl{\\{}\bar{\Phi}\bigl{(}(b^{j^{\prime}}_{\mathrm{aux}}-\theta^{j^{\prime}})(\tau_{n,b}^{j}+\ell)^{1/2}+d_{1}\bigr{)}\bigr{\\}}+\mathbb{E}\bigl{\\{}\bar{\Phi}\bigl{(}(b_{\mathrm{min}}+\theta^{j^{\prime}})(\tau_{n,b}^{j}+\ell)^{1/2}+d_{1}\bigr{)}\bigr{\\}}$
$\displaystyle\leq 2\bar{\Phi}(d_{1}).$ (3)

Moreover, by a similar argument to (13) in the proof of Proposition 4, for
$b\in(0,\theta^{j^{\prime}})$, we have

$\mathbb{P}\bigl{(}n-t_{n,b}^{j^{\prime}}-d_{2}/b^{2}>z\bigr{)}\leq
2\bar{\Phi}\biggl{(}\frac{\sqrt{d_{2}}}{b}(\theta^{j^{\prime}}-b/2)\biggr{)}\leq
2\bar{\Phi}\bigl{(}\sqrt{d_{2}}/2\bigr{)}.$ (4)

Combining (3) and (4), we have

$\displaystyle\mathbb{P}\Bigl{(}\\{j^{\prime}\in$
$\displaystyle\hat{\mathcal{S}}\\}\cap\\{n-t_{n,\tilde{b}^{j^{\prime}}}^{j^{\prime}}-d_{2}/(\tilde{b}^{j^{\prime}})^{2}>z\\}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\Bigr{)}$
$\displaystyle\leq\mathbb{P}\Bigl{(}\\{j^{\prime}\in\hat{\mathcal{S}}\\}\cap\\{\tilde{b}^{j^{\prime}}\notin(0,\theta^{j^{\prime}})\\}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\Bigr{)}+\sum_{b\in(\mathcal{B}\cup\mathcal{B}_{0})\cap(0,\theta^{j})}2\bar{\Phi}\bigl{(}\sqrt{d_{2}}/2\bigr{)}$
$\displaystyle\leq
2\bar{\Phi}(d_{1})+2\log_{2}(4p)\bar{\Phi}\bigl{(}\sqrt{d_{2}}/2\bigr{)}.$

Now, write

$r_{0}:=\biggl{(}\frac{24T^{\mathrm{off}}}{\vartheta^{2}}\vee\frac{12(a^{2}\vee
8\log
2)s}{\vartheta^{2}}\vee\frac{128(T^{\mathrm{diag}}+\log(8/\alpha))s}{\beta^{2}}\biggr{)}\log_{2}(2p)+2.$
(5)

By a union bound and Proposition 6, we have

$\displaystyle\mathbb{P}\biggl{(}N-\min_{j\in\hat{\mathcal{S}}}\Bigl{\\{}t_{N,\tilde{b}^{j}}^{j}+\frac{d_{2}}{(\tilde{b}^{j})^{2}}\Bigr{\\}}>z\biggr{)}$
$\displaystyle\leq\mathbb{P}(N>z+r_{0})$ $\displaystyle\hskip
28.45274pt+\sum_{n=z+1}^{z+\lfloor
r_{0}\rfloor}\sum_{j=1}^{p}\sum_{b\in\mathcal{B}}\sum_{j^{\prime}=1}^{p}\mathbb{P}\biggl{(}\\{j^{\prime}\in\hat{\mathcal{S}}\\}\cap\Bigl{\\{}n-t_{n,\tilde{b}^{j^{\prime}}}^{j^{\prime}}-\frac{d_{2}}{(\tilde{b}^{j^{\prime}})^{2}}>z\Bigr{\\}}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\biggr{)}$
$\displaystyle\leq\exp\biggl{\\{}-\frac{\beta^{2}(r_{0}-1)}{48\log_{2}(2p)}\biggr{\\}}+p\exp\biggl{\\{}-\frac{\vartheta^{2}(r_{0}-1)}{128\log_{2}(2p)}\biggr{\\}}+4p^{2}\log_{2}^{2}(4p)r_{0}\bigl{\\{}\bar{\Phi}(d_{1})+\bar{\Phi}\bigl{(}\sqrt{d_{2}}/2\bigr{)}\bigr{\\}}.$

Therefore, for sufficiently large $C_{1}>0$ and $C_{2}>0$, the choice of
$d_{1}$ and $d_{2}$ in the statement of the theorem ensures that

$\mathbb{P}\biggl{(}N-\min_{j\in\hat{\mathcal{S}}}\Bigl{\\{}t_{N,\tilde{b}^{j}}^{j}+\frac{d_{2}}{(\tilde{b}^{j})^{2}}\Bigr{\\}}>z\biggr{)}\leq\alpha/2.$

Combining this with the fact that $\mathbb{P}(N\leq z)\leq
z/(4\gamma)\leq\alpha/2$, which follows from Lemma 7 when $C_{1}\geq\sqrt{8}$,
we deduce the result. ∎

###### Proof of Theorem 2.

Denote
$\ell_{0}:=C_{3}\bigl{(}\frac{a^{2}s\log_{2}(2p)}{\beta^{2}}+1\bigr{)}$. Since
the output of Algorithm 2 remains unchanged if we replace
$(X_{t}^{j}:t\in\mathbb{N})$ by $(-X_{t}^{j}:t\in\mathbb{N})$ for any fixed
$j$, we may assume without loss of generality that
$\theta^{1}\geq\theta^{2}\geq\vartheta/\sqrt{s\log_{2}(2p)}$. For
$j\in\\{1,2\\}$, we denote
$b^{j}:=\max\\{b\in\mathcal{B}\cup\mathcal{B}_{0}:b\leq\theta^{j}\\}$ . Since
$\vartheta\geq\beta$ and $s\leq 2^{\lfloor\log_{2}(p)\rfloor}$, we have
$b^{1}\geq b^{2}\geq\beta/\sqrt{s\log_{2}(2p)}\geq\sqrt{2}b_{\mathrm{min}}$.
For $C_{5}>0$, let

$\displaystyle r:=\frac{C_{5}a^{2}s\log_{2}(2p)}{\beta^{2}}+2,\quad
u:=\frac{\ell_{0}\beta^{2}}{80s\log_{2}(2p)}\quad\text{and}\quad\delta:=\frac{a}{2\sqrt{r+\ell}}.$

Now define the following events:

$\displaystyle\Omega_{0}$ $\displaystyle:=\\{z<N\leq z+r\\}$
$\displaystyle\Omega_{1}$ $\displaystyle:=\bigl{\\{}t_{N,b}^{j}\leq
N-z+ub^{-2}\text{ for all }j\in[p]\text{ and
}b\in\mathcal{B}\cup\mathcal{B}_{0}\bigr{\\}},$ $\displaystyle\Omega_{2}$
$\displaystyle:=\biggl{\\{}\biggl{|}\Lambda_{N,b}^{j^{\prime},j}+\sum_{i=N+1}^{N+\ell}X_{i}^{j^{\prime}}\biggr{|}<a\sqrt{\tau_{N,b}^{j}+\ell}\text{
for all }b\in\mathcal{B}\cup\mathcal{B}_{0},j\in[p]$ $\displaystyle\hskip
142.26378pt\text{ and all }j^{\prime}\in[p]\setminus\\{j\\}\text{ with
}\bigl{|}\theta^{j^{\prime}}\bigr{|}\leq\delta\biggr{\\}},$
$\displaystyle\Omega_{3}$
$\displaystyle:=\bigl{\\{}\tau_{N,\hat{b}}^{\hat{j}}\leq
N-z+\ell/20\bigr{\\}}.$

Finally, we denote event

$\Omega_{4}:=\Omega_{4,1}\cup\Omega_{4,2},$

with

$\displaystyle\Omega_{4,1}$ $\displaystyle:=\bigl{\\{}\hat{j}\neq
1,1\in\hat{\mathcal{S}},\tilde{b}^{1}\geq b^{1}/\sqrt{2}\bigr{\\}}$
$\displaystyle\Omega_{4,2}$
$\displaystyle:=\bigl{\\{}\hat{j}=1,2\in\hat{\mathcal{S}},\tilde{b}^{2}\geq
b^{2}/\sqrt{2}\bigr{\\}}.$

Henceforth, we will assume without loss of generality that $C_{2}\geq 1/2$.
Then, on the event $\bigcap_{k=0}^{4}\Omega_{k}$, we have

$\displaystyle L$
$\displaystyle=\min_{j\in\hat{\mathcal{S}}}\Bigl{\\{}t_{N,\tilde{b}^{j}}^{j}+\frac{d_{2}}{(\tilde{b}^{j})^{2}}\Bigr{\\}}\wedge
N\leq N-z+\frac{2(u+d_{2})}{(b^{2})^{2}}\leq
r+\frac{\ell_{0}}{40}+\frac{2sd_{2}\log_{2}(2p)}{\beta^{2}}$
$\displaystyle\leq
C_{1}^{2}\Bigl{(}C_{5}+\frac{C_{3}}{40}+8C_{2}^{2}\Bigr{)}\biggl{(}\frac{s\log_{2}(2p)\log\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}}{\beta^{2}}+1\biggr{)}.$

Let $C_{4}:=C_{1}^{2}(C_{5}+\frac{C_{3}}{40}+8C_{2}^{2})$. Then

$\displaystyle\mathbb{P}\Biggl{(}L>C_{4}\biggl{(}\frac{s\log_{2}(2p)\log\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}}{\beta^{2}}+1\biggr{)}\Biggr{)}$
$\displaystyle\leq\mathbb{P}\biggl{(}\bigcup_{k=0}^{4}\Omega_{k}^{\mathrm{c}}\biggr{)}.$
(6)

By choosing $C_{1}\geq\sqrt{8}$ and choosing $C_{5}$ to be a sufficiently
large universal constant, we have
$r\geq\bigl{(}\frac{24T^{\mathrm{off}}}{\vartheta^{2}}\vee\frac{12a^{2}s}{\vartheta^{2}}\vee\frac{24T^{\mathrm{diag}}s}{\beta^{2}}\bigr{)}\log_{2}(2p)+2$,
so we may apply Proposition 6 and Lemma 7 to deduce that

$\displaystyle\mathbb{P}(\Omega_{0}^{\mathrm{c}})=\mathbb{P}(N>z+r)+\mathbb{P}(N\leq
z)$ $\displaystyle\leq
2p\exp\biggl{\\{}-\frac{\beta^{2}(r-1)}{128\log_{2}(2p)}\biggr{\\}}+\frac{z}{4\gamma}$
$\displaystyle\leq
2p\exp\biggl{\\{}-\frac{C_{5}C_{1}^{2}s\log\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}}{128}\biggr{\\}}+\frac{z}{4\gamma}.$ (7)

On $\Omega_{0}$, we have for any $j\in[p]$ and
$b\in\mathcal{B}\cup\mathcal{B}_{0}$ that

$\displaystyle t_{N,b}^{j}$ $\displaystyle=\operatorname*{sargmax}_{0\leq
h\leq N}\sum_{i=N-h+1}^{N}b(X_{i}^{j}-b/2)\leq\operatorname*{sargmax}_{N-z\leq
h\leq N}\sum_{i=N-h+1}^{N}b(X_{i}^{j}-b/2)$
$\displaystyle=N-z+\operatorname*{sargmax}_{0\leq h\leq
z}\sum_{i=z-h+1}^{z}b(X_{i}^{j}-b/2).$

Thus, by Lemma 5 (taking $\mu=-b/2$) and a union bound, we have

$\mathbb{P}(\Omega_{0}\cap\Omega_{1}^{\mathrm{c}})\leq
2p\log_{2}(4p)e^{-u/8}=2p\log_{2}(4p)\exp\biggl{\\{}-\frac{\ell_{0}\beta^{2}}{640s\log_{2}(2p)}\biggr{\\}}.$
(8)

Now observe that, for all $z<n\leq
z+r,b\in\mathcal{B}\cup\mathcal{B}_{0},j\in[p]$ and
$j^{\prime}\in[p]\setminus\\{j\\}$, we have

$\Lambda_{n,b}^{j^{\prime},j}+\sum_{i=n+1}^{n+\ell}X_{i}^{j^{\prime}}\biggm{|}\tau_{n.b}^{j}\sim\mathcal{N}\Bigl{(}\theta^{j^{\prime}}\bigl{\\{}\ell+\min\bigl{(}\tau_{n,b}^{j},n-z\bigr{)}\bigr{\\}},\tau_{n,b}^{j}+\ell\Bigr{)}.$

Hence, when $\bigl{|}\theta^{j^{\prime}}\bigr{|}\leq\delta$, we have that

$\displaystyle\mathbb{P}\biggl{(}\biggl{|}\Lambda_{n,b}^{j^{\prime},j}+\sum_{i=n+1}^{n+\ell}X_{i}^{j^{\prime}}\biggr{|}\geq
a\sqrt{\tau_{n,b}^{j}+\ell}\biggm{|}\tau_{n.b}^{j}\biggr{)}\leq\mathbb{P}(|Y_{1}|\geq
a)\leq 2\mathbb{P}(Y_{1}\geq a)\leq e^{-a^{2}/8},$

where $Y_{1}\sim\mathcal{N}(\delta\sqrt{n-z+\ell},1)$, and where the last
inequality follows from the relation $a=2\delta\sqrt{r+\ell}$. Thus, by a
union bound, we have

$\mathbb{P}(\Omega_{0}\cap\Omega_{2}^{\mathrm{c}})\leq
2rp^{2}\log_{2}(4p)e^{-a^{2}/8}\leq
2rp^{2}\log_{2}(4p)\\{p\gamma(\beta^{-2}\vee 1)\alpha^{-1}\\}^{-C_{1}^{2}/8}.$
(9)

By Chen et al. (2021, Lemma 9 in the supplement), we have
$t_{n,b}^{j}/2\leq\tau_{n,b}^{j}\leq t_{n,b}^{j}$ for all
$n\in\mathbb{N}_{0}$, $b\in\mathcal{B}\cup\mathcal{B}_{0}$ and $j\in[p]$.
Moreover, when $C_{3}\geq 80(C_{5}\vee 2)$, we have $\ell_{0}\geq 80r$. Define
$b_{*}:=\beta/\sqrt{s\log_{2}(2p)}\in\mathcal{B}$, so that
$u=\ell_{0}b_{*}^{2}/80$. We therefore have for any $z<n\leq z+r,j\in[p]$ and
$b\in\mathcal{B}$ that

$\displaystyle\mathbb{P}\Bigl{(}\\{N=n\\}\cap\Omega_{1}\cap\Omega_{2}\cap\bigl{\\{}\tilde{Q}_{n,b}^{j}\geq\tilde{Q}_{n,b_{*}}^{j}\bigr{\\}}\cap\bigl{\\{}\tau_{n,b}^{j}>n-z+\ell/20\bigr{\\}}\Bigm{|}X_{1}^{j},X_{2}^{j},\ldots\Bigr{)}$
$\displaystyle\leq\mathbb{P}\Biggl{(}\bigcup_{\begin{subarray}{c}j^{\prime}\in[p]\setminus\\{j\\}:\\\
|\theta^{j^{\prime}}|>\delta\end{subarray}}\bigl{\\{}|\Xi_{n,b}^{j^{\prime},j}|\geq|\Xi_{n,b_{*}}^{j^{\prime},j}|\bigr{\\}}\cap\\{N=n\\}\cap\Omega_{1}\cap\Omega_{2}\cap\bigl{\\{}\tau_{n,b}^{j}>n-z+\ell/20\bigr{\\}}\Biggm{|}X_{1}^{j},X_{2}^{j},\ldots\Biggr{)}$
$\displaystyle\leq\smash{\sum_{\begin{subarray}{c}j^{\prime}\in[p]\setminus\\{j\\}:\\\
|\theta^{j^{\prime}}|>\delta\end{subarray}}}\mathbb{P}\Bigl{(}\bigl{\\{}|\Xi_{n,b}^{j^{\prime},j}|\geq|\Xi_{n,b_{*}}^{j^{\prime},j}|\bigr{\\}}\cap\bigl{\\{}n-z<\tau_{n,b_{*}}^{j}\leq
n-z+\ell/80\bigr{\\}}$ $\displaystyle\hskip
274.56891pt\cap\bigl{\\{}\tau_{n,b}^{j}>n-z+\ell/20\bigr{\\}}\Bigm{|}X_{1}^{j},X_{2}^{j},\ldots\Bigr{)}$
$\displaystyle\hskip
22.76228pt+\sum_{\begin{subarray}{c}j^{\prime}\in[p]\setminus\\{j\\}:\\\
|\theta^{j^{\prime}}|>\delta\end{subarray}}\mathbb{P}\Bigl{(}\bigl{\\{}|\Xi_{n,b}^{j^{\prime},j}|\geq|\Xi_{n,b_{*}}^{j^{\prime},j}|\bigr{\\}}\cap\bigl{\\{}\tau_{n,b_{*}}^{j}\leq
n-z\bigr{\\}}\cap\bigl{\\{}\tau_{n,b}^{j}>n-z+\ell/20\bigr{\\}}\Bigm{|}X_{1}^{j},X_{2}^{j},\ldots\Bigr{)}$
$\displaystyle\leq
p\exp\biggl{(}-\frac{\ell\delta^{2}}{960}\biggr{)}=p\exp\biggl{(}-\frac{\ell
a^{2}}{3840(r+\ell)}\biggr{)},$

where the final inequality follows from Lemma 8(a), applied with
$U=\sum_{i=n-\tau_{n,b_{*}}^{j}+1}^{z}X_{i}^{j^{\prime}}$,
$V=\sum_{i=n-\tau_{n,b}^{j}+1}^{n-\tau_{n,b_{*}}^{j}}X_{i}^{j^{\prime}}$,
$Y=\sum_{i=z+1}^{n+\ell}X_{i}^{j^{\prime}}$, $\alpha=\theta^{j^{\prime}}$,
$\phi_{1}=z-n+\tau_{n,b_{*}}^{j}$, $\phi_{2}=z-n+\tau_{n,b}^{j}$,
$\phi_{3}=n-z+\ell$ and $\kappa=\ell/80$, as well as Lemma 8(b), with
$U=\sum_{i=n-\tau_{n,b}^{j}+1}^{z}X_{i}^{j^{\prime}}$,
$Y=\sum_{i=n-\tau_{n,b_{*}}^{j}+1}^{n+\ell}X_{i}^{j^{\prime}}$,
$Z=\sum_{i=z+1}^{n-\tau_{n,b_{*}}^{j}}X_{i}^{j^{\prime}}$,
$\alpha=\theta^{j^{\prime}}$, $\phi_{1}=z-n+\tau_{n,b}^{j}$,
$\phi_{3}=\ell+\tau_{n,b_{*}}^{j}$, $\phi_{4}=n-z-\tau_{n,b_{*}}^{j}$ and
$\kappa=\ell/80$. Observe that
$\tilde{Q}_{n,\hat{b}}^{\hat{j}}\geq\tilde{Q}_{n,b_{*}}^{\hat{j}}$. Thus, by a
union bound, we have

$\displaystyle\mathbb{P}(\Omega_{0}$
$\displaystyle\cap\Omega_{1}\cap\Omega_{2}\cap\Omega_{3}^{\mathrm{c}})$
$\displaystyle\leq\sum_{j=1}^{p}\sum_{b\in\mathcal{B}}\sum_{n=z+1}^{z+\lfloor
r\rfloor}\mathbb{P}\Bigl{(}\\{N=n\\}\cap\Omega_{1}\cap\Omega_{2}\cap\bigl{\\{}\tilde{Q}_{n,b}^{j}\geq\tilde{Q}_{n,b_{*}}^{j}\bigr{\\}}\cap\bigl{\\{}\tau_{n,b}^{j}>n-z+\ell/20\bigr{\\}}\Bigr{)}$
$\displaystyle\leq 2rp^{2}\log_{2}(2p)\exp\biggl{(}-\frac{\ell
a^{2}}{3840(r+\ell)}\biggr{)}.$ (10)

When $C_{3}\geq 144C_{2}^{2}\vee 80C_{5}\vee 160$, we have $\ell_{0}\geq 80r$
and $d_{1}\leq\frac{\sqrt{\ell_{0}}\beta}{12\sqrt{s\log_{2}(2p)}}\leq
b^{1}\sqrt{\ell}/12$. Thus, on $\Omega_{0}\cap\Omega_{3}$, we have

$\tau_{N,\hat{b}}^{\hat{j}}\leq N-z+\ell/20\leq r+\ell/20\leq\ell/16.$

Hence, for any $z<n\leq z+r,j\in[p]\setminus\\{1\\}$ and $b\in\mathcal{B}$, we
have

$\displaystyle\mathbb{P}\bigl{(}\Omega_{3}$
$\displaystyle\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\cap\Omega_{4,1}^{\mathrm{c}}\bigm{|}X_{1}^{j},X_{2}^{j},\ldots\bigl{)}$
$\displaystyle\leq\mathbb{P}\biggl{(}\\{\tau_{n,b}^{j}\leq\ell/16\\}\cap\Bigl{\\{}\Xi_{n,b}^{1,j}-b^{1}\sqrt{\bigl{(}\tau_{n,b}^{j}+\ell\bigr{)}/2}<d_{1}\Bigr{\\}}\biggm{|}X_{1}^{j},X_{2}^{j},\ldots\biggr{)}\leq\frac{1}{2}e^{-d_{1}^{2}/2}.$

Here, in the final bound, we have used the facts that
$\Xi_{n,b}^{1,j}\mid\tau_{n,b}^{j}\sim\mathcal{N}\bigl{(}\theta^{1}\min\\{(n+\ell-z)(\tau_{n,b}^{j}+\ell)^{-1/2},(\tau_{n,b}^{j}+\ell)^{1/2}\\},1\bigr{)}$
and that

$\displaystyle\theta^{1}\min\bigl{\\{}(n+\ell-z)(\tau_{n,b}^{j}$
$\displaystyle+\ell)^{-1/2},(\tau_{n,b}^{j}+\ell)^{1/2}\bigr{\\}}-b^{1}\sqrt{\bigl{(}\tau_{n,b}^{j}+\ell\bigr{)}/2}$
$\displaystyle\geq\frac{4\theta^{1}\sqrt{\ell}}{\sqrt{17}}-\frac{b^{1}\sqrt{17\ell}}{4\sqrt{2}}\geq\frac{b^{1}\sqrt{\ell}}{6}\geq
2d_{1},$

when $\tau_{n,b}^{j}\leq\ell/16$, as well as the standard Gaussian tail bound
used at the end of the proof of Lemma 5. By a similar argument, we also have
for any $z<n\leq z+r$ and $b\in\mathcal{B}$ that

$\displaystyle\mathbb{P}\bigl{(}\Omega_{3}$
$\displaystyle\cap\\{N=n,\hat{j}=1,\hat{b}=b\\}\cap\Omega_{4,2}^{\mathrm{c}}\bigm{|}X_{1}^{1},X_{2}^{1},\ldots\bigl{)}$
$\displaystyle\leq\mathbb{P}\biggl{(}\\{\tau_{n,b}^{1}\leq\ell/16\\}\cap\Bigl{\\{}\Xi_{n,b}^{2,1}-b^{2}\sqrt{\bigl{(}\tau_{n,b}^{1}+\ell\bigr{)}/2}<d_{1}\Bigr{\\}}\Bigm{|}X_{1}^{1},X_{2}^{1},\ldots\biggr{)}\leq\frac{1}{2}e^{-d_{1}^{2}/2}.$

Thus, by a union bound, we have

$\displaystyle\mathbb{P}(\Omega_{0}\cap\Omega_{3}\cap\Omega_{4}^{\mathrm{c}})$
$\displaystyle=\mathbb{P}(\Omega_{0}\cap\Omega_{3}\cap\Omega_{4,1}^{\mathrm{c}}\cap\Omega_{4,2}^{\mathrm{c}})$
$\displaystyle\leq\sum_{j=2}^{p}\sum_{b\in\mathcal{B}}\sum_{n=z+1}^{z+\lfloor
r\rfloor}\mathbb{P}\bigl{(}\Omega_{3}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\cap\Omega_{4,1}^{\mathrm{c}}\bigr{)}$
$\displaystyle\hskip 85.35826pt+\sum_{b\in\mathcal{B}}\sum_{n=z+1}^{z+\lfloor
r\rfloor}\mathbb{P}\bigl{(}\Omega_{3}\cap\\{N=n,\hat{j}=1,\hat{b}=b\\}\cap\Omega_{4,2}^{\mathrm{c}}\bigr{)}$
$\displaystyle\leq rp\log_{2}(2p)e^{-d_{1}^{2}/2}.$ (11)

Hence by substituting (5), (8), (9), (5) and (5) into (6), we conclude that,
by increasing the universal constant $C_{1}>0$ if necessary,

$\displaystyle\mathbb{P}\Biggl{(}$ $\displaystyle
L>C_{4}\biggl{(}\frac{s\log_{2}(2p)\log\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}}{\beta^{2}}+1\biggr{)}\Biggr{)}$ $\displaystyle\leq
2p\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}C_{5}s/128}+\frac{z}{4\gamma}+2p\log_{2}(4p)\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}C_{3}/640}$
$\displaystyle\quad+2rp^{2}\log_{2}(4p)\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}/8}+2rp^{2}\log_{2}(2p)\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}/3888}$
$\displaystyle\quad+rp\log_{2}(2p)\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}C_{2}^{2}/2}$ $\displaystyle\leq\alpha,$

as required. ∎

###### Proof of Theorem 3.

(a) For $j^{\prime}\in\mathcal{S}_{\beta}^{c}$, we have
$|\theta^{j^{\prime}}|<b_{\min}$, so the event
$\\{|\tilde{b}^{j^{\prime}}|\leq|\theta^{j^{\prime}}|\\}$ is empty. Thus by
(3), we have, for $n>z,j\in[p]$, $b\in\mathcal{B}$ and
$j^{\prime}\in\mathcal{S}_{\beta}^{\mathrm{c}}$, that

$\mathbb{P}_{z,\theta}\bigl{(}\\{j^{\prime}\in\hat{\mathcal{S}}\\}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\bigr{)}\leq
2\bar{\Phi}(d_{1}).$

Hence, recalling the definition of $r_{0}$ from (5), by Lemma 7 applied with
$C_{1}\geq\sqrt{8}$, a union bound and Proposition 6, we have

$\displaystyle\mathbb{P}_{z,\theta}(\hat{\mathcal{S}}\nsubseteq\mathcal{S}_{\beta})$
$\displaystyle\leq\mathbb{P}_{z,\theta}(N\leq
z)+\mathbb{P}_{z,\theta}(N>z+r_{0})$ $\displaystyle\hskip
85.35826pt+\sum_{n=z+1}^{z+\lfloor
r_{0}\rfloor}\sum_{j=1}^{p}\sum_{b\in\mathcal{B}}\sum_{j^{\prime}\in\mathcal{S}_{\beta}^{\mathrm{c}}}\mathbb{P}_{z,\theta}\bigl{(}\\{j^{\prime}\in\hat{\mathcal{S}}\\}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\bigr{)}$
$\displaystyle\leq\frac{\alpha}{2}+\exp\biggl{\\{}-\frac{\beta^{2}(r_{0}-1)}{48\log_{2}(2p)}\biggr{\\}}+p\exp\biggl{\\{}-\frac{\vartheta^{2}(r_{0}-1)}{128\log_{2}(2p)}\biggr{\\}}\\!+\\!4p^{2}\log_{2}(2p)r_{0}\bar{\Phi}(d_{1})\leq\alpha,$

where the final bound follows as in the proof of Theorem 1.

(b) We use the events $\Omega_{0},\Omega_{1},\Omega_{2},\Omega_{3}$ defined in
the proof of Theorem 2. Recall from the argument immediately below (5) that
when $C_{3}\geq 144C_{2}^{2}\vee 80C_{5}\vee 160$, we have
$\tau_{N,\hat{b}}^{\hat{j}}\leq\ell/16$ and
$d_{1}\leq\min_{j^{\prime}\in\mathcal{S}}|\theta^{j^{\prime}}|\sqrt{\ell}/12$
on $\Omega_{0}\cap\Omega_{3}$. Recall also the definition of
$\Xi_{n,b}^{j^{\prime},j}$ from Algorithm 2. Then, for any $z<n\leq z+r$,
$j\in[p]$, $j^{\prime}\in\mathcal{S}\setminus\\{j\\}$ and $b\in\mathcal{B}$,
we have

$\displaystyle\mathbb{P}_{z,\theta}$
$\displaystyle\bigl{(}\Omega_{3}\cap\\{N=n,\hat{j}=j,\hat{b}=b,j^{\prime}\notin\hat{\mathcal{S}}\\}\bigm{|}X_{1}^{j},X_{2}^{j},\ldots\bigr{)}$
$\displaystyle=\mathbb{P}_{z,\theta}\Bigl{(}\Omega_{3}\cap\\{N=n,\hat{j}=j,\hat{b}=b\\}\cap\bigl{\\{}|\Xi_{n,b}^{j^{\prime},j}|<b_{\min}\sqrt{\tau_{n,b}^{j}+\ell}+d_{1}\bigr{\\}}\mid
X_{1}^{j},X_{2}^{j},\ldots\Bigr{)}$
$\displaystyle\leq\mathbb{P}_{z,\theta}\biggl{(}\\{\tau_{n,b}^{j}\leq\ell/16\\}\cap\Bigl{\\{}|\Xi_{n,b}^{j^{\prime},j}|-b_{\min}\sqrt{\tau_{n,b}^{j}+\ell}<d_{1}\Bigr{\\}}\biggm{|}X_{1}^{j},X_{2}^{j},\ldots\biggr{)}\leq\frac{1}{2}e^{-d_{1}^{2}/2},$
(12)

where, in the final bound, we have used the facts that
$\Xi_{n,b}^{j^{\prime},j}\mid\tau_{n,b}^{j}\sim\mathcal{N}\bigl{(}\theta^{j^{\prime}}\min\\{(n+\ell-z)(\tau_{n,b}^{j}+\ell)^{-1/2},(\tau_{n,b}^{j}+\ell)^{1/2}\\},1\bigr{)}$
and that

$\displaystyle|\theta^{j^{\prime}}|\min\bigl{\\{}(n+\ell-z)(\tau_{n,b}^{j}$
$\displaystyle+\ell)^{-1/2},(\tau_{n,b}^{j}+\ell)^{1/2}\bigr{\\}}-b_{\min}\sqrt{\tau_{n,b}^{j}+\ell}$
$\displaystyle\geq\frac{4|\theta^{j^{\prime}}|\sqrt{\ell}}{\sqrt{17}}-\frac{b_{\min}\sqrt{17\ell}}{4\sqrt{2}}\geq\frac{|\theta^{j^{\prime}}|\sqrt{\ell}}{6}\geq
2d_{1},$

when $\tau_{n,b}^{j}\leq\ell/16$. Hence

$\displaystyle\mathbb{P}_{z,\theta}$
$\displaystyle(\hat{\mathcal{S}}\cup\\{\hat{j}\\}\nsupseteq\mathcal{S})$
$\displaystyle\leq\mathbb{P}_{z,\theta}(\Omega_{0}^{\mathrm{c}})+\mathbb{P}_{z,\theta}(\Omega_{0}\cap\Omega_{1}^{\mathrm{c}})+\mathbb{P}_{z,\theta}(\Omega_{0}\cap\Omega_{2}^{\mathrm{c}})+\mathbb{P}_{z,\theta}(\Omega_{0}\cap\Omega_{1}\cap\Omega_{2}\cap\Omega_{3}^{\mathrm{c}})$
$\displaystyle\quad+\sum_{n=z+1}^{z+\lfloor
r\rfloor}\sum_{j=1}^{p}\sum_{b\in\mathcal{B}}\sum_{j^{\prime}\in\mathcal{S}\setminus\\{j\\}}\mathbb{P}_{z,\theta}\bigl{(}\Omega_{3}\cap\\{N=n,\hat{j}=j,\hat{b}=b,j^{\prime}\notin\hat{\mathcal{S}}\\}\bigr{)}$
$\displaystyle\leq 2p\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}C_{5}s/128}+\frac{z}{4\gamma}+2p\log_{2}(4p)\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}C_{3}/640}$
$\displaystyle\quad+2rp^{2}\log_{2}(4p)\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}/8}+2rp^{2}\log_{2}(2p)\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}/3888}$
$\displaystyle\quad+rp^{2}\log_{2}(2p)\\{p\gamma(\beta^{-2}\vee
1)\alpha^{-1}\\}^{-C_{1}^{2}C_{2}^{2}/2}\leq\alpha,$

where the penultimate inequality follows from (5), (8), (9), (5) and (5), and
the last inequality follows by choosing the universal constant $C_{1}>0$ to be
sufficiently large. ∎

##  6 Auxiliary results

######  Proposition 4.

Let $X_{1},X_{2},\ldots$ be independent random variables with
$X_{1},\ldots,X_{z}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathcal{N}(0,1)$
and
$X_{z+1},X_{z+2},\ldots\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathcal{N}(\theta,1)$.
Assume that $0<b\leq\theta$ and let $t_{n,b}$ be defined as in (1) for
$n\in\mathbb{N}$. Then for any $\alpha\in(0,1)$, and any stopping time $N$
satisfying $\mathbb{P}(N<z)\leq\alpha/2$, we have that the confidence interval

$\mathcal{C}_{0}:=\biggl{[}N-t_{N,b}-\frac{4\\{\Phi^{-1}(1-\alpha/4)\\}^{2}}{b^{2}},\,N\biggr{]}$

satisfies $\mathbb{P}(z\in\mathcal{C}_{0})\geq 1-\alpha$.

######  Remark.

We could also replace $4\\{\Phi^{-1}(1-\alpha/4)\\}^{2}/b^{2}$ by
$8\log(2/\alpha)/b^{2}$ in the confidence interval construction, if we apply
the final bound from Lemma 5 in (13).

###### Proof.

For $n\in\mathbb{N}$, define $R_{n,b}:=\max\\{R_{n-1,b}+b(X_{n}-b/2),0\\}$,
with $R_{0,b}=0$. By Chen et al. (2021, Lemma 2 in the supplement), we have
$t_{N,b}=\min\\{i:0\leq i\leq N,R_{N-i,b}=0\\}=\operatorname*{sargmax}_{0\leq
h\leq N}\sum_{i=N-h+1}^{N}b(X_{i}-b/2)$. Let
$U_{n,b}:=\sum_{i=z+1}^{z+n}(X_{i}-b/2)$ for $n\in\mathbb{N}$, with
$U_{0,b}:=0$. Then $R_{n+z,b}\geq bU_{n,b}$ for all $n\in\mathbb{N}$. Hence,
for $y\in[0,\infty)$, we have

$\mathbb{P}(N-t_{N,b}-y\geq
z)\leq\mathbb{P}\biggl{(}\inf_{n\in\mathbb{N}_{0}:n\geq
z+y}R_{n,b}=0\biggr{)}\leq\mathbb{P}\biggl{(}\inf_{n\in\mathbb{N}_{0}:n\geq
y}U_{n,b}\leq 0\biggr{)}\leq 2\bar{\Phi}\Bigl{(}\sqrt{y}(\theta-b/2)\Bigr{)},$
(13)

where the last inequality follows from Lemma 5. Thus, if we choose
$y=4\\{\Phi^{-1}(1-\alpha/4)\\}^{2}/b^{2}$, then we are guaranteed that
$\mathbb{P}(N-t_{N,b}-y>z)\leq\alpha/2$. Combining this with the assumption
that $\mathbb{P}(N<z)\leq\alpha/2$, the desired result follows. ∎

######  Lemma 5.

Let
$Y_{1},Y_{2},\ldots\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathcal{N}(\mu,1)$.
Define $U_{n}:=\sum_{i=1}^{n}Y_{i}$ for $n\in\mathbb{N}_{0}$, and let
$\xi:=\operatorname*{sargmin}_{n\in\mathbb{N}_{0}}\mu U_{n}$. Then, for
$y\in[0,\infty)$, we have

$\mathbb{P}(\xi\geq y)\leq\mathbb{P}\Bigl{(}\inf_{n\in\mathbb{N}_{0}:n\geq
y}\mu U_{n}\leq 0\Bigr{)}\leq 2\bar{\Phi}\bigl{(}\sqrt{y}|\mu|\bigr{)}\leq
e^{-y\mu^{2}/2}.$

###### Proof.

The first inequality holds since $\mu U_{\xi}\leq\mu U_{0}=0$. For the second
and third inequalities, we may assume without loss of generality that $\mu>0$,
since the result is clear when $\mu=0$, and if $\mu<0$ then the result will
follow from the corresponding result with $\mu>0$ by setting
$Y_{i}^{\prime}:=-Y_{i}$ for $i\in\mathbb{N}$. Note that
$(U_{n}-n\mu)_{n\in\mathbb{N}_{0}}$ is a standard Gaussian random walk
starting at 0. Let $(B_{t})_{t\in[0,\infty)}$ denote a standard Brownian
motion starting at 0. Then, we have for any $y\in\mathbb{N}_{0}$ and $u>0$
that

$\mathbb{P}\biggl{(}\inf_{n\in\mathbb{N}_{0}:n\geq y}U_{n}\leq
0\biggm{|}U_{y}=u\biggr{)}\leq\mathbb{P}\biggl{\\{}\inf_{t\in[y,\infty)}(B_{t}+t\mu)\leq
0\biggm{|}B_{y}=u\biggr{\\}}\leq e^{-2u\mu},$ (14)

where the final inequality follows from Siegmund (1986, Proposition 2.4 and
Equation (2.5)). Thus, for $y\in[0,\infty)$, we have

$\displaystyle\mathbb{P}\biggl{(}\inf_{n\in\mathbb{N}_{0}:n\geq y}U_{n}\leq
0\biggr{)}$ $\displaystyle=\mathbb{P}\bigl{(}U_{\lceil y\rceil}\leq
0\bigr{)}+\mathbb{E}\biggl{\\{}\mathbb{P}\biggl{(}\inf_{n\in\mathbb{N}_{0}:n\geq\lceil
y\rceil}U_{n}\leq 0\biggm{|}U_{\lceil
y\rceil}\biggr{)}\mathbbm{1}_{\\{U_{\lceil y\rceil}>0\\}}\Bigr{\\}}$
$\displaystyle\leq\bar{\Phi}\Bigl{(}\sqrt{\lceil
y\rceil}\mu\Bigr{)}+\int_{0}^{\infty}\frac{1}{\sqrt{2\pi\lceil
y\rceil}}e^{-\frac{(u-\lceil y\rceil\mu)^{2}}{2\lceil y\rceil}}e^{-2u\mu}\,du$
$\displaystyle=2\bar{\Phi}\Bigl{(}\sqrt{\lceil y\rceil}\mu\Bigr{)}\leq
2\bar{\Phi}\bigl{(}\sqrt{y}\mu\bigr{)}\leq e^{-y\mu^{2}/2}.$

where the first inequality follows from (14) and the fact that $U_{\lceil
y\rceil}\sim\mathcal{N}(\lceil y\rceil\mu,\lceil y\rceil)$ and the last
inequality follows from the standard normal distribution tail bound
$\bar{\Phi}(x)\leq e^{-x^{2}/2}/2$ for $x\geq 0$. ∎

In Proposition 6 and Lemma 7 below, we assume the Gaussian data generating
mechanism given at the beginning of Section 3.

######  Proposition 6.

Assume that $\theta$ has an effective sparsity of $s:=s(\theta)\geq 2$. Then,
the right endpoint $N$ of the interval output from the ocd_CI′ algorithm, with
inputs $(X_{t})_{t\in\mathbb{N}}$, $0<\beta\leq\vartheta$, $a>0$,
$T^{\mathrm{diag}}=\log\\{16p\gamma\log_{2}(4p)\\}$ and
$T^{\mathrm{off}}=8\log\\{16p\gamma\log_{2}(2p)\\}$, satisfies

$\mathbb{P}_{z,\theta}\bigl{(}N>z+r\bigl{)}\leq\exp\biggl{\\{}-\frac{\beta^{2}(r-1)}{48\log_{2}(2p)}\biggr{\\}}+p\exp\biggl{\\{}-\frac{\vartheta^{2}(r-1)}{128\log_{2}(2p)}\biggr{\\}},$

for all
$r\geq\Bigl{\\{}\frac{24T^{\mathrm{off}}\log_{2}(2p)}{\vartheta^{2}}\vee\frac{12(a^{2}\vee
8\log
2)s\log_{2}(2p)}{\vartheta^{2}}\vee\frac{24T^{\mathrm{diag}}s\log_{2}(2p)}{\beta^{2}}\Bigr{\\}}+2$.

###### Proof.

For $\theta\in\mathbb{R}^{p}$ with effective sparsity $s(\theta)$, there is at
most one coordinate in $\theta$ of magnitude larger than $\vartheta/\sqrt{2}$,
so there exists
$b_{*}\in\bigl{\\{}\beta/\sqrt{s(\theta)\log_{2}(2p)},-\beta/\sqrt{s(\theta)\log_{2}(2p)}\bigr{\\}}\subseteq\mathcal{B}$
such that

$\mathcal{J}:=\Bigl{\\{}j\in[p]:\theta^{j}/b_{*}\geq 1\text{ and
}|\theta^{j}|\leq\vartheta/\sqrt{2}\Bigr{\\}}$ (15)

has cardinality at least $s(\theta)/2$. Note that the condition
$\theta^{j}/b_{*}\geq 1$ above ensures that $\\{\theta^{j}:j\in\mathcal{J}\\}$
all have the same sign as $b_{*}$. By Chen et al. (2021, Proposition 8), we
have on the event $\\{N>z\\}$ that

$q(X_{1},\ldots,X_{z},\theta):=\max\bigl{\\{}t_{z,b_{*}}^{j}:j\in\mathcal{J}\bigr{\\}}\leq\frac{8T^{\mathrm{diag}}s\log_{2}(2p)}{\beta^{2}}.$
(16)

We now fix

$r\geq\biggl{\\{}\frac{24T^{\mathrm{off}}\log_{2}(2p)}{\vartheta^{2}}\vee\frac{12(a^{2}\vee
8\log
2)s\log_{2}(2p)}{\vartheta^{2}}\vee\frac{24T^{\mathrm{diag}}s\log_{2}(2p)}{\beta^{2}}\biggr{\\}}+2=:r_{0}.$
(17)

For $j\in\mathcal{J}$, define the event

$\Omega_{r}^{j}:=\bigl{\\{}t_{z+\lfloor r\rfloor,b_{*}}^{j}>2\lfloor
r\rfloor/3\bigr{\\}}.$

By applying Chen et al. (2021, Lemma 2) to $t_{z+\lfloor r\rfloor,b_{*}}^{j}$,
we have for $j\in\mathcal{J}$ that

$\displaystyle t_{z+\lfloor r\rfloor,b_{*}}^{j}$
$\displaystyle=\operatorname*{sargmax}_{0\leq h\leq z+\lfloor
r\rfloor}\sum_{i=z+\lfloor r\rfloor-h+1}^{z+\lfloor
r\rfloor}b_{*}(X_{i}^{j}-b_{*}/2)\geq\operatorname*{sargmax}_{0\leq
h\leq\lfloor r\rfloor}\sum_{i=z+\lfloor r\rfloor-h+1}^{z+\lfloor
r\rfloor}b_{*}(X_{i}^{j}-b_{*}/2)$
$\displaystyle=\operatorname*{sargmax}_{0\leq h\leq\lfloor
r\rfloor}\sum_{i=z+1}^{z+\lfloor r\rfloor-h}-b_{*}(X_{i}^{j}-b_{*}/2)=\lfloor
r\rfloor-\operatorname*{largmax}_{0\leq h\leq\lfloor
r\rfloor}\sum_{i=z+1}^{z+h}-b_{*}(X_{i}^{j}-b_{*}/2).$

Recall that
$X_{z+1},X_{z+2},\ldots\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathcal{N}_{p}(\theta,I_{p})$.
Hence, by applying Chen et al. (2021, Lemma 6(b)) with $a=0,b=|b_{*}|/2$ and
$c=\lfloor r\rfloor/3$, we have

$\displaystyle\mathbb{P}_{z,\theta}\biggl{(}\bigcap_{j\in\mathcal{J}}(\Omega_{r}^{j})^{\mathrm{c}}\biggr{)}$
$\displaystyle=\prod_{j\in\mathcal{J}}\mathbb{P}_{z,\theta}\biggl{(}t_{z+\lfloor
r\rfloor,b_{*}}^{j}\leq\frac{2\lfloor r\rfloor}{3}\biggr{)}$
$\displaystyle\leq\prod_{j\in\mathcal{J}}\mathbb{P}_{z,\theta}\biggl{(}\operatorname*{largmax}_{0\leq
h\leq\lfloor
r\rfloor}\sum_{i=z+1}^{z+h}-b_{*}(X_{i}^{j}-b_{*}/2)\geq\frac{\lfloor
r\rfloor}{3}\biggr{)}$
$\displaystyle\leq\prod_{j\in\mathcal{J}}\mathbb{P}_{z,\theta}\biggl{(}\sup_{h\geq\lfloor
r\rfloor/3}\sum_{i=z+1}^{z+h}-\mathrm{sgn}(b_{*})(X_{i}^{j}-b_{*}/2)\geq
0\biggr{)}$ $\displaystyle\leq\exp\bigl{(}-|\mathcal{J}|b_{*}^{2}\lfloor
r\rfloor/24\bigr{)}\leq\exp\bigl{(}-sb_{*}^{2}\lfloor r\rfloor/48\bigr{)}.$
(18)

We now work on the event $\Omega_{r}^{j}$, for some fixed $j\in\mathcal{J}$.
We note that (17) guarantees that $r\geq 2$, and thus $t_{z+\lfloor
r\rfloor,b_{*}}^{j}\geq\bigl{\lceil}2\lfloor r\rfloor/3\bigr{\rceil}\geq 2$.
Then, by (16) and (17), we have $r_{0}>3t_{z,b_{*}}^{j}$, and hence by Chen et
al. (2021, Lemma 9),

$\frac{\lfloor r\rfloor}{3}<\frac{t_{z+\lfloor
r\rfloor,b_{*}}^{j}}{2}\leq\tau_{z+\lfloor
r\rfloor,b_{*}}^{j}\leq\frac{3t_{z+\lfloor
r\rfloor,b_{*}}^{j}}{4}\leq\frac{3\bigl{(}t_{z,b_{*}}^{j}+r\bigr{)}}{4}<r.$

We conclude that

$2/3\leq\lfloor r\rfloor/3<\tau_{z+\lfloor r\rfloor,b_{*}}^{j}\leq\lfloor
r\rfloor.$ (19)

Recall that $\Lambda_{z+\lfloor
r\rfloor,b_{*}}^{\bm{\cdot},j}\in\mathbb{R}^{p}$ records the tail CUSUM
statistics with tail length $\tau_{z+\lfloor r\rfloor,b_{*}}^{j}$. We observe
by (19) that only post-change observations are included in $\Lambda_{z+\lfloor
r\rfloor,b_{*}}^{\bm{\cdot},j}$. Hence we have that

$\Lambda_{z+\lfloor r\rfloor,b_{*}}^{k,j}\bigm{|}\tau_{z+\lfloor
r\rfloor,b_{*}}^{j}\stackrel{{\scriptstyle\mathrm{ind}}}{{\sim}}\mathcal{N}\bigl{(}\theta^{k}\tau_{z+\lfloor
r\rfloor,b_{*}}^{j},\tau_{z+\lfloor r\rfloor,b_{*}}^{j}\bigr{)}$ (20)

for $k\in[p]\setminus\\{j\\}$. By the definition of the effective sparsity of
$\theta$, the set

${\mathcal{L}}^{j}:=\biggl{\\{}j^{\prime}\in[p]:|\theta^{j^{\prime}}|\geq\frac{\vartheta}{\sqrt{s\log_{2}(2p)}}\text{
and }j^{\prime}\neq j\biggr{\\}}$

has cardinality at least $s-1$. Hence, by (19), for all
$k\in{\mathcal{L}}^{j}$,

$|\theta^{k}|\sqrt{\tau_{z+\lfloor
r\rfloor,b_{*}}^{j}}>\sqrt{\frac{\vartheta^{2}\lfloor
r\rfloor}{3s\log_{2}(2p)}}=:\tilde{a}_{r}.$

We then observe, from (17), that

$\tilde{a}_{r}>2\bigl{(}a\vee\sqrt{8\log 2}\bigr{)}.$ (21)

Hence, from (20), we have for all $k\in{\mathcal{L}}^{j}$ that

$\displaystyle\mathbb{P}_{z,\theta}\biggl{(}\Omega_{r}^{j}\cap\biggl{\\{}|\Lambda^{k,j}_{z+\lfloor
r\rfloor,b_{*}}|<\frac{1}{2}\tilde{a}_{r}\sqrt{\tau^{j}_{z+\lfloor
r\rfloor,b_{*}}}\biggr{\\}}\biggm{|}$ $\displaystyle\tau_{z+\lfloor
r\rfloor,b_{*}}^{j}\biggr{)}\leq\frac{1}{2}e^{-\tilde{a}_{r}^{2}/8}=:q_{r}.$

We denote

$U^{j}:=\biggl{|}\biggl{\\{}k\in{\mathcal{L}}^{j}:|\Lambda^{k,j}_{z+\lfloor
r\rfloor,b_{*}}|<\frac{1}{2}\tilde{a}_{r}\sqrt{\tau^{j}_{z+\lfloor
r\rfloor,b_{*}}}\biggr{\\}}\biggr{|}.$

Then, by the Chernoff–Hoeffding binomial tail bound (Hoeffding, 1963, Equation
(2.1)), we have

$\displaystyle\mathbb{P}_{z,\theta}\Bigl{(}\Omega_{r}^{j}$
$\displaystyle\cap\bigl{\\{}U^{j}\geq|{\mathcal{L}}^{j}|/2\bigr{\\}}\Bigm{|}\tau_{z+\lfloor
r\rfloor,b_{*}}^{j}\Bigr{)}\leq\exp\biggl{\\{}-\frac{|{\mathcal{L}}^{j}|}{2}\log\biggl{(}\frac{1}{4q_{r}(1-q_{r})}\biggr{)}\biggr{\\}}$
$\displaystyle\leq\exp\biggl{\\{}-\frac{|{\mathcal{L}}^{j}|}{2}\biggl{(}\frac{\tilde{a}_{r}^{2}}{8}-\log
2\biggr{)}\biggr{\\}}\leq\exp\biggl{(}-\frac{3|{\mathcal{L}}^{j}|\tilde{a}_{r}^{2}}{64}\biggr{)}\leq\exp\biggl{\\{}-\frac{\vartheta^{2}\lfloor
r\rfloor}{128\log_{2}(2p)}\biggr{\\}},$ (22)

where the penultimate inequality follows from (21). Now, on the event
$\Omega_{r}^{j}\cap\bigl{\\{}U^{j}<|{\mathcal{L}}^{j}|/2\bigr{\\}}$, we have

$\displaystyle\sum_{j^{\prime}\in[p]:j^{\prime}\neq
j}\frac{\bigl{(}\Lambda^{j^{\prime},j}_{z+\lfloor
r\rfloor,b_{*}}\bigr{)}^{2}}{\tau^{j}_{z+\lfloor r\rfloor,b_{*}}\vee 1}$
$\displaystyle\mathbbm{1}_{\bigl{\\{}|\Lambda^{j^{\prime},j}_{z+\lfloor
r\rfloor,b_{*}}|\geq a\sqrt{\tau^{j}_{z+\lfloor
r\rfloor,b_{*}}}\bigr{\\}}}\geq\sum_{j^{\prime}\in[p]:j^{\prime}\neq
j}\frac{\bigl{(}\Lambda^{j^{\prime},j}_{z+\lfloor
r\rfloor,b_{*}}\bigr{)}^{2}}{\tau^{j}_{z+\lfloor r\rfloor,b_{*}}\vee
1}\mathbbm{1}_{\bigl{\\{}|\Lambda^{j^{\prime},j}_{z+\lfloor
r\rfloor,b_{*}}|\geq\frac{1}{2}\tilde{a}_{r}\sqrt{\tau^{j}_{z+\lfloor
r\rfloor,b_{*}}}\bigr{\\}}}$
$\displaystyle\geq\frac{\tilde{a}_{r}^{2}}{4}\biggl{\\{}|{\mathcal{L}}^{j}|-\Bigl{(}\Bigl{\lceil}\frac{|{\mathcal{L}}^{j}|}{2}\Bigr{\rceil}-1\Bigr{)}\biggr{\\}}=\frac{\tilde{a}_{r}^{2}}{4}\biggl{\lceil}\frac{|{\mathcal{L}}^{j}|+1}{2}\biggr{\rceil}\geq\frac{\vartheta^{2}\lfloor
r\rfloor}{24\log_{2}(2p)}\geq T^{\mathrm{off}},$ (23)

where the penultimate inequality uses the fact that $|{\mathcal{L}}^{j}|\geq
s-1$ and the last inequality follows from (17). We now denote

$\tilde{E}_{r}^{j}:=\Biggl{\\{}\sum_{j^{\prime}\in[p]:j^{\prime}\neq
j}\frac{\bigl{(}\Lambda^{j^{\prime},j}_{z+\lfloor
r\rfloor,b_{*}}\bigr{)}^{2}}{\tau^{j}_{z+\lfloor r\rfloor,b_{*}}\vee
1}\mathbbm{1}_{\bigl{\\{}|\Lambda^{j^{\prime},j}_{z+\lfloor
r\rfloor,b_{*}}|\geq a\sqrt{\tau^{j}_{z+\lfloor
r\rfloor,b_{*}}}\bigr{\\}}}<T^{\mathrm{off}}\Biggr{\\}}.$

Combining (18), (6) and (6), we deduce that

$\displaystyle\mathbb{P}_{z,\theta}\bigl{(}N>z+r\bigr{)}$
$\displaystyle\leq\mathbb{P}_{z,\theta}\bigl{(}N>z+\lfloor
r\rfloor\bigr{)}\leq\mathbb{P}_{z,\theta}\biggl{(}\bigcap_{j\in\mathcal{J}}(\Omega_{r}^{j})^{\mathrm{c}}\biggr{)}+\sum_{j\in\mathcal{J}}\mathbb{P}_{z,\theta}\bigl{(}\tilde{E}_{r}^{j}\cap\Omega_{r}^{j}\bigr{)}$
$\displaystyle\leq\mathbb{P}_{z,\theta}\biggl{(}\bigcap_{j\in\mathcal{J}}(\Omega_{r}^{j})^{\mathrm{c}}\biggr{)}+\sum_{j\in\mathcal{J}}\mathbb{P}_{z,\theta}\bigl{(}\Omega_{r}^{j}\cap\bigl{\\{}U^{j}\geq|{\mathcal{L}}^{j}|/2\bigr{\\}}\bigr{)}$
$\displaystyle\leq\exp\biggl{\\{}-\frac{sb_{*}^{2}(r-1)}{48}\biggr{\\}}+p\exp\biggl{\\{}-\frac{\vartheta^{2}(r-1)}{128\log_{2}(2p)}\biggr{\\}},$

as desired. ∎

######  Lemma 7.

Let $p\geq 2$. Then the output $N$ from ocd′, with inputs
$(X_{t})_{t\in\mathbb{N}}$, $0<\beta\leq\vartheta$, $a\geq\sqrt{8\log(p-1)}$,
$T^{\mathrm{diag}}=\log\\{16p\gamma\log_{2}(4p)\\}$ and
$T^{\mathrm{off}}=8\log\\{16p\gamma\log_{2}(2p)\\}$, satisfies

$\mathbb{P}_{z,\theta}(N\leq z)\leq\frac{z}{4\gamma}.$

###### Proof.

This follows from Chen et al. (2021, (16) in the proof of Theorem 1 and (31)
in the proof of Theorem 3). ∎

######  Lemma 8.

Let $U\sim\mathcal{N}(0,\phi_{1})$, $V\sim\mathcal{N}(0,\phi_{2}-\phi_{1})$,
$Y\sim\mathcal{N}(\alpha\phi_{3},\phi_{3})$ and
$Z\sim\mathcal{N}(\alpha\phi_{4},\phi_{4})$ be independent random variables.

  1. (a)

Assume that $\min\\{\phi_{2},\phi_{3}\\}/4\geq\kappa\geq\phi_{1}\geq 0$ for
some $\kappa>0$. Then

$\mathbb{P}\biggl{(}\frac{|U+V+Y|}{\sqrt{\phi_{2}+\phi_{3}}}\geq\frac{|U+Y|}{\sqrt{\phi_{1}+\phi_{3}}}\biggr{)}\leq\exp\biggl{(}-\frac{\kappa\alpha^{2}}{6}\biggr{)}.$

  2. (b)

Assume that $\min\\{\phi_{1},\phi_{3}\\}/4\geq\kappa\geq\phi_{4}\geq 0$ for
some $\kappa>0$. Then

$\mathbb{P}\biggl{(}\frac{|U+Y+Z|}{\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}}\geq\frac{|Y|}{\sqrt{\phi_{3}}}\biggr{)}\leq\exp\biggl{(}-\frac{\kappa\alpha^{2}}{12}\biggr{)}.$

###### Proof.

The case $\alpha=0$ is trivial in both cases, so without loss of generality,
we may assume $\alpha>0$ throughout the rest of the proof.
(a) Let

$W_{1}:=\bigl{(}\sqrt{\phi_{2}+\phi_{3}}-\sqrt{\phi_{1}+\phi_{3}}\bigr{)}(U+Y)-\sqrt{\phi_{1}+\phi_{3}}\,V,$

so that

$\displaystyle
W_{1}\sim\mathcal{N}\Bigl{(}\alpha\phi_{3}\bigl{(}\sqrt{\phi_{2}+\phi_{3}}-\sqrt{\phi_{1}+\phi_{3}}\bigl{)},\bigl{\\{}\bigl{(}\sqrt{\phi_{2}+\phi_{3}}-\sqrt{\phi_{1}+\phi_{3}}\bigr{)}^{2}+\phi_{2}-\phi_{1}\bigr{\\}}(\phi_{1}+\phi_{3})\Bigr{)}.$

Hence, by the standard Gaussian tail bound used at the end of the proof of
Lemma 5, we have

$\mathbb{P}(W_{1}\leq 0)\leq\frac{1}{2}e^{-\alpha^{2}/(2w_{1})},$ (24)

where
$w_{1}:=\frac{\phi_{1}+\phi_{3}}{\phi_{3}^{2}}\bigl{(}1+\frac{\phi_{2}-\phi_{1}}{(\sqrt{\phi_{2}+\phi_{3}}-\sqrt{\phi_{1}+\phi_{3}})^{2}}\bigr{)}$.
Then

$\displaystyle w_{1}$
$\displaystyle=\frac{\phi_{1}+\phi_{3}}{\phi_{3}^{2}}\Biggl{(}1+\frac{\bigl{(}\sqrt{\phi_{2}+\phi_{3}}+\sqrt{\phi_{1}+\phi_{3}}\bigr{)}^{2}}{\phi_{2}-\phi_{1}}\Biggr{)}$
$\displaystyle\leq\frac{5}{16\kappa}\biggl{(}1+\frac{\bigl{(}\sqrt{8\kappa}+\sqrt{5\kappa}\bigr{)}^{2}}{3\kappa}\biggr{)}\leq\frac{3}{\kappa},$
(25)

where the first inequality holds because $w_{1}$ is increasing in $\phi_{1}$
and decreasing in both $\phi_{2}$ and $\phi_{3}$. Hence, using the fact that
$-(U+V+Y)\leq_{\mathrm{st}}U+V+Y$, as well as (24) and (6), we have

$\displaystyle\mathbb{P}\biggl{(}\frac{|U+V+Y|}{\sqrt{\phi_{2}+\phi_{3}}}\geq\frac{|U+Y|}{\sqrt{\phi_{1}+\phi_{3}}}\biggr{)}$
$\displaystyle\leq\mathbb{P}\biggl{(}\biggl{\\{}\frac{U+Y}{\sqrt{\phi_{1}+\phi_{3}}}\leq\frac{U+V+Y}{\sqrt{\phi_{2}+\phi_{3}}}\biggr{\\}}\cap\\{U+V+Y\geq
0\\}\biggr{)}$ $\displaystyle\hskip
8.5359pt+\mathbb{P}\biggl{(}\biggl{\\{}\frac{U+Y}{\sqrt{\phi_{1}+\phi_{3}}}\leq-\frac{U+V+Y}{\sqrt{\phi_{2}+\phi_{3}}}\biggr{\\}}\cap\\{U+V+Y<0\\}\biggr{)}$
$\displaystyle\leq
2\mathbb{P}\biggl{(}\frac{U+Y}{\sqrt{\phi_{1}+\phi_{3}}}\leq\frac{U+V+Y}{\sqrt{\phi_{2}+\phi_{3}}}\biggr{)}$
$\displaystyle=2\mathbb{P}(W_{1}\leq
0)\leq\exp\biggl{(}-\frac{\kappa\alpha^{2}}{6}\biggr{)},$

as required.

(b) Let

$W_{2}:=\bigl{(}\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}-\sqrt{\phi_{3}}\bigr{)}Y-\sqrt{\phi_{3}}(U+Z),$

so that

$\displaystyle
W_{2}\sim\mathcal{N}\Bigl{(}\alpha\phi_{3}\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}-\alpha(\phi_{3}+\phi_{4})\sqrt{\phi_{3}},\bigl{\\{}\bigl{(}\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}-\sqrt{\phi_{3}}\bigr{)}^{2}+\phi_{1}+\phi_{4}\bigr{\\}}\phi_{3}\Bigr{)}.$

Note that the assumption guarantees that $\mathbb{E}(W_{2})>0$. Hence, by the
standard Gaussian tail bound used at the end of the proof of Lemma 5, we have

$\mathbb{P}(W_{2}\leq 0)\leq\frac{1}{2}e^{-\alpha^{2}/(2w_{2})},$ (26)

where

$\displaystyle w_{2}$
$\displaystyle:=\frac{(\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}-\sqrt{\phi_{3}})^{2}+\phi_{1}+\phi_{4}}{\bigl{(}\sqrt{\phi_{3}(\phi_{1}+\phi_{3}+\phi_{4})}-\phi_{3}-\phi_{4}\bigr{)}^{2}}.$

Calculating the partial derivatives of $w_{2}$ with respect to
$\phi_{1},\phi_{3}$ and $\phi_{4}$ and simplifying the expressions, we have

$\displaystyle\frac{\partial w_{2}}{\partial\phi_{1}}$
$\displaystyle=\frac{(\phi_{3}+\phi_{4})\sqrt{\phi_{3}}-(\phi_{3}+2\phi_{4})\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}}{\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}\bigl{(}\sqrt{\phi_{3}(\phi_{1}+\phi_{3}+\phi_{4})}-\phi_{3}-\phi_{4}\bigr{)}^{3}}\leq
0,$ $\displaystyle\frac{\partial w_{2}}{\partial\phi_{3}}$
$\displaystyle=\frac{-\bigl{(}\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}-\sqrt{\phi_{3}}\bigr{)}^{2}\bigl{[}3\phi_{1}+\phi_{4}+\bigl{(}\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}-\sqrt{\phi_{3}}\bigr{)}^{2}\bigr{]}}{2\sqrt{\phi_{3}(\phi_{1}+\phi_{3}+\phi_{4})}\bigl{(}\sqrt{\phi_{3}(\phi_{1}+\phi_{3}+\phi_{4})}-\phi_{3}-\phi_{4}\bigr{)}^{3}}\leq
0,$ $\displaystyle\frac{\partial w_{2}}{\partial\phi_{4}}$
$\displaystyle=\frac{2\phi_{1}\bigl{(}2\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}-\sqrt{\phi_{3}}\bigr{)}^{2}+3(\phi_{3}+\phi_{4})\bigl{(}\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}-\sqrt{\phi_{3}}\bigr{)}^{2}}{2(\phi_{1}+\phi_{3}+\phi_{4})\bigl{(}\sqrt{\phi_{3}(\phi_{1}+\phi_{3}+\phi_{4})}-\phi_{3}-\phi_{4}\bigr{)}^{3}}$
$\displaystyle\hskip
28.45274pt+\frac{(\phi_{1}+\phi_{4})(\phi_{3}+\phi_{4})}{2(\phi_{1}+\phi_{3}+\phi_{4})\bigl{(}\sqrt{\phi_{3}(\phi_{1}+\phi_{3}+\phi_{4})}-\phi_{3}-\phi_{4}\bigr{)}^{3}}\geq
0.$

Thus $w_{2}$ is increasing in $\phi_{4}$ and decreasing in both $\phi_{1}$ and
$\phi_{3}$ and hence

$\displaystyle w_{2}\leq\frac{6}{\kappa}.$ (27)

Hence, using the fact that $-(U+Y+Z)\leq_{\mathrm{st}}U+Y+Z$, as well as (26)
and (27), we have

$\displaystyle\mathbb{P}\biggl{(}\frac{|U+Y+Z|}{\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}}\geq\frac{|Y|}{\sqrt{\phi_{3}}}\biggr{)}$
$\displaystyle\leq\mathbb{P}\biggl{(}\biggl{\\{}\frac{Y}{\sqrt{\phi_{3}}}\leq\frac{U+Y+Z}{\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}}\biggr{\\}}\cap\\{U+Y+Z\geq
0\\}\biggr{)}$ $\displaystyle\hskip
8.5359pt+\mathbb{P}\biggl{(}\biggl{\\{}\frac{Y}{\sqrt{\phi_{3}}}\leq-\frac{U+Y+Z}{\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}}\biggr{\\}}\cap\\{U+Y+Z<0\\}\biggr{)}$
$\displaystyle\leq
2\mathbb{P}\biggl{(}\frac{Y}{\sqrt{\phi_{3}}}\leq\frac{U+Y+Z}{\sqrt{\phi_{1}+\phi_{3}+\phi_{4}}}\biggr{)}$
$\displaystyle=2\mathbb{P}(W_{2}\leq
0)\leq\exp\biggl{(}-\frac{\kappa\alpha^{2}}{12}\biggr{)},$

as required. ∎

Acknowledgements: The research of TW was supported by Engineering and Physical
Sciences Research Council (EPSRC) grant EP/T02772X/1 and that of RJS was
supported by EPSRC grants EP/P031447/1 and EP/N031938/1, as well as European
Research Council Advanced Grant 101019498.

## References

  * Cai and Wang (2021) Cai, H. and Wang, T. (2021) Estimation of high-dimensional change-points under a group sparsity structure.  _arXiv preprint_ , arxiv:2107.08724.
  * Chan and Walther (2015) Chan, H. P. and Walther, G. (2015) Optimal detection of multi-sample aligned sparse signals.  _Ann. Statist._ , 43, 1865–1895.
  * Chen et al. (2020) Chen, Y., Wang, T. and Samworth, R. J. (2020) _ocd : high-dimensional, multiscale online changepoint detection_.  R package, available at https://cran.r-project.org/package=ocd.
  * Chen et al. (2021) Chen, Y., Wang, T. and Samworth, R. J. (2021) High-dimensional, multiscale online changepoint detection.  _J. Roy. Statist. Soc., Ser. B_ , to appear.
  * Cho (2016) Cho, H. (2016) Change-point detection in panel data via double CUSUM statistic.  _Elect. J. Statist._ , 10, 2000–2038.
  * Cho and Fryzlewicz (2015) Cho, H. and Fryzlewicz, P. (2015) Multiple-change-point detection for high dimensional time series via sparsified binary segmentation.  _J. Roy. Statist. Soc., Ser. B_ , 77, 475–507.
  * Csörgő and Horváth (1997) Csörgő, M. and Horváth, L. (1997) _Limit Theorems in Change-Point Analysis_.  John Wiley and Sons, New York.
  * Dette and Gösmann (2020) Dette, H. and Gösmann, J. (2020) A likelihood ratio approach to sequential change point detection for a general class of parameters.  _J. Amer. Statist. Assoc._ , 115, 1361–1377.
  * Duncan (1952) Duncan, A. J. (1952) _Quality Control and Industrial Statistics_.  Richard D. Irwin Professional Publishing Inc., Chicago.
  * Enikeeva and Harchaoui (2019) Enikeeva, F. and Harchaoui, Z. (2019) High-dimensional change-point detection under sparse alternatives.  _Ann. Statist._ , 47, 2051–2079.
  * Follain et al. (2021) Follain, B., Wang, T. and Samworth, R. J. (2021) High-dimensional changepoint estimation with heterogeneous missingness.  _arXiv preprint_ , arxiv:2108.01525.
  * Gösmann et al. (2020) Gösmann, J., Stoehr, C., Heiny, J. and Dette, H. (2020) Sequential change point detection in high dimensional time series.  _arXiv preprint_ , arxiv:2006.00636.
  * Hausman and Johnston (2014) Hausman, A. and Johnston, W. J. (2014) Timeline of a financial crisis: Introduction to the special issue.  _J. Bus. Res._ , 67, 2667–2670.
  * Hoeffding (1963) Hoeffding, W. (1963) Probability inequalities for sums of bounded random variables.  _J. Amer. Statist. Assoc._ , 58, 13–30.
  * Horváth and Rice (2014) Horváth, L. and Rice, G. (2014) Extensions of some classical methods in change point analysis.  _TEST_ , 23, 219–255.
  * Janková and van de Geer (2015) Janková, J. and van de Geer, S. (2015) Confidence intervals for high-dimensional inverse covariance estimation.  _Electron. J. Statist._ , 9, 1205–1229.
  * Javanmard and Montanari (2014) Javanmard, A. and Montanari, A. (2014) Confidence intervals and hypothesis testing for high-dimensional regression.  _J. Mach. Learn. Res._ , 15, 2869–2909.
  * Jirak (2015) Jirak, M. (2015) Uniform change point tests in high dimension.  _Ann. Statist._ , 43, 2451–2483.
  * Kaul et al. (2021) Kaul, A., Fotopoulos, S. B., Jandhyala, V. K. and Safikhani, A. (2021) Inference on the change point under a high dimensional sparse mean shift.  _Electron. J. Statist._ , 15, 71–134.
  * Kirch and Stoehr (2019) Kirch, C. and Stoehr, C. (2019) Sequential change point tests based on $U$-statistics.  _arXiv preprint_ , arxiv:1912.08580.
  * Liu et al. (2021) Liu, H., Gao, C. and Samworth, R. J. (2021) Minimax rates in sparse, high-dimensional changepoint detection.  _Ann. Statist._ , 49, 1081–1112.
  * Londschien et al. (2021) Londschien, M., Kovács, S. and Bühlmann, P. (2021) Change-point detection for graphical models in the presence of missing values.  _J. Comput. Graph. Statist._ , 30, 1–12.
  * Padilla et al. (2019) Padilla, O. H. M., Yu, Y., Wang, D. and Rinaldo, A. (2019) Optimal nonparametric multivariate change point detection and localization.  _arXiv preprint_ , arxiv:1910.13289.
  * Page (1954) Page, E. S. (1954) Continuous inspection schemes.  _Biometrika_ , 41, 100–115.
  * Rinaldo et al. (2021) Rinaldo, A., Wang, D., Wen, Q., Willett, R. and Yu, Y. (2021) Localizing changes in high-dimensional regression models.  In _International Conference on Artificial Intelligence and Statistics_ , 2089–2097. PMLR.
  * Ryan et al. (2020) Ryan, J. A., Ulrich, J. M., Thielen, W., Teetor, P., Bronder, S. and Ulrich, M. J. M. (2020) _quantmod : quantitative financial modelling framework_.  R package, available at https://cran.r-project.org/package=quantmod.
  * Siegmund (1986) Siegmund, D. (1986) Boundary crossing probabilities and statistical applications.  _Ann. Statist._ , 14, 361–404.
  * Soh and Chandrasekaran (2017) Soh, Y. S. and Chandrasekaran, V. (2017) High-dimensional change-point estimation: Combining filtering with convex optimization.  _Appl. Comp. Harm. Anal._ , 43, 122–147.
  * Tartakovsky et al. (2014) Tartakovsky, A., Nikiforov, I. and Basseville, M. (2014) _Sequential Analysis: Hypothesis testing and Changepoint Detection_.  Chapman and Hall, London.
  * van de Geer et al. (2014) van de Geer, S., Bühlmann, P., Ritov, Y. and Dezeure, R. (2014) On asymptotically optimal confidence regions and tests for high-dimensional models.  _Ann. Statist._ , 42, 1166–1202.
  * Wang and Samworth (2018) Wang, T. and Samworth, R. J. (2018) High dimensional change point estimation via sparse projection.  _J. Roy. Statist. Soc., Ser. B_ , 80, 57–83.
  * Yu et al. (2021a) Yu, Y., Bradic, J. and Samworth, R. J. (2021a) Confidence intervals for high-dimensional Cox models.  _Statist. Sinica_ , 31, 243–267.
  * Yu et al. (2021b) Yu, Y., Padilla, O. H. M., Wang, D. and Rinaldo, A. (2021b) Optimal network online change point localisation.  _arXiv preprint_ , arxiv:2021.05477.
  * Zhang and Zhang (2014) Zhang, C.-H. and Zhang, S. S. (2014) Confidence intervals for low dimensional parameters in high dimensional linear models.  _J. Roy. Statist. Soc., Ser. B_ , 76, 217–242.