# Optimal Change-Point Detection and Localization

Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, Patricia Reynaud-Bouret

► To cite this version:

Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, Patricia Reynaud-Bouret. Optimal Change-Point Detection and Localization. Annals of Statistics, 2023, 51 (4), pp.1586-1610. 10.1214/23-AOS2297. hal-04251607

HAL Id: hal-04251607

https://hal.science/hal-04251607v1

Submitted on 20 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Optimal Change-Point Detection and Localization

Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, and Patricia Reynaud-Bouret

November 17, 2020

Abstract

Given a times series $\mathbf{Y}$ in $\mathbb{R}^n$, with a piece-wise constant mean and independent components, the twin problems of change-point detection and change-point localization respectively amount to detecting the existence of times where the mean varies and estimating the positions of those change-points. In this work, we tightly characterize optimal rates for both problems and uncover the phase transition phenomenon from a global testing problem to a local estimation problem. Introducing a suitable definition of the energy of a change-point, we first establish in the single change-point setting that the optimal detection threshold is $\sqrt{2 \log \log(n)}$. When the energy is just above the detection threshold, then the problem of localizing the change-point becomes purely parametric: it only depends on the difference in means and not on the position of the change-point anymore. Interestingly, for most change-point positions, including all those away from the endpoints of the time series, it is possible to detect and localize them at a much smaller energy level. In the multiple change-point setting, we establish the energy detection threshold and show similarly that the optimal localization error of a specific change-point becomes purely parametric. Along the way, tight optimal rates for Hausdorff and $l_1$ estimation losses of the vector of all change-points positions are also established. Two procedures achieving these optimal rates are introduced. The first one is a least-squares estimator with a new multiscale penalty that favours well spread change-points. The second one is a two-step multiscale post-processing procedure whose computational complexity can be as low as $O(n \log(n))$. Notably, these two procedures accommodate with the presence of possibly many low-energy and therefore undetectable change-points and are still able to detect and localize high-energy change-points even with the presence of those nuisance parameters.

# 1 Introduction

Following a long historical line of work, starting with Wald [58], Girshick and Rubin [32], Page [50], and Fisher [24] in the 1940-1950's, leading to a huge bibliography including several prominent monographs such as [9, 13-15, 18, 55], and which is still vivid (e.g. [17, 28, 59]), we consider the prototypical problem of univariate change-point analysis. Let $\mathbf{Y} = (Y_1, \dots, Y_n)$ be a time series with values in $\mathbb{R}^n$, with unknown mean vector $\theta = (\theta_1, \dots, \theta_n)$ in $\mathbb{R}^n$. Change-point analysis amounts to studying possible variations in the mean vector $\theta$. In this work, we focus our attention on the independent observation setting

$$ Y_i = \theta_i + \epsilon_i, \quad i = 1, \dots, n, \qquad (1) $$

where the noise random vector $\epsilon = (\epsilon_1, \dots, \epsilon_n)$ is made of independent mean-zero random variables satisfying a sub-Gaussian condition

$$ \mathbb{E}[e^{t\epsilon_i}] \le e^{\sigma^2 t^2/2} \quad \text{for all } t \text{ in } \mathbb{R}, \quad \text{for } i = 1, \dots, n, $$
where $\sigma$ is known. By homogeneity and standardization, we assume henceforth that $\sigma = 1$. Our general objective is twofold: first, we carefully analyze the intrinsic difficulty of several detection and localization problems, thereby closing long-standing gaps between the early asymptotic results and recent non-asymptotic ones. This allows us to define desirable specifications for a change-point estimation method. Second, we introduce two procedures achieving these specifications.

## 1.1 Model and change-point procedures

Since we view the mean vector $\theta$ as piece-wise constant vector, we can define it through the change points. Given $\theta$ in $\mathbb{R}^n$, there exists an integer $0 \le K \le n-1$, a vector of integers $\tau^* = (\tau_1^*, \dots, \tau_K^*)$ satisfying $1 = \tau_0^* < \tau_1^* < \dots < \tau_K^* < \tau_{K+1}^* = n+1$, a vector $\mu = (\mu_1, \dots, \mu_{K+1})$ in $\mathbb{R}^{K+1}$ satisfying $\mu_k \ne \mu_{k+1}$ for all $k$ in $\{1, \dots, K\}$ such that

$$ \theta_i = \sum_{k=1}^{K+1} \mu_k \mathbf{1}_{\tau_{k-1}^* \le i < \tau_k^*} . \qquad (2) $$

Then, $\tau_k^*$ is called the *position* of the $k$-th change-point (or sometimes for the sake of simplicity the $k$-th change-point) and $\Delta_k = \mu_{k+1} - \mu_k$ is called the *height* of the $k$-th change-point in $\theta$. It follows from (2) that $\theta$ is uniquely defined by $\tau^*$ and $\mu$. As a consequence, one may easily deduce an estimator of $K$, $\tau^*$, and $\mu$ from an estimator of $\theta$. Conversely, any estimator $\hat{\tau}$ with length $\hat{K}$ of the change-points positions leads to an estimator $\hat{\theta}$ by simply plugging the empirical mean on the corresponding partition, that is $\hat{\theta}_i = \sum_{k=1}^{\hat{K}+1} \mathbf{1}_{\hat{\tau}_{k-1} \le i \le \hat{\tau}_k - 1}(\hat{\tau}_k - \hat{\tau}_{k-1})^{-1} [\sum_{j=\hat{\tau}_{k-1}}^{\hat{K}-1} Y_i]$ for $i = 1, \dots, n$. Hence, any change-point estimation method may be indifferently interpreted as an estimator of $\theta$ and $\tau^*$.

In general, the number $K$ of change-points is supposed to be unknown. Still, for historical and mathematical reasons to be discussed below, the literature usually divides into two settings: the *single change-point setting*<fnref n="1" /> where one assumes that $K \le 1$ and the *multiple change-point setting* where $K$ is possibly arbitrarily large. In the next paragraphs, we provide a short account of classical approaches for multiple change-point estimation, and then we explain the connections between those approaches in the single change-point setting. In the sequel, we write $\Theta_K \subset \mathbb{R}^n$ for the collection of vectors $\theta$ with $K$ change-points exactly.

## 1.2 Main approaches for change-point analysis

It is beyond the scope of this paper to give an exhaustive survey of existing methods and we refer the interested reader to [49, 57]. Still, we can roughly divide most procedures into two general categories: the ones based on minimization of (penalized) least-squares criteria and the ones based on test statistics, mostly related to the CUSUM statistic.

**Penalized least-squares minimization** If the number $K$ of change-points is known and if the noise vector follows an homoscedastic Gaussian distribution, then the maximum likelihood estimator of $\theta$ is equal to the least-squares estimator $\hat{\theta}_{LS,K} = \arg \min_{\theta' \in \Theta_K} \sum_{i=1}^n (Y_i - \theta_i')^2$. While $\Theta_K$ is not convex, it has been observed in the pioneering work of Bellman [10] that $\hat{\theta}_{LS,K}$ can be efficiently computed by a dynamic programming algorithm, whose worst-case complexity is $O(n^2)$ operations. In practice, $K$ is unknown and it is natural to select it by adding a penalty term, such as BIC [62] or more involved forms of penalties [46] arising from the general theory of model

<footnote n="1">¹It is sometimes referred as at most one change-point setting in the literature.</footnote>
selection [11]. On the computational aspect, the quadratic complexity turns out to be prohibitive for some large-scale problems arising for instance in genomics. To address this issue, Killick et al. [42] (see also [53]) have developed pruning techniques that accelerate the dynamic programming algorithm and lead to a quasi-linear time complexity in favorable situations.

More generally, penalized least-squares criteria of the form $\min_{\theta' \in \Theta_K} \sum_{i=1}^n (Y_i - \theta_i')^2 + \text{pen}(\theta')$ may involve penalty terms $\text{pen}(\theta')$ that do not only depend on the number $K$ of change-points of $\theta'$. For instance, Zhang and Siegmund [63] argue for a penalty $\text{pen}(\theta')$ that also depends on the spacing between the change-points. Alternatively, choosing $\text{pen}(\theta')$ proportional to the total variation norm $\|\theta'\|_{TV} = \sum_{i=2}^n |\theta_i' - \theta_i'|$ corresponds to the Fused Lasso estimator [56]. Efficient solvers compute the Fused Lasso estimator in quasi-linear time [38].

**Binary segmentation, CUSUM, and multiscale methods.** Beside penalty-based approaches, the other broad class of methods is based on the CUSUM statistics. In the sequel, $\mathcal{T}_3$ refers to the collection of triads, that is the set of all triplets of integers $t = (t_1, t_2, t_3)$ such that $1 \le t_1 < t_2 < t_3 \le n + 1$. Given $t = (t_1, t_2, t_3)$ in $\mathcal{T}_3$, the CUSUM statistic at $t$ is defined as the weighted difference of empirical means on $[t_1, t_2)$ and $[t_2, t_3)$

$$ \mathbf{C}(\mathbf{Y}, \mathbf{t}) = \left[ \frac{\sum_{i=t_2}^{t_3-1} Y_i}{t_3 - t_2} - \frac{\sum_{i=t_1}^{t_2-1} Y_i}{t_2 - t_1} \right] \sqrt{\frac{(t_2 - t_1)(t_3 - t_2)}{t_3 - t_1}} . \quad (3) $$

For homoscedastic Gaussian noise, this statistic also corresponds to likelihood ratio test statistic of the null hypothesis $\{\theta \text{ is constant over } [t_1, t_3]\}$ versus $\{\theta \text{ has one change-point at } t_2\}$. Under the null hypothesis, $\mathbf{C}(\mathbf{Y}, \mathbf{t})$ follows a standard normal distribution. In principle, one then could adopt a multiple-testing perspective and apply all tests based on all CUSUM statistics. However, there are two main caveats with this naive approach. First, $|\mathcal{T}_3|$ is of the order of $n^3/6$ which can lead to a prohibitive $O(n^3)$ computational complexity. Second, there is no straightforward way of transforming a collection of $|\mathcal{T}_3|$ $p$-values into a single change-point estimator $\hat{\tau}$. This is why most earlier CUSUM-based change-point procedures follow greedy approaches. CUSUM statistics have a long history in the single change-point literature. Originally, Hinkley [36] maximizes the CUSUM $\mathbf{C}(\mathbf{Y}, (1, t, n + 1))$ over all possible change-point positions $t = 2, \dots, n + 1$. Binary Segmentation (BS) [54] algorithm for multiple change-points detection amounts to recursively cut the time series into two parts by applying Hinkley's method at each step. However, BS does not consistently estimate the change-points which lead to the introduction of many variants of BS including Wild Binary Segmentation [26, 27, 29, 44, 59, 60]. Some of these procedure exhibit a quasi-linear time complexity [27]. While the connection is less clear, other methods based on moving sums such as MOSUM [21] may also be interpreted as an aggregation procedure of the CUSUM statistics with symmetric windows $\mathbf{t} = (\tau - h, \tau, \tau + h)$ where $1 \le \tau - h < \tau + h \le n + 1$. An important aspect of many of these procedures is that they consider CUSUM (3) statistics at many different scales $(t_3 - t_1)$ thereby being able to detect close change-points with large heights and change-points whose heights are small but which are distant from any other change-point.

In the single change-point setting where the statistician knows that $K = 1$, the estimator $\hat{\tau}$ maximizing the CUSUM equals the change-point of the least-squares estimator $\hat{\theta}_{LS,1}$, so that both procedures are equivalent. Hence, the distinction between CUSUM-based and least-squares-based procedures is not clear in that setting.

**Post-processing methods.** The change-points estimator $\tilde{\tau}$ produced by one of the previous methods is sometimes refined in a second step by removing spurious estimated change-points [27]
or/and improving the precision of the estimated change-points positions by a local CUSUM maximization (see e.g. Sect.3.2 in [26]). See also Lin et al. [47] for another recent post-processing method.

## 1.3 Statistical Problems

There are several ways of assessing the quality of a change-point procedure, whose choice mainly depends on the question of interest. As mentioned earlier, one can easily deduce an estimator of $\tau^*$ from an estimator $\theta$ (and conversely). However, $\tau^*$ is not a continuous function of $\theta$ and a near perfect estimator of $\theta$ does not necessarily lead to a precise estimation of the number of change-points. We can broadly summarize the statistical objectives into three classes, that are detailed below.

(a) **Signal Denoising.** Here, one mainly aims at estimating the mean $\theta$ in $\mathbb{R}^n$ from $\mathbf{Y}$ taking into account the side information that $\theta$ is a piece-wise constant vector.

(b) **Change-points Detection.** The objective is now to detect the existence of change-points in $\theta$. It is easier to state this problem in the single change-point setting where $K \le 1$. Indeed, this boils down to testing the hypothesis $\{\theta \in \Theta_0\}$ (there is no change-point) versus $\{\theta \in \Theta_1\}$ (there is exactly one change-point). Obviously, detecting one change-point is feasible only if its height $\Delta_1 = \mu_2 - \mu_1$ is not too small (in absolute value). As a consequence, a suitable detection procedure should have a small type I error probability as well as be able to detect with high probability a change-point whose height is not too small. We shall further formalize this problem in the next subsection. For multiple change-points problems, one can possibly interpret the problem of change-points detection as that of estimating the number $K$ of change-points (e.g. [25, 26, 28]). Unfortunately, stating this as an estimation problem of the functional $K$ may hide the fact that, in a vector $\theta$, some change-points may be easier to detect than some others. One of our contribution in this work is to propose an alternative formalization of this problem.

(c) **Change-point Localization.** Again, we start with the single change-point setting where $\theta$ is in $\Theta_1$. One aims at building an estimator $\hat{\tau}$ of $\tau_1$ such that $|\hat{\tau} - \tau_1|$ is the smallest possible. Intuitively, localization is only feasible if the change-point has been detected so that some minimal assumption on the height has to be done. In the multiple change-points setting, there are several ways of measuring the localization error that depend whether one is interested into estimating a specific change-point, a subset of significant change-points or the whole set of change-points. Given a vector $\tau$ with length $|\tau|$ and with coordinates $(\tau_1, \dots, \tau_{|\tau|})$ and one change-point $\tau'$, let the distance $d_{H,1}(\tau, \tau') = \min_{i=1,\dots,|\tau'|} |\tau_i - \tau'|$ between $\tau'$ and its closest element in $\tau$. Hence, for any $1 \le k \le K$, $d_{H,1}(\hat{\tau}, \tau_k^*)$ quantifies to what extent $\hat{\tau}$ estimates well the true change-point $\tau_k^*$. We refer to this as a point-wise loss. Besides, we define

$$d_{H,1}(\tau, \tau^*) = \max_{j=1,\dots,|\tau^*|} d_{H,1}(\tau, \tau_j^*); \quad d_H(\tau, \tau^*) = \max\{d_{H,1}(\tau, \tau^*), d_{H,1}(\tau^*, \tau)\}, \quad (4)$$

which respectively correspond to the screening distance and Hausdorff distance between the sets $\{\tau_i^*, i = 1, \dots, |\tau^*|\}$ and $\{\tau_i, i = 1, \dots, |\tau|\}$ (see [47] for instance). For simplicity, we will call them the screening distance from $\tau^*$ to $\tau$, and the Hausdorff distance between $\tau^*$ and $\tau$, thereby confusing vectors and sets of their values. In some sense, the Hausdorff distance $d_H(\tau, \tau^*)$ should be understood as an uniform error measure between $\tau^*$ and $\tau$. Finally,
when the change-points vectors $\tau$ and $\tau^*$ have the same length ($|\tau| = |\tau^*|$), one considers

$$d_W(\tau, \tau^*) = \sum_{j=1}^{|\tau|} |\tau_j - \tau_j^*|, \qquad (5)$$

that corresponds, up to the re-normalization by $|\tau|$, to the $L_1$-Wasserstein distance between the empirical probability measures associated with the vectors. This can be interpreted an $l_1$-loss and is referred henceforth to as the Wasserstein distance between $\tau^*$ and $\tau$.

In this manuscript, we mainly focus on the two latter problems where the statistician is more interested on change-points in themselves than on the signal $\theta$. Before explaining our contributions, we summarize how these testing and estimation problems are considered in the literature as well as the best known bounds.

## 1.4 State of the art

Although we are not specifically interested in signal denoising, we briefly discuss the literature as this viewpoint falls into the well established field of nonparametric statistic and is well understood. In particular, Gao et al. [30] have studied the optimal (in the minimax sense) risk $E[\|\hat{\theta} - \theta\|^2]$ achievable by any estimator when $\theta$ belongs to $\Theta_K$. For $K \ge 2$, the optimal risk is (up to a multiplicative numerical constant) of the order of $K \log(2n/K)$ (see also [5, 46]) whereas, for $K = 1$, the optimal risk is qualitatively different and is of the order of $\log \log(16n)$. All these bounds are achieved by least-squares estimators $\hat{\theta}_{LS,K}$ [30]. The penalized least-squares estimator of Lebarbier [46] also achieves such bounds for all $K \ge 2$ without requiring the knowledge of $K$. By constrast, the Fused LASSO achieves similar near-optimal risk bounds for $K \ge 2$ if we further restrict our attention to evenly spaced change-points [33]. Unfortunately, for some other $\theta$ in $\Theta_K$ with non-even spaced change-points, the risk of the Fused LASSO is much large; see Theorem 4.1 in [23].

In fact, most works dedicated to such penalized least-squares procedures for signal estimation provide, as in [30], theoretical risk bounds for the targeted mean vector estimation and then, empirically evaluate their performances in terms of change-points detection and localization error (see e.g. [5, 34, 46, 47]). Intuitively, near optimal signal estimation risk bounds should suggest that the procedures detect most change-points and localize them well. While this heuristic argument is appealing, tentative formalizations of it lead to quite pessimistic results [5, 47] both in terms of detection and localization.

Since the difficulty of signal denoising qualitatively changes between the single change-point and the multiple change-points settings, the remainder of the literature review is organized according to these two settings.

**Detection of a single change-point.** As mentioned in the previous section, we need to formalize the significance of a single change-point $\tau_1^*$. Given $\theta$ in $\Theta_1$, we define its energy

$$\mathbf{E}_1(\theta) = |\Delta_1| \sqrt{\frac{(\tau_1^* - 1)(n + 1 - \tau_1^*)}{n}}. \qquad (6)$$

The energy $\mathbf{E}_1(\theta)$ is equal to the $l_2$ distance between $\theta$ and $\Theta_0$ and thereby quantifies the difficulty of assessing the existence of $\tau_1^*$. As an alternative to the energy $\mathbf{E}_1(\theta)$, some authors (e.g. [30]) consider the quantity $\mathbf{E}_{\min}(\theta) = \Delta_1^2[(\tau_1^* - 1) \wedge (n + 1 - \tau_1^*)]$, where $x \wedge y$ stands for the minimum
of x and y. Both quantities are equivalent ($\mathbf{E}_1^2(\theta) \le \mathbf{E}_{\min}^2(\theta) \le 2\mathbf{E}_1^2(\theta)$), but we use $\mathbf{E}_1(\theta)$ as it is more intrinsic to the change-point problem. Testing the null hypothesis $\{\theta \in \Theta_0\}$ versus $\{\theta \in \Theta_1\}$ has been extensively studied since the seminal work of [35, 51, 52]. Csörgö and Horváth [18, eq.(3.5.22)] have proved that the test rejecting the null for large values of scan CUSUM statistic $\max_{2 \le t \le n} |\mathbf{C}(\mathbf{Y}; (1, t, n+1))|$ is asymptotically powerful when $\mathbf{E}_1(\theta)/\sqrt{\log \log(n)} \to \infty$. Recently, Gao et al. [30] established a non-asymptotic counterpart of this result as well as a minimax lower bound, stating that no test is able to reject the null with high probability simultaneously for all $\theta$ in $\Theta_1$ such that $\mathbf{E}_1(\theta) \ge c_1 \sqrt{\log \log(16n)}$ where $c_1$ is a small numerical constant.

**Localization of a single change-point.** Recall that, in this setting, both the least-squares estimator and the max CUSUM estimator are equal and are referred to $\hat{\tau}$ in this paragraph. Early work from [36, 37] considered an asymptotic setting where $\Delta_1$ is constant and established that $|\hat{\tau} - \tau_1^*| = O_P(1)$. Later, Dümbgen [19] and Csörgö and Horváth [18] have worked out the asymptotic distribution of $|\hat{\tau} - \tau_1^*|$ under the assumption that the change-point energy is high-enough so that $\mathbf{E}_1(\theta)/\sqrt{\log \log(n)} \to \infty$ and under the restriction that $\tau_1^*$ is proportional to $n$. In particular, one deduces from this asymptotic distribution that $|\hat{\tau} - \tau_1^*| = O_P(1/\Delta_1^2)$. When $\Delta_1^2 = O(1)$, this bound is minimax optimal (see Proposition 10 in [60]). Up to our knowledge, there are few non-asymptotic localization results. Still, we can easily deduce from Gao et al [30] that, with positive probability, $|\hat{\tau} - \tau_1^*| \le c \log \log(n)/\Delta_1^2$ as long as $\mathbf{E}_1(\theta) \ge c' \sqrt{\log \log(n)}$, where $c$ and $c'$ are positive constants.

**Detection for multiple change-points.** Early works typically considered an asymptotic setting where $\theta_i = g(i/n)$ and $g$ is a fixed $(K+1)$-step function defined on $[0, 1]$. Notably, Yao and Au [62] proved that the least-squares estimator with a BIC penalty selects a number $\hat{K}$ converging in probability to $K$. To formalize the detection problem in a non-asymptotic setting, and define the significance of each change-point, we extend the notion of change-point energy $\mathbf{E}_1(\theta)$ for $\theta$ in $\Theta_1$. Given a vector $\theta$, with $K$ change-points and an integer $1 \le k \le K$, we define the energy $\mathbf{E}_k(\theta)$ of the $k$-th change-point by

$$ \mathbf{E}_k(\theta) = |\Delta_k| \sqrt{\frac{(\tau_{k+1}^* - \tau_k^*)(\tau_k^* - \tau_{k-1}^*)}{\tau_{k+1}^* - \tau_{k-1}^*}} \quad (7) $$

so that this matches (6) when $k = K = 1$. We show later that $\mathbf{E}_k^2(\theta)$ equals the squared $l_2$ distance between $\theta$ and its best approximation by a vector $\theta'$ with $(K-1)$ change-points $(\tau_1^*, \dots, \tau_{k-1}^*, \tau_{k+1}^*, \dots, \tau_K^*)$. As in the single change-point case, one easily checks that $\mathbf{E}_k^2(\theta)$ is equivalent (up to a factor 2) to $\Delta_k^2[(\tau_{k+1}^* - \tau_k^*) \wedge (\tau_k^* - \tau_{k-1}^*)]$. The non-asymptotic counterpart of the detection problem would then correspond to establishing minimal condition on $\mathbf{E}_k^2(\theta)$ so that a change-point procedure detects $\hat{K} = K$ change-points with high probability. As an alternative to $\min_{1 \le k \le K} \mathbf{E}_k^2(\theta)$, most recent papers in the literature (see e.g. [25, 27, 59, 60]) use the following quantity

$$ \mathbf{E}_{min}(\theta) = \left[ \min_{1 \le k \le K} |\Delta_k| \right] \left[ \min_{0 \le k \le K} |\tau_{k+1}^* - \tau_k^*|^{1/2} \right] \quad (8) $$

When all $|\Delta_k|$ are equal and all change-points $\tau_k^*$ are equi-spaced, then $\mathbf{E}_{min}^2(\theta) \ge \min_k \mathbf{E}_k^2(\theta)$ but $\mathbf{E}_{min}^2(\theta)$ is possibly much smaller than $\min_k \mathbf{E}_k^2(\theta)$ for heterogeneous jumps. In most of the modern analyses of change-point procedures [25, 27, 59], authors usually aim at establishing that $\hat{K} = K$ with high probability as long as $\mathbf{E}_{min}^2(\theta) \ge c \log(n)$ (for some $c > 0$). Such a detection property is achieved by some penalized least-squares procedures [59] and CUSUM-based procedures (e.g. [7, 59]). Notably, Frick et al. [25] prove that their SMUCE procedure consistently estimates $K$
under the tighter condition $E_{\min}(\theta) \ge c \log(n/\min_k(\tau_{k+1}^* - \tau_k^*))$ which is of the order of $\log(K+1)$ when there are few equi-spaced change-points. Conversely, Chan and Walther [16] (see [2] for earlier results) have established in the particular setting of change-point detection that no procedure is able to consistently estimate $K$ unless $\min_k E_k^2(\theta) \ge 2\log[n/\min_k(\tau_{k+1}^* - \tau_k^*) \wedge (\tau_k^* - \tau_{k-1}^*)]$.

**Localization of several change-points.** In their asymptotic setting where $\theta_i = g(i/n)$ for a fixed function $g$, Yao and Au [62] established the asymptotic distribution of $(\hat{\tau}_k - \tau_k^*)$, $k = 1, \dots, K$ where the vector $\hat{\tau}$ is that of the least-squares estimator $\hat{\theta}_{LS,K}$. The differences $\hat{\tau}_k - \tau_k^*$ are thus proved to be asymptotically independent and to have limiting sub-exponential distributions with parameter $1/\Delta_k^2$. This result was later extended by Bai and Perron [6] and Lavielle and Moulines [45] to asymptotic settings where $K$ is still fixed but the $|\Delta_k|$'s are allowed to converge to zero. In the non-asymptotic setting, Frick et al. [25], Wang et al. [59], Baranowski et al. [7] established that, as soon as $E_{\min}(\theta) \ge c \log(n)$, the estimator $\hat{\tau}$ satisfies $d_H(\hat{\tau}, \tau^*) \le c' \log(n)/[\min_k \Delta_k^2]$ with high probability. It follows from the analysis of the single change-point case that this upper bound is optimal up to a (possible) $\log(n)$ term. In an almost concomitant but independent work, Cho and Kirch [17] have recently proved that their multiscale MOSUM procedure satisfies the tighter bound $d_H(\hat{\tau}, \tau^*) \le c' \log(K+1)/[\min_k \Delta_k^2]$.

## 1.5 Our contribution

We now describe our main results.

**Pinpointing minimal conditions for change-point detection.** In the single change-point setting, we establish that the uniform detection threshold for the energy $E_1(\theta)$ is at $\sqrt{2\log\log(n)}$. Importantly, change-points $\tau_1^*$ that are away from the endpoints of the time series can be detected at energy level $E_1(\theta)$ of the order $\sqrt{2\log\log(16n/(\tau_1^* \wedge (n+1-\tau_1^*))})$, which can be as small as a constant for $\tau_1^*$ proportional to $n$. Regarding the multiple change-points setting, we introduce a new way of assessing the detection of change-points. An estimator $\hat{\tau}$ is said to detect $\tau_k^*$ if some estimated change-point $\hat{\tau}_l$ belongs to $[(\hat{\tau}_k^* + \hat{\tau}_{k-1}^*)/2, (\hat{\tau}_k^* + \hat{\tau}_{k+1}^*)/2)$. Conversely, $\hat{\tau}$ does not detect any spurious change-point if the interval $[(\hat{\tau}_k^* + \hat{\tau}_{k-1}^*)/2, (\hat{\tau}_k^* + \hat{\tau}_{k+1}^*)/2)$ contains at most one estimated change-point $\hat{\tau}_l$. Any change-point $\tau_k^*$ is detectable by a procedure $\hat{\tau}$ whose probability of estimating spurious change-point is small as soon as

$$E_k^2(\theta) \ge c \log \left( \frac{c'n}{(\tau_{k+1}^* - \tau_k^*) \wedge (\tau_k^* - \tau_{k-1}^*)} \right), \quad (9)$$

thereby matching (up to constants) the minimax rate for the simpler problem of segment detection [16]. What matters here is that we prove such detectability results in settings where we allow an arbitrarily large number of change-points to have a low energy. This implies that the presence of many arbitrarily small change-points does not make high-energy change-points much harder to detect.

**Transition from a global to a local estimation problem.** As soon as a change-point $\tau_k^*$ is detectable (as its energy is above the appropriate threshold, then the change-point $\tau_k^*$ can be estimated at a sub-exponential rate with scale $\Delta_k^2$). As a consequence, the error rate for estimating a specific change-point is purely local and neither depends on its energy (as long as it is high enough) nor on $n$. Our non-asymptotic analysis bridges the gap between the asymptotic expansions of [18] and [45] and known non-asymptotic bounds. Besides, we recover that the respective positions estimation errors of two high-energy change-points behave like nearly independent variables [45, 62].
In turn, this allows us to establish tight risk optimality results with respect to both the Hausdorff (4) and Wasserstein (5) distances. Finally, we note that this global to local transition phenomenon also occurs in the presence of multiple low-energy change-points.

**Penalized least-squares estimation with a multiscale penalty.** We introduce two multiple change-points procedures achieving all these optimality properties. The first one is a penalized least-squares type estimator with a multiscale penalty that promote equi-spaced change-points positions. As the corresponding penalty is additive, this estimator is easily computed by (pruned) dynamic programming [42]. In contrast to the BIC-type penalty studied recently in [59], this allows us to recover the optimal logarithmic terms as well as to handle settings where low-energy change-points are present.

**Optimal post-processing procedure based on aggregation of CUSUM tests.** As an alternative to the penalized least-squares estimator, we promote a two-step method based on the aggregation of many CUSUM tests. This method can either serve as a self-standing procedure or as a post-processing procedure to improve the detection and localization properties of a preliminary estimator. It is shown to satisfy the same optimality property as the previous multiscale procedure, whereas its computational complexity can be taken as low as $n \log(n)$ operations.

From a technical perspective, our main results are based on a novel simultaneous control of all CUSUM statistic $C(Y;t)$ in Lemma 9 that can be of independent interest. Despite the fact that we introduce as least minimax formalism as possible, our viewpoint and arguments heavily borrow from the literature on minimax testing separation rates [8, 41].

## 1.6 Notation and organization of the paper

In the sequel, we use bold letters for vectors (e.g. $\theta, \mu, Y, \tau, ...$), whereas $\|\cdot\|$ stands for the Euclidean norm. For any finite set $S$, we write $|S|$ for its cardinality. As usual, we denote by $\Phi$ the probability distribution function of a standard univariate normal distribution. Besides, $\bar{\Phi}$ stands for the corresponding tail distribution function.

In the sequence, $c, c', c_1$ stand for positive numerical constant whose value may change from line to line. Given some quantity $L$, we write $c_L$ for a positive function that only depends on $L$. We write $u \lesssim v$ (resp. $u \gtrsim v$) when there exists a numerical constant $c > 0$ such that $u \le cv$ (resp. $u \ge cv$). The notation $u \asymp v$ means that both $u \lesssim v$ and $u \gtrsim v$. Given $x$ in $\mathbb{R}$, we write $x_+ = \max(x, 0)$ for the positive part of $x$, and $\lfloor x \rfloor$ (resp. $\lceil x \rceil$) for the largest (resp. smallest) integer smaller than (resp. larger than) or equal to $x$. Given two real numbers $x$ and $y$, $x \vee y$ (resp. $x \wedge y$) denotes the maximum (resp. minimum) value between $x$ and $y$. When it is clearer, we sometimes use $\max(x, y)$ and $\min(x, y)$.

Given a vector $\theta$, we write $\mathbb{P}_{\theta}$ for the distribution of $Y$.

Section 2 is dedicated to testing and estimation problems when $\theta$ contains at most one single change-point. Turning to the multiple change-points problem, we establish impossibility results in Section 3, which lead us to defining desiderata for a suitable change-point procedure. In Section 4, we establish that penalized least-squares change-point procedures with a multiscale penalty achieve the desired specifications, whereas we prove similar results for a post-processing procedure based on the CUSUM statistic in Section 5. Some extensions and open problems are discussed in Section 6. The proofs are postponed to the end of the manuscript.
## 2 Single change-point analysis

This section deals with the case where the mean vector $\theta$ contains at most one change-point, that is when $\theta$ belongs to $\Theta_0 \cup \Theta_1$. The corresponding model (1) has often been called the At Most One Change (AMOC) model in the change-point literature (see e.g. [18]). To alleviate the notation, when $\theta$ belongs to $\Theta_1$, we simply write $\tau^*$ for $\tau_1^*$ and $\Delta$ for $\Delta_1 = \mu_2 - \mu_1$ in this section and the corresponding proofs. Recall (see (6)) that the energy $\mathbf{E}_1(\theta)$ of the change-point is defined by

$$ \mathbf{E}_1(\theta) = |\Delta| \sqrt{\frac{(\tau^* - 1)(n + 1 - \tau^*)}{n}} . $$

As explained in the introduction, the change-point detection problem when $\theta$ belongs to $\Theta_0 \cup \Theta_1$ is formalized as the problem of testing the null hypothesis $(H_0) \{\theta \in \Theta_0\}$ versus the alternative $(H1) \{\theta \in \Theta_1\}$, while the change-point localization problem is treated as a problem of estimation of $\tau^*$ when $\theta$ is assumed to belong to $\Theta_1$.

We first state impossibility results in form of minimax lower bounds and then show that matching upper bounds can be obtained from test statistics and estimators based on penalized least-squares criteria. More precisely, we derive tight lower and upper bounds for the detection rate with the tight constants. Finally, we built optimal confidence intervals for $\tau^*$.

### 2.1 Impossibility results for the detection and localization problems

The impossibility results are established in the specific setting where the noise is Gaussian. Hence, we assume throughout this subsection that $\epsilon \sim N(0, I_n)$. This assumption is henceforth referred to as $(A_G)$.

#### 2.1.1 Minimax lower bound for the detection problem

Considering the problem of testing $(H_0) \{\theta \in \Theta_0\}$ versus $(H1) \{\theta \in \Theta_1\}$, we want to assess the minimal energy $\mathbf{E}_1(\theta)$ required so that a test is able to reject the null with high probability. We start with a simple and known observation, see e.g. [22]. Fix an integer $\tau$ in $\{2, \dots, n\}$ and a real number $\delta \neq 0$, then $\Theta_1$ contains

$$ \Theta_1[\tau, \delta] = \{\theta \in \Theta_1 : \tau^* = \tau, \Delta = \delta\} . $$

Testing $(H_0)$ versus the alternative $(H_{1,\tau,\delta}) \{\theta \in \Theta_1[\tau, \delta]\}$ is arguably simpler than testing $(H_0)$ versus $(H_1)$ and the minimal energy requirement for rejecting with high probability is therefore smaller. The level-$\alpha$ Likelihood Ratio Test (LRT) for this simple (but unrealistic) testing problem rejects $(H_0)$ in favor of the alternative $(H_{1,\tau,\delta})$ when the CUSUM statistic $\mathbf{C}(\mathbf{Y}; (1, \tau, n + 1))$ with

$$ \mathbf{C}(\mathbf{Y}, (1, \tau, n + 1)) = \left( \frac{\sum_{i=\tau}^{n} Y_i}{n + 1 - \tau} - \frac{\sum_{i=1}^{\tau-1} Y_i}{\tau - 1} \right) \left( \frac{1}{\tau - 1} + \frac{1}{n + 1 - \tau} \right)^{-1/2}, $$

has an absolute value larger than a critical value depending on $\alpha$. Since under the null hypothesis $(H_0)$, $\mathbf{C}(\mathbf{Y}, (1, \tau, n + 1))$ follows a standard normal distribution, this critical value can be taken equal to $t_\alpha = \Phi^{-1}(\alpha/2)$. Besides, since under the alternative $(H_{1,\tau,\delta})$, $\mathbf{C}(\mathbf{Y}, (1, \tau, n + 1))$ has a $N(b_{n,\tau}, 1)$ distribution with a bias $b_{n,\tau,\delta}$ such that $|b_{n,\tau,\delta}| = \mathbf{E}_1(\theta)$, the type II error probability of the LRT equals $\Phi(|b_{n,\tau,\delta}| - t_\alpha) + \Phi(|b_{n,\tau,\delta}| + t_\alpha)$. This probability is small only if $\mathbf{E}_1(\theta)$ is large enough (compared to the critical value $t_\alpha$). From the fundamental Neyman-Pearson Lemma, it is the smallest possible type II error probability for any $\alpha$-level test. As a consequence, noticing that
when $\alpha$ is small, $\bar{\Phi}^{-1}(\alpha)$ is of the order of $\sqrt{2\log(1/\alpha)}$, a necessary condition for a change-point to be reliably detected by a level-$\alpha$ test is that its energy is large compared to $\sqrt{2\log(1/\alpha)}$.

In a more realistic setting where the position and the height of the change-point are unknown to the statistician, that is when considering the initial problem of testing ($H_0$) versus ($H_1$), a slightly higher energy is necessary for a change-point to be reliably detected, as formalized in the next proposition.

**Proposition 1.** Assume that $\epsilon$ in (1) satisfies ($A_G$). There exist positive numerical constants $c$ and $n_0$ such that for all $\kappa$ in $(0, 2/3)$, for all $n \ge n_0$, and for any test $\mathcal{T}$ of ($H_0$) versus ($H_1$), one has

$$ \sup_{\theta \in \Theta_0} \mathbb{P}_{\theta}[\mathcal{T} = 1] + \sup_{\theta \in \Theta_1, \mathbf{E}_1(\theta) \ge \sqrt{2(1-\kappa)(1-n^{-1/2})\log\log(n)}} \mathbb{P}_{\theta}[\mathcal{T} = 0] \ge 1 - c(\log(n))^{-\frac{\kappa^2}{8(1-\kappa)}}. \quad (10) $$

The lower bound (10) implies that the sum of the type I and II error probabilities for vectors $\theta$ with $\mathbf{E}_1(\theta) \ge \sqrt{2(1-\kappa)(1-n^{-1/2})\log\log(n)}$ is close to one. This means that no test performs better than random guess. Let us interpret this proposition in an asymptotic setting. Taking e.g. $\kappa = \log^{-1/3}(n)$, we deduce from (10) that any level-$\alpha$ test $\mathcal{T}$ of $\{\theta \in \Theta_0\}$ versus $\{\theta \in \Theta_1\}$ is not able to detect a change-point with energy $\sqrt{2(1-o(1))}\log\log(n)$ with probability uniformly higher than $1 - \alpha - o(1)$. Adopting the separation rate terminology of the minimax testing literature, this enforces that the energy minimax separation rate is of the order of $\sqrt{2\log\log(n)}$. We establish in the next subsection that the leading constant 2 is tight.

Gao et al. [30] have established a similar impossibility result in an asymptotic framework but with a suboptimal leading constant $c < \sqrt{2}$. In an independent work, Han et al. [48] have recently considered the counterpart of the single change-point detection problem for multivariate time series $\mathbf{Y}$ with values in $\mathbb{R}^p$. Letting both $p$ and $n$ go to infinity, they provide a sharp characterization of the minimal energy for change-point detection.

Closely examining the proof of Proposition 1, we see that the result of (10) is still valid even if we restrict our attention to change-point positions $\tau^*$ that are smaller than $\sqrt{n}$. Intuitively, this $\sqrt{2\log\log(n)}$ price rather arises because there are $\log(n)$ possible order of magnitudes for $\tau^*$. We come back to this point below when we build an optimal test.

### 2.1.2 Minimax lower bound for the localization problem

Let us now focus on a minimax lower bound for the localization problem, viewed as a problem of estimation of the true change-point position $\tau^*$ of $\theta$, once it is assumed to belong to $\Theta_1$. The arguments provided below are standard and can be found e.g. in [60]. They are repeated here for the sake of completeness and because a slightly tighter version than [60] is required to handle the multiple change-points case.

Throughout this subsection, we use the notation $\theta(\tau^*, \mu)$ to stress the dependency of $\theta$ on these two quantities.

**Lemma 1.** Assume that $\epsilon$ in (1) satisfies ($A_G$). Let $\mu = (\mu_1, \mu_2)$ denote a couple of real numbers such that $\mu_1 \ne \mu_2$, and $\Delta = \mu_2 - \mu_1$. There exist positive constants $c$ and $c'$ such that, for $n > 4\Delta^{-2}$ and for any $x$ in $[1/2, n/2 - 1 - 2\Delta^{-2})$,

$$ \inf_{\hat{\tau}} \sup_{\tau^* \in \{2, \dots, n\}} \mathbb{P}_{\theta(\tau^*, \mu)} (|\hat{\tau} - \tau^*| \ge 2\Delta^{-2} + x) \ge c e^{-c' x \Delta^2}, $$

where the infimum is taken over all possible estimators $\hat{\tau}$ of $\tau^*$.
The probability $\mathbb{P}_{\theta(\tau^*,\mu)}(|\hat{\tau} - \tau^*| \ge 4\Delta^{-2} + x)$ is therefore at best exponential in $x$ with rate $\Delta^2$, which in particular leads to the following lower bound for the minimax risk:

$$ \inf_{\hat{\tau}} \sup_{\tau^* \in \{2, \dots, n\}} \mathbb{E}_{\theta(\tau^*, \mu)} [|\hat{\tau} - \tau^*|] \ge \frac{c}{\Delta^2}, $$

where $\mathbb{E}_{\theta(\tau^*,\mu)}$ denotes the expectation with respect to the probability distribution $\mathbb{P}_{\theta(\tau^*,\mu)}$. As a consequence, no estimator can estimate $\tau^*$ at a rate smaller than $1/\Delta^2$ when the mean values vector $\mu = (\mu_1, \mu_2)$ is fixed, with difference $\Delta$.

## 2.2 Optimal detection and localization by penalized least-squares

In this section, we construct a change-point detection procedure and a change-point estimator both based on the classical penalized least-squares minimization approach. We do not restrict the model to the Gaussian assumption ($\mathcal{A}_G$) anymore, and we therefore consider an observed random vector $\mathbf{Y}$ such that (1) holds with $\theta$ in $\Theta_0 \cup \Theta_1$, whose probability distribution is still denoted by $\mathbb{P}_\theta$.

Let $L > 0$ and define for any $\tau$ in $\{2, \dots, n\}$, the following penalized least-squares criterion

$$ \mathrm{Cr}_1(\mathbf{Y}, \tau) := \|\mathbf{Y} - \mathbf{\Pi}_\tau \mathbf{Y}\|^2 + L \mathrm{pen}_1(\tau), \quad (11) $$

where $\mathbf{\Pi}_\tau$ denotes the orthogonal projection onto the linear subspace of $\Theta_0 \cup \Theta_1$, composed of vectors $\theta$ in $\mathbb{R}^n$ with a single change-point $\tau$. The penalty term $\mathrm{pen}_1(\tau)$, chosen as

$$ \mathrm{pen}_1(\tau) = 2 \log \log \left( e \max \left\{ \left( \tau \wedge \frac{n}{\tau} \right), \left( (n+1-\tau) \wedge \frac{n}{n+1-\tau} \right) \right\} \right), \quad (12) $$

is of multiscale type. It is worth noticing that $\mathrm{pen}_1(\tau)$ is bounded from above by $2 \log \log(en) = 2 \log \log(n) + o_n(1)$ which roughly corresponds to the squared lower bound for the minimax detection rate obtained in Section 2.1.1. Nevertheless, this upper bound is sometimes pessimistic. In particular, for $\tau \asymp 1$, $n - \tau \asymp 1$, or $\tau \asymp n$, $\mathrm{pen}_1(\tau)$ is of the order of a constant.

### 2.2.1 Detection

Let us come back to the problem of detecting the existence of a change-point, that is of testing $(H_0) \{\theta \in \Theta_0\}$ versus $(H_1) \{\theta \in \Theta_1\}$. Let the penalty parameter $L$ be in $(1, 2]$ and consider the test statistic:

$$ T(\mathbf{Y}) = \min_{\tau \in \{2, \dots, n\}} \left\{ -\|(\mathbf{\Pi}_\tau - \mathbf{\Pi}_0)\mathbf{Y}\|^2 + L^2 \mathrm{pen}_1(\tau) \right\} = \min_{\tau \in \{2, \dots, n\}} \mathrm{Cr}_1(\mathbf{Y}, \tau) - \|\mathbf{Y}\|^2 + \|\mathbf{\Pi}_0 \mathbf{Y}\|^2 . \quad (13) $$

For $\alpha$ in $(0, 1)$, we can now introduce the test $\mathcal{T}_\alpha$ defined by

$$ \mathcal{T}_\alpha = \mathbf{1}_{T(\mathbf{Y}) \le -L^2(C_\alpha + C_L)}, \quad \text{with} \quad C_\alpha = 6 \log \left( \frac{12}{\alpha} \right) \quad \text{and} \quad C_L = \frac{2}{L} \log \left( \frac{L}{L-1} \right) - 2 \log \log(L). \quad (14) $$

The test $\mathcal{T}_\alpha$ can be interpreted as the aggregation of a collection of tests of $\{\theta \in \Theta_0\}$ versus $\{\theta \in \Theta_1 \text{ with } \tau^* = \tau\}$ over $\tau = 2, \dots, n$. As for the estimation procedure introduced above, the threshold $-L^2\mathrm{pen}_1(\tau) - L^2(C_\alpha + C_L)$ depends on $\tau$, thereby giving a multiscale taste to the procedure. One deduces from simple linear algebra that $\|(\mathbf{\Pi}_\tau - \mathbf{\Pi}_0)\mathbf{Y}\|^2 = \mathbf{C}^2(\mathbf{Y}; (1, \tau, n+1))$. Hence, $\mathcal{T}_\alpha$ interprets as a max penalized CUSUM statistic, with position-dependent penalties $\mathrm{pen}_1(\tau)$. This position-dependent penalization approach differs from the usual max (non-penalized) CUSUM testing procedure in the literature [18].
**Proposition 2.** For any $\alpha$ in $(0, 1)$, the test $\mathcal{T}_\alpha$ of $\{\theta \in \Theta_0\}$ versus $\{\theta \in \Theta_1\}$ defined by (13) and (14) with $L$ in (1, 2], is of level $\alpha$. Moreover, for any $\beta$ in $(0, 1)$, and any $\theta$ in $\Theta_1$ such that

$$ \mathbf{E}_1^2(\theta) \ge L^3 \mathrm{pen}_1(\tau^*) + \frac{2L}{L+1} \log\left(\frac{2}{\beta}\right) + L^3(C_\alpha + C_L), \quad (15) $$

$\mathcal{T}_\alpha$ has type II error probability smaller than $\beta$.

Choosing $L$ close to one in Condition (15) and letting $n$ go to infinity entail that a change-point can be detected with high probability if its energy $\mathbf{E}_1(\theta)$ is higher than $(1 + o(1))\sqrt{2 \log \log(n)}$. This matches the impossibility result of Proposition 1 and means that $\mathcal{T}_\alpha$ is minimax optimal. In the minimax separation rate formalism, Proposition 1 and Proposition 2 together imply that the energy minimax separation rate is equivalent to $\sqrt{2 \log \log(n)}$. In the fact, the same rate $\sqrt{2 \log \log(n)}$ was already obtained by [22, 48] using the max CUSUM statistic, which is equivalent to setting $\mathrm{pen}_1(\tau)$ to 0 in our test. However, Proposition 2 is much more optimistic than [22, 48]. Although we pay a $\sqrt{2 \log \log(n)}$ price for $\tau^* = n^\zeta$ with $\zeta$ in $(0, 1)$, which is unavoidable, the energy requirement (15) is weaker at some other positions. In particular, it is of constant order when either $\tau^* \asymp n$ or $\tau^* \asymp 1$. In other words, for most change-point positions, the requirement $\mathbf{E}_1(\theta) > \sqrt{2 \log \log(n)}$ can be mitigated. This phenomenon is due to careful choice $\mathrm{pen}_1(\tau)$ of the CUSUM statistic in the test $\mathcal{T}_\alpha$. Regarding considerations on the LRT of $(H_0)$ versus $(H_{1, \tau, \delta})$ in Section 2.1.1, the requirement that $\mathbf{E}_1(\theta)$ is large compared to $\sqrt{\log(1/\alpha)}$ (involved in $C_\alpha$) is also unavoidable.

### 2.2.2 Localization

When $\theta$ is assumed to belong to $\Theta_1$ and the energy $\mathbf{E}_1(\theta)$ is large enough, we have proved above that the change-point $\tau^*$ can be reliably detected, so that one can aim at localizing $\tau^*$. Consider the estimator $\hat{\tau}$ minimizing among all $\tau$ in $\{2, \dots, n\}$ the penalized least-squares criterion $\mathrm{Cr}_1(\mathbf{Y}, \tau)$ introduced in (11) with the multiscale penalty (12).

**Proposition 3.** Fix the tuning parameter $L$ in (1, 2] and consider the minimizer $\hat{\tau}$ of $\mathrm{Cr}_1(\mathbf{Y}, \tau)$. There exist positive constants $c$, $c_L$, and $c'_L$ such that the following holds for all $n \ge c'_L$. If

$$ \mathbf{E}_1^2(\theta) > L^2 \mathrm{pen}_1(\tau^*) + c_L, \quad (16) $$

then, for any $x$ in $(0, (\mathbf{E}_1^2(\theta) - L^2 \mathrm{pen}_1(\tau^*) - c_L)/c_L)$, with probability larger than $1 - 32e^{-x}$,

$$ |\hat{\tau} - \tau^*| \le c \frac{1 \vee x}{\Delta^2} \quad \text{and} \quad \frac{(\hat{\tau} - 1)(n + 1 - \tau^*)}{(\tau^* - 1)(n + 1 - \hat{\tau})} \in (1/2, 2). \quad (17) $$

Proposition 3 is proved in Section 7.5. Condition (16) requires that the squared energy $\mathbf{E}_1^2(\theta)$ is larger than $L^2 \mathrm{pen}_1(\tau^*)$. Choosing $L$ close to 1, we have already seen that this condition is sharp as it corresponds to the sufficient condition for the arguably simpler problem of detecting the existence of the change-point in Proposition 1. Thus, the above result entails than once a change-point is detectable, it can also be estimated by $\hat{\tau}$ with a rate of order $\Delta^{-2}$, which is optimal as discussed in Section 2.1.2. In fact, the tail distribution of the error is optimal. Indeed, Proposition 3 implies that $|\hat{\tau} - \tau^*| \lesssim \Delta^{-2} + x$ with probability higher than $1 - e^{-c'x\Delta^2}$, which is the optimal dependency in $x$ for this probability according to Lemma 1. In the specific case where the height is high ($|\Delta| \gtrsim 1$), we use that both $\hat{\tau}$ and $\tau^*$ are integers to conclude that $\hat{\tau} = \tau^*$ with probability higher than $1 - c e^{-c'\Delta^2}$, which is again optimal by Lemma 1.
## 2.3 Confidence intervals for $\tau^*$

To conclude the present single change-point analysis, we build a confidence interval $I_{\hat{\tau}}$ for $\tau^*$. Its construction can be heuristically decomposed in two steps. First, one tests the existence of a change-point. This step relies on a statistic that slightly differs from (14). The second step then depends on the conclusion of the test. If no change-point is detected, then $\tau^*$ cannot be localized and we set $I_{\hat{\tau}} := \{2, \dots, n\}$. If a change-point has been detected, we build a confidence interval $I_{\hat{\tau}}$ whose width is of order $\Delta^{-2}$ according to the error bound of Proposition 3. As the error bound depends on the unknown height $\Delta$, this step requires to estimate $\Delta$.

Fix $L$ and $\kappa$ in $(1, 2)$, and let

$$T_{IC}(\mathbf{Y}) = \inf_{\tau \in \{2, \dots, n\}} \left\{ -\| (\mathbf{\Pi}_{\tau} - \mathbf{\Pi}_{0}) \mathbf{Y} \|^2 + (1 + \kappa) L^2 \mathrm{pen}_1(\tau) \right\},$$

where $\mathrm{pen}_1$ is the multiscale penalty proposed in (12). Let $\hat{\tau}$ still denote a minimizer among all $\tau$ in $\{2, \dots, n\}$ of the criterion given by (11). This estimator $\hat{\tau}$ is then plugged into the basic empirical means to estimate $\Delta$ by

$$\hat{\Delta} = \frac{\sum_{i=\hat{\tau}}^{n} Y_i}{n + 1 - \hat{\tau}} - \frac{\sum_{i=1}^{\hat{\tau}-1} Y_i}{\hat{\tau}}. \qquad (18)$$

For some numerical constants $c$, $c_{L,\kappa}$ that are specified in the proof of Proposition 4 in Section 7.6, let

$$I_{\hat{\tau}} := \begin{cases} \left[ \hat{\tau} - \frac{c \log(e/\alpha)}{|\Delta|^2}; \hat{\tau} + \frac{c \log(e/\alpha)}{|\Delta|^2} \right] & \text{if } T_{IC}(\mathbf{Y}) < -c_{L,\kappa} \log(e/\alpha), \\ [2, n] & \text{otherwise.} \end{cases} \qquad (19)$$

**Proposition 4.** Let $I_{\hat{\tau}}$ denote the confidence interval introduced in (19). There exist constants $c$, $c_{L,\kappa}$, $c'$, and $c'_L$ such that the following holds for all $n \ge c'_L$. For any $\theta$ in $\Theta_1$ with change-point position $\tau^*$ and change-point height $\Delta$,

$$\mathbb{P}_{\theta}(\tau^* \in I_{\hat{\tau}}) \ge 1 - \alpha.$$

Besides, if

$$\mathbf{E}_1^2(\theta) \ge (1 + \kappa) L^2 \mathrm{pen}_1(\tau^*) + c_{L,\kappa} \log(e/\alpha), \qquad (20)$$

then, with probability larger than $1 - \alpha$, one has

$$|I_{\hat{\tau}}| \le c' \log(e/\alpha) \Delta^{-2}.$$

If one takes $\kappa$ and $L$ close to one in Condition (20), then Proposition 4 shows that, if the squared energy of the change-point is larger than $\mathrm{pen}_1(\tau^*)$, the width of the confidence interval is at most proportional to $\log(e/\alpha)\Delta^{-2}$ with probability larger than $(1 - \alpha)$. Conversely, Lemma 1 implies that no estimator is able to localize $\tau^*$ at the precision $c'' \log(e/\alpha)\Delta^{-2}$ with probability higher than $1 - 2\alpha$. As a consequence, no $(1 - \alpha)$-level confidence interval $\tilde{I}$ of $\tau^*$ has a width smaller than $c'' \log(e/\alpha)\Delta^{-2}$ with probability higher than $1 - \alpha$. This entails that the width of the confidence interval $I_{\hat{\tau}}$ is optimal both with respect to $\Delta$ and $\alpha$.

Finally, since $\tau^*$ is an integer, note that $I_{\hat{\tau}}$ can be reduced to the set of integers inside $I_{\hat{\tau}}$. Thus, for a high-energy change-point and $|\Delta| \gtrsim 1$ we have $I_{\hat{\tau}} = \{\tau^*\}$ with probability higher than $(1 - 2\alpha)$ as long as $\alpha \ge c e^{-c'\Delta^2}$.
# 3 Multiple change-points ($K > 1$): preliminaries and impossibility results

## 3.1 Notation and preliminaries

It has been underlined in the above section that the energy $\mathbf{E}_1(\theta)$ of a single change-point $\tau_1^*$ with height $\Delta_1 = \mu_2 - \mu_1$ in $\theta$ defined by $\mathbf{E}_1(\theta) = |\Delta_1|\sqrt{(\tau_1^* - 1)(n + 1 - \tau_1^*)/n}$ (see (6)) plays a crucial role in the analysis. Extending the single change-point analysis to the multiple change-points case necessarily poses the question of identifying the quantity which will allow to measure the difficulty for multiple change-points to be detected or localized. Most recent papers in the literature (see [7, 25, 59, 60]) extend the notion of energy using $\mathbf{E}_{\min}(\theta)$ (as in (8)). As our main purpose here is to give tighter guarantees of detection and localization, we use a more local notion of energy. Recall that $\mathcal{T}_3$ refers to the collection of triplets of integers $\mathbf{t} = (t_1, t_2, t_3)$ such that $1 \le t_1 < t_2 < t_3 \le n+1$. For $\theta$ in $\mathbb{R}^n$ and $\mathbf{t} = (t_1, t_2, t_3)$ in $\mathcal{T}_3$, define the energy

$$ \mathbf{E}(\theta, \mathbf{t}) = \left| \frac{\sum_{i=t_2}^{t_3-1} \theta_i}{t_3 - t_2} - \frac{\sum_{i=t_1}^{t_2-1} \theta_i}{t_2 - t_1} \right| \sqrt{\frac{(t_2 - t_1)(t_3 - t_2)}{t_3 - t_1}}, \quad (21) $$

which is a weighted difference of means on $[t_1, t_2)$ and on $[t_2, t_3)$. Given $\theta$ in $\Theta_K$ with change-points vector $\boldsymbol{\tau}^*$ and an integer $1 \le k \le K$, define the energy of $\theta$ at the $k$-th change-point $\mathbf{E}_k(\theta)$ by $\mathbf{E}_k(\theta) = \mathbf{E}[\theta, (\tau_{k-1}^*, \tau_k^*, \tau_{k+1}^*)]$. More simply, we refer to this quantity as the energy of the $k$-th change-point. This extends the definition of $\mathbf{E}_1(\theta)$ when $K = 1$. Note that

$$ \mathbf{E}_k(\theta) = |\Delta_k| \sqrt{\frac{(\tau_k^* - \tau_{k-1}^*)(\tau_{k+1}^* - \tau_k^*)}{\tau_{k+1}^* - \tau_{k-1}^*}}, $$

which is of order $\Delta_k \sqrt{\ell_k}$ (in fact $|\Delta_k| \sqrt{\ell_k/2} \le \mathbf{E}_k(\theta) \le |\Delta_k| \sqrt{\ell_k}$), where $\Delta_k$ denotes the height of the change-point and $\ell_k := (\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)$ is the smallest length of the segments adjacent to the change-point, more simply named the $k$-th change-point length.

Intuitively, one cannot expect to properly localize a change-point if it cannot at least be reliably detected. From the previous section (see in particular Propositions 1 and 2), one knows that only change-points whose energy is high enough are to be detected. This is why we introduce the following definition. Given $\kappa > 1$ and $q > 0$, we say that $\tau_k^*$ is a $(\kappa, q)$-high-energy change-point if

$$ \mathbf{E}_k(\theta) > \kappa \sqrt{2 \log \left( \frac{n(\tau_{k+1}^* - \tau_{k-1}^*)}{(\tau_{k+1}^* - \tau_k^*)(\tau_k^* - \tau_{k-1}^*)} \right) + q}. \quad (22) $$

In other words, the energy $\mathbf{E}_k(\theta)$ is said to be high if $\Delta_k^2 \ell_k$ is large compared to $\log(n/\ell_k) + q$. Note that if the change-point length $\ell_k$ is smaller than $n^\zeta$ with $\zeta$ in $[0, 1)$, the logarithmic term is of the order of $\log(n)$, whereas if this length is proportional to $n$, the logarithmic term is of the order of a constant.

## 3.2 Impossibility results

As in Section 2.1, we assume throughout this section that the noise in the model (1) is Gaussian, that is assumption $(A_G)$ is fulfilled. Besides, we sometimes use the $\theta(\boldsymbol{\tau}^*, \boldsymbol{\mu})$ instead of $\theta$ to stress the dependency of $\theta$ on the parameters $\boldsymbol{\tau}^*$ and $\boldsymbol{\mu}$.
### 3.2.1 Low-energy change-points cannot be detected

The targeted property for detecting a specific change-point among multiple change-points is formalized in Section 3.3 below. In this subsection, we explain why this strong detection property is not achievable when the change-point has not a high-energy. More specifically, we consider the weakened possible notion of change-point detection, that is we test whether $(H_0) \{\theta \in \Theta_0\}$ versus $(H_1) \{\theta \notin \Theta_0\}$ and we establish that, for some alternatives, only vectors $\theta$ with at least a high-energy change-point can be reliably detected. In particular, we justify the two different quantities $q$ and $\log(n(\tau_{k+1}^* - \tau_{k-1}^*)/((\tau_{k+1}^* - \tau_k^*)(\tau_k^* - \tau_{k-1}^*))$ in the definition (22) of high-energy change-points. Part of the results belong to the statistical folklore and asymptotic versions have already appeared for instance in [16]. Still, we state and prove here non-asymptotic counterparts to unify our presentation and for the sake of completeness.

We showed in Section 2.1.1 that, when testing $\{\theta \in \Theta_0\}$ versus $\{\theta \in \Theta_1\}$, even in the most simple situation where the position of the tentative change-point is known, it can only be reliably detected if its energy is large enough. More precisely, we established that any level-$\alpha$ test is only able to reject the null hypothesis with probability higher than $1 - \beta$, when the energy of the change-point is at least of the order $\sqrt{\log(1/\min(\alpha, \beta))}$. Coming back to the definition (22) of high-energy change-points, we deduce that a single change-point $\tau_1^*$ whose length $\ell_1$ is proportional to $n$, can only be detected with probability higher than $1 - c e^{-c'q}$ (for some $q > 0$) if it has $(1, q)$-high energy.

Now, we turn to the logarithmic term in the definition (22) of high-energy change-points. This quantity only arises when there are at least two change-points. Following a long line of literature [1, 2, 16], we consider the problem of segment detection. Given a positive integer $r$ (less than $\lfloor n/4 \rfloor$) and $\delta > 0$, we consider the collection $\Theta[r, \delta] \subset \Theta_2$ defined by

$$ \Theta[r, \delta] = \{ \theta \in \mathbb{R}^n : \exists \tau \in \{\lfloor n/4 \rfloor + 1, \dots, \lfloor 3n/4 \rfloor - r\}, \text{ such that } \theta_i = \delta \mathbf{1}_{i \in \{\tau, \dots, \tau + r - 1\}} \} . \quad (23) $$

A vector $\theta$ in $\Theta[r, \delta]$ equals $\delta$ on the segment $[\tau, \tau + r - 1]$ and is null outside this segment. Note that this segment belongs to $[n/4; 3n/4]$ and is therefore away from the endpoints. The problem of (single) segment detection is that of testing $\{\theta = 0\}$ versus $\{\theta \in \Theta[r, \delta]\}$. Typical asymptotic results<fnref n="2" /> (see e.g. Proposition 1 in [1]) consider sequences $r_n$ and $\delta_n$ and state that, for $r_n/n \to 0$, then the sum of the type I and type II error probabilities of any test converges to one when $\delta_n \sqrt{r_n} - \sqrt{2\log(n/r_n)}$ goes to $-\infty$. This entails that no test performs asymptotically better than pure random guess. For the sake of completeness, we provide a non-asymptotic counterpart.

**Proposition 5.** Assume that $\epsilon$ in (1) satisfies $(A_G)$. There exist positive numerical constants $c$, $c'$ and $n_0$ such that for all $n \ge n_0$, any $1 \le r \le \lfloor n/4 \rfloor$, and any $\xi$ in $(0, 1)$, the following holds. If $\delta \sqrt{r} \le \sqrt{2(1 - \xi)\log(n/(2r))}$, then any test $\mathcal{T}$ of $\{\theta = 0\}$ versus $\{\theta \in \Theta[\delta, r]\}$ satisfies

$$ \mathbb{P}_0[\mathcal{T} = 1] + \sup_{\theta \in \Theta[\delta, r]} \mathbb{P}_{\theta}[\mathcal{T} = 0] \ge 1 - c \left(\frac{r}{n}\right)^{c'\xi^2} . \quad (24) $$

We recover that $\delta\sqrt{r}$ needs to be at least of the order of $\sqrt{2\log(n/r)}$ so that the segment is reliably detected. Let us now interpret this impossibility result in terms of energy and high-energy change-points. Any $\theta$ in $\Theta[r, \delta]$ contains two change-points such that, for $k = 1, 2$, $(\tau_{k+1}^* - \tau_k^*)(\tau_k^* - \tau_{k-1}^*)/(\tau_{k+1}^* - \tau_{k-1}^*)$ belongs to $[r(1 - r/([n/4] + r)), r]$. As a consequence, their respective energies $\mathbf{E}_1(\theta)$ and $\mathbf{E}_2(\theta)$ belong to $[\delta\sqrt{r(1 - r/([n/4] + r))}, \delta\sqrt{r}]$. Rephrasing Proposition (24) we deduce

<footnote n="2">²In the literature, the segments are usually not restricted to be away from the endpoints, but one can readily adapt the minimax lower bounds to our setting.</footnote>
that when, for some $\xi'$ in $(0, 1)$ and some $r < c_\xi n$, the energy of both change-points is not $(\xi', 1)$-high then it is impossible to reliably test whether $\{\theta \in \Theta_0\}$ versus $\{\theta \in \Theta_2\}$.

Consider some $q > 1$. In summary, even in very simple settings such as $\theta$ in $\Theta_1$ or $\theta$ in $\Theta_2$, the energy a change-point has to be at least $(1, q)$-high, so that a test of $\{\theta \in \Theta_0\}$ versus $\{\theta \in \Theta_1 \cup \Theta_2\}$ of level $c e^{-c'q}$ detects a change-point with probability at least $1 - c e^{-c'q}$.

### 3.2.2 Localization error

We now provide lower bounds for the problem of localizing a high-energy change-point $\tau_k^*$. To derive the optimal rate, we consider, as in Section 2.1.2, a favorable situation where almost all parameters are known. Fix $\mu = (\mu_1, \dots, \mu_{K+1})$ with $\Delta_k = \mu_{k+1} - \mu_k \neq 0$ for all $k$ in $\{1, \dots, K\}$. Given a vector $\mathbf{t} = (t_1, \dots, t_{K+1})$ of integers such that $1 = t_1 < t_2 < \dots < t_{k+1} = n$, consider the partition $\mathcal{I}_{\mathbf{t}} = (I_k)_{k \in \{1, \dots, K\}}$ of $\{2, \dots, n\}$, where, for all $k$, $I_k = \{t_k + 1, \dots, t_{k+1}\}$. Denote by

$$ \Theta_K[\mathcal{I}_{\mathbf{t}}, \mu] = \{\theta \in \Theta_K, \theta_i = \mu_k \quad \forall i \in \{\tau_{k-1}^*, \dots, \tau_k^* - 1\}, \text{ with } \tau_k^* \in I_k \quad \forall k \in \{1, \dots, K\} \} . $$

Suppose that the statistician knows that $\theta$ is in $\Theta_K[\mathcal{I}_{\mathbf{t}}, \mu]$, that is, she knows the vector $\mu$ and she knows moreover that, for each $k$ in $\{1, \dots, K\}$, $\tau_k^*$ belongs to $I_k$. Then, $\mathbf{Y}_k = (Y_i)_{i \in I_k}$ is a sufficient statistic for estimating $\tau_k^*$. Since the $\mathbf{Y}_k$'s are independent, all $K$ estimation problems of $\tau_k^*$ can be considered independently. Arguing as in Section 2.1.2, we derive the following result.

**Proposition 6.** Assume that $n \ge 3$ and $\epsilon$ in (1) satisfies $(A_G)$. There exist universal constants $c_1, c_5$ such that the following holds. Fix $K$ in $\{2, \dots, n-1\}$, a vector $\mu = (\mu_1, \dots, \mu_{K+1})$ in $\mathbb{R}^{K+1}$ with $\Delta_k = \mu_{k+1} - \mu_k \neq 0$ for all $k$ in $\{1, \dots, K\}$, and a partition $\mathcal{I}_{\mathbf{t}} = (I_k)_{k \in \{1, \dots, K\}}$ of $\{2, \dots, n\}$ as described above and such that $|I_k| > 4\Delta_k^{-2} + 2$ for any $k = 1, \dots, K$. For any $k$ in $\{1, \dots, K\}$, for any estimator $\hat{\tau}_k$ of $\tau_k^*$ and any $x$ in $[1/2, |I_k|/2 - 1 - 2\Delta_k^{-2})$, one has

$$ \sup_{\theta \in \Theta_K[\mathcal{I}, \mu]} \mathbb{P}_{\theta} (|\hat{\tau}_k - \tau_k^*| > 2\Delta_k^{-2} + x) \ge c_1 e^{-c_2 x \Delta_k^2}. \quad (25) $$

The $\mathbb{L}_1$-Wasserstein minimax risk over $\Theta_K[\mathcal{I}, \mu]$ is bounded from below as follows

$$ \inf_{\hat{\tau} \in \mathbb{N}^K} \sup_{\theta \in \Theta_K[\mathcal{I}, \mu]} \mathbb{E}_{\theta} [d_W(\hat{\tau}, \tau^*)] \ge c_3 \sum_{k=1}^{K} \left[ \frac{e^{-\Delta_k^2/8}}{|\Delta_k|} \mathbf{1}_{|\Delta_k| \ge 2} + \Delta_k^{-2} \mathbf{1}_{|\Delta_k| \le 2} \right] . \quad (26) $$

Assume that all $\Delta_k$ are equal to some common value $\Delta > 0$. If the partition $\mathcal{I}_{\mathbf{t}}$ further satisfies $\min_{k \in \{1, \dots, K\}} |I_k| \ge c_4 \Delta^{-2} \log K$, then the Hausdorff minimax risk over $\Theta_K[\mathcal{I}, \mu]$ satisfies

$$ \inf_{\hat{\tau} \in \mathbb{N}^K} \sup_{\theta \in \Theta_K[\mathcal{I}, \mu]} \mathbb{E}_{\theta} [d_H(\hat{\tau}, \tau^*)] \ge c_5 \left[ \frac{K e^{-\Delta^2/8}}{|\Delta|} \mathbf{1}_{|\Delta| \ge 2} \sqrt{\frac{\log(K)}{2 \log(K)}} + \frac{\log(K)}{\Delta^2} \mathbf{1}_{|\Delta| < 2} \sqrt{\frac{\log(K)}{2 \log(K)}} \right] . \quad (27) $$

The bottom line of this proposition is that at best, for any estimator $\hat{\tau} \in \mathbb{N}^K$, the errors $|\hat{\tau}_k - \tau_k^*|$ behave independently and have an exponential tail of the form (25). The first lower bound (25) for estimating a single change-point $\tau_k^*$ is a straightforward consequence of Lemma 1 and analogous results may be found e.g. in [60]. However, the lower bounds (26) and (27) for the Wasserstein and Hausdorff risk are, up to our knowledge, new.
### 3.3 Which requirements for a good change-point detection and localization procedure?

The obtained lower bounds lead us to reflect upon the properties a good change-point detection and localization estimator $\tilde{\tau}$ should satisfy, and to specify them. First, it should not overestimate the number of true change-points. Besides, one cannot hope that $\tilde{\tau}$ detects all true change-points $\tau_k^*$. In view of Proposition 5, it is more reasonable to require that $\tilde{\tau}$ detects all high-energy change-points. Finally, those high-energy change-points should be localized at the parametric rate $\Delta_k$ as explained above. More precisely, our target estimator $\tilde{\tau}$ will satisfy, over a large probability event $\mathcal{A}$ the three following properties. In the sequel, the notation $\{\tilde{\tau}\}$ is short for the set $\{\tilde{\tau}_l, l \in \{1, \dots, |\tilde{\tau}|\}\}$.

**(NoSp).** No spurious change-point is detected:

$$ \left\{ \begin{array}{l} \left| \{\tilde{\tau}\} \cap \left( \frac{\tau_{k-1}^* + \tau_k^*}{2}, \frac{\tau_k^* + \tau_{k+1}^*}{2} \right) \right| \le 1 , \text{ for all } k \text{ in } \{2, \dots, K-1\} ; \\ \left| \{\tilde{\tau}\} \cap \left[ 2, \frac{\tau_1^* + \tau_2^*}{2} \right] \right| \le 1 ; \\ \left| \{\tilde{\tau}\} \cap \left( \frac{\tau_{K-1}^* + \tau_K^*}{2}, n \right) \right| \le 1 . \end{array} \right. \qquad (28) $$

**(Detec[$\kappa$, $q$, $c$]).** High-energy change-points are detected: for all $k$ in $\{1, \dots, K\}$, if $\tau_k^*$ is a ($\kappa$, $q$)-high-energy change-point then

$$ d_{H,1}(\tilde{\tau}, \tau_k^*) \le \min \left\{ \frac{\tau_{k+1}^* - \tau_k^*}{2}, \frac{\tau_k^* - \tau_{k-1}^*}{2}, c \frac{\log(1 \vee n \Delta_k^2) + q}{\Delta_k^2} \right\} . \qquad (29) $$

**(Loc[$\kappa$, $q$, $c$, $c'$]).** High-energy change-points are localized at the optimal rate: any ($\kappa$, $q$)-high-energy change-point $\tau_k^*$ satisfies

$$ \mathbb{P} \left( d_{H,1}(\tilde{\tau}, \tau_k^*) \mathbf{1}_{\mathcal{A}} \ge c x \Delta_k^{-2} \right) \le c' e^{-x}, \quad \forall x \ge 1 . \qquad (30) $$

Property **(NoSp)** is slightly stronger than requiring that $|\tilde{\tau}| \le K$, since it requires that, in each segment $((\tau_{k-1}^* + \tau_k^*)/2, (\tau_k^* + \tau_{k+1}^*)/2]$, the number of change-points is not overestimated. Property **(Detec[$\kappa$, $q$, $c$]** specifies that, for any high-energy change-point $\tau_k^*$, there exists at least one predicted change-point $\tilde{\tau}_l$ which is closer to $\tau_k^*$ than any other true change-point. The last term $d_k = c\Delta_k^{-2}[\log(1 \vee n\Delta_k^2) + q]$ in the upper bound (29) provides a quantitative bound for $d_{H,1}(\tilde{\tau}, \tau_k^*)$. Hence, **(Detec[$\kappa$, $q$, $c$]** provides an uniform control on the localization error of each high-energy change-point. In fact, it suffices to prove **(Detec[$\kappa$, $q$, $+\infty$]** to ensure **(Detec[$\kappa$, $q$, $c$]** for some $c$ large enough. Indeed, inserting in $\tau^*$ two change-points $\tau_- = \tau_k^* - \lceil 2d_k \rceil$ and $\tau_+ = \tau_k^* + \lceil 2d_k \rceil$ with a null change-point height does not change the distribution. If $c$ is chosen large enough in (29), then the energy of $\tau_k^*$ relative to the new change-point vector remains ($\kappa$, $q$)-high. As a consequence, **(Detec[$\kappa$, $q$, $+\infty$]** entails that, under the event $\mathcal{A}$, $d_{H,1}(\tilde{\tau}, \tau_k^*) \le d_k$.

As for Property **(Loc[$\kappa$, $q$, $c$, $c'$]**, it enforces that any ($\kappa$, $q$)-high-energy jump $\tau_k^*$ is estimated at the optimal rate (as given by Proposition 6) in the event $\mathcal{A}$. Since $d_{H,1}(\tilde{\tau}, \tau_k^*)$ is a non-negative integer, this property implies that, for $\Delta_k$ large enough, one has $d_{H,1}(\tilde{\tau}, \tau_k^*) = 0$ with probability higher than $1 - c' e^{-\Delta_k^2/c} - \mathbb{P}(\mathcal{A}^c)$. Let us emphasize that, in (30), the subscript $k$ is fixed inside the probability, whereas **(Detec[$\kappa$, $q$, $c$]** provides an uniform bound with respect to all high-energy jumps.

In the next two sections, we introduce and analyze change-point detection procedures bearing in mind these three specifications.
# 4 Penalized least-squares

## 4.1 Definition

Given a change-point vector $\tau$, let $\Pi_{\tau}$ denote the projector onto the space of piece-wise constant vectors on $\{\tau_i, \dots, \tau_{i+1} - 1\}$ for $i = 0, \dots, |\tau|$. Then, we consider the penalized least-squares criterion defined by

$$ \mathrm{Cr}_0(\mathbf{Y}, \tau) := \|\mathbf{Y} - \Pi_{\tau}\mathbf{Y}\|^2 + L\mathrm{pen}_0(\tau, q), \quad (31) $$

where

$$ \mathrm{pen}_0(\tau, q) = q|\tau| + 2 \sum_{i=1}^{|\tau|+1} \log \left( \frac{n}{\tau_i - \tau_{i-1}} \right), \quad (32) $$

and $L > 1, q > 0$ are tuning parameters. In the above definition, recall that we take the convention $\tau_0 = 1$ and $\tau_{|\tau|+1} = n+1$. Then, the penalized least-squares estimator $\hat{\tau}$ is defined as any minimizer of $\mathrm{Cr}_0(\mathbf{Y}, \tau)$. The dependency of $\hat{\tau}$ on the tuning parameters $L$ and $q$ is left implicit. If the noise $\epsilon$ in the model (1) satisfies the Gaussian assumption ($A_G$), $\hat{\tau}$ is simply a penalized maximum log-likelihood estimator. In the sequel, $\mathrm{pen}_0(\tau; q)$ is referred to as a multiscale penalty because its value depends on the scales of $\tau_i - \tau_{i-1}$.

**Computational complexity.** The multiscale penalty (32) is additive. The cost of a segmentation in (31) is the sum of the cost of its segments and one can apply Bellman's dynamic programming algorithm [10] to compute $\hat{\tau}$ with at most $O(n^2)$ operations. Furthermore, one may adapt pruning methods such as PELT [42] or [53] to reduce the complexity to linear in best-case scenarios.

**Penalty choice.** The multiscale penalty (32) may be contrasted with complexity based penalties in the literature. Among these complexity based penalties, one can essentially distinguish the $l_0$-penalties which are linear in the $l_0$-norm of $D\theta = (\theta_{i+1} - \theta_i)_{i \in \{1, \dots, n-1\}}$ simply equal to $|\tau|$, leading to estimators that are sometimes also referred to as Ising or Potts estimators, and which of course include the BIC penalty $\mathrm{pen}_{BIC}(\tau) = 2|\tau|\log(n)$ used in [12, 31, 45, 59, 61, 62], and the penalties $\mathrm{pen}_{MS}(\tau) = |\tau|(1 + c \log(n/|\tau|))$ of [11, 46] designed for model selection and signal estimation. The first term in our penalty (32) exactly corresponds to a $l_0$-penalty. The second term gives most weight to change-points $\tau_l$ that are the closest to one of their neighbours $\tau_{l-1}$ or $\tau_{l+1}$ at least, with a largest possible contribution of order $\log(n)$, and less weight to change-points $\tau_l$ such that $(\tau_l - \tau_{l-1}) \wedge (\tau_{l+1} - \tau_l)$ is proportional to $n$, which occurs for instance if there is a fixed number of equi-spaced change-points. Consequently, our penalty $\mathrm{pen}_0(\tau, q)$ is, up to multiplicative constants, always smaller than the BIC penalty, and favours equi-spaced change-point vectors. The general form of $\mathrm{pen}_0(\tau, q)$ is related to the definition (22) of high-energy change-points and to the target property (Detec[$\kappa, q, c$]). It is justified below, where we also explain why the previous BIC and model selection penalties lead to suboptimal performances (see Section 4.2).

**Connection with CUSUM statistics.** There are deep connections between penalized least-squares criteria such as $\mathrm{Cr}_0(\mathbf{Y}, \tau)$ and CUSUM statistics as pointed out for instance in Wang et al. [59]. Recall that, given $\mathbf{t} = (t_1, t_2, t_3)$ in $T_3$, the CUSUM statistic at $\mathbf{t}$ is defined in (3) as the empirical counterpart of the weighted difference in means on $[t_1, t_2)$ and on $[t_2, t_3)$. First recall that maximizing the CUSUM statistic $\mathbf{C}(\mathbf{Y}, \mathbf{t})$ over all $\mathbf{t}$ of the form $(1, \tau, n+1)$, with $\tau$ in $\{1, \dots, n\}$ is equivalent to computing the least-squares estimator $\arg\min_{\tau \in \{1, \dots, n\}} \|\mathbf{Y} - \Pi_{\tau}\mathbf{Y}\|^2$. More generally, local differences of the criterion $\mathrm{Cr}_0(\mathbf{Y}, \tau)$ have a natural expression in terms of the CUSUM statistic. For any integer $1 \le l \le |\tau|$, let $\tau^{(-l)}$ denote the vector $(\tau_1, \dots, \tau_{l-1}, \tau_{l+1}, \dots, \tau_{|\tau|})$ where $\tau_l$ has been removed. From Pythagorean equality, writing $\delta_{l-1} = \tau_l - \tau_{l-1}$, $\delta_l = \tau_{l+1} - \tau_l$,
$S_{l-1} = \sum_{i=\tau_{l-1}}^{\tau_l-1} Y_i$, and $S_l = \sum_{i=\tau_l}^{\tau_{l+1}-1} Y_i$, we obtain

$$
\begin{align*}
\|\mathbf{Y} - \mathbf{\Pi}_{\tau} \mathbf{Y}\|^2 - \|\mathbf{Y} - \mathbf{\Pi}_{\tau^{(-l)}} \mathbf{Y}\|^2 &= \|\mathbf{\Pi}_{\tau^{(-l)}} \mathbf{Y}\|^2 - \|\mathbf{\Pi}_{\tau} \mathbf{Y}\|^2 \\
&= (\delta_{l-1} + \delta_l) \left(\frac{S_{l-1} + S_l}{\delta_{l-1} + \delta_l}\right)^2 - \delta_{l-1} \left(\frac{S_{l-1}}{\delta_{l-1}}\right)^2 - \delta_l \left(\frac{S_l}{\delta_l}\right)^2 \\
&= -\frac{\delta_{l-1} \delta_l}{\delta_{l-1} + \delta_l} \left(\frac{S_{l-1}}{\delta_{l-1}} - \frac{S_l}{\delta_l}\right)^2 \\
&= -\mathbf{C}^2(\mathbf{Y}, (\tau_{l-1}, \tau_l, \tau_{l+1})) .
\end{align*}
$$

From the definition (31), we therefore deduce the following lemma.

**Lemma 2.** For any $\tau$ and any $l = 1, \dots, |\tau|$, we have

$$
\mathrm{Cr}_0(\mathbf{Y}, \boldsymbol{\tau}) - \mathrm{Cr}_0(\mathbf{Y}, \boldsymbol{\tau}^{(-l)}) = -\mathbf{C}^2(\mathbf{Y}, (\tau_{l-1}, \tau_l, \tau_{l+1})) + L \left[ 2 \log \left( \frac{n(\tau_{l+1} - \tau_{l-1})}{(\tau_{l+1} - \tau_l)(\tau_l - \tau_{l-1})} \right) + q \right] . \quad (33)
$$

Heuristically, the above decomposition justifies the choice (32) for the penalty $\mathrm{pen}_0(\tau, q)$. Indeed, if we assume that the noise vector $\epsilon$ in (1) is equal to zero, then $\mathbf{C}^2(\mathbf{Y}, (\tau_{l-1}, \tau_l, \tau_{l+1}))$ simplifies as $\mathbf{E}^2(\theta, (\tau_{l-1}, \tau_l, \tau_{l+1}))$) and (33) suggests that, if $\tau_l$ is a $(\sqrt{L}, q)$-high-energy change-point, it has to be included in $\hat{\tau}$.

When $\theta$ is constant on $[t_1, t_3)$, then the CUSUM statistic $\mathbf{C}(\mathbf{Y}, \mathbf{t})$ does not depend on $\theta$ and simplifies as the pure noise statistic:

$$
\mathbf{N}(\mathbf{t}) := \left[ \frac{\sum_{i=t_2}^{t_3-1} \epsilon_i}{t_3 - t_2} - \frac{\sum_{i=t_1}^{t_2-1} \epsilon_i}{t_2 - t_1} \right] \sqrt{\frac{(t_2 - t_1)(t_3 - t_2)}{t_3 - t_1}} . \quad (34)
$$

An uniform control of $\mathbf{N}(\mathbf{t})$ over $\mathbf{t}$ in $\mathcal{T}_3$ is at the heart of the analysis of $\hat{\tau}$, as explained in the next subsection.

## 4.2 Large penalty parameter $L$

In this subsection, we investigate the properties of the penalized least-squares estimator $\hat{\tau}$ when the tuning parameter $L$ is chosen large enough. Define the event $\mathcal{A}_q$ by

$$
\mathcal{A}_q = \left\{ |\mathbf{N}(\mathbf{t})| \le 2\sqrt{2\log\left(\frac{n(t_3-t_1)}{(t_3-t_2)(t_2-t_1)}\right) + q}, \quad \forall \mathbf{t} = (t_1, t_2, t_3) \in \mathcal{T}_3 \right\} . \quad (35)
$$

Lemma 9 below states that $\mathcal{A}_q$ occurs with high probability. In fact, Lemma 9 holds even if the multiplicative factor 2 in (35) is replaced by any constant larger than one. Let us discuss the order of magnitude of this bound. For a fixed $\mathbf{t}$ in $\mathcal{T}_3$, $\mathbf{N}(\mathbf{t})$ has a sub-Gaussian distribution with constant 1. Since there are at most $n^3/6$ elements in $\mathcal{T}_3$, an union bound easily leads to $\mathbb{P}(\sup_{\mathbf{t} \in \mathcal{T}_3} |\mathbf{N}(\mathbf{t})| \ge \sqrt{6 \log(n) + 2x}) \le 2e^{-x}$ for any $x > 0$. Such control are for instance used in [26] or [59]. In the event $\mathcal{A}_q$, we rely on a control of $\mathbf{N}(\mathbf{t})$ that depends on the specific scale of $\mathbf{t}$. For a small $(t_3 - t_2) \wedge (t_2 - t_1)$, the upper bound is still of the order of $\sqrt{\log(n)}$, whereas for $(t_3 - t_2) \wedge (t_2 - t_1)$ proportional to $n$, the upper bound in $\mathcal{A}_q$ behaves like a constant. Intuitively, this improved bound is related to the fact that the random variables $\mathbf{N}(\mathbf{t})$ at a large scale are highly correlated so that a peeling argument reduces from $\sqrt{\log(n)}$ to a constant. Such behaviour is reminiscent of other multiscale statistics considered in [25].

If the noise vector $\epsilon$ has a standard Gaussian distribution then, for some $\alpha$ in $(0, 1)$, one can compute by Monte-Carlo the minimal $q_{1-\alpha}$ such that $\mathbb{P}(\mathcal{A}_{q_{1-\alpha}}) \ge 1 - \alpha$.
### 4.2.1 First step analysis: global optimality

One may easily deduce from the event $A_q$ that $\hat{\tau}$ (with $L > 4$) does not overestimate too much the true number of change-points: in each segment $[\tau_k^*, \tau_{k+1}^*]$, the penalized least-squares estimator $\hat{\tau}$ contains at most two change-points. Indeed, consider any change-point vector $\tau$ that contains three such change-points $\tau_{l-1}, \tau_l, \tau_{l+1}$ in $[\tau_k^*, \tau_{k+1}^*]$ then it follows from (33) that on the event $A_q$,

$$ \mathrm{Cr}_0(\mathbf{Y}, \tau) - \mathrm{Cr}_0(\mathbf{Y}, \tau^{(-l)}) = -\mathbf{C}^2(\mathbf{Y}, (\tau_{l-1}, \tau_l, \tau_{l+1})) + L \left[ 2 \log \left( \frac{n(\tau_{l+1} - \tau_{l-1})}{(\tau_{l+1} - \tau_l)(\tau_l - \tau_{l-1})} \right) + q \right] > 0 $$

which implies that $\tau \neq \hat{\tau}$. This simple observation implies that, on $A_q$, $|\hat{\tau}| \le 2K$. Refining these arguments, we are able to establish in the proof of the next proposition that any $\tau$ with $|\tau| > K$ can be locally modified, by adding and/or removing some change-points, so that the criterion strictly decreases under $A_q$. Such arguments based on local modifications were previously used in [59], but we need to sharpen it to recover the tight logarithms.

Given any change-point vector $\tau$ and some integer $k$ such that $1 \le k \le |\tau^*| = K$, we write $\tau^{(k)}$ for the (reordered) concatenation of $\tau$ and $\tau_k^*$. For $1 \le l \le |\tau|$, we say that $\tau_l$ is a $(\kappa, q, \tau)$-high-energy change-point if

$$ \mathbf{E}(\theta, (\tau_{l-1}, \tau_l, \tau_{l+1})) > \kappa \sqrt{2 \log \left( \frac{n(\tau_{l+1} - \tau_{l-1})}{(\tau_{l+1} - \tau_l)(\tau_l - \tau_{l-1})} \right) + q} . $$

**Proposition 7.** There exist universal constants $c, c'$, $L_0$, $q_0$ and $n_0$ such that the following holds for any $L \ge L_0$, any $q > q_0$ and any $n > n_0$. For any integer $K > 0$ and $\theta$ in $\Theta_K$, there exists $\kappa_L > 0$ (only depending on $L$) and an event $A_q$ (defined in (35)) of probability higher than $1 - ce^{-c'q}$ on which the penalized least-squares estimator $\hat{\tau}$ satisfies:

(a) (NoSp) No spurious change-point is detected: for all $k = 1, \dots, K$,

$$ \left\{ \begin{array}{l} |\{\hat{\tau}\} \cap \left(\frac{\tau_{k-1}^* + \tau_k^*}{2}, \frac{\tau_k^* + \tau_{k+1}^*}{2}\right)| \le 1 \ , \text{ for all } k \text{ in } \{2, \dots, K-1\} \ ; \\ |\{\hat{\tau}\} \cap [2, \frac{\tau_1^* + \tau_2^*}{2}]| \le 1 \ ; \\ |\{\tilde{\tau}\} \cap \left(\frac{\tau_{K-1}^* + \tau_K^*}{2}, n\right)| \le 1 \ ; \end{array} \right. $$

(b) (Detec[$\kappa_L, q, \kappa_L$]) High-energy change-points are detected: for all $k$ in $\{1, \dots, K\}$ such that $\tau_k^*$ is a $(\kappa_L, q)$-high-energy change-point, we have

$$ d_{H,1}(\hat{\tau}, \tau_k^*) \le \min \left\{ \frac{\tau_{k+1}^* - \tau_k^*}{2}, \frac{\tau_k^* - \tau_{k-1}^*}{2}, \kappa_L \frac{\log(n\Delta_k^2) + q}{\Delta_k^2} \right\} ; \quad (36) $$

(c) For all $k$ in $\{1, \dots, K\}$, either $\tau_k^*$ belongs to $\hat{\tau}$ or it is not a $((\sqrt{L} + 2), q, \hat{\tau}^{(k)})$-high-energy change-point.

Increasing the value of $q$ in the penalty function $\mathrm{pen}_0(\tau, q)$ leads to a more conservative procedure which achieves (NoSp) with a higher probability guarantee, but $\tilde{\tau}$ provably detects jumps with a higher energy requirement. For a fixed but small probability $\alpha$ in $(0, 1)$, one can take $q$ of order $\log(1/\alpha)$ so that (NoSp) and (Detec[$\kappa_L, q, \kappa_L$]) hold with probability higher than $1 - \alpha$. In view of the impossibility results in Section 3.2.1, the properties (NoSp) and (Detec[$\kappa_L, q, \kappa_L$]) cannot be fulfilled with probability higher than $1 - ce^{-c'q}$. The penalized least-squares estimator $\hat{\tau}$ simultaneously achieves (NoSp) and (Detec[$\kappa_L, q, \kappa_L$]) with probability at least $1 - ce^{-c'q}$. Up
to the constants c and c', we have established in Section 3.2.1 that no change-point detection procedure is able to simultaneously achieve (NoSp) and (Detec[$\kappa_L, q, \kappa_L$]) with a probability higher than that.

This result contrasts with the previous work of [25]. In [25], the SMUCE estimator is proved to achieve a uniform bound slightly different from (36). Assuming that $E_{min}^2(\theta) = \min_{k \in \{1, ..., K\}}(\tau_{k+1}^* - \tau_k^*) \min_k \Delta_k^2$ (c.f. (8)) is large compared to $\log(n/\min_k(\tau_k^* - \tau_{k-1}^*))$, the authors establish (see their Theorem 2.8), that SMUCE detects all change-points with high probability. If all change-points have similar heights (that is all $|\Delta_k|$ are of the same order) and if all segments are of similar lengths (that is all $(\tau_{k+1}^* - \tau_k^*)$ are of the same order), then their hypothesis boils down to assuming that all change-points have a high-energy. Hence, the main novelties of our result in Proposition 7 in comparison with [25] are that: (i) it better handles non evenly spaced jumps and (ii) more importantly, it does not require that all jumps have a high energy.

Other results for Wild Binary Segmentation estimators in [7, 26, 59]) or $l_0$-penalized least-squares estimators in [59] assume that $E_{min}^2(\theta)$ is higher than $\log(n)$ which, for well-spaced change-points (and a constant $K$), is suboptimal by a $\log(n)$ factor. Besides, all those works also require that all jumps have a high-energy.

### 4.2.2 Second step analysis: local optimality

**Proposition 8.** Let $L_0, q_0$ and $A_q$ be defined as in Proposition 7. If we fix $L \ge L_0$ and $q > q_0$, there exist $\kappa_L > 0$ and $c, c' > 0$ such that the following holds. For any $\theta$ in $\mathbb{R}^n$ and any $(\kappa_L, q)$-high-energy change-point $\tau_k^*$, the penalized least-squares estimator $\hat{\tau}$ satisfies

$$ \mathbb{P} \left( d_{H,1}(\hat{\tau}, \tau_k^*) \mathbf{1}_{A_q} \ge c x \Delta_k^{-2} \right) \le c' e^{-x} \quad \forall x \ge 1. $$

As explained above, Proposition 8 improves the results of [25] and [45] in the sense that it designs nonasymptotic guarantees for a specific change-point to be localized in an optimal way. More precisely, it shows the considered penalized least-squares estimator $\hat{\tau}$ allows each change-point to be estimated at the optimal parametric rate $\Delta_k^{-2}$, as soon as it is has high-energy. Moreover, it implies in particular that, when $|\Delta_k|$ is larger than one, we have $\hat{\tau}_l = \tau_k^*$, for some $l$, on the intersection of $A_q$ and an event of probability higher than $1 - c' e^{-\Delta_k^2/c}$. Up to our knowledge, this result, combined with Proposition 6, provides the first matching upper and lower bounds for high-energy change-points localization.

**From a global to a local problem.** In view of Properties (NoSp) and (Detec[$\kappa_L, q, \kappa_L$]) of $\hat{\tau}$ and the corresponding minimax lower bounds, it is worth emphasizing how and whether the detection and localization of a change-point $\tau_k^*$ depend on its height $\Delta_k$ and the segment lengths $(\tau_k^* - \tau_{k-1}^*)$ and $(\tau_{k+1}^* - \tau_k^*)$. First, its energy $E_k^2(\theta)$, which depends on both its height $\Delta_k$ and the segment lengths $(\tau_k^* - \tau_{k-1}^*)$ and $(\tau_{k+1}^* - \tau_k^*)$, must be high enough so that the change-point is detected. Then, when the change-point energy is high enough, that is once it can be detected, estimating $\tau_k^*$ becomes a local problem and the localization error $d_{H,1}(\hat{\tau}, \tau_k^*)$ only depends on the change-point height, and not on the segment lengths.

**Hausdorff and Wasserstein bounds.** Taking an union bound over all high-energy change-points yields

$$ \max_{k, \tau_k^* \text{ has high energy}} d_{H,1}(\hat{\tau}, \tau_k^*) \mathbf{1}_{A_q} = O_P(1) \max_{k, \tau_k^* \text{ has high energy}} \left( Ke^{-c'' \Delta_k^2} \wedge \frac{\log K}{\Delta_k^2} \right). $$
Now, assuming that all change-points have high-energy, we deduce that, on the event $A_q$ of Proposition 7 and Proposition 8, $\hat{K} = K$ and

$$ \mathbb{E} [d_W (\hat{\tau}, \tau^*) \mathbf{1}_{A_q}] \lesssim \sum_{k=1}^{K} \left( e^{-c'' \Delta_k^2} \wedge \frac{1}{\Delta_k^2} \right), \quad (37) $$

$$ \mathbb{E} [d_H (\hat{\tau}, \tau^*) \mathbf{1}_{A_q}] \lesssim \max_{k \in \{1, \dots, K\}} \left( K e^{-c'' \Delta_k^2} \wedge \frac{\log K}{\Delta_k^2} \right). \quad (38) $$

When all change-points $\tau_k^*$ have a common height value $\Delta_k = \Delta$, these two bounds turn out to be in view of the impossibility result (26) and (27) in Section 3. Note that the Hausdorff bound (38) can be slightly improved when the change-points heights $\Delta_k$ are heterogeneous, by using an union bound that puts more weights to small $\Delta_k$'s.

Up to our knowledge, the Wasserstein risk has only been investigated for a Wild Binary Segmentation estimator in [60] in a high dimensional framework, but the derived upper bound (see their Corollary 6) is of the order of $Kn^4/[(\min_{k \in \{1, \dots, K\}} \Delta_k)^2 (\min_{k \in \{0, \dots, K\}} (\tau_{k+1}^* - \tau_k^*)^4]$, which is is larger than $K^5/[(\min_{k \in \{1, \dots, K\}} \Delta_k)^2]$ and is therefore suboptimal.

The Hausdorff loss of the WBS estimator [26, 59], SMUCE [25], and the BIC-penalized least-square estimators [59], or other state-of-the art procedures [7, 44] are provably upper bounded by $\log(n)/(\min_{k \in \{1, \dots, K\}} \Delta_k)^2$ under a more restrictive assumption than the present high-energy requirement. Up to our knowledge, the only comparable Hausdorff bound has been recently and independently established by Cho and Kirch [17] under the stronger assumptions that $\min_k E_k(\theta) \gtrsim \sqrt{\log(n)}$.

### 4.2.3 Comparison with complexity-based penalized estimators

Let us investigate the behaviour of the penalized least-square estimator if one had chosen a $\ell_0$-type penalty of the form $L|\tau|\log(n)$, equal to the BIC penalty $\text{pen}_{\text{BIC}}$ up to the tuning parameter $L$, as studied in [59], instead of our multiscale penalty $\text{pen}_0(\tau, q))$. It is first worth emphasizing that the corresponding estimator $\hat{\tau}_{\text{BIC}}$ does not satisfy the property (Detec). Arguing as in (33), we derive from the definition of $\hat{\tau}_{\text{BIC}}$ that for any $l \le |\hat{\tau}_{\text{BIC}}|,$

$$ \mathbf{C}^2(\mathbf{Y}, ((\hat{\tau}_{\text{BIC}})_{l-1}, (\hat{\tau}_{\text{BIC}})_l, (\hat{\tau}_{\text{BIC}})_{l+1})) > L \log(n). $$

Unless $L$ is too small, this implies that $\hat{\tau}_{\text{BIC}}$ is only able to detect change-points whose energy is higher than $\sqrt{\log(n)}$. By constrast, when all the segment sizes $\tau_{k+1}^* - \tau_k^*$ for $k$ in $\{0, \dots, K\}$ are proportional to $n$, our penalized least-squares estimator $\hat{\tau}$ is able to detect change-points with constant energy (see Proposition 7). Then, inspecting the proof of Proposition 8, one can see that, when suitably tuned, the estimator $\hat{\tau}_{\text{BIC}}$ is able to localize change-points whose energy is large compared to $\sqrt{\log(n)}$ (that is, change-points that are detected) at the parametric rate $\Delta_k^{-2}$.

Since it also satisfies (NoSp), we can conclude that $\hat{\tau}_{\text{BIC}}$: (i) satisfies (NoSp), (ii) does not satisfy (Detec) but is able to detect change-point whose energy is large compared to $\sqrt{\log(n)}$, (iii) is able to localize such (very) high-energy change-point at the parametric rate $\Delta_k^{-2}$ as in Proposition 8.

Turning now to the model selection penalty $\text{pen}_{\text{MS}}(\tau) = |\tau|(1 + c \log(n/|\tau|))$ of [11, 46], we observe that the corresponding estimator $\hat{\tau}_{\text{MS}}$ partly shares the same weakness as $\hat{\tau}_{\text{BIC}}$: when $|\hat{\tau}_{\text{MS}}|$ is small, the penalty is close to $L|\tau|\log(n)$ and the estimator is overconservative. This is for instance the case when there are $K$ equi-spaced change-points with a small $K$. In other settings, $\hat{\tau}_{\text{MS}}$ detects many spurious change-points. As an example, consider the situation where, in the first
half of the sample, there is a high change-point (with a height much larger than $\sqrt{\log(n)}$) every five points and the signal is constant in the second half of the sample. Then, $\hat{\tau}_{MS}$ will detect all those change-points in the first half so that $|\hat{\tau}_{MS}| \ge n/10$. As a consequence, $\hat{\tau}_{MS}$ nearly behaves as the penalized least-squares estimator with a penalty of the order $c'|\tau|$ and one can then show that the number of spurious change-points in the second half is proportional to $n$.

## 4.3 Near-Minimal Penalty

In the previous subsection, we considered large values $L > L_0$ of the tuning parameter in (31). In practice, such large choice of $L$ may lead to too conservative procedures. One may then wonder how small one can take $L$ while still ensuring that $\hat{\tau}$ does not overestimate too much the number of true change-points. Following the same approach as in the above subsection, one observes that $\hat{\tau}$ does not contain more than two change-points on the segment $[\tau_k^*, \tau_{k+1}^*]$ as long as the following event holds:

$$ \left\{ |\mathbf{N}(\mathbf{t})| < L^{1/2} \sqrt{2 \log \left( \frac{n(t_3 - t_1)}{(t_3 - t_2)(t_2 - t_1)} \right) + q, \quad \forall \mathbf{t} \in \mathcal{T}_3} \right\} . $$

It turns out that such an event occurs with high probability (at least for $q$ not too small) for all $L > 1$. Conversely, it occurs with negligible probability when $L < 1$ (see Lemma 9 in the proofs Section for more details). As a consequence, for $L < 1$, the penalized least-squares estimator selects spurious change-points as illustrated by the next proposition.

**Proposition 9.** Let $\hat{\tau}$ denote the penalized least-squares estimator of $\tau^*$ defined above, and assume that $\epsilon$ in (1) satisfies ($A_G$). We have, for any fixed $L < 1$, any $q > 0$, any $n$ large enough, and any $\theta$ in $\Theta_0$, that

$$ \mathbb{P}_{\theta}(|\hat{\tau}| \ge 1) \ge 1 - n^{-1} . $$

This leads us to more carefully consider the penalized least-squares estimator (31) when $L > 1$.

**Proposition 10 (First step analysis).** For any $L > 1$, there exist positive constants $q'_0$, $c_1 - c_3$, $\kappa_L$ and $\eta_L$ in (0, 1) such that the following holds. Fix any $q > q'_0 + c_1 \log[(L \wedge 2) - 1]^{-1}$. There exists an event $A_{L,q}$ (defined in the proof) occurring with probability higher than $1 - c_1 e^{-c_2 q}$ on which the least-squares estimator $\hat{\tau}$ satisfies:

(a) No interval $[\tau_k^*, \tau_{k+1}^*)$ contains more than two change-points, that is

$$ |\{\hat{\tau}\} \cap [\tau_k^*, \tau_{k+1}^*)| \le 2; $$

Besides, the beginning and the end of the intervals do not contain more than one change-point:

$$ |\{\hat{\tau}\} \cap [\tau_k^*, \tau_k^* + \eta_L(\tau_{k+1}^* - \tau_k^*)]| \le 1, \quad |\{\hat{\tau}\} \cap [\tau_{k+1}^* - \eta_L(\tau_{k+1}^* - \tau_k^*), \tau_{k+1}^*]| \le 1. $$

(b) (Detec[$\kappa_K, q, \kappa_L$]). High-energy change-points are detected. For all $k$ in $\{1, \dots, K\}$ such that $\tau_k^*$ is a ($\kappa_L, q$)-high-energy change-point, we have

$$ d_{H,1}(\hat{\tau}, \tau_k^*) \le \min \left\{ \frac{\tau_{k+1}^* - \tau_k^*}{2}, \frac{\tau_k^* - \tau_{k-1}^*}{2}, \kappa_L \frac{\log(n\Delta_k^2) + q}{\Delta_k^2} \right\}; \quad (39) $$

(c) For all $k$ in $\{1, \dots, K\}$, either $\tau_k^*$ belongs to $\hat{\tau}$ or it is not a $((1.1\sqrt{L}+0.9), \hat{\tau}^{(k)}, q)$-high-energy change-point.
Here, we may have $\hat{K} > K$ and some post-processing procedure is needed to clean the estimator so that it may satisfy (NoSp).

Similarly to the analysis for large tuning parameter $L$, the localization rate of a specific high-energy change-point $\tau_k^*$ is of the order of $\Delta_k^{-2}$ as stated in the next proposition.

**Proposition 11** (Second step analysis). Consider any $L > 1$ and fix any $q > q'_0 + c_1 \log[(L \wedge 2) - 1]^{-1}$ and $A_{L,q}$ as in Proposition 10. Then, there exists $\kappa_L > 0$ such that for any $(\kappa_L, q)$-high-energy change-point $\tau_k^*$, the least-squares estimator $\hat{\tau}$ satisfies

$$ \mathbb{P} (d_{H,1}(\hat{\tau}, \tau_k^*) \mathbf{1}_{A_{L,q}} \geq c x \Delta_k^{-2}) \leq c' e^{-x} \quad \forall x \geq 1 + \log(L-1)_+ . $$

In summary, it turns out that properties (Detec) and (Loc) are valid all the way down to the minimal penalty tuning parameter $L > 1$.

# 5 Post-processing procedure

Given any vector $\tau$ of estimated change-points, we describe here a post-processing procedure for local improvements of $\tau$. As e.g. in [26], this post-processing procedure is a two steps procedure: the first step consists in cleaning spurious change-points of $\tau$; the second one ensures improvement of the localization of well-separated change-points. We underline that, in this section, the preliminary estimator $\tau$ possibly depends on the data $\mathbf{Y}$.

## 5.1 Pruning step

In the pruning step, we rely on the CUSUM statistic (3) to build confidence intervals around each $\tau_l$ for $l = 1, \dots, |\tau|$. Given $\alpha$ in $(0, 1)$, let $\zeta_{1-\alpha}$ be the smallest number satisfying

$$ \mathbb{P} \left[ \sup_{\mathbf{t} \in \mathcal{T}_3} \left( |\mathbf{N}(\mathbf{t})| - \sqrt{2 \log \left( \frac{n(t_3 - t_1)}{(t_3 - t_2)(t_2 - t_1)} \right)} \right) > \zeta_{1-\alpha} \right] \leq \alpha . \quad (40) $$

From Lemma 9, we know that $\zeta_{1-\alpha} \leq c_1 + c_2 \sqrt{\log(1/\alpha)}$ for two numerical constants $c_1$ and $c_2$. If the distribution of the noise vector $\epsilon$ in (1) is a Gaussian distribution or another known distribution that can be simulated, then $\zeta_{1-\alpha}$ can be approximated by a Monte-Carlo method. In the sequel, we denote by $B_{1-\alpha}$ the event such that $|\mathbf{N}(\mathbf{t})| \leq \sqrt{2 \log(\frac{n(t_3-t_1)}{(t_3-t_2)(t_2-t_1)})} + \zeta_{1-\alpha}$ for all $\mathbf{t}$ in $\mathcal{T}_3$.

Given $\tau$ in $\{2, \dots, n\}$ and a positive integer $r$, define $\mathbf{t}^{(\tau,r)} = ((\tau - r) \vee 1, \tau, (\tau + r) \wedge (n+1))$. In the simple case where $r < \tau \wedge (n - \tau)$, then $\mathbf{t}^{(\tau,r)}$ is simply the triplet $(\tau - r, \tau, \tau + r)$ centered at $\tau$ with radius $r$. Then, we define $\hat{r}_{\tau}$, the smallest radius $r$ such that the CUSUM statistic $\mathbf{C}(\mathbf{Y}, \mathbf{t}^{(\tau,r)})$ centered at $\tau$ is significantly large:

$$ \hat{r}_{\tau} = \min \left\{ r, \left| \mathbf{C}(\mathbf{Y}, \mathbf{t}^{(\tau,r)}) \right| > \sqrt{2 \log \left( \frac{n(t_3^{(\tau,r)} - t_1^{(\tau,r)})}{(t_3^{(\tau,r)} - t_2^{(\tau,r)})(t_2^{(\tau,r)} - t_1^{(\tau,r)})} \right)} + \zeta_{1-\alpha} \right\}, \quad (41) $$

with the convention $\min\{\emptyset\} = +\infty$. This leads us to the following confidence interval $\underline{I}_{\tau}$ around $\tau$.

$$ \underline{I}_{\tau} = [t_1^{(\tau, \hat{r}_{\tau})} + 1, t_3^{(\tau, \hat{r}_{\tau})} - 1], \quad (42) $$
Recall from the definitions (3) and (34) of $\mathbf{C}(\mathbf{Y}, \mathbf{t})$ and $\mathbf{N}(\mathbf{t})$ that, if no change-point occurs in $[t_1^{(\tau,r)} + 1, t_3^{(\tau,r)} - 1]$, then $\mathbf{C}(\mathbf{Y}, \mathbf{t}^{(\tau,r)}) = \mathbf{N}(\mathbf{t}^{(\tau,r)})$. Hence, if no change-point occurs in $[t_1^{(\tau, \hat{r}_\tau)} + 1, t_3^{(\tau, \hat{r}_\tau)} - 1]$, then $\hat{r}_\tau$ is the smallest radius such that $|\mathbf{N}(\mathbf{t}^{(\tau,r)})|$ is larger than

$$ \sqrt{2 \log \left( \frac{n(t_3^{(\tau,r)} - t_1^{(\tau,r)})}{(t_3^{(\tau,r)} - t_2^{(\tau,r)})(t_2^{(\tau,r)} - t_1^{(\tau,r)})} \right) + \zeta_{1-\alpha}} , $$

which contradicts the event $\mathcal{B}_{1-\alpha}$ defined in (40). We conclude that, under $\mathcal{B}_{1-\alpha}$, all intervals $\underline{I}_\tau$ contain at least one true change-point.

As a consequence, if two intervals $\underline{I}_\tau$ and $\underline{I}_{\tau'}$ are disjoint, then the closest true change-point from $\tau$ differs from the closest true change-point from $\tau'$. In a nutshell, the pruning step amounts to removing change-points in $\tau$ in such a way that the confidence intervals around the coordinates of the pruned change-point vector do not intersect. The procedure (described in Algorithm 1 below) first and foremost prunes wide confidence intervals, since the corresponding estimated change-points are more prone to lie farther from a true change-point than narrow confidence intervals.

Given a vector $\tau$ and the corresponding confidence intervals $\underline{I}_{\tau_1}, \dots, \underline{I}_{\tau_{|\tau|}}$, we reorder the change-points by decreasing sizes of the corresponding confidence intervals, that is $\tau_{(1)}, \tau_{(2)}, \dots, \tau_{(|\tau|)}$ are such that $\hat{r}_{\tau_{(1)}} \ge \hat{r}_{\tau_{(2)}} \ge \dots \ge \hat{r}_{\tau_{(|\tau|)}}$.)

**Algorithm 1 Pruning Step**

1: $\mathcal{P}(\tau) = \tau$ {Initialization with all change-points}

2: **for** $l = 1, \dots, |\tau| - 1$, **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;**if** $(\hat{r}_{\tau_{(l)}} = \infty)$ or $(\underline{I}_{\tau_{(l)}} \text{ intersects } \bigcup_{j>l} \underline{I}_{\tau_{(j)}})$ **then**

4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Remove $\tau_{(l)}$ from $\mathcal{P}(\tau)$.

5: **end if**

6: **end for**

**Output:** $\mathcal{P}(\tau)$

In the next proposition, we say that a true change-point $\tau_k^*$ is reasonably well localized by $\tau$ if

$$ d_{H,1}(\tau, \tau_k^*) < \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{8} . \quad (43) $$

**Proposition 12.** There exist universal constants $\kappa$ and $c$ such that the following holds for any $\alpha$ in $(0, 1)$. On the event $\mathcal{B}_{1-\alpha}$ of probability higher than $1 - \alpha$ and for any sequence $\tau$, we have

(a) (NoSp) $\mathcal{P}(\tau)$ does not detect any spurious change-point:

$$ \left\{ \begin{array}{l} \left| \mathcal{P}(\tau) \right| \cap \left( \frac{\tau_{k-1}^* + \tau_k^*}{2}, \frac{\tau_k^* + \tau_{k+1}^*}{2} \right] \le 1 \text{ , for all } k \text{ in } \{2, \dots, K-1\} ; \\ \left| \mathcal{P}(\tau) \right| \cap \left[ 2, \frac{\tau_1^* + \tau_2^*}{2} \right] \le 1 \text{ ; } \left| \mathcal{P}(\tau) \right| \cap \left( \frac{\tau_{K-1}^* + \tau_K^*}{2}, n \right] \le 1 \text{ .} \end{array} \right. $$

(b) (Detec[$\kappa, \zeta_{1-\alpha}^2, c$]) Any ($\kappa, \zeta_{1-\alpha}^2$)-high-energy change-point $\tau_k^*$ that is reasonably well localized by $\tau$ (in the sense of (43)) also satisfies

$$ d_{H,1}(\mathcal{P}(\tau), \tau_k^*) \le \left(2d_{H,1}(\tau, \tau_k^*)\right) \vee \left(c \frac{\log(n\Delta_k^2) + \zeta_{1-\alpha}^2}{\Delta_k^2}\right) . \quad (44) $$
Note that any high-energy change-point $\tau_k^*$ detected by $\tau$ is also detected by $\mathcal{P}(\tau)$. Unfortunately, Proposition 12 does not ensure that $\mathcal{P}(\tau)$ has kept the closest change-point to $\tau_k^*$ in $\mathcal{P}(\tau)$ (it is only known to satisfy (44)). For this reason, we introduce a second post-processing step that aim at improving the localization rate for $\tau_k^*$.

## 5.2 Local Improvements

Consider any $\tau$ in $\{2, \dots, n\}$ and the associated confidence interval $\underline{I}_{\tau}$ defined in (42). We suggest to re-estimate $\tau$ by minimizing a restricted least-squares type criterion over $\underline{I}_{\tau}$. Consider the restricted vector $\mathbf{Y}^{(\tau, 2\hat{r}_{\tau}-1)} = (Y_{t_1^{\tau, 2\hat{r}_{\tau}-1}, \dots, Y_{t_3^{\tau, 2\hat{r}_{\tau}-1}_1})$. For a small $\hat{r}_{\tau}$, this means that we only keep the observations in $[\tau - 2\hat{r}_{\tau} + 1, \tau + 2\hat{r}_{\tau} - 2]$. Let $\mathcal{L}(\tau)$ be the change-point estimator minimizing over $\underline{I}_{\tau}$ the restricted least-squares criterion:

$$ \mathcal{L}(\tau) \in \arg \min_{\tau' \in \underline{I}_{\tau}} \|\mathbf{\Pi}_{\tau'} \mathbf{Y}^{(\tau, 2\hat{r}_{\tau}-1)}\|^2 . $$

Equivalently, $\mathcal{L}(\tau)$ is any maximizer of the CUSUM statistic $\mathbf{C}[\mathbf{Y}, (t_1^{\tau, 2\hat{r}_{\tau}-1}, \tau', t_3^{\tau, 2\hat{r}_{\tau}-1})]$ over $\tau' \in \underline{I}_{\tau}$. For short, we write $\mathcal{L}(\tau)$ for the vector $(\mathcal{L}(\tau_l))_{l=1,\dots,|\tau|}$ and we write $\mathcal{LP}(\tau) = \mathcal{L}(\mathcal{P}(\tau))$ for the change-point vector obtained after Pruning and Local improvement of $\tau$.

Re-estimating the change-point positions by a restricted least-squares criterion minimization was already proposed in the literature (see e.g; [26, Section 3.2]). Nevertheless, our fitting method differs in two ways: first, we restrict the new position to belong to $\underline{I}_{\tau}$ and second, we only consider data at distance less than $2\hat{r}_{\tau}$ from $\tau$ whereas [26] considers data that are closer to $\tau$ than any of the other estimated change-points. These two differences allow us to better handle cases where some of the true change-points have a small energy.

**Proposition 13 (Loc[$\kappa, \zeta_{1-\alpha}^2, c, c'$**)}.** There exist $\kappa$ and $c$ such that, on the event $\mathcal{B}_{1-\alpha}$ defined below (40), the following holds for any $\theta$ in $\mathbb{R}^n$, any $(\kappa, \zeta_{1-\alpha}^2)$-high energy change-point $\tau_k^*$ and any $\tau$ in $\{2, \dots, n\}$. If

$$ |\tau - \tau_k^*| < \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{4}, $$

Then, for any $x > 0$, we have

$$ \mathbb{P}_{\theta} \left( |\mathcal{L}(\tau) - \tau_k^*| \mathbf{1}_{\mathcal{B}_{1-\alpha}} \geq c \frac{x \vee 1}{\Delta_k^2} \right) \leq e^{-x}. $$

Fix any $L > 1$ and consider the post-processed penalized least-squares estimator $\mathcal{LP}(\hat{\tau})$ with $L > 1$ and some $q \geq q'_0 + \log[(L \wedge 2 - 1)^{-1}]$. Then, it follows from the above propositions that, on the event $\mathcal{A}_q \cap \mathcal{B}_{1-\alpha}$ of probability higher than $1 - c e^{-c'q} - \alpha$, one has

(a) (NoSp). $\mathcal{LP}(\hat{\tau})$ does not detect any spurious change-point.

(b) (Detec[$\kappa_L, q \vee \zeta_{1-\alpha}^2, c$]) Any $(\kappa_L, q \vee \zeta_{1-\alpha}^2)$-high-energy change-point $\tau_k^*$ is reasonably well localized by $\mathcal{LP}(\hat{\tau})$

$$ d_{H,1}(\mathcal{LP}(\hat{\tau}), \tau_k^*) \leq \frac{(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)}{2} \wedge \left( c \frac{\log(n\Delta_k^2) + q}{\Delta_k^2} \right). $$
(c) (Loc[$κ_L$, $q \lor \zeta_{1-\alpha}^2$, $c$, $c'$]) For all such ($κ_L$, $q \lor \zeta_{1-\alpha}^2$)-high-energy change-points $τ_k^*$ we have

$$ \mathbb{P}_{\theta} \left( d_{H,1}(\mathcal{LP}(\hat{\tau}), \tau_k^*) \mathbf{1}_{A_q \cap B_{1-\alpha}} \geq c \frac{x \lor 1}{\Delta_k^2} \right) \leq c' e^{-x}, \quad \forall x > 1. $$

The post-processed least-squares estimator with $L > 1$ therefore achieves the three aforementioned properties (NoSp), (Detec), and (Loc).

## 5.3 Post-processing the complete change-point vector as self-standing procedure

The post-processing method can also be used as a self-standing change-point detection procedure by simply applying it to the full vector $τ_f = \{2, 3, \dots, n\}$ of the $n-1$ possible change-points. From Propositions 12 and 13, we deduce the following.

**Corollary 1** (Analysis of $\mathcal{LP}(τ_f)$). Consider any $α$ in $(0, 1)$. There exist numerical constants $κ$, $c$, $c'$ and an event $B_{1-α}$ (defined below (40)) of probability higher than $1 - α$, such that on $B_{1-α}$, $\mathcal{LP}(τ_f)$ satisfies (NoSp), (Detec[$κ$, $\zeta_{1-α}^2$, $c$]), and (Loc[$κ$, $\zeta_{1-α}^2$, $c$, $c'$]).

In summary, $\mathcal{LP}(τ_f)$ achieves all the optimality performances specified in Section 3.3. In particular, its performances with respect to Hausdorff and Wasserstein risks are similar to that of the penalized least-squares estimators (see (37) and (38)).

**Computational complexity.** In worst case, computing $\mathcal{LP}(τ_f)$ requires $O(n^2)$ operations. If we slightly modify the definition of $\hat{r}_τ$ by considering $\hat{r}_τ^{(d)}$ taking values in the dyadic set $\mathbb{D} := \{1, 2, 4, \dots, 2^{\lfloor \log_2 n \rfloor}\}$ and if we take a confidence interval $I_τ^{(d)}$ based on $\hat{r}_τ^{(d)}$, Proposition 12 and Corollary 1 still remain valid for the corresponding Pruned and Locally improved $τ_f$ denoted by $\mathcal{P}^{(d)}(τ_f)$ and $\mathcal{LP}^{(d)}(τ_f)$ respectively, to the price of slightly worse numerical constants $c$ and $κ$. Besides, $\mathcal{LP}^{(d)}(τ_f)$ can be computed in $O(n \log n)$ operations with a $O(n)$ space complexity. Indeed, for $τ$ in $(r, n-r)$, $\mathbf{C}(\mathbf{Y}, \mathbf{t}^{(τ+1),r}) - \mathbf{C}(\mathbf{Y}, \mathbf{t}^{\tau,r})$ only depends on $Y_τ$, $Y_{τ+r}$ and $Y_{τ-r}$. As a consequence, if all the $\mathbf{C}(\mathbf{Y}, \mathbf{t}^{\tau,r})$ are stored, then $\hat{r}_{τ+1}^{(d)}$ can be computed in $O(\log n)$ operations which results in $O(n \log n)$ operations to compute all the confidence intervals $I_τ^{(d)}$. Then, checking whether each $I_{\tau(l)}^{(d)}$ intersects $\cup_{j>l} I_{\tau(j)}^{(d)}$ can be done in $O(\log n)$ operations using a binary search algorithm. Finally, the local improvement step computational complexity is at worst linear. In summary, the total complexity is $O(n \log(n))$ and as low as the one of some Binary Segmentation algorithms (see [27, 44]) or multiscale MOSUM [17], while it enjoys the targeted optimality properties (NoSp), (Detec), and (Loc).

## 5.4 A simple global confidence region

Given a change-point vector $τ$, we define the global confidence interval $\tilde{I}_τ^{(g)}$ as the union of the confidence intervals $I_{\tau_l}$ introduced in (42).

$$ \tilde{I}_{\tau}^{(g)} = \cup_{l \in \{1, \dots, |\tau|\}} I_{\tau_l} \qquad (45) $$

It follows from the definition (42) of $I_τ$ that, with probability higher than $1 - α$, each segment of $\tilde{I}_τ^{(g)}$ contains at least one true change-point. For suitable estimators $τ$ we have the following.

**Corollary 2.** Let $τ$ be one of the three following estimators:
(i) the penalized least-squares estimator $\hat{\tau}$ with large tuning parameter $L$ (as in Proposition 7),

(ii) the post-processed least-squares estimator $\mathcal{LP}(\hat{\tau})$ with $L \ge 1$,

(iii) the post-processed complete vector $\mathcal{LP}(\tau_f)$.

Then with probability higher than $1 - \alpha$, $\tilde{I}_{\tau}^{(g)}$ satisfies:

(a) Each segment of $\tilde{I}_{\tau}^{(g)}$ contains at least one true change-point;

(b) Each $(\kappa, \zeta_{1-\alpha}^2)$-high energy change-point $\tau_k^*$ belongs to $\tilde{I}_{\tau}^{(g)}$. Besides, the width of the corresponding segment in $\tilde{I}_{\tau}^{(g)}$ is less or equal to

$$c \frac{\log(n\Delta_k^2) + \zeta_{1-\alpha}^2}{\Delta_k^2}.$$

The proof is straightforward and is therefore omitted. In the above corollary, all the change-points do not necessarily have a high energy but we allow such change-points not to belong to $\tilde{I}_{\tau}^{(g)}$. This contrasts with the results of Frick et al. [25] which require that all the change-points have a high-energy: $\mathbb{E}_{min}(\theta) \ge \log[n/(\min_{k \in \{0, \dots, K\}}(\tau_{k+1}^* - \tau_k^*))]$.

If we had assumed that all the energies of the change-points were high, we could improve the tuning confidence region $\tilde{I}_{\tau}^{(g)}$ to segments of size $\log K/\Delta_k^2$ by plugging an estimator of $\Delta_k$ in Hausdorff bounds such as (38). Similarly, one could also obtain a confidence interval of width $c_\alpha/\Delta_k^2$ for a specific change-point $\tau_k^*$ by plugging an estimator of $\Delta_k$ in Propositions 8 or 13.

# 6 Discussion

## 6.1 Adaptation to $K \le 1$ and $K > 1$

In the later parts of the manuscript, we allowed the number $K$ to lie between 0 and $n-1$. Still, when $K=1$, our multiple change-point procedures only detect $\tau_1^*$ when its energy $\mathbb{E}_1^2(\theta)$ is large compared to $\log(n/((\tau_1^* - 1) \wedge (n+1-\tau_1^*))$). In Section 2, we established that it is possible to detect and localize change-points $\tau_1^*$ for energies that are logarithmically smaller. It is possible to combine the results to achieve simultaneous optimality for both $K \le 1$ and $K > 1$ with the following scheme. First, one computes an estimator $\hat{\tau}$ using either the penalized criterion (31) or the two-step methods $\mathcal{LP}(\tau_f)$. If $|\hat{\tau}| > 0$, then $\hat{\tau}$ is left unchanged. If $|\hat{\tau}| = 0$ (no change-point detected), the null hypothesis of non-existence of a change-point is tested (Section 2.2.1). If the test accepts the null, $\hat{\tau}$ is left unchanged again (no-change point detected). If the test rejects the null, one uses for $\hat{\tau}$ the one-change point least-squares estimator of Section 2.2. One can then easily prove that the resulting $\hat{\tau}$ is simultaneously optimal for both settings.

## 6.2 Extensions: unknown variance, heavy tail distributions and dependences

Considering the model (1), where the noise $\epsilon$ has a Gaussian distribution, but with an unknown variance, the unknown variance has to be estimated: the resulting estimator can then be plugged-in to rescale the data $\mathbf{Y}$. Suppose that we are given an estimator $\hat{\sigma}$ (possibly depending on $\mathbf{Y}$) such that the ratio $\hat{\sigma}/\sigma$ belongs to $[1, 2]$ on an event $\mathcal{E}$ of high probability. Then, all the properties of our multiscale least-squares and post-processing procedures remain valid on the event $\mathcal{E}$. Some practical recommendations for estimating $\sigma$ are given in [28]. As an alternative to estimating $\sigma$,
one could calibrate the multiplicative constant $L$ of the penalized least-squares estimator $\hat{\tau}$ using
the slope heuristic [4]. Indeed, the slope heuristic is partly validated by Propositions 9 and 10.

The only stochastic ingredient in the first step analysis of the multiscale penalized estimator
(Propositions 7 and 10) and in the analysis of the pruning step of the post-processing procedure
(Proposition 12) is an uniform control (34) of the noise variables $N(t)$. In the presence of de-
pendences between the noise variables (as e.g. in [17]), these stochastic controls become more
challenging and the constants need to be adapted. Upon establishing such controls, the remainder
of the proofs and the conclusion of the propositions remain unchanged (up to other constants).
If the noise tails are heavier than sub-Gaussians, then uniform controls of the form (40) do not
hold anymore. Relying on chaining arguments as in the proof of Lemma 9, we would obtain larger
uniform bounds for $|N(t)|$ (in the spirit of [17]). Hence, the form (32) of the penalty $\text{pen}_0(\tau, q)$ and
thresholds for confidence intervals (41) have to be accommodated in a similar fashion to [17]. As for
the local analyses (Propositions 8, 11, and 13), it seems of reach to accommodate the presence of
mild dependences or heavier tails and still derive a local error of order $\Delta_k^{-2}$, but the tail distribution
of the error will not be exponential anymore. We leave this as an open problem.

## 6.3 Exact constant for multiple change-point detection

In the single change-point problem, we establish that the exact leading constant for detection
equals $\sqrt{2}$, whereas all of our detection results in the multiple change-point setting are stated up
to numerical constants.

Let us shortly discuss the setting of segment detection. Segment detection is a specific instance
of the change-point problem where $K$ is even, $\mu_1 = \mu_3 = \dots = \mu_{K+1} = 0$ and, for $\ell = 1, \dots, K/2$,
$\tau_{2\ell}^* - \tau_{2\ell-1}^*$ is much smaller than $\tau_{2\ell-1}^* - \tau_{2\ell-2}^*$. In other words, the signal $\theta$ is null except at $K/2$
segments that are well-spaced. It has been established in [16, 43] that a segment (and the two
corresponding change-points $\tau_{2\ell-1}^*$ and $\tau_{2\ell}^*$) can be confidently detected as long as $\tau_{2\ell-1}^*$ is a $(\kappa, q)$-
high energy change point with $\kappa = 1$, as defined in (22). We conjecture that the constant $\kappa = 1$ is
not sufficient in the more general change-points detection problem so that the segment detection
problem is intrinsically easier than change-point detection. Still, we leave this as an open question.

## 6.4 Do other classical procedures satisfy the optimality requirements (NoSp), (Detec) and (Loc)?

While we have introduced two change-point procedures meeting the specific requirements, this does
not imply that they outperform other procedures. As discussed in Section 4, the BIC-penalized,
when tuned suitably, achieves (NoSp) and variants ($\text{Detec}_{\log(n)}$) and ($\text{Loc}_{\log(n)}$) of (Detec) and
($\text{Loc}$) where only change-points whose energy is high compared to $\sqrt{\log(n)}$ are detected and
localized at the parametric rate.

At the very least, achieving (Detec) (instead of ($\text{Detec}_{\log(n)}$)) is possible only if the procedure
uses scale-adaptive threshold as in Frick et al. [25] or Cho and Kirch [17]. Still, some work is
required to check whether their methods accommodate well low-energy change-points. Investigating
the proofs of Baranowski et al. [7] and Kovács et al. [44], we believe that both NOT and Seeded
Binary Segmentation achieve (NoSp) and ($\text{Detec}_{\log(n)}$), but it is not straightforward to check
whether (Loc) holds or not.

Our desired properties of the form (NoSp), (Detec) and (Loc) are more restrictive than
typical recent results in the literature by (i) tightening the logarithms (ii) requiring a parametric
localization rate of the detection threshold and (iii) allowing for possibly many small jumps that are
undetectable and possibly act as nuisance parameters. This last requirement is more in line with the literature on related statistical fields such as multiple testing or high-dimensional variable selection. Such desiderata can be extended to many other change-points settings beside the univariate case including change-points analysis in the multivariate [60] or kernel [5] frameworks. We hope that it will stimulate a research agenda towards optimal procedures in these settings.

# 7 Proofs for a single change-point

For any two integers $t_1, t_2$ such that $1 \le t_1 < t_2 \le n + 1$, we denote

$$Z_{t_1:t_2} := \sum_{i=t_1}^{t_2-1} \epsilon_i, \qquad (46)$$

the partial sum. Besides, we shall often write $\mathbf{E}_k$ for $\mathbf{E}_k(\theta)$ to alleviate the notation.

## 7.1 Proof of Proposition 1

Consider the dyadic collection $\mathcal{T} = \{2^l; l = 1, \dots, \lfloor \log_2(n)/2 \rfloor\}$ where $\log_2(n) = \log(n)/\log(2)$. In the sequel, we denote $a = \kappa^2/[4(1-\kappa)]$, and for $\tau$ in $\mathcal{T}$, we define $\theta(\tau)$ in $\Theta_1$ by $\theta_i^{(\tau)} = 0$ for $i \ge \tau$ and $\theta_i^{(\tau)} = \sqrt{2(1-\kappa)\log\log(n)/(\tau-1)}$ for any $i < \tau$. As a consequence, $\|\theta(\tau)\| = \sqrt{2(1-\kappa)\log\log(n)}$ and the energy $\mathbf{E}_1(\theta(\tau))$ satisfies $\mathbf{E}_1^2(\theta(\tau))/[2(1-\kappa)\log\log(n)] \in [1-n^{-1/2}; 1]$. To alleviate the notation, we write $\mathbb{P}_\tau$ for the distribution $\mathbb{P}_{\theta(\tau)}$, while $\mathbb{P}_0$ still stands for the distribution of $\mathbf{Y}$ when $\theta = 0$.

We claim that testing whether $\Theta = 0$ versus $\Theta \in \{\Theta^{(\tau)}, \tau \in \mathcal{T}\}$ with small type I and Type II error probabilities is impossible. More precisely we shall prove that there exists a constant $c > 0$ such that, for any test $\mathcal{T}$,

$$\mathbb{P}_0[\mathcal{T} = 1] + \max_{\tau \in \mathcal{T}} \mathbb{P}_{\tau}[\mathcal{T} = 0] \ge 1 - c \log^{-a/2}(n). \qquad (47)$$

Note that (47) implies the result of the proposition. Following Le Cam's approach [8], we define the mixture probability $\mathbf{P} = |\mathcal{T}|^{-1} \sum_{\tau \in \mathcal{T}} \mathbb{P}_\tau$. Since

$$\mathbb{P}_0[\mathcal{T} = 1] + \max_{\tau \in \mathcal{T}} \mathbb{P}_{\tau}[\mathcal{T} = 0] \ge \mathbb{P}_0[\mathcal{T} = 1] + \mathbf{P}[\mathcal{T} = 0] \\ \ge 1 - |\mathbb{P}_0[\mathcal{T} = 1] - \mathbf{P}[\mathcal{T} = 1]|,$$

inequality (47) is satisfied for all test $\mathcal{T}$ if the total variation distance between $\|\mathbb{P}_0 - \mathbf{P}\|_{TV}$ is less or equal to $c \log^{-a/2}(n)$. Writing $L_\tau$ the likelihood ratio of $\mathbb{P}_\tau$ over $\mathbb{P}_0$ and $L = |\mathcal{T}|^{-1} \sum_{\tau \in \mathcal{T}} L_\tau$ the likelihood ratio of $\mathbf{P}$ over $\mathbb{P}_0$, this is in turn equivalent to

$$\| \mathbb{P}_0 - \mathbf{P} \|_{TV} = \frac{1}{2} \mathbb{E}_0[|L - 1|] \le c \log^{-a/2}(n). \qquad (48)$$

To upper bound the first moment of $|L - 1|$ it is usual to apply Cauchy-Schwarz inequality and to control the second moment of the likelihood ratio. Unfortunately, the corresponding second moment is small only for $\kappa > 1/2$. Here, we rely on a slight variation of this approach originally introduced by Ingster [40] and strengthened in [3]. We introduce a thresholded likelihood $\tilde{L} \le L$ such that $\mathbb{E}_0[|L - \tilde{L}|]$ is small enough and $\mathbb{E}_0[\tilde{L}^2]$ is close to one.
For any $\tau \in \mathcal{T}$, define the event $\Gamma_{\tau} = \{\langle \mathbf{Y}, \boldsymbol{\theta}(\tau) \rangle \le \|\boldsymbol{\theta}(\tau)\|^2 + \|\boldsymbol{\theta}(\tau)\|\sqrt{2a \log \log(n)}\}$. Under $\mathbb{P}_{\tau}$, $\langle \mathbf{Y}, \boldsymbol{\theta}(\tau) \rangle$ is distributed as a normal random variable with mean $\|\boldsymbol{\theta}(\tau)\|^2$ and variance $\|\boldsymbol{\theta}(\tau)\|^2$. As a consequence, we have $\mathbb{P}_{\tau}[\Gamma_{\tau}^c] = \bar{\Phi}(\sqrt{2a \log \log(n)}) \le \log^{-a}(n)$.

Define the thresholded likelihood $\tilde{L}_{\tau} = L_{\tau} \mathbf{1}_{\Gamma_{\tau}}$ and $\tilde{L} = |\mathcal{T}|^{-1} \sum_{\tau \in \mathcal{T}} \tilde{L}_{\tau}$. We have $\tilde{L} \le L$ and

$$ \mathbb{E}_0[L - \tilde{L}] = \frac{1}{|\mathcal{T}|} \sum_{\tau \in \mathcal{T}} \mathbb{E}_0[L_{\tau} \mathbf{1}_{\Gamma_{\tau}^c}] = \frac{1}{|\mathcal{T}|} \sum_{\tau \in \mathcal{T}} \mathbb{P}_{\tau}[\Gamma_{\tau}^c] \le \log^{-a}(n). $$

Let us now upper bound the total variation distance between $\mathbb{P}_0$ and $\mathbf{P}$ by introducing the thresholded likelihood.

$$ \begin{aligned} \mathbb{E}_0[|L - \tilde{L}|] & \le \mathbb{E}_0[|L - \tilde{L}|] + \mathbb{E}_0[|\tilde{L} - 1|] \le \mathbb{E}_0[L - \tilde{L}] + \mathbb{E}_0^{1/2}[|\tilde{L} - 1|^2] \\ & \le \mathbb{E}_0[L - \tilde{L}] + \left[\mathbb{E}_0[\tilde{L}^2] - 1 + 2 \mathbb{E}_0[L - \tilde{L}]\right]^{1/2} \\ & \le \frac{3}{\log^{a/2}(n)} + \left[\mathbb{E}_0[\tilde{L}^2] - 1\right]^{1/2}, \end{aligned} \quad (49) $$

where we used that $L \ge \tilde{L}$ and Cauchy-Schwarz inequality. Let us work out the second thresholded moment.

$$ \begin{aligned} \mathbb{E}_0[\tilde{L}^2] &= \frac{1}{|\mathcal{T}|^2} \sum_{\tau, \tau' \in \mathcal{T}} \mathbb{E}_0[\tilde{L}_{\tau} \tilde{L}_{\tau'}] \\ &\le \frac{1}{|\mathcal{T}|^2} \sum_{\tau, \tau' \in \mathcal{T}} \left[ \mathbf{1}_{|(\tau-1)/(\tau'-1)| \in [\frac{1}{16}; 16]} \mathbb{E}_0 \left[ \frac{\tilde{L}_{\tau}^2 + \tilde{L}_{\tau'}^2}{2} \right] + \mathbf{1}_{|(\tau-1)/(\tau'-1)| \notin [\frac{1}{16}; 16]} \mathbb{E}_0 [L_{\tau} L_{\tau'}] \right] \\ &\le \frac{1}{|\mathcal{T}|} \sum_{\tau \in \mathcal{T}} \left[ 9 \mathbb{E}[\tilde{L}_{\tau}^2] + \frac{1}{|\mathcal{T}|} \sum_{|(\tau-1)/(\tau'-1)| \notin [\frac{1}{16}; 16]} \mathbb{E}_0 [L_{\tau} L_{\tau'}] \right], \end{aligned} \quad (50) $$

where we used Young's inequality and $L_{\tau} \le L_{\tau'}$ in the second inequality. Let us first work out the right-hand side term in (50). For $\tau' > \tau$, standard computations lead to

$$ \mathbb{E}_0 [L_{\tau} L_{\tau'}] = \exp \left[ \langle \boldsymbol{\theta}(\tau), \boldsymbol{\theta}(\tau') \rangle \right] = e^{2(1-\kappa) \log \log(n) \sqrt{\frac{\tau-1}{\tau'-1}}} \le e^{2 \log \log(n) \sqrt{\frac{\tau-1}{\tau'-1}}}. $$

If $(\tau' - 1)/(\tau - 1) \ge \log^2(n)$, then we get

$$ \mathbb{E}_0 [L_{\tau} L_{\tau'}] \le e^{2 \log \log(n) / \log(n)} \le 1 + \frac{4 \log \log(n)}{\log(n)}, $$

for $n$ large enough. When $(\tau' - 1)/(\tau - 1) > 16$, then $\mathbb{E}_0 [L_{\tau} L_{\tau'}] \le \sqrt{\log(n)}$. As a consequence,

$$ \begin{aligned} \frac{1}{|\mathcal{T}|} \sum_{|\tau/\tau'| \notin [\frac{1}{16}; 16]} \mathbb{E}_0 [L_{\tau} L_{\tau'}] & \le 1 + \frac{4}{\log \log(n)} + \frac{\sqrt{\log(n)}}{|\mathcal{T}|} \left| \left\{ \tau', \max\left(\frac{\tau' - 1}{\tau - 1}; \frac{\tau - 1}{\tau' - 1}\right) \in [16; \log^2(n)] \right\} \right| \\ & \le 1 + \frac{4 \log \log(n)}{\log(n)} + c \frac{\log \log(n)}{\sqrt{\log(n)}} \le 1 + c \frac{\log \log(n)}{\sqrt{\log(n)}}. \end{aligned} \quad (51) $$

The second thresholded moment is upper bounded in the following lemma
**Lemma 3.** For any $\tau \in \mathcal{T}$, we have

$$ \mathbb{E}_0 [L_{\tau}^2 \mathbf{1}_{\Gamma_{\tau}}] \leq \log(n)^{1-a}, $$

Since $|\mathcal{T}| = [\log_2(n)]/2$ and $a \le 1/3$, we conclude from (50), (51), and the last inequality that $\mathbb{E}_0[\tilde{L}^2] \le 1 + c \log^{-a}(n)$ which, together with (49) leads us to $\mathbb{E}_0[|L - 1|] \le c \log^{-a/2}(n)$. The result follows.

*Proof of Lemma 3.* Let $Z$ denote a standard random variable. Since under the null, $\langle \mathbf{Y}, \theta(\tau) \rangle$ is distributed as $Z \|\theta(\tau)\|$, we derive that

$$ \begin{aligned} \mathbb{E}_0 [L_{\tau}^2 \mathbf{1}_{\Gamma_{\tau}}] &= \mathbb{E} \left[ e^{2Z \|\theta(\tau)\|^2 - \|\theta(\tau)\|^2} \mathbf{1}_{Z \le \|\theta(\tau)\| + \sqrt{2a \log \log(n)}} \right] \\ &= \int_{-\infty}^{\sqrt{2 \log \log(n)}[\sqrt{1-\kappa} + \sqrt{a}]} \phi \left( z - 2\sqrt{2(1-\kappa)\log \log(n)} \right) e^{2(1-\kappa)\log \log(n)} dz \\ &= \log^{2(1-\kappa)}(n) \bar{\Phi} \left[ \sqrt{2 \log \log(n)}[\sqrt{1-\kappa} - \sqrt{a}] \right] \\ &\le \log(n)^{1-\kappa-a+2\sqrt{(1-\kappa)a}} = \log(n)^{1-a}, \end{aligned} $$

where we used in the last line that $a \le (1 - \kappa)$ for $\kappa < 2/3$, that $\bar{\Phi}(x) \le e^{-x^2/2}$ for any $x \ge 0$ and the definition of $a$ □

## 7.2 Proof of Lemma 1

For short, we write in this proof $\mathbb{P}_{\tau}$ for $P_{\theta(\tau, \mu)}$. Fix $\tau = 2$. Consider any $1/2 \le x \le n/2 - 1 - 4\Delta^{-2}$. Let $r$ denote the smallest integer larger than $4\Delta^{-2} + 2x$. Consider the test of assumptions

$$ \mathbf{H0} : \tau^* = \tau \quad \text{versus} \quad \mathbf{H1} : \tau^* = \tau + r. $$

The Likelihood-ratio test rejects **H0** when $T = r^{-1} \sum_{i=\tau}^{\tau+r-1} Y_i$ is larger than a threshold $t$. For symmetry reasons, the risk (sum of type I and type II error probabilities) of this test is minimal for $t = (\mu_2 + \mu_1)/2$. If $T > t$, define $\hat{\tau} = \tau + r$ and $\hat{\tau} = \tau$ otherwise. It holds that

$$ \mathbb{P}_{\tau}[\hat{\tau} \neq \tau] + \mathbb{P}_{\tau+r}[\hat{\tau} \neq \tau + r] = 2\bar{\Phi}[\sqrt{r\Delta}/2]. $$

Let $\hat{\tau}'$ denote any estimator of $\tau$. Let $T'$ denote the test such that $T' = 1$ iff $|\hat{\tau}' - \tau| \ge r/2$. Then

$$ \mathbb{P}_{\tau}[|\hat{\tau}' - \tau| \ge r/2] + \mathbb{P}_{\tau+r}[|\hat{\tau}' - \tau - r| \ge r/2] \ge \mathbb{P}_{\tau}[T' = 1] + \mathbb{P}_{\tau+r}[T' = 0]. $$

Let $t'$ denote the threshold such that $\mathbb{P}_{\tau}[T > t'] = \mathbb{P}_{\tau}[T' = 1]$. By Neyman-Pearson's theorem, $\mathbb{P}_{\tau+r}[T' = 0] \ge \mathbb{P}_{\tau+r}[T \le t']$, hence,

$$ \begin{aligned} \mathbb{P}_{\tau}[|\hat{\tau}' - \tau| \ge r/2] + \mathbb{P}_{\tau+r}[|\hat{\tau}' - \tau - r| \ge r/2] &\ge \mathbb{P}_{\tau}[T > t'] + \mathbb{P}_{\tau+r}[T \le t'] \\ &\ge \mathbb{P}_{\tau}[\hat{\tau} \ne \tau] + \mathbb{P}_{\tau+r}[\hat{\tau} \ne \tau + r] \\ &= 2\bar{\Phi}[\sqrt{r\Delta}/2]. \end{aligned} $$

In particular, this leads us to

$$ \inf_{\hat{\tau}} \sup_{\tau' \in \{\tau, \tau+r\}} \mathbb{P}_{\tau'} [|\hat{\tau} - \tau^*| \ge r/2] \ge \bar{\Phi}[\sqrt{r\Delta}/2]. $$

Recall the following lower bound $\bar{\Phi}(x) \ge \frac{\phi(x)}{2x}$ if $x \ge 4$. Since $\sqrt{r\Delta}/2 > 2$ There exist absolute constants $c, c' > 0$ such that

$$ \inf_{\hat{\tau}} \sup_{\tau' \in \{\tau, \tau+r\}} \mathbb{P}_{\tau'} [|\hat{\tau} - \tau^*| \ge r/2] \ge c \frac{e^{-r\Delta^2/8}}{r^{1/2}\Delta} \ge c'e^{-c'r\Delta^2}. \quad (52) $$

Combing back to the definition of $r$, we conclude the proof of Lemma 1.
## 7.3 Deviations inequality and Laws of iterated logarithms

The following results are non-asymptotic versions of the law of the iterated logarithm for sub-Gaussian random variables. We refer to [39] for proofs of (sharper versions) of Lemma 5. For the sake of completeness, a proof of these lemmas is also provided in Section A.1.

**Lemma 4.** Let $\epsilon_1, \dots, \epsilon_n$ be independent centered sub-Gaussian random variables such that $\mathbb{E}[e^{s\epsilon_i}] \le e^{s^2/2}$, for any $i \ge 1$ and any $s > 0$. Then, for any integer $d > 0$, any $\alpha > 0$ and any $x > 0$,

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

**Lemma 5.** Let $t_1 \in \{1, \dots, n\}$ and $\nu > 0$. For any $t > 0$, with probability larger than $1 - e^{-x}$, for all $t_2 \ge t_1 + 1/\nu$,

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

**Lemma 6.** For any $\alpha \in (0, 1)$ and any $x > 0$, with probability larger than $1 - 6e^{-x}$, for any $\tau \in \{2, \dots, n\}$

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

where $t_{\tau} = (1, \tau, n+1)$ and $\mathbf{N}$ is defined in (34). Here, the constant $C_{\alpha}$ can be chosen as follows

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

**Lemma 7.** Fix $\tau, \tau^* \in \{2, \dots, n\}$ and let

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

For any $x > 0$, with probability higher than $1 - 2e^{-x}$, we have, uniformly over all $\tau \le \tau^*$,

$$ \mathbf{N}(t_{\tau}) \le 4\sqrt{\log \log (e\gamma_{\tau}^{-1}) + x + 1} \quad (54) $$

## 7.4 Proof of Proposition 2

For any $t \in \mathcal{T}_3$, let

$$ \mathbf{B}(t) := \left( \frac{\sum_{i=t_2}^{t_3-1} \theta_i}{t_3 - t_2} - \frac{\sum_{i=t_1}^{t_2-1} \theta_i}{t_2 - t_1} \right) \sqrt{\frac{(t_2 - t_1)(t_3 - t_2)}{t_3 - t_1}} \, . $$

Hence, $\mathbf{E}(t) = |\mathbf{B}(t)|$ (see the definition of $\mathbf{E}(t)$ in (21)). For any $\tau$, define the triad $t_{\tau} = (1, \tau, n+1)$. Basic algebra shows that (see (34) for a definition of $\mathbf{N}(t)$)

$$ \|(\Pi_{\tau} - \Pi_0)\mathbf{Y}\|^2 = \frac{(\tau - 1)(n + 1 - \tau)}{n} \left( \frac{1}{\tau - 1} \sum_{i=1}^{\tau - 1} Y_i - \frac{1}{n + 1 - \tau} \sum_{i=\tau}^{n} Y_i \right)^2 = (\mathbf{B}(t_{\tau}) + \mathbf{N}(t_{\tau}))^2 \quad (55) $$
A consequence of this elementary remark is that

$$ \varphi_1(\tau) = \mathrm{Cr}_1(\tau, \mathbf{Y}) - \|\mathbf{Y}\|^2 + \|\mathbf{\Pi}_0 \mathbf{Y}\|^2 = -(\mathbf{B}(t_\tau) + \mathbf{N}(t_\tau))^2 + L^2 \mathrm{pen}_1(\tau) . \quad (56) $$

When $\theta \in \Theta_0$, for any $\tau$, $\mathbf{B}(t_\tau) = 0$, so $\varphi_1(\tau) = -\mathbf{N}^2(t_\tau) + L^2 \mathrm{pen}_1(\tau)$. It follows from Lemma 6 that, for any $\alpha \in (0, 1]$ and any $x > 0$, with probability $1 - 12e^{-x}$, for any $\tau \in \{2, \dots, n\}$,

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

Choosing $\alpha = L - 1$, this yields, for any $x > 0$, with probability $1 - 12e^{-x}$, for any $\tau \in \{2, \dots, n\}$,

$$ |\mathbf{N}(t_\tau)| \le L \sqrt{\mathrm{pen}_1(\tau) + 6x + C_L^*}, \quad \text{where} \quad C_L^* = \frac{2}{L} \log \left( \frac{L}{L-1} \right) - 2 \log \log(L) . $$

In particular, for all $t > 0$, with probability $1 - 12e^{-x}$,

$$ \varphi_1 \ge -L^2(6x + C_L^*) . $$

Choosing $x = \log(12/\alpha)$ proves the first statement of Proposition 2.

Assume now that $\theta \in \Theta_1$. From (56) and the inequality $(a+b)^2 \ge b^2/(L+1) - a^2/L$, valid for any $a, b \in \mathbb{R}$ and $L > 0$, we derive that

$$ \varphi_1 \le \varphi_1(\tau^*) \le -\frac{\mathbf{E}_1^2}{L} + \frac{\mathbf{N}^2(t_{\tau^*})}{L+1} + L^2 \mathrm{pen}_1(\tau^*) . \quad (57) $$

Now for any $t = (t_1, t_2, t_3) \in \mathcal{T}_3$, there exist $\alpha_{t_1}, \dots, \alpha_{t_3}$ such that $\mathbf{N}(t) = \sum_{i=t_1}^{t_3} \alpha_i \epsilon_i$ and

$$ \sum_{i=t_1}^{t_3-1} \alpha_i^2 = \frac{(t_3-t_2)(t_2-t_1)}{t_3-t_1} \left( \frac{1}{t_3-t_2} + \frac{1}{t_2-t_1} \right) = 1 . $$

Therefore, for any $s > 0$,

$$ \mathbb{E}[e^{s\mathbf{N}(t)}] = \mathbb{E}[\prod_{i=t_1}^{t_3-1} e^{s\alpha_i \epsilon_i}] = \prod_{i=t_1}^{t_3-1} \mathbb{E}[e^{s\alpha_i \epsilon_i}] \le e^{s^2 \sum_{i=t_1}^{t_3-1} \alpha_i^2/2} = e^{s^2/2} . $$

It follows that, for any $u > 0$, taking $s = u/2$, $\mathbb{P}(\mathbf{N}(t) > u) \le e^{-su+s^2/2} = e^{-u^2/2}$, so

$$ \mathbb{P}(\mathbf{N}(t_{\tau^*}) \le \sqrt{2x}) \ge 1 - e^{-x}, \quad \mathbb{P}(\mathbf{N}^2(t_{\tau^*}) \le 2x) \ge 1 - 2e^{-x} . \quad (58) $$

Plugging this inequality in (57) with $x = \log(2/\beta)$ concludes the proof of Proposition 2.

## 7.5 Proof of Proposition 3

The idea of the proof is that, with high probability, for all $\tau \in \{2, \dots, n\}$ such that $\Delta^2|\tau - \tau^*|$ is large,

$$ \mathrm{Cr}_1(\tau, \mathbf{Y}) < \mathrm{Cr}_1(\tau^*, \mathbf{Y}) . $$
On the same event, this implies that $\Delta^2|\hat{\tau} - \tau^*|$ is small. Let

$$ \gamma = \frac{(\sqrt{L} - 1)(L - 1)}{2L^{3/2}} \in (0, 1/2) . $$

Assume that $n$ is sufficiently large to ensure that $2\gamma\sqrt{n} \ge e$.

**Case 1: $\tau$ is far from $\tau^*$**. First, consider times $\tau$ satisfying

$$ \mathbf{E}^2(t_{\tau}) \leq \gamma \mathbf{E}_1^2 . \qquad (59) $$

Define $\kappa_1 = \sqrt{L} - 1$. $\kappa_2 = (1 - L^{-1})/2$, so

$$ \gamma = \frac{\kappa_1 \kappa_2}{1 + \kappa_1} = \frac{\kappa_2}{1 + \kappa_1^{-1}}. $$

From the inequality $2|xz| \le \kappa x^2 + \kappa^{-1}z^2$ valid for any $x, z \in \mathbb{R}$ and $\kappa > 0$, we derive

$$ (x+z)^2 \le (1+\kappa)x^2 + (1+\kappa^{-1}z^2), \quad (x+z)^2 \ge (1-\kappa)x^2 + (1-\kappa^{-1}z^2). $$

Hence, from (55),

$$ \begin{aligned} \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) &= -\|(\Pi_\tau - \Pi_0)\mathbf{Y}\|^2 + L\mathrm{pen}_1(\tau) + \|(\Pi_{\tau^*} - \Pi_0)\mathbf{Y}\|^2 - L\mathrm{pen}_1(\tau^*) \\ &= -(\mathbf{B}(t_\tau) + \mathbf{N}(t_\tau))^2 + L\mathrm{pen}_1(\tau) + (\mathbf{B}(t_{\tau^*}) + \mathbf{N}(t_{\tau^*}))^2 - L\mathrm{pen}_1(\tau^*) \\ &\ge -\mathbf{N}^2(t_\tau)(1 + \kappa_1) + L\mathrm{pen}_1(\tau) - \mathbf{E}^2(t_\tau)(1 + \kappa_1^{-1}) \\ &\quad + \mathbf{E}^2(t_{\tau^*})(1 - \kappa_2) + \mathbf{N}^2(t_{\tau^*})(1 - \kappa_2^{-1}) - L\mathrm{pen}_1(\tau^*) . \end{aligned} \qquad (60) $$

From Assumption (59), it follows that

$$ \begin{aligned} \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) &\ge -\mathbf{N}^2(t_\tau)(1 + \kappa_1) + L\mathrm{pen}_1(\tau) + \mathbf{E}^2(t_{\tau^*})[1 - \kappa_2 - \gamma(1 + \kappa_1^{-1})] \\ &\quad + \mathbf{N}^2(t_{\tau^*})(1 - \kappa_2^{-1}) - L\mathrm{pen}_1(\tau^*) \\ &= -\sqrt{L}\mathbf{N}^2(t_\tau) + L\mathrm{pen}_1(\tau) + \frac{1}{L}\mathbf{E}^2(t_{\tau^*}) - L\mathrm{pen}_1(\tau^*) - \mathbf{N}^2(t_{\tau^*})\frac{L+1}{L-1}. \end{aligned} \qquad (61) $$

Let us apply Lemma 6 with $\alpha = L^{1/4} - 1$. With probability larger than $1 - 12e^{-x}$, simultaneously for all $\tau \in \{2, \dots, n\}$,

$$ \mathbf{N}^2(t_\tau)L^{1/2} \le L\mathrm{pen}_1(\tau) + 6Lx + C_L^*, \qquad (62) $$

where

$$ C_L^* = L^{3/4} \log \left( \frac{L^{1/4}}{L^{1/4} - 1} \right) - L \log \log(L^{1/4}) . $$

Moreover, by (58), $\mathbf{N}^2(\tau^*) \le 2x$ with probability larger than $1 - 2e^{-x}$. Plugging this bound and (62) into (61) shows that, with probability at least $1 - 14e^{-x}$, simultaneously for all $\tau \in \{2, \dots, n\}$, such that (59) holds

$$ \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) \ge \frac{1}{L}\mathbf{E}^2(t_{\tau^*}) - L\mathrm{pen}_1(\tau^*) - 2x \left[ 3L + \frac{L+1}{L-1} \right] - C_L^* . $$

This last expression is positive as long as

$$ \mathbf{E}^2(t_{\tau^*}) > L^2 \mathrm{pen}_1(\tau^*) + 2Lx \left[ 3L + \frac{L+1}{L-1} \right] + C_L^* . \qquad (63) $$
We have proved, that with probability larger than $1 - 14e^{-x}$, we have $\mathbf{E}^2(t_{\hat{\tau}}) > \gamma \mathbf{E}_1^2$, as long as Condition (63) is satisfied.

**Case 2.** $\tau$ is neither far nor close to $\tau^*$. Now consider times $\tau$ such that

$$ \gamma < \frac{\mathbf{E}^2(t_{\tau})}{\mathbf{E}^2(t_{\tau^*})} \le \frac{1}{2}. \qquad (64) $$

Starting from (60), we derive that $\mathrm{Cr}_1(\tau, \mathbf{Y}) > \mathrm{Cr}_1(\tau^*, \mathbf{Y})$ if

$$ [\mathbf{B}(t_{\tau^*}) + \mathbf{N}(t_{\tau^*})]^2 - [\mathbf{B}(t_{\tau}) + \mathbf{N}(t_{\tau})]^2 > L\mathrm{pen}_1(\tau^*) - L\mathrm{pen}_1(\tau) . $$

In particular, the above inequality is met if

$$ |\mathbf{B}(t_{\tau^*}) + \mathbf{N}(t_{\tau^*})| - |\mathbf{B}(t_{\tau}) + \mathbf{N}(t_{\tau})| > \sqrt{L(\mathrm{pen}_1(\tau^*) - \mathrm{pen}_1(\tau))_+} . $$

By the triangular inequality, it follows that $\mathrm{Cr}_1(\tau, \mathbf{Y}) > \mathrm{Cr}_1(\tau^*, \mathbf{Y})$ if

$$ \mathbf{E}(t_{\tau^*}) - \mathbf{E}(t_{\tau}) - |\mathbf{N}(t_{\tau^*})| - |\mathbf{N}(t_{\tau})| - \sqrt{L(\mathrm{pen}_1(\tau^*) - \mathrm{pen}_1(\tau))_+} > 0. \qquad (65) $$

Assume, without loss of generality, that $\tau < \tau^*$. In this case, an important fact is that

$$ \mathbf{E}(t_{\tau}) = \mathbf{E}(t_{\tau^*}) \sqrt{\frac{n+1-\tau^*}{n+1-\tau}} \frac{\tau-1}{\tau^*-1} . $$

Thus, Condition (64) is equivalent to

$$ \gamma < \frac{n+1-\tau^*}{n+1-\tau} \frac{\tau-1}{\tau^*-1} \le \frac{1}{2}. $$

In particular, as $\tau < \tau^*$, it implies that

$$ n+1-\tau^* > \gamma(n+1-\tau), \quad \tau-1 > \gamma(\tau^*-1). \qquad (66) $$

We claim, that as long as $\tau$ satisfies (66) for some $\gamma \in (0, 1/2)$ such that $\gamma\sqrt{n} \ge \sqrt{e}$, then

$$ \mathrm{pen}_1(\tau^*) - \mathrm{pen}_1(\tau) \le c \log \log(e\gamma^{-1}), \qquad (67) $$

for some constant $c$.

*Proof of (67).* Suppose that $\tau^* < n/2 + 1$ (the case $\tau^* \ge n/2 + 1$ follows by similar arguments). In this case, as $\tau < \tau^*$, $\mathrm{pen}_1(\tau^*) = 2 \log \log(2(\tau^* \wedge n/\tau^*))$, $\mathrm{pen}_1(\tau) = 2 \log \log(2(\tau \wedge n/\tau))$. If $\tau^* > \sqrt{n}$, then $\mathrm{pen}_1(\tau^*) = 2 \log \log(2n/\tau^*)$. For $\tau > \sqrt{n}$, we have $\mathrm{pen}_1(\tau) = 2 \log \log(2n/\tau)$ and

$$ \mathrm{pen}_1(\tau^*) - \mathrm{pen}_1(\tau) = 2 \log \log(2n/\tau^*) - 2 \log \log(2n/\tau) \le 0. $$

If $\tau < \sqrt{n}$, then $\tau > \gamma\sqrt{n}$, so

$$ \mathrm{pen}_1(\tau^*) - \mathrm{pen}_1(\tau) = 2 \log \log(2n/\tau^*) - 2 \log \log(2\tau) \le 2 \log \log(n) - 2 \log \log(\gamma\sqrt{n}) \le c \log \log(e\gamma^{-1}). $$

If $\tau^* \le \sqrt{n}$, then $\tau \le \sqrt{n}$ and

$$ \mathrm{pen}_1(\tau^*) - \mathrm{pen}_1(\tau) = 2 \log \log(\tau^*) - 2 \log \log(\tau) \le 2 \log \log(1+\tau/\gamma) - 2 \log \log(\tau) \le c \log \log(e\gamma^{-1}). $$

This proves (67). □
Eq. (67) implies that Condition (65) is fulfilled if

$$ \mathbf{E}(t_{\tau^*}) - \mathbf{E}(t_{\tau}) - |\mathbf{N}(t_{\tau^*})| - |\mathbf{N}(t_{\tau})| - \sqrt{LC_{\gamma}} > 0 . \quad (68) $$

Condition (64) implies that

$$ \mathbf{E}(t_{\tau^*}) - \mathbf{E}(t_{\tau}) \geq (\sqrt{2} - 1)\mathbf{E}(t_{\tau^*}) . $$

By (58), $\mathbf{N}^2(\tau^*) \leq 2x$ with probability higher than $1 - 2e^{-x}$. Moreover, Lemma 4 applied with $d = \gamma(\tau^* - 1)$ and $\alpha = 1/\gamma - 1$ shows that, with probability at least $1 - 2e^{-x}$,

$$ \forall \tau \in [\gamma\tau^*, \tau^*], \quad Z_{1:\tau} \leq \sqrt{\frac{2(\tau - 1)x}{\gamma}} . $$

Likewise, Lemma 4 applied with $d = n + 1 - \tau^*$ and $\alpha = 1/\gamma$ shows that, with probability at least $1 - 2e^{-x}$,

$$ \forall \tau \in [n + 1 - \tau^*, (n + 1 - \tau^*)/\gamma], \quad Z_{\tau:(n+1)} \leq \sqrt{2(1 + \gamma^{-1})(n + 1 - \tau)x} . $$

Hence, with probability larger than $1 - 4e^{-x}$,

$$ |\mathbf{N}(t_{\tau})| \leq \left| \sqrt{\frac{n+1-\tau}{n(\tau-1)}} Z_{1:\tau} \right| + \left| Z_{\tau:n+1} \sqrt{\frac{\tau-1}{(n+1-\tau)n}} \right| \leq 2\sqrt{2(1+\gamma^{-1})x} . $$

It follows that Condition (68) holds with probability at least $1 - 6e^{-x}$ if

$$ (\sqrt{2} - 1)\mathbf{E}(t_{\tau^*}) - \sqrt{2x}(1 + 2\sqrt{1 + \gamma^{-1}}) + \sqrt{LC_{\gamma}} > 0 , $$

that is if

$$ \mathbf{E}(t_{\tau^*}) \geq \frac{\sqrt{2x}(1 + 2\sqrt{1 + \gamma^{-1}}) - \sqrt{LC_{\gamma}}}{\sqrt{2} - 1} . \quad (69) $$

The conclusion of Case 2 is that, if Condition (69) is fulfilled, with probability at least $1 - 6e^{-x}$, $\mathbf{E}^2(t_{\tau^*}) \geq \mathbf{E}(t_{\tau^*})^2/2$ or $\mathbf{E}^2(t_{\tau^*}) < \gamma \mathbf{E}(t_{\tau^*})^2$.

**Case 3:** Let $\tau \in \{2, \dots, n\}$ be such that $\mathbf{E}^2(t_{\tau}) > \mathbf{E}^2(t_{\tau^*})/2$. Assume moreover, without loss of generality, that $\tau < \tau^*$. Since $\mathbf{E}(t_{\tau}) = \mathbf{E}(t_{\tau^*})\sqrt{\frac{\tau-1}{\tau^*-1}} \cdot \frac{n+1-\tau^*}{n+1-\tau}$, this implies that $\frac{\tau-1}{\tau^*-1} \cdot \frac{n+1-\tau^*}{n+1-\tau} \geq 1/2$.

We now use a slightly different approach than in the previous cases. Define the orthogonal projector $\Pi_{\tau, \tau^*}$ onto the space of vectors that are constant on $[1, \tau - 1]$, $[\tau, \tau^* - 1]$ and $[\tau^*, n]$. Note that, if $\mathbf{1}_{a:b}$ denote the vector with coordinates 1 for all $i \in \{a, \dots, b - 1\}$ and null otherwise, then, for any $\tau < \tau^*$ and any vector $\mathbf{a} \in \mathbb{R}^n$, we have

$$ \Pi_{\tau} \mathbf{a} = \left( \frac{1}{\tau - 1} \sum_{i=1}^{\tau - 1} a_i \right) \mathbf{1}_{1:\tau} + \left( \frac{1}{n + 1 - \tau} \sum_{i=\tau}^{n} a_i \right) \mathbf{1}_{\tau:n+1} , $$

$$ \Pi_{\tau, \tau^*} \mathbf{a} = \left( \frac{1}{\tau - 1} \sum_{i=1}^{\tau - 1} a_i \right) \mathbf{1}_{1:\tau} + \left( \frac{1}{\tau^* - \tau} \sum_{i=\tau}^{\tau^*-1} a_i \right) \mathbf{1}_{\tau:\tau^*} + \left( \frac{1}{n + 1 - \tau^*} \sum_{i=\tau^*}^{n} a_i \right) \mathbf{1}_{\tau^*:n+1} . $$
Hence,

$$ (\mathbf{\Pi}_{\tau} - \mathbf{\Pi}_{\tau, \tau^*})\mathbf{a} = \left( \frac{1}{n+1-\tau} \sum_{i=\tau}^{n} a_i - \frac{1}{\tau^* - \tau} \sum_{i=\tau}^{\tau^*-1} a_i \right) \mathbf{1}_{\tau:\tau^*} + \left( \frac{1}{n+1-\tau} \sum_{i=\tau}^{n} a_i - \frac{1}{n+1-\tau^*} \sum_{i=\tau^*}^{n} a_i \right) \mathbf{1}_{\tau^*:n+1} \\ = \left( \frac{1}{n+1-\tau^*} \sum_{i=\tau^*}^{n} a_i - \frac{1}{\tau^* - \tau} \sum_{i=\tau}^{\tau^*-1} a_i \right) \frac{n+1-\tau^*}{n+1-\tau} \mathbf{1}_{\tau:\tau^*} + \left( \frac{1}{\tau^* - \tau} \sum_{i=\tau}^{\tau^*-1} a_i - \frac{1}{n+1-\tau^*} \sum_{i=\tau^*}^{n} a_i \right) \frac{\tau^* - \tau}{n+1-\tau} \mathbf{1}_{\tau^*:n+1} . $$

Therefore, by orthogonality of the vectors $\mathbf{1}_{\tau^*:n+1}$ and $\mathbf{1}_{\tau:\tau^*}$,

$$ \| (\mathbf{\Pi}_{\tau} - \mathbf{\Pi}_{\tau, \tau^*}) \mathbf{a} \|^2 = \left( \frac{1}{\tau^* - \tau} \sum_{i=\tau}^{\tau^*-1} a_i - \frac{1}{n+1-\tau^*} \sum_{i=\tau^*}^{n} a_i \right)^2 \left( \frac{(n+1-\tau^*)^2(\tau^* - \tau)}{(n+1-\tau)^2} + \frac{(\tau^* - \tau)^2(n+1-\tau^*)}{(n+1-\tau)^2} \right) \\ = \left( \frac{1}{\tau^* - \tau} \sum_{i=\tau}^{\tau^*-1} a_i - \frac{1}{n+1-\tau^*} \sum_{i=\tau^*}^{n} a_i \right)^2 \frac{(n+1-\tau^*)(\tau^* - \tau)}{n+1-\tau} . \quad (70) $$

Likewise, one can show that

$$ \| (\mathbf{\Pi}_{\tau^*} - \mathbf{\Pi}_{\tau, \tau^*}) \mathbf{a} \|^2 = \left( \frac{1}{\tau^* - \tau} \sum_{i=\tau}^{\tau^*-1} a_i - \frac{1}{\tau - 1} \sum_{i=1}^{\tau} a_i \right)^2 \frac{(\tau - 1)(\tau^* - \tau)}{\tau^* - 1} . \quad (71) $$

By Pythagoras relationship, we have

$$ \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) = \|(\mathbf{\Pi}_{\tau, \tau^*} - \mathbf{\Pi}_{\tau})\mathbf{Y}\|^2 - \|(\mathbf{\Pi}_{\tau, \tau^*} - \mathbf{\Pi}_{\tau^*})\mathbf{Y}\|^2 + L(\mathrm{pen}_1(\tau) - \mathrm{pen}_1(\tau^*)) . $$

From (70) and (71), it follows that

$$ \begin{aligned} \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) &= \frac{(\tau^* - \tau)(n+1-\tau^*)}{n+1-\tau} \left[ \frac{\sum_{i=\tau^*}^{n} Y_i}{n+1-\tau^*} - \frac{\sum_{i=\tau}^{\tau^*-1} Y_i}{\tau^* - \tau} \right]^2 + \frac{(\tau^* - \tau)(\tau-1)}{\tau^* - 1} \left[ \frac{\sum_{i=\tau}^{\tau^*} Y_i}{\tau^* - \tau} - \frac{\sum_{i=1}^{\tau^*-1} Y_i}{\tau - 1} \right]^2 \\ &\quad + L(\mathrm{pen}_1(\tau) - \mathrm{pen}_1(\tau^*)) \\ &= \frac{(\tau^* - \tau)(n+1-\tau^*)}{n+1-\tau} \left[ \frac{Z_{\tau^*:n+1}}{n+1-\tau^*} - \frac{Z_{\tau:\tau^*}}{\tau^* - \tau} + \Delta \right]^2 - \frac{(\tau^* - \tau)(\tau-1)}{\tau^* - 1} \left[ \frac{Z_{\tau:\tau^*}}{\tau^* - \tau} - \frac{Z_{1:\tau^*} - Z_{\tau:\tau^*}}{\tau - 1} \right]^2 \\ &\quad + L(\mathrm{pen}_1(\tau) - \mathrm{pen}_1(\tau^*)) . \end{aligned} $$

From the inequalities $a^2/2 - b^2 \le (a+b)^2 \le 2(a^2+b^2)$, it follows

$$ \begin{aligned} \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) \ge \frac{(\tau^* - \tau)(n+1-\tau^*)}{n+1-\tau} \left( \frac{\Delta^2}{2} - \frac{4Z_{\tau:\tau^*}^2}{(\tau^* - \tau)^2} - \frac{4Z_{\tau^*:n+1}^2}{(n+1-\tau^*)^2} \right) \\ - \frac{2(\tau^* - \tau)(\tau-1)}{\tau^* - 1} \left( \frac{Z_{1:\tau^*}^2}{(\tau-1)^2} + \frac{Z_{\tau:\tau^*}^2(\tau^*-1)^2}{[(\tau-1)(\tau^* - \tau)]^2} \right) . \end{aligned} $$
Using repeatedly $\frac{\tau-1}{\tau^*-1} \cdot \frac{n+1-\tau^*}{n+1-\tau} \ge 1/2$ and $\tau < \tau^*$, this yields

$$ \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) \ge \frac{\Delta^2(\tau^* - \tau)}{4} - 8 \frac{Z_{\tau:\tau^*}^2}{\tau^* - \tau} - 4(\tau^* - \tau) \frac{Z_{\tau^*:n+1}^2}{(n+1-\tau^*)^2} - 2(\tau^* - \tau) \frac{Z_{1:\tau^*}^2}{(\tau-1)^2} + L(\mathrm{pen}_1(\tau) - \mathrm{pen}_1(\tau^*)) . $$

By (67), there exists an absolute constant $C$ such that $\mathrm{pen}_1(\tau) - \mathrm{pen}_1(\tau^*) \le C$. It follows that

$$ \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) \ge \frac{\Delta^2(\tau^* - \tau)}{4} - 8 \frac{Z_{\tau:\tau^*}^2}{\tau^* - \tau} - 4(\tau^* - \tau) \left( \frac{Z_{\tau^*:n+1}^2}{(n+1-\tau^*)^2} + \frac{Z_{1:\tau^*}^2}{(\tau-1)^2} \right) - 2C . $$

The proof of (58) shows that, on an event of probability at least $1 - 4e^{-x}$, both $|Z_{\tau^*:n+1}| \le \sqrt{2(n+1-\tau^*)x}$ and $|Z_{1:\tau^*}| \le \sqrt{2(\tau^*-1)x}$ simultaneously. By Lemma 5, with probability larger than $1 - 2e^{-x}$,

$$ |Z_{\tau:\tau^*}| \mathbf{1}_{\{(\tau^*-\tau)\Delta^2 \ge 1\}} \le 2\sqrt{2(\tau^*-\tau)(\log \log[3\Delta^2(\tau^*-\tau)] + x + 1)} $$

Plugging these deviations inequalities in the above bound, we conclude that for, $(\tau^* - \tau)\Delta^2 \ge 1$,

$$ \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) \ge (\tau^* - \tau) \left[ \frac{\Delta^2}{4} - 16x \frac{n}{(n+1-\tau^*)(\tau^*-1)} \right] - 32(\log \log[3\Delta^2(\tau^*-\tau)] + x + 1) - 2C $$

Restricting our attention to $x \le \mathbf{E}_1^2/128$ (which is possible by taking $c_L$ large enough in the statement of the proposition), this simplifies in

$$ \mathrm{Cr}_1(\tau, \mathbf{Y}) - \mathrm{Cr}_1(\tau^*, \mathbf{Y}) \ge \frac{\Delta^2(\tau^* - \tau)}{8} - 32(\log \log[3\Delta^2(\tau^* - \tau)] + x + 1) - 2C, $$

which is positive provided that $(\tau^* - \tau) \ge C \frac{1\sqrt{x}}{\Delta^2}$. Hence, there exists an absolute constant $C > 0$ such that, for any $x \le \mathbf{E}_1^2/32$, with probability $1 - 12e^{-x}$, any $\tau$ such that $\mathbf{E}^2(t_\tau) > \mathbf{E}^2(t_{\tau^*})/2$ and $\mathrm{Cr}_1(\tau, \mathbf{Y}) \le \mathrm{Cr}_1(\tau^*, \mathbf{Y})$ satisfies $|\tau^* - \tau| \le C \frac{1\sqrt{x}}{\Delta^2}$.

Gathering the conclusions of Cases 1, 2 and 3, we conclude that there exist constants $C > 0$ (absolute) and $C_L$ such that, with probability larger than $1 - 32e^{-x}$, if $\mathbf{E}_1^2 \ge L^2\mathrm{pen}_1(\tau^*) + C_L(1+x)$, then,

$$ |\hat{\tau} - \tau^*| \le C \frac{1 \vee x}{\Delta^2} . $$

## 7.6 Proof of Proposition 4

All along the proof, the change-point energy is called small if

$$ \mathbf{E}_1^2 \le L^2 \mathrm{pen}_1(\tau^*) + \underline{c}_L'' \log \left( \frac{e}{\alpha} \right) . \qquad (72) $$

In this expression, the constant $\underline{c}_L''$ is chosen to ensure that, when (72) does not hold, Proposition 3 applies and $|\hat{\tau} - \tau^*| \le C \log(1/\alpha)/\Delta^2$ with probability higher than $1 - \alpha/2$.

Proposition 4 follows from the three following claims.

**Claim 1:** If the change-point energy is small, with probability higher than $1 - \alpha$, the test $\varphi_{IC}$ does not reject the null. When $\varphi_{IC}$ does not reject the null $I_{\hat{\tau}} = \{2, \dots, n\}$, so $\tau^* \in I_{\hat{\tau}}$. Hence, if the change-point energy is small, with probability higher than $1 - \alpha$, $\tau^* \in I_{\hat{\tau}}$.
**Claim 2:** If the change-point energy is not small, the confidence interval defined by (19) contains $\tau^*$ with probability larger than $1 - \alpha$.

**Claim 3:** If (20) is satisfied, with probability larger than $1 - \alpha$, $\varphi_{IC}$ rejects the null and $|\hat{\Delta}| \ge |\Delta|/4$. To conclude the proof, it remains to prove each claim.

**Proof of Claim 1.** We prove that, with probability higher than $1 - \alpha$, for all $\tau$, $\varphi_{IC}(\tau) \ge -\underline{c}_{L,\kappa} \log(\frac{e}{\alpha})$. As in the proof of Proposition 3, we distinguish the cases where $\tau$ is far and close from $\tau^*$.

**Case 1:** Fix $\gamma_0 = (\text{pen}_1(\tau^*))^{-1} \wedge 1$ and consider $\tau$ such that $\mathbf{E}^2(t_\tau) \le \gamma_0 \mathbf{E}_1^2$. From (55) and Lemma 6 applied with $\alpha = L - 1$, with probability larger than $1 - \alpha/2$,

$$ \begin{aligned} \varphi_{IC}(\tau) &\ge -(1 + \kappa^{-1})\mathbf{E}^2(t_\tau) - (1 + \kappa)\mathbf{N}^2(t_\tau) + L^2(1 + \kappa)\text{pen}_1(\tau) \\ &\ge -(1 + \kappa^{-1})\gamma_0\mathbf{E}_1^2 - (1 + \kappa)L^2[6\log(1/\alpha) + C_L] \\ &\ge -(1 + \kappa^{-1})\left[L^2 + \underline{c}_L'' \log(\frac{e}{\alpha})\right] - (1 + \kappa)L^2[6\log(1/\alpha) + C_L] . \end{aligned} $$

We used (72) in the third line. There exists a constant $\underline{c}_{L,\kappa}$ such that this last lower bound is smaller than $-\underline{c}_{L,\kappa} \log(\frac{e}{\alpha})$. In conclusion, we have proved that, with probability higher than $1 - \alpha/2$, one has $\varphi_{IC}(\tau) \ge -\underline{c}_{L,\kappa} \log(\frac{e}{\alpha})$ simultaneously for all $\tau$ satisfying $\mathbf{E}^2(t_\tau) \le \gamma_0 \mathbf{E}_1^2$.

**Case 2:** Now consider $\tau$ satisfying $\mathbf{E}^2(t_\tau) \ge \gamma_0 \mathbf{E}_1^2$. We assume that $\tau \le \tau^*$, the case $\tau > \tau^*$ is handled similarly. Recall the basic inequality

$$ \gamma_{\tau} = \frac{\mathbf{E}^2(t_{\tau})}{\mathbf{E}_1^2} = \frac{(\tau - 1)(n + 1 - \tau^*)}{(\tau^* - 1)(n + 1 - \tau)} . $$

With this notation,

$$ \begin{aligned} \varphi_{IC}(\tau) &\ge -(1 + \kappa)\mathbf{E}^2(t_\tau) - (1 + \kappa^{-1})\mathbf{N}^2(t_\tau) + (1 + \kappa)L^2\text{pen}_1(\tau) \\ &\ge -(1 + \kappa)\gamma_\tau\mathbf{E}_1^2 - (1 + \kappa^{-1})\mathbf{N}^2(t_\tau) + (1 + \kappa)L^2\text{pen}_1(\tau) . \end{aligned} $$

We need uniform controls of both $\mathbf{N}^2(t_\tau)$ and $\text{pen}_1(\tau)$. By Lemma 7, with probability higher than $1 - \alpha/4$, we have

$$ \varphi_{IC}(\tau) \ge -(1 + \kappa)\gamma_{\tau}\mathbf{E}_1^2 - (1 + \kappa^{-1})16\left[\log\log(e\gamma_{\tau}^{-1}) + \log\left(\frac{8}{\alpha}\right) + 1\right] + (1 + \kappa)L^2\text{pen}_1(\tau) . \quad (73) $$

Assume first that $\gamma_\tau \ge 1/2$. In this case, by (67), there exists an absolute constant $C$ such that

$$ \text{pen}_1(\tau) \ge \text{pen}_1(\tau^*) - C . $$

Therefore, (73) implies that

$$ \varphi_{IC}(\tau) \ge (1 + \kappa) [-\mathbf{E}_1^2 + L^2(\text{pen}_1(\tau^*) - C)] - (1 + \kappa^{-1})16 \left[0.6 + \log\left(\frac{8}{\alpha}\right) + 1\right] . $$

As the change-point energy is small, this implies that

$$ \varphi_{IC}(\tau) \ge -(1 + \kappa) \left[ \underline{c}_L'' \log(\frac{e}{\alpha}) + C L^2 \right] - (1 + \kappa^{-1})16 \left[ 1.6 + \log\left(\frac{8}{\alpha}\right) \right] . $$
This last lower bound is larger than $-\underline{\mathcal{L}}_{L,\kappa} \log(\frac{\epsilon}{\alpha})$ if we choose $\underline{\mathcal{L}}_{L,\kappa}$ large enough.
Assume now that $\gamma_{\tau} < 1/2$. By (67), there exists an absolute constant $C$ such that

$$\mathrm{pen}_1(\tau) - \mathrm{pen}_1(\tau^*) \geq -C \log \log(e\gamma_0^{-1}).$$

Therefore, (73) implies that, with probability higher than $1 - \alpha/4$

$$\begin{align*}
\varphi_{IC}(\tau) &\ge (1+\kappa) \left[ -\frac{1}{2} \mathbf{E}_1^2 + L^2(\mathrm{pen}_1(\tau^*) - C \log \log(e\gamma_0^{-1})) \right] \\
&\quad -16(1+\kappa^{-1}) \left[ \log \log(2e\gamma_0^{-1}) + 1 + \log\left(\frac{8}{\alpha}\right) \right] \\
&\ge (1+\kappa) \left[ -\underline{\mathcal{L}}_L'' \log(\frac{e}{\alpha}) + \frac{L^2}{2} \mathrm{pen}_1(\tau^*) \right] \\
&\quad -C_{L,\kappa} \left[ \log \log [2e(\mathrm{pen}_1(\tau^*) \lor 1)] + 1 + \log\left(\frac{e}{\alpha}\right) \right].
\end{align*}$$

It remains to say that, for any positive $a$ and $b$, there exists $C_{a,b}$ such that $ax-b\log\log(2ex) \ge C_{a,b}$. This implies that $\varphi_{IC}(\tau) \ge -\underline{\mathcal{L}}_{L,\kappa} \log(\frac{\epsilon}{\alpha})$ if we choose $\underline{\mathcal{L}}_{L,\kappa}$ large enough.

Arguing similarly for $\tau \ge \tau^*$ and combining this result with Case 1, we have proved that the test $\varphi_{IC}$ does not reject the null with probability higher than $1 - \alpha$, when $\mathbf{E}_1$ is small (72).

**Proof of Claim 2:** Assume that $\mathbf{E}_1$ is large so (72) does not hold. We have to prove that there exists an absolute constant $C$ such that, with probability higher than $1 - \alpha$, $\tau^*$ belongs to the interval

$$[\hat{\tau} - C \log(\frac{\epsilon}{\alpha}) |\hat{\Delta}|^{-2}; \hat{\tau} + C \log(\frac{\epsilon}{\alpha}) |\hat{\Delta}|^{-2}] .$$

Since (72) does not hold, Proposition 3 implies that there exists an absolute constant $C$ such that, for $n$ large enough, with probability larger than $1 - \alpha/2$,

$$|\hat{\tau} - \tau^*| \le C \frac{\log(e/\alpha)}{\Delta^2} \quad \text{and} \quad \gamma_{\hat{\tau}} \ge 1/2. \qquad (74)$$

From Lemma 7, with probability larger than $1 - \alpha/4$, we have for all $\tau < \tau^*$ such that $\gamma_{\tau} \ge 1/2$

$$|\mathbf{N}(t_{\tau})| \le 4\sqrt{\log(8/\alpha) + 1.6} =: u_{\alpha}$$

By symmetry, the same bound holds for all $\tau > \tau^*$ such that $\gamma_{\tau} \ge 1/2$. In view of (74), it therefore holds for $\mathbf{N}(t_{\hat{\tau}})$ with probability larger than $1 - \alpha/2$. Since

$$\hat{\Delta} := \frac{\sum_{i=\hat{\tau}}^{n+1-\hat{\tau}} Y_i}{n+1-\hat{\tau}} - \frac{\sum_{i=1}^{\hat{\tau}-1} Y_i}{\hat{\tau}-1} = \Delta \left[ \frac{\tau^* - 1}{\hat{\tau}-1} \wedge \frac{n+1-\tau^*}{n+1-\hat{\tau}} \right] + \sqrt{\frac{n}{(\hat{\tau}-1)(n+1-\hat{\tau})}} \mathbf{N}(t_{\hat{\tau}}),$$

we deduce that, with probability larger than $1 - \alpha/2$,

$$\frac{|\Delta|}{2} - \sqrt{\frac{n}{(\hat{\tau}-1)(n+1-\hat{\tau})}} u_{\alpha} \le |\hat{\Delta}| \le |\Delta| + \sqrt{\frac{n}{(\hat{\tau}-1)(n+1-\hat{\tau})}} u_{\alpha}.$$

Since $\gamma_{\hat{\tau}} \ge 1/2$, we have $\sqrt{\frac{n}{(\hat{\tau}-1)(n+1-\hat{\tau})}} \le \sqrt{2\frac{n}{(\tau^*-1)(n+1-\tau^*)}}$ and the previous bounds imply that

$$\left[ \frac{1}{2} - \frac{\sqrt{2u_{\alpha}}}{\mathbf{E}_1} \right] \le \frac{|\hat{\Delta}|}{\Delta} \le \left[ 1 + \frac{\sqrt{2u_{\alpha}}}{\mathbf{E}_1} \right]$$
If $\zeta_L''$ in (72) is sufficiently large, this implies that

$$ \frac{|\hat{\Delta}|}{\Delta} \in [1/4, 5/4] . \qquad (75) $$

Together with (74), this shows that $\tau^*$ belongs to the interval (19) with probability higher than $1 - \alpha$, provided that the constant $\zeta$ is large enough.

**Proof of Claim 3.** This last claim is quite straightforward. If $E_1$ is large enough, then $\varphi_{IC}(\tau^*)$ is small enough and the test is rejected with probability higher than $1 - \alpha/2$. On this event, $IC_{\hat{\tau}}$ is defined as in (19). Arguing as in Claim 2, we derive as in (75) that $|\hat{\Delta}| \ge |\Delta|/4$. The result follows.

# 8 Proofs for multiple change-points

## 8.1 Proofs of the lower bounds

*Proof of Proposition 5.* Let $r$ in $\{1, \dots, \lfloor n/4 \rfloor\}$, $\delta \le \sqrt{2(1-\xi)\log(n/r)/r}$, and

$$ \mathcal{T} = \left\{ \lfloor n/4 \rfloor + kr + 1, k \in \left\{ 0, \dots, \left\lfloor \frac{3n/4}{r} - \lfloor n/4 \rfloor - 1 \right\rfloor - 1 \right\} \right\}. $$

For $\tau$ in $\mathcal{T}$, define $\theta(\tau)$ in $\Theta_2$ by $\theta_i(\tau) = \delta \mathbf{1}_{i \in [\tau, \tau+r-1]}$. We aim at proving that, for any test $\mathcal{T}$,

$$ \mathbb{P}_0[\mathcal{T} = 1] + \max_{\tau \in \mathcal{T}} \mathbb{P}_{\theta(\tau)}[\mathcal{T} = 0] \ge 1 - c_n, \qquad (76) $$

with $c_n = c(r/n)^{c'\xi}$ for some positive numerical constants $c$ and $c'$. Note that (76) implies the result of the proposition. As in the proof of Proposition 1 and with the same notation, we use Le Cam's approach and therefore define the mixture probability $\mathbf{P} = |\mathcal{T}|^{-1} \sum_{\tau \in \mathcal{T}} \mathbb{P}_{\tau}$. Then, one knows that Inequality (76) holds for all test $\mathcal{T}$ if $\|\mathbb{P}_0 - \mathbf{P}\|_{TV}$ is less or equal to $c_n$.

Let us introducing for any $\tau$ in $\mathcal{T}$, the event $\Gamma_{\tau} = \{\langle \mathbf{Y}, \theta(\tau) \rangle \le \|\theta(\tau)\|^2 + \|\theta(\tau)\|\sqrt{2a}\}, (a > 0)$ such that $\mathbb{P}_{\tau}[\Gamma_{\tau}^c] = \bar{\Phi}(\sqrt{2a}) \le e^{-a}$.

Now, define the thresholded likelihood $\tilde{L}_{\tau} = L_{\tau} \mathbf{1}_{\Gamma_{\tau}}$ and $\tilde{L} = |\mathcal{T}|^{-1} \sum_{\tau \in \mathcal{T}} \tilde{L}_{\tau}$. We have $\tilde{L} \le L$ and

$$ \mathbb{E}_0[L - \tilde{L}] = \frac{1}{|\mathcal{T}|} \sum_{\tau \in \mathcal{T}} \mathbb{E}_0[L_{\tau} \mathbf{1}_{\Gamma_{\tau}^c}] = \frac{1}{|\mathcal{T}|} \sum_{\tau \in \mathcal{T}} \mathbb{P}_{\tau}[\Gamma_{\tau}^c] \le e^{-a}. $$

We first upper bound $\|\mathbb{P}_0 - \mathbf{P}\|_{TV}$ by

$$ \| \mathbb{P}_0 - \mathbf{P} \|_{TV} = \frac{1}{2} \mathbb{E}_0[|L - 1|] \le \frac{3}{2} [\mathbb{E}_0[L - \tilde{L}]]^{1/2} + \frac{1}{2} [\mathbb{E}_0[\tilde{L}^2] - 1]^{1/2} \le \frac{3}{2} e^{-a/2} + \frac{1}{2} [\mathbb{E}_0[\tilde{L}^2] - 1]^{1/2} . $$

Now, remark that:

$$ \mathbb{E}_0[\tilde{L}^2 - 1] = \frac{1}{|\mathcal{T}|^2} \sum_{\tau, \tau' \in \mathcal{T}} [\mathbb{E}_0[L_{\tau} L_{\tau'} \mathbf{1}_{\Gamma_{\tau}} \mathbf{1}_{\Gamma_{\tau'}}] - 1] . $$

Recall that $L_{\tau} = \exp\left[\sum_{i=\tau}^{\tau+r-1} Y_i \tau - \frac{r\delta^2}{2}\right]$. Hence, $L_{\tau}$ is independent of $L_{\tau'}$ for $\tau \ne \tau'$. This implies that for $\tau \ne \tau'$,

$$ \mathbb{E}_0[L_{\tau} L_{\tau'} \mathbf{1}_{\Gamma_{\tau}} \mathbf{1}_{\Gamma_{\tau'}}] \le \mathbb{E}_0[L_{\tau}] \mathbb{E}_0[L_{\tau'}] = 1. $$
As a consequence,

$$ \mathbb{E}_0[\tilde{L}^2 - 1] \le \frac{1}{|\mathcal{T}|^2} \sum_{\tau \in \mathcal{T}} [\mathbb{E}_0[\tilde{L}_\tau^2] - 1] \le \frac{1}{|\mathcal{T}|^2} \sum_{\tau \in \mathcal{T}} \mathbb{E}_0 \left[ \exp \left[ \sum_{i=\tau}^{\tau+r-1} 2Y_i \delta - r\delta^2 \right] \mathbf{1}_{\sum_{i=\tau}^{\tau+r-1} Y_i \le \sqrt{2ra} + r\delta} \right]. $$

Introducing $Z = r^{-1/2} \sum_{i=\tau}^{\tau+r-1} Y_i$ which follows a standard Gaussian distribution under $\mathbb{P}_0$,

$$ \begin{aligned} \mathbb{E}_0[\tilde{L}^2 - 1] & \le \frac{1}{|\mathcal{T}|} \mathbb{E}_0 \left[ e^{2Zr^{1/2}\delta - r\delta^2} \mathbf{1}_{Z \le \sqrt{2a} + r^{1/2}\delta} \right] = \frac{1}{|\mathcal{T}|} e^{r\delta^2} \int_{-\infty}^{\sqrt{2a} + r^{1/2}\delta} \phi(z - 2r^{1/2}\delta) dz \\ & \le \frac{1}{|\mathcal{T}|} e^{r\delta^2} \bar{\Phi}(r^{1/2}\delta - \sqrt{2a}) \\ & \le \frac{1}{|\mathcal{T}|} e^{r\delta^2/2 - a + \delta\sqrt{2ar}}, \end{aligned} $$

provided that $a \le r\delta^2/2$. Gathering everything, we have proved that

$$ \| \mathbb{P}_0 - \mathbf{P} \|_{TV} \le \frac{3}{2} e^{-a/2} + \frac{1}{2|\mathcal{T}|^{1/2}} e^{r\delta^2/4 - a/2 + \sqrt{ar/2}\delta} . $$

With $\delta = \sqrt{2(1-\xi)\log(n/r)/r}$, $n \ge 8$ and $r \le n/4$, then $|\mathcal{T}| \ge n/(8r)$. Taking $a = b\log(n/r)$ with $b \le (1-\xi)$, this leads us to

$$ \| \mathbb{P}_0 - \mathbf{P} \|_{TV} \le \frac{3}{2} \left(\frac{n}{r}\right)^{-b/2} + \sqrt{2} \left(\frac{n}{r}\right)^{-\xi/2 - b/2 + \sqrt{b(1-\xi)}} . $$

Take $b = [\xi^2/[2(1-\xi)]] \wedge (1-\xi)$ so that $\sqrt{b(1-\xi)} \le \xi/2$ for any $\xi \in (0,1)$, which leads us to $\|\mathbb{P}_0 - \mathbf{P}\|_{TV} \le 3(n/r)^{-b/2}$. Finally, it suffices to observe that there exists $c' > 0$ such that $b \ge c'\xi^2$ for any $\xi$ in $(0,1)$. $\square$

**Proof of Proposition 6.** Let us first prove the lower bound (25). As $\tau_k^* \in I_k$, both $\mu_{k-1}$ and $\mu_k$ are known to the statistician and as all other change-points do not belong to $I_k$, the statistic $(Y_i)$, $i \in I_k$ is sufficient for estimating of $\tau_k^*$. As a consequence, estimating $\tau^*$ boils downs to 6 a one-change-point estimation problem on $(Y_i)_{i \in I_k}$ and the results follow from Lemma 1.

For any probability distribution $\pi$ on $\Theta[\mathcal{I}, \mu]$ and any estimator $\hat{\tau}$ of $\tau^*$,

$$ \sup_{\theta \in \Theta[\mathcal{I}, \mu]} \mathbb{E}_{\theta} \left[ \sum_{k=1}^{K} |\hat{\tau}_k - \tau_k^*| \right] \ge \int \mathbb{E}_{\theta} \left[ \sum_{k=1}^{K} |\hat{\tau}_k - \tau_k^*| \right] \pi(d\theta) . $$

To define a probability distribution $\pi$, fix first a sequence $(r_k)_{k \in \{1, \dots, K\}}$ such that all $|r_k| \le |I_k| - 1$ and, for all $k \in \{1, \dots, K\}$, fix

$$ z_{k,0} = x_k + 1, \quad z_{k,1} = x_k + 1 + r_k . $$

Let $\mathcal{U}$ denote the uniform distribution over $\{0, 1\}^K$ and, for any $\mathbf{u} \in \{0, 1\}^K$, let $\theta_{\mathbf{u}} \in \Theta[\mathcal{I}, \mu]$ be the vector such that, for all $k \in \{1, \dots, K\}$, $\tau_k^* = z_{k, \mathbf{u}_k}$. Let $\pi$ denote the distribution of $\theta_{\mathbf{U}}$, where $\mathbf{U} \sim \mathcal{U}$. As all $\theta_{\mathbf{u}} \in \Theta[\mathcal{I}, \mu]$, the coordinates $U_1, \dots, U_K$ of $\mathbf{U}$ are independent conditionally on $\mathbf{Y}$.

First, consider the Wasserstein loss. The Bayes risk is achieved by the MAP estimator $\hat{u}$. As a consequence,

$$ \begin{aligned} \inf_{\hat{\tau} \in \mathbb{N}^K} \sup_{\theta \in \Theta[(I_l), \mu]} \mathbb{E}_{\theta} \left[ \sum_{k=1}^{K} |\hat{\tau}_k - \tau_k^*| \right] & \ge \sum_{k=1}^{K} r_k \mathbb{P}[\hat{u}_k \ne u_k] \\ & \ge \sum_{k=1}^{K} r_k \bar{\Phi}[r_k^{1/2} |\Delta_k|/2] , \end{aligned} $$
where we argued as in (25). Taking $r_k = 1$ if $|\Delta_k| \ge 2$ and $r_k = \lfloor \frac{4}{\Delta_k^2} \rfloor$ for $|\Delta_k| \le 2$ leads to (26).

Turning to (27), we restrict ourselves to the case where all $r_k$'s are equal to some $0 < r < \min_k |I_k|/2$. Again, one easily checks that

$$ \inf_{\hat{\tau} \in \mathbb{N}^K} \sup_{\theta \in \Theta[(I_l), \mu]} \mathbb{E}_{\theta} [d_H(\hat{\tau}; \tau^*)] \ge \frac{r}{2} \mathbb{P}[\hat{u} \ne u] = \frac{r}{2} \left[ 1 - (1 - \bar{\Phi}[r^{1/2} |\Delta|/2])^K \right]. $$

If $\Delta^2 \ge 4$, we simply take $r = 1$, which, together with $(1-x)^K \ge 1 - Kx$, leads us to

$$ \inf_{\hat{\tau} \in \mathbb{N}^K} \sup_{\theta \in \Theta[(I_l), \mu]} \mathbb{E}_{\theta} [d_H(\hat{\tau}; \tau^*)] \ge \frac{K}{2} \bar{\Phi}(|\Delta|/2) \ge c \frac{K e^{-\Delta^2/8}}{|\Delta|}, $$

since $\bar{\Phi}(x) \ge cx^{-1}e^{-x^2/2}$ for $x \ge 1/2$ by integration by part. If $\Delta^2 \le 4$, we take $r = \lfloor \frac{4}{\Delta^2} (\bar{\Phi}^{-1}[1/(4K)])^2 \rfloor \ge 1$. We have $r < \min_k |I_k|/2$ since $|I_k| \ge c \log(K)/\Delta^2$ for a suitable constant $c > 0$. Hence,

$$ \inf_{\hat{\tau} \in \mathbb{N}^K} \sup_{\theta \in \Theta[(I_l), \mu]} \mathbb{E}_{\theta} [d_H(\hat{\tau}; \tau^*)] \ge r \left(1 - \left(1 - \frac{1}{4K}\right)^K\right) \ge c' \frac{\log(K)}{\Delta^2}, $$

and the result follows.

□

## 8.2 Further Notation and preliminary Lemmas for Multiple Jumps

The purpose of this subsection is to introduce relevant quantities for evaluating the criteria differences $\text{Cr}_0(\tau, Y) - \text{Cr}_0(\tau', Y)$ for change-point vectors $\tau$ and $\tau'$ that differ at exactly one change-point. For any $k = 1, \dots, K+1$, we write for short $\delta_k^* = \tau_k^* - \tau_{k-1}^*$. For any $q > 0$, we define the function $\psi_q$, for any $\delta = (\delta_1, \delta_2) \in \{1, \dots, n\}^2$,

$$ \psi_q[\delta] := \sqrt{2 \log \left( \frac{n(\delta_1 + \delta_2)}{\delta_1 \delta_2} \right) + q}. \qquad (77) $$

Given $t \in \mathcal{T}_3$, we write define $\Delta_t$ as the difference of means

$$ \Delta_t := \frac{1}{\tau_2 - \tau_1} \sum_{i=\tau_1}^{\tau_2 - 1} \theta_i - \frac{1}{\tau_3 - \tau_2} \sum_{i=\tau_2}^{\tau_3 - 1} \theta_i, \qquad (78) $$

so that the energy satisfies $\mathbb{E}[t] := \sqrt{\frac{(\tau_3 - \tau_2)(\tau_2 - \tau_1)}{\tau_3 - \tau_1}} |\Delta_t|$. For $t \in \mathcal{T}_3$, let $\delta(t) = (t_2 - t_1, t_3 - t_2)$ denote the differences. In the following lemma, we compute the difference of penalized criteria. It is a slight variation of the decomposition given in Lemma 2.

**Lemma 8 (Comparison of the criteria for one change-point difference).** Consider any change-point vector $\tau = (\tau_1, \dots, \tau_m)$ (with the convention $\tau_0 = 1$ and $\tau_{m+1} = n+1$). For any $l \in [m]$, let $t = (\tau_{l-1}, \tau_l, \tau_{l+1}) \in \mathcal{T}_3$. We have the following decomposition.

$$ \text{Cr}_0(\tau^{(-l)}, \mathbf{Y}) - \text{Cr}_0(\tau, \mathbf{Y}) = \left( (-1)^{\text{sign}(\Delta_t)} \mathbf{E}(t) - \mathbf{N}(t) \right)^2 - L \psi_q^2(\tau_l - \tau_{l-1}, \tau_{l+1} - \tau_l). $$

The next lemma provides a probability bound on the noise random variables $\mathbf{N}(t)$. Its proof is postponed to Section A.2.
**Lemma 9 (Concentration of N(t)).** Fix any $x \in (0,1)$. With probability higher than $1-x$, one has

$$ \mathbf{N}^2(\mathbf{t}) \le 2 \log \left( \frac{n(\delta_1(\mathbf{t}) + \delta_2(\mathbf{t}))}{\delta_1(\mathbf{t})\delta_2(\mathbf{t})} \right) + c_1 \log \log \left( \frac{n(\delta_1(\mathbf{t}) + \delta_2(\mathbf{t}))}{\delta_1(\mathbf{t})\delta_2(\mathbf{t})x} \right) + c_2 \log \left( \frac{1}{x} \right) + c_3. \quad (79) $$

simultaneously over all triads $\mathbf{t} = (t_1, t_2, t_3)$ in $\mathcal{T}_3$.

In the proof of Propositions 7 and 10, we fix $\ell = [(\sqrt{L} + 9)/10] \wedge 2 < \sqrt{L}$. When, $L > 1$, we also have $\ell > 1$. For any $L > 1$ and $q > 2$, define the event

$$ \mathcal{A}_{L,q} := \{|\mathbf{N}(t)| \le \ell \psi_q[\delta(t)] , \forall t \in \mathcal{T}_3\} , \quad (80) $$

where $\psi_q$ is defined in (77). Note that, for $L$ large enough, $\mathcal{A}_{L,q}$ is simply the even $\mathcal{A}_q$ defined in (35). The next result is a consequence of the previous lemma.

**Lemma 10.** There exist universal constants $q_0$, $c$ and $c'$ such that the following holds. For any $\ell > 1$ and any $q \ge q_0 + c \log[(\ell - 1)^{-1}]_+$, we have

$$ \mathbb{P}[\mathcal{A}_{L,q}] \ge 1 - e^{-c'q} . $$

Finally, we shall often use the following identity for the $\psi_q$ function (77). For $\delta \ne \delta'$, one has

$$ \psi_q[\delta] - \psi_q[\delta'] = \frac{2}{\psi_q(\delta) + \psi_q(\delta')} \log \left( \frac{(\delta_1 + \delta_2)\delta'_1\delta'_2}{\delta_1\delta_2(\delta'_1 + \delta'_2)} \right) . \quad (81) $$

Its proof is straightforward.

## 8.3 Proof of Proposition 9

Let $\tau = \arg\max_{i \in [n/4; 3n/4]} \epsilon_i$ and define the change-point vector $\tau = (\tau, \tau + 1)$. We shall prove that, with overwhelming probability, $\text{Cr}_0(\emptyset) > \text{Cr}_0(\tau)$. As a consequence, the empty vector will not be the global minimal minimum and the penalized least-squares estimator $\hat{\tau}$ selects at least one change-point.

Define $x_L = (\sqrt{L} + 1)/2 \in (1/2, 1)$. Note that

$$ \mathbb{P}[Y_{\tau} - \theta_{\tau} \le x_L \sqrt{2 \log(n)}] = [1 - \bar{\Phi}(x_L \sqrt{2 \log(n)})]^{[n/2]} \le e^{-[n/2] \log(\bar{\Phi}(x_L \sqrt{2 \log(n)}))} . $$

Since $\bar{\Phi}(x) \ge ce^{-x^2/2}/x$ for any $x \ge 1$, it follows that, for a constant $\beta_L \in (0, 1)$ and $n$ large enough,

$$ \mathbb{P}[Y_{\tau} - \theta_{\tau} \le x_L \sqrt{2 \log(n)}] \le e^{-\beta_L n} . $$

Applying an union bound to all $Z_{1:i}$ with $i = n/4, \dots, 3n/4$, we obtain that, with probability higher than $1 - 1/(2n)$, $|Z_{1:\tau}| \le c\sqrt{n \log(n)}$. From the definition (34) of $\mathbf{N}(t)$, we deduce that

$$ |\mathbf{N}(1, \tau, \tau + 1)| \ge \left[ \frac{\sqrt{L} + 1}{2} \sqrt{2 \log(n)} - c' \sqrt{\frac{\log(n)}{n}} \right] \left[ 1 - \frac{1}{\tau + 1} \right]^{1/2} \ge \frac{\sqrt{L} + 2}{3} \sqrt{2 \log(n)} , $$

for $n$ large enough. Applying two times the decomposition (33), we deduce that

$$ \begin{aligned} \text{Cr}_0(\emptyset) - \text{Cr}_0(\tau) &\ge -\mathbf{N}^2(\tau, \tau + 1, n + 1) - \mathbf{N}^2(0, \tau, n + 1) + 2Lq + 4L \log(4) + 2L \log(n) \\ &\ge -2 \log(n) \left[ \left( \frac{\sqrt{L} + 2}{3} \right)^2 - L \right] + 2q + 8 \log(2) , \end{aligned} $$

which is negative for $n$ large enough. The result follows.
## 8.4 Proof of Propositions 7 and 10

The proofs of these two propositions is decomposed in a few lemmas.

**Lemma 11.** Fix any $L > 1$ and any $q > 2$. Under the event $\mathcal{A}_{L,q}$, the following holds

* For any $k \in \{0, \dots, K\}$, $\hat{\tau}$ contains at most two change-points in $[\tau_k^*; \tau_{k+1}^*]$.

* Either $\tau_k^*$ does not belong to $\hat{\tau}$ or it is a $(\ell + \sqrt{L}, \hat{\tau}^{(k)}, q)$-high energy change-point.

**Lemma 12.** For any $L > 1$ and $q > 2$, there exists a constant $\kappa_L > 1$ such that the following holds under the event $\mathcal{A}_{L,q}$. If $\tau_k^*$ is a $(\kappa_L, q)$-high energy change-point, then

$$d_{H,1}(\hat{\tau}, \tau_k^*) \le \min \left[ \frac{\tau_{k+1}^* - \tau_k^*}{2}, \frac{\tau_k^* - \tau_{k-1}^*}{2} \right].$$

Define $\delta_0 = \kappa_L \Delta_k^{-2}[\log(n\Delta_k^2) + q]$. If $2\delta_0 \le \min(\tau_{k+1}^* - \tau_k^*, \tau_k^* - \tau_{k-1}^*)$, then we may build a new vector $\tilde{\tau}^* = (\tau_1^*, \dots, \tau_{k-1}^*, \tau_k^* - [2\delta_0], \tau_k^*, \tau_k^* + [2\delta_0], \tau_{k+1}^*, \dots)$. Obviously, $\theta$ is piece-wise constant with respect to $\tau^*$. The energy of $\tau_k^*$ for this new change-point vector is lower bounded as follows

$$\frac{[2\delta_0]}{2} \Delta_k^2 \ge \kappa_L [\log(n\Delta_k^2) + q] > \kappa_L \left[\log\left(\frac{n}{\delta_0}\right) + q\right] \ge \kappa_L \psi_q^2 [\delta(\tau_k^* - [2\delta_0], \tau_k^*, \tau_k^* + [2\delta_0])] .$$

As a consequence, $\tau_k^*$ is a $(\kappa_L, q)$-high energy change-point for $\tilde{\tau}^*$. From Lemma 12, we deduce that

$$d_{H,1}(\hat{\tau}, \tau_k^*) \le \delta_0$$

Hence, we arrive the following proposition. It ensures that, under $\mathcal{A}_{L,q}$, $\hat{\tau}$ satisfies Property (Detec$[\kappa_L, q, \kappa_L]$).

**Proposition 14.** For any $L > 1$ and $q > 2$, there exists a constant $\kappa_L > 1$ such that the following holds under the event $\mathcal{A}_{L,q}$. If $\tau_k^*$ is a $(\kappa_L, q)$-high energy change-point, then

$$d_{H,1}(\hat{\tau}, \tau_k^*) \le \min \left[ \frac{\tau_{k+1}^* - \tau_k^*}{2}, \frac{\tau_k^* - \tau_{k-1}^*}{2}, \kappa_L \frac{\log(n\Delta_k^2) + q}{\Delta_k^2} \right]$$

To ensure that no spurious change-points is estimated, we need to strengthen Lemma 11. The next two lemmas ensure, that in the vicinity of a true change-point $\tau_k^*$, $\hat{\tau}$ does not contain two many change-points.

**Lemma 13.** For any $L > 1$ and $q \ge 2$, there exists $\eta_L \in (0, 1/2]$ such that the following holds under $\mathcal{A}_{L,q}$. For any $k = 1, \dots, K$, $\hat{\tau}$ contains at most one change-point in $[\tau_k^*; \eta_L(\tau_{k+1}^* + \tau_k^*)]$ and in $[\eta_L(\tau_k^* + \tau_{k-1}^*); \tau_k^*]$. Besides for $L$ large enough, we have $\eta_L = 1/2$.

**Lemma 14.** There exists $L_0 > 1$ and $q_0$ such that, for all $L \ge L_0$ and $q \ge q_0$, $\hat{\tau}$ satisfies (NoSp) under the event $\mathcal{A}_{L,q}$.

Each of these four lemmas is proved using local improvements of $\hat{\tau}$. More precisely, if $\hat{\tau}$ does not satisfy any of the properties of Lemmas 11–14, than a local modification of $\hat{\tau}$ (insertion/deletion of a change-point) decreases the criterion $\text{Cr}_0$ contradicting the optimality of $\hat{\tau}$. This approach was already followed by Wang et al. [59] but here the arguments are slightly more delicate.

*Proof of Proposition 7.* For $L$ large enough, we have $\ell = 2$ and Lemma 10 ensures that $\mathbb{P}[\mathcal{A}_{L,q}] \ge 1 - e^{-c'q}$. Since $\ell = 2$, we simply have $\mathcal{A}_{L,q} = \mathcal{A}_q$ where $\mathcal{A}_q$ is defined in (35). Since both $L$ and $q$ are large enough, we may apply Lemmas 11 and 14 and Proposition 14. The result follows. $\square$

*Proof of Proposition 10.* It follows from Lemma 10 that $\mathbb{P}[\mathcal{A}_{L,q}] \ge 1 - e^{-c'q}$. We then apply Lemmas 11 and 13 and Proposition 14 to conclude. $\square$
### 8.4.1 Proof of Lemma 11

Consider a sequence $\tau$ such that, for some integers $l$ and $k$, we have $[\tau_{l-1}, \tau_{l+1}] \subset [\tau_{k-1}^*, \tau_k^*]$. As the signal is constant over $[\tau_{l-1}, \tau_{l+1})$, we have $\Delta_t = 0$ (defined in (78)) for $t = (\tau_{l-1}, \tau_l, \tau_{l+1})$. We claim that, under $\mathcal{A}_{L,q}$, $\text{Cr}_0(\tau, \mathbf{Y}) > \text{Cr}_0(\tau^{(-l)}, \mathbf{Y})$ which implies that $\hat{\tau} \neq \tau$. Indeed, Lemma 8 together with the definition of $\mathcal{A}_{L,q}$ ensure

$$ \text{Cr}_0(\tau^{(-l)}, \mathbf{Y}) - \text{Cr}_0(\tau, \mathbf{Y}) = \mathbf{N}^2[t] - L\psi_q^2(\delta(t)) \le \psi_q^2(\delta(t))[-L + \ell], $$

which is negative since $L > \ell$.

Turning to the second result, we consider a true change-point $\tau_k^*$ and a sequence $\tau$ such that $\tau_k^*$ is a $(\ell + \sqrt{L}, q, \tau)$-high energy change-point and $\tau_k^*$ does not belong to $\tau$. Let $l$ such that $\tau_l < \tau_k^* < \tau_{l+1}$. Write $t = (\tau_l, \tau_k^*, \tau_{l+1})$. By Lemma 8 and the definition of $\mathcal{A}_{L,q}$,

$$ \text{Cr}_0(\tau^{(k)}, \mathbf{Y}) - \text{Cr}_0(\tau, \mathbf{Y}) \le -[\mathbf{E}(t) - \ell\psi_q(\delta(t))]_+^2 + L\psi_q^2(\delta(t)), $$

which is negative as long as $\mathbf{E}(t) > \psi_q(\delta(t))(\ell + \sqrt{L})$. The latter inequality holds since $\tau_k^*$ is a $(\ell + \sqrt{L}, q, \tau)$-high energy change-point. This implies that $\hat{\tau} \neq \tau$.

### 8.4.2 Proof of Lemma 12

Consider any sequence $\tau$ that does not detect a high-energy change-point, say $\tau_k^*$. We shall prove that $\tau \neq \hat{\tau}$. Write $r = [(\tau_{k+1}^* - \tau_k^*) \wedge (\tau_k^* - \tau_{k-1}^*)]/2$. As a consequence, there exists an index $l$ such that

$$ \tau_l < \tau_k^* - r < \tau_k^* + r < \tau_{l+1}. \qquad (82) $$

Define the vector $t = (\tau_l, \tau_k^*, \tau_{l+1})$.

$$ \begin{aligned} \mathbf{E}(t) &= |\bar{\theta}_{\tau_k^*:\tau_{l+1}} - \bar{\theta}_{\tau_l:\tau_k^*}| \sqrt{\frac{(\tau_k^* - \tau_l)(\tau_{l+1} - \tau_k^*)}{\tau_{l+1} - \tau_l}} \\ &\ge \left[ |\Delta_k| - \mathbf{1}_{\tau_l < \tau_{k-1}^*} |\mu_{k-1} - \bar{\theta}_{\tau_l:\tau_k^*}| - \mathbf{1}_{\tau_{l+1} > \tau_{k+1}^*} |\mu_k - \bar{\theta}_{\tau_k^*:\tau_{l+1}}| \right] \sqrt{\frac{(\tau_k^* - \tau_l)(\tau_{l+1} - \tau_k^*)}{\tau_{l+1} - \tau_l}} \end{aligned} \qquad (83) $$

Denote $A_\tau = \mathbf{1}_{\tau_l < \tau_{k-1}^*} |\mu_{k-1} - \bar{\theta}_{\tau_l:\tau_k^*}|$ and $B_\tau = \mathbf{1}_{\tau_{l+1} > \tau_{k+1}^*} |\mu_k - \bar{\theta}_{\tau_{k+1}^*:\tau_{l+1}}|$. We consider four subcases depending on the values of $A_\tau$ and $B_\tau$. Throughout this proof we shall often use that $\mathbf{E}_k \le |\Delta_k|\sqrt{2r}$, which holds by definition of $\mathbf{E}_k$.

**Case 1:** $A_\tau \lor B_\tau \le |\Delta_k|/3$. It then follows from (83) and that $(\tau_k^* - \tau_l) \wedge (\tau_{l+1} - \tau_k^*) \ge r$ that

$$ \mathbf{E}(t) \ge \frac{|\Delta_k|}{3} \sqrt{\frac{(\tau_k^* - \tau_l)(\tau_{l+1} - \tau_k^*)}{\tau_{l+1} - \tau_l}} \ge \frac{|\Delta_k|\sqrt{r}}{3\sqrt{2}} \ge \frac{\mathbf{E}_k}{6}, $$

where we used (82) and $\mathbf{E}_k \le |\Delta_k|\sqrt{2r}$. Then, we consider the sequence $\tau^{(k)}$ such that $\tau_k^*$ has been inserted into $\tau$. We shall prove that $\text{Cr}_0(\tau^{(k)}, \mathbf{Y}) < \text{Cr}_0(\tau, \mathbf{Y})$. Indeed, we deduce from Lemma 8 and the definition of $\mathcal{A}_{L,q}$ that

$$ \begin{aligned} \text{Cr}_0(\tau^{(k)}, \mathbf{Y}) - \text{Cr}_0(\tau, \mathbf{Y}) &\le -[\mathbf{E}(t) - \ell\psi_q(\delta(t))]_+^2 + L[\text{pen}_0(\tau^{(k)}) - \text{pen}_0(\tau)] \\ &\le -[\mathbf{E}_k/6 - \ell\psi_q(\delta(t))]^2 + L\psi_q^2(\delta(t)). \end{aligned} $$
Since $(\tau_{l+1} - \tau_k^*) \wedge (\tau_k^* - \tau_l) \ge [(\tau_{k+1}^* - \tau_k^*) \wedge (\tau_k^* - \tau_{k-1}^*)]/2$, we derive from (81) that $\psi_q(\delta(t)) \le \sqrt{\psi_q^2(\delta_k^*, \delta_{k+1}^*) + \log(4)} < 1.5\psi_q(\delta_k^*, \delta_{k+1}^*)$ since $\psi_q(\delta_k^*, \delta_{k+1}^*) \ge q \ge 2$. As $\tau_k^*$ is a high-energy change-point, $E_k > \kappa_L \psi_q(\delta_k^*, \delta_{k+1}^*)$ is large compared to $L \psi_q(\delta_k^*, \delta_{k+1}^*)$. As a consequence, we have $\text{Cr}_0(\tau^{(k)}Y) < \text{Cr}_0(\tau, Y)$, providing that $\kappa_L \ge 9(\ell + \sqrt{L})$.

**Case 2:** $A_\tau \ge |\Delta_k|/3$ and $B_\tau \le |\Delta_k|/3$. We then consider the sequence $\tau^{(k-1,k)}$ such that both $\tau_{k-1}^*$ and $\tau_k^*$ have been inserted into $\tau$. We consider two subcases

1. $(\tau_{k-1}^* - \tau_l) \ge (\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{l+1} - \tau_k^*)$. Let $t' = (\tau_{k-1}^*, \tau_k^*, \tau_l)$. Observing that we can move from $\tau$ to $\tau^{(k-1,k)}$ by first adding $\tau_{k-1}^*$ and then adding $\tau_k^*$, we get

$$ \begin{aligned} \text{Cr}_0(\tau^{(k-1,k)}, \mathbf{Y}) - \text{Cr}_0(\tau, \mathbf{Y}) &\le -((-1)^{\text{sign}(\Delta_{t'})}\mathbf{E}[t'] + \mathbf{N}[t'])^2 + L[\text{pen}_0(\tau^{(k-1,k)}) - \text{pen}_0(\tau)] \\ &\le -(\mathbf{E}[t'] - \ell\psi_q(\delta(t')))_+^2 + L[\text{pen}_0(\tau^{(k-1,k)}) - \text{pen}_0(\tau)] . \end{aligned} \quad (84) $$

As $\tau_{k-1}^* - \tau_l \ge (\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{l+1} - \tau_k^*)$, the penalty difference is at most $2L\psi_q^2(\delta(t'))$. Arguing as in (83), we have

$$ \begin{aligned} \mathbf{E}[t'] &\ge \left[ |\Delta_k| - \mathbf{1}_{\tau_{l+1}>\tau_{k+1}^*} |\mu_k - \bar{\theta}_{\tau_k^*:\tau_{l+1}}| \right] \sqrt{\frac{(\tau_k^* - \tau_{k-1}^*)(\tau_{l+1} - \tau_k^*)}{\tau_{l+1} - \tau_{k-1}^*}} \\ &\ge \frac{2|\Delta_k|\sqrt{r}}{3\sqrt{2}} \ge \frac{\mathbf{E}_k}{3} . \end{aligned} $$

Finally, we observe that, as for $t$ in Case 1, $\psi_q(\delta(t')) \le 1.5\psi_q(\delta_k^*, \delta_{k+1}^*)$. Since $\tau_k^*$ is a high-energy change-point, it then follows from (84) that $\text{Cr}_0(\tau^{(k-1,k)}, \mathbf{Y}) < \text{Cr}_0(\tau, \mathbf{Y})$, providing that $\kappa_L \ge 4.5(\ell + \sqrt{2L})$.

2. $(\tau_{k-1}^* - \tau_l) < (\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{l+1} - \tau_k^*)$. Let $t_- = (\tau_l, \tau_{k-1}^*, \tau_k^*)$. Observing that we may go from $\tau$ to $\tau^{(k-1,k)}$ by first adding $\tau_k^*$ and then adding $\tau_{k-1}^*$, we get

$$ \begin{aligned} \text{Cr}_0(\tau^{(k-1,k)}, \mathbf{Y}) - \text{Cr}_0(\tau, \mathbf{Y}) &\le -((-1)^{\text{sign}(\Delta_{t-})}\mathbf{E}[t_-] + \mathbf{N}[t_-])^2 + L[\text{pen}_0(\tau^{(k-1,k)}) - \text{pen}_0(\tau)] \\ &\le -[\mathbf{E}[t_-] - \ell\psi_q(\delta(t_-))]^2 + L[\text{pen}_0(\tau^{(k-1,k)}) - \text{pen}_0(\tau)] . \end{aligned} \quad (85) $$

Since $(\tau_{k-1}^* - \tau_l)$ is small, the penalty difference is at most $2L\psi_q^2[\delta(t_-)]$. As a consequence, the expression (85) is negative as long as

$$ \mathbf{E}[t_-] > (\sqrt{2L} + \ell)\psi_q(\delta(t_-)) . \quad (86) $$

Working out $\mu_{k-1} - \bar{\theta}_{\tau_l:\tau_k^*}$ and relying on the inequality $A_\tau \ge |\Delta_k|/3$, we get

$$ \begin{aligned} \mathbf{E}[t_-] &= |\mu_{k-1} - \bar{\theta}_{\tau_l:\tau_{k-1}^*}| \sqrt{\frac{(\tau_{k-1}^* - \tau_l)(\tau_k^* - \tau_{k-1}^*)}{\tau_k^* - \tau_l}} = |\mu_{k-1} - \bar{\theta}_{\tau_l:\tau_k^*}| \sqrt{\frac{(\tau_k^* - \tau_l)(\tau_k^* - \tau_{k-1}^*)}{\tau_{k-1}^* - \tau_l}} \\ &\ge \frac{\mathbf{E}_k}{3} \sqrt{\frac{(\tau_k^* - \tau_l)(\tau_{k+1}^* - \tau_{k-1}^*)}{(\tau_{k-1}^* - \tau_l)(\tau_{k+1}^* - \tau_k^*)}} \\ &> \frac{\mathbf{E}_k}{3} \sqrt{\frac{\tau_k^* - \tau_l}{\tau_{k-1}^* - \tau_l}} \ge \frac{\kappa_L}{3} \psi_q[\delta_k^*, \delta_{k+1}^*] \sqrt{\frac{\tau_k^* - \tau_l}{\tau_{k-1}^* - \tau_l}}, \end{aligned} $$
Since $\tau_k^*$ is a high-energy change-point. By (81), the penalty term in (86) satisfies

$$ \begin{aligned} \psi_q(\delta(t_{-})) &\le \sqrt{\psi_q^2[\delta_k^*, \delta_{k+1}^*] + 2 \log \left( \frac{\tau_k^* - \tau_l}{\tau_{k-1}^* - \tau_l} \right)} \le \psi_q(\delta_k^*, \delta_{k+1}^*) \left[ 1 + \frac{1}{q} \log \left( \frac{\tau_k^* - \tau_l}{\tau_{k-1}^* - \tau_l} \right) \right] \\ &\le \psi_q[\delta_k^*, \delta_{k+1}^*] \sqrt{\frac{\tau_k^* - \tau_l}{\tau_{k-1}^* - \tau_l}}, \end{aligned} $$

where we used $q \ge 2$ and $x - 1 - \log(x) \ge 0$. Combining the two last bounds, we conclude that (86) holds providing that $\kappa_L \ge 3(\sqrt{2L} + \ell)$.

**Case 3:** $A_{\tau} < |\Delta_k|/3$ and $B_{\tau} \ge |\Delta_k|/3$. We consider the sequence $\tau^{(k,k+1)}$ and argue as in Case 2.

**Case 4:** $A_{\tau} \ge |\Delta_k|/3$ and $B_{\tau} \ge |\Delta_k|/3$. We consider the sequence $\tau^{(k-1,k,k+1)}$ by inserting all three true change-points into $\tau$. Define $t_+ = (\tau_k^*, \tau_{k+1}^*, \tau_{l+1})$. Depending in which order we add the three change-points, we have the following bounds

$$ \mathrm{Cr}_0(\tau^{(k-1,k,k+1)}, \mathbf{Y}) - \mathrm{Cr}_0(\tau, \mathbf{Y}) \le - \max_{t=t_{-}, t_k^*, t_{+}} \left( (-1)^{\mathrm{sign}(\Delta_t)} \mathbf{E}(t) + \mathbf{N}(t) \right)^2 + L \left[ \mathrm{pen}_0(\tau^{(k-1,k,k)}) - \mathrm{pen}_0(\tau) \right] \quad (87) $$

Then, we focus on $t_{-}$, $t_k^*$, $t_{+}$, depending on the relative values of $(\tau_{k-1}^* - \tau_l)$, $(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)$, and $(\tau_{l+1} - \tau_{k^*})$. If $(\tau_k^* - \tau_{k-1}^*) \wedge (\tau_{k+1}^* - \tau_k^*)$ is the smallest quantity of those three, it follows from (87) that

$$ \mathrm{Cr}_0(\tau^{(k-1,k,k+1)}, \mathbf{Y}) - \mathrm{Cr}_0(\tau, \mathbf{Y}) \le -(\mathbf{E}_k - \ell \psi_q(\delta_k^*, \delta_{k+1}^*))^2 + 3L \psi_q^2(\delta_k^*, \delta_{k+1}^*) , $$

which is negative since $\tau_k^*$ is a high-energy change-point. If $(\tau_{k-1}^* - \tau_l)$ is smallest difference, then we focus on $t_{-}$. The corresponding penalty is the largest one and we have

$$ \mathrm{Cr}_0(\tau^{(k-1,k,k+1)}, \mathbf{Y}) - \mathrm{Cr}_0(\tau, \mathbf{Y}) \le (\mathbf{E}[t_{-}] - \ell \psi_q(\delta(t_{-})))^2 + 3L \psi_q^2(t_{-}) . $$

Arguing as in the second part of Case 2, we derive that $\mathbf{E}[t_{-}] \ge \frac{1}{3}\mathbf{E}_k \sqrt{\frac{\tau_k^* - \tau_l}{\tau_{k-1}^* - \tau_l}}$ which is large compared to $(\sqrt{3L} + \ell)\psi_q(\delta(t_{-}))$. The case where $(\tau_{l+1} - \tau_{k+1}^*)$ is the smallest difference is handled similarly by focusing on $t_{+}$.

### 8.4.3 Proof of Lemma 13

Consider some $\eta_L \in (0, 1/2]$ whose value will be fixed later. Take any $\tau$ such that, for some $k$ and some $l$, $\tau_k^* \le \tau_{l-1} < \tau_l \le \eta_L(\tau_{k+1}^* + \tau_k^*) < \tau_{k+1}^*$. We shall prove that $\tau \ne \hat{\tau}$. If $\tau_{l+1} \le \tau_{k+1}^*$, then Lemma 11 already enforces that $\tau \ne \hat{\tau}$. We assume henceforth that $\tau_{l+1} > \tau_k^*$. Consider the vector $\tau^{(-l)}$ and define $t = (\tau_{l-1}, \tau_l, \tau_{l+1})$. By Lemma 8 and the definition of $A_{L,q}$, we have

$$ \begin{aligned} \mathrm{Cr}_0(\tau^{(-l)}, \mathbf{Y}) - \mathrm{Cr}_0(\tau, \mathbf{Y}) &\le \left[ (-1)^{\mathrm{sign}(\Delta_l)} \mathbf{E}(t) + \mathbf{N}(t) \right]^2 - L \psi_q^2[\delta(t)] \\ &\le [\mathbf{E}(t) + \ell \psi_q(\delta(t))]^2 - L \psi_q^2[\delta(t)] . \end{aligned} $$

If $\mathbf{E}(t)$ is small enough so that the right-hand side is negative, we have $\hat{\tau} \ne \tau$. As a consequence, we only need to deal with the case where $\mathbf{E}(t)$ is large. Henceforth, we assume that

$$ \mathbf{E}(t) \ge [\sqrt{L} - \ell] \psi_q[\delta(t)] . $$
In view of the definition of $\mathbf{E}(t)$, this is equivalent to

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

Introduce the vector $\boldsymbol{\tau}^{(-l,k+1)} := (\tau_1, \dots, \tau_{l-1}, \tau_{k+1}^*, \tau_{l+1}, \dots)$. Define $u = (\tau_{l-1}, \tau_l, \tau_{k+1}^*)$, $v = (\tau_l, \tau_{k+1}^*, \tau_{l+1})$, and

$$ z := \frac{(\tau_{l+1} - \tau_{l-1})(\tau_{k+1}^* - \tau_l)}{(\tau_{l+1} - \tau_{k+1}^*)(\tau_l - \tau_{l-1})} \geq \frac{(\tau_{k+1}^* - \tau_l)}{(\tau_l - \tau_{l-1})} \geq \frac{1}{\eta_L} - 1, $$

since $\tau_k^* \le \tau_{l-1} < \tau_l \le \eta_L(\tau_{k+1}^* + \tau_k^*)$. From the definition of $\mathbf{E}(v)$ together with the previous bound, we derive that

$$ \mathbf{E}^2(v) \geq z(\sqrt{L} - \ell)^2 \psi_q^2[\delta(t)] . \quad (88) $$

Since $\tau_{l+1} - \tau_l \ge \tau_{k+1}^* - \tau_l \ge \tau_l - \tau_{l-1}$, we deduce that $\psi_q^2(\delta(u)) \le \psi^2(\delta(t)) + \log(4)$. Applying Lemma 8 and relying on the event $\mathcal{A}_{L,q}$, we obtain

$$ \begin{aligned} & \mathrm{Cr}_0(\boldsymbol{\tau}^{(-l,k+1)}, \mathbf{Y}) - \mathrm{Cr}_0(\boldsymbol{\tau}, \mathbf{Y}) \\ &= \mathrm{Cr}_0(\boldsymbol{\tau}^{(-l,k+1)}, \mathbf{Y}) - \mathrm{Cr}_0(\boldsymbol{\tau}^{(k+1)}, \mathbf{Y}) + \mathrm{Cr}_0(\boldsymbol{\tau}^{(k+1)}, \mathbf{Y}) - \mathrm{Cr}_0(\boldsymbol{\tau}, \mathbf{Y}) \\ &\le \mathbf{N}^2(u) - \left( (-1)^{\mathrm{sign}(\Delta_v)} \mathbf{E}(v) + \mathbf{N}(v) \right)^2 + L \left[ \mathrm{pen}_0(\boldsymbol{\tau}^{(-l,k+1)}) - \mathrm{pen}_0(\boldsymbol{\tau}) \right], \\ &\le \ell^2 \psi_q^2[\delta(u)] - (\mathbf{E}(v) - \ell \psi_q[\delta(v)])_+^2 + L \left[ \mathrm{pen}_0(\boldsymbol{\tau}^{(-l,k+1)}) - \mathrm{pen}_0(\boldsymbol{\tau}) \right] \\ &< \ell^2 [\psi_q^2[\delta(t)] + \log(4)] - \left( \sqrt{z}(\sqrt{L} - \ell) \psi_q[\delta(t)] - \ell \psi_q[\delta(v)] \right)_+^2 + L \left[ \mathrm{pen}_0(\boldsymbol{\tau}^{(-l,k+1)}) - \mathrm{pen}_0(\boldsymbol{\tau}) \right]. \end{aligned} $$

Let us compute the penalty difference.

$$ \begin{aligned} \mathrm{pen}_0(\boldsymbol{\tau}^{(-l,k+1)}) - \mathrm{pen}_0(\boldsymbol{\tau}) &= \psi_q^2[\delta(v)] - \psi_q^2[\delta(u)] \\ &= 2 \log \left( \frac{(\tau_{l+1} - \tau_l)(\tau_l - \tau_{l-1})}{(\tau_{l+1} - \tau_{k+1}^*)(\tau_{k+1}^* - \tau_{l-1})} \right). \end{aligned} $$

Since $\tau_k^* \le \tau_{l-1} < \tau_l \le (\tau_k^* + \tau_{k+1}^*)/2 < \tau_{k+1}^* \le \tau_{l+1}$, one easily checks that the above expression is less or equal to $2 \log(z)$. Hence, we also have $\psi_q^2[\delta(v)] \le \psi_q^2[\delta(t)] + 2 \log(z)$. We derive from the previous inequalities that

$$ \begin{aligned} \frac{\mathrm{Cr}_0(\boldsymbol{\tau}^{(-l,k+1)}, \mathbf{Y}) - \mathrm{Cr}_0(\boldsymbol{\tau}, \mathbf{Y})}{\psi_q^2[\delta(t)]} &\le - \left[ z^{1/2}(\sqrt{L} - \ell) - \ell \sqrt{1 + \frac{2 \log(2z)}{\psi_q^2[\delta(t)]}} \right]_+^2 + \ell^2 + \frac{2L \log(z) + 2\ell^2(\log(2))}{\psi_q^2[\delta(t)]} \\ &\le - \left[ z^{1/2}(\sqrt{L} - \ell) - \ell \sqrt{1 + \log(2z)} \right]_+^2 + \ell^2 + L \log(2z), \end{aligned} $$

since $\psi_q^2[\delta(t)] \ge q \ge 2$ and $\ell^2 \le L$. Coming back to the definition of $\ell$ (Section 8.2), we observe that the last expression is negative as soon as

$$ 0.9\sqrt{z}(\sqrt{L}-1) > 2\sqrt{L}\sqrt{1+\log(2z)}, \quad \text{if } \sqrt{L} \le 11, \quad (89) $$

$$ \sqrt{z}(\sqrt{L}-2) > \sqrt{4+L\log(2z)} + 2\sqrt{1+\log(2z)}, \quad \text{if } \sqrt{L} > 11. \quad (90) $$

Recall that $z \ge \eta_L^{-1} - 1$. In summary we only have to prove, that for all $L > 1$, there exists $\eta_L \in (0, 1/2]$ such that (89) or (90) holds for all $z \ge \eta_L^{-1} - 1$ and that, for $\sqrt{L} > 11$ large enough, (90) holds for all $z \ge 1$ (which corresponds to taking $\eta_L = 1/2$).
The function $h: z \mapsto \frac{z}{1+\log(2z)}$ is increasing for $z \ge 1$. If $\eta_L \in (0, 1/2)$ is chosen in such a way $h(1/\eta_L - 1) > 4L[0.9(\sqrt{L}-1)]^{-2}$, then (89) is satisfied.

Now consider the large $L$ regime ($\sqrt{L} > 11$). Since $1 + \log(2z) \le 2z$, (90) is satisfied as soon as

$$z[\sqrt{L} - 2 - 2\sqrt{2}]^2 - 4 - L \log(2z) > 0 \quad (91)$$

For a fixed $\sqrt{L} > 11$, the above expression is positive for $z$ large enough. Hence, there exists $\eta_L \in (0, 1/2)$ such that (91) holds for all $z \ge \eta_L - 1$. Beside, using a derivation argument, we derive that Inequality (91) holds for all $z \ge 1$ as long as

$$L(1 - \log(2)) - 4 + 2L \log \left( 1 - \frac{2 + 2\sqrt{2}}{\sqrt{L}} \right) > 0,$$

which holds for $L$ large enough. This concludes the proof.

### 8.4.4 Proof of Lemma 14

We consider the specific cases $k=1$ and $k=K$ at the end of this proof. Consider any vector $\boldsymbol{\tau}$ such that, for some $k$ and $l$, $\tau_{l-1}$ and $\tau_l$ both belong to $[(\tau_{k-1}^* + \tau_k^*)/2; (\tau_k^* + \tau_{k+1}^*)/2]$. Since $L$ is chosen large enough, we may assume that $\eta_L$ in Lemma 13 is equal to $1/2$. Applying this lemma, we have $\boldsymbol{\tau} \ne \hat{\boldsymbol{\tau}}$ unless

$$\frac{\tau_{k-1}^* + \tau_k^*}{2} \le \tau_{l-1} < \tau_k^* < \tau_l \le \frac{\tau_k^* + \tau_{k+1}^*}{2}$$

By symmetry, we may assume that $\tau_l - \tau_k^* \ge \tau_k^* - \tau_{l-1}$. As a warm-up, we consider the simpler situation where $\tau_{l+1} \le \tau_{k+1}^*$. We shall prove that either $\boldsymbol{\tau}^{(-l)}$ or $\boldsymbol{\tau}^{(-l,k)}$ achieves a smaller criterion value than $\boldsymbol{\tau}$ which as usual implies that $\boldsymbol{\tau} \ne \hat{\boldsymbol{\tau}}$. Write $t = (\tau_{l-1}, \tau_l, \tau_{l+1})$, $u = (\tau_k^*, \tau_l, \tau_{l+1})$, and $v = (\tau_{l-1}, \tau_k^*, \tau_l)$. We have

$$\mathrm{Cr}_0[\boldsymbol{\tau}^{(-l)}] - \mathrm{Cr}_0[\boldsymbol{\tau}] \le (\mathbf{E}(t) + \ell \psi_q[\delta(t)])^2 - L \psi_q^2[\delta(t)].$$

If $\mathbf{E}(t) < \psi_q[\delta(t)](\sqrt{L} - \ell)$, then $\mathrm{Cr}_0[\boldsymbol{\tau}^{(-l)}] < \mathrm{Cr}_0[\boldsymbol{\tau}]$ and $\boldsymbol{\tau} \ne \hat{\boldsymbol{\tau}}$. Now assume that $\mathbf{E}(t)$ is large. Considering the local modification $\boldsymbol{\tau}^{(-l,k)}$, we obtain

$$\mathrm{Cr}_0[\boldsymbol{\tau}^{(-l,k)}] - \mathrm{Cr}_0[\boldsymbol{\tau}] \le -[\mathbf{E}(v) - \ell \psi_q[\delta(v)]]_+^2 + \ell^2 \psi_q^2[\delta(u)] + L \left[\mathrm{pen}_0(\boldsymbol{\tau}^{(-l,k)}) - \mathrm{pen}_0(\boldsymbol{\tau})\right]. \quad (92)$$

We shall prove that the rhs in (92) is negative. From the definition of energies, we derive

$$\mathbf{E}^2(t) = \Delta_k^2 \frac{(\tau_{l+1} - \tau_l)(\tau_k^* - \tau_{l-1})^2}{(\tau_{l+1} - \tau_{l-1})(\tau_l - \tau_{l-1})} = \mathbf{E}^2(v) \frac{(\tau_k^* - \tau_{l-1})(\tau_{l+1} - \tau_l)}{(\tau_l - \tau_k^*)(\tau_{l+1} - \tau_{l-1})}.$$

Define $z = \frac{(\tau_l - \tau_k^*)(\tau_{l+1} - \tau_{l-1})}{(\tau_k^* - \tau_{l-1})(\tau_{l+1} - \tau_l)} > 1$. So that $\mathbf{E}(v) = \sqrt{z}\mathbf{E}(t) > \sqrt{z}\psi_q[\delta(t)](\sqrt{L} - \ell)$. Also

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

since $\tau_l - \tau_{l-1} \le 2(\tau_l - \tau_k^*)$. By definition of the penalty function we have

$$\begin{align*}
\mathrm{pen}_0(\boldsymbol{\tau}^{(-l,k)}) - \mathrm{pen}_0(\boldsymbol{\tau}) &= \psi_q^2[\delta(v)] - \psi_q^2[\delta(u)] = 2 \log \left( \frac{(\tau_{l+1} - \tau_l)(\tau_l - \tau_{l-1})}{(\tau_{l+1} - \tau_k^*)(\tau_k^* - \tau_{l-1})} \right) \\
&= 2 \log \left( \frac{(\tau_l - \tau_k^*)(\tau_{l+1} - \tau_{l-1})}{(\tau_{l+1} - \tau_l)(\tau_k^* - \tau_{l-1})} \right) + 2 \log \left( \frac{(\tau_{l+1} - \tau_l)^2(\tau_l - \tau_{l-1})}{(\tau_{l+1} - \tau_k^*)(\tau_{l+1} - \tau_{l-1})(\tau_l - \tau_k^*)} \right) \\
&\le 2 \log(z) + 2 \log(2),
\end{align*}$$
since $\tau_l - \tau_{l-1} \le 2(\tau_l - \tau_k)^*$. Hence, $\psi_q^2[\delta(v)] \le \psi_q^2[\delta(t)] + 2\log(4z)$. Coming back to (92), this leads us to

$$ \begin{aligned} \frac{\mathrm{Cr}_0[\boldsymbol{\tau}^{(-l,k)}] - \mathrm{Cr}_0[\boldsymbol{\tau}]}{\psi_q^2[\delta(t)]} &\le - \left[ \sqrt{z}(\sqrt{L} - \ell) - \ell \left(1 + \frac{2\log(4z)}{\psi_q^2[\delta(t)]}\right)^{1/2} \right]_+^2 + \ell^2 \left(1 + \frac{2\log(2)}{\psi_q^2[\delta(t)]}\right) + \frac{2L \log(2z)}{\psi_q^2[\delta(t)]} \\ &\le - \left[ \sqrt{z}(\sqrt{L} - \ell) - \ell \left(1 + \frac{2\log(4z)}{q}\right) \right]_+^2 + \ell^2 \left(1 + \frac{2\log(2)}{q}\right) + \frac{2L \log(2z)}{q}, \\ &\le - \left[ \sqrt{z}(\sqrt{L} - 2) - 2\sqrt{1 + \log(4z)} \right]_+^2 + 4(1 + \log(2)) + L \log(2z), \end{aligned} \quad (93) $$

since $q \ge 2$ and $\ell = 2$ for $L \ge \sqrt{11}$. Hence, it only remains to prove that, for all $L$ large enough, all $z \ge 1$,

$$ \sqrt{z}(\sqrt{L} - 2) > 2\sqrt{1 + \log(4z)} + 2\sqrt{1 + \log(2)} + \sqrt{L \log(2z)}. $$

Consider any $\zeta \in (0, 1)$. There exists $L_\zeta$ such that, for all $L > L_\zeta$ and all $z \ge 1$,

$$ \zeta \sqrt{zL} > 2\sqrt{z} + 2\sqrt{1 + \log(4z)} + 2\sqrt{1 + \log(2)}. $$

Hence, it suffices to prove that there exists $\zeta_0 \in (0, 1)$ such that for all $z \ge 1$, we have $(1 - \zeta_0)^2 z \ge \log(2z)$. Deriving this expression with respect to $z$, we conclude that the latter inequality holds as long as $2\log(1 - \zeta_0)^{-1} \le \log(e/2)$. Taking $\zeta_0 = 1 - \sqrt{2/e}$ concludes this part.

Now, we consider the more challenging (and painful) situation where $\tau_{l+1} > \tau_{k+1}^*$. We shall prove, by deleting $\tau_l$ and possibly inserting $\tau_k^*$ or $\tau_{k+1}^*$, the penalized criterion will decrease. In other words, at least one the sequences $\boldsymbol{\tau}^{(-l)}$, $\boldsymbol{\tau}^{(-l,k)}$ and $\boldsymbol{\tau}^{(-l,k+1)}$ achieves a smaller criterion than $\boldsymbol{\tau}$. It suffices to show that $\mathrm{Cr}_0[\boldsymbol{\tau}] > \mathrm{Cr}_0[\boldsymbol{\tau}^{(-l)}]$ as long as $\mathrm{Cr}_0[\boldsymbol{\tau}] \le \mathrm{Cr}_0[\boldsymbol{\tau}^{(-l,k)}] \wedge \mathrm{Cr}_0[\boldsymbol{\tau}^{(-l,k+1)}]$. We assume in the remainder of this proof that the latter inequality holds. Under the event $\mathcal{A}_{L,q}$, Lemma 8 enforces that

$$ \begin{aligned} \mathrm{Cr}_0[\boldsymbol{\tau}^{(-l,k)}] - \mathrm{Cr}_0[\boldsymbol{\tau}] &\le -(\mathbf{E}[(\tau_{l-1}, \tau_k^*, \tau_l)] - \ell \psi_q[\delta(\tau_{l-1}, \tau_k^*, \tau_l)])_+^2 + (\mathbf{E}(\tau_k^*, \tau_l, \tau_{l+1}) + \ell \psi_q[\delta(\tau_k^*, \tau_l, \tau_{l+1})])^2 \\ &\quad + L (\psi_q^2[\delta(\tau_{l-1}, \tau_k^*, \tau_l)] - \psi_q^2[\delta(\tau_k^*, \tau_l, \tau_{l+1})]) ; \end{aligned} $$

$$ \begin{aligned} \mathrm{Cr}_0[\boldsymbol{\tau}^{(-l,k+1)}] - \mathrm{Cr}_0[\boldsymbol{\tau}] &\le -(\mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_{l+1}) - \ell \psi_q[\delta(\tau_l, \tau_{k+1}^*, \tau_{l+1})])_+^2 + (\mathbf{E}(\tau_{l-1}, \tau_l, \tau_{k+1}^*) + \ell \psi_q[\delta(\tau_{l-1}, \tau_l, \tau_{k+1}^*)])^2 \\ &\quad + L (\psi_q^2[\delta(\tau_l, \tau_{k+1}^*, \tau_{l+1})] - \psi_q^2[\delta(\tau_{l-1}, \tau_l, \tau_{k+1}^*)]) . \end{aligned} $$

From (81) and the respective positions of the change-points, we derive that

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

Similarly, we get

$$ \psi_q^2[\delta(\tau_l, \tau_{k+1}^*, \tau_{l+1})] - \psi_q^2[\delta(\tau_{l-1}, \tau_l, \tau_{k+1}^*)] = 2 \log \left( \frac{(\tau_l - \tau_{l-1})(\tau_{l+1} - \tau_l)}{(\tau_{l+1} - \tau_{k+1}^*)(\tau_{k+1}^* - \tau_{l-1})} \right) \le 2 \log \left( \frac{\tau_{l+1} - \tau_l}{\tau_{l+1} - \tau_{k+1}^*} \right). $$
Since $\mathrm{Cr}_0[\boldsymbol{\tau}] \le \mathrm{Cr}_0[\boldsymbol{\tau}^{(-l,k)}] \wedge \mathrm{Cr}_0[\boldsymbol{\tau}^{(-l,k+1)}]$, since $\ell \le \sqrt{L}$, the above inequalities lead us to

$$ \mathbf{E}(\tau_{l-1}, \tau_k^*, \tau_l) \le \mathbf{E}(\tau_k^*, \tau_l, \tau_{l+1}) + \omega_1; \quad (94) $$

$$ \mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_{l+1}) \le \mathbf{E}(\tau_{l-1}, \tau_l, \tau_{k+1}^*) + \omega_2; \quad (95) $$

$$ \begin{aligned} \omega_1 &:= 2\ell\psi_q[\delta(\tau_k^*, \tau_l, \tau_{l+1})] + 2\sqrt{2L \log \left( \frac{\tau_l - \tau_{l-1}}{\tau_k^* - \tau_{l-1}} \right)}; \\ \omega_2 &:= 2\ell\psi_q[\delta(\tau_{l-1}, \tau_l, \tau_{k+1}^*)] + 2\sqrt{2L \log \left( \frac{\tau_{l+1} - \tau_l}{\tau_{l+1} - \tau_{k+1}^*} \right)}. \end{aligned} $$

We aim at proving that $\mathrm{Cr}_0(\boldsymbol{\tau}^{(-l)}) < \mathrm{Cr}_0(\boldsymbol{\tau})$. Define $t = (\tau_{l-1}, \tau_l, \tau_{l+1})$. In view of Lemma 8, it suffices to establish the following inequality

$$ \mathbf{E}(t) < \psi_q[\delta(t)] (\sqrt{L} - \ell), \quad (96) $$

We start with the following lemma that relates the change-point energies.

**Lemma 15.** It holds that

$$ \frac{\mathbf{E}(\tau_k^*, \tau_l, \tau_{l+1}) \mathbf{E}(\tau_{l-1}, \tau_l, \tau_{k+1}^*)}{\mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_{l+1}) \mathbf{E}(\tau_{l-1}, \tau_k^*, \tau_l)} = \sqrt{\frac{(\tau_{l+1} - \tau_{k+1}^*)(\tau_k^* - \tau_{l-1})}{(\tau_{l+1} - \tau_k^*)(\tau_{k+1}^* - \tau_{l-1})}} \le \sqrt{\frac{1}{3}}; \quad (97) $$

$$ \frac{\mathbf{E}(\tau_k^*, \tau_l, \tau_{l+1})}{\mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_{l+1})} \le \sqrt{\frac{\tau_{l+1} - \tau_{k+1}^*}{\tau_{l+1} - \tau_k^*}}; \quad \frac{\mathbf{E}(\tau_{l-1}, \tau_l, \tau_{k+1}^*)}{\mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_l)} \le \sqrt{\frac{\tau_k^* - \tau_{l-1}}{\tau_l - \tau_k^*}}; \quad (98) $$

$$ \mathbf{E}(t) \le \mathbf{E}(\tau_{l-1}, \tau_k^*, \tau_l) \sqrt{\frac{\tau_k^* - \tau_{l-1}}{\tau_l - \tau_k^*}} + \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}}}. \quad (99) $$

It follows from (97–98) together with (94) and (95) that $\mathbf{E}(\tau_{l-1}, \tau_k^*, \tau_l)$ is small. Indeed, we have

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

which implies

$$ \mathbf{E}(\tau_{l-1}, \tau_k^*, \tau_l) \le \frac{3 + \sqrt{3}}{2} \left( \omega_1 + \sqrt{\frac{\tau_{l+1} - \tau_{k+1}^*}{\tau_{l+1} - \tau_k^*}} \omega_2 \right). $$

Similarly, we obtain

$$ \mathbf{E}(\tau_l, \tau_{k+1}^*, \tau_{l+1}) \le \frac{3 + \sqrt{3}}{2} \left( \omega_2 + \sqrt{\frac{\tau_k^* - \tau_{l-1}}{\tau_l - \tau_k^*}} \omega_1 \right). $$