Thanks to (99), and since $\tau_l - \tau_k^* \le \tau_k^* - \tau_{l-1}$, we arrive at

$$ \mathbf{E}(t) \le 6 \left[ \omega_1 \sqrt{\frac{\tau_k^* - \tau_{l-1}}{\tau_l - \tau_k^*}} + \omega_2 \sqrt{\frac{\tau_{l+1} - \tau_{k+1}^*}{\tau_{l+1} - \tau_k^*}} \right]. $$

Write $z_1 = \frac{\tau_l - \tau_k^*}{\tau_k^* - \tau_{l-1}} \ge 1$ and $z_2 = \frac{\tau_{l+1} - \tau_k^*}{\tau_{l+1} - \tau_{k+1}^*} \ge 1$. We then come back to the definition of $\omega_1$ and $\omega_2$

$$ \begin{aligned} \mathbf{E}(t) & \le 12\ell [\psi_q[\delta(\tau_k^*, \tau_l, \tau_{l+1})] + \psi_q[\delta(\tau_{l-1}, \tau_l, \tau_{k+1}^*)]] + 4\sqrt{2L} \left[ \sqrt{\frac{\log(1+z_1)}{z_1}} + \sqrt{\frac{\log(1+z_2)}{z_2}} \right] \\ & \le 12\ell [\psi_q[\delta(\tau_k^*, \tau_l, \tau_{l+1})] + \psi_q[\delta(\tau_{l-1}, \tau_l, \tau_{k+1}^*)]] + 12\sqrt{L}. \end{aligned} $$

Then, we use the definition (77) of $\psi_q$.

$$ \psi_q^2[\delta(\tau_k^*, \tau_l, \tau_{l+1})] \le 2 \log \left( \frac{n(\tau_{l+1} - \tau_k^*)}{(\tau_{l+1} - \tau_l)(\tau_l - \tau_k^*)} \right) + q \le 2 \log(2) + \psi^2[\delta(t)] , $$

since $\tau_l - \tau_k^* \ge (\tau_l - \tau_{l-1})/2$. Besides,

$$ \psi_q^2[\delta(\tau_{l-1}, \tau_l, \tau_{k+1}^*)] \le 2 \log \left( \frac{3n}{\tau_l - \tau_{l-1}} \right) + q \le 2 \log(2) + \psi^2[\delta(t)] , $$

since $\tau_{k+1}^* - \tau_l \ge (\tau_l - \tau_{l-1})/2$. We conclude that

$$ \mathbf{E}(t) \le 24\ell \psi_q[\delta(t)] + 24\ell \sqrt{2\log(3)} + 12\sqrt{L}, $$

which is smaller than $\psi_q[\delta(t)][\sqrt{L} - \ell]$ provided that we have chosen $q$ large enough. This shows (96) and concludes the main part of the proof for general $k$.

It remains to consider the cases $k=1$ and $k=K$. By symmetry, we focus on the case $k=1$. Suppose that $[2; (\tau_1^* + \tau_2^*)/2]$ contains two change-points $\tau_1$ and $\tau_2$. The case $\tau_2 \le \tau_1^*$ has already been handled in Lemma 11. The case $\tau_1 \ge (1 + \tau_1^*)/2$ has already been considered in the general case. Finally, the case $\tau_1 \le (\tau_1^* + \tau_2^*)/2$ has already been handled in Lemma 13.

*Proof of Lemma 15.* In order to prove the first bound, we simply come back to the definition of the energy. To alleviate notation, we write $\mu'_{l+1} = \bar{\theta}_{\tau_{k+1}^*; \tau_{l+1}}$ and $\mu'_l = \bar{\theta}_{\tau_{l-1}^*; \tau_k^*}$.

$$ \begin{aligned} \mathbf{E}^2[\tau_k^*, \tau_l, \tau_{l+1}] & = \left( \mu'_{l+1} \frac{\tau_{l+1} - \tau_{k+1}^*}{\tau_{l+1} - \tau_l} + \mu_{k+1} \frac{\tau_{k+1}^* - \tau_l}{\tau_{l+1} - \tau_l} - \mu_{k+1} \right)^2 \frac{(\tau_{l+1} - \tau_l)(\tau_l - \tau_k^*)}{(\tau_{l+1} - \tau_k^*)} \\ & = (\mu'_{l+1} - \mu_{k+1})^2 \frac{(\tau_{l+1} - \tau_{k+1}^*)^2 (\tau_l - \tau_k^*)}{(\tau_{l+1} - \tau_k^*)(\tau_{l+1} - \tau_l)} \\ & = \mathbf{E}^2[\tau_l, \tau_{k+1}^*, \tau_{l+1}] \frac{(\tau_{l+1} - \tau_{k+1}^*)(\tau_l - \tau_k^*)}{(\tau_{l+1} - \tau_k^*)(\tau_{k+1}^* - \tau_l)} \\ & \le \mathbf{E}^2[\tau_l, \tau_{k+1}^*, \tau_{l+1}] \frac{(\tau_{l+1} - \tau_{k+1}^*)}{(\tau_{l+1} - \tau_k^*)}, \end{aligned} \quad (100) $$

where we used in the last line that $\tau_l$ is closer to $\tau_k^*$ than to $\tau_{k+1}^*$. This proves the first part of (98). Analogously, we obtain

$$ \mathbf{E}^2[\tau_{l-1}, \tau_l, \tau_{k+1}^*] = \mathbf{E}^2[\tau_{l-1}, \tau_k^*, \tau_l] \frac{(\tau_k^* - \tau_{l-1})(\tau_{k+1}^* - \tau_l)}{(\tau_l - \tau_k^*)(\tau_{k+1}^* - \tau_{l-1})} \le \frac{(\tau_k^* - \tau_{l-1})}{(\tau_l - \tau_k^*)} . \quad (101) $$
This proves the second of (98). Multiplying (100) and (101), we obtain the identity in (97). Besides, $\tau_k^* \le \tau_{k+1}^* \le \tau_{l+1}$ and $\tau_{k+1}^* - \tau_{l-1} \ge 3(\tau_k^* - \tau_{l-1})$ since $\tau_k^* - \tau_{l-1} \le \tau_l - \tau_k^* \le \tau_{k+1}^* - \tau_l$. This allows us to recover the upper bound in (97).

Turning to the last bound (99), we also come back to the definition of the energy

$$ 
\begin{aligned}
\mathbf{E}^2(t) \frac{(\tau_{l+1} - \tau_{l-1})}{(\tau_{l+1} - \tau_l)(\tau_l - \tau_{l-1})} &= \left[ \left( \mu'_{l+1} \frac{\tau_{l+1} - \tau_{k+1}^*}{\tau_{l+1} - \tau_l} + \mu_{k+1} \frac{\tau_{k+1}^* - \tau_l}{\tau_{l+1} - \tau_l} \right) - \left( \mu'_{l} \frac{\tau_k^* - \tau_{l-1}}{\tau_l - \tau_{l-1}} + \mu_{k+1} \frac{\tau_l - \tau_k^*}{\tau_l - \tau_{l-1}} \right) \right]^2 \\
&= \left[ (\mu'_{l+1} - \mu_{k+1}) \frac{\tau_{l+1} - \tau_{k+1}^*}{\tau_{l+1} - \tau_l} - (\mu'_{l} - \mu_{k+1}) \frac{\tau_k^* - \tau_{l-1}}{\tau_l - \tau_{l-1}} \right]^2 \\
&\le \left[ \mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_{l+1}) \sqrt{\frac{\tau_{l+1} - \tau_{k+1}^*}{(\tau_{l+1} - \tau_l)(\tau_{k+1}^* - \tau_l)}} + \mathbf{E}(\tau_{l-1}, \tau_k^*, \tau_l) \sqrt{\frac{\tau_k^* - \tau_{l-1}}{(\tau_l - \tau_{l-1})(\tau_l - \tau_k^*)}} \right]^2.
\end{aligned}
$$

This leads us to

$$ 
\begin{aligned}
\mathbf{E}(t) &\le \mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_{l+1}) \sqrt{\frac{(\tau_{l+1} - \tau_{k+1}^*)(\tau_l - \tau_{l-1})}{(\tau_{l+1} - \tau_{l-1})(\tau_{k+1}^* - \tau_l)}} + \mathbf{E}(\tau_{l-1}, \tau_k^*, \tau_l) \sqrt{\frac{(\tau_k^* - \tau_{l-1})(\tau_{l+1} - \tau_l)}{(\tau_l - \tau_k^*)(\tau_{l+1} - \tau_{l-1})}} \\
&\le \mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_{l+1}) \sqrt{2 \frac{\tau_{l+1} - \tau_{k+1}^*}{\tau_{l+1} - \tau_{l-1}}} + \mathbf{E}(\tau_{l-1}, \tau_k^*, \tau_l) \sqrt{\frac{\tau_k^* - \tau_{l-1}}{\tau_l - \tau_k^*}},
\end{aligned}
$$

where we used again $\tau_k^* - \tau_{l-1} \le \tau_l - \tau_k^* \le (\tau_{k+1}^* - \tau_k^*)/2$.

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

## 8.5 Localized analysis (Proof of Propositions 8 and 11)

We still work conditionally to the event $A_{L,q}$ so that the result of Proposition 7 is valid for large $L$ and the result of Proposition 10 is true for $L > 1$. Consider any high-energy change-point $\tau_k^*$. The closest estimated change-point $\hat{\tau}_l$ to $\tau_k^*$ belongs to the interval $[\frac{\tau_{k-1}^* + \tau_k^*}{2}, \frac{\tau_k^* + \tau_{k+1}^*}{2}]$. By symmetry, we may assume that $\hat{\tau}_l > \tau_k^*$, also if the energy $\mathbf{E}_k$ is high enough, Propositions 7 and 10 enforce that $\hat{\tau}_l - \tau_k^* \le (\tau_{k+1}^* - \tau_k^*)/4$. To alleviate the notation, we write $\tau$ for $\hat{\tau}$ in this subsection. We deduce from Lemma 8 that, for $t_1 = (\tau_{l-1}, \tau_k^*, \tau_l)$ and $t_2 = (\tau_k^*, \tau_l, \tau_{l+1})$,

$$ 
\begin{aligned}
\mathrm{Cr}_0(\tau^{(-l,k)}, \mathbf{Y}) - \mathrm{Cr}_0(\tau, \mathbf{Y}) &= -((-1)^{\mathrm{sign}(\Delta_{t_1})} \mathbf{E}(t_1) - \mathbf{N}(t_1))^2 + ((-1)^{\mathrm{sign}(\Delta_{t_2})} \mathbf{E}(t_2) - \mathbf{N}(t_2))^2 \\
&\quad + L\psi_q^2(\delta(t_1)) - L\psi_q^2(\delta(t_2))
\end{aligned}
$$

This difference is non-negative since $\tau$ minimizes the criterion $\mathrm{Cr}_0$. This implies that

$$ [\mathbf{E}(t_1) - |\mathbf{N}(t_1)|]_+^2 \le [\mathbf{E}(t_2) + |\mathbf{N}(t_2)|]^2 + L(\psi_q^2(\delta(t_1)) - \psi_q^2(\delta(t_2))) . \quad (102) $$

First, we control the energies $\mathbf{E}(t_1)$ and $\mathbf{E}(t_2)$.

**Lemma 16.** The energy $\mathbf{E}(t_1)$ satisfies

$$ \mathbf{E}^2(t_1) \ge [\tau_l - \tau_k^*] \left[ \frac{\mathbf{E}_k^2}{16(\tau_{k+1}^* - \tau_l)} \vee \frac{\Delta_k^2}{8} \right]. $$
Turning to $\mathbf{E}(t_2)$, we have $\mathbf{E}(t_2) = 0$ if $\tau_{l+1} \le \tau_{k+1}^*$. If $\tau_{l+1} > \tau_{k+1}^*$, then, since $\tau_{k+1}^*$ is not a $(\sqrt{L} + \sqrt{l}, q, \tau^{(k+1)})$-high energy change-point, we get

$$
\begin{align*}
\mathbf{E}^2(t_2) &= [\tau_l - \tau_k^*](\overline{\theta}_{\tau_{k+1}:\tau_{l+1}} - \mu_{k+1})^2 \frac{(\tau_{l+1} - \tau_{k+1}^*)^2}{(\tau_{l+1} - \tau_l)(\tau_{l+1} - \tau_k^*)} \\
&\le \frac{(\tau_l - \tau_k^*)(\tau_{l+1} - \tau_{k+1}^*)}{(\tau_{k+1}^* - \tau_l)(\tau_{l+1} - \tau_k^*)} (\sqrt{L} + \sqrt{l})^2 \psi_q^2(\delta(\tau_l, \tau_{k+1}^*, \tau_{l+1})) \\
&\stackrel{(a)}{\le} \frac{\tau_l - \tau_k^*}{\tau_{k+1}^* - \tau_l} (\sqrt{L} + \sqrt{l})^2 \left[ 2 \log \left( \frac{n(\tau_{l+1} - \tau_l)}{(\tau_{l+1} - \tau_k^*)(\tau_{k+1}^* - \tau_l)} \right) + q \right] \\
&\stackrel{(b)}{\le} \frac{\tau_l - \tau_k^*}{\tau_{k+1}^* - \tau_l} (\sqrt{L} + \sqrt{l})^2 \left[ 2 \log \left( \frac{n}{\tau_{l+1} - \tau_k^*} \right) + q \right] \\
&\le \frac{\tau_l - \tau_k^*}{\tau_{k+1}^* - \tau_l} (\sqrt{L} + \sqrt{l})^2 \left[ 2 \log \left( \frac{n}{\tau_{k+1}^* - \tau_k^*} \right) + q \right] \\
&\stackrel{(c)}{\le} \frac{\tau_l - \tau_k^*}{\tau_{k+1}^* - \tau_l} (\sqrt{L} + \sqrt{l})^2 \psi_q^2 [\delta(\tau_{k-1}^*, \tau_k^*, \tau_{k+1}^*)] ,
\end{align*}
$$

where we used in (a) that $x(\log(t/x)+1) \le \log(t)+1$ for $t \ge 1$ and $x \le 1$, in (b) that $\tau_{k+1}^* \le \tau_l$ and in (c) that $\tau_l$ is closer to $\tau_k^*$ than to $\tau_{k+1}^*$. Together with Lemma 16, we obtain that $\mathbf{E}^2(t_1) \ge 2\mathbf{E}^2(t_2)$ provided $\tau_k^*$ is a $(\sqrt{32}(\sqrt{L} + \sqrt{l}), q)$ high-energy change-point. Since $(x-y)_+^2 \ge 3x^2/4 - 3y^2$ and $(x+y)^2 \le 5/4x^2 + 5y^2$, we deduce from (102) that

$$
\frac{\mathbf{E}^2(t_1)}{8} \le 3\mathbf{N}^2(t_1) + 5\mathbf{N}^2(t_2) + L(\psi_q^2(\delta(t_1)) - \psi_q^2(\delta(t_2))) .
$$

Then, we use Lemma 16 to deduce that

$$
[\tau_l - \tau_k^*] \Delta_k^2 \le c [\mathbf{N}^2(t_1) + 5\mathbf{N}^2(t_2) + L[\psi_q^2(\delta(t_1)) - \psi_q^2(\delta(t_2))]] . \quad (103)
$$

Next, we control the random variables $|\mathbf{N}(t_1)|$ and $|\mathbf{N}(t_2)|$ relying on a non-asymptotic law of iterated logarithms.

**Case 1:** $\tau_{l+1} - \tau_l \ge \tau_l - \tau_k^*$. In that situation, the penalty difference satisfies

$$
\psi_q^2(\delta(t_1)) - \psi_q^2(\delta(t_2)) = 2 \log \left[ \frac{(\tau_l - \tau_{l-1})(\tau_{l+1} - \tau_l)}{(\tau_k^* - \tau_{l-1})(\tau_{l+1} - \tau_k^*)} \right] \le 2 \log \left( \frac{\tau_l - \tau_{l-1}}{\tau_k^* - \tau_{l-1}} \right) \le 2 \log \left( 1 + \frac{\tau_l - \tau_k^*}{\tau_k^* - \tau_{l-1}} \right), \quad (104)
$$

since $\tau_l$ is closer to $\tau_k^*$ than $\tau_{l-1}$.

To control $|\mathbf{N}(t_1)|$ and $|\mathbf{N}(t_2)|$, we apply Lemma 5 to the variables $(Z_{\tau_k^*:\tau'}, \tau' > \tau_k^*)$ and to the variables $(Z_{\tau^’:\tau_k^*}, \tau' < \tau_k^*)$. Since $|\tau_l - \tau_k^*| \le |\tau_k^* - \tau_{l-1}|$, we have, with probability higher than $1 - c e^{-s}$,

$$
\begin{align}
|\mathbf{N}(t_1)| 1_{\Delta_k^2 | \tau_l - \tau_k^*| \ge 1} &\le c \left[ \sqrt{\frac{\tau_k^* - \tau_{l-1}}{\tau_l - \tau_{l-1}}} + \sqrt{\frac{\tau_l - \tau_k^*}{\tau_l - \tau_{l-1}}} \right] \left[ \sqrt{s} + \sqrt{\log \log (\Delta_k^2 |\tau_l - \tau_k^*|)} \right] \nonumber \\
&\le c \left[ \sqrt{s} + \sqrt{\log \log (\Delta_k^2 |\tau_l - \tau_k^*|)} \right] . \tag{105}
\end{align}
$$
Note that $Z_{\tau_l: \tau_{l+1}} = -Z_{\tau_k^*: \tau_l} + Z_{\tau_k^*: \tau_{l+1}}$. Applying again Lemma 5, we derive that, with probability higher than $1 - ce^{-x}$,

$$ 
\begin{aligned}
|Z_{\tau_l: \tau_{l+1}}| 1_{\Delta_k^2 | \tau_l - \tau_k^*| \ge 1} &\le c \sqrt{\tau_{l+1} - \tau_k^*} \left[ \sqrt{\log \log(\Delta_k^2 (\tau_{l+1} - \tau_k^*))} + \sqrt{x} \right] \\
&\le c' \sqrt{\tau_{l+1} - \tau_l} \left[ \sqrt{\log \log(\Delta_k^2 (\tau_{l+1} - \tau_l))} + \sqrt{x} \right],
\end{aligned}
$$

since $\tau_{l+1} - \tau_l \ge \tau_l - \tau_k^*$. We have bounded $Z_{\tau_k^*: \tau_l}$ above. Combining these bounds, we get

$$ 
\begin{aligned}
|\mathbf{N}(t_2)| 1_{\Delta_k^2 | \tau_l - \tau_k^*| \ge 1} &\le c \sqrt{\frac{\tau_{l+1} - \tau_l}{\tau_{l+1} - \tau_k^*}} \left[ \sqrt{x} + \sqrt{\log \log(\Delta_k^2 |\tau_l - \tau_k^*|)} \right] \\
&\quad + c' \sqrt{\frac{\tau_l - \tau_k^*}{\tau_{l+1} - \tau_k^*}} \left[ \sqrt{x} + \sqrt{\log \log(\Delta_k^2 (\tau_{l+1} - \tau_l))} \right] \\
&\le c \left[ \sqrt{x} + \sqrt{\log \log(\Delta_k^2 |\tau_l - \tau_k^*|)} \right].
\end{aligned}
$$

Gathering (102) and (104), we deduce from (103) that

$$ |\tau_l - \tau_k^*| \Delta_k^2 1_{\Delta_k^2 |\tau_l - \tau_k^*| \ge 1} \le c \left[ x + \log \log(\Delta_k^2 |\tau_l - \tau_k^*|) + L \log \left( 1 + \frac{\tau_l - \tau_k^*}{\tau_k^* - \tau_{l-1}} \right) \right] . \quad (106) $$

The expression inside the last logarithm is smaller or equal to 2, which implies that $|\tau_l - \tau_k^*| \Delta_k^2 \le c'(x \vee L)$ with probability higher than $1 - c''e^{-x}$. If we restrict ourselves to $L \le L_0$ (where $L_0$ is the absolute constant introduced in Proposition 7), the above inequality yields

$$ |\tau_l - \tau_k^*| \Delta_k^2 \le c(x \vee 1) . $$

When $L$ is larger than $L_0$ (as in Proposition 7), we know from that proposition that $\tau_k^* - \tau_{l-1} \ge (\tau_k^* - \tau_{k-1})/2$. Since $(\tau_{k+1}^* - \tau_k^*) \Delta_k^2 \ge \mathbf{E}_k^2 \ge \kappa_L \psi_q^2 [\delta(\tau_k^*, \tau_k^*, \tau_{k+1}^*)] \ge 2\kappa_L$ since $q \ge 2$. Then, we deduce from (106) that

$$ |\tau_l - \tau_k^*| \Delta_k^2 1_{\Delta_k^2 |\tau_l - \tau_k^*| \ge 1} \le c \left[ x + L \log \left( 1 + \frac{\Delta^2 (\tau_l - \tau_k^*)}{2\kappa_L} \right) \right] \le c \left[ x + \frac{L}{2\kappa_L} \Delta^2 (\tau_l - \tau_k^*) \right] $$

Provided that we fix $\kappa_L$ in such a way that $\kappa_L \ge cL$ (where $c$ is the same constant as in the above inequality), we conclude that

$$ |\tau_l - \tau_k^*| \Delta_k^2 1_{\Delta_k^2 |\tau_l - \tau_k^*| \ge 1} \le c' [x \vee 1] , $$

with probability higher than $1 - c''e^{-x}$.

**Case 2:** $\tau_{l+1} - \tau_l \le \tau_l - \tau_k^*$. This situation does not arise for large $L \ge L_0$ setting as justified in Proposition 7. We still use the same deviation bound (105) for $|\mathbf{N}(t_1)|$, but we need to rely on a different approach for $\mathbf{N}(t_2)$.

Fix any $q \ge 1$ and $\tau'_q = \tau_k^* 2^q [1/\Delta_k^2]$. Applying Lemma 9 with $n$ replaced by $\tau'_q - \tau_k^*$, we derive that, with probability higher than $1 - x$, we have simultaneously over all $\tau \in [\tau'_q/2; \tau'_q]$

$$ \mathbf{N}^2(\tau_k^*, \tau, \tau'_q) \le 2 \log \left( \frac{(\tau - \tau_k^*)(\tau'_q - \tau_k^*)}{(\tau'_q - \tau)(\tau - \tau_k^*)} \right) + c_1 \log \log \left( \frac{(\tau - \tau_k^*)(\tau'_q - \tau_k^*)}{(\tau'_q - \tau)(\tau - \tau_k^*)x} \right) + c_2 \log \left( \frac{1}{x} \right) + c_3 . $$
Applying an union bound over all $q$, we deduce that, with probability higher than $1-x$,

$$ \mathbf{N}^2(t_2)\mathbf{1}_{(\tau_l - \tau_k^*)\Delta_k^{2*} \ge 1} \le 2\log\left(\frac{\tau_{l+1} - \tau_k^*}{\tau_{l+1} - \tau_l}\right) + c_1 \log\log\left(\frac{\tau_{l+1} - \tau_k^*}{\tau_{l+1} - \tau_l}\right) \\ + c_2 \log\log((\tau_l - \tau_k^*)\Delta_k^2) + c_3 \log\left(\frac{1}{x}\right) + c_4 \quad (107) $$

As for the penalty difference, we have

$$ \psi_q^2(\delta(t_1)) - \psi_q^2(\delta(t_2)) = 2 \log \left[ \frac{(\tau_l - \tau_{l-1})(\tau_{l+1} - \tau_l)}{(\tau_k^* - \tau_{l-1})(\tau_{l+1} - \tau_k^*)} \right] \le 2 \log(2) - 2 \log \left( \frac{\tau_{l+1} - \tau_k^*}{\tau_{l+1} - \tau_l} \right). $$

Since $\mathbf{E}(t_2) = 0$ in that case, it follows from (102) and Lemma 16, we conclude that

$$ |\tau_l - \tau_k^*| \Delta_k^2 1_{\Delta_k^2 |\tau_l - \tau_k^*| \ge 1} \le c [1 + x + L + \log \log (\Delta_k^2 |\tau_l - \tau_k^*|)] \\ + c_1 \log \log \left( \frac{\tau_{l+1} - \tau_k^*}{\tau_{l+1} - \tau_l} \right) - 2(L-1) \log \left( \frac{\tau_{l+1} - \tau_k^*}{\tau_{l+1} - \tau_l} \right). $$

Since $a \log(x) - bx \le a \log(a/(eb))$ for any positive numbers $a, b, x$, the expression in the second line is a most $c[1 + \log((L-1)^{-1})_+]$. Hence, we conclude that

$$ |\tau_l - \tau_k^*| \Delta_k^2 \le c(x \vee 1 + \log((L-1)^{-1})_+) , $$

with probability higher than $1 - ce^{-x}$.

*Proof of Lemma 16.* If $\tau_{l-1} \ge \tau_{k-1}^*$, then the energy expression is simply

$$ \mathbf{E}^2(t_1) = [\tau_l - \tau_k^*] \Delta_k^2 \frac{(\tau_k^* - \tau_{l-1})}{(\tau_l - \tau_{l-1})} \ge [\tau_l - \tau_k^*] \frac{\Delta_k^2}{2}, $$

since $\tau_k^*$ is closer to $\tau_l$ than $\tau_{l+1}$. We claim that, even in the more involved situation where $\tau_{l-1} < \tau_{k-1}^*$, one has

$$ \mathbf{E}^2(t_1) \ge [\tau_l - \tau_k^*] \frac{\Delta_k^2}{8}. \quad (108) $$

Coming back to the definition of $\mathbf{E}_k$, we have

$$ \frac{\mathbf{E}^2(t_1)}{[\tau_l - \tau_k^*]\mathbf{E}_k^2} \ge \frac{(\tau_{k+1}^* - \tau_{k-1}^*)}{8(\tau_{k+1}^* - \tau_k^*)(\tau_k^* - \tau_{k-1}^*)} \ge \frac{1}{8(\tau_{k+1}^* - \tau_k^*)} \ge \frac{1}{16(\tau_{k+1}^* - \tau_l)} , $$

where we used in the last inequality that $2(\tau_l - \tau_k^*) \le (\tau_{k+1}^* - \tau_k^*)$.

To finish this proof, it remains to prove (108) when $\tau_{l-1} < \tau_{k-1}^*$. In that case, we have

$$ \frac{(\tau_l - \tau_{l-1})\mathbf{E}^2(t_1)}{[\tau_l - \tau_k^*](\tau_k^* - \tau_{l-1})} = \left( \mu_{k+1} - \mu_k \frac{\tau_k^* - \tau_{k-1}^*}{\tau_k^* - \tau_{l-1}} - \bar{\theta}_{\tau_{l-1}:\tau_{k-1}^*} \frac{\tau_{k-1}^* - \tau_{l-1}}{\tau_k^* - \tau_{l-1}} \right)^2 \\ = \left( \mu_{k+1} - \mu_k + (\mu_k - \bar{\theta}_{\tau_{l-1}:\tau_{k-1}^*}) \frac{\tau_{k-1}^* - \tau_{l-1}}{\tau_k^* - \tau_{l-1}} \right)^2 . $$

Since $\tau_l - \tau_{l-1} \le 2(\tau_l - \tau_k^*)$ ($\tau_l$ is closer to $\tau_k^*$ than any other point), it suffices to prove that

$$ |\mu_k - \bar{\theta}_{\tau_{l-1}:\tau_{k-1}^*}| \frac{\tau_{k-1}^* - \tau_{l-1}}{\tau_k^* - \tau_{l-1}} \le \frac{1}{2} |\mu_{k+1} - \mu_k| . \quad (109) $$
Since $\tau_{k-1}^*$ is not a $(\sqrt{L} + \sqrt{\ell}, q, \tau^{(k-1)})$-high energy change-point, we have

$$|\bar{\theta}_{\tau_{l-1}:\tau_{k-1}^*} - \mu_k \frac{\tau_k^* - \tau_{k-1}^*}{\tau_l - \tau_{k-1}^*} - \mu_{k+1} \frac{\tau_l - \tau_k^*}{\tau_l - \tau_{k-1}^*}| \le \psi_q[\delta(\tau_{l-1}, \tau_{k-1}^*, \tau_l)][\sqrt{L} + \sqrt{\ell}] \frac{\tau_l - \tau_{l-1}}{(\tau_l - \tau_{k-1}^*)(\tau_{k-1}^* - \tau_{l-1})},$$

which in turn implies

$$|\bar{\theta}_{\tau_{l-1}:\tau_{k-1}^*} - \mu_k| \frac{\tau_{k-1}^* - \tau_{l-1}}{\tau_k^* - \tau_{l-1}} \le |\mu_{k+1} - \mu_k| \frac{(\tau_l - \tau_k^*)(\tau_{k-1}^* - \tau_{l-1})}{(\tau_l - \tau_{k-1}^*)(\tau_k^* - \tau_{l-1})} + \psi_q[\delta(\tau_{l-1}, \tau_{k-1}^*, \tau_l)][\sqrt{L} + \sqrt{\ell}] \sqrt{\frac{(\tau_l - \tau_{l-1})(\tau_{k-1}^* - \tau_{l-1})}{(\tau_l - \tau_{k-1}^*)(\tau_k^* - \tau_{l-1})^2}}.$$

The first expression in the rhs is smaller than $|\mu_{k+1} - \mu_k|/3$ because $(\tau_l - \tau_k^*) \le (\tau_k^* - \tau_{k-1}^*)/2$ and $\tau_{k-1}^* \le \tau_k^*$. Since $x \log(t) \le \log(tx)$ for $t \ge 1$ and $x \le 1$, it follows that

$$\begin{aligned} \psi_q[\delta(\tau_{l-1}, \tau_{k-1}^*, \tau_l)] \sqrt{\frac{\tau_{k-1}^* - \tau_{l-1}}{\tau_l - \tau_{l-1}}} &\le \sqrt{2 \log \left( \frac{n}{\tau_l - \tau_{k-1}^*} \right) + q} \le \sqrt{2 \log \left( \frac{n}{\tau_k^* - \tau_{k-1}^*} \right) + q} \\ &\le \psi_q[\delta(\tau_{k-1}^*, \tau_k^*, \tau_{k+1}^*)] \\ &\le \frac{\mathbf{E}_k}{\kappa_L} \le \frac{|\mu_{k+1} - \mu_k|}{\kappa_L} (\tau_k^* - \tau_{k-1}^*)^{1/2}, \end{aligned}$$

since we assume that $\mathbf{E}_k$ is a $\kappa_L$-high energy change-point. Coming back to $\bar{\theta}_{\tau_{l-1}:\tau_{k-1}^*} - \mu_k$, this yields

$$\begin{aligned} |\bar{\theta}_{\tau_{l-1}:\tau_{k-1}^*} - \mu_k| \frac{\tau_{k-1}^* - \tau_{l-1}}{\tau_k^* - \tau_{l-1}} &\le \frac{|\mu_{k+1} - \mu_k|}{3} + \frac{\sqrt{L} + \sqrt{\ell}}{\kappa_L} |\mu_{k+1} - \mu_k| \frac{(\tau_l - \tau_{l-1})\sqrt{\tau_k^* - \tau_{k-1}^*}}{(\tau_k^* - \tau_{l-1})\sqrt{\tau_l - \tau_{k-1}^*}} \\ &\le |\mu_{k+1} - \mu_k| \left[ \frac{1}{3} + 2 \frac{\sqrt{L} + \sqrt{\ell}}{\kappa_L} \right] \\ &\le \frac{|\mu_{k+1} - \mu_k|}{2}, \end{aligned}$$

where we used that $\tau_l$ is closer to $\tau_k^*$ than $\tau_{l-1}$ and that $\kappa_L$ is large enough. $\square$

## 8.6 Proofs for the post-processing steps

*Proof of Proposition 12.* We recall the definition of that the event $B_{1-\alpha}$ of probability higher than $1 - \alpha$ is such that

$$|\mathbf{N}(t)| \le \sqrt{2 \log \left( \frac{n(t_3 - t_1)}{(t_2 - t_1)(t_3 - t_2)} \right)} + \zeta_{1-\alpha}, \quad \forall t \in \mathcal{T}_3. \quad (110)$$

Under this event, for any $\tau$ such that $\hat{r}_{\tau} < \infty$, the interval $[t_1^{(\tau, \hat{r}_{\tau})} + 1; t_3^{(\tau, \hat{r}_{\tau})} - 1]$ contains a least one true change-point, say $\tau_k^*$. By definition of the pruning step, the confidence intervals associated to the pruned change-points $\mathcal{P}(\tau)$ do not intersect. Suppose that two change-points, say $\mathcal{P}(\tau)_l$ and $\mathcal{P}(\tau)_{l+1}$, in the segment $(\frac{\tau_{k-1}^* + \tau_k^*}{2}, \frac{\tau_k^* + \tau_{k+1}^*}{2}]$. Since both confidence intervals of $\mathcal{P}(\tau)_l$ and $\mathcal{P}(\tau)_{l+1}$ contain at least one change-point, this implies that $\tau_k^*$ belongs to these two intervals which
contradicts the non intersection property. For $k = 1$ and $k = K$, the same argument applies with $[2; \frac{\tau_k^* + \tau_{k-1}^*}{2}]$ and $[\frac{\tau_{k-1}^* + \tau_k^*}{2}; n]$ respectively.

Let us turn to the second result. Consider a $(\kappa, \zeta_{1-\alpha}^2)$-high-energy change-point $\tau_k^*$ and assume that there exists $\tau_l$ such that

$$|\tau_l - \tau_k^*| < \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{8}.$$

Consider any $r \ge |\tau_l - \tau_k^*| \wedge \tau_l \wedge (n+1 - \tau_l)$. Writing down the energy of $t^{(\tau_l, r)}$ and relying on (110), we derive that

$$\mathbf{E}(t^{(\tau_l, r)}) = |\Delta_k| \left(1 - \frac{|\tau_l - \tau_k^*|}{r}\right)_+ \sqrt{\frac{r}{2}}, \quad |\mathbf{N}(t^{(\tau_l, r)})| \le \sqrt{2\log\left(2\frac{n}{r}\right)} + \zeta_{1-\alpha}.$$

Let $\bar{r}_l$ be the smallest $r > 0$ such that $\mathbf{E}(t^{(\tau_l, r)}) \ge 2\sqrt{2\log(2\frac{n}{r})} + 2\zeta_{1-\alpha}$. Since $|\mathbf{C}(t^{(\tau_l, r)})| \ge \mathbf{E}(t^{(\tau_l, r)}) - |\mathbf{N}(t^{(\tau_l, r)})|$, we have $\bar{r}_l \ge \hat{r}_{\tau_l}$. This implies that

$$\hat{r}_{\tau_l} \le 2|\tau_l - \tau_k^*| \vee \left[ \frac{64 \left[ \sqrt{\log(n\Delta_k^2)} + \zeta_{1-\alpha}/\sqrt{2} \right]^2}{\Delta_k^2} \right] < 1 + \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{4}, \quad (111)$$

since $\tau_k^*$ is a $(\kappa, \zeta_{1-\alpha}^2)$-high-energy change-point and since the constant $\kappa$ is large enough. In turn, this also implies that

$$\underline{I}_{\tau_l} \subset \left[ \tau_k^* - \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{4}, \tau_k^* + \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{4} \right]. \quad (112)$$

We prove below that, in $\mathcal{P}(\tau)$, there exists a least one change-point, say $\mathcal{P}(\tau)_j$ satisfying $|\mathcal{P}(\tau)_j - \tau_k^*| \le \hat{r}_{\tau_l}$. If $\tau_l$ belongs to $\mathcal{P}(\tau)$, this is obviously true. Now assume that $\tau_l$ is pruned. Consequently, there exists $\tau_m$ such that $\hat{r}_{\tau_m} \le \hat{r}_{\tau_l}$ and $\underline{I}_{\tau_m} \cap \underline{I}_{\tau_l} \ne \emptyset$. Since $\hat{r}_{\tau_m} \le \hat{r}_{\tau_l}$ an by (112), this implies that

$$|\tau_m - \tau_k^*| \le \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{2}.$$

Recall that $\underline{I}_{\tau_m}$ contains at least one true change-point. Hence, $\tau_k^* \in \underline{I}_{\tau_m}$. Therefore,

$$|\tau_m - \tau_k^*| \le \hat{r}_{\tau_m} - 1 \le \hat{r}_{\tau_l} - 1$$

If $\tau_m$ itself is also pruned, then we show similarly that there exists a change-point $\tau_{m'}$ satisfying $|\tau_{m'} - \tau_k^*| \le \hat{r}_{\tau_m} - 1 \le \hat{r}_{\tau_l} - 1$. By recursion, this implies that, there exists one change-point $\mathcal{P}(\tau)_j$ in $\mathcal{P}(\tau)$ such that $|\mathcal{P}(\tau)_j - \tau_k^*| \le \hat{r}_{\tau_l} - 1$. The result follows. $\square$

*Proof of Proposition 13.* On the event $\mathcal{B}_{1-\alpha}$, we have

$$|\tau - \tau_k^*| \le \hat{r}_{\tau} - 1 < \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{4}. \quad (113)$$

The first inequality holds since at least one true change-point belongs to $\underline{I}_{\tau}$. The second inequality is proved as (111) in the proof of Proposition 12. As a consequence,

$$|\tau - \tau_k^*| + 2\hat{r}_{\tau} - 1 < 1 + \frac{3}{4}(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*).$$
Since the rhs is an integer, this implies that

$$|\tau - \tau_k^k| + 2\hat{r}_\tau - 1 \le \left[ \frac{3}{4}(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*) \right] \le (\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*) .$$

Hence, the interval $[\tau - 2\hat{r}_\tau + 1, \tau + 2\hat{r}_\tau - 1)$ is included in $[\tau_{k-1}^*; \tau_{k+1}^*)$ and only contain the true change-point $\tau_k^*$.

Then, we argue as in the proof of Proposition 11. Fix any $x > 0$. From Lemma 5 (with $\nu = \Delta_k^{-2}$), we deduce that, with probability higher than $1 - 2e^{-x}$, we have

$$\begin{aligned} |Z_{\tau_k^* - s; \tau_k^*}| &\le 2\sqrt{2s}\sqrt{2\log(\log(3\Delta_k^{-2}s)) + x + 2} ; \\ |Z_{\tau_k^*; \tau_k^* + s}| &\le 2\sqrt{2s}\sqrt{2\log(\log(3\Delta_k^{-2}s)) + x + 2} , \end{aligned} \quad (114)$$

simultaneously over all integers $s \ge \Delta_k^{-2}$.

Consider any $\tau' \in I_\tau$ such that $|\tau' - \tau| \ge \Delta_k^{-2}$. By symmetry we can assume that $\tau' \le \tau_k^*$. Define $t_1 = (\tau', \tau_k^*, \tau + 2\hat{r}_\tau - 1)$ and $t_2 = (\tau - 2\hat{r}_\tau + 1, \tau', \tau_k^*)$.

$$\begin{aligned} \|\Pi_{\tau'} Y^{(\tau; 2\hat{r}_{\tau}-1)}\|^2 - \|\Pi_{\tau_k^*} Y^{(\tau; 2\hat{r}_{\tau}-1)}\|^2 &= -C^2[t_1] + C^2[t_2] \\ &= -((-1)^{\text{sign}(\Delta_k)} \mathbf{E}[t_1] - \mathbf{N}(t_1))^2 + \mathbf{N}^2(t_2) \\ &\ge \frac{1}{2} \mathbf{E}^2(t_1) - \mathbf{N}^2(t_1) - \mathbf{N}^2(t_2) . \end{aligned} \quad (115)$$

First, we work out the energy.

$$\mathbf{E}^2(t_1) = |\tau_k^* - \tau'| \frac{|\tau + 2\hat{r}_\tau - 1 - \tau_k^*|}{|\tau + 2\hat{r}_\tau - 1 - \tau'|} \Delta_k^2 \ge |\tau_k^* - \tau'| \frac{\Delta_k^2}{3} .$$

Since $\tau_k^* \le \tau + \hat{r}_\tau - 1$ and $\tau' \ge \tau - \hat{r}_\tau + 1$. Then, we rely on (114) to control the stochastic terms $\mathbf{N}(t_1)$ and $\mathbf{N}(t_2)$.

$$\begin{aligned} \frac{|\mathbf{N}(t_1)|}{2\sqrt{2}} &\le \sqrt{\frac{\tau + 2\hat{r}_\tau - 1 - \tau_k^*}{\tau + 2\hat{r}_\tau - 1 - \tau'}} \sqrt{\log(\log(e\Delta_k^{-2}|\tau_k^* - \tau'|)) + x + 2} \\ &\quad + \sqrt{\frac{|\tau_k^* - \tau'|}{\tau + 2\hat{r}_\tau - 1 - \tau'}} \sqrt{\log(\log(e\Delta_k^{-2}|\tau + 2\hat{r}_\tau - 1 - \tau_k^*|)) + x + 2} \\ &\le \sqrt{\log(\log(e\Delta_k^{-2}|\tau_k^* - \tau'|)) + x + 2} \\ &\quad + \sqrt{\frac{|\tau_k^* - \tau'|}{\tau + 2\hat{r}_\tau - 1 - \tau'}} \sqrt{\log(\log(e\Delta_k^{-2}|\tau + 2\hat{r}_\tau - 1 - \tau'|)) + x + 2} \\ &\le 2\sqrt{\log(\log(e\Delta_k^{-2}|\tau_k^* - \tau'|)) + x + 2} , \end{aligned}$$

where we used in the last line that the function $x \mapsto x[\log \log(a/x) + b]$ is increasing on $(0, 1]$ for
any $a \ge e$. As for $\mathbf{N}(t_2)$, we decompose $Z_{\tau-2\hat{r}_{\tau}+1:\tau'}$ into $Z_{\tau-2\hat{r}_{\tau}+1:\tau_k^*} - Z_{\tau':\tau_k^*}$ to rely on (114)

$$
\begin{align*}
|\mathbf{N}(t_2)| & \le \frac{|Z_{\tau':\tau_k^*}|}{\sqrt{|\tau_k^* - \tau'|}} + \frac{(|Z_{\tau-2\hat{r}_{\tau}+1:\tau_k^*}| - |Z_{\tau':\tau_k^*}|)}{\sqrt{\tau' - \tau + 2\hat{r}_{\tau} - 1}} \sqrt{\frac{|\tau_k^* - \tau|}{\tau_k^* - \tau + 2\hat{r}_{\tau} - 1}} \\
& \le 2\sqrt{2}\sqrt{\log(\log(e\Delta_k^{-2}|\tau_k^* - \tau'|)) + x + 2} \\
& \phantom{\le} + 4\sqrt{2}\sqrt{\log(\log(e\Delta_k^{-2}|\tau_k^* - \tau + 2\hat{r}_{\tau} - 1|)) + x + 2} \sqrt{\frac{|\tau_k^* - \tau'|}{\tau_k^* - \tau + 2\hat{r}_{\tau} - 1}} \\
& \le 6\sqrt{2}\sqrt{\log(\log(e\Delta_k^{-2}|\tau_k^* - \tau'|)) + x + 2}.
\end{align*}
$$

Coming back to (115) we conclude that $\mathcal{L}(\tau) \neq \tau'$ if $|\tau' - \tau_k^*| \ge \Delta_k^{-2}$ and

$$
|\tau_k^* - \tau'| \geq c \frac{\log \log(e \Delta_k^{-2} |\tau_k^* - \tau'|) + x}{\Delta_k^2} .
$$

This concludes the proof.

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

A Proof of the deviation inequalities

A.1 Proof of the law of iterated logarithms lemmas

*Proof of Lemma 4.* Define, for any integer $n \ge 1$, the random walk $S_n = \sum_{i=1}^n \epsilon_i$. Let $k < n$ denote two positive integers. For any $s > 0$,

$$
\mathbb{E}[e^{s(S_n - S_k)}] = \prod_{i=k+1}^{n} \mathbb{E}[e^{s\epsilon_i}] \le \prod_{i=k+1}^{n} \mathbb{E}[e^{s^2/2}] = e^{(n-k)s^2/2} .
$$

Let $\mathcal{F}_k$ denote the sigma-algebra induced by $(\epsilon_1, \dots, \epsilon_k)$. As $S_k$ is independent of $S_n - S_k$, this
entails that

$$
\mathbb{E}[e^{sS_n - \frac{s^2 n}{2}} | \mathcal{F}_k] = e^{sS_k - \frac{s^2 k}{2}} \mathbb{E}[e^{s(S_n - S_k) - \frac{s^2(n-k)}{2}}] \le e^{sS_k - \frac{s^2 k}{2}} .
$$

Hence, $e^{sS_n - \frac{s^2 n}{2}}$ is a super-martingale. Fix $x > 0$ and let $A$ be the stopping time defined by

$$
A = \inf\{n \ge d, S_n \ge \sqrt{n}x\} .
$$

By definition, $S_A \ge \sqrt{A}x \ge \sqrt{dx}$. Hence,

$$
\mathbb{E} \left[ e^{s \sqrt{dx} - \frac{s^2 A}{2}} \right] \le \mathbb{E} \left[ e^{s S_A - \frac{s^2 A}{2}} \right] \le \mathbb{E} \left[ e^{s S_1 - \frac{s^2}{2}} \right] \le 1 .
$$

Now, by definition,

$$
\mathbb{P} \left[ \max_{k \in [d, (1+\alpha)d]} \frac{\sum_{i=1}^{k} Y_i}{\sqrt{k}} \ge x \right] = \mathbb{P}[A \le (1+\alpha)d].
$$

As the function $u \mapsto e^{\sqrt{dx} - \frac{s^2 u}{2}}$ is non-increasing, it follows that

$$
\mathbb{P} \left[ \max_{k \in [d, (1+\alpha)d]} \frac{\sum_{i=1}^{k} Y_i}{\sqrt{k}} \ge x \right] = \mathbb{P} \left[ e^{s\sqrt{dx} - \frac{s^2 A}{2}} \ge e^{s\sqrt{dx} - s^2(1+\alpha)d/2} \right].
$$
By Markov inequality, we obtain that

$$ \mathbb{P}\left[\max_{k \in [d, (1+\alpha)d]} \frac{\sum_{i=1}^{k} Y_i}{\sqrt{k}} \geq x\right] \leq e^{-s\sqrt{d}x + s^2(1+\alpha)d/2} . $$

Choosing $s = x/[(1+\alpha)\sqrt{d}]$ concludes the proof of Lemma 4. □

**Proof of Lemma 5.** Let $\nu > 0$, and $t_1, t_2$, two integers such that $t_1 - 1/\nu < t_2$. Without loss of generality, assume that $1/\nu \geq 1$ and that $t_1 + 1/\nu \leq t_2$. Up to a renumbering of the indices, the sum $Z_{t_1:t_2}$ can be written

$$ Z_{t_1:t_2} = \sum_{i=1}^{t_2-t_1} \epsilon_i . $$

Consider any non-negative integer $s$. By Lemma 4, we have

$$ \forall x > 0, \quad \mathbb{P}\left(\sup_{t_2-t_1 \in [2^s/\nu, 2^{s+1}/\nu]} \frac{Z_{t_1:t_2}}{\sqrt{t_2-t_1}} > 2x\right) \leq e^{-\frac{x^2}{4}} . $$

Let $T_s = [t_1 + 2^s/\nu, t_1 + 2^{s+1}/\nu]$. By a union bound, this yields, for any $x > 0$,

$$ \mathbb{P}\left(\exists s \geq 0 : \sup_{t_2 \in T_s} \frac{Z_{t_1:t_2}}{\sqrt{t_2-t_1}} > 2\sqrt{\log[(s+1)(s+2)] + x}\right) \leq \sum_{s=0}^{+\infty} \frac{e^{-x}}{(s+1)(s+2)} = e^{-x}. \quad (116) $$

For any $t_1, t_2$ such that $t_2 - t_1 \geq 2^s/\nu$, $s \leq \log[(t_2 - t_1)\nu]/\log 2$, hence

$$ (s+1)(s+2) \leq \frac{\log[2(t_2-t_1)\nu]\log[4(t_2-t_1)\nu]}{(\log 2)^2} \leq \left(\frac{\log[\sqrt{8}(t_2-t_1)\nu]}{\log 2}\right)^2 . $$

Thus,

$$ \log[(s+1)(s+2)] \leq 2\log\left(\frac{\log[3(t_2-t_1)\nu]}{\log 2}\right) \leq 2\log\log[3(t_2-t_1)\nu] + 1 . $$

Plugging this inequality into (116) shows that, with probability larger than $1 - e^{-x}$, for any $t_2 \geq t_1 + 1/\nu$,

$$ Z_{t_1:t_2} \leq 2\sqrt{t_2-t_1}(\sqrt{2\log\log[3(t_2-t_1)\nu]} + 1 + x) . $$

**Proof of Lemma 6.** By definition,

$$ \mathbf{N}(t_{\tau}) = \sqrt{\frac{n+1-\tau}{n(\tau-1)}} Z_{1:\tau} - Z_{\tau:n+1} \sqrt{\frac{\tau-1}{(n+1-\tau)n}} . $$

We control the deviations of $\mathbf{N}(t_\tau)$ simultaneously for all $\tau \leq n/2 + 1$ with probability higher than $1 - 6e^{-x}$. By symmetry between $\tau$ and $n+1-\tau$, the desired result follows. Applying Lemma 4 with $\alpha = 1$ and $d = n/2$, we show that, with probability at least $1 - e^{-x}$, for all $\tau \leq n/2 + 1$,

$$ -Z_{\tau:n+1}\sqrt{\frac{\tau-1}{(n+1-\tau)n}} \leq 2\sqrt{\frac{\tau-1}{n}}x. \quad (117) $$
Fix now $\alpha > 0$ and $s \ge 0$. By Lemma 4 applied with $d = (1 + \alpha)^s$, we derive that, for any $x \ge 0$,

$$ \mathbb{P}\left[\forall \tau \in [(1 + \alpha)^s, (1 + \alpha)^{s+1}], \frac{Z_{1:\tau}}{\sqrt{\tau - 1}} \le \sqrt{2(1 + \alpha)x}\right] \ge 1 - e^{-x}. $$

A union bound shows then that, for any $x > 0$,

$$ \forall s \ge 0, \forall \tau \in [(1 + \alpha)^s, (1 + \alpha)^{s+1}], \quad \frac{Z_{1:\tau}}{\sqrt{\tau - 1}} \le \sqrt{2(1 + \alpha)(x + \log[(1 + \alpha^{-1})(s+1)^{1+\alpha}])}, $$

with probability at least

$$ 1 - \sum_{s \ge 0} e^{-(x+\log[(1+\alpha^{-1})(s+1)^{1+\alpha}])} = 1 - \frac{\alpha e^{-x}}{1+\alpha} \sum_{s \ge 0} \frac{1}{s^{1+\alpha}} \ge 1 - e^{-x}. $$

Now, for any $\tau \in [(1 + \alpha)^s, (1 + \alpha)^{s+1}]$, we have $s \le \log(\tau)/\log(1 + \alpha)$. As a consequence, we have

$$ s + 1 \le \frac{\log[(1 + \alpha)\tau]}{\log(1 + \alpha)}. $$

It follows that, with probability at least $1 - e^{-x}$, for any $\tau \ge 1$,

$$ \begin{aligned} \frac{Z_{1:\tau}}{\sqrt{\tau - 1}} &\le \sqrt{2(1 + \alpha)\left(x + \log\left[(1 + \alpha^{-1})\left(\frac{\log[(1 + \alpha)\tau]}{\log(1 + \alpha)}\right)^{1+\alpha}\right]\right)} \\ &\le \sqrt{2(1 + \alpha)\left(x + \log(1 + \alpha^{-1}) + (1 + \alpha)\log\left[\frac{\log[(1 + \alpha)\tau]}{\log(1 + \alpha)}\right]\right)} \\ &\le (1 + \alpha)\sqrt{2(\log\log[(1 + \alpha)\tau] + x + C_{\alpha})}. \end{aligned} $$

Here

$$ C_{\alpha} = \frac{\log(1 + \alpha^{-1})}{1 + \alpha} - \log \log[1 + \alpha]. $$

Combined with (117), with probability $1 - 2e^{-x}$, we proved that, for any $\tau \le n/2 + 1$,

$$ \begin{aligned} \mathbf{N}(t_{\tau}) &\le (1 + \alpha)\sqrt{2(\log \log[(1 + \alpha)\tau] + x + C_{\alpha})}\sqrt{\frac{n+1-\tau}{n}} + 2\sqrt{\frac{\tau-1}{n}}x \\ &\le (1 + \alpha)\sqrt{2(\log \log[(1 + \alpha)\tau] + 3x + C_{\alpha})}. \end{aligned} $$

Here, we used the inequality

$$ (\sqrt{1 - ua} + \sqrt{ub})^2 = (1 - u)a^2 + 2\sqrt{u(1 - u)}ab + ub^2 \le a^2 + b^2, $$

which holds for any $u \in [0, 1]$, $a, b > 0$ with

$$ a = (1 + \alpha)\sqrt{2(\log \log[(1 + \alpha)\tau] + x + C_{\alpha})}, \quad b = 2\sqrt{x}, \quad u = \frac{\tau - 1}{n}. $$

The term $\log \log(en/\tau)$ is obtained similarly by applying Lemma 4 to bound the deviations of $Z_{1:\tau}$ on the intervals $[n/(1 + \alpha)^{s+1}; n/(1 + \alpha)^s]$. Combining both results shows that, with probability larger than $1 - 3e^{-x}$, for all $\tau \le n/2 + 1$

$$ \mathbf{N}(t_{\tau}) \le (1 + \alpha)\sqrt{2\left(\log \log\left[(1 + \alpha)\left(\tau \wedge \frac{n}{\tau}\right)\right] + 3x + C_{\alpha}\right)}. $$

The result follows.

□
Proof of Lemma 7. Recall that

$$ \mathbf{N}(t_{\tau}) = \sqrt{\frac{(\tau - 1)(n + 1 - \tau)}{n}} \left( \frac{Z_{1:\tau}}{\tau - 1} + \frac{Z_{\tau:n+1}}{n + 1 - \tau} \right) . \qquad (118) $$

Let us first apply Lemma 4. For any $s \ge 0$, with probability $1 - e^{-x}/(s+1)(s+2)$, we have

$$ \frac{Z_{1:\tau}}{(\tau - 1)^{1/2}} \le 2\sqrt{\log[(s+1)(s+2)] + x}, \qquad (119) $$

uniformly over all $\tau \in [\tau^*/2^{s+1}, \tau^*/2^s]$. For any $\tau \le \tau^*/2^s$, $s \le \log(\tau^*/\tau)/\log 2$, hence,

$$ (s+1)(s+2) \le \frac{\log(e\tau^*/\tau) \log(e^2\tau^*/\tau)}{(\log 2)^2} \le \left( \frac{\log(e^{3/2}\tau^*/\tau)}{\log 2} \right)^2 . $$

Hence, by the inequality $\log(a+x) \le \log a + \log(1+x)$ valid for any $x \ge 0$ and $a \ge 1$,

$$ \begin{aligned} \log[(s+1)(s+2)] &\le 2\log\left(\frac{3}{2} + \log[\tau^*/\tau]\right) - 2\log\log 2 \\ &\le 2\log\left[\frac{3}{2\log 2}\right] + 2\log\log(e\tau^*/\tau) \\ &\le 1.6 + 2\log\log\left(e\frac{\tau^*-1}{\tau-1}\right). \end{aligned} \qquad (120) $$

Moreover, for any $\tau \le \tau^*$, we have $n+1-\tau^* \le n+1-\tau$ and

$$ \frac{\tau^*-1}{\tau-1} = \gamma_{\tau}^{-1} \frac{n+1-\tau^*}{n+1-\tau} \le \gamma_{\tau}^{-1}. $$

Applying a union bound over all non-negative integers $s$, we derive that, with probability higher than $1 - e^{-x}$, simultaneously over all $\tau \le \tau^*$,

$$ \frac{Z_{1:\tau}}{(\tau - 1)^{1/2}} \le 2\sqrt{2\log\log(e\gamma_{\tau}^{-1}) + x + 1.6}. \qquad (121) $$

We proceed similarly for $Z_{\tau:n+1}/(n+1-\tau)$. It follows from Lemma 4 that, for any $s \ge 0$, with probability $1 - e^{-x}/(s+1)(s+2)$, uniformly over all $\tau \in [2^s(n+1-\tau^*), 2^{s+1}(n+1-\tau^*)]$,

$$ \frac{Z_{\tau:n+1}}{(n+1-\tau)^{1/2}} \le 2\sqrt{\log[(s+1)(s+2)] + x}. \qquad (122) $$

Arguing exactly as when we deduced (121) from (119), we obtain that, simultaneously over all $\tau \le \tau^*$,

$$ \frac{Z_{\tau:n+1}}{(n+1-\tau)^{1/2}} \le 2\sqrt{2\log\log(e\gamma_{\tau}^{-1}) + x + 1.6}, \qquad (123) $$

with probability higher than $1 - e^{-x}$. Plugging (121) and (123) into (118), we get

$$ \mathbf{N}(t_{\tau}) \le \frac{2}{\sqrt{n}} \sqrt{2 \log \log (e \gamma_{\tau}^{-1}) + x + 1.6} (\sqrt{\tau - 1} + \sqrt{n+1-\tau}) \le 4 \sqrt{\log \log (e \gamma_{\tau}^{-1}) + x + 1}. $$

Here, we used for the last inequality that $\sqrt{a} + \sqrt{n-a} \le \sqrt{2n}$ for any $a \in [0, n]$. $\square$
## A.2 Proof of Lemmas 9 and 10

We first establish Lemma 9. For any $t \in \mathcal{T}_3$, define

$$X_t = \frac{(t_3 - t_2)(t_2 - t_1)}{(t_3 - t_1)} \left[ \frac{Z_{t_1:t_2}}{t_2 - t_1} - \frac{Z_{t_2:t_3}}{t_3 - t_2} \right],$$

so that $Z_t = \sqrt{\frac{(t_3-t_2)(t_2-t_1)}{t_3-t_1}} X_t$. In the sequel, we write $\delta_1$ and $\delta_2$ for $t_2-t_1$ and $t_3-t_2$ respectively.

Given a centered sugGaussian random variable $Y$, it sub-Gaussian norm $\|Y\|_{\psi_2}$ is defined the smallest $\sigma$ such that $\mathbb{E}[e^{sY}] \le e^{s^2\sigma^2/2}$ for all $s \in \mathbb{R}$. Defining $\sigma^2(t) = \frac{\delta_1\delta_2}{\delta_1+\delta_2} \in [(\delta_1 \wedge \delta_2)/2, \delta_1 \wedge \delta_2)$, we observe that $Z_t = X_t/\sigma(t)$ and that the sub-Gaussian norm of $X_t$ is less or equal to $\sigma(t)$.

We prove Lemma 9 using an adaptive peeling argument as in Dümbgen and Spokoiny [20]. Denote $\mathcal{T}_+$ (resp. $\mathcal{T}_-$) the subset of vectors $t \in \mathcal{T}_3$ satisfying $\delta_1 \le \delta_2$ (resp. $\delta_2 \le \delta_1$). We focus on triads $t \in \mathcal{T}_+$, triads in $\mathcal{T}_-$ being handled analogously. Given any $t \neq t'$ in $\mathcal{T}_+$, define

$$\rho^2(t, t') = |t_1 - t'_1| + |t_2 - t'_2| + |t_3 - t'_3| \left( \frac{\delta_1}{\delta_2} + \frac{\delta'_1}{\delta'_2} \right)^2 . \quad (124)$$

The next lemma bounds the deviations of $X_t - X_{t'}$ in terms of $\rho(t, t')$.

**Lemma 17.** For any $t, t' \in \mathcal{T}_+$, we have

$$\|X_t - X_{t'}\|_{\psi_2}^2 \le \frac{7}{2} \rho^2(t, t') . \quad (125)$$

In other words, $X_t - X_{t'}$ is small if $(t_1, t_2)$ is close to $(t'_1, t'_2)$ and either if $|t_3 - t'_3|$ is small or if $\delta_1/\delta_2$ and $\delta'_1/\delta'_2$ are small.

To formalize our adaptive peeling argument, we partition $\mathcal{T}_+$ into the collections

$$\mathcal{T}_+^{(k,q)} := \{t \in \mathcal{T}_+, \delta_1 \in [n2^{-k}, n2^{-k+1}), \quad \delta_2 \in [n2^{q-k}n, 2^{q-k+1}]\},$$

where $k = 1, \dots, \lceil \log_2(n) \rceil$ and $q = 0, \dots, k-1$. Given any $\kappa \in (0, 1)$, we denote $S_{k,q,\kappa}$ a minimal covering of $\mathcal{T}_+^{(k,q)}$ of radius $r_{k,\kappa} := \kappa \sqrt{n2^{-k+1}}$ with respect to the semi-metric $\rho$.

**Lemma 18.** For any $\kappa \in (0, 1)$ and positive integer $k \le \lceil \log_2(n) \rceil$, we have

$$|S_{k,q,\kappa}| \le c \cdot \frac{2^{k-q}}{\kappa^6}, \quad (126)$$

for a numerical constant $c > 0$.

For $t \in \mathcal{T}_+^{(k,q)}$, we write $\pi_{k,q,\kappa}(t)$ for any closest element of $t$ in $S_{k,q,\kappa}$. Given any integer $k \le \lceil \log_2(n) \rceil$, define $l(k) := \lceil \frac{\log(\log(n))}{\log(k)} \rceil$. Using a chaining argument with the collections $(S_{k,q,k^{-i}})$, $i = 1, \dots, l(k)$, we arrive at the decomposition

$$X_t = X_{\pi_{k,q,k-1}(t)} + \sum_{i=1}^{l(k)-1} \left( X_{\pi_{k,q,k-i-1}(t)} - X_{\pi_{k,q,k-i}(t)} \right) + X_t - X_{\pi_{k,q,k-l(k)}(t)} . \quad (127)$$

Let us first control the deviation of $X_t - X_{\pi_{k,q,k-l(k)}(t)}$. Since $|\mathcal{T}_+| \le n^3/6$, it then follows from an union bound over all $t, t' \in \mathcal{T}_+$ and from (125) that, with probability higher than $1-x$,

$$|X_t - X_{t'}| \le \rho(t, t') \sqrt{42 \log(n) + 7 \log(1/x)}, \quad (128)$$
simultaneously over all $t$ and $t'$ in $\mathcal{T}_+$. Next, the random variables $X_s$, with $s \in S_{k,q,k-1}$ are simply controlled using an union bound. With probability higher than $1-x$, we have

$$|X_{\pi_{k,q,k-1}(t)}| \le \sigma(\pi_{k,q,k-1}(t)) \sqrt{2 \log \left( \frac{2|S_{k,q,k-1}|}{x} \right)}, \quad (129)$$

simultaneously over all $t \in \mathcal{T}_+^{(k)}$. Finally, we consider the differences $X_{\pi_{k,q,k-i-1}(t)} - X_{\pi_{k,q,k-i}(t)}$ for $1 \le i \le l(k)$. For a fixed $i$, there are at most $|S_{k,q,k-i-1}| |S_{k,q,k-i}| \le |S_{k,q,k-i-1}|^2$ such differences. Taking an upper bound over all possible $X_{\pi_{k,q,k-i-1}(t)} - X_{\pi_{k,q,k-i}(t)}$ with $t \in \mathcal{T}_+^{(k)}$, we conclude that, with probability higher than $1-x$

$$|X_{\pi_{k,q,k-i-1}(t)} - X_{\pi_{k,q,k-i}(t)}| \le \rho(\pi_{k,q,k-i-1}(t), \pi_{k,q,k-i}(t)) \sqrt{7 \log \left( 2 \frac{|S_{k,q,k-i-1}|^2}{x} \right)}, \quad (130)$$

simultaneously for all $t \in \mathcal{T}_+^{(k)}$. Then taking an union bound over all $i \le l(k) - 1$ with weight $18x/(\pi^2 i^2)$ and gathering it (128) and (129), we conclude that with probability higher than $1-x$, we have

$$|X_t| \le \sigma(\pi_{k,q,k-1}(t)) \sqrt{2 \log \left( \frac{6|S_{k,q,k-1}|}{x} \right)} + \sum_{i=1}^{l(k)-1} \rho(\pi_{k,q,k-i-1}(t), \pi_{k,q,k-i}(t)) \sqrt{7 \log \left( \frac{36|S_{k,q,k-i-1}|i^2}{\pi^2 x} \right)} \\ + \rho(t, \pi_{k,q,k-l}(t)) \sqrt{42 \log(n) + 7 \log \left( \frac{3}{x} \right)},$$

simultaneously over all $t \in \mathcal{T}_+^{(k,q)}$. For any such $t, t' \in \mathcal{T}_+^{(k,q)}$, we have

$$|t_1 - t'_1| + |t_2 - t'_2| + 2^{2-2q} |t_3 - t'_3| \le \rho^2(t, t') \le |t_1 - t'_1| + |t_2 - t'_2| + 2^{4-2q} |t_3 - t'_3|$$

Hence, we get

$$\rho^2(\pi_{k,q,k-i-1}(t), \pi_{k,q,k-i}(t)) \le 4[\rho^2(\pi_{k,q,k-i-1}(t), t) + \rho^2(\pi_{k,q,k-i}(t), t)] \le 8\rho^2(\pi_{k,q,k-i}(t), t) \le 8k^{-2i}n2^{-k+1}, \\ \text{and } \sigma(t) \ge \sqrt{\delta_1/2} \ge \sqrt{n2^{-k-1}}. \text{ Then, relying on Lemma 18, we conclude that}$$

$$\begin{aligned} \frac{|X_t|}{\sigma(t)} &\le \frac{\sigma(\pi_{k,q,k-1}(t))}{\sigma(t)} \sqrt{2 \log(2^{k-q}) + 12 \log(k) + c + 2 \log(1/x)} \\ &\quad + c' \sum_{i=1}^{\infty} k^{-i} \sqrt{k-q + \log(i) + i \log(k) + 1 + \log(1/x)} + c'' \frac{\sqrt{\log(1/x) + 1}}{\sqrt{\log(n)}} \\ &\le \sqrt{2 \log(2^{k-q}) + c_1 \log(k) + c_2 + c_3 \log(\frac{1}{x})} \\ &\quad + \frac{|\sigma(\pi_{k,k-1}(t)) - \sigma(t)|}{\sigma(t)} \sqrt{2k + 12 \log(k) + c + 2 \log(1/x)}. \end{aligned}$$

**Lemma 19.** For $\kappa \in (0,1)$ and $t \in \mathcal{T}_+^{(k)}$, we have

$$\frac{|\sigma(t) - \sigma(\pi_{k,q,\kappa}(t))|}{\sigma(t)} \le \frac{2r_{k,\kappa}^2}{\sigma^2(t)} \le 8\kappa^2.$$
With this last lemma, we obtain

$$ \frac{|X_t|}{\sigma(t)} \le \sqrt{2 \log(2^{k-q}) + c_1 \log(k) + c_2 + c_3 \log(\frac{1}{x})}, $$

simultaneously over all $t \in \mathcal{T}_+^{(k,q)}$ with probability higher than $1-x$. Taking an union bound over all $k$ and $q$ with weights $36x/[\pi^2 k^2 q^2]$, we conclude that, with probability higher than $1-x$,

$$ \frac{|X_t|}{\sigma(t)} \le \sqrt{2 \log(2^k) + c'_1 \log(k) + c'_2 + c'_3 \log(\frac{1}{x})}, $$

simultaneously over all $t \in \mathcal{T}_+^{(k,q)}$ with $k = 1, \dots, \lfloor \log_2(n) \rfloor$ and $q = 1, \dots, k$. Since $t \in \mathcal{T}_+^{(k,q)}$, we have $2^k \le 2n/\delta_1$, which implies

$$ \frac{|X_t|}{\sigma(t)} \le \sqrt{2 \log \left( \frac{n(\delta_1 + \delta_2)}{\delta_1 \delta_2} \right) + c'_1 \log \log \left( \frac{n(\delta_1 + \delta_2)}{\delta_1 \delta_2} \right) + c'_2 + c'_3 \log(\frac{1}{x})}. $$

*Proof of Lemma 17.* By symmetry, we assume that $\delta_2 \ge \delta'_2$. Let us upper bound $\|X_t - X_{t'}\|_{\psi_2}^2$. Since $X_t - X'_t$ decomposes as $\sum_{i=t_1 \wedge t'_1}^{(t_3 \vee t'_3)-1} \alpha_i \epsilon_i$ for some $\alpha_i$'s, its squared sub-Gaussian norm is at most $\sum_i \alpha_i^2$. The value of the $\alpha_i$'s depends on whether $i$ belongs to $[t_1, t_2)$, $[t_2, t_3)$, $[t'_1, t'_2]$ or $[t'_2, t'_3)$. More precisely, we have

(a) $|\alpha_i| \le 1$ if $i \in ([t_1, t_2) \cap [t'_1, t'_3)^c) \cup ([t'_1, t'_2) \cap [t_1, t_3)^c)$

(b) $|\alpha_i| \le (\delta_1/\delta_2 + \delta'_1/\delta'_2)$ if $i \in ([t_2, t_3) \cap [t'_1, t'_3)^c) \cup ([t'_2, t'_3) \cap [t_1, t_3)^c)$

(c) $|\alpha_i| \le 3/2$ if $i \in ([t_1, t_2) \cap [t'_2, t'_3)) \cup ([t'_1, t'_2) \cap [t_2, t_3))$

(d) For $i \in ([t_1, t_2) \cap [t'_1, t'_2)) \cup ([t_2, t_3) \cap [t'_2, t'_3))$, we have

$$ \alpha_i^2 = \left[ \frac{\delta'_1}{\delta'_1 + \delta'_2} - \frac{\delta_1}{\delta_1 + \delta_2} \right]^2 \le \left[ \frac{(\delta_2 - \delta'_2)\delta'_1 + \delta'_2|\delta'_1 - \delta_1|}{(\delta'_1 + \delta'_2)(\delta_1 + \delta_2)} \right]^2. $$

If $\delta_2 = \delta'_2$, the above expression is less or equal to $|\delta_1 - \delta'_1|$. Now assume that $\delta_2 > \delta'_2$. Using $(a+b)^2 \le (1+x)a^2 + (1+x^{-1})b^2$ with $x = \frac{\delta_1+\delta'_2}{\delta_2-\delta'_2}$ yields

$$ \begin{aligned} \alpha_i^2 & \le \frac{|\delta_2 - \delta'_2|}{\delta_1 + \delta_2} \left( \frac{\delta'_1}{\delta'_1 + \delta'_2} \right)^2 + \frac{|\delta_1 - \delta'_1|^2 \delta'_2^2}{(\delta'_1 + \delta'_2)^2 (\delta_1 + \delta_2) (\delta_1 + \delta'_2)} \\ & \le \frac{|\delta_2 - \delta'_2|}{\delta_1 + \delta_2} \left( \frac{\delta'_1}{\delta'_1 + \delta'_2} \right)^2 + \frac{|\delta_1 - \delta'_1|}{\delta_1 + \delta_2}. \end{aligned} $$

There are at least $\delta_1 + \delta_2$ indices of type (d). If $[t_1, t_3) \cap [t_1, t'_3) \ne \emptyset$, then there are at most $|t_1 - t'_1|$ indices of type (a), $|t_3 - t'_3|$ indices of type (b) and $|t_2 - t'_2|$ indices of type (c). This leads us to 6

$$ \begin{aligned} \|X_t - X_{t'}\|_{\psi_2}^2 & \le |t_1 - t'_1| + \frac{9}{4}|t_2 - t'_2| + |t_3 - t'_3| \left(\frac{\delta_1}{\delta_2} + \frac{\delta'_1}{\delta'_2}\right)^2 + |\delta_2 - \delta'_2| \left(\frac{\delta'_1}{\delta'_1 + \delta'_2}\right)^2 + |\delta_1 - \delta'_1| \\ & \le \frac{7}{2}\rho^2(t, t'). \end{aligned} $$
Now assume that $[t_1, t_3) \cap [t_1, t'_3) = \emptyset$. For instance, assume that $t_3 \le t'_1$. Then,

$$
\begin{align*}
\|X_t - X_{t'}\|_{\psi_2}^2 &\le \delta_1 + \delta'_1 + (\delta_2 + \delta'_2) \left(\frac{\delta_1}{\delta_2} + \frac{\delta'_1}{\delta'_2}\right)^2 \\
&\le [\delta_1 + 2\delta_2] + [\delta'_1 + 2\delta'_2] + (t_3 - t'_3) \left(\frac{\delta_1}{\delta_2} + \frac{\delta'_1}{\delta'_2}\right)^2 \\
&\le 2\rho^2(t, t') ,
\end{align*}
$$

where we used that $|t'_1 - t_1| \ge \delta_1 + \delta_2$ and $|t'_2 - t_2| \ge \delta'_1 + \delta'_2$.

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

Proof of Lemma 18. Let us upper bound $|S_{k,q,\kappa}|$ by building a covering subset $S'_{k,q,\kappa}$ of $\mathcal{T}_+^{(k,q)}$. First, we consider the case where $q \ge 3$. Take a regular subgrid (containing $n$) of $\{1, \dots, n\}$ with radius $[r_{k,\kappa}^2/6]$. Then, given any $t_1$ on this grid, we build a regular grid (containing $t_1 + \lfloor n2^{-k+1} \rfloor)$ of $[t_1 + n2^{-k}, t_1 + n2^{-k+1}]$ with radius $[r_{k,\kappa}^2/6]$. Finally, given any such $t_1$ and $t_2$, we construct a regular grid (containing $t_2 + \lfloor n2^{q+1-k} \rfloor$ and $t_2 + \lfloor n2^{q-k} \rfloor$) of $[t_2 + 2^{q-k}n, t_2 + n2^{q+1-k}]$ with radius $[r_{k,\kappa}^2 2^{2q-5}]$.

$$
|S'_{k,q,\kappa}| \le \frac{n}{\lfloor r_{k,\kappa}^2/6 \rfloor} \cdot \frac{n2^{-k+1}}{\lfloor r_{k,\kappa}^2/6 \rfloor} \cdot \frac{n2^{q-k}}{\lfloor r_{k,\kappa}^2 2^{2q-5} \rfloor} \le c \frac{2^{k-q}}{\kappa^6} .
$$

It remains to check that $S'_{k,q,\kappa}$ is a covering subset. Consider any $t \in \mathcal{T}_+^{(k,q)}$ and define $\bar{t} \in S'_{k,q,\kappa}$ in such a way that $\bar{t}_1 - t_1 > 0$ is the smallest possible, then $\bar{t}_2 - t_2 > 0$ is the smallest possible and finally $\bar{t}_3 \ge t_3$ is the smallest possible. Obviously, we have $|\bar{t}_1 - t_1| \le r_{k,\kappa}^2/6$, $|\bar{t}_2 - t_2| \le r_{k,\kappa}^2/3$. Since $|t_3 - t_2| \ge 2^{q-k}n \ge 2^q r_{k,\kappa}^2/2$, we have $t_3 \ge \bar{t}_2$. $t_3 \in [\bar{t}_2 + 2^{q-k}n, \bar{t}_2 + 2^{q-k+1}n]$ so that $|\bar{t}_3 - t_3| \le (r_{k,\kappa}^2 2^{2q-5}) \vee (r_{k,\kappa}^2/3) \le r_{k,\kappa}^2 2^{2q-5}$ since $q \ge 3$. We have

$$
\rho(t, \bar{t}) \le \frac{r_{k,\kappa}^2}{2} + r_{k,\kappa}^2 2^{2q-5} \left[ \frac{\delta_1}{\delta_2} + \frac{\bar{\delta}_1}{\bar{\delta}_2} \right]^2 \le \frac{r_{k,\kappa}^2}{2} + \frac{r_{k,\kappa}^2}{2} \le r_{k,\kappa}^2,
$$

since both $\overline{\delta}_1/\overline{\delta}_2$ and $\delta_1/\delta_2$ are at most $2^{-q+1}$. This proves that $|S_{k,q,\kappa}| \le c \frac{2^{k-q}}{\kappa^6}$ for any $q \ge 3$. It remains to consider the case $q \le 2$. We build the same covering subsets as $S'_{k,q,\kappa}$ above except the radius of each of the subgrid is at most $\lceil r_{k,\kappa}^2/16 \rceil$. One easily checks that $|S'_{k,q,\kappa}| \le c' 2^k \kappa^{-6} \le 4c' 2^{k-q} \kappa^{-6}$. Then, given $t \in \mathcal{T}_+^{(k,q)}$, we build $\bar{t}$ as above. One easily checks that $|t_1 - \bar{t}_1| \le r_{k,\kappa}^2/16$, $|t_2 - \bar{t}_2| \le r_{k,\kappa}^2/8$ and that $|t_2 - \bar{t}_2| \le r_{k,\kappa}^2/8$ Since $\rho(t, \bar{t}) \le |t_1 - \bar{t}_1| + |t_2 - \bar{t}_2| + 4|t_3 - \bar{t}_3| \le r_{k,\kappa}^2$, we obtain the desired result.

□

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

Proof of Lemma 19. Recall that $\sigma^2(t) = \delta_1\delta_2/(\delta_1 + \delta_2)$ and write for short $\bar{t} = \pi_{k,\kappa}(t)$ and $(\overline{\delta}_1, \overline{\delta}_2)$ the corresponding segment length.

$$
\begin{align*}
|\sigma^2(t) - \sigma^2(\bar{t})| &= \left| \delta_1 \frac{\delta_2}{\delta_1 + \delta_2} - \bar{\delta}_1 \frac{\bar{\delta}_2}{\bar{\delta}_1 + \bar{\delta}_2} \right| &\le |\delta_1 - \bar{\delta}_1| + \delta_1 \frac{\overline{\delta}_1 |\delta_2 - \bar{\delta}_2| + \overline{\delta}_2 |\delta_1 - \bar{\delta}_1|}{(\delta_1 + \delta_2)(\overline{\delta}_1 + \bar{\delta}_2)} \\
&\le 2 [|t_1 - \bar{t}_1| + |t_2 - \bar{t}_2|] + \frac{\delta_1 \overline{\delta}_1}{\delta_2 \overline{\delta}_2} |t_3 - \bar{t}_3| \\
&\le 2\rho^2(t, \bar{t}) \le 2r_{k,\kappa}^2,
\end{align*}
$$
where we used in the second line that $|\delta_j - \delta'_j| \le |t_j - t'_j| + |t_j - t'_{j+1}|$ for $j = 1, 2$. Since $\sigma^2(t) \ge (\delta_1 \wedge \delta_2)/2 \ge n2^{-k-1}$, we obtain

$$ \frac{|\sigma(t) - \sigma(\pi_{k,\kappa}(t))|}{\sigma(t)} \le \frac{2r_{k,\kappa}^2}{\sigma^2(t)} \le 8\kappa^2 . $$

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

*Proof of Lemma 10.* Fix $\ell > 1$. For any $a > 0$, $b > 0$ and any $z > 0$, we have $b \log(z) \le az + b \log[(b/ae) \vee e]$. Applying Lemma 9, we deduce that, uniformly over all $t \in \mathcal{T}$, one has

$$ \mathbf{N}^2(t) \le 2\ell^2 \log \left( \frac{n(\delta_1(t) + \delta_2(t))}{\delta_1(t)\delta_2(t)} \right) + (c_1 + c_2) \log \left( \frac{1}{x} \right) + c_3 + c_1 \log \left( \frac{c_1}{\ell-1} \vee e \right), $$

with probability higher than $1-x$. Then, taking $x = \exp[-q/(2(c_1 + c_2))]$ and assuming that $q \ge 2[c_3 + c_1 \log(\frac{c_1}{\ell-1} \vee e]$, we conclude that $\mathbb{P}[A_{L,q}] \ge 1 - e^{-c'q}$. $\square$

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

**Acknowledgements** We are grateful to Guillem Rigaill for many stimulating discussions.

## References

[1] Ery Arias-Castro, Emmanuel J. Candès, and Arnaud Durand. Detection of an anomalous cluster in a network. *Ann. Statist.*, 39(1):278–304, 2011.

[2] Ery Arias-Castro, David L Donoho, and Xiaoming Huo. Near-optimal detection of geometric objects by fast multiscale methods. *IEEE Transactions on Information Theory*, 51(7):2402–2425, 2005.

[3] Ery Arias-Castro and Nicolas Verzelen. Community detection in dense random networks. *The Annals of Statistics*, 42(3):940–969, 2014.

[4] Sylvain Arlot. Minimal penalties and the slope heuristics: a survey. *arXiv preprint arXiv:1901.07277*, 2019.

[5] Sylvain Arlot, Alain Celisse, and Zaid Harchaoui. A kernel multiple change-point algorithm via model selection. *J. Mach. Learn. Res.*, 20:Paper No. 162, 56, 2019.

[6] Jushan Bai and Pierre Perron. Estimating and testing linear models with multiple structural changes. *Econometrica*, 66(1):47–78, 1998.

[7] 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.

[8] Yannick Baraud. Non-asymptotic minimax rates of testing in signal detection. *Bernoulli*, 8(5):577–606, 2002.

[9] Michèle Basseville and Igor V Nikiforov. *Detection of abrupt changes: theory and application*, volume 104. prentice Hall Englewood Cliffs, 1993.

[10] Richard Bellman. On the approximation of curves by line segments using dynamic programming. *Communications of the ACM*, 4(6):284, 1961.

[11] Lucien Birgé and Pascal Massart. Gaussian model selection. *Journal of the European Mathematical Society*, 3(3):203–268, 2001.

[12] Leif Boysen, Angela Kempe, Volkmar Liebscher, Axel Munk, and Olaf Wittich. Consistencies and rates of convergence of jump-penalized least squares estimators. *Ann. Statist.*, 37(1):157–183, 2009.
[13] E Brodsky and Boris S Darkhovsky. *Non-parametric statistical diagnosis: problems and methods*, volume 509. Springer Science & Business Media, 2013.

[14] E Brodsky and Boris S Darkhovsky. *Nonparametric methods in change point problems*, volume 243. Springer Science & Business Media, 2013.

[15] E Carlstein, HG Müller, and D Siegmund. Change-point problems (vol. 23 of lecture notes—monograph series). *Institute of Mathematical Statistics*, 1994.

[16] Hock Peng Chan and Guenther Walther. Detection with the scan and the average likelihood ratio. *Statist. Sinica*, 23(1):409–428, 2013.

[17] Haeran Cho and Claudia Kirch. Localised pruning for data segmentation based on multiscale change point procedures. *arXiv preprint arXiv:1910.12486*, 2019.

[18] Miklos Csorgo and Lajos Horváth. *Limit theorems in change-point analysis*. John Wiley & Sons Chichester, 1997.

[19] L Dumbgen. The asymptotic behavior of some nonparametric change-point estimators. *The Annals of Statistics*, 19(3):1471–1495, 1991.

[20] Lutz Dumbgen and Vladimir G Spokoiny. Multiscale testing of qualitative hypotheses. *Annals of Statistics*, pages 124–152, 2001.

[21] Birte Eichinger and Claudia Kirch. A mosum procedure for the estimation of multiple random change points. *Bernoulli*, 24(1):526–564, 2018.

[22] Farida Enikeeva and Zaid Harchaoui. High-dimensional change-point detection under sparse alternatives. *Annals of statistics*, 46(5), 2018.

[23] Zhou Fan and Leying Guan. Approximate $\ell_0$-penalized estimation of piecewise-constant signals on graphs. *The Annals of Statistics*, 46(6B):3217–3245, 2018.

[24] Walter D. Fisher. On grouping for maximum homogeneity. *Journal of the American statistical Association*, 53(284):789–798, 1958.

[25] 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.

[26] Piotr Fryzlewicz. Wild binary segmentation for multiple change-point detection. *The Annals of Statistics*, 42(6):2243–2281, 2014.

[27] Piotr Fryzlewicz. Tail-greedy bottom-up data decompositions and fast multiple change-point detection. *The Annals of Statistics*, 46(6B):3390–3421, 2018.

[28] Piotr Fryzlewicz. Detecting possibly frequent change-points: Wild binary segmentation 2 and steepest-drop model selection. *Journal of the Korean Statistical Society*, pages 1–44, 2020.

[29] Piotr Fryzlewicz. Narrowest significance pursuit: inference for multiple change-points in linear models. *arXiv preprint arXiv:2009.05431*, 2020.

[30] Chao Gao, Fang Han, and Cun-Hui Zhang. On estimation of isotonic piecewise constant signals. *Ann. Statist.*, 48(2):629–654, 2020.

[31] Damien Garreau and Sylvain Arlot. Consistent change-point detection with kernels. *Electron. J. Stat.*, 12(2):4440–4486, 2018.

[32] Meyer A. Girshick and Herman Rubin. A bayes approach to a quality control model. *The Annals of Mathematical Statistics*, 23(1):114–125, 1952.

[33] Adityanand Guntuboyina, Donovan Lieu, Sabyasachi Chatterjee, Bodhisattva Sen, et al. Adaptive risk bounds in univariate total variation denoising and trend filtering. *The Annals of Statistics*, 48(1):205–229, 2020.

[34] Zaid Harchaoui and Céline Lévy-Leduc. Multiple change-point estimation with a total variation penalty. *J. Amer. Statist. Assoc.*, 105(492):1480–1493, 2010.

[35] Douglas M. Hawkins. Testing a sequence of observations for a shift in location. *J. Amer. Statist. Assoc.*, 72(357):180–186, 1977.

[36] David V Hinkley. Inference about the change-point in a sequence of random variables.
*Biometrika*, pages 1–17, 1970.

[37] David V. Hinkley and Elizabeth A. Hinkley. Inference about the change-point in a sequence of binomial variables. *Biometrika*, 57:477–488, 1970.

[38] Holger Hoefling. A path algorithm for the fused lasso signal approximator. *Journal of Computational and Graphical Statistics*, 19(4):984–1006, 2010.

[39] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Uniform, nonparametric, non-asymptotic confidence sequences. *arXiv preprint arXiv:1810.08240*, 2018.

[40] Yu. I. Ingster and I. A. Suslina. *Nonparametric goodness-of-fit testing under Gaussian models*, volume 169 of *Lecture Notes in Statistics*. Springer-Verlag, New York, 2003.

[41] Yuri I. Ingster. Asymptotically minimax hypothesis testing for nonparametric alternatives. I. *Math. Methods Statist.*, 2(2):85–114, 1993.

[42] Rebecca Killick, Paul Fearnhead, and Idris A Eckley. Optimal detection of changepoints with a linear computational cost. *Journal of the American Statistical Association*, 107(500):1590–1598, 2012.

[43] Jiyao Kou. Identifying the support of rectangular signals in gaussian noise. *arXiv preprint arXiv:1703.06226*, 2017.

[44] 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.

[45] Marc Lavielle and Eric Moulines. Least-squares estimation of an unknown number of shifts in a time series. *Journal of time series analysis*, 21(1):33–59, 2000.

[46] Émilie Lebarbier. Detecting multiple change-points in the mean of gaussian process by model selection. *Signal processing*, 85(4):717–736, 2005.

[47] Kevin Lin, James Sharpnack, Alessandro Rinaldo, and Ryan J Tibshirani. Approximate recovery in changepoint problems, from $\ell_2$ estimation error rates. *arXiv preprint arXiv:1606.06746*, 2016.

[48] Haoyang Liu, Chao Gao, and Richard J Samworth. Minimax rates in sparse, high-dimensional changepoint detection. *arXiv preprint arXiv:1907.10012*, 2019.

[49] Yue S Niu, Ning Hao, and Heping Zhang. Multiple change-point detection: A selective overview. *Statistical Science*, 31(4):611–623, 2016.

[50] Ewan S. Page. Continuous inspection schemes. *Biometrika*, 41(1/2):100–115, 1954.

[51] Ewan S. Page. A test for a change in a parameter occurring at an unknown point. *Biometrika*, 42(3/4):523–527, 1955.

[52] Ewan S. Page. On problems in which a change in a parameter occurs at an unknown point. *Biometrika*, 44(1/2):248–252, 1957.

[53] Guillem Rigaill. Pruned dynamic programming for optimal multiple change-point detection. *arXiv preprint arXiv:1004.0887*, 17, 2010.

[54] Andrew Jhon Scott and M Knott. A cluster analysis method for grouping means in the analysis of variance. *Biometrics*, pages 507–512, 1974.

[55] Alexander Tartakovsky, Igor Nikiforov, and Michele Basseville. *Sequential analysis: Hypothesis testing and changepoint detection*. Chapman and Hall/CRC, 2014.

[56] Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. Sparsity and smoothness via the fused lasso. *Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, 67(1):91–108, 2005.

[57] Charles Truong, Laurent Oudre, and Nicolas Vayatis. Selective review of offline change point detection methods. *Signal Processing*, 167:107299, 2020.

[58] Abraham Wald. Sequential tests of statistical hypotheses. *The annals of mathematical statistics*, 16(2):117–186, 1945.
[59] Daren Wang, Yi Yu, and Alessandro Rinaldo. Univariate mean change point detection: Penalization, CUSUM and optimality. Electron. J. Stat., 14(1):1917-1961, 2020.

[60] Tengyao Wang and Richard J. Samworth. High dimensional change point estimation via sparse projection. J. R. Stat. Soc. Ser. B. Stat. Methodol., 80(1):57-83, 2018.

[61] Yi-Ching Yao. Estimating the number of change-points via schwarz'criterion. Statistics & Probability Letters, 6(3):181-189, 1988.

[62] Yi-Ching Yao and S. T. Au. Least-squares estimation of a step function. Sankhyā Ser. A, 51(3):370-381, 1989.

[63] Nancy R Zhang and David O Siegmund. A modified bayes information criterion with applications to the analysis of comparative genomic hybridization data. Biometrics, 63(1):22-32, 2007.