In addition to the fact that we allow some change-points to have an arbitrarily low energy, our requirement for detection scales like $\sqrt{p} + \sqrt{\log(n/r_k)}$ instead of $\sqrt{p \log(n)}$.

The next proposition establishes that the latter condition is minimal. By homogeneity, we can only consider the case where $B = 3/2$. We focus our attention on Gaussian distributions so that the distribution of the sequence $(y_1, \dots, y_n)$ is uniquely defined by the sequence $(\Sigma_1, \dots, \Sigma_n)$ of covariance matrices. Given an integer $1 \le r \le n/4$ and $\zeta \in (0, 1/\sqrt{2})$, we define $\hat{P}(r, \zeta)$ the collection of sequences $\eta = (\Sigma_1, \dots, \Sigma_n)$ of covariance matrices that satisfy either $\Sigma_t = I_p$ or $\|\Sigma_t\|_{op} = 1 + \zeta$. Besides, the corresponding change-points $(\tau_1, \dots, \tau_K)$ of $\eta$ must satisfy $\min_k r_k \ge r$ and $\min_k \|\Sigma_{\tau_k} - \Sigma_{\tau_{k-1}}\|_{op} \ge \zeta$. For $\eta \in \hat{P}(r, \zeta)$, we write $\mathbb{P}_\eta$ for the corresponding distribution of $(y_1, \dots, y_n)$.

**Proposition 6.** There exists a positive numerical constant $c$ such that, for any $n, p$ and any length $1 \le r \le n/4$ the following holds. Provided that $r\zeta^2 \le c(p + \log(n/r)) \wedge \frac{r}{2}$, we have

$$ \inf_{\hat{\tau} \in \hat{P}(r, \zeta)} \sup_{\eta \in \mathcal{P}(r, \zeta)} \mathbb{P}_{\eta}(\hat{K} \neq K) \ge \frac{1}{4}. $$

As a consequence, our procedure $\hat{\tau}$ achieves the minimal separation condition (24) for change-point detection. In their work, [40] obtain faster localization errors than (25) to the price of stronger separation conditions. Our focus in this work is to provide optimal detection conditions and we did not try to optimize (24).

## 6.2. Univariate nonparametric change-point detection

We now turn to the univariate nonparametric change-point model considered in [33]. Let $m \ge 1$ be any positive integer. At each time $t = 1, \dots, n$, the random vector $y_t$ is an $m$-sample of a univariate distribution with cumulative distribution function $F_t$. Then, we aim at detecting a vector $\tau = (\tau_1, \dots, \tau_K)$ of change-points such that $F_{\tau_k} \neq F_{\tau_{k-1}}$. As in [33], we quantify the distance between two distributions by the Kolmogorov distance $\|F_1 - F_2\|_{\infty} = \sup_{z \in \mathbb{R}} |F_1(z) - F_2(z)|$.

As in the previous subsection, we build a procedure $\hat{\tau}$ with our generic algorithm on the dyadic grid. Regarding the collection of tests $(T_{l,r})$, we consider two-sample Kolmogorov-Smirnov tests. More precisely, we denote $\hat{F}_t$ the empirical distribution function associated with the sample $y_t$ and we define the test

$$ T_{l,r} = 1 \left\{ \left\| r^{-1} \left( \sum_{t=l}^{l+r-1} \hat{F}_t - \sum_{t=l-r}^{l-1} \hat{F}_t \right) \right\|_{\infty} \ge \sqrt{2 \frac{\log(4n/(\delta r))}{mr}} \right\}. $$

In the following, a change-point $\tau_k$ is said to have a high-energy if

$$ r_k \|F_{\tau_k} - F_{\tau_{k-1}}\|_{\infty}^{2} \ge \frac{c_1}{m} \log \left( \frac{n}{r_k \delta} \right), \quad (26) $$
random real number $N_i \in [1, 5]$ and define the time series $\eta_i$ by $(\eta_i)_t = N_i \Delta_i \mathbf{1}_{t \ge \tau_i}$. Finally, the signal $\eta = \sum_{i=1}^{10} \eta_i$ has exactly 10 change-points with random locations. As previously, the noise components $(\varepsilon_t)$ follow independent centered and standard gaussian vectors.

3. **Time-dependencies.** We use the same signal as in the segment setting with $s = 20$ but we move away from our assumptions by considering time dependencies. More precisely, the $(\varepsilon_t)$'s are now defined according to an AR process such that $\varepsilon_{t+1} = \rho\varepsilon_t + \sqrt{1-\rho^2}\varepsilon'_{t+1}$ for $t \ge 0$ where $(\varepsilon'_t)$ are independent centered and normalized gaussian vectors, $\rho = 0.05$ for the simulation and by convention $\varepsilon_0 \sim N(0, I_p)$.

**Risk estimation with Monte-Carlo.** In each setting, we generate 500 independent samples and compute the two losses $\mathbf{SAND}((\tau_k), (\hat{\tau}_{k'}))$ and $\mathbf{1}\{\hat{K} \neq K\}$. We estimate the risks $\mathbb{E}[\mathbf{SAND}((\tau_k), (\hat{\tau}_{k'}))]$ and $\mathbb{P}(K \neq \hat{K})$ by averaging the loss over the 500 trials. We also compute 95% confidence intervals.

**Results.** In the segment setting - see Figure 4, 5, 6, the risks tend to decrease as $\alpha$ increases since the higher $\alpha$, the higher the energy of the generated change-points are. As $s$ increases, we can see that both methods need a higher scaling factor to achieve the same risk, which translates the fact that the higher $s$, the more energy is needed to detect a change-point with vector $\Delta$ of sparsity $s$. In the segment settings, our bottom-up procedure tends to achieve significantly smaller loss than the inspect method on average. It is not the case in the multiple change-points setting - see Figure 7 - where the inspect method tends to perform slightly better. In the setting with time-dependencies - see Figure 8 - the risks are worse than the corresponding setting without time-dependencies - see Figure 5 - mainly because adding time-dependencies tends to create more spurious change-points (i.e. false positives).

**Computation time** Our code is implemented with python 3.9 and it mainly uses the convolution function conv1d from pytorch 1.12.1 to compute the Cusum statistics. Simulations are run on CPU (Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz) with 32Go of memory. Running our method on pure noise - i.e. $\theta_t = 0$ for all $t$ - takes $101 \pm 2$ ms while the inspect method takes only $18 \pm 2$ ms to run on average, but optimizing our code is out of the scope of this paper. All the experiments are described in the repository https://github.com/epilliat/multicpdetec.

<figure><img src="image_5.png" /><figcaption>Figure 4: Estimation of $\mathbb{E}[\mathbf{SAND}((\tau_k), (\hat{\tau}_{k'}))]$ and $\mathbb{P}(\hat{K} \neq K)$ in the segment setting with $s = 1$.</figcaption></figure>
where the numerical constant $c_1$ is introduced in the proof of the next proposition. As in Subsection 6.1, it is straightforward to prove, based on Dvoretzky-Kiefer-Wolfowitz inequality, that the FWER of the multiple testing procedures $(T_{l,r})$ with $(l, r) \in \mathcal{G}_D$ is small. Then, we analyze the type II error probability of this test and plug it into the generic result (Theorem 1) to control the behavior of the change-point estimator $\hat{\tau}$.

**Proposition 7.** There exist positive numerical constants $c_1$ and $c_2$ such that the following holds. With probability higher than $1 - \delta$, the change-point estimator $\hat{\tau}$ satisfies (NoSp) and detects all high-energy change-points $\tau_k$ in the sense of (26). Besides, any such high-energy change-points $\tau_k$ satisfies

$$d_{H,1}(\hat{\tau}_{k'}, \tau_k) \le c_2 \frac{\log(\delta^{-1}nm \|F_{\tau_k} - F_{\tau_{k-1}}\|_{\infty}^2)}{m \|F_{\tau_k} - F_{\tau_{k-1}}\|_{\infty}^2} \le \frac{r_k}{4}, \quad (27)$$

under the same event of probability than $1 - \delta$.

In [33], the authors introduce a procedure detecting all the change-points provided that

$$\min_k r_k \min_k \|F_{\tau_k} - F_{\tau_{k-1}}\|_{\infty}^2 \ge c_1 \frac{\log(n)}{m}.$$

Comparing this last condition with (26), we observe that our logarithmic term is tighter and that we allow arbitrarily low-energy change-points.

The next proposition establishes that the condition (26) is unimprovable. Given an integer $1 \le r \le n/4$ and $\zeta \in (0, 1/4)$, we focus our attention on the collection $\tilde{P}(r, \zeta)$ of sequences $(F_1, \dots, F_n)$ of distributions such that the corresponding change-points $(\tau_1, \dots, \tau_K)$ satisfy $\min_k r_k \ge r$ and $\min_k \|F_{\tau_k} - F_{\tau_{k-1}}\|_{\infty} \ge \zeta$. For $\eta \in \tilde{P}(r, \zeta)$, we write $\mathbb{P}_{\eta}$ for the corresponding distribution of the sequence $(y_1, \dots, y_n)$.

**Proposition 8.** There exists a positive numerical constant $c$ such that, for any $n, p$ and any length $1 \le r \le n/4$ the following holds. Provided that $r\zeta^2 \le c' \log(n/r)/m$, we have

$$\inf_{\hat{\tau}} \sup_{\eta \in \tilde{P}(r, \zeta)} \mathbb{P}_{\eta}(\hat{K} \neq K) \ge \frac{1}{4}.$$

# 7. Discussion

## 7.1. Noise distribution for multivariate change-point detection

**Comparison between Gaussian and sub-Gaussian rates** In this work, we have studied two types of noise distribution: Gaussian (Section 3) and general sub-Gaussian distributions (Section 4) without further knowledge on the distribution functions. Since the Gaussian setting is a specific instance of the sub-Gaussian setting, it is clear that the minimax lower bounds from Section 5 apply in both settings. As described in the previous subsection, the performances
<figure><img src="image_6.png" /><figcaption>Figure 5: Estimation of $\mathbb{E}[\text{SAND}((\tau_k), (\hat{\tau}_{k'}))]$ and $\mathbb{P}(\hat{K} \neq K)$ in the segment setting with $s = 20$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 6: Estimation of $\mathbb{E}[\text{SAND}((\tau_k), (\hat{\tau}_{k'}))]$ and $\mathbb{P}(\hat{K} \neq K)$ in the segment setting with $s = 100$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 7: Estimation of $\mathbb{E}[\text{SAND}((\tau_k), (\hat{\tau}_{k'}))]$ and $\mathbb{P}(\hat{K} \neq K)$ in a multiple change-point setting with $K = 10$ where change-points have random norms in $[1, 5]$ and random sparsities in $[1, p]$.</figcaption></figure>
in the sub-Gaussian case almost match those in the Gaussian setting except for $s_k$ slightly lower but close to $\sqrt{p \log(en/r_k)}$. Indeed, in that regime, Berk-Jones or Higher-Criticism type statistics heavily rely on the probability distribution function of the noise, which is not available in the general sub-Gaussian case. Still, we could slightly improve the sub-Gaussian rates if we further assume that the noise components are identically distributed with common CDF F.

* If F is known (know noise distribution), then one may adapt Berk-Jones test by replacing $\tilde{\Phi}(x)$ in Equation (14) by $F(-x)+(1-F(x))$. This would allow us to recover the exact same detection condition as in the Gaussian setting.

* If F is unknown and if there are not too many change-points, one could hope to estimate the quantiles of the CUSUM statistic at each scale r and plug them into a Berk-Jones statistics. This goes however beyond the scope of this paper.

**Unknown variance or more general variance matrix** We assumed in the sparse multivariate sections that the variance $\sigma^2$ is known. Whereas the partial norm test only requires the knowledge of an upper bound on $\sigma$, the dense statistic $\Psi_{l,r}^{(d)}$ requires the exact knowledge of the variance. As soon as there are not too many change-points, it is possible to roughly estimate $\sigma$ and therefore accommodate the partial norm test with an unknown variance. In contrast, the dense statistics needs to be replaced by a U-statistics. Consider any even positive integer r and define

$$ \tilde{\mathbf{C}}_{l,r}(Y) = \frac{\sqrt{r}}{2} \left( \frac{2}{r} \sum_{t=1}^{r/2} Y_{l-2(t-1)-1} - \frac{2}{r} \sum_{t=1}^{r/2} Y_{l+2(t-1)} \right), $$

$$ \tilde{\mathbf{C}}'_{l,r}(Y) = \frac{\sqrt{r}}{2} \left( \frac{2}{r} \sum_{t=1}^{r/2} Y_{l-2t} - \frac{2}{r} \sum_{t=1}^{r/2} Y_{l+2(t-1)+1} \right), $$

where $\tilde{\mathbf{C}}_{l,r}(Y)$ and $\tilde{\mathbf{C}}'_{l,r}(Y)$ are independent. If there is one change-point at position l and no other change-points in $(l-r, l+r)$, then these statistics are identically distributed and we consider $\tilde{\Psi}_{l,r}''^{(d)} = \langle \tilde{\mathbf{C}}_{l,r}(Y), \tilde{\mathbf{C}}'_{l,r}(Y) \rangle$ whose expectation is null when there are no change-points in the segment. As a consequence, $\tilde{\Psi}_{l,r}''^{(d)}$ does not require the knowledge of $\sigma$; only an upper bound of $\sigma$ is required to calibrate the corresponding test. Such a U-statistics has already been introduced in [45] and analyzed in an asymptotic setting. Unfortunately, since we can only consider even r, this precludes us to detecting change-points that are very close together with $r_k = 1$.

In the general case where there is spatial covariance in the noise, that is $\text{var}(\epsilon_t) = \Sigma$ for an unknown but general $\Sigma$, we can still use the same U-statistic described in the previous paragraph for the dense case. For the sparse case, one could use the supremum norm of the CUSUM statistics as in Jirak [21] and Yu and Chen [48]. To calibrate those tests, we need to estimate both the Frobenius
<figure><img src="image_9.png" /><figcaption>Figure 8: Estimation of $E[SAND((\tau_k), (\hat{\tau}_{k'})]]$ and $P(\hat{K} \neq K)$ in the segment setting with $s = 20$ but with time-dependent noise that have an auto-correlation of $\rho = 5\%$.</figcaption></figure>

**Acknowledgements.** The work of A. Carpentier is partially supported by the Deutsche Forschungsgemeinschaft (DFG) Emmy Noether grant MuSyAD (CA 1488/1-1), by the DFG - 314838170, GRK 2297 MathCoRe, by the FG DFG, by the DFG CRC 1294 'Data Assimilation', Project A03, by the Forschungsgruppe FOR 5381 "Mathematical Statistics in the Information Age - Statistical Efficiency and Computational Tractability", Project TP 02, by the Agence Nationale de la Recherche (ANR) and the DFG on the French-German PRCI ANR ASCAI CA 1488/4-1 "Aktive und Batch-Segmentierung, Clustering und Seriation: Grundlagen der KI" and by the UFA-DFH through the French-German Doktorandenkolleg CDFA 01-18 and by the SFI Sachsen-Anhalt for the project RE-BCI. The work of E. Pilliat and N. Verzelen has been partially supported by ANR-21-CE23-0035 (ASCAI). The authors are grateful to two anonymous referees for their helpful comments that improved the presentation of the manuscript.
and the operator norm of $\Sigma$, which seems to be doable as soon as there are not too many change-points. If the spatial covariance matrix $\text{var}(\epsilon_t)$ is unknown and even allowed to change with time, we suspect that the problem becomes intrinsically more involved.

## 7.2. Optimal localization rates

In this work, we mainly considered the problem of **detecting** change-points in the mean of a random vector. We provided tight conditions on the energy so that a change-point is detectable. When such a change-point $\tau_k$ is detected, Corollary 2 states that its position is estimated up to an error of $r_k^*$, which is also of the order of $\sigma^2 \Psi_{n, \bar{\tau}_k, s_k}^{(g)} \Delta_k^{-2}$ – see the definition (9). It is not clear whether this error is optimal or not.

In the univariate setting ($p=1$), [38] has established that, above the detection threshold, a specific change-point position $\tau_k$ can be localized at the rate $\sigma^2 \Delta_k^{-2}$. In the multivariate setting, the situation is more tricky and there are certainly several localization regimes beyond the detection threshold. It is an interesting direction of research to pinpoint the exact localization rate between $\sigma^2 \Delta_k^{-2}$ and $\sigma^2 \Psi_{n, \bar{\tau}_k, s_k}^{(g)} \Delta_k^{-2}$. We leave this for future work.

## 7.3. On the choice of the grid in the generic algorithm

Our general procedure is defined for almost any arbitrary grid. Optimal procedures with the dyadic grid are introduced in Sections 3 and 6, whereas we use a near-optimal procedure on the complete grid in Section 4.

From a computational perspective, the procedure's worst-case complexity is proportional to the size $|\mathcal{G}|$ of the grid $\mathcal{G}$. In that respect, the dyadic grid and more generally the *a*-adic grids benefit from a linear size whereas the size of the complete grid is quadratic.

From a mathematical perspective, it is much easier to control the behaviour of the procedure for an *a*-adic grid by a simple Bonferroni correction on all the statistics as it turns out that this correction is sufficient for our purpose – see the proofs of Section 3. In constrast, controlling larger collections of tests turns out to be much more challenging as one needs to carefully take into account the dependences between the test statistics, which becomes all the more challenging for complex models. As an example, we introduced in Section 3 Berk-Jones statistics to achieve the tight minimax condition for change-point detection. Unfortunately, we did not manage to apply a suitable chaining argument to these statistics and were therefore unable to control the behavior of the corresponding change-point detection procedure on the complete grid.

From a purely statistical perspective, it is difficult to appreciate the respective benefits of denser or sparser grids. On the one hand, for denser grids, the approximation $\bar{\tau}_k$ of $\tau_k$ at scale $r$ will be closer to $\tau_k$ so that the corresponding test $T_{\bar{\tau}_k, r}$ may be more powerful. On the other hand, for a denser grid, the tests
# A An alternative Algorithm

In Algorithm 2 below, we also introduce a variant of the procedure, where instead of merging relevant interesting intervals at the same scale, we only keep one of them. More precisely, we choose the convention of discarding the interval $[l - r + 1, l + r - 1]$ if there exists $l' < l$ such that $T_{l',r} = 1$ and $[l - r + 1, l + r - 1] \cap [l' - r + 1, l' + r - 1] \neq \emptyset$. Alternatively, we could have chosen to discard one of the intervals at random.

**Data:** $y_t, t = 1...n$ and local test statistic $(T_{l,r})_{(l,r) \in \mathcal{G}}$

**Result:** $(\hat{\tau}_k)_{k \le \hat{K}}$

$$S = \emptyset \quad \mathcal{T} = \emptyset;$$

for $r \in \mathcal{R}$ do

for $l \in \mathcal{D}_r$ s.t. $T_{l,r} = 1$ do
    if $[l - r + 1, l + r - 1] \cap S = \emptyset$ then
        $S \leftarrow S \cup [l - r + 1, l + r - 1]$;
        $\mathcal{T} \leftarrow \mathcal{T} \cup \{l\}$;
    end
end

end

return $\mathcal{T}$

**Algorithm 2:** Variant bottom-up aggregation procedure of multiscale tests

# B Proofs

## B.1 Proof of Theorem 1

Let $\Theta \in \mathbb{R}^{n \times p}$, $T$ be a local test statistic, $\mathcal{K}^*$ be a set of indices of significant change-points and $(\bar{\tau}_k, \bar{r}_k)_{k \in \mathcal{K}^*}$ be elements of the grid $\mathcal{G}$ that satisfy (6). We assume that $\mathcal{A}(\Theta, T, \mathcal{K}^*, (\bar{\tau}_k, \bar{r}_k)_{k \in \mathcal{K}^*})$ holds, that is:

1. (No False Positive) $T_{l,r} = 0$ for all $(l,r) \in \mathcal{H}_0 \cap \mathcal{G}$, where $\mathcal{H}_0$ is defined by (7)

2. (Significant change-point detection) for every $k \in \mathcal{K}^*$, we have $T_{\bar{\tau}_k, \bar{r}_k} = 1$.

For every $r \in \mathcal{R}$ define

$$\mathcal{T}_r^* = \{l \in \mathcal{T}_r : \exists k \in \mathcal{K}^* \text{ s.t. } \tau_k \in [l - r + 1, l + r - 1]\},$$

$$S_r^* = \bigcup_{l \in \mathcal{T}_r^*} [l - r + 1, l + r - 1].$$

In other words, for all $r \in \mathcal{R}$, $\mathcal{T}_r^*$ is the subset of $\mathcal{T}_r$ for which each interval of detection $[l - r + 1, l + r - 1]$ contains a significant change-point. The next proposition recursively analyzes the detection sets corresponding to significant change-points $(S_r^*)_{r \ge 1}$. The first inclusion means that significant change-points which can be detected with a local statistic with radius smaller than $r$ are detected before step $r$, while the second inclusion means that each connected component of $\bigcup_{r \in \mathcal{R}} S_r^*$ is included in a close neighborhoods of some significant change-point $\tau_k$, $k \in \mathcal{K}^*$.

**Proposition 9.** For all $r \in \mathcal{R} \cup \{0\}$, we have the double inclusion

$$\{\tau_k : k \in \mathcal{K}^* \text{ and } \bar{r}_k \le r\} \subset \bigcup_{r' \le r, r' \in \mathcal{R}} S_{r'}^* \subset \bigcup_{k \in \mathcal{K}^*} [\tau_k - 2(\bar{r}_k - 1), \tau_k + 2(\bar{r}_k - 1)]. \quad (28)$$
possibly suffer from a higher price for multiplicity. This price can be mild if one takes into account the dependences between the tests. Still, except perhaps in the univariate Gaussian change-point model for which delicate controls of the CUSUM process exist, it is challenging to provide theoretical guidance towards the best choice of the grid.

### 7.4. Optimality of the generic algorithm in a broader context

Algorithm 1 aggregates homogeneity tests and provides theoretical guarantees on the event $A(T, K^*, (\bar{\tau}_k, \bar{r}_k)_{k \in K^*})$ – i.e. the event where the outcomes of the tests are consistent – as stated in Theorem 1. In the possibly sparse high-dimensional mean change-point model, we introduced a suitable multiple testing procedure which, when combined with Algorithm 1, leads to a minimax optimal change-point detection procedure.

We described in Section 2 how to adapt this approach to other change-point problems and this was already illustrated in Section 6 with covariance and nonparametric problems. One may then wonder whether this roadmap still leads to minimax optimal procedures for general problems. Consider the general setting from Section 1 where we are interested in detecting change-points in $(\Gamma(\mathbb{P}_t))_{t \in [n]}$. Upon endowing the space $\mathcal{V}$ with some distance $d$, we define, for any $k$,

$$ \bar{\Delta}_k = d(\Gamma(\mathbb{P}_{\tau_k}), \Gamma(\mathbb{P}_{\tau_{k-1}})), $$

which corresponds to the change-point height. Then, one may wonder how large $\bar{\Delta}_k$ has to be – as a function of $r_k$ – so that a change-point detection procedure achieving the no-spurious property (NoSp) with high probability is able to detect $\tau_k$. In this discussion, we restrict our attention to independent observations, that is the random variables $y_t$ are assumed to be independent and we consider the dyadic grid $\mathcal{G}_D$.

Fix $\delta \in (0, 1)$. At each scale $r \in \{1, 2, \dots, 2^{\lceil \log_2(n) \rceil - 1}\}$ and for each $l \in \mathcal{D}_r$, with $\mathcal{D}_r$ defined in (5), we consider the testing problem $H_{0,l,r}: \{\mathbb{P}: \Gamma(\mathbb{P}_{l-r}) = \dots = \Gamma(\mathbb{P}_{l+r-1})\}$ versus

$$ H_{\rho,l,r}: \left\{ \begin{array}{ll} \Gamma(\mathbb{P}_{l-r}) = \dots = \Gamma(\mathbb{P}_{l-m-1}) & \\ \Gamma(\mathbb{P}_{l-m}) = \dots = \Gamma(\mathbb{P}_{l+r-1}) & \text{for some integer } m \in [-r/2, r/2] \\ d(\Gamma(\mathbb{P}_{l-m-1}), \Gamma(\mathbb{P}_{l-m}) \ge \rho) & \end{array} \right\} $$

This amounts to testing whether there is a single change-point near $l$ of height at least $\rho$ in the segment $(l-r, l+r)$. Given $\delta \in (0, 1)$ and a test $T$ we define the $\delta$-separation distance of $T$ by

$$ \rho_{l,r}^*(T, \delta) = \inf \left\{ \rho: \sup_{\mathbb{P} \in H_{0,l,r}} \mathbb{P}(T=1) \vee \sup_{\mathbb{P} \in H_{\rho,l,r}} \mathbb{P}(T=0) \le \delta \right\}. $$

This corresponds to the minimal change-point height that is detected by the test $T$. Then, the minimax separation distance $\rho_{l,r}^*(\delta)$ is simply $\inf_T \rho_{l,r}(T, \delta)$, i.e. the
The next proposition shows that for each step $r \in \mathcal{R}$, the subset of detection corresponding to non significant change-point is disjoint from $\bigcup_{r' \in \mathcal{R}} S_{r'}^*$.

**Proposition 10.** For all $r \in \mathcal{R}$, we have

$$ \bigcup_{l \in \mathcal{T}_r \setminus \mathcal{T}_{r'}^*} [l-r+1, l+r-1] \cap \left( \bigcup_{r' \in \mathcal{R}} S_{r'}^* \right) = \emptyset . $$

Recall that $(C_k)_{k=1,...,\hat{K}}$ are defined as the connected component of $\bigcup_{r \in \mathcal{R}} S_r$. To ease the notation, re-index $(C_k)$ so that $\tau_k$ is the closest true change-point to $\hat{\tau}_k = \frac{\min C_k + \max C_k}{2}$. Since there is no false positive, $\tau_k \in C_k$.

By Proposition 10, the two closed subset $\bigcup_{r \in \mathcal{R}} \bigcup_{l \in \mathcal{T}_r \setminus \mathcal{T}_{r'}^*} [l-r+1, l+r-1]$ and $\bigcup_{r \in \mathcal{R}} S_r^*$ are disjoint. For all $k \in \mathcal{K}^*$, it holds by Proposition 9 that $\tau_k \in \bigcup_{r \in \mathcal{R}} S_r^*$, so that $C_k$ is a connected component of $\bigcup_{r \in \mathcal{R}} S_r^*$ containing the significant change-point $\tau_k$. In particular, $\hat{K} \ge |\mathcal{K}^*|$. We have

* By Proposition 9, $C_k \subset [\tau_k - 2(\bar{r}_k - 1), \tau_k + 2(\bar{r}_k - 1)]$ for every $k \in \mathcal{K}^*$. Thus

$$ |\hat{\tau}_k - \tau_k| \le (\bar{r}_k - 1) < \frac{r_k}{4}. $$

* For all $k \in [K] \setminus \mathcal{K}^*$, either $\tau_k$ does not belong to $\bigcup_{r \in \mathcal{R}} S_r$ and it is simply not detected, or it is the closest true change-point to $\hat{\tau}_k = \frac{\min C_k + \max C_k}{2}$ so that

$$ \hat{\tau}_k \in \left[ \tau_k - \frac{\tau_k + \tau_{k-1}}{2}, \tau_k + \frac{\tau_k + \tau_{k+1}}{2} \right] . $$

In particular,

$$ \{\hat{\tau}_{k'}, k' \le \hat{K}\} \subset \left[ \tau_1 - \frac{\tau_1 - \tau_0}{2}, \tau_K + \frac{\tau_{K+1} - \tau_K}{2} \right] . $$

* Finally, if there exists two estimated change-points $\hat{\tau}_{k_1}$, $\hat{\tau}_{k_2}$ in $[\tau_k - \frac{\tau_k + \tau_{k-1}}{2}, \tau_k + \frac{\tau_k + \tau_{k+1}}{2}]$, then either $C_{k_1}$ or $C_{k_2}$ does not contain $\tau_k$. Then $\Theta$ is constant on $C_{k_1}$ or on $C_{k_2}$ and we obtain a contradiction since there is no false positive.

This concludes the proof of Theorem 1.

*Proof of Proposition 9.* To prove the proposition, we do an induction on $r \in \mathcal{R} \cup \{0\}$. The case $r = 0$ is trivial since by definition, $S_0 = \emptyset$. Let $r \in \mathcal{R}$ and assume that the double inclusion Proposition 9 holds for all $r' < r, r' \in \mathcal{R} \cup \{0\}$.

**First inclusion:** Let $k \in \mathcal{K}^*$ be such that $\bar{r}_k = r$ and assume that the corresponding significant change-point $\tau_k$ has not been detected before step $r$, that is $\tau_k \notin \bigcup_{r' < r} S_{r'}^*$. Since $k \in \mathcal{K}^*$, this implies in particular that $\tau_k \notin \bigcup_{r' < r} S_{r'}$. Let us show that $\tau_k \in S_r$. To this end we prove that

$$ [\bar{\tau}_k - r + 1, \bar{\tau}_k + r - 1] \cap \bigcup_{r' < r, r' \in \mathcal{R}} S_{r'}^* = \emptyset \quad (29) $$

and

$$ T_{\bar{\tau}_k, r} = 1, \quad (30) $$

which will be enough since $|\bar{\tau}_k - \tau_k| \le \bar{r}_k - 1 = r - 1$.
infimum over all tests $T$ of the separation distance. By translation invariance of
the testing problem, note that $\rho_{l,r}^*(\delta)$ does not depend on $l$ and is henceforth
denoted $\rho_r^*(\delta)$.

For any $(l, r)$, take any test $T_{l,r}$ (nearly)<fnref n="3" /> achieving the minimax separation
distance $\rho_r^*(\delta|\mathcal{D}_r|^{-1}\beta_r)$ with $\beta_r = 6 \log_2^{-2}(n/r))\pi^{-2}$. Then, it follows from a
simple union bound on the dyadic grid that, with probability higher than $1 - \delta$,
the collection of tests $T_{l,r}$, where $(l, r)$ belongs to the dyadic grid, does not detect
any false positive and detects any change-point $\tau_k$ such that $\bar{\Delta}_k$ is higher than
$\rho_{\tilde{r}_k}^*(\delta|\mathcal{D}_{\tilde{r}_k}|^{-1}\beta_{\tilde{r}_k})$, where $\tilde{r}_k$ is the largest scale in $\mathcal{R}$ such that $4(\tilde{r}_k - 1) \le r_k$. As
a consequence of Theorem 1, the corresponding detection procedure achieves,
with probability higher than $1 - \delta$, the property (**NoSp**) and **detects** any
change-point satisfying the energy condition $\bar{\Delta}_k \ge \rho_{\tilde{r}_k}^*(r\delta\beta_r/2n)$.

Conversely, we believe that this energy condition is almost tight. Indeed, fix
any even range $r \ge 2$. To simplify the discussion suppose that $n/(2r)$ is an
integer. We consider a specific instance of the problem where the statistician
knows that there are $n/(2r) - 1$ evenly-spaced change-points respectively at
$2r + 1, 4r + 1, \dots, n - 2r + 1$ that allow to reduce the change-point detection
problem to $n/(2r)$ change-point detection problem in intervals $(l-r, l+r]$ for $l =
r+1, 3r+1, 5r+1, \dots$. Furthermore, it is known that, in each such segment, there
exists at most one change-point that is situated in $[l - 0.5r, l + 0.5r]$, and if the
change-point is present then its height is at least $\rho = \rho_r^*(\delta) - \zeta$ for $\zeta$ arbitrarily
small. Since all $n/(2r) - 1$ evenly-spaced change-points $2r+1, 4r+1, \dots, n-2r+1$
are known to the statistician, detecting all remaining change-points is equivalent
to building an $n/(2r)$ multiple test of the hypotheses $H_{0,l,r}$ versus $H_{\rho,l,r}$ for
$l = r+1, 3r+1, 5r+1, \dots$. If a change-point procedure achieves (**NoSp**) and
**detects** all change-points with radius at least $r/2$ and height at least $\rho$ with
probability at least $1 - \delta$, then one is able, with probability uniformly higher
than $1 - \delta$, to simultaneously perform without error $n/(2r)$ independent tests
$H_{0,l,r}$ versus $H_{\rho,l,r}$. Since any single test must endure an error with probability
at least $\delta$ in the worst case, no collection of independents tests is able to endure
less than $1 - (1 - \delta)^{n/(2r)}$. When $n/r$ is large and $\delta < 2r/n$, the latter is of the
order of $\delta 2r/n$. Based on this, we conjecture that no change-point procedure is
able to achieve, with probability higher than $1 - \delta$ the property (**NoSp**), and
also to **detect** all change-points with radius at least $r/2$ and height at least
$\rho_r^*(2r\delta/n) - \zeta$ for $\zeta > 0$ arbitrarily small.

Comparing the performances of our procedure with the negative arguments
that we just outlined, we see that aggregating optimal tests on a dyadic grid
allows to detect change-points with (almost) uniform height higher

$\rho_{\tilde{r}_k}^*(r_k \delta \beta_{r_k} / (2n))$ whereas, as explained above, we conjecture that a change-
point $\tau_k$ can be detected only if $\bar{\Delta}_k \ge \rho_{r_k}^*(2r_k \delta / n)$. Since $\tilde{r}_k \ge (r_k/8) \vee 1$- as we
considered the dyadic grid when constructing $\tilde{r}_k$ – the difference between these
two bounds is mostly due to the term $\beta_r$ which is of the order of $\log^2(n/r)$.

<footnote n="3">³Since the minimax separation distance is defined as an infimum, it is not necessarily achieved by a test. Still, we can build a test whose separation distance is arbitrarily close to the optimal one. We neglect the additive error term for the purpose of the discussion.</footnote>
* **Proof of (29):** Assume for the sake of contradiction that there exists an integer $z$ which belongs to $[\bar{\tau}_k - r + 1, \bar{\tau}_k + r - 1] \cap \bigcup_{\substack{r' < r \\ r' \in \mathcal{R}}} S_{r'}$. There exists $r' < r$ such that $z \in S_{r'}$ and $l(z) \in \mathcal{T}_{r'}$ such that $z \in [l(z) - r' + 1, l(z) + r' - 1]$. Since $\tau_k \notin \bigcup_{r' < r} S_{r'}$, we have $\tau_k \notin [l(z) - r' + 1, l(z) + r' - 1]$. Moreover,

$$ 
\begin{aligned}
|l(z) - \tau_k| &\le |l(z) - z| + |z - \bar{\tau}_k| + |\bar{\tau}_k - \tau_k| \\
&\le (r' - 1) + (r - 1) + |\bar{\tau}_k - \tau_k| \\
&< r_k - r',
\end{aligned}
$$

Where the last inequality comes from the hypothesis $3(\bar{\tau}_k - 1) + |\bar{\tau}_k - \tau_k| \le r_k$. Consequently,

$$ [l(z) - r', l(z) + r'] \subset [\tau_k - r_k, \tau_k + r_k) \setminus \{\tau_k\}, $$

so that $\theta$ is constant on $[l(z) - r', l(z) + r'] \cap \mathbb{N}$. Thus, $(l(z), r') \in \mathcal{H}_0$ and $l(z) \notin \mathcal{T}_{r'}$ since there is no false positive. This gives a contradiction and concludes the proof of (29).

* **Proof of (30):** This is simply a consequence of the fact that significant change-point are detected on the grid (See Item 2 in the definition of $\mathcal{A}$).

We have just shown that $\tau_k \in S_r$ and hence $\tau_k \in S_r^*$ so that the first inclusion holds at step $r$.

**Second inclusion:** Let $x$ be an element of $S_r^*$. There exists $l(x) \in \mathcal{T}_r^*$ such that $x \in [l(x) - r + 1, l(x) + r - 1]$. By definition of $\mathcal{T}_r^*$, there exists a significant change-point $\tau_k$ (i.e. such that $k \in \mathcal{K}^*$) belonging to $[l(x) - r + 1, l(x) + r - 1]$.

We necessarily have $\bar{\tau}_k \ge r$. Indeed, if $\bar{\tau}_k < r$, then by the induction hypothesis, $\tau_k \in S_{r'}^*$ for some $r' < r$, which contradicts the fact that $S_{r'}^*$ is disjoint from $[l(x) - r + 1, l(x) + r - 1] \subset S_r^*$. Consequently,

$$ 
\begin{aligned}
|l(x) - \tau_k| + r - 1 &\le 2r - 2 \\
&\le 2(\bar{\tau}_k - 1)
\end{aligned}
$$

Thus

$$ x \in [l(x) - r + 1, l(x) + r - 1] \subset [\tau_k - 2(\bar{\tau}_k - 1), \tau_k + 2(\bar{\tau}_k - 1)] . $$

We have just shown that $S_r^* \subset \bigcup_{k \in \mathcal{K}^*} [\tau_k - 2(\bar{\tau}_k - 1), \tau_k + 2(\bar{\tau}_k - 1)]$.

Therefore, the proposition is verified at step $r$ and the induction is proved. $\square$

**Proof of Proposition 10.** Let $k \in \mathcal{K}^*$ and $C_k$ be the detected connected component containing the significant change-point $\tau_k$

$$ C_k = \bigcup_{r' \in \mathcal{R}} S_{r'}^* \cap [\tau_k - 2(\bar{\tau}_k - 1), \tau_k + 2(\bar{\tau}_k - 1)] . $$

We know from Proposition 9 that $C_k$ is a connected component of $\bigcup_{r' \in \mathcal{R}} S_{r'}^*$ and we want to prove now that $C_k$ does not overlap with $\bigcup_{l \in \mathcal{T}_r \setminus \mathcal{T}_r^*} [l - r + 1, l + r - 1]$ for some $r \in \mathcal{R}$. Let $r_0$ be such that $C_k$ is the connected component of $S_{r_0}$,

$$ C_k \subset S_{r_0}^* . $$
Whereas it is possible to detect change-points at a given scale with a test of type I error probability $2r\delta/n$, our multi-scale procedure relies on a collection of single tests with type I error probability of the order of $r\delta/n/\log^2(n/r)$. This mild mismatch – that we introduce to deal with the multiplicity of scales – of order $\log^2(n/r)$ is harmless for the Gaussian mean-detection problem. Indeed, one may deduce from our analysis in Section 3 that $\rho_{r_k}^*(2r_k\delta/n)$ is of the same order as $\rho_{\tilde{r}_k}^*(\delta|\mathcal{D}_{\tilde{r}_k}|^{-1}\beta_{\tilde{r}_k})$.

In conclusion, one can build through Algorithm 1 an almost optimal change-point procedure in any model provided that we are given optimal homogeneity tests of the form $H_{0,l,r}$ versus $H_{\rho,l,r}$. This provides a universal reduction of the problem of change-point detection to the problem of homogeneity testing.

## 8. Numerical experiments

In this section, we illustrate the behavior of our procedure to detect change-points in a sparse high-dimensional setting (2).

**Performance Measure.** To assess the quality of change-point estimator $\hat{\tau}$, we first measure whether the estimated number of change-points $\hat{K} = |\hat{\tau}|$ is equal to the true number $K$ of change-points. We also define the **SAND** loss as the proportion of **Spurious** estimated change-points **And** true change-points that are **Not Detected**:

$$ \text{SAND}((\tau_k), (\hat{\tau}_{k'})) = \frac{1}{K} \sum_{k=1}^{K} \left| \left| \left( (\tau_k + \tau_{k-1})/2, (\tau_k + \tau_{k+1})/2 \right) \cap \{\hat{\tau}_k, k \in [\hat{K}]\} \right| - 1 \right| $$

**Change-point Detection Methods.** In the experiments, we implemented the bottom-up aggregation procedure Algorithm 1 with partial norm tests $T^{(p)}$ and dense test $T^{(d)}$ corresponding to Section 4 on a semi-complete grid $\mathcal{G}_F = \{(l,r) : l \in \{r+1, \dots, n-r+1, r \in \mathcal{R}\} - \text{we take scales } r \text{ in the dyadic set for computational purposes. On a location } l \text{ and a scale } r, \text{ each test statistic can be seen as a partial norm test relying on the statistic } \Psi_{l,r,s}^{(p)} \text{ defined in Section 4.2 and a threshold Threshold}(r, s) \text{ which is either equal to } x_r^{(d)} \text{ when } s=d \text{ see Section 4.1 - or to } x_{r,s}^{(p)} \text{ when } s \in \mathcal{Z}_r := \{1, 2, 4, \dots, 2^{\lceil \log_2(s_{\max}) \rceil}\} \text{ with } s_{\max} := \frac{\sqrt{p\gamma_r}}{\log(p)-\log(\gamma_r)} \text{ - see Section 4.3 for the definition of the boundary between sparse and dense regimes } s_{\max}. \text{ We actually do not use the definition of } x_r^{(d)} \text{ and } x_{r,s}^{(p)} \text{ for our thresholds Threshold}(r, s) \text{ since they rely on constants that are not necessarily tight, but we rather calibrate them by a Monte-Carlo method using 10.000 independent samples. For each sample consisting in a time series made of } n \text{ gaussian normal centered vector in } \mathbb{R}^p, \text{ and for each } r \in \mathcal{R}, s \in \mathcal{Z}_r \cup \{p\}, \text{ we compute the maximum over all } l \text{ of the statistics } \Psi_{l,r,s}^{(p)}. \text{ Considering the list of all the 10.000 maximums and taking } \delta = 5\%, \text{ Threshold}(r, s) \text{ is then defined as the } (1 - \delta/(2|\mathcal{R}||\mathcal{Z}_r|))\text{-quantile if } s \in \mathcal{Z}_r \text{ and as the } (1 - \delta/(2|\mathcal{R}|))\text{-quantile if } s = p, \text{ so that, by a union bound, the total probability of finding a false positive}$$
Such an $r_0$ exists and is unique since the sets $(S_{r'}^*)$ are disjoint. We have from Proposition 9 that $\tau_k \in \bigcup_{r' \in \mathcal{R}, r' \le \bar{r}_k} S_{r'}^*$ so that

$$r_0 \le \bar{r}_k.$$

Let $r \in \mathcal{R}$ and $l \in \mathcal{T}_r \setminus \mathcal{T}_r^*$ and assume without loss of generality that $l+r-1 < \tau_k$. Since there is no false positive, $(l, r) \notin \mathcal{H}_0$ and there exists at least one true change-point in the interval of detection $[l-r+1, l+r-1]$. Denote $\tau_a, \dots, \tau_b$ with $a \le b$ the true change-points belonging to $[l-r+1, l+r-1]$. By definition of $\mathcal{T}_r \setminus \mathcal{T}_r^*$, $\tau_a, \dots, \tau_b$ are not significant change-points, i.e. $a, a+1, \dots, b \notin \mathcal{K}^*$. We consider the two cases $r > \bar{r}_k$ and $r \le \bar{r}_k$

* $r > \bar{r}_k$: In that case, since the sets $(S_{r'})$ are disjoint and $C_k \subset S_{r_0}^*$, we have $C_k \cap [l-r+1, l+r-1] = \emptyset$.

* $r \le \bar{r}_k$: In that case, we have

$$l+r-1 \le \tau_b + 2(r-1) \le \tau_b + 2(\bar{r}_k - 1) < \tau_k - 2(\bar{r}_k - 1),$$

where we used the fact that $4(\bar{r}_k - 1) < r_k \le \tau_k - \tau_b$. Since by Proposition 9 we have $C_k \subset [l-r+1, l+r-1]$, we also have in that case $C_k \cap [l-r+1, l+r-1] = \emptyset$.

This concludes the proof of the proposition. □

## B.2 Proofs for Gaussian multivariate change-point detection

From now on, we use the following notation for all $(l, r) \in J_n$.

* For any $(v_1, \dots, v_n)$ with $v_t \in \mathbb{R}^p$, the left mean and right mean of $v$ on $[l-r, l+r)$ are denoted by

$$\bar{v}_{l,+r} = \frac{1}{r} \sum_{t=l}^{l+r-1} v_t \quad \bar{v}_{l,-r} = \frac{1}{r} \sum_{t=l-r}^{l-1} v_t.$$

* The population term of the CUSUM statistic $C_{l,r}$ is written

$$U_{l,r} = \sqrt{\frac{r}{2}} (\bar{\theta}_{l,+r} - \bar{\theta}_{l,-r}).$$

* With these notation, we write $v_{l,+r,i}, v_{l,-r,i}, U_{l,r,i}$ for the $i^{th}$ coordinate of the vector $v_{l,+r}, v_{l,-r}, U_{l,r}$.

* We define, for $1 \le s \le p$, the order statistics $U_{l,r,s}$ by $|U_{l,r,(1)}| \ge |U_{l,r,(2)}| \ge \dots |U_{l,r,(p)}|$.

### B.2.1 Proof of Proposition 1

**Step 0: Consequence of Equation (10) on the grid.** Let $k \in [K]$ and assume that $\tau_k$ is a $\kappa_d$-dense high-energy change-point (see Equation (10)). We have that

$$\begin{aligned} \| U_{\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)}} \|^2 &\ge \frac{9}{16} \| U_{\tau_k, \bar{r}_k^{(d)}} \|^2 \\ &\ge \frac{9}{16 \times 12} \kappa_d \left( \sqrt{p \log \left( \frac{n}{\bar{r}_k^{(d)}}, \delta \right)} + \log \left( \frac{n}{\bar{r}_k^{(d)}, \delta} \right) \right), \end{aligned} \quad (31)$$

since by definition $\|\tau_k - \bar{\tau}_k^{(d)}\| \le \bar{r}_k^{(d)}/4$, so that $\|\bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}\|^2 \ge \frac{9}{16} \|\bar{\theta}_{\tau_k, +\bar{r}_k^{(d)} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}}\|^2$.
is less than $\delta$. Note that this calibration step only depends on $n$, $p$, and $\sigma$ and
only needs to be performed once and for all.

We compare our procedure with the inspect method of [46] which is available
as an R package. The tuning parameters of inspect are computed with the
automatic method defined in the same R package.

In all the following experiments, we fix the dimension $p = 100$ and the sample
size $n = 200$. We generate a piecewise constant signal $(\eta_t)_{t=1}^n$ in $\mathbb{R}^p$ with possible
change-points $(\tau_1, \dots, \tau_K)$ using one of the three following settings. We then
add a scaling factor $\alpha > 0$ and apply our procedure to the data $y_t = \alpha\eta_t + \varepsilon_t$,
which amounts to setting $\theta_t = \alpha\eta_t$ in model (2). We fix the variance of all the
coordinates of $\varepsilon_t$ to be equal to one. Increasing $\alpha$ on a grid with step 0.1 allows
us to experimentally identify a transition between the regime where we do not
detect precisely the change-points – in which case the two losses tend to be close
to one – and the regime where we do detect the change-points – in which cases
the losses are smaller. We consider three simulation settings:

1. **Segment.** We generate a signal $\eta$ which is zero everywhere, except on $[80, 100]$ where we set it equal to a random vector $\Delta$ with $\|\Delta\| = 1$ and $\|\Delta\|_0 = s$, for $s = 1, 20, 100$. In each one of these cases, we choose the location of the $s$ non null coordinates of $\Delta$ uniformly at random and their value uniformly at random in the set $\{-1/\sqrt{s}, 1/\sqrt{s}\}$. Each time, $\eta$ has 2 true change-points, and we generate the noise $(\epsilon_t)$ as independent centered and normalized gaussian vectors.

2. **Multiple Change points.** We generate 10 uniform random locations $\tau_1 < \tau_2 < \dots < \tau_{10}$ on $[1, 200]$. For each location $\tau_i$, we generate a uniform random integer $s_i \in [1, 100]$ and a vector $\Delta_i$ as in the segment setting with $\|\Delta_i\| = 1$ and $\|\Delta_i\|_0 = s_i$. We generate a uniform random real number $N_i \in [1, 5]$ and define the time series $\eta_i$ by $(\eta_i)_t = N_i \Delta_i \mathbf{1}_{t \ge \tau_i}$. Finally, the signal $\eta = \sum_{i=1}^{10} \eta_i$ has exactly 10 change-points with random locations. As previously, the noise components $(\epsilon_t)$ follow independent centered and standard gaussian vectors.

3. **Time-dependencies.** We use the same signal as in the segment setting with $s = 20$ but we move away from our assumptions by considering time dependencies. More precisely, the $(\epsilon_t)$'s are now defined according to an AR process such that $\epsilon_{t+1} = \rho\epsilon_t + \sqrt{1-\rho^2}\epsilon'_{t+1}$ for $t \ge 0$ where $(\epsilon'_t)$ are independent centered and normalized gaussian vectors, $\rho = 0.05$ for the simulation and by convention $\epsilon_0 \sim N(0, I_p)$.

**Risk estimation with Monte-Carlo** In each setting, we generate 500 inde-
pendent samples and compute the two losses SAND((τ_k), (τ̂_k')) and 1{K̂ ≠ K}.
We estimate the risks E[SAND((τ_k), (τ̂_k))] and P(K ≠ K̂) by averaging
the loss over the 500 trials. We also compute 95% confidence intervals.

**Results** In the segment setting – see Figure 4, 5, 6, the risks tend to decrease as $\alpha$ increases since the higher $\alpha$, the higher the energy of the generated change-points are. As $s$ increases, we can see that both methods need a higher scaling
**Step 1: Introduction of useful high probability events.** Remark that

$$ \frac{r}{2} \left[ \|\bar{y}_{l,+r} - \bar{y}_{l,-r}\|^2 - \|\bar{\theta}_{l,-r} - \bar{\theta}_{l,+r}\|^2 \right] - \sigma^2 p = r \langle \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle + \frac{r}{2} \|\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}\|^2 - \sigma^2 p . $$

The first term, written as

$$ r \langle \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle , $$

is a crossed term between the noise and the mean vector $\theta$. Lemma 1 states that near the change-points and on the grid defined by the sets $\mathcal{R}, \mathcal{D}_r$, it is jointly controlled with high probability.

**Lemma 1.** Let $1 \ge \delta > 0$. The event

$$ \begin{aligned} \xi_1^{(d)} &= \bigcap_{k \in [K]} \left\{ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}}, +\bar{r}_k^{(d)} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}}, -\bar{r}_k^{(d)}, \bar{\theta}_{\bar{\tau}_k^{(d)}}, +\bar{r}_k^{(d)} - \bar{\theta}_{\bar{\tau}_k^{(d)}}, -\bar{r}_k^{(d)} \rangle \right| \right. \\ & \le \frac{1}{8} \bar{r}_k^{(d)} \left. \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2 + 16\sigma^2 \log \left( 2 \frac{n}{\bar{r}_k^{(d)} \delta} \right) \right\} . \end{aligned} $$

holds with probability larger than $1 - \delta$.

The second term, written as

$$ \frac{r}{2} \|\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}\|^2 - \sigma^2 p , $$

is a term of pure noise. Lemma 2 states that it is controlled jointly with high probability on the grid defined by the sets $\mathcal{R}, \mathcal{D}_r$.

**Lemma 2.** Let $1 \ge \delta > 0$. The event

$$ \xi_2^{(d)} = \bigcap_{r \in \mathcal{R}} \bigcap_{l \in \mathcal{D}_r} \left\{ \left| \frac{r}{2} \|\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}\|^2 - \sigma^2 p \right| \le 4\sigma^2 \left[ \sqrt{p \log\left(2 \frac{n}{r\delta}\right)} + \log\left(2 \frac{n}{r\delta}\right) \right] \right\} , $$

holds with probability larger than $1 - \delta$.

Set now

$$ \xi^{(d)} := \xi^{(d)} = \xi_{1}^{(d)} \cap \xi_{2}^{(d)} . $$

Note that

$$ \mathbb{P}(\xi^{(d)}) \ge 1 - 2\delta . $$

**Step 2: Study in the ‘no change-point’ situation.** Consider $r \in \mathcal{R}, l \in \mathcal{D}_r$ such that $\{\tau_k, k \in [K]\} \cap [l - r, l + r) = \emptyset$. Note that since $\{\tau_k, k \in [K]\} \cap [l - r, l + r) = \emptyset$, we have $\bar{\theta}_{l,-r} = \bar{\theta}_{l,+r}$ so that

$$ \frac{r}{2} \|\bar{\theta}_{l,-r} - \bar{\theta}_{l,+r}\|^2 = 0 , $$

and

$$ r \langle \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle = 0. $$
<figure><img src="image_5.png" /><figcaption>FIG 4. Estimation of $E[\mathbf{SAND}((\tau_k), (\hat{\tau}_{k'}))]$ and $\mathbb{P}(\hat{K} \neq K)$ in the segment setting with $s = 1$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIG 5. Estimation of $E[\mathbf{SAND}((\tau_k), (\hat{\tau}_{k'}))]$ and $\mathbb{P}(\hat{K} \neq K)$ in the segment setting with $s = 20$.</figcaption></figure>

factor to achieve the same risk, which translates the fact that the higher $s$, the more energy is needed to detect a change-point with vector $\Delta$ of sparsity $s$. In the segment settings, our bottom-up procedure tends to achieve significantly smaller loss than the inspect method on average. It is not the case in the multiple change-points setting – see Figure 7 – where the inspect method tends to perform slightly better. In the setting with time-dependencies – see Figure 8 – the risks are worse than the corresponding setting without time-dependencies – see Figure 5 – mainly because adding time-dependencies tends to create more spurious change-points (i.e. false positives).

**Computation time** Our code is implemented with python 3.9 and it mainly uses the convolution function conv1d from pytorch 1.12.1 to compute the Cusum statistics. Simulations are run on CPU (Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz) with 32Go of memory. Running our method on pure noise – i.e. $\theta_t = 0$ for all $t$ – takes $101 \pm 2$ ms while the inspect method takes only $18 \pm 2$ ms to run on average, but optimizing our code is out of the scope of this paper. All the experiments are described in the repository https://github.com/epilliat/multicpetec.
Moreover we have on $\xi^{(d)}$ that - see Lemma 2

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 4\sigma^2 \left[ \sqrt{p \log \left( 2 \frac{n}{r\delta} \right)} + \log \left( 2 \frac{n}{r\delta} \right) \right] = \sigma^2 x_r^{(d)}. $$

And so

$$ \Psi_{l,r}^{(d)} \le x_r^{(d)}, $$

so that

$$ T_{l,r}^{(d)} = 0, $$

on $\xi^{(d)}$. This concludes the proof of the first part of the proposition.

**Step 3: Study in the ‘change-point’ situation.** Consider $k \in [K]$ $\tau_k$ is a $\kappa_d$-dense high-energy change-point - that is Equation(10) holds. We have from (31) that for $\kappa_d$ large enough,

$$ \begin{aligned} \frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} \right\|^2 &\ge \frac{9}{16 \times 12} \kappa_d \sigma^2 \left( \sqrt{p \log \left( \frac{n}{\bar{r}_k^{(d)}, \delta} \right)} + \log \left( \frac{n}{\bar{r}_k^{(d)}, \delta} \right) \right) \\ &> 4\sigma^2 x_{\bar{r}_k^{(d)}}^{(d)}. \end{aligned} $$

So on $\xi^{(d)}$ this implies that - see Lemma 1

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}}, -\bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}}, -\bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \right| \le \frac{\bar{r}_k^{(d)}}{4} \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2. $$

Moreover we have on $\xi^{(d)}$ that - see Lemma 2

$$ \left| \frac{\bar{r}^{(d)}}{2} \left\| \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2 - \sigma^2 p \right| \le 4\sigma^2 \left[ \sqrt{p \log \left( 2 \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right)} + \log \left( 2 \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right) \right] = \sigma^2 x_{\bar{r}_k^{(d)}}^{(d)}. $$

And so on $\xi^{(d)}$, combining the three previous displayed equations implies

$$ \Psi_{\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)}}^{(d)} \ge \frac{\frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2}{2\sigma^2} - x_{\bar{r}_k^{(d)}}^{(d)} > (2-1)x_{\bar{r}_k^{(d)}}^{(d)} = x_{\bar{r}_k^{(d)}}^{(d)}, $$

so that

$$ T_{\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)}}^{(d)} = 1. $$

This concludes the proof of the second part of the proposition.

*Proof of Lemma 1.* Let $k \in [K]$. Since the vectors $\epsilon_t$ are i.i.d. and distributed as $N(0, \sigma^2 I_p)$, it holds that

$$ \bar{r}_k^{(d)} \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}}, -\bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}}, -\bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \sim N \left( 0, 2\bar{r}_k^{(d)} \sigma^2 \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2 \right). $$
<figure><img src="image_7.png" /><figcaption>FIG 6. Estimation of $E[SAND((τ_k), (τ_{k'})]]$ and $P(\hat{K} ≠ K)$ in the segment setting with $s = 100$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>FIG 7. Estimation of $E[SAND((τ_k), (τ_{k'})]]$ and $P(\hat{K} ≠ K)$ in a multiple change-point setting with $K = 10$ where change-points have random norms in $[1, 5]$ and random sparsities in $[1, p]$.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>FIG 8. Estimation of $E[SAND((τ_k), (τ_{k'})]]$ and $P(\hat{K} ≠ K)$ in the segment setting with $s = 20$ but with time-dependent noise that have an auto-correlation of $ρ = 5\%$.</figcaption></figure>
And so for $\delta_k > 0$, it holds with probability larger than $1 - \delta_k$ it holds that

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \right| \le 2\sigma \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\| \sqrt{\bar{r}_k^{(d)} \log(2\delta_k^{-1})} . $$

Let us set $\delta_k = \frac{(\bar{r}_k^{(d)})^2 \delta}{2n^2}$. Note that

$$ \sum_{k \in [K]} \delta_k = \sum_{r \in \mathbb{R}} \sum_{k \in [K]: \bar{r}_k^{(d)}=r} \frac{(\bar{r}_k^{(d)})^2 \delta}{2n^2} \le \sum_{r \in \mathbb{R}} \sum_{l \in D_r} \frac{r^2 \delta}{2n^2} \le \sum_{r \in \mathbb{R}} \frac{r \delta}{2n} \le \delta, $$

since $r_k \ge \bar{r}_k^{(d)}$ and $|D_r| \le 2n/r$, and also by definition of $\mathcal{R}$ which implies $\sum_{r \in \mathcal{R}} \frac{r}{n} \le 1$. And so if $\delta \le 1$, then with probability larger than $1 - \delta$, for any $k \in [K]$, we have

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \right| \le 2\sigma \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\| \sqrt{2\bar{r}_k^{(d)} \log \left( 2 \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right)}. $$

This implies in particular that with probability larger than $1 - \delta$, for any $k \in [K]$, we have

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \right| \le \frac{\bar{r}_k^{(d)}}{2} \frac{\left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2}{4} + 16\sigma^2 \log \left( 2 \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right). $$

□

Proof of Lemma 2. Let $r \in \mathcal{R}$ and $l \in D_r$. Since the vectors $\epsilon_t$ are i.i.d. and distributed as $\mathcal{N}(0, \sigma^2 \mathbf{I}_p)$, it holds that

$$ \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 \sim \sigma^2 \chi_p^2, $$

which implies by properties of the $\chi_p^2$ distribution - see e.g. Lemma 1 of [26] - that for any $\delta_r > 0$ we have with probability larger than $1 - \delta_r$

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 2\sigma^2 \sqrt{p \log(2/\delta_r)} + 2\sigma^2 \log(2/\delta_r) . $$

If we set, for $\delta > 0$, $\delta_r = \frac{r^2 \delta}{2n^2}$, we have that with probability larger than $1 - \frac{r\delta}{n}$, that $\forall l \in D_r$

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 2\sigma^2 \sqrt{p \log(2/\delta_r)} + 2\sigma^2 \log(2/\delta_r) , $$

since $|D_r| \le 2n/r$. And so with probability larger than $1 - \delta$, for all $r \in \mathcal{R}$ and $l \in D_r$

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 2\sigma^2 \sqrt{p \log(2/\delta_r)} + 2\sigma^2 \log(2/\delta_r) , $$

since $\sum_{r \in \mathcal{R}} \frac{r}{n} \le 1$. And so finally for $\delta \le 1$ and with probability larger than $1 - \delta$, for all $r \in \mathcal{R}$ and $l \in D_r$

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 4\sigma^2 \left[ \sqrt{p \log\left(2 \frac{n}{r} \delta^{-1}\right)} + \log\left(2 \frac{n}{r} \delta^{-1}\right) \right] . $$

This concludes the proof.

□
## Appendix A: An alternative algorithm

In Algorithm 2 below, we also introduce a variant of the procedure, where instead of merging relevant interesting intervals at the same scale, we only keep one of them. More precisely, we choose the convention of discarding the interval $[l - r + 1, l + r - 1]$ if there exists $l' < l$ such that $T_{l',r} = 1$ and $[l - r + 1, l + r - 1] \cap [l' - r + 1, l' + r - 1] \neq \emptyset$. Alternatively, we could have chosen to discard one of the intervals at random.

**Data:** $y_t, t = 1...n$ and local test statistic $(T_{l,r})_{(l,r) \in \mathcal{G}}$

**Result:** $(\hat{\tau}_k)_{k \le \hat{K}}$

$$S = \emptyset \quad T = \emptyset;$$

for $r \in \mathcal{R}$ do

for $l \in \mathcal{D}_r$ s.t. $T_{l,r} = 1$ do
    if $[l - r + 1, l + r - 1] \cap S = \emptyset$ then
        $S \leftarrow S \cup [l - r + 1, l + r - 1]$;
        $T \leftarrow T \cup \{l\}$;
    end
end
end
return $T$

**Algorithm 2:** Variant bottom-up aggregation procedure of multiscale tests

## Appendix B: Proofs

### B.1. Proof of Theorem 1

Let $\Theta \in \mathbb{R}^{n \times p}$, $T$ be a local test statistic, $\mathcal{K}^*$ be a set of indices of significant change-points and $(\bar{\tau}_k, \bar{r}_k)_{k \in \mathcal{K}^*}$ be elements of the grid $\mathcal{G}$ that satisfy (6). We assume that $\mathcal{A}(\Theta, T, \mathcal{K}^*, (\bar{\tau}_k, \bar{r}_k)_{k \in \mathcal{K}^*})$ holds, that is:

1. (No False Positive) $T_{l,r} = 0$ for all $(l,r) \in \mathcal{H}_0 \cap \mathcal{G}$, where $\mathcal{H}_0$ is defined by (7)

2. (Significant change-point detection) for every $k \in \mathcal{K}^*$, we have $T_{\bar{\tau}_k, \bar{r}_k} = 1$.

For every $r \in \mathcal{R}$ define

$$\mathcal{T}_r^* = \{l \in \mathcal{T}_r : \exists k \in \mathcal{K}^* \text{ s.t. } \tau_k \in [l - r + 1, l + r - 1]\},$$

$$S_r^* = \bigcup_{l \in \mathcal{T}_r^*} [l - r + 1, l + r - 1].$$

In other words, for all $r \in \mathcal{R}$, $\mathcal{T}_r^*$ is the subset of $\mathcal{T}_r$ for which each interval of detection $[l - r + 1, l + r - 1]$ contains a significant change-point. The next proposition recursively analyzes the detection sets corresponding to significant change-points $(S_r^*)_{r \ge 1}$. The first inclusion means that significant change-points which can be detected with a local statistic with radius smaller than $r$ are detected before step $r$, while the second inclusion means that each connected
### B.2.2 Proof of Proposition 2

**Step 1: Analysis of the Berk-Jones statistics** We first define a threshold $x_{r,s}^{(\text{BJ})}$ for the Berk-Jones statistics for all $r, s \ge 1$

$$x_{r,s}^{(\text{BJ})} = \min \left\{ x \ge 2 : \bar{\Phi}(x) \le \frac{s^2}{28^2 p \log(2\delta_{x,r}^{-1})} \right\}, \quad (32)$$

where we recall that $\delta_{x,r}$ are the weights defined by (13):

$$\delta_{x,r} = \frac{6\delta r}{\pi^2 x^2 |\mathcal{D}_r| n}.$$

Remark that $(x_{r,s}^{(\text{BJ})})$ is nonincreasing with $s$ and define for all $r \ge 1$

$$\bar{s}_r = \min \left\{ s \in \mathcal{Z} : s \ge \frac{28}{3} \log \left( 2\delta_{x_{r,s}^{(\text{BJ})}, r}^{-1} \right) \right\}. \quad (33)$$

The second point of the following proposition ensures that if there exists $s \in \mathcal{Z}$ such that $U_{l,r,(s)} \ge t_s$ for some $s \ge \bar{s}_r$, for $(l,r) = (\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)})$, then $T_{l,r}^{(\text{BJ})} = 1$ with high probability. We recall that $|U_{l,r,(1)}| \ge \dots \ge |U_{l,r,(p)}|$ are the sorted absolute values of the coordinate of $U_{l,r}$ and that $\mathcal{H}_0$ is defined by (7).

**Proposition 11.** There exists an event $\xi^{(\text{BJ})}$ of probability larger than $1-2\delta$ such that the following holds:

* $T_{l,r}^{(\text{BJ})} = 0$ for any $(l,r) \in \mathcal{H}_0 \cap G$.

* For all $k \in [K]$, if there exists $s \in \mathcal{Z}$ such that $s \ge \bar{s}_{\bar{\tau}_k^{(s)}}$ and $U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s)} > x_{\bar{\tau}_k^{(s)}, s}^{(\text{BJ})}$, then $T_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}}^{(\text{BJ})} = 1$.

**Step 2: Analysis of the partial norm statistics** Since it may happen that $\tau_k$ is a sparse high-energy change-point but there is no $s \ge \bar{s}_{\bar{\tau}_k^{(s)}}$ such that $U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s)} \ge x_{\bar{\tau}_k^{(s)}, s}^{(\text{BJ})}$, we use the following proposition on the partial norm test statistic $T_{l,r}^{(\text{p})}$:

**Proposition 12.** There exists an event $\xi^{(\text{p})}$ of probability larger than $1-2\delta$ such that the following holds:

* $T_{l,r}^{(\text{p})} = 0$ for any $(l,r) \in \mathcal{H}_0 \cap G$.

* for any $k \in [K]$, if there exists $s \in \mathcal{Z}$ such that

$$\sum_{s'=1}^{s} |U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}^{(\text{p})}|^2 > 4x_{\bar{\tau}_k^{(s)}, s}^{(\text{p})}, \quad (34)$$

then $T_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}}^{(\text{p})} = 1$.
component of $\bigcup_{r \in \mathbb{R}} S_r^*$ is included in a close neighborhoods of some significant change-point $\tau_k, k \in \mathcal{K}^*$.

**Proposition 9.** For all $r \in \mathbb{R} \cup \{0\}$, we have the double inclusion

$$ \{\tau_k : k \in \mathcal{K}^* \text{ and } \bar{r}_k \le r\} \subset \bigcup_{r' \le r, r' \in \mathcal{R}} S_{r'}^* \subset \bigcup_{k \in \mathcal{K}^*} [\tau_k - 2(\bar{r}_k - 1), \tau_k + 2(\bar{r}_k - 1)] . \quad (28) $$

The next proposition shows that for each step $r \in \mathbb{R}$, the subset of detection corresponding to non significant change-point is disjoint from $\bigcup_{r' \in \mathcal{R}} S_{r'}^*$.

**Proposition 10.** For all $r \in \mathbb{R}$, we have

$$ \bigcup_{l \in \mathcal{T}_r \setminus \mathcal{T}_r^*} [l - r + 1, l + r - 1] \cap \left( \bigcup_{r' \in \mathcal{R}} S_{r'}^* \right) = \emptyset . $$

Recall that $(C_k)_{k=1,...,\hat{K}}$ are defined as the connected component of $\bigcup_{r \in \mathbb{R}} S_r$. To ease the notation, re-index $(C_k)$ so that $\tau_k$ is the closest true change-point to $\hat{\tau}_k = \frac{\min C_k + \max C_k}{2}$. Since there is no false positive, $\tau_k \in C_k$.

By Proposition 10, the two closed subset $\bigcup_{r \in \mathbb{R}} \bigcup_{l \in \mathcal{T}_r \setminus \mathcal{T}_r^*} [l - r + 1, l + r - 1]$ and $\bigcup_{r \in \mathbb{R}} S_r^*$ are disjoint. For all $k \in \mathcal{K}^*$, it holds by Proposition 9 that $\tau_k \in \bigcup_{r \in \mathbb{R}} S_r^*$, so that $C_k$ is a connected component of $\bigcup_{r \in \mathbb{R}} S_r^*$ containing the significant change-point $\tau_k$. In particular, $\hat{K} \ge |\mathcal{K}^*|$. We have

* By Proposition 9, $C_k \subset [\tau_k - 2(\bar{r}_k - 1), \tau_k + 2(\bar{r}_k - 1)]$ for every $k \in \mathcal{K}^*$. Thus

$$ |\hat{\tau}_k - \tau_k| \le (\bar{r}_k - 1) < \frac{r_k}{4}. $$

* For all $k \in [K] \setminus \mathcal{K}^*$, either $\tau_k$ does not belong to $\bigcup_{r \in \mathbb{R}} S_r$ and it is simply not detected, or it is the closest true change-point to $\hat{\tau}_k = \frac{\min C_k + \max C_k}{2}$ so that

$$ \hat{\tau}_k \in \left[ \tau_k - \frac{\tau_k + \tau_{k-1}}{2}, \tau_k + \frac{\tau_k + \tau_{k+1}}{2} \right] . $$

In particular,

$$ \{\hat{\tau}_{k'}, k' \le \hat{K}\} \subset \left[ \tau_1 - \frac{\tau_1 - \tau_0}{2}, \tau_K + \frac{\tau_{K+1} - \tau_K}{2} \right] . $$

* Finally, if there exists two estimated change-points $\hat{\tau}_{k_1}, \hat{\tau}_{k_2}$ in $[\tau_k - \frac{\tau_k + \tau_{k-1}}{2}, \tau_k + \frac{\tau_k + \tau_{k+1}}{2}]$, then either $C_{k_1}$ or $C_{k_2}$ does not contain $\tau_k$. Then $\Theta$ is constant on $C_{k_1}$ or on $C_{k_2}$ and we obtain a contradiction since there is no false positive.

This concludes the proof of Theorem 1.

*Proof of Proposition 9.* To prove the proposition, we do an induction on $r \in \mathbb{R} \cup \{0\}$. The case $r = 0$ is trivial since by definition, $S_0 = \emptyset$. Let $r \in \mathbb{R}$ and assume that the double inclusion Proposition 9 holds for all $r' < r, r' \in \mathbb{R} \cup \{0\}$.
**Step 3: Combination of the two Statistics** Let us return to the proof of Proposition 2. To conclude the proof, it suffices to show that if $\tau_k$ is a $\kappa_s$-sparse high-energy change-point - see (11) - for some large enough constant $\kappa_s$, then the result of one of the two preceding propositions holds. This is precisely what the following lemma shows.

**Lemma 3.** There exists a constant $\kappa_s$ such that if $\tau_k$ is a $\kappa_s$-sparse high-energy change-point, then one of the following propositions is true:

* There exists $s \in \mathbb{Z}$ such that $s > \bar{s}_{\bar{\tau}_k}^{(s)}$ and $|U_{\bar{\tau}_k}^{(s)}, \bar{\tau}_k^{(s)}, (s)| > x_{\bar{\tau}_k}^{(\text{BJ})}$.

* There exists $s \in \mathbb{Z}$ such that $s \le \bar{s}_{\bar{\tau}_k}^{(s)}$ and $\sum_{s'=1}^{s} |U_{\bar{\tau}_k}^{(s)}, \bar{\tau}_k^{(s)}, (s')|^2 > 4x_{\bar{\tau}_k}^{(\text{p})}$.

*Proof of Proposition 11.* The first part of the proposition is a simple consequence of the definition together with an union bound.

$$ \mathbb{P}\left[\max_{(l,r) \in \mathcal{H}_0} T_{l,r}^{(\text{BJ})} = 1\right] \le \sum_{r \in \mathcal{R}} \sum_{l \in \mathcal{D}_r} \sum_{x \in \mathbb{N}^*} \delta_{x,r}^{(\text{BJ})} \\ \le \sum_{r \in \mathcal{R}} \sum_{l \in \mathcal{D}_r} \frac{\delta r}{|\mathcal{D}_r|n} \le \sum_{r \in \mathcal{R}} \frac{\delta r}{n} \le \delta. $$

We focus on the second part of the proposition. To ease the reading, we introduce some notation

$$ \gamma_{x,r} = \overline{Q}^{-1}[\delta_{x,r}, p, 2\overline{\Phi}(x)]; \quad \eta_{x,r,s} = \overline{Q}^{-1}[1 - \delta_{x,r}/2, p - s, 2\overline{\Phi}(x)]; \\ \psi_{x,r,s}(u) = \overline{Q}^{-1}[1 - \delta_{x,r}/2, s, \overline{\Phi}(x - u) + \overline{\Phi}(x + u)], $$

for $x \ge 0$. In fact, $\gamma_{x,r}$ is the threshold of the statistics $N_{x,l,r}$. As for $\eta_{x,r,s}$, it stands for the contribution to $N_{x,l,r}$ of the $(p-s)$ coordinates $i$ such that $\theta_{.,i}$ is constant over $[l-r, l+r)$. Finally, $\psi_{x,r,s}(u)$ stands for the contribution to $N_{x,l,r}$ of the $s$ coordinates $i$ whose population CUSUM statistics $U_{l,r,i}$ is equal to $u$.

**Lemma 4.** Consider any $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$. If for some positive integers $s$ and $x$ we have

$$ \psi_{x,r,s}(|U_{l,r,s}|) > \gamma_{x,r} - \eta_{x,r,s}, \qquad (35) $$

then $\mathbb{P}[T_{l,r}^{(\text{BJ})} = 1] \ge 1 - \delta_{x,r}$.

Denote $\mathcal{H}[\theta]$ the collection of $(l,r)$ with $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$ that satisfy Condition (35) for some $s$ and some $x$. We easily deduce from the above Lemma together with an union bound that, with probability higher than $1 - \delta$, $T_{l,r}^{(\text{BJ})} = 1$ for all $(l,r) \in \mathcal{H}[\theta]$.

Let us now provide a more explicit characterisation of $\mathcal{H}[\theta]$ with the following Lemma.

**Lemma 5.** For any $1 \le s \le p$ and $r \in \mathcal{R}$ define $x_s$ by

$$ x_s := x_{r,s}^{(\text{BJ})} = \min \left\{ x \ge 2 : \overline{\Phi}(x) \le \frac{s^2}{28^2 p \log(2\alpha_{x,r}^{-1})} \right\}. $$

We have $\psi_{x_s,r,s}(t_s) > \gamma_{x_s,r} - \eta_{x_s,r,s}$ provided that

$$ s \ge \frac{28}{3} \log(2\delta_{x_s,r}^{-1}). \qquad (36) $$
**First inclusion:** Let $k \in \mathcal{K}^*$ be such that $\bar{r}_k = r$ and assume that the corresponding significant change-point $\tau_k$ has not been detected before step $r$, that is $\tau_k \notin \bigcup_{r'<r} S_{r'}^*$. Since $k \in \mathcal{K}^*$, this implies in particular that $\tau_k \notin \bigcup_{r'<r} S_{r'}$. Let us show that $\tau_k \in S_r$. To this end we prove that

$$[\bar{\tau}_k - r + 1, \bar{\tau}_k + r - 1] \cap \bigcup_{r'<r, r' \in \mathcal{R}} S_{r'} = \emptyset \quad (29)$$

and

$$T_{\bar{\tau}_k, r} = 1, \quad (30)$$

which will be enough since $|\bar{\tau}_k - \tau_k| \le \bar{r}_k - 1 = r - 1$.

* **Proof of (29):** Assume for the sake of contradiction that there exists an integer $z$ which belongs to $[\bar{\tau}_k - r + 1, \bar{\tau}_k + r - 1] \cap \bigcup_{r'<r, r' \in \mathcal{R}} S_{r'}$. There exists $r' < r$

such that $z \in S_{r'}$ and $l(z) \in \mathcal{T}_{r'}$ such that $z \in [l(z) - r' + 1, l(z) + r' - 1]$.

Since $\tau_k \notin \bigcup_{r'<r} S_{r'}$, we have $\tau_k \notin [l(z) - r' + 1, l(z) + r' - 1]$. Moreover,

$$\begin{aligned} |l(z) - \tau_k| &\le |l(z) - z| + |z - \bar{\tau}_k| + |\bar{\tau}_k - \tau_k| \\ &\le (r' - 1) + (r - 1) + |\bar{\tau}_k - \tau_k| \\ &< r_k - r', \end{aligned}$$

Where the last inequality comes from the hypothesis $3(\bar{r}_k - 1) + |\bar{\tau}_k - \tau_k| \le r_k$. Consequently,

$$[l(z) - r', l(z) + r'] \subset [\tau_k - r_k, \tau_k + r_k) \setminus \{\tau_k\},$$

so that $\theta$ is constant on $[l(z) - r', l(z) + r'] \cap \mathbb{N}$. Thus, $(l(z), r') \in \mathcal{H}_0$ and $l(z) \notin \mathcal{T}_{r'}$ since there is no false positive. This gives a contradiction and concludes the proof of (29).

* **Proof of (30):** This is simply a consequence of the fact that significant change-point are detected on the grid (See Item 2 in the definition of $\mathcal{A}$).

We have just shown that $\tau_k \in S_r$ and hence $\tau_k \in S_r^*$ so that the first inclusion holds at step $r$.

**Second inclusion** : Let $x$ be an element of $S_r^*$. There exists $l(x) \in \mathcal{T}_r^*$ such that

$x \in [l(x) - r + 1, l(x) + r - 1]$. By definition of $\mathcal{T}_r^*$, there exists a significant change-point $\tau_k$ (i.e. such that $k \in \mathcal{K}^*$) belonging to $[l(x) - r + 1, l(x) + r - 1]$.

We necessarily have $\bar{r}_k \ge r$. Indeed, if $\bar{r}_k < r$, then by the induction hypothesis, $\tau_k \in S_{r'}^*$ for some $r' < r$, which contradicts the fact that $S_{r'}^*$ is disjoint from $[l(x) - r + 1, l(x) + r - 1] \subset S_r^*$. Consequently,

$$|l(x) - \tau_k| + r - 1 \le 2r - 2$$
Combining Lemma 5 and Lemma 4, we conclude the proof of the proposition. □

*Proof of Lemma 4.* Denote $S$ any subset of size $s$, such that for any $j \in S$, $|U_{l,r,j}| \ge |U_{l,r,(s)}|$. Define

$$N_{x,l,r}^{(1)} = \sum_{i=1}^{p} \mathbf{1}_{i \notin S} \mathbf{1}_{C_{l,r,i}} > x, \qquad N_{x,l,r}^{(2)} = \sum_{i=1}^{p} \mathbf{1}_{i \in S} \mathbf{1}_{C_{l,r,i}} > x$$

Since, for any $x > 0$, the function $u \mapsto \bar{\Phi}(x+u) + \bar{\Phi}(x-u)$ is non-decreasing. As a consequence, the random variable $N_{x,l,r}^{(1)}$ is stochastically dominated by a Binomial distribution with parameters $(p-s, 2\bar{\Phi}(x))$. Besides, $N_{x,l,r}^{(2)}$ is stochastically dominated by a Binomial distribution with parameters $(s, \bar{\Phi}(x + |U_{l,r,(s)}|) + \bar{\Phi}(x - |U_{l,r,(s)}|))$. We obtain

$$ \begin{aligned} \mathbb{P}[T_{l,r}^{(BJ)} = 0] &\le \mathbb{P}[N_{x,l,r} \le \gamma_{x,r}] \le \mathbb{P}[N_{x,l,r}^{(1)} < \eta_{x,r,s}] + \mathbb{P}[N_{x,l,r}^{(2)} \le \gamma_{x,r} - \eta_{x,r,s}] \\ &\le \frac{\delta_{x,r}}{2} + 1 - \bar{Q}[\gamma_{x,r} - \eta_{x,r,s}, s, \bar{\Phi}(x - |U_{l,r,(s)}|) + \bar{\Phi}(x + |U_{l,r,(s)}|)] \\ &\le \frac{\delta_{x,r}}{2} + \frac{\delta_{x,r}}{2} \le \delta_{x,r}. \end{aligned} $$

<figure><img src="image_10.png" /></figure>

*Proof of Lemma 5.* From Bernstein inequality, we deduce that, for any positive integers $s$ and $x$,

$$ \begin{aligned} \gamma_{x,s} &\le 2p\bar{\Phi}(x) + 2\sqrt{p\bar{\Phi}(x)\log(\delta_{x,r}^{-1})} + \frac{2}{3}\log(\delta_{x,r}^{-1}) ; \\ \eta_{x,r,s} &\ge 2(p-s)\bar{\Phi}(x) - 2\sqrt{p\bar{\Phi}(x)\log(2\delta_{x,r}^{-1})} - \frac{2}{3}\log(2\delta_{x,r}^{-1}) . \end{aligned} $$

Hence, it follows that

$$ \gamma_{x,s} - \eta_{x,r,s} \le 2s\bar{\Phi}(x) + 4\sqrt{p\bar{\Phi}(x)\log(2\delta_{x,r}^{-1})} + \frac{4}{3}\log(2\delta_{x,r}^{-1}) . $$

For $u = x$, we have $\bar{\Phi}(x-u) + \bar{\Phi}(x+u) \ge \bar{\Phi}(0) = 1/2$ and we derive from Bernstein inequality that

$$ \psi_{x,r,s}(t) \ge \frac{s}{2} - \sqrt{s \log(2\delta_{x,r}^{-1})} - \frac{2}{3} \log(2\delta_{x,r}^{-1}) . $$

As a ce, $\psi_{x,r,s}(t) > \gamma_{x,s} - \eta_{x,r,s}$ as long as

$$ s(1 - 4\bar{\Phi}(x)) > 12\sqrt{p\bar{\Phi}(x)\log(2\delta_{x,r}^{-1})} + \frac{12}{3}\log(2\delta_{x,r}^{-1}) . $$

Provided that we take $x \ge 2$, the latter holds if

$$ s \ge 14\sqrt{p\bar{\Phi}(x)\log(2\delta_{x,r}^{-1})} + \frac{14}{3}\log(2\delta_{x,r}^{-1}) \qquad (37) $$

In view of the definition (32) of $x_s$, we have $14\sqrt{p\bar{\Phi}(x_s)\log(2\delta_{x_s,r}^{-1})} \le s/2$. Hence, under Condition (33), (37) holds and we conclude that $\psi_{x_s,r,s}(x_s) > \gamma_{x_s,s} - \eta_{x_s,r,s}$. □

<figure><img src="image_11.png" /></figure>
$$ \leq 2(\bar{r}_k - 1) $$

Thus

$$ x \in [l(x) - r + 1, l(x) + r - 1] \subset [\tau_k - 2(\bar{r}_k - 1), \tau_k + 2(\bar{r}_k - 1)] . $$

We have just shown that $S_r^* \subset \bigcup_{k \in \mathcal{K}^*} [\tau_k - 2(\bar{r}_k - 1), \tau_k + 2(\bar{r}_k - 1)]$.

Therefore, the proposition is verified at step $r$ and the induction is proved. $\square$

**Proof of Proposition 10.** Let $k \in \mathcal{K}^*$ and $C_k$ be the detected connected component containing the significant change-point $\tau_k$

$$ C_k = \bigcup_{r' \in \mathcal{R}} S_{r'}^* \cap [\tau_k - 2(\bar{r}_k - 1), \tau_k + 2(\bar{r}_k - 1)] . $$

We know from Proposition 9 that $C_k$ is a connected component of $\bigcup_{r' \in \mathcal{R}} S_{r'}^*$ and we want to prove now that $C_k$ does not overlap with $\bigcup_{l \in \mathcal{T}_r \setminus \mathcal{T}_{r'}^*} [l-r+1, l+r-1]$ for some $r \in \mathcal{R}$. Let $r_0$ be such that $C_k$ is the connected component of $S_{r_0}$,

$$ C_k \subset S_{r_0}^* . $$

Such an $r_0$ exists and is unique since the sets $(S_{r'}^*)$ are disjoint. We have from Proposition 9 that $\tau_k \in \bigcup_{r' \in \mathcal{R}, r' \le \bar{r}_k} S_{r'}^*$ so that

$$ r_0 \le \bar{r}_k . $$

Let $r \in \mathcal{R}$ and $l \in \mathcal{T}_r \setminus \mathcal{T}_r^*$ and assume without loss of generality that $l+r-1 < \tau_k$. Since there is no false positive, $(l, r) \notin \mathcal{H}_0$ and there exists at least one true change-point in the interval of detection $[l-r+1, l+r-1]$. Denote $\tau_a, \dots, \tau_b$ with $a \le b$ the true change-points belonging to $[l-r+1, l+r-1]$. By definition of $\mathcal{T}_r \setminus \mathcal{T}_r^*$, $\tau_a, \dots, \tau_b$ are not significant change-points, i.e. $a, a+1, \dots, b \notin \mathcal{K}^*$. We consider the two cases $r > \bar{r}_k$ and $r \le \bar{r}_k$

* $r > \bar{r}_k$: In that case, since the sets $(S_{r'})$ are disjoint and $C_k \subset S_{r_0}^*$, we have $C_k \cap [l-r+1, l+r-1] = \emptyset$.

* $r \le \bar{r}_k$: In that case, we have

$$ l+r-1 \le \tau_b + 2(r-1) \le \tau_b + 2(\bar{r}_k - 1) < \tau_k - 2(\bar{r}_k - 1), $$

where we used the fact that $4(\bar{r}_k - 1) < r_k \le \tau_k - \tau_b$. Since by Proposition 9 we have $C_k \subset [l-r+1, l+r-1]$, we also have in that case $C_k \cap [l-r+1, l+r-1] = \emptyset$.

This concludes the proof of the proposition. $\square$

## B.2. Proofs for Gaussian multivariate change-point detection

From now on, we use the following notation for all $(l, r) \in J_n$.
Proof of Proposition 12. The following lemma ensures that the partial norm test returns 0 with high probability jointly at all positions where there is no change-point. We write $\bar{C}_p^s$ for the set of all combinations of s indices taken from $[p]$.

**Lemma 6** (concentration of the pure noise for the second sparse statistic). If $1 \ge \delta > 0$, then the event

$$ \xi_1^{(p)} = \left\{ \forall r \in \mathcal{R}, l \in \mathcal{D}_r, s \in \mathcal{Z} \quad \max_{S \in \bar{C}_p^s} \sum_{i \in S} \frac{r}{2\sigma^2} (\bar{\varepsilon}_{l,+r,i} - \bar{\varepsilon}_{l,-r,i})^2 \le x_{r,s}^{(p)} \right\} $$

holds with probability higher than $1 - \delta$.

We now state the following lemma, which ensures that the partial norm test returns 1 with high probability jointly at relevant positions which are close to a change-point.

**Lemma 7** (concentration on the change-points for the second sparse statistic). We write $\bar{\mathcal{K}}^*$ for the set of $k \in [K]$ such that

$$ \bullet \ s_k \le \sqrt{p \log \left( \frac{n}{r_k \delta} \right)} $$

$$ \bullet \ \sum_{s'=1}^{s} \left| U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')} \right|^2 \ge 4x_{\bar{\tau}_k^{(s)}, s}^{(p)} $$

If $1 \ge \delta > 0$, the event

$$ \xi_2^{(p)} = \left\{ \forall k \in \bar{\mathcal{K}}^* : \exists s \in \mathcal{Z} \text{ s.t. } \Psi_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, s}^{(p)} > x_{\bar{\tau}_k^{(s)}, s}^{(p)} \right\}, $$

holds with probability higher than $1 - \delta$.

Lemmas 6 and 7 directly imply the result of the proposition. $\square$

Proof of Lemma 6. Let $r \in \mathcal{R}$, $l \in \mathcal{D}_r$, $s \le \bar{s}_r$ and $S \in \bar{C}_p^s$. Let $\delta > 0$, $\delta_{r,s} = (\frac{r}{n})^2 (\frac{s}{2ep})^s \delta$. Since $\sqrt{\frac{r}{2\sigma^2}} (\bar{\varepsilon}_{l,+r,i} - \bar{\varepsilon}_{l,-r,i})$ follows a $\mathcal{N}(0, 1)$ distribution for all $l, r, i$, we have by Bernstein's inequality that with probability larger than $1 - \delta_{r,s}$,

$$ \begin{aligned} \sum_{i \in S} (\bar{\varepsilon}_{l,+r,i} - \bar{\varepsilon}_{l,-r,i})^2 &\le s + 2 \sqrt{s \log \left( \frac{1}{\delta_{r,s}} \right)} + \log \left( \frac{1}{\delta_{r,s}} \right) \\ &\le 2 \left( s + \log \left( \frac{1}{\delta_{r,s}} \right) \right) \\ &= 2 \left( s + s \log \left( \frac{2ep}{s} \right) + \log \left( \frac{n^2}{r^2 \delta} \right) \right) \\ &\le 4 \left( s \log \left( \frac{2ep}{s} \right) + \log \left( \frac{n}{r \delta} \right) \right). \end{aligned} $$
* For any $(v_1, \dots, v_n)$ with $v_t \in \mathbb{R}^p$, the left mean and right mean of $v$ on $[l-r, l+r)$ are denoted by

$$ \bar{v}_{l,+r} = \frac{1}{r} \sum_{t=l}^{l+r-1} v_t \quad \bar{v}_{l,-r} = \frac{1}{r} \sum_{t=l-r}^{l-1} v_t . $$

* The population term of the CUSUM statistic $C_{l,r}$ is written

$$ U_{l,r} = \sqrt{\frac{r}{2}} (\bar{\theta}_{l,+r} - \bar{\theta}_{l,-r}) . $$

* With these notation, we write $v_{l,+r,i}$, $v_{l,-r,i}$, $U_{l,r,i}$ for the $i^{th}$ coordinate of the vector $v_{l,+r}$, $v_{l,-r}$, $U_{l,r}$.

* We define, for $1 \le s \le p$, the order statistics $U_{l,r,(s)}$ by $|U_{l,r,(1)}| \ge |U_{l,r,(2)}| \ge \dots |U_{l,r,(p)}|$.

### B.2.1. Proof of Proposition 1

**Step 0: Consequence of Equation (10) on the grid** Let $k \in [K]$ and assume that $\tau_k$ is a $\kappa_d$-dense high-energy change-point (see Equation (10)). We have that

$$ \begin{aligned} \| U_{\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)}} \|^2 &\ge \frac{9}{16} \| U_{\tau_k, \bar{r}_k^{(d)}} \|^2 \\ &\ge \frac{9}{16 \times 12} \kappa_d \left( \sqrt{p \log \left( \frac{n}{\bar{r}_k^{(d)}}, \delta \right)} + \log \left( \frac{n}{\bar{r}_k^{(d)}}, \delta \right) \right), \end{aligned} \quad (31) $$

since by definition $\|\tau_k - \bar{\tau}_k^{(d)}\| \le \bar{r}_k^{(d)}/4$, so that $||\bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}||^2 \ge \frac{9}{16} ||\bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}}||^2$.

**Step 1: Introduction of useful high probability events** Remark that

$$ \begin{aligned} & \frac{r}{2} \left[ \| \bar{y}_{l,+r} - \bar{y}_{l,-r} \|^2 - \| \bar{\theta}_{l,-r} - \bar{\theta}_{l,+r} \|^2 \right] - \sigma^2 p \\ & = r \langle \bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle + \frac{r}{2} \| \bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r} \|^2 - \sigma^2 p . \end{aligned} $$

The first term, written as

$$ r \langle \bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle , $$

is a crossed term between the noise and the mean vector $\theta$. Lemma 1 states that near the change-points and on the grid defined by the sets $\mathcal{R}$, $\mathcal{D}_r$, it is jointly controlled with high probability.
Since the number of such S is smaller than $(\frac{ep}{s})^s$, a union bound gives

$$ 
\begin{aligned}
\mathbb{P}(\xi_1^{(p)}) &\ge 1 - \sum_{r \in \mathcal{R}} \sum_{l \in \mathcal{D}_r} \sum_{s \in \mathcal{Z}} |\tilde{C}_p^s| \left(\frac{s}{2ep}\right)^s \left(\frac{r}{n}\right)^2 \delta \\
&\ge 1 - \sum_{r \in \mathcal{R}} \sum_{l \in \mathcal{D}_r} \sum_{s \in \mathcal{Z}} \left(\frac{1}{2}\right)^s \left(\frac{r}{n}\right)^2 \delta \\
&\ge 1 - \delta,
\end{aligned}
$$

which yields the result.

<figure><img src="image_12.png" /></figure>

*Proof of Lemma 7.* Let $k \in \bar{\mathcal{K}}^*$, and $s \in \mathcal{Z}$ such that

$$ \sum_{i=1}^{s} U_{\bar{\tau}_{k}^{(s)}, \bar{r}_{k}^{(s)}, (i)}^{2} > 4x_{\bar{\tau}_{k}^{(s)}, s}^{(p)} \quad (38) $$

To ease the reading, we write $(\tau, r) = (\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)})$. Then on the event $\xi_1^{(p)}$ which holds with probability $1 - \delta$, we have

$$ 
\begin{aligned}
\Psi_{\tau,r,s}^{(p)} &= \max_{S \in \bar{C}_p^s} \sum_{i \in S} \frac{r}{2\sigma^2} (\bar{\theta}_{\tau,+r,i} + \bar{\varepsilon}_{\tau,+r,i} - \bar{\theta}_{\tau,-r,i} - \bar{\varepsilon}_{\tau,-r,i})^2 \\
&\geq \max_{S \in \bar{C}_p^s} \sum_{i \in S} \frac{1}{2} U_{\tau,r,i}^2 - \frac{r}{2\sigma^2} (\bar{\varepsilon}_{\tau,+r,i} - \bar{\varepsilon}_{\tau,-r,i})^2 \\
&> 2x_{r,s}^{(p)} - x_{r,s}^{(p)} \\
&= x_{r,s}^{(p)},
\end{aligned}
$$

where in the second inequality, we used the fact that $(a+b)^2 \ge \frac{1}{2}a^2 - b^2$ for all $a, b \in \mathbb{R}$.

<figure><img src="image_13.png" /></figure>

*Proof of Lemma 3.* First remark that there exists a large enough constant $C$ such that for all $r, s \ge 1$,

$$ 
\begin{aligned}
(x_{r,s}^{(\text{BJ})})^2 &\le C \log \left( \frac{ep}{s^2} \log \left( \frac{n}{r\delta} \right) \right) \\
\bar{s}_r &\le C \log \left( \log \left( \frac{ep}{\bar{s}_r^2} \right) \frac{n}{r\delta} \right),
\end{aligned}
$$

where we recall that $\bar{s}_r$ is defined by (33) and $x_{r,s}^{(\text{BJ})}$ by (32). These two inequalities come from the fact that for all $t \ge 2$ and all $A > 0$, if $t \le A + \log(t)$ then $t \le 2A$. Assume that for all $s' = \bar{s}_{\bar{\tau}_k^{(s)}} + 1, \dots, s_k$ we have $|U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}| < x_{\bar{\tau}_k^{(s)}, s'}^{(\text{BJ})}$. To ease the notation, we write $\bar{s} = \bar{s}_{\bar{\tau}_k^{(s)}} \wedge s_k$ and in what follows we prove that $\sum_{s'=1}^{\bar{s}} |U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}|^2 > 4x_{\bar{\tau}_k^{(s)}, \bar{s}}^{(p)}$ when $\kappa_s$ is a large enough constant. We have

$$ 
\begin{aligned}
\sum_{s'=\bar{s}_{\bar{\tau}_k^{(s)}+1}}^{s_k} U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}^2 &\le C_1 \sum_{i=0}^{[\log(s_k)]} 2^i \log \left( \frac{ep}{2^{2i}} \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right) \\
&\le C_1 s_k \log \left( 2e \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right) + C_1 \sum_{i=0}^{[\log(s_k)]} 2^i \log \left( \frac{p}{2^{2(i+1)}} \right),
\end{aligned}
$$
**Lemma 1.** Let $1 \ge \delta > 0$. The event

$$ \xi_1^{(d)} = \bigcap_{k \in [K]} \left\{ \bar{r}_k^{(d)} \left| \begin{aligned} & \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}}, +\bar{r}_k^{(d)} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}}, -\bar{r}_k^{(d)}, \bar{\theta}_{\bar{\tau}_k^{(d)}}, +\bar{r}_k^{(d)} - \bar{\theta}_{\bar{\tau}_k^{(d)}}, -\bar{r}_k^{(d)} \rangle \\ & \le \frac{1}{8} \bar{r}_k^{(d)} \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2 + 16\sigma^2 \log \left( 2 \frac{n}{\bar{r}_k^{(d)} \delta} \right) \end{aligned} \right\}. $$

holds with probability larger than $1 - \delta$.

The second term, written as

$$ \frac{r}{2} \|\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}\|^2 - \sigma^2 p, $$

is a term of pure noise. Lemma 2 states that it is controlled jointly with high probability on the grid defined by the sets $\mathcal{R}, \mathcal{D}_r$.

**Lemma 2.** Let $1 \ge \delta > 0$. The event

$$ \xi_2^{(d)} = \bigcap_{r \in \mathcal{R}} \bigcap_{k \in \mathcal{D}_r} \left\{ \left| \frac{r}{2} \|\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}\|^2 - \sigma^2 p \right| \le 4\sigma^2 \left[ \sqrt{p \log\left(2 \frac{n}{r\delta}\right)} + \log\left(2 \frac{n}{r\delta}\right) \right] \right\}, $$

holds with probability larger than $1 - \delta$.

Set now

$$ \xi^{(d)} := \xi^{(d)} = \xi_{1}^{(d)} \cap \xi_{2}^{(d)}. $$

Note that

$$ \mathbb{P}(\xi^{(d)}) \ge 1 - 2\delta. $$

**Step 2: Study in the ‘no change-point’ situation** Consider $r \in \mathcal{R}, l \in \mathcal{D}_r$ such that $\{\tau_k, k \in [K]\} \cap [l-r, l+r) = \emptyset$. Note that since $\{\tau_k, k \in [K]\} \cap [l-r, l+r) = \emptyset$, we have $\bar{\theta}_{l,-r} = \bar{\theta}_{l,+r}$ so that

$$ \frac{r}{2} \|\bar{\theta}_{l,-r} - \bar{\theta}_{l,+r}\|^2 = 0, $$

and

$$ r \langle \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle = 0. $$

Moreover we have on $\xi^{(d)}$ that – see Lemma 2

$$ \left| \frac{r}{2} \|\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}\|^2 - \sigma^2 p \right| \le 4\sigma^2 \left[ \sqrt{p \log\left(2 \frac{n}{r\delta}\right)} + \log\left(2 \frac{n}{r\delta}\right) \right] = \sigma^2 x_r^{(d)}. $$

And so

$$ \Psi_{l,r}^{(d)} \le x_r^{(d)}, $$

so that

$$ T_{l,r}^{(d)} = 0, $$

on $\xi^{(d)}$. This concludes the proof of the first part of the proposition.
for some universal constant $C_1$. To handle the second term remark that since $x \mapsto \log(p/x^2)$ is decreasing, we have

$$ \begin{aligned} \sum_{i=0}^{\lfloor \log(s_k) \rfloor} 2^i \log \left( \frac{p}{2^{2(i+1)}} \right) &\le \int_1^{2s_k} \log \left( \frac{p}{x^2} \right) dx \\ &= 2s_k \log \left( \frac{p}{(2s_k)^2} \right) + 2s_k - 1 \\ &\le 2s_k \log \left( \frac{p}{s_k^2} \right), \end{aligned} $$

and thus

$$ \sum_{s'=\bar{s}, \bar{s}=(s_k)+1}^{s_k} U_{\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)}, (s')}^2 \le 2C_1 s_k \log \left( 2e \frac{p}{s_k^2} \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right), $$

which finally gives

$$ \begin{aligned} \sum_{s'=1}^{\bar{s}} U_{\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)}, (s')}^2 &\ge \frac{9}{16} \bar{r}_k^{(s)} \Delta_k^2 - 2C_1 s_k \log \left( \frac{2ep}{s_k^2} \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right) \\ &\ge 4x_{\bar{r}_k^{(s)}, \bar{s}}^{(p)}. \end{aligned} $$

In the first inequality we used the fact that

$$ |\bar{\tau}_k^{(s)} - \tau_k| \le \frac{1}{4} \bar{r}_k^{(s)}, $$

so that for all $i$,

$$ \begin{aligned} \left| \bar{\theta}_{\bar{\tau}_k^{(s)}, +\bar{r}_k^{(s)}, i} - \bar{\theta}_{\bar{\tau}_k^{(s)}, -\bar{r}_k^{(s)}, i} \right| &= \frac{1}{\bar{r}_k^{(s)}} \left| (\bar{r}_k^{(s)} + \bar{\tau}_k^{(s)} - \tau_k) \mu_{k,i} - (\bar{r}_k^{(s)} - \bar{\tau}_k^{(s)} + \tau_k) \mu_{k-1,i} \right| \\ &\ge \left( 1 - \frac{|\bar{\tau}_k^{(s)} - \tau_k|}{\bar{r}_k^{(s)}} \right) |\mu_{k,i} - \mu_{k-1,i}| \\ &> \frac{3}{4} |\mu_{k,i} - \mu_{k-1,i}| = \frac{3}{4} U_{k,i} . \end{aligned} $$

In the second inequality, we used the fact that

• $8\bar{r}_k^{(s)} \Delta_k^2 \ge \kappa_s \sigma^2 \left( s_k \log \left( \frac{p}{s_k^2} \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right) + \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right)$ for a large enough constant $\kappa_s$ (see (11)),

• $x \mapsto x \log(p/x^2)$ is increasing for $x \le p$, so that $s_k$ can be replaced by $\bar{s}$,

• $\bar{s} \le C \log \left( \log \left( \frac{ep}{s^2} \frac{n}{r\delta} \right) \right)$.

This concludes the proof of the lemma. $\square$
**Step 3: Study in the 'change-point' situation** Consider $k \in [K]$ $\tau_k$ is a $\kappa_d$-dense high-energy change-point – that is Equation (10) holds. We have from (31) that for $\kappa_d$ large enough,

$$ \frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} \right\|^2 \\ \geq \frac{9}{16 \times 12} \kappa_d \sigma^2 \left( \sqrt{p \log \left( \frac{n}{\bar{r}_k^{(d)}, \delta} \right)} + \log \left( \frac{n}{\bar{r}_k^{(d)}, \delta} \right) \right) > 4\sigma^2 x_{\bar{r}_k^{(d)}} $$

So on $\xi^{(d)}$ this implies that – see Lemma 1

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \right| \\ \leq \frac{\bar{r}_k^{(d)}}{4} \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2. $$

Moreover we have on $\xi^{(d)}$ that – see Lemma 2

$$ \left| \frac{\bar{r}^{(d)}}{2} \left\| \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2 - \sigma^2 p \right| \\ \leq 4\sigma^2 \left[ \sqrt{p \log \left( 2 \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right)} + \log \left( 2 \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right) \right] = \sigma^2 x_{\bar{r}_k^{(d)}}^{(d)}. $$

And so on $\xi^{(d)}$, combining the three previous displayed equations implies

$$ \Psi_{\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)}}^{(d)} \geq \frac{\frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2}{2\sigma^2} - x_{\bar{r}_k^{(d)}}^{(d)} > (2-1)x_{\bar{r}_k^{(d)}}^{(d)} = x_{\bar{r}_k^{(d)}}^{(d)}, $$

so that

$$ T_{\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)}}^{(d)} = 1. $$

This concludes the proof of the second part of the proposition.

*Proof of Lemma 1.* Let $k \in [K]$. Since the vectors $\epsilon_t$ are i.i.d. and distributed as $N(0, \sigma^2 I_p)$, it holds that

$$ \bar{r}_k^{(d)} \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \\ \sim \mathcal{N} \left( 0, 2\bar{r}_k^{(d)} \sigma^2 \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2 \right). $$

And so for $\delta_k > 0$, it holds with probability larger than $1 - \delta_k$ it holds that

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \right| \\ \leq 2\sigma \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\| \sqrt{\bar{r}_k^{(d)} \log(2\delta_k^{-1})}. $$
### B.2.3 Proof of Corollary 2

Let $\xi^{(d)}$ and $\xi^{(s)}$ be two events such that Proposition 1 and Proposition 2 hold respectively with constants $\kappa_d, \kappa_s$ and with probability $1-2\delta$ and $1-4\delta$, and write $\xi = \xi^{(d)} \cap \xi^{(s)}$. From now on, we work on the event $\xi$, which holds with probability $1-6\delta$. Let us choose $c_0 \ge 2(\kappa_d \vee \kappa_s)$ in (8). For all $k$ such that $\tau_k$ is a $c_0$-high-energy change-point, define

$$ (\bar{\tau}_k, \bar{r}_k) = \begin{cases} (\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)}) & \text{if } s_k > \sqrt{p \log \left( \frac{n}{r_k \delta} \right)} \\ (\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)}) & \text{if } s_k \le \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}. \end{cases} $$

$(\bar{r}_k, \bar{\tau}_k)$ is well defined. Indeed, If $s_k \le \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}$ then

$$ s_k \log \left( 1 + \frac{\sqrt{p}}{s_k} \sqrt{\log \left( \frac{n}{r_k \delta} \right)} \right) + \log \left( \frac{n}{r_k \delta} \right) \ge \frac{1}{2} \left( s_k \log \left( \frac{p}{s_k^2} \log \left( \frac{n}{r_k \delta} \right) \right) + \log \left( \frac{n}{r_k \delta} \right) \right). $$

Now if $s_k \ge \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}$ then using $\log(1+x) \ge \frac{x}{2}$ for $x \in [0,1]$ we have

$$ s_k \log \left( 1 + \frac{\sqrt{p}}{s_k} \sqrt{\log \left( \frac{n}{r_k \delta} \right)} \right) + \log \left( \frac{n}{r_k \delta} \right) \ge \frac{1}{2} \left( \sqrt{p \log \left( \frac{n}{r_k \delta} \right)} + \log \left( \frac{n}{r_k \delta} \right) \right). $$

According to Theorem 1, it is sufficient to prove that the event $\mathcal{A}(\Theta, T, \mathcal{K}^*, (\bar{\tau}_k, \bar{r}_k)_{k \in \mathcal{K}^*})$ defined in Section 2.3 holds on $\xi$:

1. (No false positive): for every $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$, if $\Theta$ is constant on $[l-r, l+r)$ then

$$ T_{l,r} = T_{l,r}^{(d)} \vee T_{l,r}^{(s)} = 0, $$

by Proposition 1 and Proposition 2.

2. (High-energy change-point detection): for every $k$ such that $\tau_k$ has $c_0$-high-energy, it holds by definition of $\bar{r}_k^{(d)}$ and $\bar{r}_k^{(s)}$ that

$$ 4(\bar{r}_k - 1) \le r_k. $$

Moreover, $T_{\bar{\tau}_k, \bar{r}_k}^{(s)} = 1$ if $(\bar{\tau}_k, \bar{r}_k) = (\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)})$ by Proposition 2 and $T_{\bar{\tau}_k, \bar{r}_k}^{(d)} = 1$ if $(\bar{\tau}_k, \bar{r}_k) = (\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)})$ by Proposition 1.

Theorem 1 ensures that for all $k \in [K]$ such that $\tau_k$ is a $c_0$-high-energy change-point, there exists $k' \in [\hat{K}]$ such that

$$ |\hat{\tau}_{k'} - \tau_k| \le \bar{r}_k - 1. $$

It remains to show that

$$ \bar{r}_k - 1 \le \frac{r_k^*}{2}, $$

where $r_k^*$ is defined by (9). Using $\log(1+x) \ge \frac{x}{2}$ for $x \in [0,1]$ and $\log(1+x) \ge \log(x)$ for $x \ge 1$ we have

$$ 8\bar{r}_k \Delta_k^2 \le 4(\kappa_d \vee \kappa_s) \left[ s_k \log \left( 1 + \frac{\sqrt{p}}{s_k} \sqrt{\log \left( \frac{n}{\bar{r}_k \delta} \right)} \right) + \log \left( \frac{n}{\bar{r}_k \delta} \right) \right], $$

when $\bar{r}_k \ge 2$. Thus $2(\bar{r}_k - 1) \le r_k^*$ for $c_0 \ge 2(\kappa_d \vee \kappa_s)$. This concludes the proof of Corollary 2.
Let us set $\delta_k = \frac{(\bar{r}_k^{(d)})^2 \delta}{2n^2}$. Note that

$$ \sum_{k \in [K]} \delta_k = \sum_{r \in R} \sum_{k \in [K]: \bar{r}_k^{(d)} = r} \frac{(\bar{r}_k^{(d)})^2 \delta}{2n^2} \le \sum_{r \in R} \sum_{l \in D_r} \frac{r^2 \delta}{2n^2} \le \sum_{r \in \mathcal{R}} \frac{r \delta}{2n} \le \delta, $$

since $r_k \ge \bar{r}_k^{(d)}$ and $|\mathcal{D}_r| \le 2n/r$, and also by definition of $\mathcal{R}$ which implies $\sum_{r \in \mathcal{R}} \frac{r}{n} \le 1$. And so if $\delta \le 1$, then with probability larger than $1 - \delta$, for any $k \in [K]$, we have

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}}, +\bar{r}_k^{(d)} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}}, -\bar{r}_k^{(d)}, \bar{\theta}_{\bar{\tau}_k^{(d)}}, +\bar{r}_k^{(d)} - \bar{\theta}_{\bar{\tau}_k^{(d)}}, -\bar{r}_k^{(d)} \rangle \right| \\ \le 2\sigma \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\| \le \sqrt{2\bar{r}_k^{(d)} \log \left( 2 \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right)}. $$

This implies in particular that with probability larger than $1 - \delta$, for any $k \in [K]$, we have

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}}, \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \rangle \right| \\ \le \frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\theta}_{\bar{\tau}_k^{(d)}, +\bar{r}_k^{(d)}} - \bar{\theta}_{\bar{\tau}_k^{(d)}, -\bar{r}_k^{(d)}} \right\|^2 + 16\sigma^2 \log \left( 2 \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right) . \quad \square $$

*Proof of Lemma 2.* Let $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$. Since the vectors $\epsilon_t$ are i.i.d. and distributed as $N(0, \sigma^2 I_p)$, it holds that

$$ \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 \sim \sigma^2 \chi_p^2, $$

which implies by properties of the $\chi_p^2$ distribution – see e.g. Lemma 1 of [26] – that for any $\delta_r > 0$ we have with probability larger than $1 - \delta_r$

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 2\sigma^2 \sqrt{p \log(2/\delta_r)} + 2\sigma^2 \log(2/\delta_r) . $$

If we set, for $\delta > 0$, $\delta_r = \frac{r^2 \delta}{2n^2}$, we have that with probability larger than $1 - \frac{r\delta}{n}$, that $\forall l \in \mathcal{D}_r$

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 2\sigma^2 \sqrt{p \log(2/\delta_r)} + 2\sigma^2 \log(2/\delta_r) , $$

since $|\mathcal{D}_r| \le 2n/r$. And so with probability larger than $1 - \delta$, for all $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 2\sigma^2 \sqrt{p \log(2/\delta_r)} + 2\sigma^2 \log(2/\delta_r) , $$

since $\sum_{r \in \mathcal{R}} \frac{r}{n} \le 1$. And so finally for $\delta \le 1$ and with probability larger than $1 - \delta$, for all $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$

$$ \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le 4\sigma^2 \left[ \sqrt{p \log \left( 2 \frac{n}{r} \delta^{-1} \right)} + \log \left( 2 \frac{n}{r} \delta^{-1} \right) \right] . $$

This concludes the proof.

$\square$
## B.3 Proofs for sub-Gaussian multivariate change-point detection

We recall that in this section, we work on the complete grid $\mathcal{G}_F = J_n$ defined in Section 2.

### B.3.1 Proof of Proposition 3

**Step 1: Introduction of useful high probability events.** We first introduce two events $\xi_1^{(d)}$ and $\xi_2^{(d)}$ on which the noise can be controlled. Remark that by a simple computation, the noise can be decomposed as follows:

$$ \frac{r}{2} \left[ \|\bar{y}_{l,+r} - \bar{y}_{l,-r}\|^2 - \|\bar{\theta}_{l,-r} - \bar{\theta}_{l,+r}\|^2 \right] - \sigma^2 p = r \langle \bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle + \frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p . $$

The first term written as

$$ r \langle \bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle $$

is a crossed term between the noise and the mean vector $\theta$. Lemma 8 states that for $l$ equal to a true change-point $\tau_k$ and $r$ of order $r_k^*$, it is controlled on event $\xi_1^{(d)}$ with high probability.

**Lemma 8 (concentration of the crossed terms).** Assume that $\kappa$ is a large enough universal constant. The event

$$ \xi_1^{(d)} = \left\{ \forall k \in [K] \text{ s.t. Equation (17) holds for } k, \right. $$

$$ \bar{r}_k^{(d)} \left| \langle \bar{\varepsilon}_{\tau_k, + \bar{r}_k^{(d)}}, - \bar{\varepsilon}_{\tau_k, - \bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, + \bar{r}_k^{(d)}}, - \bar{\theta}_{\tau_k, - \bar{r}_k^{(d)}}, \rangle \right| \le \frac{\bar{r}_k^{(d)}}{4} \left\| \bar{\theta}_{\tau_k, + \bar{r}_k^{(d)}}, - \bar{\theta}_{\tau_k, - \bar{r}_k^{(d)}}, \right\|^2 \right\} $$

holds with probability higher than $1 - \delta$.

The second term written as

$$ \frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p , $$

is a term of pure noise. Lemma 9 states that it is controlled on event $\xi_2^{(d)}$ with high probability.

**Lemma 9 (concentration of the pure noise).** There exists a constant $\bar{c}_{\text{conc}} > 0$ such that the event

$$ \xi_2^{(d)} = \left\{ \forall (l,r) \in J_n, \left| \frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p \right| \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{p \log \left( \frac{n}{r\delta} \right)} + \log \left( \frac{n}{r\delta} \right) \right) \right\} $$

holds with probability higher than $1 - 2\delta$.

Set now

$$ \xi^{(d)} := \xi_1^{(d)} \cap \xi_2^{(d)} . $$

Note that

$$ \mathbb{P}(\xi^{(d)}) \ge 1 - 3\delta . $$
### B.2.2. Proof of Proposition 2

**Step 1: Analysis of the Berk-Jones statistics** We first define a threshold $x_{r,s}^{(\text{BJ})}$ for the Berk-Jones statistics for all $r, s \ge 1$

$$x_{r,s}^{(\text{BJ})} = \min \left\{ x \ge 2 : \bar{\Phi}(x) \le \frac{s^2}{28^2 p \log(2\delta_{x,r}^{-1})} \right\}, \quad (32)$$

where we recall that $\delta_{x,r}$ are the weights defined by (13):

$$\delta_{x,r} = \frac{6\delta r}{\pi^2 x^2 |\mathcal{D}_r| n}.$$

Remark that $(x_{r,s}^{(\text{BJ})})$ is nonincreasing with $s$ and define for all $r \ge 1$

$$\bar{s}_r = \min \left\{ s \in \mathcal{Z} : s \ge \frac{28}{3} \log \left( 2\delta_{x_{r,s}^{(\text{BJ})},r}^{-1} \right) \right\}. \quad (33)$$

The second point of the following proposition ensures that if there exists $s \in \mathcal{Z}$ such that $U_{l,r,(s)} \ge t_s$ for some $s \ge \bar{s}_r$, for $(l,r) = (\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)})$, then $T_{l,r}^{(\text{BJ})} = 1$ with high probability. We recall that $|U_{l,r,(1)}| \ge \dots \ge |U_{l,r,(p)}|$ are the sorted absolute values of the coordinate of $U_{l,r}$ and that $\mathcal{H}_0$ is defined by (7).

**Proposition 11.** There exists an event $\xi^{(\text{BJ})}$ of probability larger than $1 - 2\delta$ such that the following holds:

* $T_{l,r}^{(\text{BJ})} = 0$ for any $(l,r) \in \mathcal{H}_0 \cap \mathcal{G}$.

* For all $k \in [K]$, if there exists $s \in \mathcal{Z}$ such that $s \ge \bar{s}_{\bar{\tau}_k^{(s)}}$ and $U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s)} > x_{\bar{\tau}_k^{(s)}, s}^{(\text{BJ})}$, then $T_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}}^{(\text{BJ})} = 1$.

**Step 2: Analysis of the partial norm statistics** Since it may happen that $\tau_k$ is a sparse high-energy change-point but there is no $s \ge \bar{s}_{\bar{\tau}_k^{(s)}}$ such that $U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s)} \ge x_{\bar{\tau}_k^{(s)}, s}^{(\text{BJ})}$, we use the following proposition on the partial norm test statistic $T_{l,r}^{(\text{p})}$:

**Proposition 12.** There exists an event $\xi^{(\text{p})}$ of probability larger than $1 - 2\delta$ such that the following holds:

* $T_{l,r}^{(\text{p})} = 0$ for any $(l,r) \in \mathcal{H}_0 \cap \mathcal{G}$.

* for any $k \in [K]$, if there exists $s \in \mathcal{Z}$ such that

$$\sum_{s'=1}^{s} \left| U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')} \right|^2 > 4x_{\bar{\tau}_k^{(s)}, s}^{(\text{p})}, \quad (34)$$

then $T_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}}^{(\text{p})} = 1$.
**Step 2: Study in the 'no change-point' situation.** We remind that $\mathcal{H}_0$ stands for elements $(l, r)$ such that there is no change-point in $[l - r, l + r)$ and that it is defined in (7). Consider $(l, r) \in J_n \cap \mathcal{H}_0$. Note that since $\{\tau_k, k \in [K]\} \cap [l - r, l + r) = \emptyset$, we have $\bar{\theta}_{l,-r} = \bar{\theta}_{l,+r}$ so that

$$ \frac{r}{2} \|\bar{\theta}_{l,-r} - \bar{\theta}_{l,+r}\|^2 = 0, $$

and

$$ r\langle\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle = 0. $$

Moreover we have on $\xi^{(d)}$ that - see Lemma 9

$$ \left| \frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p \right| \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{p \log \left( \frac{n}{r\delta} \right)} + \log \left( \frac{n}{r\delta} \right) \right) \le \sigma^2 x_r^{(d)}, $$

for $\bar{c}_{\text{thresh}} \ge \bar{c}_{\text{conc}}$ - note that $\bar{c}_{\text{conc}} > 0$ is a universal constant. And so

$$ \Psi_{l,r}^{(d)} \le x_r^{(d)}, $$

so that

$$ T_{l,r}^{(d)} = 0, $$

on $\xi^{(d)}$. This concludes the proof of the first part of the proposition.

**Step 3: Study in the 'change-point' situation.** Consider $k \in [K]$ such that $\tau_k$ is a $\kappa$-dense high-energy change-point - see Equation (17). We have

$$ \frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} \right\|^2 \ge \frac{\kappa}{8} L^2 \left( \sqrt{p \log \left( \frac{n}{\bar{r}_k^{(d)} \delta} \right)} + \log \left( \frac{n}{\bar{r}_k^{(d)} \delta} \right) \right). $$

So on $\xi^{(d)}$ choosing $\kappa$ large enough implies that - see Lemma 8

$$ \bar{r}_k^{(d)} \left| \langle \bar{\varepsilon}_{\tau_k, +\bar{r}_k^{(d)}}, \bar{\varepsilon}_{\tau_k, -\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \rangle \right| \le \frac{\bar{r}_k^{(d)}}{4} \left\| \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right\|^2. $$

Moreover we have on $\xi^{(d)}$ that - see Lemma 9

$$ \left| \frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\varepsilon}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\varepsilon}_{\tau_k, -\bar{r}_k^{(d)}} \right\|^2 - \sigma^2 p \right| \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{p \log \left( \frac{n}{\bar{r}_k^{(d)} \delta} \right)} + \log \left( \frac{n}{\bar{r}_k^{(d)} \delta} \right) \right) \le \sigma^2 x_{\bar{r}_k^{(d)}}, $$

for $\bar{c}_{\text{thresh}} \ge \bar{c}_{\text{conc}}$ - note that $\bar{c}_{\text{conc}} > 0$ is a universal constant. Thus on $\xi^{(d)}$, combining the three previous displayed equations implies

$$ \begin{aligned} \Psi_{\tau_k, \bar{r}_k^{(d)}}^{(d)} &\ge \frac{\bar{r}_k^{(d)}}{4\sigma^2} \left\| \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right\|^2 - x_{\bar{r}_k^{(d)}}^{(d)} \\ &\ge \left( \frac{c_0}{16} - \bar{c}_{\text{thresh}} \right) \frac{L^2}{\sigma^2} \left( \sqrt{p \log \left( \frac{n}{\bar{r}_k^{(d)} \delta} \right)} + \log \left( \frac{n}{\bar{r}_k^{(d)} \delta} \right) \right) > x_{\bar{r}_k^{(d)}}^{(d)}, \end{aligned} $$

since $\kappa > 32\bar{c}_{\text{thresh}}$. And so on $\xi^{(d)}$:

$$ T_{\tau_k, \bar{r}_k^{(d)}}^{(d)} = 1. $$

This concludes the proof of the second part of the proposition.
**Step 3: Combination of the two statistics** Let us return to the proof of Proposition 2. To conclude the proof, it suffices to show that if $\tau_k$ is a $\kappa_s$-sparse high-energy change-point – see (11) – for some large enough constant $\kappa_s$, then the result of one of the two preceding propositions holds. This is precisely what the following lemma shows.

**Lemma 3.** There exists a constant $\kappa_s$ such that if $\tau_k$ is a $\kappa_s$-sparse high-energy change-point, then one of the following propositions is true:

* There exists $s \in \mathcal{Z}$ such that $s > \bar{s}_{\bar{\tau}_k^{(s)}}$ and $|U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s)}| > x_{\bar{\tau}_k^{(s)}, s}^{(\text{BJ})}$.

* There exists $s \in \mathcal{Z}$ such that $s \le \bar{s}_{\bar{\tau}_k^{(s)}}$ and $\sum_{s'=1}^s |U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}|^2 > 4x_{\bar{\tau}_k^{(s)}, s}^{(\text{p})}$.

*Proof of Proposition 11.* The first part of the proposition is a simple consequence of the definition together with a union bound.

$$ \mathbb{P} \left[ \max_{(l,r) \in \mathcal{H}_0} T_{l,r}^{(\text{BJ})} = 1 \right] \le \sum_{r \in \mathcal{R}} \sum_{l \in \mathcal{D}_r} \sum_{x \in \mathbb{N}^*} \delta_{x,r}^{(\text{BJ})} \\ \le \sum_{r \in \mathcal{R}} \sum_{l \in \mathcal{D}_r} \frac{\delta r}{|\mathcal{D}_r|n} \le \sum_{r \in \mathcal{R}} \frac{\delta r}{n} \le \delta. $$

We focus on the second part of the proposition. To ease the reading, we introduce some notation

$$ \gamma_{x,r} = \bar{Q}^{-1}[\delta_{x,r}, p, 2\bar{\Phi}(x)]; \quad \eta_{x,r,s} = \bar{Q}^{-1}[1 - \delta_{x,r}/2, p - s, 2\bar{\Phi}(x)]; \\ \psi_{x,r,s}(u) = \bar{Q}^{-1}[1 - \delta_{x,r}/2, s, \bar{\Phi}(x - u) + \bar{\Phi}(x + u)], $$

for $x \ge 0$. In fact, $\gamma_{x,r}$ is the threshold of the statistics $N_{x,l,r}$. As for $\eta_{x,r,s}$, it stands for the contribution to $N_{x,l,r}$ of the $(p-s)$ coordinates $i$ such that $\theta_{.,i}$ is constant over $[l-r, l+r)$. Finally, $\psi_{x,r,s}(u)$ stands for the contribution to $N_{x,l,r}$ of the $s$ coordinates $i$ whose population CUSUM statistics $U_{l,r,i}$ is equal to $u$.

**Lemma 4.** Consider any $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$. If for some positive integers $s$ and $x$ we have

$$ \psi_{x,r,s}(|U_{l,r,(s)}|) > \gamma_{x,r} - \eta_{x,r,s}, \quad (35) $$

then $\mathbb{P}[T_{l,r}^{(\text{BJ})} = 1] \ge 1 - \delta_{x,r}$.

Denote $\mathcal{H}[\theta]$ the collection of $(l,r)$ with $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$ that satisfy Condition (35) for some $s$ and some $x$. We easily deduce from the above Lemma together with an union bound that, with probability higher than $1 - \delta$, $T_{l,r}^{(\text{BJ})} = 1$ for all $(l,r) \in \mathcal{H}[\theta]$.

Let us now provide a more explicit characterisation of $\mathcal{H}[\theta]$ with the following Lemma.

**Lemma 5.** For any $1 \le s \le p$ and $r \in \mathcal{R}$ define $x_s$ by

$$ x_s := x_{r,s}^{(\text{BJ})} = \min \left\{ x \ge 2 : \bar{\Phi}(x) \le \frac{s^2}{28^2 p \log(2\alpha_{x,r}^{-1})} \right\}. $$
Proof of Lemma 8. Let $k$ be in $[K]$ and such that Equation (17) is satisfied. Remark that $\theta$ is constant on $[\tau_k - \bar{r}_k^{(d)}, \tau_k)$ and is equal to $\mu_{k-1}$, and is also constant on $[\tau_k, \tau_k + \bar{r}_k^{(d)})$ and is equal to $\mu_k$. First, from the definition of the $\psi_2$-norm of a vector, there exists a universal constant $C > 0$ such that for all $k = 1...K$,

$$ \begin{aligned} \left\| \bar{r}_k^{(d)} \left\langle \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}}, -\bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}}, -\bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right\rangle \right\|_{\psi_2} &\le \bar{r}_k^{(d)} \left\| \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}}, -\bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}} \right\|_{\psi_2} |\mu_k - \mu_{k-1}| \\ &\le C \sqrt{\bar{r}_k^{(d)}} \|\epsilon_1\|_{\psi_2} |\mu_k - \mu_{k-1}| \\ &\le C \sqrt{\bar{r}_k^{(d)}} L |\mu_k - \mu_{k-1}| \\ &\le C L \sqrt{r_k \Delta_k^2} . \end{aligned} $$

Thus by definition of sub-Gaussianity, for all $t > 0$,

$$ \mathbb{P} \left( \bar{r}_k^{(d)} \left| \left\langle \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}}, -\bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}}, -\bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right\rangle \right| \ge t \right) \le \exp \left( -c \frac{t^2}{L^2 r_k \Delta_k^2} \right), $$

for some constant $c > 0$. Finally we apply the concentration inequality to $t = \frac{r_k \Delta_k^2}{4}$ - remembering that $\tau_k$ is a $\kappa$-dense high-energy change-point in the sense of Equation (17) - and sum over $k$ to obtain a union bound over $\xi_2^c$:

$$ \begin{aligned} \mathbb{P}(\xi_2^c) &\le \sum_{k=1}^K \mathbb{P} \left( r \left| \left\langle \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}}, -\bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}}, -\bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right\rangle \right| \ge \frac{r_k \Delta_k^2}{4} \right) \\ &\le \sum_{k=1}^K \exp \left( -c \frac{r_k \Delta_k^2}{16L^2} \right) \\ &\le \sum_{k=1}^K \exp \left( -c' \kappa \log \left( \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right) \right) \quad (c' = c/16) \\ &\le \sum_{k=1}^K \left( \frac{\bar{r}_k^{(d)}}{n} \right)^{c'\kappa} \delta^{c'\kappa} \\ &\le \delta, \end{aligned} $$

where the last inequality comes from the fact that $\sum_{k=1}^K \bar{r}_k^{(d)} \le n$ and the fact that $\kappa$ is chosen large enough so that $c'\kappa \ge 1$. $\square$

Proof of Lemma 9. Remark first that by homogeneity, we can assume without loss of generality that $L = 1$. To provide a proof, we will use the Hanson-Wright inequality in high dimension, which is a way to control quadratic forms of the noise.

**Lemma 10 (Hanson-Wright inequality in high dimension).** Let $A = (a_{ij})$ be a $m \times m$ matrix and $\varepsilon_1, \dots, \varepsilon_m$ be sub-Gaussian vectors of dimension $p$ with norm smaller than 1. Then

$$ \mathbb{P} \left( \left| \sum_{1 \le i,j \le m} a_{i,j} \langle \varepsilon_i, \varepsilon_j \rangle - \mathbb{E} \left[ \sum_{1 \le i,j \le m} a_{i,j} \langle \varepsilon_i, \varepsilon_j \rangle \right] \right| \ge t \right) \le 2 \exp \left( -c \min \left( \frac{t^2}{p \|A\|_F^2}, \frac{t}{\|A\|_{op}} \right) \right), $$

where $c$ is an absolute constant, $\|A\|_F^2 = \sum_{i,j} a_{i,j}^2$ is the squared Frobenius norm of $A$ and $\|A\|_{op}$ is the operator norm of $A$.
We have $\psi_{x,s,r,s}(t_s) > \gamma_{x,s,r} - \eta_{x,s,r,s}$ provided that

$$s \geq \frac{28}{3} \log(2\delta_{x,s,r}^{-1}) . \qquad (36)$$

Combining Lemma 5 and Lemma 4, we conclude the proof of the proposition. □

*Proof of Lemma 4.* Denote $S$ any subset of size $s$, such that for any $j \in S$, $|U_{l,r,j}| \geq |U_{l,r,(s)}|$. Define

$$N_{x,l,r}^{(1)} = \sum_{i=1}^{p} \mathbf{1}_{i \notin S} \mathbf{1}_{|C_{l,r,i}| > x}, \quad N_{x,l,r}^{(2)} = \sum_{i=1}^{p} \mathbf{1}_{i \in S} \mathbf{1}_{|C_{l,r,i}| > x}$$

Since, for any $x > 0$, the function $u \mapsto \bar{\Phi}(x+u) + \bar{\Phi}(x-u)$ is non-decreasing. As a consequence, the random variable $N_{x,l,r}^{(1)}$ is stochastically dominated by a Binomial distribution with parameters $(p-s, 2\bar{\Phi}(x))$. Besides, $N_{x,l,r}^{(2)}$ is stochastically dominated by a Binomial distribution with parameters $(s, \bar{\Phi}(x+|U_{l,r,(s)}|) + \bar{\Phi}(x - |U_{l,r,(s)}|))$. We obtain

$$\begin{aligned}
\mathbb{P}[T_{l,r}^{(BJ)} = 0] & \leq \mathbb{P}[N_{x,l,r} \leq \gamma_{x,r}] \leq \mathbb{P}[N_{x,l,r}^{(1)} < \eta_{x,r,s}] + \mathbb{P}[N_{x,l,r}^{(2)} \leq \gamma_{x,r} - \eta_{x,r,s}] \\
& \leq \frac{\delta_{x,r}}{2} + 1 - \bar{Q}[\gamma_{x,r} - \eta_{x,r,s}, s, \bar{\Phi}(x - |U_{l,r,(s)}|) + \bar{\Phi}(x + |U_{l,r,(s)}|)] \\
& \leq \frac{\delta_{x,r}}{2} + \frac{\delta_{x,r}}{2} \leq \delta_{x,r} . \quad \square
\end{aligned}$$

*Proof of Lemma 5.* From Bernstein inequality, we deduce that, for any positive integers $s$ and $x$,

$$\begin{aligned}
\gamma_{x,s} & \leq 2p\bar{\Phi}(x) + 2\sqrt{p\bar{\Phi}(x) \log(\delta_{x,r}^{-1})} + \frac{2}{3}\log(\delta_{x,r}^{-1}) ; \\
\eta_{x,r,s} & \geq 2(p-s)\bar{\Phi}(x) - 2\sqrt{p\bar{\Phi}(x) \log(2\delta_{x,r}^{-1})} - \frac{2}{3}\log(2\delta_{x,r}^{-1}) .
\end{aligned}$$

Hence, it follows that

$$\gamma_{x,s} - \eta_{x,r,s} \leq 2s\bar{\Phi}(x) + 4\sqrt{p\bar{\Phi}(x) \log(2\delta_{x,r}^{-1})} + \frac{4}{3}\log(2\delta_{x,r}^{-1}) .$$

For $u = x$, we have $\bar{\Phi}(x-u) + \bar{\Phi}(x+u) \geq \bar{\Phi}(0) = 1/2$ and we derive from Bernstein inequality that

$$\psi_{x,r,s}(t) \geq \frac{s}{2} - \sqrt{s \log(2\delta_{x,r}^{-1})} - \frac{2}{3} \log(2\delta_{x,r}^{-1}) .$$

As a ce, $\psi_{x,r,s}(t) > \gamma_{x,s} - \eta_{x,r,s}$ as long as

$$s(1 - 4\bar{\Phi}(x)) > 12\sqrt{p\bar{\Phi}(x) \log(2\delta_{x,r}^{-1})} + \frac{12}{3}\log(2\delta_{x,r}^{-1}) .$$
The proof of this lemma relies on the classical Hanson Wright inequality that is proved for example in [35]. To prove the proposition, we will use a chaining argument. To this end, we let $(N_u)_{u \ge 0}$ be the following covering sets of $J_n$:

$$N_u = J_n \cap \{i 2^{\kappa_1 - u}, i \in \mathbb{N}\}^2,$$

where we define $\kappa_1 = \lfloor \log_2(n) \rfloor$, and more generally $\kappa_r = \lfloor \log_2(n/r) \rfloor$ for $r = 1, \dots, n$. Remark that the higher $u$ is, the finer the covering set $N_u$ is, and $N_{\kappa_1} = J_n$. For all $u \ge 0$, we define the projection map $\pi_u$ from $J_n$ to $N_u$ by

$$\pi_u(l, r) = \arg \min_{(\hat{l}, \hat{r}) \in N_u} (|\hat{l} - l| + |\hat{r} - r|) .$$

In the sequel, we will use the slight abuse of notation for $(l, r)$ in $J_n$:

$$(l_u, r_u) = \pi_u(l, r) .$$

A useful lemma to control the distance between $(l, r)$ and its projection $(l_u, r_u)$ can be stated as follows.

**Lemma 11.** For all $(l, r) \in J_n$ and $0 \le u \le \kappa_1$ such that $N_u \ne \emptyset$,

$$|l_u - l| + |r_u - r| \le 2 \frac{n}{2u} .$$

Let $(l, r) \in J_n$. From now on, we write $\varepsilon_{l,+r} = r\bar{\varepsilon}_{l,+r} = \sum_{t=l}^{l+r-1} \varepsilon_t$ and $\varepsilon_{l,-r} = r\bar{\varepsilon}_{l,-r}$. The chaining relation can be written as

$$\frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p = \frac{1}{2r} \left[ \|\varepsilon_{l_{\kappa_r},+r_{\kappa_r}} - \varepsilon_{l_{\kappa_r},-r_{\kappa_r}}\|^2 - 2r_{\kappa_r} \sigma^2 p \right] \\ + \frac{1}{2r} \sum_{v=\kappa_r}^{\kappa_1} \left[ \|\varepsilon_{l_{v+1},+r_{v+1}} - \varepsilon_{l_{v+1},-r_{v+1}}\|^2 - \|\varepsilon_{l_v,+r_v} - \varepsilon_{l_v,-r_v}\|^2 - 2(r_{v+1} - r_v)\sigma^2 p \right].$$

Remark that the chaining summation starts at scale $u = \kappa_r$ so that $\frac{n}{2u} \asymp r$. The first term of the chaining is an approximation on the grid at level $u$ of the term $\frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p$. The second term can be viewed as an error term, and we will show that it is of the same order as the first term. Since both terms are quadratic forms of the noise, we will need an upper bound on the norm of their corresponding matrix to apply the Hanson Wright inequality - see Lemma 10.

**Lemma 12 (Control of the Frobenius norm).** Let $(l, r)$ be a fixed element of $J_n$. Let A and B be the corresponding matrix of the two following quadratic form:

$$\varepsilon^T A \varepsilon = \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 \quad \text{and} \quad \varepsilon^T B \varepsilon = \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - \|\varepsilon_{l',+r'} - \varepsilon_{l',-r'}\|^2 .$$

Then

$$\|A\|_F^2 \le 16r^2 \\ \|B\|_F^2 \le 24 (|l - l'| + |r - r'|) (r + r' + |l - l'|) .$$

The following lemma aims at upper bounding the first term of the chaining relation with high probability.
Provided that we take $x \ge 2$, the latter holds if

$$s \ge 14\sqrt{p\bar{\Phi}(x)\log(2\delta_{x,r}^{-1})} + \frac{14}{3}\log(2\delta_{x,r}^{-1}) \quad (37)$$

In view of the definition (32) of $x_s$, we have $14\sqrt{p\bar{\Phi}(x_s)\log(2\delta_{x,s,r}^{-1})} \le s/2$. Hence, under Condition (33), (37) holds and we conclude that $\psi_{x_s,r,s}(x_s) > \gamma_{x_s,s} - \eta_{x_s,r,s}$. □

**Proof of Proposition 12.** The following lemma ensures that the partial norm test returns 0 with high probability jointly at all positions where there is no change-point. We write $\bar{C}_p^s$ for the set of all combinations of $s$ indices taken from $[p]$.

**Lemma 6** (concentration of the pure noise for the second sparse statistic). If $1 \ge \delta > 0$, then the event

$$\xi_1^{(p)} = \left\{ \forall r \in \mathcal{R}, l \in \mathcal{D}_r, s \in \mathcal{Z} \max_{S \in \bar{C}_p^s} \sum_{i \in S} \frac{r}{2\sigma^2} (\bar{\varepsilon}_{l,+r,i} - \bar{\varepsilon}_{l,-r,i})^2 \le x_{r,s}^{(p)} \right\}$$

holds with probability higher than $1 - \delta$.

We now state the following lemma, which ensures that the partial norm test returns 1 with high probability jointly at relevant positions which are close to a change-point.

**Lemma 7** (concentration on the change-points for the second sparse statistic). We write $\bar{\mathcal{K}}^*$ for the set of $k \in [K]$ such that

$$\bullet \ s_k \le \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}$$

$$\bullet \ \sum_{s'=1}^{s} \left| U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')} \right|^2 \ge 4x_{\bar{\tau}_k^{(s)}, s}^{(p)}$$

If $1 \ge \delta > 0$, the event

$$\xi_2^{(p)} = \left\{ \forall k \in \bar{\mathcal{K}}^* : \exists s \in \mathcal{Z} \text{ s.t. } \Psi_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, s}^{(p)} > x_{\bar{\tau}_k^{(s)}, s}^{(p)} \right\},$$

holds with probability higher than $1 - \delta$.

Lemmas 6 and 7 directly imply the result of the proposition. □

**Proof of Lemma 6.** Let $r \in \mathcal{R}$, $l \in \mathcal{D}_r$, $s \le \bar{s}_r$ and $S \in \bar{C}_p^s$. Let $\delta > 0$, $\delta_{r,s} = (\frac{r}{n})^2 (\frac{s}{2ep})^s \delta$. Since $\sqrt{\frac{r}{2\sigma^2}} (\bar{\varepsilon}_{l,+r,i} - \bar{\varepsilon}_{l,-r,i})$ follows a $\mathcal{N}(0, 1)$ distribution for all $l, r, i$, we have by Bernstein's inequality that with probability larger than $1 - \delta_{r,s}$,

$$\sum_{i \in S} (\bar{\varepsilon}_{l,+r,i} - \bar{\varepsilon}_{l,-r,i})^2 \le s + 2\sqrt{s \log\left(\frac{1}{\delta_{r,s}}\right)} + \log\left(\frac{1}{\delta_{r,s}}\right)$$
**Lemma 13.** There exists a constant $C_N$ such that for all $n$, the event

$$ \xi_N^{(d)} = \bigcap_{u \ge 0} \bigcap_{(l,r) \in N_u} \left\{ \left| \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - 2r\sigma^2p \right| \le C_N r \left( \sqrt{p\log(2^u\delta^{-1})} + \log(2^u\delta^{-1}) \right) \right\} . $$

holds with probability higher than $1 - \delta$.

For $u = \kappa_r$, $(l_u, r_u) \in N_u$ Lemma 11 gives $r_u \le r + 2\frac{n}{2^u} \le 3\frac{n}{2^u}$. Consequently, on the event $\xi_N^{(d)}$, we obtain

$$ \left| \frac{1}{2r} \| \varepsilon_{l_{\kappa_r},+r_{\kappa_r}} - \varepsilon_{l_{\kappa_r},-r_{\kappa_r}} \|^2 - \frac{r_{\kappa_r}}{r} \sigma^2 p \right| \le C'_N \left( \sqrt{p \log \left( \frac{n}{r\delta} \right)} + \log \left( \frac{n}{r\delta} \right) \right), $$

for $C'_N$ a large absolute constant. To upper bound the second term, we use the following lemma :

**Lemma 14.** For all $(l, r)$ and $(l', r')$ in $J_n$, set

$$ \xi_{\Delta,v}^{(d)}(l,r,l',r') = \left\{ \left| \|\varepsilon_{l',+r'} - \varepsilon_{l',-r'}\|^2 - \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - 2(r' - r)\sigma^2 p \right| \le C_{\Delta} \sqrt{\frac{rn}{2^v}} \left( \sqrt{p \log (2^v \delta^{-1})} + \log (2^v \delta^{-1}) \right) \right\}. $$

There exists a constant $C_\Delta$ such that, for all $n$, the event

$$ \xi_{\Delta}^{(d)} = \bigcap_{v \ge 0} \left\{ \xi_{\Delta,v}^{(d)}(l,r,l',r') \text{ holds for all } ((l,r), (l',r')) \in N_v \times N_{v+1} \text{ s.t. } |l-l'| + |r-r'| \le 3 \frac{n}{2^v} \right\}. $$

holds with probability higher than $1 - \delta$.

For $v \ge \kappa_r$, $((l_v, r_v), (l_{v+1}, r_{v+1})) \in N_v \times N_{v+1}$ and by Lemma 11,

$$ \begin{aligned} |r_v - r_{v+1}| + |l_v - l_{v+1}| &\le |r_v - r| + |l_v - l| + |r - r_{v+1}| + |l - l_{v+1}| \\ &\le 3 \frac{n}{2^v}. \end{aligned} $$

Therefore, on the event $\xi_\Delta^{(d)}$,

$$ \begin{aligned} & \left| \frac{1}{2r} \sum_{v=\kappa_r}^{\kappa_1-1} \left[ \| \varepsilon_{l_{v+1},+r_{v+1}} - \varepsilon_{l_{v+1},-r_{v+1}} \|^2 - \| \varepsilon_{l_v,+r_v} - \varepsilon_{l_v,-r_v} \|^2 - 2(r_{v+1} - r_v)\sigma^2 p \right] \right| \\ &\le C_\Delta \frac{1}{2r} \sum_{v=\kappa_r}^{\kappa_1-1} \sqrt{\frac{r_v n}{2^v}} \left( \sqrt{p \log (2^v \delta^{-1})} + \log (2^v \delta^{-1}) \right) \\ &\le C'_\Delta \sum_{v' \ge 0} \frac{1}{2^{v'}} \left( \sqrt{p \log \left( \frac{n 2^{v'}}{r \delta} \right)} + \log \left( \frac{n 2^{v'}}{r \delta} \right) \right) \\ &\le C''_\Delta \left( \sqrt{p \log \left( \frac{n}{r \delta} \right)} + \log \left( \frac{n}{r \delta} \right) \right), \end{aligned} $$

where $C'_\Delta, C''_\Delta$ are large absolute constants. Hence, letting $\bar{c}_{\text{conc}} = C'_N + C''_\Delta$ we obtain

$$ \xi_N^{(d)} \cap \xi_\Delta^{(d)} \subset \xi_2^{(d)}, $$

which must be of probability higher than $1 - 2\delta$.

<figure><img src="image_14.png" /></figure>
$$ 
\begin{aligned}
&\le 2 \left( s + \log \left( \frac{1}{\delta_{r,s}} \right) \right) \\
&= 2 \left( s + s \log \left( \frac{2ep}{s} \right) + \log \left( \frac{n^2}{r^2\delta} \right) \right) \\
&\le 4 \left( s \log \left( \frac{2ep}{s} \right) + \log \left( \frac{n}{r\delta} \right) \right) .
\end{aligned}
$$

Since the number of such $S$ is smaller than $(\frac{ep}{s})^s$, a union bound gives

$$ 
\begin{aligned}
\mathbb{P} \left( \xi_1^{(p)} \right) &\ge 1 - \sum_{r \in \mathbb{R}} \sum_{l \in \mathcal{D}_r} \sum_{s \in \mathcal{Z}} |\bar{C}_p^s| \left( \frac{s}{2ep} \right)^s \left( \frac{r}{n} \right)^2 \delta \\
&\ge 1 - \sum_{r \in \mathbb{R}} \sum_{l \in \mathcal{D}_r} \sum_{s \in \mathcal{Z}} \left( \frac{1}{2} \right)^s \left( \frac{r}{n} \right)^2 \delta \\
&\ge 1 - \delta,
\end{aligned}
$$

which yields the result.

<figure><img src="image_10.png" /></figure>

*Proof of Lemma 7.* Let $k \in \bar{\mathcal{K}}^*$, and $s \in \mathcal{Z}$ such that

$$ \sum_{i=1}^{s} U_{\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)}, (i)}^{2} > 4x_{\bar{r}_k^{(s)}, s}^{(p)} . \qquad (38) $$

To ease the reading, we write $(\tau, r) = (\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)})$. Then on the event $\xi_1^{(p)}$ which holds with probability $1 - \delta$, we have

$$ 
\begin{aligned}
\Psi_{\tau,r,s}^{(p)} &= \max_{S \in \bar{C}_p^s} \sum_{i \in S} \frac{r}{2\sigma^2} (\bar{\theta}_{\tau,+r,i} + \bar{\varepsilon}_{\tau,+r,i} - \bar{\theta}_{\tau,-r,i} - \bar{\varepsilon}_{\tau,-r,i})^2 \\
&\ge \max_{S \in \bar{C}_p^s} \sum_{i \in S} \frac{1}{2} U_{\tau,r,i}^2 - \frac{r}{2\sigma^2} (\bar{\varepsilon}_{\tau,+r,i} - \bar{\varepsilon}_{\tau,-r,i})^2 \\
&> 2x_{r,s}^{(p)} - x_{r,s}^{(p)} \\
&= x_{r,s}^{(p)},
\end{aligned}
$$

where in the second inequality, we used the fact that $(a+b)^2 \ge \frac{1}{2}a^2 - b^2$ for all $a, b \in \mathbb{R}$.

<figure><img src="image_11.png" /></figure>

*Proof of Lemma 3.* First remark that there exists a large enough constant $C$ such that for all $r, s \ge 1$,

$$ 
\begin{aligned}
(x_{r,s}^{(\text{BJ})})^2 &\le C \log \left( \frac{ep}{s^2} \log \left( \frac{n}{r\delta} \right) \right) \\
\bar{s}_r &\le C \log \left( \log \left( \frac{ep}{\bar{s}_r^2} \right) \frac{n}{r\delta} \right),
\end{aligned}
$$

where we recall that $\bar{s}_r$ is defined by (33) and $x_{r,s}^{(\text{BJ})}$ by (32). These two inequalities come from the fact that for all $t \ge 2$ and all $A > 0$, if $t \le A+\log(t)$ then $t \le 2A$.
Proof of Lemma 11. Since the mesh of the grid $N_u$ is equal to $2^{\kappa_1 - u} \le \frac{n}{2^u}$, there exists $(\tilde{l}, \tilde{r}) \in N_u$ such that

$$|l - \tilde{l}| \le \frac{n}{2^u} \quad \text{and} \quad |r - \tilde{r}| \le \frac{n}{2^u}.$$

□

Proof of Lemma 12. Let us write

$$\varepsilon^T A \varepsilon = \sum_{l-r \le i,j < l+r} a_{ij} \langle \varepsilon_i, \varepsilon_j \rangle \quad \text{and} \quad \varepsilon^T B \varepsilon = \sum_{m_1 \le i,j < m_2} b_{ij} \langle \varepsilon_i, \varepsilon_j \rangle,$$

where $m_1 = \min(l-r, l'-r')$, $m_2 = \max(l+r, l'+r')$. Remark that for all $i, j$ in $[l-r, l+r)$, $a_{ij} \le 2$. This gives the first inequality.

For the second inequality, assume without loss of generality that $l \le l'$. As for the first inequality, $b_{ij} \le 2$ for all $i, j \in [m_1, m_2)$. Remark that $b_{ij}$ can be non zero only if $(i, j)$ is in one of the following cases :

1. $i$ or $j$ is in $[\min(l+r, l'+r'), \max(l+r, l'+r'))$

2. $i$ or $j$ is in $[\min(l-r, l'-r'), \max(l-r, l'-r'))$

3. $i$ or $j$ is in $[l, l')$.

Hence there is at most $(4(|l-l'| + |r-r'|) + 2|l-l'|)(r+r' + |l-l'|)$ non zero $b_{ij}$, and we obtain the second inequality. □

Proof of Lemma 13. The probability of $(\xi_N^{(d)})^c$ can be written as :

$$\mathbb{P}((\xi_N^{(d)})^c) = \mathbb{P}\left(\exists u \ge 0, \exists (l,r) \in N_u \text{ s.t. } r \le 3\frac{n}{2^u} \text{ and } \left|\|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - 2r\sigma^2p\right| \le C_N r \left(\sqrt{p\log(2^u\delta^{-1})} + \log(2^u\delta^{-1})\right)\right).$$

First, fix $u \ge 0$ and $(l, r) \in N_u$ such that $r \le 3\frac{n}{2^u}$.

Applying the first inequality of Lemma 12 and the Hanson-Wright inequality - see Lemma 10, we obtain for all $t \ge 0$

$$\mathbb{P}\left(\left|\|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - 2r\sigma^2p\right| \ge t\right) \le 2\exp\left(-c\min\left(\frac{t^2}{pr^2}, \frac{t}{r}\right)\right),$$

where $c$ is an absolute constant. Choosing

$$t = C_N r \left( \sqrt{p \log (2^u \delta^{-1})} + \log (2^u \delta^{-1}) \right),$$

we obtain

$$\mathbb{P}\left(\left|\|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - 2r\sigma^2p\right| \ge C_N r \left(\sqrt{p \log (2^u \delta^{-1})} + \log (2^u \delta^{-1})\right)\right) \le C \left(\frac{1}{2^u}\right)^{cC_N} \delta^{cC_N},$$
Assume that for all $s' = \bar{s}_{\bar{\tau}_k^{(s)}} + 1, \dots, s_k$ we have $|U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}| < x_{\bar{\tau}_k^{(s)}, s'}^{(\text{BJ})}$. To ease the notation, we write $\bar{s} = \bar{s}_{\bar{\tau}_k^{(s)}} \wedge s_k$ and in what follows we prove that $\sum_{s'=1}^{\bar{s}} |U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}|^2 > 4x_{\bar{\tau}_k^{(s)}, \bar{s}}^{(\text{p})}$ when $\kappa_s$ is a large enough constant. We have

$$ \sum_{s'=\bar{s}_{\bar{\tau}_k^{(s)}}+1}^{s_k} U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}^2 \le C_1 \sum_{i=0}^{\lfloor \log(s_k) \rfloor} 2^i \log \left( \frac{ep}{2^{2i}} \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right) \\ \le C_1 s_k \log \left( 2e \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right) + C_1 \sum_{i=0}^{\lfloor \log(s_k) \rfloor} 2^i \log \left( \frac{p}{2^{2(i+1)}} \right), $$

for some universal constant $C_1$. To handle the second term remark that since $x \mapsto \log(\frac{p}{x^2})$ is decreasing, we have

$$ \sum_{i=0}^{\lfloor \log(s_k) \rfloor} 2^i \log \left( \frac{p}{2^{2(i+1)}} \right) \le \int_1^{2s_k} \log \left( \frac{p}{x^2} \right) dx \\ = 2s_k \log \left( \frac{p}{(2s_k)^2} \right) + 2s_k - 1 \\ \le 2s_k \log \left( \frac{p}{s_k^2} \right), $$

and thus

$$ \sum_{s'=\bar{s}_{\bar{\tau}_k^{(s)}}+1}^{s_k} U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}^2 \le 2C_1 s_k \log \left( 2e \frac{p}{s_k^2} \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right), $$

which finally gives

$$ \sum_{s'=1}^{\bar{s}} U_{\bar{\tau}_k^{(s)}, \bar{\tau}_k^{(s)}, (s')}^2 \ge \frac{9}{16} \bar{r}_k^{(s)} \Delta_k^2 - 2C_1 s_k \log \left( \frac{2ep}{s_k^2} \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right) \\ \ge 4x_{\bar{\tau}_k^{(s)}, \bar{s}}^{(\text{p})}. $$

In the first inequality we used the fact that

$$ |\bar{\tau}_k^{(s)} - \tau_k| \le \frac{1}{4} \bar{r}_k^{(s)}, $$

so that for all $i$,

$$ \left| \bar{\theta}_{\bar{\tau}_k^{(s)}, +\bar{r}_k^{(s)}, i} - \bar{\theta}_{\bar{\tau}_k^{(s)}, -\bar{r}_k^{(s)}, i} \right| = \frac{1}{\bar{r}_k^{(s)}} \left| (\bar{r}_k^{(s)} + \bar{\tau}_k^{(s)} - \tau_k) \mu_{k,i} - (\bar{r}_k^{(s)} - \bar{\tau}_k^{(s)} + \tau_k) \mu_{k-1,i} \right| $$
where c, C are absolute constants. Since the cardinal of $N_u$ is upper bounded by $2^{2u+2}$, A union bound on each $N_u$ for each $u \ge 0$ gives :

$$ 
\begin{aligned}
\mathbb{P}((\xi_N^{(d)})^c) &\le \sum_{u \ge 0} C |N_u| \left(\frac{1}{2^u}\right)^{cC_N} \delta^{cC_N} \\
&\le \sum_{u \ge 0} 4C \left(\frac{1}{2^u}\right)^{2-cC_N} \delta^{cC_N},
\end{aligned}
$$

which is convergent. For $C_N$ large enough, we obtain $\mathbb{P}(\xi_N^c) \le 1 - \delta$. $\square$

Proof of Lemma 14.

$$ \mathbb{P}((\xi_{\Delta}^{(d)})^c) = \mathbb{P}(\exists v \ge 0, \exists((l, r), (l', r')) \in N_v \times N_{v+1} \text{ s.t. } |l-l'| + |r-r'| \le 4\frac{n}{2^v} \text{ and } (\xi_{\Delta,v}^{(d)}(l, r, l', r'))^c \text{ holds}) . $$

First fix $v \ge 0$ and $((l, r), (l', r')) \in N_v \times N_{v+1}$. Remark that by definition of $N_v$,

$$ r \ge \frac{n}{2^{v+1}} . $$

Thus,

$$ r + r' + |l - l'| \le 2r + |l - l'| + |r - r'| \le 10r . $$

Then by Lemma 12, letting $B$ be the matrix such that $\varepsilon^T B \varepsilon = \|\varepsilon_{l',r'} - \varepsilon_{l',-r'}\|^2 - \|\varepsilon_{l,r} - \varepsilon_{l,-r}\|^2$, we obtain

$$ \|B\|^2 \le \|B\|_F^2 \le 40r \frac{n}{2^v} . $$

Thus, by the Hanson Wright inequality - see Lemma 10,

$$ \mathbb{P}(|\varepsilon^T B_u \varepsilon - \mathbb{E}[\varepsilon^T B_u \varepsilon]| \ge t) \le 2 \exp \left( -c \min \left( \frac{2^v}{pmr} t^2, \sqrt{\frac{2^v}{nr}} t \right) \right) . $$

From now on, we choose

$$ t = C_{\Delta} \sqrt{\frac{rn}{2^v}} \left( \sqrt{p \log (2^v \delta^{-1})} + \log (2^v \delta^{-1}) \right) . $$

There are at most $2^{4v+6}$ elements in $N_v \times N_{v+1}$. Therefore, a union bound on $v \ge 0$ and $N_v \times N_{v+1}$ gives

$$ 
\begin{aligned}
\mathbb{P}((\xi_{\Delta}^{(d)})^c) &\le \sum_{u \ge 0} 2|N_v \times N_{v+1}| (2^v)^{-cC_{\Delta}} \delta^{cC_{\Delta}} \\
&\le \sum_{u \ge 0} 2^7 (2^v)^{4-cC_{\Delta}} \delta^{cC_{\Delta}} \\
&\le C \delta^{cC_{\Delta}},
\end{aligned}
$$

where the last inequality holds if $C_{\Delta}$ is large enough, for c, C universal constants. $\square$
$$ \geq \left( 1 - \frac{|\bar{\tau}_k^{(s)} - \tau_k|}{\bar{r}_k^{(s)}} \right) |\mu_{k,i} - \mu_{k-1,i}| > \frac{3}{4} |\mu_{k,i} - \mu_{k-1,i}| = \frac{3}{4} U_{k,i} . $$

In the second inequality, we used the fact that

• $8\bar{r}_k^{(s)}\Delta_k^2 \geq \kappa_s\sigma^2 \left( s_k \log \left( \frac{p}{s_k^2} \log \left( \frac{n}{\bar{r}_k^{(s)}\delta} \right) \right) + \log \left( \frac{n}{\bar{r}_k^{(s)}\delta} \right) \right)$ for a large enough constant $\kappa_s$ (see (11)),

• $x \mapsto x \log\left(\frac{ep}{x^2}\right)$ is increasing for $x \le p$, so that $s_k$ can be replaced by $\bar{s}$,

• $\bar{s} \le C \log\left(\log\left(\frac{ep}{\bar{s}^2}\right) \frac{n}{r\delta}\right)$.

This concludes the proof of the lemma.

<figure><img src="image_12.png" /></figure>

### B.2.3. Proof of Corollary 2

Let $\xi^{(d)}$ and $\xi^{(s)}$ be two events such that Proposition 1 and Proposition 2 hold respectively with constants $\kappa_d$, $\kappa_s$ and with probability $1-2\delta$ and $1-4\delta$, and write $\xi = \xi^{(d)} \cap \xi^{(s)}$. From now on, we work on the event $\xi$, which holds with probability $1-6\delta$. Let us choose $c_0 \ge 2(\kappa_d \vee \kappa_s)$ in (8). For all $k$ such that $\tau_k$ is a $c_0$-high-energy change-point, define

$$ (\bar{\tau}_k, \bar{r}_k) = \begin{cases} (\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)}) & \text{if } s_k > \sqrt{p \log \left( \frac{n}{r_k \delta} \right)} \\ (\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)}) & \text{if } s_k \le \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}. \end{cases} $$

$(\bar{r}_k, \bar{\tau}_k)$ is well defined. Indeed, If $s_k \le \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}$ then

$$ s_k \log \left( 1 + \frac{\sqrt{p}}{s_k} \sqrt{\log \left( \frac{n}{r_k \delta} \right)} \right) + \log \left( \frac{n}{r_k \delta} \right) \\ \geq \frac{1}{2} \left( s_k \log \left( \frac{p}{s_k^2} \log \left( \frac{n}{r_k \delta} \right) \right) + \log \left( \frac{n}{r_k \delta} \right) \right) . $$

Now if $s_k \ge \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}$ then using $\log(1+x) \ge \frac{x}{2}$ for $x \in [0,1]$ we have

$$ s_k \log \left( 1 + \frac{\sqrt{p}}{s_k} \sqrt{\log \left( \frac{n}{r_k \delta} \right)} \right) + \log \left( \frac{n}{r_k \delta} \right) \ge \frac{1}{2} \left( \sqrt{p \log \left( \frac{n}{r_k \delta} \right)} + \log \left( \frac{n}{r_k \delta} \right) \right) . $$

According to Theorem 1, it is sufficient to prove that the event $A(\Theta, T, K^*, (\bar{\tau}_k, \bar{r}_k)_{k \in K^*})$ defined in Section 2.3 holds on $\xi$:
### B.3.2 Proof of Proposition 4

**Step 1: Introduction of useful high probability events.** Let $s \le p$ and consider $S \in \bar{C}_p^s$. In what follows and for an vector $u \in \mathbb{R}^p$, we write $u^{(S)}$ for the vector $u$ restricted to the set $S$.

Remark that by a simple computation, the noise can be decomposed as follows:

$$ \frac{r}{2} \left[ \left\| \bar{y}_{l,+r}^{(S)} - \bar{y}_{l,-r}^{(S)} \right\|^2 - \left\| \bar{\theta}_{l,-r}^{(S)} - \bar{\theta}_{l,+r}^{(S)} \right\|^2 \right] - \sigma^2 s \\ = r \langle \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)}, \bar{\theta}_{l,+r}^{(S)} - \bar{\theta}_{l,-r}^{(S)} \rangle + \frac{r}{2} \left\| \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s . $$

The first term written as

$$ r \langle \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)}, \bar{\theta}_{l,+r}^{(S)} - \bar{\theta}_{l,-r}^{(S)} \rangle , $$

is a crossed term between the noise and the mean vector $\theta$. Lemma 8 states that for $l$ equal to a true change-point $\tau_k$, $r$ of order $r_k^*$, and $S$ being the corresponding support of the change-point, it is controlled on event $\xi_1^{(p)}$ with high probability.

**Lemma 15.** For $k \in [K]$, let us write $S_k \subset [K]$ for the support of $\mu_k - \mu_{k-1}$. Assume that $c_0$ is a large enough universal constant. The event

$$ \xi_1^{(p)} := \xi_1^{(p)}(\delta) = \left\{ \forall k \in [K] \text{ s.t. Equation (18) holds for } k, \right. $$

$$ \bar{r}_k^{(d)} \left| \langle \bar{\varepsilon}_{\tau_k, + \bar{r}_k^{(d)}}^{(S_k)} - \bar{\varepsilon}_{\tau_k, - \bar{r}_k^{(s)}}^{(S_k)}, \bar{\theta}_{\tau_k, + \bar{r}_k^{(s)}}^{(S_k)} - \bar{\theta}_{\tau_k, - \bar{r}_k^{(s)}}^{(S_k)} \rangle \right| \le \frac{\bar{r}_k^{(d)}}{4} \left\| \bar{\theta}_{\tau_k, + \bar{r}_k^{(s)}} - \bar{\theta}_{\tau_k, - \bar{r}_k^{(s)}} \right\|^2 \right\} $$

holds with probability higher than $1 - \delta$.

The proof of this lemma follows directly from the one of Lemma 8, restricting the term corresponding to change-point $k$ to $S_k$ - and diminishing the deviation by doing so.

The second term written as

$$ \frac{r}{2} \left\| \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s $$

is a term of pure noise. Lemma 16 states that it is controlled on event $\xi_2^{(p)}(S)$ with high probability.

**Lemma 16.** There exists a constant $\bar{c}_{\text{conc}} > 0$ such that the event

$$ \xi_2^{(p)}(S) := \xi_2^{(p)}(S, \delta) = \left\{ \begin{array}{l} \forall (l, r) \in J_n, \left| \frac{r}{2} \left\| \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s \right| \\ \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{s \log \left( \frac{n}{r\delta} \right)} + \log \left( \frac{n}{r\delta} \right) \right) \end{array} \right\} $$

holds with probability higher than $1 - 2\delta$.

The proof of this lemma is exactly the same as the one of Lemma 9, restricting all vectors to $S$. Set $\delta_s = \delta/(2^s \binom{p}{s})$. Lemma 16 implies that with probability larger than $1 - 2\delta$, $\forall (l, r) \in J_n$, $\forall S \subset [p]$

$$ \left| \frac{r}{2} \left\| \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s \right| \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{s \log \left( \frac{n}{r\delta_s} \right)} + \log \left( \frac{n}{r\delta_s} \right) \right). $$
1. (No false positive): for every $r \in \mathbb{R}$ and $l \in \mathcal{D}_r$, if $\Theta$ is constant on $[l-r, l+r)$ then

$$T_{l,r} = T_{l,r}^{(d)} \lor T_{l,r}^{(s)} = 0,$$

by Proposition 1 and Proposition 2.

2. (High-energy change-point detection): for every $k$ such that $\tau_k$ has $c_0$-high-energy, it holds by definition of $\bar{r}_k^{(d)}$ and $\bar{r}_k^{(s)}$ that

$$4(\bar{r}_k - 1) \leq r_k.$$

Moreover, $T_{\bar{\tau}_k, \bar{r}_k}^{(s)} = 1$ if $(\bar{\tau}_k, \bar{r}_k) = (\bar{\tau}_k^{(d)}, \bar{r}_k^{(d)})$ by Proposition 2 and $T_{\bar{\tau}_k, \bar{r}_k}^{(d)} = 1$ if $(\bar{\tau}_k, \bar{r}_k) = (\bar{\tau}_k^{(s)}, \bar{r}_k^{(s)})$ by Proposition 1.

Theorem 1 ensures that for all $k \in [K]$ such that $\tau_k$ is a $c_0$-high-energy change-point, there exists $k' \in [K]$ such that

$$|\hat{\tau}_{k'} - \tau_k| \leq \bar{r}_k - 1.$$

It remains to show that

$$\bar{r}_k - 1 \leq \frac{r_k^*}{2},$$

where $r_k^*$ is defined by (9). Using $\log(1+x) \geq \frac{x}{2}$ for $x \in [0, 1]$ and $\log(1+x) \geq \log(x)$ for $x \geq 1$ we have

$$8\bar{r}_k \Delta_k^2 \leq 4(\kappa_d \lor \kappa_s) \left[ s_k \log \left( 1 + \frac{\sqrt{p}}{s_k} \sqrt{\log \left( \frac{n}{\bar{r}_k \delta} \right)} \right) + \log \left( \frac{n}{\bar{r}_k \delta} \right) \right],$$

when $\bar{r}_k \geq 2$. Thus $2(\bar{r}_k - 1) \leq r_k^*$ for $c_0 \geq 2(\kappa_d \lor \kappa_s)$. This concludes the proof of Corollary 2.

### B.3. Proofs for sub-Gaussian multivariate change-point detection

We recall that in this section, we work on the complete grid $\mathcal{G}_F = J_n$ defined in Section 2.

#### B.3.1. Proof of Proposition 3

**Step 1: Introduction of useful high probability events** We first introduce two events $\xi_1^{(d)}$ and $\xi_2^{(d)}$ on which the noise can be controlled. Remark that by a simple computation, the noise can be decomposed as follows:

$$\frac{r}{2} \left[ \|\bar{y}_{l,+r} - \bar{y}_{l,-r}\|^2 - \|\bar{\theta}_{l,-r} - \bar{\theta}_{l,+r}\|^2 \right] - \sigma^2 p = r \langle \bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r} \rangle + \frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p.$$
And so since $\binom{p}{s} \le \binom{ep}{s}^s$, we have probability larger than $1 - 2\delta$, $\forall (l, r) \in J_n$, $\forall S \subset [p]$

$$ \left| \frac{r}{2} \left\| \bar{\epsilon}_{l,+r}^{(S)} - \bar{\epsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s \right| \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{s \log\left(\frac{n}{r\delta}\right) + s \log\left(\frac{2ep}{s}\right)} + \log\left(\frac{n}{r\delta}\right) + s \log\left(\frac{2ep}{s}\right) \right) \\ \le 4\bar{c}_{\text{conc}} L^2 \left( \log\left(\frac{n}{r\delta}\right) + s \log\left(\frac{2ep}{s}\right) \right). $$

And so the event

$$ \xi_2^{(p)} := \xi_2^{(p)}(\delta) = \left\{ \begin{array}{l} \forall (l,r) \in J_n, \forall S \subset [p], \left| \frac{r}{2} \left\| \bar{\epsilon}_{l,+r}^{(S)} - \bar{\epsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s \right| \\ \le 4\bar{c}_{\text{conc}} L^2 \left( \log\left(\frac{n}{r\delta}\right) + s \log\left(\frac{2ep}{s}\right) \right) \end{array} \right\} \quad (39) $$

has probability larger than $1 - 2\delta$.

Set now

$$ \xi^{(p)} := \xi_1^{(p)} \cap \xi_2^{(p)}. $$

Note that

$$ \mathbb{P}(\xi^{(p)}) \ge 1 - 3\delta. $$

**Step 2: Study in the ‘no change-point’ situation.** Consider $(l, r) \in J_n$ such that $\{\tau_k, k \in [K]\} \cap [l - r, l + r) = \emptyset$, and $S \subset [p]$. Note that since $\{\tau_k, k \in [K]\} \cap [l - r, l + r) = \emptyset$, we have $\bar{\theta}_{l,-r}^{(S)} = \bar{\theta}_{l,+r}^{(S)}$ so that

$$ \frac{r}{2} \left\| \bar{\theta}_{l,-r}^{(S)} - \bar{\theta}_{l,+r}^{(S)} \right\|^2 = 0, $$

and

$$ r \langle \bar{\epsilon}_{l,+r}^{(S)} - \bar{\epsilon}_{l,-r}^{(S)}, \bar{\theta}_{l,+r}^{(S)} - \bar{\theta}_{l,-r}^{(S)} \rangle = 0. $$

Moreover we have on $\xi^{(p)}$ that - see Equation (39)

$$ \left| \frac{r}{2} \left\| \bar{\epsilon}_{l,+r}^{(S)} - \bar{\epsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s \right| \le 4\bar{c}_{\text{conc}} L^2 \left( \log\left(\frac{n}{r\delta}\right) + s \log\left(\frac{2ep}{s}\right) \right) \le \sigma^2 x_r^{(p)}, $$

for $\bar{c}_{\text{thresh}} \ge 4\bar{c}_{\text{conc}}$ - note that $\bar{c}_{\text{conc}} > 0$ is a universal constant. And so

$$ \Psi_{l,r}^{(p)} \le x_r^{(p)}, $$

so that on $\xi^{(d)}$,

$$ T_{l,r}^{(p)} = 0. $$

This concludes the proof of the first part of the proposition.

**Step 3: Study in the ‘change-point’ situation.** Consider $k \in [K]$ such that $\tau_k$ is a $\kappa$-sparse high-energy change-point, - see Equation (18). Since $S_k$ is the support of $\mu_k - \mu_{k-1}$ - and therefore of $\bar{\theta}_{\tau_k, -\bar{r}_k^{(s)}} - \bar{\theta}_{\tau_k, +\bar{r}_k^{(s)}}$ - we have

$$ \frac{\bar{r}_k^{(s)}}{2} \left\| \bar{\theta}_{\tau_k, -\bar{r}_k^{(s)}} - \bar{\theta}_{\tau_k, +\bar{r}_k^{(s)}} \right\|^2 \ge \frac{\kappa}{8} L^2 \left( s_k \log \left( \frac{2ep}{s_k} \right) + \log \left( \frac{n}{\bar{r}_k^{(s)} \delta} \right) \right). $$
The first term written as

$$r(\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r})$$

is a crossed term between the noise and the mean vector $\theta$. Lemma 8 states that for $l$ equal to a true change-point $\tau_k$ and $r$ of order $r_k^*$, it is controlled on event $\xi_1^{(d)}$ with high probability.

**Lemma 8 (concentration of the crossed terms).** Assume that $\kappa$ is a large enough universal constant. The event

$$\xi_1^{(d)} = \left\{ \forall k \in [K] \text{ s.t. Equation (17) holds for } k, \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\tau_k, + \bar{r}_k^{(d)}}, - \bar{\epsilon}_{\tau_k, - \bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, + \bar{r}_k^{(d)}}, - \bar{\theta}_{\tau_k, - \bar{r}_k^{(d)}} \rangle \right| \le \frac{\bar{r}_k^{(d)}}{4} \left\| \bar{\theta}_{\tau_k, + \bar{r}_k^{(d)}}, - \bar{\theta}_{\tau_k, - \bar{r}_k^{(d)}} \right\|^2 \right\}$$

holds with probability higher than $1 - \delta$.

The second term written as

$$\frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p ,$$

is a term of pure noise. Lemma 9 states that it is controlled on event $\xi_2^{(d)}$ with high probability.

**Lemma 9 (concentration of the pure noise).** There exists a constant $\bar{c}_{\text{conc}} > 0$ such that the event

$$\xi_2^{(d)} = \left\{ \forall (l,r) \in J_n, \left| \frac{r}{2} \| \bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r} \|^2 - \sigma^2 p \right| \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{p \log \left( \frac{n}{r\delta} \right)} + \log \left( \frac{n}{r\delta} \right) \right) \right\}$$

holds with probability higher than $1 - 2\delta$.

Set now

$$\xi^{(d)} := \xi_1^{(d)} \cap \xi_2^{(d)} .$$

Note that

$$\mathbb{P}(\xi^{(d)}) \ge 1 - 3\delta .$$

**Step 2: Study in the ‘no change-point’ situation** We remind that $\mathcal{H}_0$ stands for elements $(l,r)$ such that there is no change-point in $[l-r, l+r)$ and that it is defined in (7). Consider $(l,r) \in J_n \cap \mathcal{H}_0$. Note that since $\{\tau_k, k \in [K]\} \cap [l-r, l+r) = \emptyset$, we have $\bar{\theta}_{l,-r} = \bar{\theta}_{l,+r}$ so that

$$\frac{r}{2} \| \bar{\theta}_{l,-r} - \bar{\theta}_{l,+r} \|^2 = 0 ,$$
So on $\xi^{(p)}$ this implies that - see Lemma 15

$$ \bar{r}_k^{(d)} \left| \langle \bar{\epsilon}^{(S_k)}_{\tau_k, +\bar{r}_k^{(s)}} - \bar{\epsilon}^{(S_k)}_{\tau_k, -\bar{r}_k^{(s)}}, \bar{\theta}^{(S_k)}_{\tau_k, +\bar{r}_k^{(s)}} - \bar{\theta}^{(S_k)}_{\tau_k, -\bar{r}_k^{(s)}} \rangle \right| \le \frac{\bar{r}_k^{(s)}}{4} \left\| \bar{\theta}_{\tau_k, +\bar{r}_k^{(s)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(s)}} \right\|^2. $$

Moreover we have on $\xi^{(p)}$ that - see Equation (39)

$$ \left| \frac{\bar{r}_k^{(s)}}{2} \left\| \bar{\epsilon}^{(S_k)}_{\tau_k, +\bar{r}_k^{(s)}} - \bar{\epsilon}^{(S_k)}_{\tau_k, -\bar{r}_k^{(s)}} \right\|^2 - \sigma^2 s \right| \le 4\bar{c}_{\text{conc}} L^2 \left( \log \left( \frac{n}{\bar{r}_k^{(s)}\delta} \right) + 2s_k \log \left( \frac{2ep}{s_k} \right) \right) \le \sigma^2 x_{\bar{r}_k^{(s)}}^{(p)}, $$

for $\bar{c}_{\text{thresh}} \ge 4\bar{c}_{\text{conc}}$ - note that $\bar{c}_{\text{conc}} > 0$ is a universal constant. And so on $\xi^{(p)}$, combining the three previous displayed equations implies

$$ \Psi_{\tau_k, \bar{r}_k^{(s)}}^{(p)} \ge \frac{\bar{r}_k^{(d)}}{4\sigma^2} \left\| \bar{\theta}^{(S_k)}_{\tau_k, +\bar{r}_k^{(s)}} - \bar{\theta}^{(S_k)}_{\tau_k, -\bar{r}_k^{(s)}} \right\|^2 - x_{\bar{r}_k^{(s)}}^{(p)} \\ \ge \left( \frac{\kappa}{16} - \bar{c}_{\text{thresh}} \right) \frac{L^2}{\sigma^2} \left( \log \left( \frac{n}{\bar{r}_k^{(s)}\delta} \right) + s_k \log \left( \frac{2ep}{s_k} \right) \right) > x_{\bar{r}_k^{(s)}}^{(p)}, $$

since $\kappa > 32\bar{c}_{\text{thresh}}$. And so on $\xi^{(p)}$

$$ T_{\tau_k, \bar{r}_k^{(s)}}^{(p)} = 1. $$

This concludes the proof of the second part of the proposition.

### B.3.3 Proof of Corollary 5

Let $\xi^{(d)}$ and $\xi^{(s)}$ be two events such that Proposition 3 and Proposition 4 both hold with probability $1-3\delta$, and write $\xi = \xi^{(d)} \cap \xi^{(p)}$. From now on, we work on the event $\xi$, which holds with probability $1-6\delta$. Define here simply $\bar{\tau}_k = \tau_k$. Note that by definition of $\bar{r}_k$ in the sub-Gaussian regime:

$$ \bar{r}_k = \begin{cases} \bar{r}_k^{(d)} & \text{if } s_k \log \left( \frac{ep}{s_k} \right) > \sqrt{p \log \left( \frac{n}{r_k \delta} \right)} \\ \bar{r}_k^{(s)} & \text{if } s_k \log \left( \frac{ep}{s_k} \right) \le \sqrt{p \log \left( \frac{n}{r_k \delta} \right)} \end{cases} $$

According to Theorem 1, it is sufficient to prove that $\mathcal{A}(\Theta, T, \mathcal{K}^*, (\bar{\tau}_k, \bar{r}_k)_{k \in \mathcal{K}^*})$ holds.

1. (No false positive): $T_{l,r} = T_{l,r}^{(p)} \cup T_{l,r}^{(d)} = 0$ for any $(l,r) \in \mathcal{G}_F \cap \mathcal{H}_0$. by Proposition 3 and Proposition 4.

2. (Significant change-point detection): for every $k \in \mathcal{K}^*$ (see (20)), we have by definition of $\bar{r}_k$:

$$ 4(\bar{r}_k - 1) \le r_k. $$

Now if $s_k \log \left( \frac{ep}{s_k} \right) \ge \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}$, we have $T_{\bar{\tau}_k, \bar{r}_k}^{(d)} = 1$ by Proposition 3, by definition of $c_0$, and for $\bar{c}_{\text{thresh}}^{(d)}$ as in Proposition 3.

If $s_k \log \left( \frac{ep}{s_k} \right) \le \sqrt{p \log \left( \frac{n}{r_k \delta} \right)}$, we have $T_{\bar{\tau}_k, \bar{r}_k}^{(p)} = 1$ by Proposition 4, by definition of $c_0$, and for $\bar{c}_{\text{thresh}}^{(p)}$ as in Proposition 4.
and

$$r\langle\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}, \bar{\theta}_{l,+r} - \bar{\theta}_{l,-r}\rangle = 0.$$

Moreover we have on $\xi^{(d)}$ that – see Lemma 9

$$\left| \frac{r}{2} \|\bar{\epsilon}_{l,+r} - \bar{\epsilon}_{l,-r}\|^2 - \sigma^2 p \right| \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{p \log\left(\frac{n}{r\delta}\right)} + \log\left(\frac{n}{r\delta}\right) \right) \le \sigma^2 x_r^{(d)},$$

for $\bar{c}_{\text{thresh}} \ge \bar{c}_{\text{conc}}$ – note that $\bar{c}_{\text{conc}} > 0$ is a universal constant. And so

$$\Psi_{l,r}^{(d)} \le x_r^{(d)},$$

so that

$$T_{l,r}^{(d)} = 0,$$

on $\xi^{(d)}$. This concludes the proof of the first part of the proposition.

**Step 3: Study in the ‘change-point’ situation** Consider $k \in [K]$ such that $\tau_k$ is a $\kappa$-dense high-energy change-point – see Equation (17). We have

$$\frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} \right\|^2 \ge \frac{\kappa}{8} L^2 \left( \sqrt{p \log\left(\frac{n}{\bar{r}_k^{(d)}\delta}\right)} + \log\left(\frac{n}{\bar{r}_k^{(d)}\delta}\right) \right).$$

So on $\xi^{(d)}$ choosing $\kappa$ large enough implies that – see Lemma 8

$$\bar{r}_k^{(d)} \left| \langle \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \rangle \right| \le \frac{\bar{r}_k^{(d)}}{4} \left\| \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right\|^2.$$

Moreover we have on $\xi^{(d)}$ that – see Lemma 9

$$\left| \frac{\bar{r}_k^{(d)}}{2} \left\| \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}} \right\|^2 - \sigma^2 p \right| \\ \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{p \log\left(\frac{n}{\bar{r}_k^{(d)}\delta}\right)} + \log\left(\frac{n}{\bar{r}_k^{(d)}\delta}\right) \right) \le \sigma^2 x_{\bar{r}_k^{(d)}},$$

for $\bar{c}_{\text{thresh}} \ge \bar{c}_{\text{conc}}$ – note that $\bar{c}_{\text{conc}} > 0$ is a universal constant.

Thus on $\xi^{(d)}$, combining the three previous displayed equations implies

$$\Psi_{\tau_k, \bar{r}_k^{(d)}}^{(d)} \ge \frac{\bar{r}_k^{(d)}}{4\sigma^2} \left\| \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right\|^2 - x_{\bar{r}_k^{(d)}}^{(d)} \\ \ge \left( \frac{c_0}{16} - \bar{c}_{\text{thresh}} \right) \frac{L^2}{\sigma^2} \left( \sqrt{p \log\left(\frac{n}{\bar{r}_k^{(d)}\delta}\right)} + \log\left(\frac{n}{\bar{r}_k^{(d)}\delta}\right) \right) > x_{\bar{r}_k^{(d)}}^{(d)},$$

since $\kappa > 32\bar{c}_{\text{thresh}}$. And so on $\xi^{(d)}$:

$$T_{\tau_k, \bar{r}_k^{(d)}}^{(d)} = 1.$$

This concludes the proof of the second part of the proposition.
Theorem 1 ensures that for all $k \in \mathcal{K}^*$, there exists $k' \in [\hat{\mathcal{K}}]$ such that

$$|\hat{\tau}_{k'} - \tau_k| \le \bar{r}_k - 1.$$

This concludes the proof since $4(\bar{r}_k - 1) \le r_k$ for $k \in \mathcal{K}^*$.

## B.4 Proof of Theorem 2

Let us fix $(r, s) \in [1, n/4] \times [1, p]$. Let $\Delta$ be such that

$$r\Delta^2 = \frac{1}{2}\sigma^2 \left[ s \log \left( 1 + u \frac{\sqrt{p}}{s} \sqrt{\log \left( \frac{n}{r} \right)} \right) + u \log \left( \frac{n}{r} \right) \right],$$

for some $u \le \frac{1}{8}$.

In what follows, we consider any change-point detection method that outputs an estimator $\hat{\tau}$ of the change-points, associated to a number $\hat{\mathcal{K}}$ of detected change-points, i.e. the length of $\hat{\tau}$. We also write $\mathbb{P}_{\Theta}$ for the distribution of the data when the mean parameter or the time series is fixed to a $n \times p$ matrix $\Theta$, i.e. of $\Theta + \varepsilon$ where the noise entries $(\varepsilon_t)_j$ are i.i.d. and follow $\mathcal{N}(0, \sigma^2)$ as in Section 3. Also abusing slightly notations, we write $\mathbb{P}_0$ for the distribution of the data when the parameter is constant and equal to 0.

Consider also any prior $\pi$ over the set of $n \times p$ matrices $\Theta$ such that the number of true change-points over the support of the prior is larger than 1 - i.e. the prior puts mass only on problems where more than one change-point occurs. Let $\mathbb{P}_{\pi}$ be the corresponding distribution of the data, namely the distribution of the matrix of data when the mean parameter of the time series is the random matrix $\hat{\Theta} \sim \pi$. Otherwise said, $\mathbb{P}_{\pi}$ is the distribution of $\hat{\Theta} + \varepsilon$ where $\hat{\Theta} \sim \pi$.

We remind that in our setting $\mathcal{K}$ is the number of true change-points in a given problem - which would be either 0 under $\mathbb{P}_0$, or more than 1 under $\mathbb{P}_{\pi}$. If the support of $\pi_1$ is included in $\mathcal{P}(r, s)$, then

$$\sup_{\Theta \in \mathcal{P}(r,s)} \mathbb{P}_{\Theta}(\hat{\mathcal{K}} \neq \mathcal{K}) \ge \frac{1}{2} \left( \mathbb{P}_{\pi}(\hat{\mathcal{K}} = 0) + \mathbb{P}_{0}(\hat{\mathcal{K}} \neq 0) \right) \\ \ge \frac{1}{2} (1 - d_{TV}(\mathbb{P}_{\pi}, \mathbb{P}_{0})), \qquad (40)$$

where $d_{TV}$ is the total variation distance. From the Cauchy-Schwarz inequality, we have

$$d_{TV}(\bar{\mathbb{P}}_{\pi}, \mathbb{P}_{0}) \le \frac{1}{2} \sqrt{\chi^2(\bar{\mathbb{P}}_{\pi}, \mathbb{P}_{0})}, \qquad (41)$$

where $\chi^2$ is the divergence between probability distributions:

$$\chi^2(\bar{\mathbb{P}}_{\pi}, \mathbb{P}_{0}) = \mathbb{E}_{\mathbb{P}_{0}} \left[ \left( \frac{d\bar{\mathbb{P}}_{\pi}}{d\mathbb{P}_{0}} - 1 \right)^2 \right].$$

By a simple computation that can be found for example in [47]

$$\chi^2(\bar{\mathbb{P}}_{\pi}, \mathbb{P}_{0}) = \mathbb{E}_{\hat{\Theta}, \hat{\Theta}'} \left[ e^{\frac{1}{\sigma^2} \langle \hat{\Theta}, \hat{\Theta}' \rangle} \right] - 1, \qquad (42)$$

where $\hat{\Theta}$ and $\hat{\Theta}'$ are i.i.d. and distributed according to $\pi$, $\langle \hat{\Theta}, \hat{\Theta}' \rangle = \text{Tr}(\hat{\Theta}'\hat{\Theta}^T)$ is the standard scalar product, and $\mathbb{E}_{\hat{\Theta}, \hat{\Theta}'}$ is the expectation according to $\hat{\Theta}$ and $\hat{\Theta}'$.
**Proof of Lemma 8.** Let $k$ be in $[K]$ and such that Equation (17) is satisfied. Remark that $\theta$ is constant on $[\tau_k - \bar{r}_k^{(d)}, \tau_k)$ and is equal to $\mu_{k-1}$, and is also constant on $[\tau_k, \tau_k + \bar{r}_k^{(d)})$ and is equal to $\mu_k$. First, from the definition of the $\psi_2$-norm of a vector, there exists a universal constant $C > 0$ such that for all $k = 1...K$,

$$ \begin{aligned} & \|\bar{r}_k^{(d)} \langle \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \rangle\|_{\psi_2} \\ & \le \bar{r}_k^{(d)} \left\| \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}} \right\|_{\psi_2} |\mu_k - \mu_{k-1}| \\ & \le C \sqrt{\bar{r}_k^{(d)}} \|\epsilon_1\|_{\psi_2} |\mu_k - \mu_{k-1}| \le C \sqrt{\bar{r}_k^{(d)}} L |\mu_k - \mu_{k-1}| \le CL \sqrt{r_k \Delta_k^2}. \end{aligned} $$

Thus by definition of sub-Gaussianity, for all $t > 0$,

$$ \mathbb{P} \left( \left| \bar{r}_k^{(d)} \right| \left| \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right| \ge t \right) \le \exp \left( -c \frac{t^2}{L^2 r_k \Delta_k^2} \right), $$

for some constant $c > 0$. Finally we apply the concentration inequality to $t = \frac{r_k \Delta_k^2}{4}$ – remembering that $\tau_k$ is a $\kappa$-dense high-energy change-point in the sense of Equation (17) – and sum over $k$ to obtain a union bound over $\xi_2$:

$$ \begin{aligned} \mathbb{P}(\xi_2^c) &\le \sum_{k=1}^K \mathbb{P} \left( r \left| \bar{\epsilon}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\epsilon}_{\tau_k, -\bar{r}_k^{(d)}}, \bar{\theta}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(d)}} \right| \ge \frac{r_k \Delta_k^2}{4} \right) \\ &\le \sum_{k=1}^K \exp \left( -c \frac{r_k \Delta_k^2}{16L^2} \right) \\ &\le \sum_{k=1}^K \exp \left( -c' \kappa \log \left( \frac{n}{\bar{r}_k^{(d)}} \delta^{-1} \right) \right) \quad (c' = c/16) \\ &\le \sum_{k=1}^K \left( \frac{\bar{r}_k^{(d)}}{n} \right)^{c'\kappa} \delta^{c'\kappa} \\ &\le \delta, \end{aligned} $$

where the last inequality comes from the fact that $\sum_{k=1}^K \bar{r}_k^{(d)} \le n$ and the fact that $\kappa$ is chosen large enough so that $c'\kappa \ge 1$. $\square$

**Proof of Lemma 9.** Remark first that by homogeneity, we can assume without loss of generality that $L = 1$. To provide a proof, we will use the Hanson-Wright inequality in high dimension, which is a way to control quadratic forms of the noise.

**Lemma 10 (Hanson-Wright inequality in high dimension).** Let $A = (a_{ij})$ be a $m \times m$ matrix and $\epsilon_1, \dots, \epsilon_m$ be sub-Gaussian vectors of dimension $p$ with norm smaller than 1. Then

$$ \mathbb{P} \left( \left| \sum_{1 \le i,j \le m} a_{i,j} \langle \epsilon_i, \epsilon_j \rangle - \mathbb{E} \left[ \sum_{1 \le i,j \le m} a_{i,j} \langle \epsilon_i, \epsilon_j \rangle \right] \right| \ge t \right) $$
Let us consider the three following cases for the couple $(r, s)$:

$$ \textbf{Case 1:} \quad u \log \left(\frac{n}{r}\right) \le s \log \left(1 + u \frac{\sqrt{p}}{s} \sqrt{\log \left(\frac{n}{r}\right)}\right) \quad \text{and} \quad s \le u \sqrt{p \log \left(\frac{n}{r}\right)}, $$

$$ \textbf{Case 2:} \quad u \log \left(\frac{n}{r}\right) \le s \log \left(1 + u \frac{\sqrt{p}}{s} \sqrt{\log \left(\frac{n}{r}\right)}\right) \quad \text{and} \quad s > u \sqrt{p \log \left(\frac{n}{r}\right)}, $$

$$ \textbf{Case 3:} \quad u \log \left(\frac{n}{r}\right) > s \log \left(1 + u \frac{\sqrt{p}}{s} \sqrt{\log \left(\frac{n}{r}\right)}\right). $$

Each case corresponds to the regime of detection of one of the three statistics. The first one corresponds to the Berk-Jones statistic, the second one to the dense statistic and the last one to the partial norm statistic.

**Case 1:** In that case, $r\Delta^2 \le \sigma^2 s \log(4u\frac{p}{s}\log(\frac{n}{r}))$. Let us define a probability distribution on the parameter $\Theta \in \mathcal{P}(r, s)$. For $\zeta = \lfloor\frac{n}{r}\rfloor - 1$ and $l \in \hat{\mathcal{D}}_r = \{1, r+1, 2r+1, \dots, \zeta r + 1\}$, define the column vector $v_l = \sum_{j=l}^{l+r-1} e_j$, where $e_j$ is the $j$th element of the canonical basis of $\mathbb{R}^n$. Let $a$ be a random variable uniformly distributed in $\{x \in \{0, 1\}^p, |x|_0 = s\}$ and $\nu$ be a random variable independent from $a$ and uniformly distributed on $\{v_l : l \in \hat{\mathcal{D}}_r\}$. Let

$$ \tilde{\Theta}_{(1)} = \frac{\Delta}{\sqrt{s}} a \nu^T \in \mathbb{R}^{p \times n}, $$

and $\pi_1$ be the distribution of the random variable $\tilde{\Theta}_{(1)}$, and $\bar{\mathbb{P}}_{\pi_1}$ be the corresponding distribution of the data.

Consider two independent copies $\tilde{\Theta}_{(1)}$ and $\tilde{\Theta}'_{(1)}$ that are distributed like $\pi_1$. The probability that $\tilde{\Theta}_{(1)}$ and $\tilde{\Theta}'_{(1)}$ have the same support is exactly $\frac{1}{\zeta+1}$. Hence, from Equation (42)

$$ \chi^2(\bar{\mathbb{P}}_{\pi_1}, \mathbb{P}_0) = \frac{1}{\zeta+1} \left( \mathbb{E}_{a,a'} \left[ e^{\frac{r\Delta^2}{s\sigma^2} \langle a, a' \rangle} - 1 \right] \right), \quad (43) $$

where $a'$ is an independent copy of $a$, and $\mathbb{E}_{a,a'}$ is the expectation according to $a, a'$. Remark by symmetry that $\langle a, a' \rangle$ has the same law as $\sum_{i=1}^s a_i$. Hence

$$ \mathbb{E}_{a,a'} \left[ e^{\frac{r\Delta^2}{s\sigma^2} \langle a, a' \rangle} \right] = \mathbb{E}_a \left[ e^{\frac{r\Delta^2}{s\sigma^2} \sum_{i=1}^s a_i} \right], $$

where $\mathbb{E}_a$ is the expectation according to $a$.

Remark that $(a_1, \dots, a_p)$ has the same distribution as a random sampling without replacement of the list of length $p$ containing $(1, \dots, 1, 0, \dots, 0)$ - the list containing exactly $s$ times the quantity 1 and otherwise only 0. The following lemma allows us to replace the variables $a_i$ by independent Bernoulli random variables $Z_i \sim \mathcal{B}(s/p)$.

**Lemma 17.** Let $c = (c_1, \dots, c_p) \in \mathbb{R}^p$. We associate to the list $c$ two random sampling processes: (i) the sampling process without replacement $(X_i)_{i=1\dots s}$ of $s$ elements uniformly on the list $c$ and (ii) the sampling process with replacement $(Z_i)_{i=1\dots s}$ of $s$ elements uniformly in the list. Then for any convex function $f$,

$$ \mathbb{E} \left[ f \left( \sum_{i=1}^{s} X_i \right) \right] \le \mathbb{E} \left[ f \left( \sum_{i=1}^{s} Z_i \right) \right]. $$
$$ \leq 2 \exp \left( -c \min \left( \frac{t^2}{p \|A\|_F^2}, \frac{t}{\|A\|_{op}} \right) \right), $$

where c is an absolute constant, $\|A\|_F^2 = \sum_{i,j} a_{i,j}^2$ is the squared Frobenius norm of A and $\|A\|_{op}$ is the operator norm of A.

The proof of this lemma relies on the classical Hanson Wright inequality that is proved for example in [35]. To prove the proposition, we will use a chaining argument. To this end, we let $(N_u)_{u \ge 0}$ be the following covering sets of $J_n$:

$$ N_u = J_n \cap \{i 2^{\kappa_1 - u}, i \in \mathbb{N}\}^2, $$

where we define $\kappa_1 = \lfloor \log_2(n) \rfloor$, and more generally $\kappa_r = \lfloor \log_2(n/r) \rfloor$ for $r = 1, \dots, n$. Remark that the higher $u$ is, the finer the covering set $\tilde{N}_u$ is, and $N_{\kappa_1} = J_n$. For all $u \ge 0$, we define the projection map $\pi_u$ from $J_n$ to $N_u$ by

$$ \pi_u(l, r) = \arg \min_{(\hat{l}, \hat{r}) \in N_u} (|\hat{l} - l| + |\hat{r} - r|). $$

In the sequel, we will use the slight abuse of notation for $(l, r)$ in $J_n$:

$$ (l_u, r_u) = \pi_u(l, r). $$

A useful lemma to control the distance between $(l, r)$ and its projection $(l_u, r_u)$ can be stated as follows.

**Lemma 11.** For all $(l, r) \in J_n$ and $0 \le u \le \kappa_1$ such that $N_u \ne \emptyset$,

$$ |l_u - l| + |r_u - r| \le 2 \frac{n}{2u}. $$

Let $(l, r) \in J_n$. From now on, we write $\varepsilon_{l,+r} = r\bar{\varepsilon}_{l,+r} = \sum_{t=l}^{l+r-1} \varepsilon_t$ and $\varepsilon_{l,-r} = r\bar{\varepsilon}_{l,-r}$. The chaining relation can be written as

$$ \begin{aligned} & \frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p \\ &= \frac{1}{2r} \left[ \|\varepsilon_{l_{\kappa_r},+r_{\kappa_r}} - \varepsilon_{l_{\kappa_r},-r_{\kappa_r}}\|^2 - 2r_{\kappa_r} \sigma^2 p \right] \\ & \quad + \frac{1}{2r} \sum_{v=\kappa_r}^{\kappa_1} \left[ \|\varepsilon_{l_{v+1},+r_{v+1}} - \varepsilon_{l_{v+1},-r_{v+1}}\|^2 \right. \\ & \qquad \left. - \|\varepsilon_{l_v,+r_v} - \varepsilon_{l_v,-r_v}\|^2 - 2(r_{v+1} - r_v)\sigma^2 p \right]. \end{aligned} $$

Remark that the chaining summation starts at scale $u = \kappa_r$ so that $\frac{n}{2u} \asymp r$. The first term of the chaining is an approximation on the grid at level $u$ of the term $\frac{r}{2} \|\bar{\varepsilon}_{l,+r} - \bar{\varepsilon}_{l,-r}\|^2 - \sigma^2 p$. The second term can be viewed as an error term, and we will show that it is of the same order as the first term. Since both terms are quadratic forms of the noise, we will need an upper bound on the norm of their corresponding matrix to apply the Hanson Wright inequality – see Lemma 10.
The proof of this lemma can be found in [19]. Thus, if $(Z_i)_{i=1...s}$ is an i.i.d sequence of Bernoulli variables with parameter $\frac{s}{p}$ as described above, we obtain

$$ 
\begin{aligned}
\chi^2(\bar{\mathbb{P}}_{\pi_1}, \mathbb{P}_0) &\le \frac{1}{\zeta+1} \left( \mathbb{E}_Z \left[ e^{\frac{r\Delta^2}{s\sigma^2} \sum_{i=1}^s Z_i} \right] - 1 \right) && (44) \\
&= \frac{1}{\zeta+1} \left[ \left( \frac{s}{p} e^{\frac{r\Delta^2}{s\sigma^2}} + 1 - \frac{s}{p} \right)^s - 1 \right] \le \frac{1}{\zeta+1} \left[ e^{\frac{s^2}{p} \left( e^{\frac{r\Delta^2}{s\sigma^2}} - 1 \right)} - 1 \right] \\
&\le 2 \frac{r}{n} e^{\frac{s^2}{p} \left( e^{\log(4u^2 \frac{p}{s^2 \log(\frac{n}{r})})} \right)} \le 2 \left( \frac{r}{n} \right)^{1-4u^2} \le 1 , && (45)
\end{aligned}
$$

where $\mathbb{E}_Z$ is the expectation according to the $(Z_i)_i$ and where in the last inequality we used $u \le 1/3$ and $n \ge 4r$.

**Case 2:** In that case, $r\Delta^2 \le \sigma^2 u \sqrt{p \log(\frac{n}{r})}$. Let $s_0 = \left\lceil u \sqrt{p \log(\frac{n}{r})} \right\rceil$ and $b$ be a random variable uniformly distributed in $\{x \in \{0,1\}^p, |x|_0 = s_0\}$ and $\nu$ be defined as in **Case 1**. Let

$$ \tilde{\Theta}_{(2)} = \frac{\Delta}{\sqrt{p}} b \nu^T, $$

let $\pi_2$ be the distribution of $\tilde{\Theta}_{(2)}$ and $\bar{\mathbb{P}}_{\pi_2}$ be the associated probability distribution of the data. Doing the same reasoning and similar computations as for **Case 1**, see in particular the steps of Equations (43) and (44) - replacing $s$ by $s_0$ and $a$ by $b$ - we have

$$ 
\begin{aligned}
\chi^2(\bar{\mathbb{P}}_{\pi_2}, \mathbb{P}_0) &= \mathbb{E}_{\tilde{\Theta}_{(2)}, \tilde{\Theta}'_{(2)}} \left[ e^{\frac{1}{\sigma^2} \langle \tilde{\Theta}_{(2)}, \tilde{\Theta}'_{(2)} \rangle} \right] - 1 = \frac{1}{\zeta+1} \mathbb{E}_{b,b'} \left[ e^{\frac{r\Delta^2}{p\sigma^2} \langle b,b' \rangle} - 1 \right] \le \frac{1}{\zeta+1} \left[ e^{\frac{s_0^2}{p} \left( e^{\frac{r\Delta^2}{s_0\sigma^2}} - 1 \right)} - 1 \right] \\
&\le \frac{1}{\zeta+1} e^{2 \frac{s_0 r \Delta^2}{p \sigma^2}} \le 2 \frac{r}{n} e^{4u \log \frac{n}{r}} = 2 \left( \frac{r}{n} \right)^{1-4u} \le 1 , && (46)
\end{aligned}
$$

where $\mathbb{E}_{\tilde{\Theta}_{(2)}, \tilde{\Theta}'_{(2)}}$ is the expectation according to $\tilde{\Theta}_{(2)}$, $\tilde{\Theta}'_{(2)}$ (where $\tilde{\Theta}'_{(2)}$ is an independent copy of $\tilde{\Theta}_{(2)}$) and where $\mathbb{E}_{b,b'}$ is the expectation according to $b, b'$ (where $b'$ is an independent copy of $b$), and where in the last step we used $u \le 1/8$ and $n \ge 4r$.

**Case 3:** In that case, $r\Delta^2 \le u \log(\frac{n}{r})$. Let $c = (1,0,0,\dots,0)$ be the vector with 0 entries except the first one. Let $\nu$ be the random vector defined as in **Case 1**. Let

$$ \tilde{\Theta}_{(3)} = \Delta c \nu^T, $$

and $\pi_3$ be the distribution of the random variable $\tilde{\Theta}_{(3)}$ - and $\bar{\mathbb{P}}_{\pi_3}$ be the associated probability distribution of the data. Doing the same reasoning as in **Case 1** - see in particular the step of Equation (43) - replacing $a$ by $c$ and $s$ by 1 - for the prior $\pi_3$, we obtain

$$ 
\begin{aligned}
\chi^2(\bar{\mathbb{P}}_{\pi_3}, \mathbb{P}_0) &= \mathbb{E}_{\tilde{\Theta}_{(3)}, \tilde{\Theta}'_{(3)}} \left[ e^{\frac{1}{\sigma^2} \langle \tilde{\Theta}_{(3)}, \tilde{\Theta}'_{(3)} \rangle} \right] - 1 = \frac{1}{\zeta+1} e^{\frac{r\Delta^2}{\sigma^2}} \le 2 \frac{r}{n} e^{u \log(\frac{n}{r})} \le 2 \left( \frac{r}{n} \right)^{1-u} \le 1 , && (47)
\end{aligned}
$$

where $\mathbb{E}_{\tilde{\Theta}_{(3)}, \tilde{\Theta}'_{(3)}}$ is the expectation according to $\tilde{\Theta}_{(3)}$, $\tilde{\Theta}'_{(3)}$ (where $\tilde{\Theta}'_{(3)}$ is an independent copy of $\tilde{\Theta}_{(3)}$) and where in the last step we used $n \ge 4r$ and $u \le 1/2$.
**Lemma 12** (Control of the Frobenius norm). Let $(l, r)$ be a fixed element of $J_n$. Let A and B be the corresponding matrix of the two following quadratic form:

$$ \varepsilon^T A \varepsilon = \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 \quad \text{and} \quad \varepsilon^T B \varepsilon = \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - \|\varepsilon_{l',+r'} - \varepsilon_{l',-r'}\|^2 . $$

Then

$$ \|A\|_F^2 \le 16r^2 $$

$$ \|B\|_F^2 \le 24 (|l - l'| + |r - r'|) (r + r' + |l - l'|) . $$

The following lemma aims at upper bounding the first term of the chaining relation with high probability.

**Lemma 13.** There exists a constant $C_N$ such that for all $n$, the event

$$ \xi_N^{(d)} = \bigcap_{u \ge 0} \bigcap_{(l,r) \in N_u} \left\{ \begin{aligned} & \left\| \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - 2r\sigma^2p \right| \\ & \le C_N r \left( \sqrt{p \log (2^u \delta^{-1})} + \log (2^u \delta^{-1}) \right) \end{aligned} \right\} . $$

holds with probability higher than $1 - \delta$.

For $u = \kappa_r$, $(l_u, r_u) \in N_u$ Lemma 11 gives $r_u \le r + 2\frac{n}{2^u} \le 3\frac{n}{2^u}$. Consequently, on the event $\xi_N^{(d)}$, we obtain

$$ \left| \frac{1}{2r} \| \varepsilon_{l_{\kappa_r},+r_{\kappa_r}} - \varepsilon_{l_{\kappa_r},-r_{\kappa_r}} \|^2 - \frac{r_{\kappa_r}}{r} \sigma^2 p \right| \le C'_N \left( \sqrt{p \log \left( \frac{n}{r\delta} \right)} + \log \left( \frac{n}{r\delta} \right) \right), $$

for $C'_N$ a large absolute constant. To upper bound the second term, we use the following lemma:

**Lemma 14.** For all $(l, r)$ and $(l', r')$ in $J_n$, set

$$ \xi_{\Delta,v}^{(d)}(l,r,l',r') = \left\{ \begin{aligned} & \left\| \|\varepsilon_{l',+r'} - \varepsilon_{l',-r'}\|^2 - \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - 2(r' - r)\sigma^2 p \right| \\ & \le C_{\Delta} \sqrt{\frac{rn}{2^v}} \left( \sqrt{p \log (2^v \delta^{-1})} + \log (2^v \delta^{-1}) \right) \end{aligned} \right\} . $$

There exists a constant $C_{\Delta}$ such that, for all $n$, the event

$$ \xi_{\Delta}^{(d)} = \bigcap_{v \ge 0} \left\{ \begin{array}{l} \xi_{\Delta,v}^{(d)}(l,r,l',r') \text{ holds for all } ((l,r), (l', r')) \in N_v \times N_{v+1} \\ \text{s.t. } |l - l'| + |r - r'| \le 3 \frac{n}{2^v} \end{array} \right\} . $$

holds with probability higher than $1 - \delta$.
Thus, in all cases - combining Equations (40) and (41) with Equations (45), (46) and (47) - we obtain in all three cases

$$ \sup_{\Theta \in \mathcal{P}(r,s)} \mathbb{P}_{\Theta}(\hat{K} \neq K) \geq \frac{1}{4}. $$

and this concludes the proof.

## B.5 Proofs for covariance and nonparametric change-point detection

*Proof of Proposition 5.* Consider an r-sample $(z_1, \dots, z_r)$ with mean zero and covariance matrix $\Sigma$ and Orlicz norm $B$. Koltchinskii and Lounici [23] have proved that, for any $x > 0$, the empirical covariance matrix $\hat{\Sigma} = r^{-1}(\sum_{i=1}^r z_i z_i^T)$ satisfies

$$ \|\hat{\Sigma} - \Sigma\|_{op} \leq c' B^2 \left[ \sqrt{\frac{p}{r}} + \frac{p}{r} + \sqrt{\frac{x}{r}} + \frac{x}{r} \right], $$

with probability higher than $1 - \exp(-x)$. Here $c'$ is a suitable positive constant. Considering a union bound over all $(l, r) \in \mathcal{G}_D$ such that $\Sigma_t$ is constant over $[l-r, l+r)$, we have, with probability higher than $1 - \delta/2$, that simultaneously on all such $r \in \mathcal{R}$ and $l \in \mathcal{D}_r$,

$$ \|\hat{\Sigma}_{l,r} - \hat{\Sigma}_{l,-r}\|_{op} \le \|\hat{\Sigma}_{l,r} - \Sigma_l\|_{op} + \|\hat{\Sigma}_{l,-r} - \Sigma_l\|_{op} \le 8c'B^2 \left[ \sqrt{\frac{p}{r}} + \frac{p}{r} + \sqrt{\frac{\log(2n/(r\delta))}{r}} + \frac{\log(2n/(r\delta))}{r} \right], $$

where the constant 8 comes from the union bound on all elements of the grid. As a consequence, the FWER of the multiple testing collection is at most $\delta/2$ provided that we choose $c_0 \le 8c'$.

Conversely, consider any high-energy change-point $\tau_k$. Let $\bar{r}_k$ be the smallest radius $r \in \mathcal{R}$ such that

$$ r \|\Sigma_{\tau_k} - \Sigma_{\tau_{k-1}}\|_{op}^2 \ge 0.25 c_1 B^4 \left[ \left( p + \log \left( \frac{2n}{r\delta} \right) \right) \wedge r \right]. \quad (48) $$

and consider the closest location $l \in \mathcal{D}_r$ of $\tau_k$ so that $|l - \tau_k| \le r/2$. To ease the notation, we still write $r$ for $\bar{r}_k$. Without loss of generality, we assume that $l \ge \tau_k$. Let us decompose the statistic $\hat{\Sigma}_{l,-r} = \frac{r-l+\tau_k}{r} \hat{\Sigma}_{\tau_k,-(r-l+\tau_k)} + \frac{l-\tau_k}{r} \hat{\Sigma}_{l,-(l-\tau_k)}$. Since $r \le r_k/2$, $\Sigma_l$ is constant over $[l-r, \tau_k)$ and over $[\tau_k, l+r)$. Then, we apply three times the deviation inequality of Koltchinskii and Lounici [23] to get

$$ \begin{aligned} \|\hat{\Sigma}_{l,r} - \hat{\Sigma}_{l,-r}\|_{op} &\ge \frac{r-l+\tau_k}{r} \|\Sigma_{\tau_k} - \Sigma_{\tau_{k-1}}\|_{op} - \|\hat{\Sigma}_{l,r} - \Sigma_{\tau_k}\|_{op} \\ &\quad - \frac{l-\tau_k}{r} \|\hat{\Sigma}_{l,-(l-\tau_k)} - \Sigma_{\tau_k}\|_{op} - \frac{r-l+\tau_k}{r} \|\hat{\Sigma}_{\tau_k,-(r-l+\tau_k)} - \Sigma_{\tau_{k-1}}\|_{op} \\ &\ge \frac{1}{2} \|\Sigma_{\tau_k} - \Sigma_{\tau_{k-1}}\|_{op} - c'' B^2 \left[ \sqrt{\frac{p}{r}} + \frac{p}{r} + \sqrt{\frac{\log(2n/(r\delta))}{r}} + \frac{\log(2n/(r\delta))}{r} \right], \end{aligned} $$

with probability higher than $1 - 0.5\delta[r/(2n)]^2$. As a consequence, we have $T_{l,r} = 1$ provided that

$$ \|\Sigma_{\tau_k} - \Sigma_{\tau_{k-1}}\|_{op} \ge 2(c'' + c_0)B^2 \left[ \sqrt{\frac{p}{r}} + \frac{p}{r} + \sqrt{\frac{\log(2n/(r\delta))}{r}} + \frac{\log(2n/(r\delta))}{r} \right]. $$

Since $\|\Sigma_{\tau_k} - \Sigma_{\tau_{k-1}}\|_{op} \le 2B^2$ and if we choose $c_1 \ge 17 \vee 32(c'' + c_0)$, the bound (48) is achievable only if $r \ge p + \log(2n/(r\delta))$ and we deduce from (48) that $T_{l,r} = 1$.
For $v \ge \kappa_r$, $((l_v, r_v), (l_{v+1}, r_{v+1})) \in N_v \times N_{v+1}$ and by Lemma 11,

$$ 
\begin{aligned}
& |r_v - r_{v+1}| + |l_v - l_{v+1}| \le |r_v - r| + |l_v - l| + |r - r_{v+1}| + |l - l_{v+1}| \\
& \le 3 \frac{n}{2^v}.
\end{aligned}
$$

Therefore, on the event $\xi_{\Delta}^{(d)}$,

$$ 
\begin{aligned}
& \left| \frac{1}{2r} \sum_{v=\kappa_r}^{\kappa_1-1} \left[ \|\varepsilon_{l_{v+1},+r_{v+1}} - \varepsilon_{l_{v+1},-r_{v+1}}\|^2 - \|\varepsilon_{l_v,+r_v} - \varepsilon_{l_v,-r_v}\|^2 - 2(r_{v+1} - r_v)\sigma^2 p \right] \right| \\
& \le C_{\Delta} \frac{1}{2r} \sum_{v=\kappa_r}^{\kappa_1-1} \sqrt{\frac{r_v n}{2^v}} \left( \sqrt{p \log (2^v \delta^{-1})} + \log (2^v \delta^{-1}) \right) \\
& \le C'_{\Delta} \sum_{v' \ge 0} \frac{1}{2^{v'}} \left( \sqrt{p \log \left( \frac{n 2^{v'}}{r \delta} \right)} + \log \left( \frac{n 2^{v'}}{r \delta} \right) \right) \\
& \le C''_{\Delta} \left( \sqrt{p \log \left( \frac{n}{r \delta} \right)} + \log \left( \frac{n}{r \delta} \right) \right),
\end{aligned}
$$

where $C'_{\Delta}, C''_{\Delta}$ are large absolute constants. Hence, letting $\bar{c}_{\text{conc}} = C'_{N} + C''_{\Delta}$ we obtain

$$ \xi_N^{(d)} \cap \xi_{\Delta}^{(d)} \subset \xi_2^{(d)}, $$

which must be of probability higher than $1 - 2\delta$. $\square$

*Proof of Lemma 11.* Since the mesh of the grid $N_u$ is equal to $2^{\kappa_1 - u} \le \frac{n}{2^u}$, there exists $(\tilde{l}, \tilde{r}) \in N_u$ such that

$$ |l - \tilde{l}| \le \frac{n}{2^u} \quad \text{and} \quad |r - \tilde{r}| \le \frac{n}{2^u} \square $$

*Proof of Lemma 12.* Let us write

$$ \varepsilon^T A \varepsilon = \sum_{l-r \le i,j < l+r} a_{ij} \langle \varepsilon_i, \varepsilon_j \rangle \quad \text{and} \quad \varepsilon^T B \varepsilon = \sum_{m_1 \le i,j < m_2} b_{ij} \langle \varepsilon_i, \varepsilon_j \rangle, $$

where $m_1 = \min(l-r, l'-r')$, $m_2 = \max(l+r, l'+r')$. Remark that for all $i, j$ in $[l-r, l+r)$, $a_{ij} \le 2$. This gives the first inequality.

For the second inequality, assume without loss of generality that $l \le l'$. As for the first inequality, $b_{ij} \le 2$ for all $i, j \in [m_1, m_2)$. Remark that $b_{ij}$ can be non zero only if $(i, j)$ is in one of the following cases:

1. $i$ or $j$ is in $[\min(l+r, l'+r'), \max(l+r, l'+r')]$

2. $i$ or $j$ is in $[\min(l-r, l'-r'), \max(l-r, l'-r')]$

3. $i$ or $j$ is in $[l, l')$.

Hence there is at most $(4(|l-l'| + |r-r'|) + 2|l-l'|)(r+r' + |l-l'|)$ non zero $b_{ij}$, and we obtain the second inequality. $\square$
Taking a union bound over all high-energy change-points, we deduce from Theorem 1 that, with probability higher than $1 - \delta$, $\hat{\tau}$ achieves (NoSp) and detects all high-energy change-points. Besides, the localization error (25) is a consequence of the definition (48) together with Theorem 1. $\square$

<figure><img src="image_15.png" /></figure>

**Proof of Proposition 6.** As in the proof of Theorem 2, we only consider a specific setting where one aims at testing $K = 0$ with $\Sigma_1 = I_p$ versus $K = 2$ with $\tau_1 \in (n/4; 3n/4)$, $\tau_2 = \tau_1 + r$, $\Sigma_1 = \Sigma_{\tau_2} = I_p$ and $\Sigma_{\tau_1} = I_p + \zeta uu^T$ for some unknown unit vector $u$ in $\mathbb{R}^p$. Obviously, we have $r_1 = r_2 = r$ and $\|\Sigma_{\tau_1} - \Sigma_{\tau_0}\|_{op} = \|\Sigma_{\tau_2} - \Sigma_{\tau_1}\|_{op} = \zeta$ so that it suffices to prove that the sum of the type I and type II error probabilities of any test of these hypotheses is bounded away from zero. We consider two subcases:

**Case 1:** $\zeta \le c' \sqrt{p/r} \wedge \frac{1}{\sqrt{2}}$. Then, we focus on the specific alternative hypothesis where $\tau_1 = \lfloor n/2 \rfloor$ and $\tau_2 = \tau_1 + r$, so that the problem reduces exactly to testing whether the covariance matrix $\Sigma$ of a $r$-sample satisfies $\Sigma = I_p$ or whether $\Sigma = I_p + \zeta uu^T$. This hypothesis testing problem for covariance matrices is well understood. In particular, one can deduce from Theorem 5.1 in [3] that, as soon as $\zeta \le c'[\sqrt{p/r} \wedge 1]$, for some $c'$ sufficiently small, one has

$$ \inf_{\hat{\tau}} \sup_{\Theta \in \bar{\mathcal{P}}(r, \zeta)} \mathbb{P}_{\Theta}(\hat{K} \neq K) \geq \frac{1}{4}. $$

**Case 2:** $\zeta \le c' \sqrt{\log(n/r)/r} \wedge 1/\sqrt{2}$. Here, we consider another specific class of alternative hypotheses where we fix $u = (1, 0, \dots, 0)$ but $\tau_1$ can take different values, i.e. $\tau_1 \in \{\lfloor n/4 \rfloor, \lfloor n/4 \rfloor + r, \dots, \lfloor n/4 \rfloor + r \lfloor n/2r \rfloor \}$. It turns out that this is equivalent to a univariate variance testing problem where one observes $q = \lfloor n/(2r) \rfloor$ samples of size $r$ with distributions $\mathcal{N}(0, \sigma_1^2)$, $\dots$, $\mathcal{N}(0, \sigma_q^2)$. Under the null, we have $\sigma_1 = \sigma_2 = \dots = \sigma_q = 1$. Under the alternative, for some $j \in [q]$, we have $\sigma_j = \sqrt{1 + \zeta}$ and $\sigma_l = 1$ for $l \neq j$. For $j = 1, \dots, q$, write $\mathbb{P}_j$ for the distributions of the $j$-th sample of size $r$ when $\sigma_j^2 = 1 + \zeta$ and $\sigma_l = 1$ for $l \neq j$. Besides, we write $L_j$ for the corresponding likelihood ratio with the null distribution $\mathbb{P}_0$. Then, the mixture distribution is defined as $\bar{\mathbb{P}} = \frac{1}{q} \sum_{j=1}^q \mathbb{P}_j$ whereas $\bar{L}$ stands for the mean likelihood ratio. Following the classical path of Le Cam's method we obtain that, for any test $T$,

$$ \mathbb{P}_0[T=1] + \sup_{j=1,\dots,q} \mathbb{P}_j[T=0] \ge \mathbb{P}_0[T=1] + \bar{\mathbb{P}}[T=0] \ge 1 - \|\mathbb{P}_0 - \bar{\mathbb{P}}\|_{TV}, $$

where $\|\cdot\|_{TV}$ is the total variation norm. Using Cauchy-Schwarz inequality, we bound this total variation distance between the covariates

$$ \| \mathbb{P}_0 - \bar{\mathbb{P}} \|_{TV} \le \mathbb{E}_0 [\bar{L}^2] - 1 = \frac{1}{q} (\mathbb{E}_0 [L_i^2] - 1) = \frac{1}{q} \left[ (1 - \zeta^2)^{-r/2} - 1 \right] \le \frac{1}{q} \left[ e^{r\zeta^2} - 1 \right], $$

since $\zeta \in (0, 1/2)$. As a consequence, we derive that $\|\mathbb{P}_0 - \bar{\mathbb{P}}\|_{TV} \le 1/4$ as long as $r\zeta^2 \le c' \log(q) \wedge 1$. The result follows. $\square$

<figure><img src="image_16.png" /></figure>

**Proof of Proposition 7.** The proof is based on an application of Dvoretzky-Kiefer-Wolfowitz (DKW) inequality [4] together with an union bound. For a $q$ sample of a univariate distribution with empirical distribution function $\hat{F}$ and true distribution function $F$, DKW inequality ensures that

$$ \mathbb{P} \left[ \| \hat{F} - F \|_{\infty} \ge \sqrt{\frac{x}{2q}} \right] \le 2e^{-x}. $$
Proof of Lemma 13. The probability of $(\xi_N^{(d)})^c$ can be written as:

$$ \mathbb{P}((\xi_N^{(d)})^c) = \mathbb{P}\left(\exists u \ge 0, \exists(l,r) \in N_u \text{ s.t. } r \le 3\frac{n}{2^u} \text{ and } \left\|\|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2 - 2r\sigma^2p\right\| \le C_N r \left(\sqrt{p\log(2^u\delta^{-1})} + \log(2^u\delta^{-1})\right)\right). $$

First, fix $u \ge 0$ and $(l,r) \in N_u$ such that $r \le 3\frac{n}{2^u}$.

Applying the first inequality of Lemma 12 and the Hanson-Wright inequality – see Lemma 10, we obtain for all $t \ge 0$

$$ \mathbb{P}\left(\left\|\varepsilon_{l,+r} - \varepsilon_{l,-r}\right\|^2 - 2r\sigma^2p \ge t\right) \le 2\exp\left(-c\min\left(\frac{t^2}{pr^2}, \frac{t}{r}\right)\right), $$

where $c$ is an absolute constant. Choosing

$$ t = C_N r \left(\sqrt{p \log (2^u \delta^{-1})} + \log (2^u \delta^{-1})\right), $$

we obtain

$$ \mathbb{P}\left(\left\|\varepsilon_{l,+r} - \varepsilon_{l,-r}\right\|^2 - 2r\sigma^2p \le C_N r \left(\sqrt{p \log (2^u \delta^{-1})} + \log (2^u \delta^{-1})\right)\right) \\ \le C \left(\frac{1}{2^u}\right)^{cC_N} \delta^{cC_N}, $$

where $c, C$ are absolute constants. Since the cardinal of $N_u$ is upper bounded by $2^{2u+2}$, A union bound on each $N_u$ for each $u \ge 0$ gives:

$$ \mathbb{P}((\xi_N^{(d)})^c) \le \sum_{u \ge 0} C |N_u| \left(\frac{1}{2^u}\right)^{cC_N} \delta^{cC_N} \\ \le \sum_{u \ge 0} 4C \left(\frac{1}{2^u}\right)^{2-cC_N} \delta^{cC_N}, $$

which is convergent. For $C_N$ large enough, we obtain $\mathbb{P}(\xi_N^c) \le 1 - \delta$. $\square$

Proof of Lemma 14.

$$ \mathbb{P}((\xi_{\Delta}^{(d)})^c) = \mathbb{P}\left(\exists v \ge 0, \exists((l,r), (l', r')) \in N_v \times N_{v+1} \text{ s.t. } |l-l'| + |r-r'| \le 4\frac{n}{2^v} \text{ and } (\xi_{\Delta,v}^{(d)}(l,r,l',r'))^c \text{ holds}\right). $$

First fix $v \ge 0$ and $((l,r), (l', r')) \in N_v \times N_{v+1}$. Remark that by definition of $N_v$,

$$ r \ge \frac{n}{2^{v+1}}. $$
Applying two-times DKW inequality to each statistic $T_{l,r}$ such that no-change-point occurs on $(l-r, l+r)$, we deduce that, setting $c_1$ sufficiently larger, the FWER of $(T_{l,r})$ is at most $\delta/2$ by summing the probabilities over all scales $r \in \mathcal{R}$ and by a union bound on all $l \in \mathcal{D}_r$.

Turning to the high-energy change points, we consider $\tau_k$ satisfying (26). Let $\bar{r}_k$ be the smallest radius $r \in \mathcal{R}$ such that

$$r \|F_{\tau_k} - F_{\tau_{k-1}}\|_{\infty}^2 \ge 0.25c_1 \frac{\log\left(\frac{n}{r\delta}\right)}{m}, \quad (49)$$

and consider the closest location $l \in \mathcal{D}_r$ of $\tau_k$ so that $|l - \tau_k| \le r/2$ and $2r \le r_k$. To ease the notation, we still write $r$ for $\bar{r}_k$. As in the proof of Proposition 5, we decompose the statistic

$$\sum_{t=l}^{l+r-1} \hat{F}_t - \sum_{t=l-r}^{l-1} \hat{F}_t = \sum_{t=l}^{l+r-1} \hat{F}_t - \sum_{t=l-r}^{\tau_k-1} \hat{F}_t - \sum_{t=\tau_k}^{l-1} \hat{F}_t,$$

and apply DKW inequality to each of three sums. Taking the union bound over all possible $T_{l,r}$ we deduce that, with probability higher than $1 - \delta/2$

$$r^{-1} \left\| \sum_{t=l}^{l+r-1} \hat{F}_t - \sum_{t=l-r}^{l-1} \hat{F}_t \right\|_{\infty} \ge \frac{1}{2} \|F_{\tau_k} - F_{\tau_{k-1}}\|_{\infty} - c'' \sqrt{\frac{\log(4n/r\delta)}{mr}},$$

so that in view of Condition (49) implies that $T_{l,r} = 1$. Applying Theorem 1 allows us to conclude. □

*Proof of Proposition 8.* As in the proof of Proposition 6, we focus on a simpler testing problem. Write $U$ for the cumulative distribution function of the uniform distribution on $[0, 1]$, i.e. $U(x) = x$ for any $x \in [0, 1]$. Given $\zeta \in (0, 1/4)$, we define the cumulative distribution function $U_{\zeta}$ by $U_{\zeta}(x) = (1 + 2\zeta)x$ for $x \in [0, 1/2]$ and $U_{\zeta}(x) = (1/2 + \zeta) + (1 - 2\zeta)(x - 1/2)$ for $x \in [1/2, 1]$. Note that $\|U_{\zeta} - U\|_{\infty} = \zeta$.

We focus on a testing problem where, under the null, $F_t = U$ for all $t = 1, \dots, n$, whereas under the alternative there exists $\tau_1 \in \{\lfloor n/4 \rfloor, \lfloor n/4 \rfloor + r, \dots, \lfloor n/4 \rfloor + (r-1)\lfloor n/(2r) \rfloor\}$ such that $F_t = U_{\zeta}$ for $t = \tau_1, \dots, \tau_1 + r - 1$ and $F_t = U$ otherwise. Defining $q = \lfloor n/(2r) \rfloor$, we observe that this amounts to testing whether $q$ samples of size $rm$ are distributed according to the null distribution or whether exactly one of them is distributed according to $U_{\zeta}$. Arguing again in the proof of Proposition 6, we only need to bound the total variation distance between the distribution $\mathbb{P}_0$ under the null and the mixture distribution $q^{-1} \sum_{j=1}^q \mathbb{P}_j$ of the $q$ possible alternatives - here $\mathbb{P}_0 = \otimes_{k=1}^q U^{\otimes(rm)}$ is the distribution of the samples when $F_t = U$ and $\mathbb{P}_j = [\otimes_{k=1}^{j-1} U^{\otimes(rm)}] \otimes U_{\zeta}^{\otimes(rm)} \otimes [\otimes_{k=j+1}^q U^{\otimes(rm)}]$, is for $j \ge 1$ the distribution of the samples when $F_t = U$ except for $t \in [jr, (j+1)r)$, in which case $F_t = U_{\zeta}$.

Let $z$ be a uniform random variable over $[0, 1]$ and $w$ be an independent Bernoulli random variable with parameter $1/2$. Then, one easily checks that $z/2 + w/2$ is uniformly distributed on $[0, 1]$. If $w$ is a Bernoulli random variable with parameter $1/2 - 2\zeta$, then one easily checks that the cumulative distribution function of $z/2 + w/2$ is $F_{\zeta}$. As a consequence, by a standard data-processing inequality [47], one derives that

$$\|\mathbb{P}_0 - q^{-1} \sum_{j=1}^{q} \mathbb{P}_j\|_{TV} \le \|\tilde{\mathbb{P}}_0 - q^{-1} \sum_{j=1}^{q} \tilde{\mathbb{P}}_j\|_{TV},$$

where under $\tilde{\mathbb{P}}_0$ one observes $q$ independent Binomial random variables with parameter $(mr, 1/2)$, whereas under $\tilde{\mathbb{P}}_j$, the $j$-th observation follows a Binomial distribution with parameter $(mr, 1/2 -$
Thus,

$$r + r' + |l - l'| \le 2r + |l - l'| + |r - r'| \le 10r.$$

Then by Lemma 12, letting $B$ be the matrix such that
$$\varepsilon^T B \varepsilon = \|\varepsilon_{l',+r'} - \varepsilon_{l',-r'}\|^2 - \|\varepsilon_{l,+r} - \varepsilon_{l,-r}\|^2,$$ we obtain

$$\|B\|^2 \le \|B\|_F^2 \le 40r \frac{n}{2^v}.$$

Thus, by the Hanson Wright inequality – see Lemma 10,

$$\mathbb{P} \left( |\varepsilon^T B_u \varepsilon - \mathbb{E}[\varepsilon^T B_u \varepsilon]| \ge t \right) \le 2 \exp \left( -c \min \left( \frac{2^v}{pnr} t^2, \sqrt{\frac{2^v}{nr}} t \right) \right).$$

From now on, we choose

$$t = C_{\Delta} \sqrt{\frac{rn}{2^v}} \left( \sqrt{p \log (2^v \delta^{-1})} + \log (2^v \delta^{-1}) \right).$$

There are at most $2^{4v+6}$ elements in $N_v \times N_{v+1}$. Therefore, a union bound on $v \ge 0$ and $N_v \times N_{v+1}$ gives

$$\begin{aligned}
\mathbb{P} \left( (\xi_{\Delta}^{(d)})^c \right) &\le \sum_{u \ge 0} 2 |N_v \times N_{v+1}| (2^v)^{-cC_{\Delta}} \delta^{cC_{\Delta}} \\
&\le \sum_{u \ge 0} 2^7 (2^v)^{4-cC_{\Delta}} \delta^{cC_{\Delta}} \\
&\le C \delta^{cC_{\Delta}},
\end{aligned}$$

where the last inequality holds if $C_{\Delta}$ is large enough, for $c, C$ universal constants.

□

### B.3.2. Proof of Proposition 4

**Step 1: Introduction of useful high probability events** Let $s \le p$ and consider $S \in \bar{C}_p^s$. In what follows and for an vector $u \in \mathbb{R}^p$, we write $u^{(S)}$ for the vector $u$ restricted to the set $S$.

Remark that by a simple computation, the noise can be decomposed as follows:

$$\begin{aligned}
& \frac{r}{2} \left[ \| \bar{y}_{l,+r}^{(S)} - \bar{y}_{l,-r}^{(S)} \|^2 - \| \bar{\theta}_{l,-r}^{(S)} - \bar{\theta}_{l,+r}^{(S)} \|^2 \right] - \sigma^2 s \\
= & r \langle \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)}, \bar{\theta}_{l,+r}^{(S)} - \bar{\theta}_{l,-r}^{(S)} \rangle + \frac{r}{2} \| \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)} \|^2 - \sigma^2 s .
\end{aligned}$$

The first term written as

$$r \langle \bar{\varepsilon}_{l,+r}^{(S)} - \bar{\varepsilon}_{l,-r}^{(S)}, \bar{\theta}_{l,+r}^{(S)} - \bar{\theta}_{l,-r}^{(S)} \rangle,$$

is a crossed term between the noise and the mean vector $\theta$. Lemma 8 states that for $l$ equal to a true change-point $\tau_k$, $r$ of order $r_k^*$, and $S$ being the corresponding support of the change-point, it is controlled on event $\xi_1^{(p)}$ with high probability.
2ζ). Using Cauchy-Schwarz inequality, we upper bound the square of the total variation distance by the χ² distance and then compute it explicitly. This leads us to

$$ \|\tilde{\mathbb{P}}_0 - q^{-1} \sum_{j=1}^{q} \tilde{\mathbb{P}}_j\|_{TV}^2 \le \frac{1}{q} [(1 + 16\zeta^2)^{rm} - 1] , $$

which is smaller than 1/4 provided that $16rm\zeta^2 \le \log(q/4 + 1)$. If we choose c' small enough in the statement of the proposition, this last condition holds and the result follows. □

## References

[1] Sylvain Arlot, Alain Celisse, and Zaid Harchaoui. A kernel multiple change-point algorithm via model selection. *J. Mach. Learn. Res.*, 20, 2019.

[2] Rafal Baranowski, Yining Chen, and Piotr Fryzlewicz. Narrowest-over-threshold detection of multiple change points and change-point-like features. *Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, 81(3):649–672, 2019.

[3] Quentin Berthet and Philippe Rigollet. Optimal detection of sparse principal components in high dimension. *Annals of Statistics*, 41(4):1780–1815, 2013.

[4] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. *Concentration inequalities*. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux.

[5] Hock-Peng Chan and Hao Chen. Multi-sequence segmentation via score and higher-criticism tests. *arXiv preprint arXiv:1706.07586*, 2017.

[6] Hock Peng Chan, Guenther Walther, et al. Optimal detection of multi-sample aligned sparse signals. *Annals of Statistics*, 43(5):1865–1895, 2015.

[7] Haeran Cho and Claudia Kirch. Data segmentation algorithms: Univariate mean change and beyond. *Econometrics and Statistics*, 2021.

[8] Lynna Chu and Hao Chen. Asymptotic distribution-free change-point detection for multivariate and non-euclidean data. *The Annals of Statistics*, 47(1):382–414, 2019.

[9] Holger Dette, Josua Gösmann, et al. Relevant change points in high dimensional time series. *Electronic Journal of Statistics*, 12(2):2578–2636, 2018.

[10] Holger Dette, Guangming Pan, and Qing Yang. Estimating a change point in a sequence of very high-dimensional covariance matrices. *Journal of the American Statistical Association*, pages 1–11, 2020.

[11] David Donoho and Jiashun Jin. Higher criticism for detecting sparse heterogeneous mixtures. *Ann. Statist.*, 32(3):962–994, 2004.

[12] Farida Enikeeva and Zaid Harchaoui. High-dimensional change-point detection under sparse alternatives. *Ann. Statist.*, 47(4):2051–2079, 2019.

[13] Klaus Frick, Axel Munk, and Hannes Sieling. Multiscale change point inference. *Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, 76(3):495–580, 2014.

[14] Piotr Fryzlewicz. Wild binary segmentation for multiple change-point detection. *The Annals of Statistics*, 42(6):2243–2281, 2014.

[15] Piotr Fryzlewicz. Tail-greedy bottom-up data decompositions and fast multiple change-point detection. *The Annals of Statistics*, 46(6B):3390–3421, 2018.

[16] Damien Garreau and Sylvain Arlot. Consistent change-point detection with kernels. *Electron. J. Stat.*, 12(2):4440–4486, 2018.

[17] Alex J Gibberd and Sandipan Roy. Multiple changepoint estimation in high-dimensional gaussian graphical models. *arXiv preprint arXiv:1712.05786*, 2017.
**Lemma 15.** For $k \in [K]$, let us write $S_k \subset [K]$ for the support of $\mu_k - \mu_{k-1}$. Assume that $c_0$ is a large enough universal constant. The event

$$ \xi_1^{(p)} := \xi_1^{(p)}(\delta) = \left\{ \forall k \in [K] \text{ s.t. Equation (18) holds for } k, \right. \\ \left. \bar{r}_k^{(d)} \left| \begin{array}{l} \langle \bar{\epsilon}^{(S_k)}_{\tau_k, +\bar{r}_k^{(d)}} - \bar{\epsilon}^{(S_k)}_{\tau_k, -\bar{r}_k^{(s)}}, \bar{\theta}^{(S_k)}_{\tau_k, +\bar{r}_k^{(s)}} - \bar{\theta}^{(S_k)}_{\tau_k, -\bar{r}_k^{(s)}} \rangle \\ \left| \frac{\bar{r}_k^{(d)}}{4} \left\| \bar{\theta}_{\tau_k, +\bar{r}_k^{(s)}} - \bar{\theta}_{\tau_k, -\bar{r}_k^{(s)}} \right\|^2 \end{array} \right| \right\} $$

holds with probability higher than $1 - \delta$.

The proof of this lemma follows directly from the one of Lemma 8, restricting the term corresponding to change-point $k$ to $S_k$ – and diminishing the deviation by doing so.

The second term written as

$$ \frac{r}{2} \left\| \bar{\epsilon}_{l,+r}^{(S)} - \bar{\epsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s $$

is a term of pure noise. Lemma 16 states that it is controlled on event $\xi_2^{(p)}(S)$ with high probability.

**Lemma 16.** There exists a constant $\bar{c}_{\text{conc}} > 0$ such that the event

$$ \xi_2^{(p)}(S) := \xi_2^{(p)}(S, \delta) = \left\{ \begin{array}{l} \forall (l,r) \in J_n, \left| \frac{r}{2} \left\| \bar{\epsilon}_{l,+r}^{(S)} - \bar{\epsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s \right| \\ \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{s \log\left(\frac{n}{r\delta_s}\right)} + \log\left(\frac{n}{r\delta}\right) \right) \end{array} \right\} $$

holds with probability higher than $1 - 2\delta$.

The proof of this lemma is exactly the same as the one of Lemma 9, restricting all vectors to $S$.

Set $\delta_s = \delta/(2^s \binom{p}{s})$. Lemma 16 implies that with probability larger than $1-2\delta$, $\forall (l,r) \in J_n, \forall S \subset [p]$

$$ \left| \frac{r}{2} \left\| \bar{\epsilon}_{l,+r}^{(S)} - \bar{\epsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s \right| \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{s \log \left( \frac{n}{r\delta_s} \right)} + \log \left( \frac{n}{r\delta_s} \right) \right). $$

And so since $\binom{p}{s} \le \binom{ep}{s}^s$, we have probability larger than $1 - 2\delta, \forall (l,r) \in J_n, \forall S \subset [p]$

$$ \begin{aligned} & \left| \frac{r}{2} \left\| \bar{\epsilon}_{l,+r}^{(S)} - \bar{\epsilon}_{l,-r}^{(S)} \right\|^2 - \sigma^2 s \right| \\ & \le \bar{c}_{\text{conc}} L^2 \left( \sqrt{s \log \left( \frac{n}{r\delta} \right) + s \log \left( \frac{2ep}{s} \right)} + \log \left( \frac{n}{r\delta} \right) + s \log \left( \frac{2ep}{s} \right) \right) \\ & \le 4 \bar{c}_{\text{conc}} L^2 \left( \log \left( \frac{n}{r\delta} \right) + s \log \left( \frac{2ep}{s} \right) \right). \end{aligned} $$
[18] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. *The Journal of Machine Learning Research*, 13(1):723–773, 2012.

[19] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In *The Collected Works of Wassily Hoeffding*, pages 409–426. Springer, 1994.

[20] Shouri Hu, Jingyan Huang, Hao Chen, and Hock Peng Chan. Sparsity likelihood for sparse signal and change-point detection. *arXiv preprint arXiv:2105.07137*, 2021.

[21] Moritz Jirak. Uniform change point tests in high dimension. *The Annals of Statistics*, 43(6):2451–2483, 2015.

[22] Laura Jula Vanegas, Merle Behr, and Axel Munk. Multiscale quantile segmentation. *Journal of the American Statistical Association*, pages 1–14, 2021.

[23] Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. *Bernoulli*, 23(1):110–133, 2017.

[24] Solt Kovács, Housen Li, Peter Bühlmann, and Axel Munk. Seeded binary segmentation: A general methodology for fast and optimal change point detection. *arXiv preprint arXiv:2002.06633*, 2020.

[25] Solt Kovács, Housen Li, Lorenz Haubner, Axel Munk, and Peter Bühlmann. Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries. *arXiv preprint arXiv:2010.10194*, 2020.

[26] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. *Annals of Statistics*, 28(5):1302–1338, 2000.

[27] Housen Li, Qinghai Guo, Axel Munk, et al. Multiscale change-point segmentation: Beyond step functions. *Electronic Journal of Statistics*, 13(2):3254–3296, 2019.

[28] Haoyang Liu, Chao Gao, and Richard J Samworth. Minimax rates in sparse, high-dimensional changepoint detection. *arXiv preprint arXiv:1907.10012*, 2019.

[29] Amit Moscovich, Boaz Nadler, and Clifford Spiegelman. On the exact berk-jones statistics and their *p*-value calculation. *Electronic Journal of Statistics*, 10(2):2329–2354, 2016.

[30] AS Nemirovskiy. Nonparametric estimation of smooth regression function. *Soviet Journal of Computer and Systems Sciences*, 23(6):1–11, 1985.

[31] Yue S Niu, Ning Hao, and Heping Zhang. Multiple change-point detection: A selective overview. *Statistical Science*, 31(4):611–623, 2016.

[32] Adam B Olshen, ES Venkatraman, Robert Lucito, and Michael Wigler. Circular binary segmentation for the analysis of array-based dna copy number data. *Biostatistics*, 5(4):557–572, 2004.

[33] Oscar Hernan Madrid Padilla, Yi Yu, Daren Wang, and Alessandro Rinaldo. Optimal non-parametric change point detection and localization. *arXiv preprint arXiv:1905.10019*, 2019.

[34] Alessandro Rinaldo, Daren Wang, Qin Wen, Rebecca Willett, and Yi Yu. Localizing changes in high-dimensional regression models. In *International Conference on Artificial Intelligence and Statistics*, pages 2089–2097. PMLR, 2021.

[35] Mark Rudelson and Roman Vershynin. Hanson-wright inequality and sub-gaussian concentration. *Electronic Communications in Probability*, 18, 2013.

[36] Charles Truong, Laurent Oudre, and Nicolas Vayatis. Selective review of offline change point detection methods. *Signal Processing*, 167:107299, 2020.

[37] Roman Vershynin. *High-dimensional probability: An introduction with applications in data science*, volume 47. Cambridge university press, 2018.

[38] Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, and Patricia Reynaud-Bouret. Optimal Change-Point Detection and Localization. *arXiv preprint arXiv:2010.11470*, 2020.

[39] Abraham Wald. Sequential tests of statistical hypotheses. *The annals of mathematical statis-