Emmanuel Pilliat

Alexandra Carpentier

Nicolas Verzelen

Optimal multiple change-point detection for high-dimensional data

This manuscript makes two contributions to the field of change-point detection. In a general change-point setting, we provide a generic algorithm for aggregating local homogeneity tests into an estimator of change-points in a time series. Interestingly, we establish that the error rates of the collection of tests directly translate into detection properties of the change-point estimator. This generic scheme is then applied to various problems including covariance changepoint detection, nonparametric change-point detection and sparse multivariate mean changepoint detection. For the latter, we derive minimax optimal rates that are adaptive to the unknown sparsity and to the distance between change-points when the noise is Gaussian. For sub-Gaussian noise, we introduce a variant that is optimal in almost all sparsity regimes.

Introduction

Change-point detection has a long history since the seminal work of Wald [START_REF] Wald | Sequential tests of statistical hypotheses[END_REF] that lead to flourishing lines (see [START_REF] Yue S Niu | Multiple change-point detection: A selective overview[END_REF][START_REF] Truong | Selective review of offline change point detection methods[END_REF] for recent surveys). Earlier contributions focused on the problems of detecting and localizing change-points in a univariate time series. Spurred by applications in genomics [START_REF] Adam B Olshen | Circular binary segmentation for the analysis of array-based dna copy number data[END_REF] and finance, there has been a recent trend in the literature towards the analysis of more complex time series for instance in a high-dimensional linear space [START_REF] Jirak | Uniform change point tests in high dimension[END_REF] or even belonging to a non-Euclidean space [START_REF] Chu | Asymptotic distribution-free change-point detection for multivariate and non-euclidean data[END_REF].

In this work, we study high-dimensional time series whose mean may change possibly on a few number of coordinates. See the introduction of [START_REF] Wang | High dimensional change point estimation via sparse projection[END_REF] for an account of possible applications and practical motivations. In particular, we build a procedure which is able to detect and localize change-points under minimal assumptions on the height of these change-points. Along the way towards this optimal procedure, we define and analyze a scheme for general change-point problems that aggregates a collection of local tests into an estimator change-points. This generic scheme is of independent interest and easily allows to derive optimal change-point procedure in other complex settings such as covariance change-points problems or nonparametric change-point problems. In this introduction, we first describe this generic scheme before turning to our results in high-dimensional sparse change-point detection and finally discussing other applications.

General change-point setting

In the most general form of a change-point problem, we consider a random sequence Y = (y 1 , y 2 , . . . , y n ) in some measured space Y n and, for t = 1, . . . , n, we write P t for the marginal 1 distribution of y t . We are also given a functional Γ mapping the probability distribution P t to some space V. Then, the purpose of change-point detection is to detect changes in the sequence (Γ(P 1 ), Γ(P 2 ), . . . , Γ(P n )) in V n and to estimate the positions of these changes. This setting is really general and does not require that the random variables (y t ) are independent.

Let us shortly explain how this general framework encompasses most offline change-point detection problems. In the Gaussian mean univariate change-point setting, we have Y = R, the distribution P t corresponds to the normal distribution with mean θ t ∈ R and variance σ 2 and Γ(P t ) = θ t . In the (heteroscedastic) mean univariate change-point problem, the distribution P t is not necessarily Gaussian and, in particular, the variance of y t is allowed to vary with t. Still, one is only interested in detecting variations of Γ(P t ) = xdP t = E[y t ]. By contrast, in the variance univariate change-point problems, one focuses on changes in the variance of y t . This can be done by taking Γ(P t ) = x 2 dP t -[ xdP t ] 2 = Var(y t ). If one is interested in possibly nonparametric changes in the distributions, then the functional Γ is simply taken to be the identity map. In semiparametric quantile change-point detection [START_REF] Vanegas | Multiscale quantile segmentation[END_REF], the univariate distributions P t can be arbitrary whereas Γ(P t ) is a quantile of P t .

To further formalize the change-point detection problem in the sequence (Γ(P 1 ), Γ(P 2 ), . . . , Γ(P n )), we define an integer 0 ≤ K ≤ n -1 and a vector of integers τ = (τ 1 , . . . , τ K ) satisfying 1 = τ 0 < τ 1 < • • • < τ K < τ K+1 = n + 1 such that Γ(P t ) is constant over each interval [τ k , τ k+1 -1] and Γ(P τ k -1 ) = Γ(P τ k ). Hence, τ k corresponds to the position of the k th change-point. We shall often refer to τ k as a change-point. Equipped with this notation, we are interested in building an estimator τ = (τ 1 , . . . , τ K ) of τ from the time series Y . Here, τ1 , . . . , τ K correspond to the estimated change-points of τ and K to the number of the estimated change-points.

Desirable Guarantees of an estimator.

Before describing the generic scheme for estimating τ , let us first formalize the desired properties of a good change-point procedure. Informally, the primary objectives are to detect most if not all change-points while estimating no (or at least very few) spurious change-points.

Regarding the latter objective, it is usually required that the number of change-points K is not overestimated by τ . Here, we require a slightly stronger local property introduced in [START_REF] Verzelen | Optimal Change-Point Detection and Localization[END_REF]. An estimator τ of size K is said to detect no spurious change-points (NoSp) if

{τ k , 1 ≤ k ≤ K} ∩ τ k - τ k -τ k-1 2 , τ k + τ k+1 -τ k 2 ≤ 1 , for all 1 ≤ k ≤ K ; {τ k , 1 ≤ k ≤ K} ⊂ τ 1 -τ 1 -1 2 , τ K + n+1-τ K 2 . (1)
The second condition simply ensures that no change-point is estimated near the boundaries of the time series. The first condition entails that, for each change-point τ k there is at most one estimated change-point τk in the interval [τ k -(τ k -τ k-1 )/2, τ k + (τ k+1 -τ k )/2]. In other words, (NoSp) requires that, on each sub-interval, the number of change-points is not overestimated.

Let us now formalize the objective of detecting the change-points. In this work, we consider as in [START_REF] Verzelen | Optimal Change-Point Detection and Localization[END_REF] realistic settings where some change-points are so close or their heights are so small that they are impossible to detect. As a consequence, we can only hope to detect the subset of significant change-points. In what follows, we define a subset K * ⊂ [K] of change-point indices that correspond to significant change-points. Obviously, the significance of a particular change-point is relative to the problem under consideration -data distribution, nature of change-points -and the definition is problem dependent. As an example, we define in the next subsection the suitable notion of energy and significance of a change-point in the mean multivariate change-point setting. In Section 6, we formalize this notion for covariance and univariate nonparametric change-point problems. In light of this discussion, the second guarantee we aim for is to detect all significant change-points. A change-point τ k is said to be detected if there is at least one estimated change-point τl in the interval [τ k -(τ k -τ k-1 )/2, τ k + (τ k+1 -τ k )/2]. Equivalently, this means that at least one of the estimated change-points is closer to τ k than to any other true change-point.

Aside from (NoSp) and (detect) properties, one may additionally aim at localizing the changepoints as well as possible -see the discussions in [START_REF] Wang | Optimal change point detection and localization in sparse dynamic networks[END_REF]. Given a specific change-point τ k detected by an estimator τ , its localization error d H,1 ( τ , τ k ) is defined by

d H,1 ( τ , τ k ) = min l=1,...,| τ | | τ l -τ k | ,
which is the smallest distance between τ k and one of the estimated change-points. While this work mainly focused on the detection problem, we shall also provide localization bounds along the way.

A generic roadmap for change-point detection.

In this manuscript, our first contribution is a generic procedure for aggregating a collection of tests into an estimator τ of τ . For two positive integers (l, r), we consider the time interval [l -r, l + r). Suppose we are given a collection G of such (l, r). For each (l, r) ∈ G, we are also given a homogeneity test T l,r of the null hypothesis H 0 : {(Γ(P t )) is constant over the segment [l-r, l+r)}. This hypothesis is equivalent to the absence of any change-point on the interval (l -r, l + r). Given such a collections of homogeneity tests (T l,r ), (l, r) ∈ G, we build in this manuscript an estimator τ that satisfies the following properties. If the multiple testing procedure does not reject any true null hypothesis (no false positives), then τ does not estimate any spurious change-point, that is, it satisfies (No Sp). Furthermore, any change-point τ k that is detected by some test T τk ,r k , where τk is close enough to τ k and r k is small enough is detected by the estimator τ . In other words, we establish a completely generic result that translates properties of the multiple testing procedure into detection properties. Thus, the construction of a change-point procedure boils down to building a suitable multiple testing procedure (T l,r ), (l, r) ∈ G whose family-wise error rate (FWER) is controlled, while being able to detect all the significant change-points. In turn, this allows us to reduce the problem of change-point detection under minimal distance between the change-points to the well-established field of minimax testing.

Related Work and possible applications.

In the last years, there has been a growing interest into the extension of univariate mean changepoint procedures such as wild binary segmentation (WBS) [START_REF] Fryzlewicz | Wild binary segmentation for multiple change-point detection[END_REF] to other problems such as covariance change-point [START_REF] Wang | Optimal covariance change point localization in high dimension[END_REF], network change-point [START_REF] Wang | Optimal change point detection and localization in sparse dynamic networks[END_REF], or nonparametric change-point [START_REF] Hernan | Optimal nonparametric change point detection and localization[END_REF]. For each of these problems (and for others), it turns out that the general ideas of WBS can be instantiated. However, for each setting, the proofs need to be fully adapted in a case by case manner. Besides, the resulting procedures are only optimal up to logarithmic terms.

Recently, Chan and Chen [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF] and Kovács et al. [START_REF] Kovács | Seeded binary segmentation: A general methodology for fast and optimal change point detection[END_REF] have introduced bottom-up aggregation procedures for mean change-point segmentation (see also [START_REF] Kovács | Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries[END_REF] for localization improvements). Moreover, Kovács et al. [START_REF] Kovács | Seeded binary segmentation: A general methodology for fast and optimal change point detection[END_REF][START_REF] Kovács | Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries[END_REF] illustrate the numerical performances to other change-point models, such as graphical models or multivariate mean-change point models. In fact, one may extend their procedures to generic problems, but the theoretical guarantees are only provided for univariate models and it remains unclear whether one can extend them beyond very specific cases.

In contrast, it is quite straightforward to adapt our generic procedure to any new setting once suitable homogeneity multiple tests have been crafted. As the most prominent example, we consider the sparse high-dimensional mean change-point detection and establish the optimality of our procedure -see the next subsection for details. In Section 6, we also handle the covariance changepoint detection and the univariate nonparametric change-point detection problems. In each case, we pinpoint the first tight minimal conditions for detection.

Besides, we could apply our strategy to other problems such changes in auto-regressive models [START_REF] Wang | Localizing changes in highdimensional vector autoregressive processes[END_REF], changes in the inverse covariance matrix of y i [START_REF] Gibberd | Multiple changepoint estimation in high-dimensional gaussian graphical models[END_REF][START_REF] Kovács | Seeded binary segmentation: A general methodology for fast and optimal change point detection[END_REF] or changes in a high-dimensional regression model [START_REF] Rinaldo | Localizing changes in high-dimensional regression models[END_REF]. All such change-point problems can be addressed through the construction and careful analysis of two-sample tests for auto-regressive models, inverse covariance matrices, and linear regression models respectively. Similarly, we can build Kernel change-point procedures [START_REF] Sylvain Arlot | A kernel multiple change-point algorithm via model selection[END_REF][START_REF] Garreau | Consistent change-point detection with kernels[END_REF] from kernel two-sample tests [START_REF] Gretton | A kernel two-sample test[END_REF].

Sparse Multivariate Change-point Setting

As explained above, our primary application of our generic scheme is the multivariate mean changepoint detection problem with sparse variations where one observes a time series Y = (y 1 , . . . , y n ) ∈ R p×n with unknown means Θ = (θ 1 , . . . , θ n ) ∈ R p×n so that we have the decomposition

y t = θ t + ε t t = 1, . . . , n , (2)
where the noise matrix ε = (ε 1 , . . . , ε n ) is made of independent and mean zero random vectors of size p. In this manuscript, we make two distributional assumptions on the noise. Either we suppose that all random vectors ε i follow independent normal distribution with variance σ 2 I p (see Section 3) or that the components of ε i follow independent sub-Gaussian distributions with variance σ 2 (see Section 4). In either case, we assume that σ 2 is known.

Here, we are interested in the variations of the mean vector θ t so that, relying on the formalism of the previous subsection, we have Γ(P t ) = θ t . Considering the vector of change-points τ = (τ 1 , . . . , τ K ), we can define K + 1 vectors µ 0 , . . . , µ K in R p satisfying µ k = µ k+1 for all k = 0, . . . , K -1 such that

θ t = K k=0 µ k 1 τ k ≤t<τ k+1 .
Equivalently, µ k is the constant mean of y over the interval [τ k , τ k+1 -1]. The difference µ k -µ k-1 in R p measures the variation of Θ at the change-point τ k and can possibly have many null coordinates. In this possibly sparse multi-dimensional setting, the significance of a changepoint is measured through three quantities ∆ k , r k , and s k . First, the height ∆ k of the change-point τ k is defined as the Euclidean norm of the signal difference. The length r k of the change-point τ k is the minimal distance from τ k to another change-point, τ k-1 or τ k+1 . More precisely,

∆ k = µ k -µ k-1 ; r k = min(τ k+1 -τ k , τ k -τ k-1 ) . (3)
As a simple example, Figure 1 depicts a one dimensional piece-wise constant sequence Θ with 3 change-points illustrating the setting presented above. In the univariate change-point literature (e.g. [START_REF] Cho | Data segmentation algorithms: Univariate mean change and beyond[END_REF][START_REF] Fryzlewicz | Wild binary segmentation for multiple change-point detection[END_REF][START_REF] Fryzlewicz | Tail-greedy bottom-up data decompositions and fast multiple change-point detection[END_REF]) the height and the length of a change-point characterize the significance of a change-point. In the multivariate setting, where the change-points can be sparse, meaning the number of non null coordinates of the vector µ k -µ k-1 is possibly small, one also considers the sparsity s k of change-point τ k , defined by

s k = µ k -µ k-1 0 , (4)
where, for any v ∈ R p , v 0 = 1≤i≤p 1{v i = 0}. Following the literature on binary and wild binary segmentation, we consider the CUSUM statistic

C l,r (Y ) = r 2σ 2 1 r l+r-1 i=l y i - 1 r l-1 i=l-r y i .
This statistic computes the normalized difference of empirical mean of y i on [l -r, l) and [l, l + r).

If the noise is Gaussian and if Θ is constant on [l -r, l + r), then C l,r (Y ) simply follows a standard p-dimensional normal distribution. To simplify, consider a specific instance of our testing problem where we want to test whether {Θ is constant over [l -r, l + r)} versus {Θ contains exactly one change-point at l on the segment [l -r, l + r)}. This corresponds to a two-sample mean testing problem, for which the CUSUM statistic C l,r (Y ) is a sufficient statistic if the noise is Gaussian. Then, given C l,r (Y ), one wants to test whether its expectation is 0 (no change-point on [l -r, l + r)) versus its expectation is non-zero but is s-sparse for some unknown s. This classical detection problem is well understood [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] and it is well known that a combination of a χ 2 -type test with a higher-criticism-type test is optimal. Here, the challenge stems from the fact that we do not want to perform a single such test, but a large collection of tests over a collection of (l, r) ∈ G.

Our contribution

As usual in the mean change-point literature, we consider the energy r k ∆ 2 k of the change-point τ k . Up to a possible factor in [1/2, 1], r k ∆ 2 k is the square distance between Θ and its projection on the space of vectors Θ with change-point at (τ 1 , . . . , τ k-1 , τ k+1 , . . . , τ K ) -see e.g. [START_REF] Verzelen | Optimal Change-Point Detection and Localization[END_REF] for a discussion in the univariate setting. In other words, the energy r k ∆ 2 k characterizes the significance of the change-point τ k . In Section 3, we introduce a multi-scale change-point detection procedure detecting any change-point τ k whose energy is higher, up to a numerical constant, than σ 2 s k log(1+ √ p s k log(n/r k )) + σ 2 log(n/r k ). This result is valid for arbitrary length r k and sparsity s k , and does not require the knowledge of these two quantities. In summary, our procedure does not estimate any spurious change-point (NoSp) and detects all the change-points whose energy are higher than the latter threshold. In Section 5, we establish that, as soon as the unknown number K of the change-points is larger than 1, the condition σ 2 s k log(1 + √ p s k log(n/r k )) + σ 2 log(n/r k ) on the energy is tight with respect to n, p, r k and s k , in the sense that no procedure achieving (NoSp) is able to detect with high probability a change-point whose energy is smaller (up to some constant) than the latter threshold. In Section 4, we consider the more general setting where the noise is L-sub-gaussian with known variance, and we establish a similar result to the Gaussian case up to a logarithmic loss in some regimes. Finally, we illustrate in Section 8 the behavior of our procedure on numerical experiments.

Related work

For dense change-points (s k = p) but with unknown covariance for the noise, Wang et al. [START_REF] Wang | Inference for change points in high dimensional data[END_REF] (see also [START_REF] Wang | Dating the break in high-dimensional data[END_REF]) study the behavior of a procedure based on U -statistics of the CUSUM. Jirak [START_REF] Jirak | Uniform change point tests in high dimension[END_REF] and Yu and Chen [START_REF] Yu | Finite sample change point inference and identification for high-dimensional mean vectors[END_REF] introduce binary segmentation procedures based on the l ∞ norm of the CUSUMs. Although those work explicitly characterize the asymptotic distribution of the test statistics and, for some of them, allow temporal dependencies in the data, the corresponding energy requirements for change-point detection are either not studied or turn out to be suboptimal.

Closest to our work, Chan and Chen [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF] study a bottom-up approach to detect change-points of a Gaussian multivariate time series in an asymptotic setting. More specifically, the authors consider an asymptotic regime where the size of the time series is exponential in the dimension: n = e p ζ with ζ ∈ (0, 1). The authors also assume that the number K of change-points remains finite when n, p → ∞ and that the minimal sparsity s of these change-points is polynomial is p. In this specific regime, their procedures provably recover change-points under a near-minimal (up to logarithmic factors with respect to n) condition on the energy. In contrast, our results provide non-asymptotic and tight results for all scaling with respect to n and p, allow for arbitrarily large number K of change-points and allow for the presence of non-significant change-points. In the same specific asymptotic setting, [START_REF] Hu | Sparsity likelihood for sparse signal and change-point detection[END_REF] introduce a so called score test statistic used in a change-point detection procedure which is shown to achieve the same performance as [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF] in the gaussian model but also handle Poisson observations. Recently, Liu et al. [START_REF] Liu | Minimax rates in sparse, high-dimensional changepoint detection[END_REF] have characterized the optimal detection rate of a possibly sparse change-point in the specific case where there is at most one change-point, but the optimal rates are significantly slower in the multiple change-point setting. See also [START_REF] Enikeeva | High-dimensional change-point detection under sparse alternatives[END_REF] and [START_REF] Holger Dette | Relevant change points in high dimensional time series[END_REF] for earlier results. Wang and Samworth [START_REF] Wang | High dimensional change point estimation via sparse projection[END_REF] have proposed the INSPECT method based on sparse projection to handle sparse change-points, but INSPECT provably detects the change-points under strong assumption on the energy; see Section 3 for a precise comparison.

In the univariate setting (p = 1), minimal energy requirements for change-point detection are well understood [START_REF] Frick | Multiscale change point inference[END_REF][START_REF] Fryzlewicz | Tail-greedy bottom-up data decompositions and fast multiple change-point detection[END_REF][START_REF] Verzelen | Optimal Change-Point Detection and Localization[END_REF][START_REF] Wang | Univariate mean change point detection: Penalization, CUSUM and optimality[END_REF] and are nearly achieved by a wide range of procedures including penalized least-square and multi-scale tests methods.

A Generic algorithm for multiscale change-point detection on a grid

In this section, we study the problem of change-point detection in the general setting defined in Section 1.1. We introduce a bottom-up algorithm that aggregates a collection of homogeneity tests, performed at many positions, and for many scales, of our data. Then, we establish that, under some conditions on these tests, the procedure detects significant change-points.

Grid and multiscale statistics

Since our purpose is to translate a collection of local tests T = (T l,r ) (l,r)∈G indexed by a grid G into a change-point detection procedure, we first need to formalize what we mean by a grid. Henceforth, we call a grid G of [n] a collection of locations and scales where a scale r is a positive integer smaller or equal to n/2 and a location l is an integer between r + 1 and n -r. This couple (l, r) refers to the segment [l -r, l + r) centered at l and with radius r. Formally, G is therefore a subset of J n = (l, r) : r = 1, . . . , n 2 and l = r + 1, . . . , n -r + 1 . Given a grid G, we call R its collection of scales, that is R = {r : ∃l s.t. (l, r) ∈ G}. Finally, for a scale r ∈ R, D r stands for the corresponding collection of locations, that is D r = {l : (l, r) ∈ G}. Although we do not make any assumption on the grid G for the time being, we will mainly consider two specific grids in this section: the complete grid G F = J n and the dyadic grid

G D defined by R = {1, 2, 4, . . . , 2 log 2 (n) -1 }, D 1 = [2, n],
and

D r = r + 1, 3 r/2 + 1, 4 r/2 + 1, . . . , n r/2 -2 r 2 + 1, n -r + 1 for r ∈ R \ {1} . (5)
See Figure 2 for a visual representation of the dyadic grid. At some points, we shall also mention a-adic grids G a . For any a ∈ (0, 1), G a is defined by R = {1, a -1 , a -2 , . . . , a 1-log(n)/ log(a) } and D r as in [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF]. Interestingly, the cardinality of the dyadic grid or more generally of the a-adic grid is order O(n), whereas the complete grid G D is quadratic. Grids are reminiscent of the c-normal systems of intervals introduced by Nemirovsky [START_REF] Nemirovskiy | Nonparametric estimation of smooth regression function[END_REF] (see also [START_REF] Li | Multiscale change-point segmentation: Beyond step functions[END_REF] for a definition) although our definition allows for non-necessarily normal intervals.

Given a fixed grid G, a multiscale test is simply a collection of test T = (T l,r ) (l,r)∈G indexed by the elements of G, which amounts to testing at all scales r ∈ R and all locations l ∈ D r whether the functional Γ(P t ) is constant over the segment [l -r, l + r). Equivalently, T l,r tests whether there exists a change-point in [l -r + 1, l + r -1].

From a multiscale test to a change-point detection procedure

Our purpose is to introduce a generic procedure to translate a multiscale procedure into a vector of change-points. Intuitively, if, for some (l, r) ∈ G, we have T l,r = 1, then the functional Γ(P t ) is certainly not constant over [l -r, l + r) which entails that there is possibly at least one changepoint in [l -r + 1, l + r -1]. As a consequence, the multiscale test gives a collection I(T ) = {[l -r + 1, l + r -1] s.t. T l,r = 1} of intervals that tentatively contain at least one change-point.

If all these intervals were disjoint, then one simply would take τ as the sequence of centers of these intervals. Unfortunately, when two intervals [l 1 -r 1 + 1, l 1 + r 1 -1] and [l 2 -r 2 + 1, l 2 + r 2 -1] in I(T ) have a non-empty intersection, one cannot necessarily decipher whether there is only one change-point in the intersection of both intervals or if each interval contains a specific change-point. Hence, our general objective is to transform the collection I(T ) into a collection of non-intersecting intervals by either discarding or merging some of them. We propose the following bottom-up iterative procedure for building a collection of nonintersecting intervals. Start with T 0 = S 0 = ∅. For any scale r ∈ R, we compute the collections S r of intervals of scale r and the collection T r of locations based on the following

T r =    l ∈ D r , T l,r = 1 and [l -r + 1, l + r -1] r <r, r ∈R S r = ∅ ;    S r = l∈Tr [l -r + 1, l + r -1] .
The sets T 1 and S 1 are made of all positions l such that T l,1 = 1. More generally, T r contains all locations l such that T l,r = 1 and the corresponding interval [l -r + 1, l + r -1] does not intersect with any of the detected intervals at a smaller scale r < r. The set S r contains all intervals associated to T r .

One can easily check that S = r S r is a union of closed non-intersecting intervals. Denote C = {C 1 , . . . , C K } the partition of S into connected components such that, for all 1 ≤ i < j ≤ K, max C i < min C j . Finally, we estimate the vector of change-points τ by taking the center of each segment C k . In other words, we take τk := 1 2 (min C k +max C k ) for any 1 ≤ k ≤ K. This bottom-up aggregation procedure is summarized in Algorithm 1 and illustrated in Figure 3 below.

Remark: If, for some r ∈ R and some l 1 < l 2 ∈ D r , we have T l 1 ,r = 1, T l 2 ,r = 1, and l 1 + r -1 ≥ l 2 -r + 1, then S r contains the segment [l 1 -r + 1, l 2 + r -1]. In other words, our aggregation procedure merges two intervals if and only if they correspond to the same scales. In Section A, we also introduce a variant of the algorithm where, instead of merging these two intersecting with identical scale, we discard one of them. Computational Cost. A naive implementation of Algorithm 1 -and also of Algorithm 2 defined in Appendix -requires to compute all tests T l,r on the grid, whereas the aggregation procedure only needs to compute a number of tests T l,r proportional to the size of the grid. More precisely, if the Data: y t , t = 1 . . . n and local test statistics (T l,r ) (l,r)∈G Result:

(τ k ) k≤ K T r , S r = ∅ for all r ∈ R and S = ∅; for increasing r ∈ R do for l ∈ D r s.t. T l,r = 1 do if [l -r + 1, l + r -1] S = ∅ then T r ← T r ∪ {l}; S r ← S r ∪ [l -r + 1, l + r -1]; end end S = S S r ; end Let (C k ) k=1,.
.., K be the connected components of S sorted in increasing order;

return τk = 1 2 (min C k + max C k ) k=1,...,

K

Algorithm 1: Bottom-up aggregation procedure of multiscale tests computational cost of T l,r is Λ l,r for each (l, r) in the grid G, then the aggregation procedure requires O( (l,r)∈G Λ l,r ) computations. If for all (l, r), the cost Λ l,r is proportional to r, that is Λ l,r = O(rΛ), then the overall computational cost is O(Λ (l,r)∈G r) which is O(Λn 3 ) for the complete grid and O(Λn log(n)) for the dyadic grid. One can speed up the full procedure by computing the statistics T l,r and aggregating on the fly by checking whether [l -r + 1, l + r -1] intersects S before evaluating T l,r = 1. Indeed, the connected components C k can be computed at each increasing scale r. Hence, at scale r, one only needs to compute the tests T l,r at locations l such that [l -r + 1, l + r -1] does not intersect the connected components detected at scales r < r.

General analysis

In this subsection, we provide an abstract theorem translating error controls of the multiple test procedure T in terms of properties of τ . As explained in the introduction, the time series (y t ) may contain change-points that are too small to be detected. Having this in mind, we define a subset K * ⊂ [K] of indices corresponding to so-called significant change-points. As our purpose is to provide deterministic condition so that the change-points in K * , we need to introduce, for each k ∈ K * , an element of the grid (τ k , rk ) ∈ G at which the statistic T is expected to detect τ k . One could think of τk as some position close to τ k and to rk as some radius which is large enough to convey information on the change-point. Recall that the length r k of the change-point τ k is defined by

r k = min(τ k+1 -τ k , τ k -τ k-1
). We assume that the scales rk and the location τk of detection satisfy the two following conditions:

4(r k -1) < r k and |τ k -τ k | ≤ rk -1. (6)
The first condition ensures that the scale rk < r k /4 + 1 is small enough compared to the length r k . The second condition is always satisfied if τk is the best approximation of τ k in D rk and if the grid G satisfies the following approximation property (App): For all r ∈ R and all l ∈ [r + 1, n -r + 1], there exists l ∈ D r such that |l -l| ≤ r -1.

This property entails that any point l can be approximated at distance r -1 by some location in D r . This also implies that each point l ∈ [r + 1, n -r] belongs to at least one segment (l -r, l + r) where l 1 lies in D r . In practice, the a-adic grids G a and the complete grid satisfy (App). Next, we introduce an event on the tests (T l,r ) under which the change-point estimator τ of Algorithm 1 performs well. In the following, we write H 0 , the collection of all possible (l, r) ∈ J n such that there is no change in [l -r +1, l +r -1], i.e. Γ(P t ) is constant on [l -r, l +r). Equivalently, we have (l, r) ∈ H 0 iff (l -r, l + r) ∩ {τ k , k = 1, . . . , K} = ∅ .

For a collection K * and some elements of the grid (τ k , rk ) satisfying (6), the Event A (T, K * , (τ k , rk ) k∈K * ) is defined as the conjunction of the two following properties: (i) (No false positive) T l,r = 0 for all (l, r) ∈ H 0 ∩ G (ii) (Detection of significant change-points) for every k ∈ K * , we have T τk ,r k = 1.

The first property states that T performs no type I errors on the event A (T, K * , (τ k , rk ) k∈K * ), whereas the second property enforces that all the significant change-points are detected by the specific tests T τk ,r k . Theorem 1. The following holds for any grid G, any local test statistic T , any non-negative integer K, any distribution with K change-points, any K * ⊂ [K] and scales and locations (τ k , rk ) k∈K * in G satisfying Assumption [START_REF] Peng Chan | Optimal detection of multi-sample aligned sparse signals[END_REF]. Under the event A(T, K * , (τ k , rk ) k∈K * ), the estimated change-point vector τ returned by Algorithm 1 satisfies the two following properties • Significant change-points are detected: for all k ∈ K * , there exists k ≤ K such that

|τ k -τ k | ≤ rk -1 < r k 4 .
• (NoSp): No Spurious change-point is detected (1).

The first property states that so-called significant change-points (τ k ) k∈K * are detected by the generic algorithm at the right scale. The no-spurious property (1) guarantees that, around any true change-point τ k , the procedure estimates at most one single change-point τ l . Importantly, the theorem does not make any assumption on the non-significant change-points. In fact, change-points τ k with k ∈ [K] \ K * may or may not be detected. In general, we can only conclude from Theorem 1 that |K * | ≤ K ≤ K on the event A (T, K * , (τ k , rk ) k∈K * ) .

Theorem 1 is abstract but its main virtue is to translate multiple testing properties into changepoint detection properties. For a specific problem such as multivariate mean change-point detection considered in the next section, the construction of a near optimal procedure boils down to introducing a collection of local test statistics, such that (a) change-points τ k belong to K * under minimal conditions, (b) the scale rk is the smallest possible, and (c) the event A(T, K * , (τ k , rk ) k∈K * ) holds with high probability.

In the case where all the change-points are significant, the result of Theorem 1 can be reformulated as follows:

Corollary 1. The following holds for any grid G, any local test statistic T , any non-negative integer K, any distribution with K change-points, any (τ k , rk ) k=1,...,K in G satisfying Assumption [START_REF] Peng Chan | Optimal detection of multi-sample aligned sparse signals[END_REF]. Under the event A(T, [K], (τ k , rk ) k=1,...,K , the estimated change-point vector τ returned by Algorithm 1 satisfies K = K and,

|τ k -τ k | < rk -1 ≤ r k 4 for all k = 1, . . . , K .
Let us respectively define the Hausdorff distance and the Wasserstein distance of two vectors (u 1 , . . . , u K ) and (v 1 , . .

. , v K ) in R K by d H (u, v) = max k=1,...,K |u k -v k | and d W (u, v) = k=1,...,K |u k -v k |. Then, Corollary 1 straightforwardly implies that, if K * = [K]
, then these two losses are bounded as follows

d H (τ , τ ) ≤ max k=1,...,K (r k -1) and d W (τ , τ ) ≤ k=1,...,K (r k -1) .
As an alternative of Algorithm 1, one could use other bottom-up aggregating procedures. For instance, Algorithm 2 defined in Appendix A also satisfies Theorem 1. Although these two algorithms are closely related, Algorithm 1 is slightly more conservative than Algorithm 2 since it merges all detection intervals at a given resolution while Algorithm 2 only keeps one interval at a given resolution when multiple intervals intersect -the one with smallest index t. While the minimax properties of both methods are comparable -at least up to a multiple constant -the choice of aggregation method will have an influence in practice on the outcome: Algorithm 1 will be slightly more stable, detect less change-points, and provide wider confidence interval around them, while Algorithm 2 will be slightly more sensitive to smaller changes, i.e. detect smaller change-points, will be more precise, and somewhat less stable.

Theorem 1 ensures that, if T τ k ,r k = 1 with (τ k , r k ) satisfying Assumption [START_REF] Peng Chan | Optimal detection of multi-sample aligned sparse signals[END_REF], then the changepoint τ k is detected. Inspecting the proof of Theorem 1, one easily checks that Assumption (6) is minimal for Algorithm 1 (and also for Algorithm 2). Still, one may wonder whether any generic algorithm has to require that 4(r k -1) < r k to detect the change-points or if there exists a generic algorithm where the constant 4 in the above condition can be improved.

Comparison with narrowest over threshold methods. As mentioned in the introduction, other aggregation procedures have been proposed in the literature. In particular, the narrowest over threshold scheme proposed by [START_REF] Baranowski | Narrowest-over-threshold detection of multiple change points and change-point-like features[END_REF] and later used in [START_REF] Kovács | Seeded binary segmentation: A general methodology for fast and optimal change point detection[END_REF] is also closely related to the local segmentation algorithm of Chan and Chen [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF]. A simple extension of these procedures for generic change-point problems and for a general collection of tests (T l,r ) would amount to modifying Algorithm 1 by selecting locations l in D r such that T l,r = 1 and [l -r + 1, l + r -1] does not intersect previously detected change-points, whereas we require in Algorithms 1 and 2, that [l-r +1, l+r -1] does not intersect previously detected confidence intervals. In some way, the narrowest-over threshold scheme is therefore less conservative. Unfortunately, there is no generic result in the form of Theorem 1 for such procedures and, from informal arguments, we doubt that the corresponding procedure provably achieves (NoSp) under a control of the FWER of the tests. Inspecting the proof of Theorem 1 in [START_REF] Baranowski | Narrowest-over-threshold detection of multiple change points and change-point-like features[END_REF] and Theorem 3 in [START_REF] Kovács | Seeded binary segmentation: A general methodology for fast and optimal change point detection[END_REF] for univariate mean change-point problems, one observes that the chosen threshold is much larger than what is needed to control the FWER so that the theoretical threshold is certainly over-conservative -see step 5 of the proof of Theorem 1 in [START_REF] Baranowski | Narrowest-over-threshold detection of multiple change points and change-point-like features[END_REF]. In contrast, Theorem 1 in [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF] for univariate change-point problems is based on the minimal threshold, but the proof relies on the important assumption that the number K of change-point remains bounded while n goes to infinity. Besides, it is not clear how one could extend the arguments to more general settings.

Multivariate Gaussian change-point detection

We now turn to the multivariate change-point model introduced in Section 1.2. Throughout this section, we assume that the random vectors ε t are independently and identically distributed with ε t ∼ N (0, σ 2 I p ). Since we shall apply the general aggregation procedures introduced in the previous section, our main job here is to introduce a near-optimal testing procedure.

Fix some quantity δ ∈ (0, 1). At the end of the section, 1 -δ will correspond to the probability of the event A (T, K * , (τ k , rk ) k∈K * ) introduced in the previous section. Alternatively, one may interpret δ as an upper bound of the desired probability that the change-point detection procedure detects a spurious change-points. Recall that, for a change-point τ k , s k stands for the sparsity of the difference µ k+1 -µ k . The energy of a given change-point τ k is c 0 -high if

r k ∆ 2 k ≥ c 0 σ 2 s k log 1 + √ p s k log n r k δ + log n r k δ , (8)
for some universal constant c 0 to be defined later. We show in this section that when c 0 is large enough, all high-energy change-points can be detected. Conversely, it is established in Section 5 that Condition ( 8) is (up to a multiplicative constant) optimal for detecting change-points and cannot be weakened.

Let us now discuss the different regimes contained in Equation [START_REF] Chu | Asymptotic distribution-free change-point detection for multivariate and non-euclidean data[END_REF]. In what follows, define

ψ (g) n,r,s := s log 1 + √ p s √ γ r + γ r ; γ r := log n rδ , in order to alleviate notations. If γ r ≥ p/2, then ψ (g) n,r,s
γ r where u v means that for two positive numerical constants c 1 and c 2 , one has c 1 v ≤ u ≤ c 2 v. This corresponds to the minimal energy condition for detection in the univariate case, i.e. when p = 1; see [START_REF] Verzelen | Optimal Change-Point Detection and Localization[END_REF]. The condition γ r ≥ p/2 occurs when p is rather small and the scale r is much smaller than n. If γ r ≤ p/2, then

ψ (g) n,r,s      γ r if s ≤ γr log(p)-log(γr) s log 2 p s 2 γ r if γr log(p)-log(γr) < s < √ pγ r √ pγ r if s ≥ √ pγ r .
We define K * ⊂ [K] as the subset of indices such that τ k satisfies [START_REF] Chu | Asymptotic distribution-free change-point detection for multivariate and non-euclidean data[END_REF]. For any k ∈ K * , we define r * k as the minimum radius r such that an inequality similar to ( 8) is satisfied for r∆ 2 k , namely

r * k = min r ∈ R + : r∆ 2 k ≥ c 0 σ 2 s k log 1 + √ p s k log n rδ + log n rδ . (9)
In the following, we introduce multi-scale tests for respectively dense and sparse change-points. For simplicity, we restrict our attention to the dyadic grid G D = (R, D) introduced in the previous section (see Equation ( 5)), the complete grid being used in the next section.

To apply Theorem 1, we will consider an event A (T, K * , (τ k , rk ) k∈K * ) in the proof of Corollary 2 where the scale rk ∈ R is of the same order as r * k ∈ R + .

Dense change-points

We focus here on dense change-points for which s k is possibly as large as p. Given κ > 0, τ k is a κ-dense high-energy change-point if

r k ∆ 2 k ≥ κσ 2 p log n r k δ + log n r k δ . ( 10
)
The requirement ( 10) is analogous to (8) when s k ≥ [p log(n/(r k δ))] 1/2 . For any κ-dense highenergy change-point, we define r(d) k ∈ R as the minimum radius r ∈ R such that an inequality of the same type as [START_REF] Holger Dette | Estimating a change point in a sequence of very high-dimensional covariance matrices[END_REF]

is satisfied for r∆ 2 k , r(d) k = min r ∈ R : 8r∆ 2 k ≥ κσ 2 p log n rδ + log n rδ . Intuitively, r (d)
k corresponds to the smallest scale such that τ k is guaranteed to be detected. By definition, we have 4(r

(d) k -1) ≤ r k . Let τ (d) k
be the best approximation of τ k in the grid with scale r(d)

k . By definition of the dyadic grid, we have |τ

(d) k -τ k | ≤ r(d) k /4. For any positive integers r ∈ [1; n] and l ∈ [r + 1, n + 1 -r], we define the statistic Ψ (d) l,r := C l,r 2 -p. If θ is constant over [l -r, l + r), then the expectation of Ψ (d)
l,r is zero. Recall that the rescaled CUSUM statistic C l,r depends on the noise level σ, and the statistic Ψ

T (d) l,r := 1 Ψ (d) l,r > x (d) r ; x (d) r := 4 p log 2n rδ + log 2n rδ .
Proposition 1. There exists a universal constant κ d > 0 and an event ξ (d) of probability larger than 1 -2δ such that (i)

T (d) l,r = 0 for all (l, r) ∈ H 0 ∩ G D and (ii) T (d) τ (d) k ,r (d) k
= 1 for all κ d -dense high-energy change-point τ k .

The above proposition ensures that, on the event ξ (d) , the collection of tests T

Sparse change-points

Energy condition

For a given 1

≤ k ≤ K, the change-point τ k is a κ-sparse high-energy change-point if s k ≤ [p log(n/(r k δ))] 1/2 and r k ∆ 2 k ≥ κσ 2 s k log p s 2 k log n r k δ + log n r k δ . ( 11
)
If τ k is a κ-sparse high-energy change-point, we define r(s) k as the minimum scale such that an inequality similar to [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] is satisfied :

r(s) k = min r ∈ R : 8r∆ 2 k ≥ κσ 2 s k log p s 2 k log n rδ + log n rδ .
As in the dense case, we have 4(r

(s) k -1) ≤ r k . Set τ (s)
k as the best approximation of τ k in the grid D r(s) k at scale τ k . By definition of the dyadic grid, we have |τ

(s) k -τ k | ≤ r(s) k /4.
We introduce below two statistics for handling this problem.

Berk-Jones Test

The Berk-Jones test [START_REF] Moscovich | On the exact berk-jones statistics and their p-value calculation[END_REF] is a variation of the Higher-Criticism test originally introduced in [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] for signal detection. It has been previously studied in [START_REF] Peng Chan | Optimal detection of multi-sample aligned sparse signals[END_REF] for sparse segment detection. We decided to use the Berk-Jones test in this paper because of its intrinsic formulation in terms of the quantiles of a Bernoulli distribution, but the Higher-Criticism test would reach the same rates of detection within a constant factor. We use the notation N * to denote the set of positive itegers. Given (l, r) in the grid G D , we first introduce N x,l,r as the number of coordinates of C l,r that are larger than x in absolute value.

N x,l,r = p i=1 1 |C l,r,i |>x (12)
If (l, r) ∈ H 0 , then the rescaled CUSUM statistic follows a standard normal distribution and N x,l,r therefore follows a Binomial distribution with parameters p and 2Φ(x). The Berk-Jones test amounts to rejecting the null, when at least one of the statistics N x,l,r , for x ∈ N * , is significantly large. Next, we formalize what we mean by 'large'.

For any u > 0, any q 0 ∈ [0, 1], and positive integer p 0 , denote Q(u, p 0 , q 0 ) = P[B(p 0 , q 0 ) > u] the tail distribution function of a Binomial distribution with parameters p 0 and q 0 . Given δ ∈ [0, 1], we then write Q -1 (δ, p 0 , q 0 ) for the corresponding quantile function,

Q -1 (δ, p 0 , q 0 ) = inf u [P[B(p 0 , q 0 ) > u] ≤ δ] .
Given a scale r ∈ R and a positive integer x, we define the weights

δ (BJ) x,r = 6δr π 2 x 2 |D r |n . ( 13
)
This allows us to define the Berk-Jones statistic over [l -r, l + r) as the test rejecting the null when at least one N x,l,r is large.

T (BJ) l,r = max x∈N * 1 N x,l,r > Q -1 (δ (BJ) x,r , p, 2Φ(x)) . (14)
Equivalently, T

(BJ) l,r
is an aggregated test based on the statistics N x,l,r with weights δ (BJ)

x,r . From the above remark and a union bound, we deduce that the probability that the collection of tests {T (BJ) l,r , (l, r) ∈ G D } rejects a least one false positive is at most δ:

P max (l,r)∈H 0 ∩G D T (BJ) l,r = 1 ≤ r∈R l∈Dr x∈N * δ (BJ) x,r ≤ r∈R l∈Dr δr |D r |n ≤ r∈R δr n ≤ δ ,
where we recall that (l, r) ∈ H 0 if and only if Θ is constant on [l -r, l + r). Although one may think from the definition ( 14) that T

(BJ) l,r
involves an infinite number of N x,l,r , this is not the case.

Indeed, N x,l,r is a non-increasing function of x whereas for all x such that 2pΦ(x) ≤ δ

(BJ)
x,r , we have

Q -1 (δ (BJ)
x,r , p, 2Φ(x)) = 0. Writing x 0,r the smallest x such that 2pΦ(x) ≤ δ

(BJ)
x,r we derive

T (BJ) l,r = max x=1,...,x 0,r 1 N x,l,r > Q -1 (δ (BJ) x,r , p, 2Φ(x)) .
Since, for any x > 0, we have Φ(x) ≤ e -x 2 /2 , one can deduce that x 0,r ≤ c[log(np/(rδ))] 1/2 , for some numerical constant c > 0.

Partial norm statistics

The Berk-Jones test is able to detect change-points τ k for which there exists s such that the s largest squared coordinates of µ k -µ k-1 are larger than C(log(ep/s 2 ) + log(n/r k )/s) with a large enough constant C. However, it may happen that τ k satisfies the energy condition ( 8) and that the s largest coordinates of µ k -µ k-1 are negligible compared to log(n/r k )/s, mainly because s → 1/s is not summable. To solve this issue, we introduce a second sparse statistic based on the partial sums. Let

Z = 1, 2, 2 2 , . . . , 2 log 2 (p)
denote the dyadic set. Only the sparsities s ∈ Z will be analysed by the partial norm statistic. For any (l, r) in the grid G D , we respectively write C l,r,(1) , C l,r,(2) , . . . the reordered entries of C l,r by decreasing absolute value, that is

|C l,r,(1) | ≥ • • • ≥ |C l,r,(p) |.
Then, for s ∈ Z, we define the partial CUSUM norm by

Ψ (p) l,r,s = s i=1 C l,r,(i) 2 . (15)
Then, we define the test

T (p)
l,r rejecting the null when at least one of the partial norms is large

x (p) r,s := x (p) r,s (δ) = 4s log 2ep s + 4 log n rδ ; T (p) l,r = max s∈Z 1 Ψ (p) l,r,s > x (p) r,s
.

Finally, we define the sparse test by aggregating both the Berk-Jones test and the partial norm test. For any (l, r) ∈ G D , let T Proposition 2. There exists a universal constant κ s > 0 and an event ξ (s) of probability larger than 1 -4δ such that (i)

T (s) l,r = 0 for all (l, r) ∈ H 0 ∩ G D and (ii) T (s) τ (s) k ,r (s) k = 1 for all κ s -sparse high-energy change-point τ k .
Here we introduced two different statistics for the same sparse regime s k ≤ [p log(n/(r k δ))] 1/2the Berk-Jones statistic and the partial sums statistic -mainly to solve a problem of integrability. We made this choice for the sake of simplicity, but we could have used a single test, as presented in [START_REF] Liu | Minimax rates in sparse, high-dimensional changepoint detection[END_REF] Ψ

(LGS) x,l,r = p i=1 C 2 l,r,i -E [Z|Z ≥ x] 1{C 2 l,r,i ≥ x} ,
where Z follows a standard normal distribution N (0, 1). This statistic leads to the same type of result as the Berk-Jones statistic when enough coordinates µ k -µ k-1 are large in absolute value, and it is comparable to the partial sums statistic when its threshold x becomes low enough.

Consequences

To conclude this section, it suffices to observe that, for c 0 in ( 8), any c 0 -high-energy change-point τ k in the sense of ( 8) is either a c 0 2 -dense or a c 0 2 -sparse high-energy change-point. Hence, upon defining the test T l,r = T

(d) l,r ∨ T (s)
l,r for (l, r) ∈ G D , we consider the change-point procedure τ defined in Algorithm 1. Gathering Theorem 1 with Proposition 1 and Proposition 2, we obtain the following.

Corollary 2. There exists a universal constant c 0 > 0 such that, with probability higher than 1-6δ, the estimator τ satisfies (NoSp) and detects all c 0 -high-energy change-points (as defined in (8))

τ k in the sense d H,1 (τ , τ k ) < r * k 2 ≤ r k 2 ,
where r * k is defined in [START_REF] Holger Dette | Relevant change points in high dimensional time series[END_REF].

If the change-points are of high-energy, that is K * = [K], then Corollary 2 can be reformulated as follows:

Corollary 3. Assume that for all k = 1, . . . , K, τ k is a c 0 -high-energy change-point (see [START_REF] Chu | Asymptotic distribution-free change-point detection for multivariate and non-euclidean data[END_REF]) where c 0 is the same as in Corollary 2. Then, with probability higher than 1 -6δ, the estimator τ satisfies K = K and

|τ k -τ k | < r * k 2 ≤ r k 2 , for all k = 1, . . . , K .
In particular, one can respectively bound the Hausdorff and the Wasserstein losses, with probability higher than 1 -6δ by

d H (τ , τ ) ≤ max k=1,...,K r * k 2 and d W (τ , τ ) ≤ k=1,...,K r * k 2 . ( 16
)
In Section 5, we establish that the Condition ( 8) is (up to a multiplicative constant) unimprovable and corresponds to the detection threshold for multivariate change-points.

Corollary 3 can be compared to the result of [START_REF] Wang | High dimensional change point estimation via sparse projection[END_REF] on multivariate change-point detection in the multiple change-point setting. Using a method based on the CUSUM statistic and assuming that there are only high-energy change-points, the authors also obtain an upper bound on the energy necessary to detect the change-points. However, this result does not adapt to r k , ∆ k , s k , and the detection rate is suboptimal in many regimes. Writing r = min k=1,...,K r k , ∆ = min k=1,...,K ∆ k and s = max k=1,...,K s k , Theorem 5 of [START_REF] Wang | High dimensional change point estimation via sparse projection[END_REF] requires two conditions of the type r∆ 2 ≥ c( n r ) 4 log(np) and r∆ 2 ≥ cs n r log(np). This detection rate is therefore suboptimal by a polynomial factor in n/r when r is of smaller order than n, and by a logarithmic factor log(np) instead of log(1 + √ p/s log(n/r)) + 1 s log(n/r) when r is of order n. Closer to our results, [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF] have introduced another bottom-up procedure in the very specific asymptotic setting n = e p ζ for ζ ∈ (0, 1) with a fixed K number of change-points. Assuming that, for each change-point, at least s coordinates of µ k+1 -µ k+1 are larger than ζ in absolute value, [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF] establish that their procedure provably detects the change-points as long as

rsζ 2 ≥ c p log(n) if s ≥ 0.5 p log(n) s log p s 2 log (n) if s ≤ 0.5 p log(n) .
In their specific asymptotic regime and when all non-zero coordinates are of the same order, and all the change-points have a similar length r k , their result is similar to ours up to the logarithmic terms. Indeed, for equispaced change-points, our logarithmic term log(n/r k ) = log(K) is much smaller than log(n). Besides, their result does not handle the presence of low-energy change-points and does not hold beyond the asymptotic regime n = e p ζ . In contrast, our condition (8) for high-energy change-points entails that the detection conditions are qualitatively different for other scalings in n and p. On the technical side, our condition ( 8) is of l 2 type whereas that in [START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF] is of minimal non-zero type. Recovering the tight l 2 conditions turns out to be much more challenging as we need to handle situations where some coordinates have different orders of magnitude. This is the main reason why we need to resort to a combination of the Berk-Jones and the partial-norm statistics.

Comparison to one change-point problem. When one knows that K ≤ 1 (at most one change-point), then [START_REF] Liu | Minimax rates in sparse, high-dimensional changepoint detection[END_REF] proved that it is possible to detect τ 1 if and only if

r 1 ∆ 2 1 ≥ cσ 2 s 1 log(1 + 1 s 1
√ p log log 8n) + log log 8n . As in the univariate setting, the problem with only one change-point is simpler than for general K ≥ 2. As for our procedure, Liu et al. [START_REF] Liu | Minimax rates in sparse, high-dimensional changepoint detection[END_REF] rely on statistics based on the CUSUM -a chi square statistics in the dense case and a thresholded sum of squared coordinates in the sparse case -to detect and localize τ 1 . It turns out that the detection procedure of [START_REF] Liu | Minimax rates in sparse, high-dimensional changepoint detection[END_REF] adapts to distance r 1 = max(τ 1 -1, n + 1 -τ 1 ) the boundary, and one could refine their result by stating that τ 1 is detectable if and only if

r 1 ∆ 2 1 ≥ cσ 2 [s 1 log(1 + 1 s 1
p log log(2n/r 1 )) + log log(2n/r 1 )] which is more smaller when r 1 is of the order of n. This refined result is in the same spirit as our bounds for mutiple change-point, but the rate is faster because one obtains log log(n/r 1 )instead of log(n/r k ) in our case. The reason for this faster rate is due to the relative simplicity of the problem with only one change-point. Indeed, in single change-point detection, there is no need to look for change-points at all positions and scale at the same time, since scale and positions are related. This implies that it is possible to attain faster rates than in multiple change-point detection. The comparison between single and multiple change-point detection is thoroughly done in [START_REF] Verzelen | Optimal Change-Point Detection and Localization[END_REF] for univariate models.

Computational Cost. The cost of the tests T (d)

l,r in the dense regime is O(rp). The computation of the partial norm statistic requires to sort the coordinates C l,r,i of the CUSUM statistic, which takes O(p(r + log(p))) operations. Since only the thresholds x ≤ c log(np/(rδ)) 1/2 are needed to compute the Berk-Jones statistic, it holds that, for δ ≥ (np) -c with a numerical constant c > 0, the computational cost of the Berk-Jones statistic is O(p(r + log(np))). Thus, for each (l, r), the overall computational cost of the test T l,r = T

Multi-scale change-point detection with sub-Gaussian noise

We now turn to the more general case of sub-Gaussian distributions [START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF]. Given a random variable Z, define its ψ 2 -norm by Z ψ 2 = inf{x > 0, E[exp(Z2 /x 2 )] ≤ 2} . Given L > 0, a mean zero real random variable is said to be L-sub-Gaussian if Z ψ 2 ≤ L. This implies in particular that, for all x ≥ 0, one has P (|Z| ≥ x) ≤ 2 exp(-x 2 /L 2 ). Throughout this section, we assume that, for t = 1, . . . , n, the random vectors ε t are independent, have independent L-sub-Gaussian components ε t,i , for i = 1, . . . , p with variance σ 2 . As in the previous section, we apply the general aggregation procedures introduced in Section 2. As a consequence, our main task boils down to introducing a near-optimal multiple testing procedure indexed by a grid for detecting the existence of a change-point. Here, we shall rely on the complete grid G F = J n = (l, r) : r = 1, . . . , n 2 and l = r + 1, . . . , n -r whose size is quadratic with respect to n. All the results presented in this section are still valid (but with different numerical constants) if we keep the dyadic grid G D as in the previous section. Here, we use the complete grid as a proof of concept that one can rely on the full collection of possible segments without deteriorating the rates. Still, controlling the behavior of the procedure on the complete grid is technically more involved and requires chaining arguments. A detailed comparison between the complete and dyadic grids is made in Section 7.

In order to emphasize the common points with the previous section, we use the same notation K * for the collection of high-energy change-points1 , rk for the scales associated to the k-th changepoints 2 , Ψ for the statistics, T for the test and x for the thresholds although these quantities are slightly changed to cope with the sub-Gaussian tail distribution. We follow the same scheme as for the Gaussian case and first introduce multi-scale tests for dense change-points before turning to sparse change-points. As in the previous section, we consider some δ ∈ (0, 1) corresponding to the type I error probability.

Dense change-points with sub-Gaussian noise

Recall that, for a change-point τ k , s k stands for the sparsity of the difference µ k+1 -µ k . We focus here on dense change-points for which s k is possibly as large as p. Given κ > 0, τ k is a κ-dense high-energy change-point if

r k ∆ 2 k ≥ κL 2 p log n r k δ + log n r k δ . ( 17
)
This condition is very similar to its counterpart [START_REF] Holger Dette | Estimating a change point in a sequence of very high-dimensional covariance matrices[END_REF] for Gaussian noise. Still, we introduce it here for the sake of completeness. For k ∈ [K] such that τ k is a κ-dense high-energy change-point, we define r(d) k as the minimum length such that an inequality similar to ( 17) is satisfied :

r(d) k = min r ∈ N * : 4r∆ 2 k ≥ κL 2 p log n rδ + log n rδ .
As in the Gaussian case in Section 3, r(d) k corresponds to the smallest scale such that τ k is guaranteed to be detected. For any κ-dense high-energy change-point, it holds that 4(r

T (d) l,r := 1 Ψ (d) l,r > x (d) r ; x (d) r = c(d) thresh L 2 σ 2 p log n rδ + log n rδ .
Proposition 3. There exists a numerical constant c(d) thresh > 0 such that the following holds for any κ d > 32c In comparison to Proposition 1 in the previous section, there are two differences. First, we need to cope with sub-Gaussian distribution by applying the Hanson-Wright inequality. Most importantly, the grid G F is much larger than G D so that we cannot simply consider each test T l,r separately and simply apply a union bound as in the previous section. To handle the dependencies between the statistics Ψ (d) l,r , we have to apply a chaining argument. In fact, the thresholds x (d) r are similar to their counterpart in the previous section, whereas the number |G F | of tests is now proportional to n 2 . In principle, the benefit of using the full grid G F is that (τ k , r(d) k ) belongs to G F so that we can consider the CUSUM statistic based on a segment [τ k -r

(d) k , τ k +r (d) k ] centered around the change-point τ k . In contrast, (τ k , r(d) k )
does not necessarily belong to the dyadic grid G D and we needed to consider its best approximation (τ

(d) k , r(d) k ). The segment [τ (d) k -r (d) k , τ (d) k +r (d)
k ] is therefore not centered on τ k and the corresponding statistic Ψ

(d) τ (d) k ,r (d) k is in expectation smaller than Ψ (d) τ k ,r (d) k
. In summary, both the collections of dense tests Ψ (d) l,r on G D and G F are able to detect change-points whose energy is, up to some multiplicative constants, higher than

L 2 [[p log( n r k δ )] 1/2 + log( n r k δ )].

Sparse change-points with sub-Gaussian noise

Unlike in the Gaussian case, we do not know the exact distribution of the noise. As a consequence, the Berk-Jones test and more generally higher-criticism type tests cannot be applied to this setting. This is why we only rely on the partial norm statistic. Recall that Z = 1, 2, 2 2 , . . . , 2 log 2 (p) stands for a dyadic set of sparsities. For (l, r) ∈ G F and s ∈ Z, we also recall that the partial CUSUM norm is defined as

Ψ (p) l,r,s = s i=1 C l,r,(i) 2 .
Then, for any (l, r) ∈ G F , the test T (p) l,r rejects the null when at least one of the partial norms is large

x (p) r,s = s + c(p) thresh L 2 σ 2 s log 2ep s + log n rδ ; T (p) l,r = max s∈Z 1 Ψ (p) l,r,s > x (p) r,s
, where c(p) thresh is a tuning parameter in Proposition 4 below. The partial norm test alone is not able to detect sparse high-energy change-points in the sense of [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] and we need to introduce a stronger condition on the energy. Given κ > 0, a change-point τ k is a κ-sparse high-energy change-point in the sub-Gaussian setting if

s k ≤ [p log( n r k δ )] 1/2 and r k ∆ 2 k ≥ κL 2 s k log ep s k + log n r k δ . ( 18
)
Both Conditions [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF] and ( 18) are compared at the end of the subsection. For a κ-sparse highenergy change-point τ k , we define its scale r(s)

k by r(s) k = min r ∈ N * : 4r∆ 2 k ≥ κL 2 s k log ep s k + log n rδ . (19)
For any κ-sparse high-energy change-point, it holds that 4(r

(s) k -1) ≤ r k .
Proposition 4. There exists a numerical constant c(p) thresh > 0 such that the following holds for any κ s > 32c (p) thresh . With probability higher than 1 -δ, one has (i)

T (p) l,r = 0 for all (l, r) ∈ G F ∩ H 0 and (ii) T (p) τ k ,r (s) k
= 1 for all κ s -sparse high-energy change-point τ k in the sense of [START_REF] Gretton | A kernel two-sample test[END_REF].

As for Proposition 3, the proof relies on a careful analysis of the joint distributions of the statistics Ψ (p) l,r,s to handle the multiplicity of G F .

Consequences

Let c 0 > 0 be some constant that we will discuss later. A change-point τ k is then said to be a c 0 -high-energy change-points -in the sub-Gaussian setting-if

r k ∆ 2 k ≥ c 0 L 2 p log n r k δ ∧ s k log ep s k + log n r k δ . ( 20
)
We here re-introduce K * ⊂ [K] as the subset of indices such that τ k satisfies [START_REF] Hu | Sparsity likelihood for sparse signal and change-point detection[END_REF]. We gather both tests by considering, for any (l, r) ∈ G F , the test T l,r = T

= r(d) k ∧ r(s) k , (21)
we straightforwardly derive from Proposition 3 and Proposition 4 the following result.

Corollary 4. There exists two numerical constants c(p) thresh > 0 and c(d) thresh > 0 such that the following holds. With probability higher than 1 -δ, it holds that (i) T l,r = 0 for all (l, r) ∈ G F ∩ H 0 and (ii) T τ k ,r k = 1 for any c 0 -high-energy change-point τ k in the sense of [START_REF] Hu | Sparsity likelihood for sparse signal and change-point detection[END_REF].

Then, it suffices to combine this multiple testing procedure with Algorithm 1 to get the changepoint procedure τ . Since, for a high-energy change-point in the sense of (20), we have 4(r k -1) < r k , we are in position to apply Theorem 1.

Corollary 5. There exist two numerical constant c(p) thresh > 0 and c(d) thresh > 0 such that the following holds. With probability higher than 1 -δ, the estimator τ satisfies (NoSp) and detects c 0 -highenergy change-point τ k (as defined in( 20)), that is

d H,1 ( τ , τ k ) ≤ rk -1 ≤ r k 4 ,
where rk is defined in [START_REF] Jirak | Uniform change point tests in high dimension[END_REF].

In the case where all change-points are c 0 -high-energy change-points in the sense of [START_REF] Hu | Sparsity likelihood for sparse signal and change-point detection[END_REF], all of them are detected, and a result similar to Corollary 3 holds here, replacing r * k /2 by rk -1. Also, both the Hausdorff distance and the Wasserstein distance, can be bounded as in Equation ( 16) if we replace r * k /2 by rk -1. As already stated, we could have obtained a similar result (but with different constants) using the dyadic grid G D instead of G F . To conclude this section, let us compare the conditions ( 20) and (8) for high-energy. Define

ψ (sg) n,r,s = √ pγ r ∧ s log ep s + γ r ,
where we recall that γ r = log n rδ . If γ r ≥ p/2, then ψ (sg) n,r,s γ r . In low dimension, the energy threshold for multivariate change-point detection is the same as in the univariate setting, see [START_REF] Verzelen | Optimal Change-Point Detection and Localization[END_REF]. If γ r ≤ p/2, then

ψ (sg) n,r,s      γ r if s ≤ γr log(p)-log(γr) s log e p s if γr log(p)-log(γr) < s < √ pγr log(p)-log(γr) √ pγ r if s ≥ √ pγr log(p)-log(γr)
As a consequence, ψ

n,r,s and ψ (g) n,r,s are of the same order of magnitude for all s when γ r ≥ p/2. When log(n/rδ) < p, they are also of the same order of magnitude except when s is close but smaller than √ pγ r , for which the ratio ψ

(sg) n,r,s /ψ (g)
n,r,s between these two quantities can be as large as log(p) -log(γ r ). This gap corresponds to the regime where the test based on the Berk-Jones statistic defined in Equation ( 14), used in the Gaussian case, outperforms the test based on the partial CUSUM norm statistic defined in Equation [START_REF] Fryzlewicz | Tail-greedy bottom-up data decompositions and fast multiple change-point detection[END_REF].

In the definitions of the tests, the tuning constants c(p) thresh and c(d) thresh are left implicit, although one can find suitable values by following the proofs of Propositions 3 and 4. In practice, the practitioner can calibrate them by a Monte-Carlo method by simulating a Gaussian multivariate times series without any change-points. Then, c(p) thresh and c(d) thresh are chosen so that the Family-wise error rate (FWER) of the two collections (T

Minimax lower bound

In this section, we write for any Θ ∈ R p×n , the distribution of the time series Y = (y 1 , . . . , y n ) in the model [START_REF] Baranowski | Narrowest-over-threshold detection of multiple change points and change-point-like features[END_REF] with Gaussian noise ε t ∼ N (0, σ 2 I p ). In Section 3, we have established that any change-point satisfying the condition [START_REF] Chu | Asymptotic distribution-free change-point detection for multivariate and non-euclidean data[END_REF], that is

r k ∆ 2 k ≥ c 0 σ 2 s k log 1 + √ p s k log n r k δ + log n r k δ ,
is detected by our change-point procedure. We now show that this energy condition is unimprovable from a minimax point of view. More precisely, let us define, for any u > 0, the class P(u) of mean parameters Θ with arbitrary K ≥ 0 number of change points and such that any change-point

τ k for 1 ≤ k ≤ K satisfies r k ∆ 2 k ≥ 1 2 σ 2 s k log 1 + u √ p s k log n r k + u log n r k . ( 22
)
For u small enough, it turns out no change-point estimator is able to detect all change-points without estimating any spurious change-point with high probability on the full class P(u). Still, using this large class provides somewhat pessimistic bounds. For instance, the most challenging distributions in P(u) for the purpose of change-point detection satisfy s k = p and r k = 1 (very close change-points). As a consequence, relying on the full collection P(u) turns too pessimistic.

To establish that our bounds are adaptive with respect to the sparsity s k and the length r k , we define, for any positive integers 1 ≤ r ≤ n/2 and any 1 ≤ s ≤ p the collection P(u, r, s) = {Θ ∈ P(u) : min k r k ≥ r and max

k s k ≤ s} .
By convention, constant means Θ with no change-points (K = 0) also belong to P(u, r, s). In the class P(u, r, s), all change-points have a sparsity at most s and a length at least r. Hence, P(u, r, s) becomes larger when s increases or when r increases.

Theorem 2. Fix any u ∈ (0, 1/8

P Θ ( K = K) ≥ 1 4 ,
where the infimum is taken over all estimators τ of the change-point vector τ and and K = |τ |.

Thus, in the Gaussian setting, if all the change-points have a high-energy in the sense of ( 8) but with a smaller multiplicative constant factor, no change-point estimator can consistently estimate the true number of change-points. The next corollary restates this negative results in the same lines as Corollary 3. Corollary 6. Fix any u ∈ (0, 1/8). For any σ > 0, n ≥ 2, p > 1, any length 1 ≤ r ≤ n/4, any sparsity 1 ≤ s ≤ p, and any estimator τ , there exists some Θ ∈ P(u, r, s) such that with P Θ -probability larger than 1/4, at least one of the two following properties is satisfied

• τ contains at least one spurious change-point

• at least a change-point τ k with 1 ≤ k ≤ K is not detected, i.e. there is no change-point estimated in the interval [(τ k-1 + τ k )/2, (τ k + τ k+1 )/2].
This corollary is to be compared to Corollary 3 -indeed, the energy condition in Equation ( 22) differs from Equation (8) only by a numerical multiplicative constant. As a consequence, the energy condition ( 22) is minimal for detection by a change-point estimator that achieves (NoSp).

Application to other change-point problems

In this section, we apply the general methodology of Section 2 to two other problems, namely detection of covariance and nonparametric change-points. This allows us to obtain the first tight minimax detection conditions for these problems.

Covariance change-point detection

Following Wang et al. [START_REF] Wang | Optimal covariance change point localization in high dimension[END_REF], we consider the covariance change-point model where the covariance matrices Σ t of the centered random vectors y t ∈ R p are piece-wise constant. Then, the goal is to estimate the times 0 < τ 1 < . . . < τ K < τ K+1 = n + 1 such that Σ t is varying. See [START_REF] Wang | Optimal covariance change point localization in high dimension[END_REF] for motivations. As in that work, we assume that the random vectors y t are independent and are sub-Gaussian with a uniformly bounded Orlicz norm, that is max t=1,...,n y t ψ 2 ≤ B for some known fixed B. The Orlicz norm of a random vector y is the supremum of the Orlicz norm of any uni-dimensional projection of y -see e.g. [START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF]. If the y t 's follow a normal distribution, this amounts to assuming that max t=1,...,n Σ t op ≤ 2B 2 where . op is for the operator norm. The purpose of Wang et al. was to detect small changes in operator norm, that is detecting instants τ k such that Σ τ k = Σ τ k -1 with Σ τ k -Σ τ k-1 op possibly small. Apart from the operator norm, other norms have also been considered e.g. in [START_REF] Holger Dette | Estimating a change point in a sequence of very high-dimensional covariance matrices[END_REF]. Here, we focus on the operator norm as in [START_REF] Wang | Optimal covariance change point localization in high dimension[END_REF].

Recalling the generic procedure introduced in Section 2, we consider the dyadic grid G D and some δ ∈ (0, 1). For any (l, r) ∈ G, we respectively write Σ l,-r and Σ l,r for the empirical covariance matrices

Σ l,-r = r -1 l-1 t=l-r y t y T t ; Σ l,r = r -1 l+r-1 t=l y t y T t .
Then, we consider the test T l,r rejecting for large values of Σ l,r -Σ l,-r op .

T l,r = 1    Σ l,r -Σ l,-r op ≥ c 0 B 2   p r + p r + log( 2n δr ) r + log( 2n δr ) r      , (23)
where the numerical tuning constant c 0 is set in the proof of the following proposition. Relying on concentration bounds [START_REF] Koltchinskii | Concentration inequalities and moment bounds for sample covariance operators[END_REF] for the empirical covariance matrix of sub-Gaussian random vectors, we easily prove that the FWER of the multiple testing procedure (T l,r ) with (l, r) ∈ G D is small. Then, we can analyze the type II error probability and plug it into the generic result (Theorem 1) to control the behavior of the change-point estimator τ . This leads us to the following result. In the sequel, a change-point τ k is said to have a high-energy if

r k Σ τ k -Σ τ k-1 2 op ≥ c 1 B 4 p + log 2n r k δ ∧ r k , (24)
where the numerical constant c 1 is introduced in the proof of the following proposition. We recall that, by definition of the model, we have

Σ τ k -Σ τ k-1 op ≤ 4B 2 .
Proposition 5. There exist positive numerical constants c 0 , c 1 , and c 2 such that the following holds for any B > 0 and any sequence of independent centered random vectors (y t ) satisfying max t y t ψ 2 ≤ B. With probability higher than 1-δ, the change-point estimator τ satisfies (NoSp) and detects all high-energy change-points in the sense of [START_REF] Kovács | Seeded binary segmentation: A general methodology for fast and optimal change point detection[END_REF]. Besides, any such high-energy change-point τ k satisfies

d H,1 ( τ , τ k ) ≤ c 2 B 4 p + log 2δ -1 B -4 n Σ τ k -Σ τ k-1 2 op Σ τ k -Σ τ k-1 2 op ≤ r k 4 , (25)
under the same event of probability than 1 -δ.

Let us compare our condition [START_REF] Kovács | Seeded binary segmentation: A general methodology for fast and optimal change point detection[END_REF] for detection with Theorem 2 in Wang et al. [START_REF] Wang | Optimal covariance change point localization in high dimension[END_REF]. The authors assume that all the change-points satisfy

min k r k min k Σ τ k -Σ τ k-1 2 op ≥ c 1 B 4 p log(n) .
In addition to the fact that we allow some change-points to have an arbitrarily low energy, our requirement for detection scales like √ p + log(n/r k ) instead of p log(n).

The next proposition establishes that the latter condition is minimal. By homogeneity, we can only consider the case where B = 3/2. We focus our attention on Gaussian distributions so that the distribution of the sequence (y 1 , . . . , y n ) is uniquely defined by the sequence (Σ 1 , . . . , Σ n ) of covariance matrices. Given an integer 1 ≤ r ≤ n/4 and ζ ∈ (0, 1/ √ 2), we define P(r, ζ) the collection of sequences η = (Σ 1 , . . . , Σ n ) of covariance matrices that satisfy either Σ t = I p or Σ t op = 1 + ζ. Besides, the corresponding change-points (τ 1 , . . . , τ K ) of η must satisfy min k r k ≥ r and min k Σ τ k -Σ τ k-1 op ≥ ζ. For η ∈ P(r, ζ), we write P η for the corresponding distribution of (y 1 , . . . , y n ). Proposition 6. There exists a positive numerical constant c such that, for any n, p and any length 1 ≤ r ≤ n/4 the following holds. Provided that rζ 2 ≤ c(p + log(n/r)) ∧ r 2 , we have

inf τ sup η∈ P(r,ζ) P η ( K = K) ≥ 1 4 .
As a consequence, our procedure τ achieves the minimal separation condition [START_REF] Kovács | Seeded binary segmentation: A general methodology for fast and optimal change point detection[END_REF] for changepoint detection. In their work, [START_REF] Wang | Optimal covariance change point localization in high dimension[END_REF] obtain faster localization errors than [START_REF] Kovács | Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries[END_REF] to the price of stronger separation conditions. Our focus in this work is to provide optimal detection conditions and we did not try to optimize (24).

Univariate nonparametric change-point detection

We now turn to the univariate nonparametric change-point model considered in [START_REF] Hernan | Optimal nonparametric change point detection and localization[END_REF]. Let m ≥ 1 be any positive integer. At each time t = 1, . . . , n, the random vector y t is an m-sample of a univariate distribution with cumulative distribution function F t . Then, we aim at detecting a vector τ = (τ 1 , . . . , τ K ) of change-points such that F τ k = F τ k-1 . As in [START_REF] Hernan | Optimal nonparametric change point detection and localization[END_REF], we quantify the distance between two distributions by the Kolmogorov distance

F 1 -F 2 ∞ = sup z∈R |F 1 (z) -F 2 (z)|.
As in the previous subsection, we build a procedure τ with our generic algorithm on the dyadic grid. Regarding the collection of tests (T l,r ), we consider two-sample Kolmogorov-Smirnov tests. More precisely, we denote F t the empirical distribution function associated with the sample y t and we define the test

T l,r = 1    r -1 l+r-1 t=l F t - l-1 t=l-r F t ∞ ≥ 2 log(4n/(δr)) mr    .
In the following, a change-point τ k is said to have a high-energy if

r k F τ k -F τ k-1 2 ∞ ≥ c 1 m log n r k δ , (26)
where the numerical constant c 1 is introduced in the proof of the next proposition. As in Subsection 6.1, it is straightforward to prove, based on Dvoretzky-Kiefer-Wolfowitz inequality, that the FWER of the multiple testing procedures (T l,r ) with (l, r) ∈ G D is small. Then, we analyze the type II error probability of this test and plug it into the generic result (Theorem 1) to control the behavior of the change-point estimator τ .

Proposition 7. There exist positive numerical constants c 1 and c 2 such that the following holds. With probability higher than 1 -δ, the change-point estimator τ satisfies (NoSp) and detects all high-energy change-points τ k in the sense of [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF]. Besides, any such high-energy change-points τ k satisfies

d H,1 ( τ k , τ k ) ≤ c 2 log δ -1 nm F τ k -F τ k-1 2 ∞ m F τ k -F τ k-1 2 ∞ ≤ r k 4 , (27)
under the same event of probability than 1 -δ.

In [START_REF] Hernan | Optimal nonparametric change point detection and localization[END_REF], the authors introduce a procedure detecting all the change-points provided that

min k r k min k F τ k -F τ k-1 2 ∞ ≥ c 1 log(n) m .
Comparing this last condition with [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF], we observe that our logarithmic term is tighter and that we allow arbitrarily low-energy change-points.

The next proposition establishes that the condition ( 26) is unimprovable. Given an integer 1 ≤ r ≤ n/4 and ζ ∈ (0, 1/4), we focus our attention on the collection P(r, ζ) of sequences (F 1 , . . . , F n ) of distributions such that the corresponding change-points (τ 1 , . . . , τ K ) satisfy min k r k ≥ r and

min k F τ k -F τ k-1 ∞ ≥ ζ.
P η ( K = K) ≥ 1 4
.

Discussion

Noise distribution for multivariate change-point detection

Comparison between Gaussian and sub-Gaussian rates. In this work, we have studied two types of noise distribution: Gaussian (Section 3) and general sub-Gaussian distributions (Section 4) without further knowledge on the distribution functions. Since the Gaussian setting is a specific instance of the sub-Gaussian setting, it is clear that the minimax lower bounds from Section 5 apply in both settings. As described in the previous subsection, the performances in the sub-Gaussian case almost match those in the Gaussian setting except for s k slightly lower but close to p log(en/r k ). Indeed, in that regime, Berk-Jones or Higher-Criticism type statistics heavily rely on the probability distribution function of the noise, which is not available in the general sub-Gaussian case. Still, we could slightly improve the sub-Gaussian rates if we further assume that the noise components are identically distributed with common CDF F .

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

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

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

C l,r (Y ) = √ r 2   2 r r/2 t=1 Y l-2(t-1)-1 - 2 r r/2 t=1 Y l+2(t-1)   , C l,r (Y ) = √ r 2   2 r r/2 t=1 Y l-2t - 2 r r/2 t=1 Y l+2(t-1)+1   ,
where C l,r (Y ) and C l,r (Y ) are independent. If there is one change-point at position l and no other change-points in (l-r, l+r), then these statistics are identically distributed and we consider Ψ does not require the knowledge of σ; only an upper bound of σ is required to calibrate the corresponding test. Such a U -statistics has already been introduced in [START_REF] Wang | Inference for change points in high dimensional data[END_REF] and analyzed in an asymptotic setting. Unfortunately, since we can only consider even r, this precludes us to detecting change-points that are very close together with r k = 1.

In the general case where there is spatial covariance in the noise, that is var( t ) = Σ for an unknown but general Σ, we can still use the same U -statistic described in the previous paragraph for the dense case. For the sparse case, one could use the supremum norm of the CUSUM statistics as in Jirak [START_REF] Jirak | Uniform change point tests in high dimension[END_REF] and Yu and Chen [START_REF] Yu | Finite sample change point inference and identification for high-dimensional mean vectors[END_REF]. To calibrate those tests, we need to estimate both the Frobenius and the operator norm of Σ, which seems to be doable as soon as there are not too many change-points. If the spatial covariance matrix var( t ) is unknown and even allowed to change with time, we suspect that the problem becomes intrinsically more involved.

Optimal Localization rates

In this work, we mainly considered the problem of detecting change-points in the mean of a random vector. We provided tight conditions on the energy so that a change-point is detectable. When such a change-point τ k is detected, Corollary 2 states that its position is estimated up to an error of r * k , which is also of the order of σ 2 Ψ (g) n,r k ,s k ∆ -2 k -see the definition [START_REF] Holger Dette | Relevant change points in high dimensional time series[END_REF]. It is not clear whether this error is optimal or not.

In the univariate setting (p = 1), [START_REF] Verzelen | Optimal Change-Point Detection and Localization[END_REF] has established that, above the detection threshold, a specific change-point position τ k can be localized at the rate σ 2 ∆ -2 k . In the multivariate setting, the situation is more tricky and there are certainly several localization regimes beyond the detection threshold. It is an interesting direction of research to pinpoint the exact localization rate between σ 2 ∆ -2 k and σ 2 Ψ (g) n,r k ,s k ∆ -2 k . We leave this for future work.

On the choice of the grid in the generic algorithm

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

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

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

From a purely statistical perspective, it is difficult to appreciate the respective benefits of denser or sparser grids. On the one hand, for denser grids, the approximation τ k of τ k at scale r will be closer to τ k so that the corresponding test T τ k ,r may be more powerful. On the other hand, for a denser grid, the tests possibly suffer from a higher price for multiplicity. This price can be mild if one takes into account the dependences between the tests. Still, except perhaps in the univariate Gaussian change-point model for which delicate controls of the CUSUM process exist, it is challenging to provide theoretical guidance towards the best choice of the grid.

Optimality of the generic algorithm in a broader context.

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

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

∆k = d Γ (P τ k ) , Γ P τ k-1 ,
which corresponds to the change-point height. Then, one may wonder how large ∆k has to be -as a function of r k -so that a change-point detection procedure achieving the no-spurious property (NoSp) with high probability is able to detect τ k . In this discussion, we restrict our attention to independent observations, that is the random variables y t are assumed to be independent and we consider the dyadic grid G D . Fix δ ∈ (0, 1). At each scale r ∈ {1, 2, . . . , 2 log 2 (n) -1 } and for each l ∈ D r , with D r defined in (5), we consider the testing problem H 0,l,r : {P : Γ(P l-r ) = . . . = Γ(P l+r-1 )} versus H ρ,l,r :    P : Γ(P l-r ) = . . . = Γ(P l-m-1 ) Γ(P l-m ) = . . . = Γ(P l+r-1 ) d(Γ(P l-m-1 ), Γ(P l-m ) ≥ ρ) for some integer m ∈ [-r/2, r/2]    This amounts to testing whether there is a single change-point near l of height at least ρ in the segment (l -r, l + r). Given δ ∈ (0, 1) and a test T we define the δ-separation distance of T by

ρ * l,r (T, δ) = inf ρ : sup P∈H 0,l,r P(T = 1) ∨ sup P∈H ρ,l,r P(T = 0) ≤ δ .
This corresponds to the minimal change-point height that is detected by the test T . Then, the minimax separation distance ρ * l,r (δ) is simply inf T ρ l,r (T, δ), i.e. the infimum over all tests T of the separation distance. By translation invariance of the testing problem, note that ρ * l,r (δ) does not depend on l and is henceforth denoted ρ * r (δ). For any (l, r), take any test T l,r (nearly) 3 achieving the minimax separation distance ρ * r (δ|D r | -1 β r ) with β r = 6 log -2 2 (n/r))π -2 . Then, it follows from a simple union bound on the dyadic grid that, with probability higher than 1 -δ, the collection of tests T l,r , where (l, r) belongs to the dyadic grid, does not detect any false positive and detects any change-point τ k such that ∆ k is higher than ρ * rk (δ|D rk | -1 β rk ), where rk is the largest scale in R such that 4(r k -1) ≤ r k . As a consequence of Theorem 1, the corresponding detection procedure achieves, with probability higher than 1 -δ, the property (NoSp) and detects any change-point satisfying the energy condition ∆ k ≥ ρ * rk (rδβ r /2n).

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

Comparing the performances of our procedure with the negative arguments that we just outlined, we see that aggregating optimal tests on a dyadic grid allows to detect change-points with (almost) uniform height higher ρ * rk (r k δβ r k /(2n)) whereas, as explained above, we conjecture that a change-point τ k can be detected only if ∆k ≥ ρ * r k (2r k δ/n). Since rk ≥ (r k /8) ∨ 1-as we considered the dyadic grid when constructing rk -the difference between these two bounds is mostly due to the term β r which is of the order of log 2 (n/r). Whereas it is possible to detect change-points at a given scale with a test of type I error probability 2rδ/n, our multi-scale procedure relies on a collection of single tests with type I error probability of the order of rδ/n/ log 2 (n/r). This mild mismatch -that we introduce to deal with the multiplicity of scales -of order log 2 (n/r) is harmless for the Gaussian mean-detection problem. Indeed, one may deduce from our analysis in Section that ρ * r k (2r k δ/n) is of the same order as ρ * rk (δ|D rk | -1 β rk ).

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

Numerical Experiments

In this section, we illustrate the behavior of our procedure to detect change-points in a sparse high-dimensional setting [START_REF] Baranowski | Narrowest-over-threshold detection of multiple change points and change-point-like features[END_REF].

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

SAND((τ k ), (τ k )) = 1 K K k=1 |[(τ k + τ k-1 )/2, (τ k + τ k+1 )/2] ∩ {τ k , k ∈ [ K]}| -1 .
Change-point Detection Methods. In the experiments, we implemented the bottom-up aggregation procedure Algorithm 1 with partial norm tests T (p) and dense test T (d) corresponding to Section 4 on a semi-complete grid G F = {(l, r) : l ∈ {r + 1, . . . , n -r + 1, r ∈ R} -we take scales r in the dyadic set for computational purposes. On a location l and a scale r, each test statistic can be seen as a partial norm test relying on the statistic Ψ (p) l,r,s defined in Section 4.2 and a threshold Thresh(r, s) which is either equal to x r,s for our thresholds Thresh(r, s) since they rely on constants that are not necessarily tight, but we rather calibrate them by a Monte-Carlo method using 10.000 independant samples. For each sample consisting in a time series made of n gaussian normal centered vector in R p , and for each r ∈ R, s ∈ Z r ∪ {p}, we compute the maximum over all l of the statistics Ψ (p) l,r,s . Considering the list of all the 10.000 maximums and taking δ = 5%, Thresh(r, s) is then defined as the (1 -δ/(2|R||Z r |))-quantile if s ∈ Z r and as the (1 -δ/(2|R|))-quantile if s = p, so that, by a union bound, the total probability of finding a false positive is less than δ. Note that this calibration step only depends on n, p, and σ and only needs to be performed once and for all.

We compare our procedure with the inspect method of [START_REF] Wang | High dimensional change point estimation via sparse projection[END_REF] which is available as an R package. The tuning parameters of inspect are computed with the automatic method defined in the same R package.

In all the following experiments, we fix the dimension p = 100 and the sample size n = 200. We generate a piecewise constant signal (η t ) n t=1 in R p with possible change-points (τ 1 , . . . , τ K ) using one of the three following settings. We then add a scaling factor α > 0 and apply our procedure to the data y t = αη t + ε t , which amounts to setting θ t = αη t in model [START_REF] Baranowski | Narrowest-over-threshold detection of multiple change points and change-point-like features[END_REF]. We fix the variance of all the coordinates of ε t to be equal to one. Increasing α on a grid with step 0.1 allows us to experimentally identify a transition between the regime where we do not detect precisely the change-points -in which case the two losses tend to be close to one -and the regime where we do detect the change-points -in which cases the losses are smaller. We consider three simulation settings:

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

2. Multiple Change points. We generate 10 uniform random locations τ 1 < τ 2 < . . . < τ 10 on [START_REF] Sylvain Arlot | A kernel multiple change-point algorithm via model selection[END_REF]200]. For each location τ i , we generate a uniform random integer s i ∈ [1, 100] and a vector ∆ i as in the segment setting with ∆ i = 1 and ∆ i 0 = s i . We generate a uniform random real number N i ∈ [START_REF] Sylvain Arlot | A kernel multiple change-point algorithm via model selection[END_REF][START_REF] Chan | Multi-sequence segmentation via score and higher-criticism tests[END_REF] and define the time series η i by (η i ) t = N i ∆ i 1 t≥τ i . Finally, the signal η = 10 i=1 η i has exactly 10 change-points with random locations. As previously, the noise components (ε t ) follow independent centered and standard gaussian vectors.

3. Time-dependencies. We use the same signal as in the segment setting with s = 20 but we move away from our assumptions by considering time dependencies. More precisely, the (ε t )'s are now defined according to an AR process such taht ε t+1 = ρε t + 1 -ρ 2 ε t+1 for t ≥ 0 where (ε t ) are independent centered and normalized gaussian vectors, ρ = 0.05 for the simulation and by convention ε 0 ∼ N (0, I p ).

Risk estimation with Monte-Carlo. In each setting, we generate 500 independent samples and compute the twpo losses SAND((τ k ), (τ k )) and 1{ K = K}. We estimate the risks E[SAND((τ k ), (τ k ))] and P(K = K) by averaging the loss over the 500 trials. We also compute 95% confidence intervals.

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

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

A An alternative Algorithm

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

Data: y t , t = 1 . . . n and local test statistic (T l,r ) (l,r)∈G Result: Let Θ ∈ R n×p , T be a local test statistic, K * be a set of indices of significant change-points and (τ k , rk ) k∈K * be elements of the grid G that satisfy [START_REF] Peng Chan | Optimal detection of multi-sample aligned sparse signals[END_REF]. We assume that A(Θ, T, K * , (τ k , rk ) k∈K * ) holds, that is:

(τ k ) k≤ K S = ∅ T = ∅; for r ∈ R do for l ∈ D r s.t. T l,r = 1 do if [l -r + 1, l + r -1] ∩ S = ∅ then S ← S ∪ [l -r + 1, l + r - 1
1. (No False Positive) T l,r = 0 for all (l, r) ∈ H 0 ∩ G, where H 0 is defined by [START_REF] Cho | Data segmentation algorithms: Univariate mean change and beyond[END_REF] 2. (Significant change-point detection) for every k ∈ K * , we have T τk ,r k = 1.

For every r ∈ R define

T * r = {l ∈ T r : ∃k ∈ K * s.t. τ k ∈ [l -r + 1, l + r -1]}, S * r = l∈T * r [l -r + 1, l + r -1].
In other words, for all r ∈ R, T * r is the subset of T r for which each interval of detection [l -r + 1, l + r -1] contains a significant change-point. The next proposition recursively analyzes the detection sets corresponding to significant change-points (S * r ) r≥1 . The first inclusion means that significant change-points which can be detected with a local statistic with radius smaller than r are detected before step r, while the second inclusion means that each connected component of r∈R S * r is included in a close neighborhoods of some significant change-point τ k , k ∈ K * . Proposition 9. For all r ∈ R ∪ {0}, we have the double inclusion

{τ k : k ∈ K * and rk ≤ r} ⊂ r ≤r,r ∈R S * r ⊂ k∈K * [τ k -2(r k -1), τ k + 2(r k -1)] . (28)
The next proposition shows that for each step r ∈ R, the subset of detection corresponding to non significant change-point is disjoint from r ∈R S * r . Proposition 10. For all r ∈ R, we have

l∈Tr\T * r [l -r + 1, l + r -1] ∩ r ∈R S * r = ∅ .
Recall that (C k ) k=1,..., K are defined as the connected component of r∈R S r . To ease the notation, re-index (C k ) so that τ k is the closest true change-point to τk = min C k +max C k

2

. Since there is no false positive, τ k ∈ C k . By Proposition 10, the two closed subset r∈R l∈Tr\T * r [l -r +1, l +r -1] and r∈R S * r are disjoint. For all k ∈ K * , it holds by Proposition 9 that τ k ∈ r∈R S * r , so that C k is a connected component of r∈R S * r containing the significant change-point τ k . In particular, K ≥ |K * |. We have

• By Proposition 9, C k ⊂ [τ k -2(r k -1), τ k + 2(r k -1)] for every k ∈ K * . Thus |τ k -τ k | ≤ (r k -1) < r k 4 .
• For all k ∈ [K] \ K * , either τ k does not belong to r∈R S r and it is simply not detected, or it is the closest true change-point to τk

= min C k +max C k 2 so that τk ∈ τ k - τ k + τ k-1 2 , τ k + τ k + τ k+1 2 .
In particular,

{τ k , k ≤ K} ⊂ τ 1 - τ 1 -τ 0 2 , τ K + τ K+1 -τ K 2 .
• Finally, if there exists two estimated change-points τk 1 , τk 2 in τ k -

τ k +τ k-1 2 , τ k + τ k +τ k+1 2
, then either C k 1 or C k 2 does not contain τ k . Then Θ is constant on C k 1 or on C k 2 and we obtain a contradiction since there is no false positive. This concludes the proof of Theorem 1.

Proof of Proposition 9. To prove the proposition, we do an induction on r ∈ R ∪ {0}. The case r = 0 is trivial since by definition, S 0 = ∅. Let r ∈ R and assume that the double inclusion Proposition 9 holds for all r < r, r ∈ R ∪ {0}.

First inclusion: Let k ∈ K * be such that rk = r and assume that the corresponding significant change-point τ k has not been detected before step r, that is τ k ∈ r <r S * r . Since k ∈ K * , this implies in particular that τ k ∈ r <r S r . Let us show that τ k ∈ S r . To this end we prove that

[τ k -r + 1, τk + r -1] ∩ r <r,r ∈R S r = ∅ (29)
and

T τk ,r = 1, (30)
which will be enough since

|τ k -τ k | ≤ rk -1 = r -1.
• Proof of (29): Assume for the sake of contradiction that there exists an integer z which belongs to [τ k -r + 1, τk + r -1] ∩ r <r r ∈R S r . There exists r < r such that z ∈ S r and l(z

) ∈ T r such that z ∈ [l(z)-r +1, l(z)+r -1]. Since τ k ∈ r <r S r , we have τ k ∈ [l(z)-r +1, l(z)+r -1].
Moreover,

|l(z) -τ k | ≤ |l(z) -z| + |z -τk | + |τ k -τ k | ≤ (r -1) + (r -1) + |τ k -τ k | < r k -r ,
Where the last inequality comes from the hypothesis 3(r k -1)

+ |τ k -τ k | ≤ r k Consequently, [l(z) -r , l(z) + r ] ⊂ [τ k -r k , τ k + r k ) \ {τ k } , so that θ is constant on [l(z) -r , l(z) + r ) ∩ N.
Thus, (l(z), r ) ∈ H 0 and l(z) ∈ T r since there is no false positive. This gives a contradiction and concludes the proof of ( 29).

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

We have just shown that τ k ∈ S r and hence τ k ∈ S * r so that the first inclusion holds at step r.

Second inclusion : Let x be an element of S * r . There exists l(x

) ∈ T * r such that x ∈ [l(x) -r + 1, l(x) + r -1]. By definition of T * r , there exists a significant change-point τ k ( i.e. such that k ∈ K * ) belonging to [l(x) -r + 1, l(x) + r -1].
We necessarily have rk ≥ r. Indeed, if rk < r, then by the induction hypothesis, τ k ∈ S * r for some r < r, which contradicts the fact that

S * r is disjoint from [l(x) -r + 1, l(x) + r -1] ⊂ S * r . Consequently, |l(x) -τ k | + r -1 ≤ 2r -2 ≤ 2(r k -1) Thus x ∈ [l(x) -r + 1, l(x) + r -1] ⊂ [τ k -2(r k -1), τ k + 2(r k -1)] . We have just shown that S * r ⊂ k∈K * [τ k -2(r k -1), τ k + 2(r k -1)].
Therefore, the proposition is verified at step r and the induction is proved.

Proof of Proposition 10. Let k ∈ K * and C k be the detected connected component containing the significant change-point τ k

C k = r ∈R S * r ∩ [τ k -2(r k -1), τ k + 2(r k -1)] .
We know from Proposition 9 that C k is a connected component of r ∈R S * r and we want to prove now that C k does not overlap with l∈Tr\T * r [l -r + 1, l + r -1] for some r ∈ R. Let r 0 be such that C k is the connected component of S r 0 ,

C k ⊂ S * r 0 .
Such an r 0 exists and is unique since the sets S * r are disjoint. We have from Proposition 9 that τ k ∈ r ∈R,r ≤r k S * r so that r 0 ≤ rk .

Let r ∈ R and l ∈ T r \ T * r and assume without loss of generality that l + r -1 < τ k . Since there is no false positive, (l, r) ∈ H 0 and there exists at least one true change-point in the interval of detection [l -r + 1, l + r -1]. Denote τ a , . . . , τ b with a ≤ b the true change-points belonging to [l -r + 1, l + r -1]. By definition of T r \ T * r , τ a , . . . , τ b are not significant change-points, i.e. a, a + 1, . . . , b ∈ K * . We consider the two cases r > rk and r ≤ rk • r > rk : In that case, since the sets (S r ) are disjoint and C k ⊂ S * r 0 , we have

C k ∩ [l -r + 1, l + r -1] = ∅.
• r ≤ rk : In that case, we have

l + r -1 ≤ τ b + 2(r -1) ≤ τ b + 2(r k -1) < τ k -2(r k -1) ,
where we used the fact that 4(r k -1) < r k ≤ τ k -τ b . Since by Proposition 9 we have

C k ⊂ [l -r + 1, l + r -1], we also have in that case C k ∩ [l -r + 1, l + r -1] = ∅.
This concludes the proof of the proposition.

B.2 Proofs for Gaussian multivariate change-point detection

From now on, we use the following notation for all (l, r) ∈ J n .

• For any (v 1 , . . . , v n ) with v t ∈ R p , the left mean and right mean of v on [l -r, l + r) are denoted by vl,+r = 1 r

l+r-1 t=l v t vl,-r = 1 r l-1 t=l-r v t .
• The population term of the CUSUM statistic C l,r is written

U l,r = r 2 θl,+r -θl,-r .
• With these notation, we write v l,+r,i , v l,-r,i , U l,r,i for the i th coordinate of the vector v l,+r , v l,-r , U l,r .

• We define, for 1 ≤ s ≤ p, the order statistics U l,r,(s) by |U l,r,(1) | ≥ |U l,r,(2) | ≥ . . . |U l,r,(p) |.

B.2.1 Proof of Proposition 1

Step 0: Consequence of Equation (10) on the grid. Let k ∈ [K] and assume that τ k is a κ d -dense high-energy change-point (see Equation ( 10)). We have that

U τ (d) k ,r (d) k 2 ≥ 9 16 U τ k ,r (d) k 2 ≥ 9 16 × 12 κ d   p log n r(d) k , δ + log n r(d) k , δ   , (31)
since by definition

τ k - τ (d) k ≤ r(d) k /4, so that ||θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k || 2 ≥ 9 16 ||θ τ k ,+r (d) k -θ τ k ,-r (d) k || 2 .
Step 1: Introduction of useful high probability events. Remark that

r 2 y l,+r -y l,-r 2 -θ l,-r -θ l,+r 2 -σ 2 p = r ε l,+r -ε l,-r , θ l,+r -θ l,-r + r 2 ε l,+r -ε l,-r 2 -σ 2 p .
The first term, written as r ε l,+r -ε l,-r , θ l,+r -θ l,-r , is a crossed term between the noise and the mean vector θ. Lemma 1 states that near the changepoints and on the grid defined by the sets R, D r , it is jointly controlled with high probability.

Lemma 1. Let 1 ≥ δ > 0. The event ξ (d) 1 = k∈[K] r(d) k ε τ (d) k ,+r (d) k -ε τ (d) k ,-r (d) k , θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k ≤ 1 8 r(d) k θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k 2 + 16σ 2 log 2 n r(d) k δ .
holds with probability larger than 1 -δ.

The second term, written as

r 2 ε l,+r -ε l,-r 2 -σ 2 p ,
is a term of pure noise. Lemma 2 states that it is controlled jointly with high probability on the grid defined by the sets R, D r .

Lemma 2. Let 1 ≥ δ > 0. The event ξ (d) 2 = r∈R l∈Dr r 2 ε l,+r -ε l,-r 2 -σ 2 p ≤ 4σ 2 p log 2 n rδ + log 2 n rδ ,
holds with probability larger than 1 -δ.

Set now

ξ (d) := ξ (d) = ξ (d) 1 ∩ ξ (d) 2
.

Note that

P(ξ (d) ) ≥ 1 -2δ .
Step 2: Study in the 'no change-point' situation.

Consider r ∈ R, l ∈ D r such that {τ k , k ∈ [K]} ∩ [l -r, l + r) = ∅. Note that since {τ k , k ∈ [K]} ∩ [l -r, l + r) = ∅,
we have θ l,-r = θ l,+r so that r 2 θ l,-r -θ l,+r 2 = 0 , and r ε l,+r -ε l,-r , θ l,+r -θ l,-r = 0.

Moreover we have on ξ (d) that -see Lemma 2

r 2 ε l,+r -ε l,-r 2 -σ 2 p ≤ 4σ 2 p log 2 n rδ + log 2 n rδ = σ 2 x (d) r .
And so d) . This concludes the proof of the first part of the proposition.

Ψ (d) l,r ≤ x (d) r , so that T (d) l,r = 0 , on ξ (
Step 3: Study in the 'change-point' situation. Consider k ∈ [K] τ k is a κ d -dense high-energy change-point -that is Equation( 10) holds. We have from ( 31) that for κ d large enough, r(d)

k 2 θ τ (d) k ,-r (d) k -θ τ (d) k ,+r (d) k 2 ≥ 9 16 × 12 κ d σ 2   p log n r(d) k , δ + log n r(d) k , δ   > 4σ 2 x (d) r(d) k .
So on ξ (d) this implies that -see Lemma 1

r(d) k ε τ (d) k ,+r (d) k -ε τ (d) k ,-r (d) k , θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k ≤ r(d) k 4 θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k 2
.

Moreover we have on ξ (d) that -see Lemma 2

r(d) 2 ε τ (d) k ,+r (d) k -ε τ (d) k ,-r (d) k 2 -σ 2 p ≤ 4σ 2   p log 2 n r(d) k δ -1 + log 2 n r(d) k δ -1   = σ 2 x (d) r(d) k .
And so on ξ (d) , combining the three previous displayed equations implies

Ψ (d) τ (d) k ,r (d) k
≥ r(d) k 2 θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k 2 2σ 2 -x (d) r(d) k > (2 -1)x (d) r(d) k = x (d) r(d) k
, so that

T (d) τ (d) k ,r (d) k
= 1 .
This concludes the proof of the second part of the proposition.

Proof of Lemma 1. Let k ∈ [K]. Since the vectors ε t are i.i.d. and distributed as N (0,

σ 2 I p ), it holds that r(d) k ε τ (d) k ,+r (d) k -ε τ (d) k ,-r (d) k , θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k ∼ N 0, 2r (d)
k σ 2 θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k 2
.

And so for δ k > 0, it holds with probability larger than 1 -δ k it holds that r(d)

k ε τ (d) k ,+r (d) k -ε τ (d) k ,-r (d) k , θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k ≤ 2σ θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k r(d) k log(2δ -1 k ) . Let us set δ k = (r (d) k ) 2 δ 2n 2 . Note that k∈[K] δ k = r∈R k∈[K]:r (d) k =r (r (d) k ) 2 δ 2n 2 ≤ r∈R l∈Dr r 2 δ 2n 2 ≤ r∈R rδ 2n ≤ δ , since r k ≥ r(d) k and |D r | ≤ 2n/r
, and also by definition of R which implies r∈R r n ≤ 1. And so if δ ≤ 1, then with probability larger than 1 -δ, for any k ∈ [K], we have

r(d) k ε τ (d) k ,+r (d) k -ε τ (d) k ,-r (d) k , θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k ≤2σ θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k 2r (d) k log 2 n r(d) k δ -1 .
This implies in particular that with probability larger than 1 -δ, for any k ∈ [K], we have

r(d) k ε τ (d) k ,+r (d) k -ε τ (d) k ,-r (d) k , θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k ≤ r(d) k 2 θ τ (d) k ,+r (d) k -θ τ (d) k ,-r (d) k 2 4 + 16σ 2 log 2 n r(d) k δ -1 .
Proof of Lemma 2. Let r ∈ R and l ∈ D r . Since the vectors ε t are i.i.d. and distributed as N (0, σ 2 I p ), it holds that r 2 ε l,+r -ε l,-r 2 ∼ σ 2 χ 2 p , which implies by properties of the χ 2 p distribution -see e.g. Lemma 1 of [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF] -that for any δ r > 0 we have with probability larger than 1 -δ r r 2 ε l,+r -ε l,-r 2 -σ 2 p ≤ 2σ 2 p log(2/δ r ) + 2σ 2 log(2/δ r ) .

If we set, for δ > 0, δ r = r 2 δ 2n 2 , we have that with probability larger than 1 This concludes the proof.

-rδ n , that ∀l ∈ D r r 2 ε l,+r -ε l,-r 2 -σ 2 p ≤ 2σ 2 p log(2/δ r ) + 2σ 2 log(2/δ r ) ,

B.2.2 Proof of Proposition 2

Step 1 : Analysis of the Berk-Jones statistics We first define a threshold x (BJ) r,s

for the Berk-Jones statistics for all r, s ≥ 1

x (BJ) r,s = min x ≥ 2 : Φ(x) ≤ s 2 28 2 p log(2δ -1 x,r ) , (32)
where we recall that δ x,r are the weights defined by [START_REF] Frick | Multiscale change point inference[END_REF]:

δ x,r = 6δr π 2 x 2 |D r |n .
Remark that (x

(BJ)
r,s ) is nonincreasing with s and define for all r ≥ 1 sr = min s ∈ Z : s ≥ 28 3 log 2δ -1

x (BJ) r,s ,r . (33)
The second point of the following proposition ensures that if there exists s ∈ Z such that U l,r,(s) ≥ t s for some s ≥ sr , for (l, r) = (τ

(s) k , r(s) k ), then T (BJ) l,r
= 1 with high probability. We recall that |U l,r,(1) | ≥ • • • ≥ |U l,r,(p) | are the sorted absolute values of the coordinate of U l,r and that H 0 is defined by [START_REF] Cho | Data segmentation algorithms: Univariate mean change and beyond[END_REF].

Proposition 11. There exists an event ξ (BJ) of probability larger than 1-2δ such that the following holds:

• T (BJ) l,r = 0 for any (l, r) ∈ H 0 ∩ G.

• For all k ∈ [K], if there exists s ∈ Z such that s ≥ sr

T (BJ) τ (s) k ,r (s) k = 1.
Step 2 : Analysis of the partial norm statistics Since it may happen that τ k is a sparse highenergy change-point but there is no s ≥ sr (s)

k such that U τ (s) k ,r (s) k ,(s) ≥ x (BJ) r(s) k ,s
, we use the following proposition on the partial norm test statistic T (p) l,r : Proposition 12. There exists an event ξ (p) of probability larger than 1 -2δ such that the following holds:

• T (p) l,r = 0 for any (l, r) ∈ H 0 ∩ G. • for any k ∈ [K], if there exists s ∈ Z such that s s =1 U τ (s) k ,r (s) k ,(s ) 2 > 4x (p) r(s) k ,s , (34) then T
(p) τ (s) k ,r (s) k = 1.
Step 3 : Combination of the two Statistics Let us return to the proof of Proposition 2. To conclude the proof, it suffices to show that if τ k is a κ s -sparse high-energy change-point -see ( 11)for some large enough constant κ s , then the result of one of the two preceding propositions holds. This is precisely what the following lemma shows.

Lemma 3. There exists a constant κ s such that if τ k is a κ s -sparse high-energy change-point, then one of the following propositions is true: We focus on the second part of the proposition. To ease the reading, we introduce some notation

• There exists s ∈ Z such that s > sr (s) k and U τ (s) k ,r (s)
γ x,r = Q -1 [δ x,r , p, 2Φ(x)] ; η x,r,s = Q -1 [1 -δ x,r /2, p -s, 2Φ(x)] ; ψ x,r,s (u) = Q -1 [1 -δ x,r /2, s, Φ(x -u) + Φ(x + u)] ,
for x ≥ 0. In fact, γ x,r is the threshold of the statistics N x,l,r . As for η x,r,s , it stands for the contribution to N x,l,r of the (p -s) coordinates i such that θ •,i is constant over [l -r, l + r). Finally, ψ x,r,s (u) stands for the contribution to N x,l,r of the s coordinates i whose population CUSUM statistics U l,r,i is equal to u.

Lemma 4. Consider any r ∈ R and l ∈ D r . If for some positive integers s and x we have

ψ x,r,s (|U l,r,(s) |) > γ x,r -η x,r,s , (35)
then P[T

(BJ) l,r = 1] ≥ 1 -δ x,r .
Denote H[θ] the collection of (l, r) with r ∈ R and l ∈ D r that satisfy Condition [START_REF] Rudelson | Hanson-wright inequality and sub-gaussian concentration[END_REF] for some s and some x. We easily deduce from the above Lemma together with an union bound that, with probability higher than 1 -δ, T x,r )

.

We have ψ xs,r,s (t s ) > γ xs,r -η xs,r,s provided that

s ≥ 28 3 log(2δ -1 xs,r ) . (36)
Combining Lemma 5 and Lemma 4, we conclude the proof of the proposition.

Proof of Lemma 4. Denote S any subset of size s, such that for any j ∈ S, |U l,r,j | ≥ |U l,r,(s) |. Define N

x,l,r = p i=1

1 i / ∈S 1 |C l,r,i |>x , N (2)
x,l,r = p i=1

1 i∈S 1 |C l,r,i |>x
Since, for any x > 0, the function u → Φ(x + u) + Φ(x -u) is non-decreasing. As a consequence, the random variable N

x,l,r is stochastically dominated by a Binomial distribution with parameters (p-s, 2Φ(x)). Besides, N

x,l,r is stochastically dominated by a Binomial distribution with parameters (s, Φ(x + |U l,r,(s) |) + Φ(x -|U l,r,(s) |)). We obtain

P[T (BJ) l,r = 0] ≤ P[N x,l,r ≤ γ x,r ] ≤ P[N (1)
x,l,r < η x,r,s ] + P[N [START_REF] Baranowski | Narrowest-over-threshold detection of multiple change points and change-point-like features[END_REF] x,l,r ≤ γ x,r -η x,r,s ]

≤ δ x,r 2 + 1 -Q[γ x,r -η x,r,s , s, Φ(x -|U l,r,(s) |) + Φ(x + |U l,r,(s) |)] ≤ δ x,r 2 + δ x,r 2 ≤ δ x,r .
Proof of Lemma 5. From Bernstein inequality, we deduce that, for any positive integers s and x,

γ x,s ≤ 2pΦ(x) + 2 pΦ(x) log(δ -1 x,r ) + 2 3 log(δ -1 x,r ) ; η x,r,s ≥ 2(p -s)Φ(x) -2 pΦ(x) log(2δ -1 x,r ) - 2 3 log(2δ -1 x,r ) .
Hence, it follows that γ x,s -η x,r,s ≤ 2sΦ(x) + 4 pΦ(x) log(2δ -1 x,r ) + 4 3 log(2δ -1 x,r ) .

For u = x, we have Φ(x -u) + Φ(x + u) ≥ Φ(0) = 1/2 and we derive from Bernstein inequality that

ψ x,r,s (t) ≥ s 2 -s log(2δ -1 x,r ) - 2 3 log(2δ -1 x,r ) .
As a ce, ψ x,r,s (t) > γ x,s -η x,r,s as long as

s(1 -4Φ(x)) > 12 pΦ(x) log(2δ -1 x,r ) + 12 3 log(2δ -1 x,r ) .
Provided that we take x ≥ 2, the latter holds if

s ≥ 14 pΦ(x) log(2δ -1 x,r ) + 14 3 log(2δ -1 x,r ) (37)
In view of the definition (32) of x s , we have 14 pΦ(x s ) log(2δ -1 xs,r ) ≤ s/2. Hence, under Condition [START_REF] Hernan | Optimal nonparametric change point detection and localization[END_REF], [START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF] holds and we conclude that ψ xs,r,s (x s ) > γ xs,s -η xs,r,s .

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

Lemma 6 (concentration of the pure noise for the second sparse statistic). If 1 ≥ δ > 0, then the event

ξ (p) 1 = ∀r ∈ R, l ∈ D r , s ∈ Z max S∈ Cs p i∈S r 2σ 2 (ε l,+r,i -εl,-r,i ) 2 ≤ x (p)
r,s holds with probability higher than 1 -δ.

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

Lemma 7 (concentration on the change-points for the second sparse statistic). We write K * for the set of k ∈ [K] such that -r,i ) follows a N (0, 1) distribution for all l, r, i, we have by Bernstein's inequality that with probability larger than 1 -δ r,s , i∈S (ε l,+r,i -εl,-r,i )

• s k ≤ p log n r k δ • s s =1 U τ (s) k ,r (s) k ,(s ) 2 ≥ 4x (p) r(s) k ,s If 1 ≥ δ > 0, the event
s i=1 U 2 τ (s) k ,r (s) k ,(i) > 4x (p) r(s) k ,s . (38)
To ease the reading, we write (τ, r) = (τ

(s) k , r(s) k ). Then on the event ξ (p)
1 which holds with probability 1 -δ, we have

Ψ (p) τ,r,s = max S∈ Cs p i∈S r 2σ 2 θτ,+r,i + ετ,+r,i -θτ,-r,i -ετ,-r,i 2 ≥ max S∈ Cs p i∈S 1 2 U 2 τ,r,i - r 2σ 2 (ε τ,+r,i -ετ,-r,i ) 2 > 2x (p) r,s -x (p) r,s = x (p) r,s ,
where in the second inequality, we used the fact that (a + b) 2 ≥ 1 2 a 2 -b 2 for all a, b ∈ R.

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

x (BJ) r,s 2 ≤ C log ep s 2 log n rδ sr ≤ C log log ep s2 r n rδ ,
where we recall that sr is defined by (33) and x (BJ) r,s by [START_REF] Adam B Olshen | Circular binary segmentation for the analysis of array-based dna copy number data[END_REF]. These two inequalies come from the fact that for all t ≥ 2 and all A > 0, if t ≤ A + log (t) then t ≤ 2A. Assume that for all s = sr (s)

k + 1, . . . , s k we have |U τ (s) k ,r (s) k ,(s ) | < x (BJ) r(s) k ,s
. To ease the notation, we write s = sr (s)

k ∧ s k
and in what follows we prove that s

s =1 |U τ (s) k ,r (s) k ,(s ) | 2 > 4x (p) r(s) k ,s
when κ s is a large enough constant.

We have

s k s =s r(s) k +1 U 2 τ (s) k ,r (s) k ,(s ) ≤ C 1 log(s k ) i=0 2 i log ep 2 2i log n r(s) k δ ≤ C 1 s k log 2e log n r(s) k δ + C 1 log(s k ) i=0 2 i log p 2 2(i+1) ,
for some universal constant C 1 . To handle the second term remark that since x → log p x 2 is decreasing, we have

log(s k ) i=0 2 i log p 2 2(i+1) ≤ 2s k 1 log p x 2 dx = 2s k log p (2s k ) 2 + 2s k -1 ≤ 2s k log p s 2 k ,
and thus

s k s =s r(s) k +1 U 2 τ (s) k ,r (s)
k ,(s )

≤ 2C 1 s k log 2e p s 2 k log n r(s) k δ
, which finally gives

s s =1 U 2 τ (s) k ,r (s) k ,(s )
≥ 9 16 r(s) k ∆ 2 k -2C 1 s k log 2ep s 2 k log n r(s) k δ ≥ 4x (p) r(s) k ,s .
In the first inequality we used the fact that

τ (s) k -τ k ≤ 1 4 r(s) k ,
so that for all i,

θτ (s) k ,+r (s)
k ,i -θτ (s) k ,-r (s) k ,i = 1 r(s) k r(s) k + τ (s) k -τ k µ k,i - r(s) k - τ (s) k + τ k µ k-1,i ≥   1 - τ (s) k -τ k r(s) k   |µ k,i -µ k-1,i | > 3 4 |µ k,i -µ k-1,i | = 3 4 U k,i .
In the second inequality, we used the fact that

• 8r (s) k ∆ 2 k ≥ κ s σ 2 s k log p s 2 k log n r(s) k δ + log n r(s) k δ
for a large enough constant κ s (see [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF]),

• x → x log ep
x 2 is increasing for x ≤ p, so that s k can be replaced by s,

• s ≤ C log log ep s2 n rδ .
This concludes the proof of the lemma.

B.2.3 Proof of Corollary 2

Let ξ (d) and ξ (s) be two events such that Proposition 1 and Proposition 2 hold respectively with constants κ d , κ s and with probability 1 -2δ and 1 -4δ, and write ξ = ξ (d) ∩ ξ (s) . From now on, we work on the event ξ, which holds with probability 1 -6δ. Let us choose c 0 ≥ 2(κ d ∨ κ s ) in [START_REF] Chu | Asymptotic distribution-free change-point detection for multivariate and non-euclidean data[END_REF].

For all k such that τ k is a c 0 -high-energy change-point, define

(τ k , rk ) =            (τ (d) k , r(d) k ) if s k > p log n r k δ (τ (s) k , r(s) k ) if s k ≤ p log n r k δ . (r k , τk ) is well defined. Indeed, If s k ≤ p log n r k δ then s k log 1 + √ p s k log n r k δ + log n r k δ ≥ 1 2 s k log p s 2 k log n r k δ + log n r k δ . Now if s k ≥ p log n r k δ then using log (1 + x) ≥ x 2 for x ∈ [0, 1] we have s k log 1 + √ p s k log n r k δ + log n r k δ ≥ 1 2 p log n r k δ + log n r k δ .
According to Theorem 1, it is sufficient to prove that the event A (Θ, T, K * , (τ k , rk ) k∈K * ) defined in Section 2.3 holds on ξ: Moreover, T

s) τk ,r k = 1 if (τ k , rk ) = (τ (d) k , r(d) k ) by Proposition 2 and T (d) τk ,r k = 1 if (τ k , rk ) = (τ (s) k , r(s) k ) by Proposition 1. Theorem 1 ensures that for all k ∈ [K] such that τ k is a c 0 -high-energy change-point, there exists k ∈ [ K] such that |τ k -τ k | ≤ rk -1. It remains to show that rk -1 ≤ r * k 2 , (
where r * k is define by [START_REF] Holger Dette | Relevant change points in high dimensional time series[END_REF]. Using log (1 + x) ≥ x 2 for x ∈ [0, 1] and log (1 + x) ≥ log (x) for x ≥ 1 we have

8r k ∆ 2 k ≤ 4(κ d ∨ κ s ) s k log 1 + √ p s k log n rk δ + log n rk δ , when rk ≥ 2. Thus 2(r k -1) ≤ r * k for c 0 ≥ 2(κ d ∨ κ s ).
This concludes the proof of Corollary 2.

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

We recall that in this section, we work on the complete grid G F = J n defined in Section 2.

B.3.1 Proof of Proposition 3

Step 1: Introduction of useful high probability events. We first introduce two events ξ on which the noise can be controlled. Remark that by a simple computation, the noise can be decomposed as follows :

r 2 y l,+r -y l,-r 2 -θ l,-r -θ l,+r 2 -σ 2 p = r ε l,+r -ε l,-r , θ l,+r -θ l,-r + r 2 ε l,+r -ε l,-r 2 -σ 2 p .
The first term written as r ε l,+r -ε l,-r , θ l,+r -θ l,-r is a crossed term between the noise and the mean vector θ. Lemma 8 states that for l equal to a true change-point τ k and r of order r * k , it is controlled on event ξ

(d)

1 with high probability.

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

ξ (d) 1 = ∀k ∈ [K] s.t. Equation (17) holds for k, r(d) k ε τ k ,+r (d) k -ε τ k ,-r (d) k , θ τ k ,+r (d) k -θ τ k ,-r (d) k ≤ r(d) k 4 θ τ k ,+r (d) k -θ τ k ,-r (d) k 2
holds with probability higher than 1 -δ.

The second term written as

r 2 ε l,+r -ε l,-r 2 -σ 2 p ,
is a term of pure noise. Lemma 9 states that it is controlled on event ξ

2 with high probability.

Lemma 9 (concentration of the pure noise). There exists a constant cconc > 0 such that the event

ξ (d) 2 = ∀(l, r) ∈ J n , r 2 ε l,+r -ε l,-r 2 -σ 2 p ≤ cconc L 2 p log n rδ + log n rδ
holds with probability higher than 1 -2δ.

Set now

ξ (d) := ξ (d) 1 ∩ ξ (d) 2
.

Note that

P(ξ (d) ) ≥ 1 -3δ .
Step 2: Study in the 'no change-point' situation. We remind that H 0 stands for elements (l, r) such that there is no change-point in [l -r, l + r) and that it is defined in [START_REF] Cho | Data segmentation algorithms: Univariate mean change and beyond[END_REF]. Consider (l, r) ∈ J n ∩ H 0 . Note that since {τ k , k ∈ [K]} ∩ [l -r, l + r) = ∅, we have θ l,-r = θ l,+r so that r 2 θ l,-r -θ l,+r 2 = 0 , and r ε l,+r -ε l,-r , θ l,+r -θ l,-r = 0 .

Moreover we have on ξ (d) that -see Lemma 9

r 2 ε l,+r -ε l,-r 2 -σ 2 p ≤ cconc L 2 p log n rδ + log n rδ ≤ σ 2 x (d) r ,
for cthresh ≥ cconc -note that cconc > 0 is a universal constant. And so d) . This concludes the proof of the first part of the proposition.

Ψ (d) l,r ≤ x (d) r , so that
T (d) l,r = 0 , on ξ (
Step 3: Study in the 'change-point' situation. Consider k ∈ [K] such that τ k is a κ-dense high-energy change-point -see Equation [START_REF] Gibberd | Multiple changepoint estimation in high-dimensional gaussian graphical models[END_REF]. We have

r(d) k 2 θ τ k ,-r (d) k -θ τ k ,+r (d) k 2 ≥ κ 8 L 2   p log n r(d) k δ + log n r(d) k δ   .
So on ξ (d) choosing κ large enough implies that -see Lemma 8 r(d)

k ε τ k ,+r (d) k -ε τ k ,-r (d) k , θ τ k ,+r (d) k -θ τ k ,-r (d) k ≤ r(d) k 4 θ τ k ,+r (d) k -θ τ k ,-r (d) k 2 .
Moreover we have on ξ

(d) that -see Lemma 9 r(d) k 2 ε τ k ,+r (d) k -ε τ k ,-r (d) k 2 -σ 2 p ≤ cconc L 2   p log n r(d) k δ + log n r(d) k δ   ≤ σ 2 x (d) r(d) k ,
for cthresh ≥ cconc -note that cconc > 0 is a universal constant. Thus on ξ (d) , combining the three previous displayed equations implies

Ψ (d) τ k ,r (d) k ≥ r(d) k 4σ 2 θ τ k ,+r (d) k -θ τ k ,-r (d) k 2 -x (d) r(d) k ≥ c 0 16 -cthresh L 2 σ 2   p log n r(d) k δ + log n r(d) k δ   > x (d) r(d) k ,
since κ > 32c thresh . And so on ξ (d) :

T (d) τ k ,r (
d) k = 1 .
This concludes the proof of the second part of the proposition.

Proof of Lemma 8. Let k be in [K] and such that Equation ( 17) is satisfied. Remark that θ is constant on [τ k -r(d) k , τ k ) and is equal to µ k-1 , and is also constant on [τ k , τ k + r(d) k ) and is equal to µ k . First, from the definition of the ψ 2 -norm of a vector, there exists a universal constant C > 0 such that for all k = 1 . . . K,

r(d) k ε τ k ,+r (d) k -ε τ k ,-r (d) k , θ τ k ,+r (d) k -θ τ k ,-r (d) k ψ 2 ≤ r(d) k ε τ k ,+r (d) k -ε τ k ,-r (d) k ψ 2 |µ k -µ k-1 | ≤ C r(d) k ε 1 ψ 2 |µ k -µ k-1 | ≤ C r(d) k L |µ k -µ k-1 | ≤ CL r k ∆ 2 k .
Thus by definition of sub-Gaussianity, for all t > 0,

P r(d) k ε τ k ,+r (d) k -ε τ k ,-r (d) k , θ τ k ,+r (d) k -θ τ k ,-r (d) k ≥ t ≤ exp -c t 2 L 2 r k ∆ 2 k ,
for some constant c > 0. Finally we apply the concentration inequality to t =

r k ∆ 2 k 4
-remembering that τ k is a κ-dense high-energy change-point in the sense of Equation ( 17) -and sum over k to obtain a union bound over ξ c 2 :

P (ξ c 2 ) ≤ K k=1 P r ε τ k ,+r (d) k -ε τ k ,-r (d) k , θ τ k ,+r (d) k -θ τ k ,-r (d) k ≥ r k ∆ 2 k 4 ≤ K k=1 exp -c r k ∆ 2 k 16L 2 ≤ K k=1 exp -c κ log n r(d) k δ -1 (c = c/16) ≤ K k=1 r(d) k n c κ δ c κ ≤ δ ,
where the last inequality comes from the fact that K k=1 r(d) k

≤ n and the fact that κ is chosen large enough so that c κ ≥ 1.

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

Lemma 10 (Hanson-Wright inequality in high dimension). Let A = (a ij ) be a m × m matrix and ε 1 , . . . , ε m be sub-Gaussian vectors of dimension p with norm smaller than 1. Then

P   1≤i,j≤m a i,j ε i , ε j -E   1≤i,j≤m a i,j ε i , ε j   ≥ t   ≤ 2 exp -c min t 2 p A 2 F , t A op ,
where c is an absolute constant, A 2 F = i,j a 2 i,j is the squared Frobenius norm of A and A op is the operator norm of A.

B.3.2 Proof of Proposition 4

Step 1: Introduction of useful high probability events. Let s ≤ p and consider S ∈ Cs p . In what follows and for an vector u ∈ R p , we write u (S) for the vector u restricted to the set S.

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

r 2 ȳ(S) l,+r - ȳ(S) l,-r 2 - θ(S) l,-r - θ(S) l,+r 2 -σ 2 s = r ε(S) l,+r - ε(S) l,-r , θ(S) l,+r - θ(S) l,-r + r 2 ε(S) l,+r - ε(S) l,-r 2 -σ 2 s .
The first term written as

r ε(S) l,+r - ε(S) l,-r , θ(S) l,+r - θ(S) l,-r ,
is a crossed term between the noise and the mean vector θ. Lemma 8 states that for l equal to a true change-point τ k , r of order r * k , and S being the corresponding support of the change-point, it is controlled on event ξ

:= ξ (p) 1 (δ) = ∀k ∈ [K] s.t. Equation (18) holds for k, r(d) k ε(S k ) τ k ,+r (d) k - ε(S k ) τ k ,-r (s) k , θ(S k ) τ k ,+r (s) k
- θ(S k ) τ k ,-r (s) k ≤ r(d) k 4 θ τ k ,+r (s) k -θ τ k ,-r (s) k 2
holds with probability higher than 1 -δ.

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

The second term written as

r 2 ε(S) l,+r - ε(S) l,-r 2 -σ 2 s
is a term of pure noise. Lemma 16 states that it is controlled on event ξ (p) 2 (S) with high probability. Lemma 16. There exists a constant cconc > 0 such that the event

ξ (p) 2 (S) := ξ (p) 2 (S, δ) = ∀(l, r) ∈ J n , r 2 ε(S) l,+r - ε(S) l,-r 2 -σ 2 s ≤ cconc L 2 s log n rδ + log n rδ
holds with probability higher than 1 -2δ.

The proof of this lemma is exactly the same as the one of Lemma And so the event

ξ (p) 2 := ξ (p) 2 (δ) = ∀(l, r) ∈ J n , ∀S ⊂ [p], r 2 ε(S) l,+r - ε(S) l,-r 2 -σ 2 s ≤ 4c conc L 2 log n rδ + s log 2ep s (39)
has probability larger than 1 -2δ. Set now

ξ (p) := ξ (p) 1 ∩ ξ (p) 2 . Note that P(ξ (p) ) ≥ 1 -3δ.
Step 2: Study in the 'no change-point' situation. Consider (l, r)

∈ J n such that {τ k , k ∈ [K]} ∩ [l -r, l + r) = ∅, and S ⊂ [p]. Note that since {τ k , k ∈ [K]} ∩ [l -r, l + r) = ∅, we have θ(S) l,-r = θ(S) l,+r so that r 2 θ(S) l,-r - θ(S) l,+r 2
= 0, and r ε(S) l,+r -ε(S) l,-r , θ(S) l,+r -θ(S) l,-r = 0. Moreover we have on ξ (p) that -see Equation (39)

r 2 ε(S) l,+r - ε(S) l,-r 2 -σ 2 s ≤ 4c conc L 2 log n rδ + s log 2ep s ≤ σ 2 x (p) r ,
for cthresh ≥ 4c conc -note that cconc > 0 is a universal constant. And so

Ψ (p) l,r ≤ x (p) r , so that on ξ (d) , T (p)
l,r = 0 . This concludes the proof of the first part of the proposition.

Step 3: Study in the 'change-point' situation. Consider k ∈ [K] such that τ k is a κ-sparse high-energy change-point, -see Equation [START_REF] Gretton | A kernel two-sample test[END_REF]. Since S k is the support of µ k -µ k-1 -and therefore of θ τ k ,-r (s)

k -θ τ k ,+r (s) k -we have r(s) k 2 θ(S k ) τ k ,-r (s) k - θ(S k ) τ k ,+r (s) k 2 ≥ κ 8 L 2 s k log 2ep s k + log n r(s) k δ . So on ξ (p) this implies that -see Lemma 15 r(d) k ε(S k ) τ k ,+r (s) k - ε(S k ) τ k ,-r (s) k , θ(S k ) τ k ,+r (s) k - θ(S k ) τ k ,-r (s) k ≤ r(s) k 4 θ τ k ,+r (s) k -θ τ k ,-
τ k ,r (s) k = 1.
This concludes the proof of the second part of the proposition.

B.3.3 Proof of Corollary 5

Let ξ (d) and ξ (s) be two events such that Proposition 3 and Proposition 4 both hold with probability 1 -3δ, and write ξ = ξ (d) ∩ ξ (p) . From now on, we work on the event ξ, which holds with probability 1 -6δ. Define here simply τk = τ k . Note that by definition of rk in the sub-Gaussian regime:

rk =            r(d) k if s k log ep s k > p log n r k δ r(s) k if s k log ep s k ≤ p log n r k δ
According to Theorem 1, it is sufficient to prove that A (Θ, T, K * , (τ k , rk ) k∈K * ) holds. for some u ≤ 1 8 . In what follows, we consider any change-point detection method that outputs an estimator τ of the change-points, associated to a number K of detected change-points, i.e. the length of τ . We also write P Θ for the distribution of the data when the mean parameter or the time series is fixed to a n × p matrix Θ, i.e. of Θ + ε where the noise entries (ε t ) j are i.i.d. and follow N (0, σ 2 ) as in Section 3. Also abusing slightly notations, we write P 0 for the distribution of the data when the parameter is constant and equal to 0. Consider also any prior π over the set of n × p matrices Θ such that the number of true changepoints over the support of the prior is larger than 1 -i.e. the prior puts mass only on problems where more than one change-point occurs. Let Pπ be the corresponding distribution of the data, namely the distribution of the matrix of data when the mean parameter of the time series is the random matrix Θ ∼ π. Otherwise said, Pπ is the distribution of Θ + ε where Θ ∼ π.

We remind that in our setting K is the number of true change-points in a given problem -which would be either 0 under P 0 , or more than 1 under Pπ . If the support of π 1 is included in P(r, s), then sup Θ∈P(r,s)

P Θ ( K = K) ≥ 1 2
Pπ ( K = 0) + P 0 ( K = 0)

≥ 1 2 (1 -d T V ( Pπ , P 0 )), (40)
where d T V is the total variation distance. From the Cauchy-Schwarz inequality, we have

d T V ( Pπ , P 0 ) ≤ 1 2 χ 2 ( Pπ , P 0 ), (41)
where χ 2 is the divergence between probability distributions:

χ 2 ( Pπ , P 0 ) = E P 0 d Pπ d P 0 -1 2 .
By a simple computation that can be found for example in [START_REF] Wu | Lecture notes for ece598yw: Information-theoretic methods for high-dimensional statistics[END_REF] χ 2 ( Pπ , P 0 ) = E Θ, Θ e

1 σ 2 Θ, Θ -1, (42)
where Θ and Θ are i.i.d. and distributed according to π, Θ, Θ = Tr( Θ ΘT ) is the standard scalar product, and E Θ, Θ is the expectation according to Θ and Θ .

Let us consider the three following cases for the couple (r, s): Each case corresponds to the regime of detection of one of the three statistics. The first one corresponds to the Berk-Jones statistic, the second one to the dense statistic and the last one to the partial norm statistic.

Case 1 : In that case, r∆ 2 ≤ σ 2 s log 4u p s 2 log n r . Let us define a probability distribution on the parameter Θ ∈ P(r, s). For ζ = n r -1 and l ∈ Dr = {1, r + 1, 2r + 1, . . . ζr + 1}, define the column vector v l = l+r-1 j=l e j , where e j is the j th element of the canonical basis of R n . Let a be a random variable uniformly distributed in {x ∈ {0, 1} p , |x| 0 = s} and ν be a random variable independent from a and uniformly distributed on {v l : l ∈ Dr }. Let Θ(1) = ∆ √ s aν T ∈ R p×n , and π 1 be the distribution of the random variable Θ(1) , and Pπ 1 be the corresponding distribution of the data. Consider two independent copies Θ(1) and Θ (1) that are distributed like π 1 . The probability that Θ(1) and Θ

(1) have the same support is exactly 1 ζ+1 . Hence, from Equation (42)

χ 2 ( Pπ 1 , P 0 ) = 1 ζ + 1 E a,a e r∆ 2 sσ 2 a,a -1 , ( 43
)
where a is an independent copy of a, and E a,a is the expectation according to a, a . Remark by symmetry that a, a has the same law as s i=1 a i . Hence , where E a is the expectation according to a.

Remark that (a 1 , . . . , a p ) has the same distribution as a random sampling without replacement of the list of length p containing (1, . . . , 1, 0, . . . , 0) -the list containing exactly s times the quantity 1 and otherwise only 0. The following lemma allows us to replace the variables a i by independent Bernoulli random variables Z i ∼ B(s/p). Lemma 17. Let c = (c 1 , . . . , c p ) ∈ R p . We associate to the list c two random sampling processes: (i) the sampling process without replacement (X i ) i=1...s of s elements uniformly on the list c and (ii) the sampling process with replacement (Z i ) i=1...s of s elements uniformly in the list. Then for any convex function f ,

E f s i=1 X i ≤ E f s i=1 Z i .
The proof of this lemma can be found in [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]. Thus, if (Z i ) i=1...s is an i.i.d sequence of Bernoulli variables with parameter s p as described above, we obtain ≤ 2 r n

1-4u 2 ≤ 1 , (45)
where E Z is the expectation according to the (Z i ) i and where in the last inequality we used u ≤ 1/3 and n ≥ 4r.

where E Θ(2) , Θ

is the expectation according to Θ(2) , Θ

(where Θ (2) is an independent copy of Θ(2) ) and where E b,b is the expectation according to b, b (where b is an independent copy of b), and where in the last step we used u ≤ 1/8 and n ≥ 4r.

Case 3 : In that case, r∆ 2 ≤ u log n r . Let c = (1, 0, 0, . . . , 0) be the vector with 0 entries except the first one. Let ν be the random vector defined as in Case 1. Let Θ(3) = ∆cν T , and π 3 be the distribution of the random variable Θ(3) -and Pπ 3 be the associated probability distribution of the data. Doing the same reasoning as in Case 1 -see in particular the step of Equation ( 43) -replacing a by c and s by 1 -for the prior π 3 , we obtain χ 2 ( Pπ 3 , P 0 ) = E Θ(3) , Θ where

E Θ(3) , Θ (3)
is the expectation according to Θ(3) , Θ

(where Θ (3) is an independent copy of Θ(3) ) and where in the last step we used n ≥ 4r and u ≤ 1/2. Taking a union bound over all high-energy change-points, we deduce from Theorem 1 that, with probability higher than 1 -δ, τ achieves (NoSp) and detects all high-energy change-points. Besides, the localization error ( 25) is a consequence of the definition (48) together with Theorem 1.

Proof of Proposition 6. As in the proof of Theorem 2, we only consider a specific setting where one aims at testing K = 0 with Σ 1 = I p versus K = 2 with τ 1 ∈ (n/4; 3n/4), τ 2 = τ 1 + r, Σ 1 = Σ τ 2 = I p and Σ τ 1 = I p + ζuu T for some unknown unit vector u in R p . Obviously, we have r 1 = r 2 = r and Σ τ 1 -Σ τ 0 op = Σ τ 2 -Σ τ 1 op = ζ so that it suffices to prove that the sum of the type I and type II error probabilities of any test of these hypotheses is bounded away from zero. We consider two subcases: Case 1: ζ ≤ c p/r ∧ 1 √ 2 . Then, we focus on the specific alternative hypothesis where τ 1 = n/2 and τ 2 = τ 1 + r, so that the problem reduces exactly to testing whether the covariance matrix Σ of a r-sample satisfies Σ = I p or whether Σ = I p + ζuu T . This hypothesis testing problem for covariance matrices is well understood. In particular, one can deduce from Theorem 5.1 in [START_REF] Berthet | Optimal detection of sparse principal components in high dimension[END_REF] that, as soon as ζ ≤ c [ p/r ∧ 1], for some c sufficiently small, one has inf τ sup Θ∈ P(r,ζ)

P Θ ( K = K) ≥ 1 4
.

Case 2: ζ ≤ c log(n/r)/r ∧ 1/ √ 2. Here, we consider another specific class of alternative hypotheses where we fix u = (1, 0, . . . , 0) but τ 1 can take different values, i.e. τ 1 ∈ { n/4 , n/4 + r, . . . , n/4 + r n/2r }. It turns out that this is equivalent to a univariate variance testing problem where one observes q = n/(2r) samples of size r with distributions N (0, σ 2 1 ), . . . , N (0, σ 2 q ). Under the null, we have σ 1 = σ 2 = . . . = σ q = 1. Under the alternative, for some j ∈ [q], we have σ j = √ 1 + ζ and σ l = 1 for l = j. For j = 1, . . . , q, write P j for the distributions of the j-th sample of size r when σ 2 j = 1 + ζ and σ l = 1 for l = j. Besides, we write L j for the corresponding likelihood ratio with the null distribution P 0 . Then, the mixture distribution is defined as P = 1 q q j=1 P j whereas L stands for the mean likelihood ratio. Following the classical path of Le Cam's method we obtain that, for any test T , P 0 [T = 1] + sup j=1,...,q P j [T = 0] ≥ P 0 [T = 1] + P[T = 0] ≥ 1 -P 0 -P T V , where . T V is the total variation norm. Using Cauchy-Schwarz inequality, we bound this total variation distance between the covariates

P 0 -P T V ≤ E 0 L 2 -1 = 1 q E 0 L 2 i -1 = 1 q (1 -ζ 2 ) -r/2 -1 ≤ 1 q e rζ 2 -1 ,
since ζ ∈ (0, 1/2). As a consequence, we derive that P 0 -P T V ≤ 1/4 as long as rζ 2 ≤ c log(q) ∧ 1. The result follows.

Proof of Proposition 7. The proof is based on an application of Dvoretzky-Kiefer-Wolfowitz (DKW) inequality [START_REF] Boucheron | Concentration inequalities[END_REF] together with an union bound. For a q sample of a univariate distribution with empirical distribution function F and true distribution function F , DKW inequality ensures that

P F -F ∞ ≥ x 2q ≤ 2e -x .

Figure 1 :

 1 Figure 1: An example of a piece-wise constant sequence Θ with 3 change-points and p = 1.

Figure 2 :

 2 Figure 2: The dyadic grid is represented as follows : for each r = 2 i and l ∈ D r , we draw the interval [l -r + 1, l + r -1] at position (l, log 2 (r)).

Figure 3 :

 3 Figure 3: Example of our change-point detection procedure with three change-points. The first two change-points have large heights and are detected at a small scale r (in magenta) while the third one is detected at a larger scale r.

  therefore requires the knowledge of σ. To calibrate the corresponding test T (d) l,r rejecting for large values of Ψ (d) l,r we introduce

  detects all dense high-energy change-points at the scale r(d) k and makes no false positives on the dyadic grid G D . If we plugged this collection of tests into the general multiple change-point procedure, then Theorem 1 would entail that all κ d -dense high-energy change-points are discovered and localized and that τ does not detect any spurious change-point. In the next subsection, we introduce alternative tests that are tailored to sparse change-points and thereby allow to detect change-points that are not κ d -dense high-energy but still satisfy the energy condition[START_REF] Chu | Asymptotic distribution-free change-point detection for multivariate and non-euclidean data[END_REF].

  . The next proposition controls the error of this collection of tests.

  (d) l,r ∨ T (s) l,r is Λ = O(p(r + log(np))), and the computational cost of the whole change-point detection procedure on the dyadic grid is O(np log(np)).

  (d) k -1) < r k . For any positive integers (l, r) ∈ G F , we consider the same CUSUM-based statistic Ψ (d) l,r := C l,r 2 -p as for Gaussian noise. Let c(d) thresh > 0 be a tuning parameter to be discussed later. To calibrate the corresponding multiple test procedures (T (d) l,r ) with (l, r) ∈ G F rejecting for large values of Ψ (d) l,r we introduce

  (d) thresh . With probability higher than 1 -δ, one has (i)T (d) l,r = 0 for all (l, r) ∈ G F ∩ H 0 and (ii) T (d) τ k ,r(d) k= 1 for all κ d -dense high-energy change-points τ k .

  (d) l,r ∨ T (p) l,r with tuning parameters c(d) thresh and c(p) thresh as in Propositions 3 and 4. Consider any c 0 > 32(c (d) thresh ∨ c(p) thresh ) and any c 0 -high-energy change-point τ k , which is either a c 0 -sparse or a c 0 -dense high-energy changepoint. Defining rk

  is equal to δ. Computational Cost. The computational cost of the statistic T l,r = T(d) l,r ∨ T (p) l,r is O(p(r + log(p))). Thus, a naive computation of all the tests T l,r for (l, r) in the complete gridG F requires O(p log(p) (l,r)∈G F r) = O(pn(n 2 + log(p))) operations. Nevertheless, using the fact that l+r i=l+1 Y i = ( l+r-1 i=l Y i ) + Y l+r -Y l ,it is possible to compute all the tests at scale r with cost O(np log(p)). Since there are n possible scales r on the complete grid, the whole procedure cost is O(n 2 p log(p)). Using a grid G = {(l, r) ∈ G F : r ∈ R} that contains dyadic scales and all possible locations l for each scale, the whole change-point detection would then require only O(np log(n) log(p)) computations, since there are only log(n) possible scales r for such grids.

Proposition 8 .

 8 For η ∈ P(r, ζ), we write P η for the corresponding distribution of the sequence (y 1 , . . . , y n ). There exists a positive numerical constant c such that, for any n, p and any length 1 ≤ r ≤ n/4 the following holds. Provided that rζ 2 ≤ c log(n/r)/m, we have inf τ sup η∈ P(r,ζ)

  = C l,r (Y ), C l,r (Y ) whose expectation is null when there are no change-points in the segment. As a consequence, Ψ (d) l,r

r

  when s = d -see Section 4.1 -or to x (p) r,s when s ∈ Z r := {1, 2, 4, . . . , 2 log 2 (smax) } with s max := √ pγr log(p)-log(γr) -see Section 4.3 for the definition of the boundary between sparse and dense regimes s max . We actually do not use the definition of x

Figure 4 :

 4 Figure 4: Estimation of E[SAND((τ k ), (τ k ))] and P( K = K) in the segment setting with s = 1.

Figure 5 :

 5 Figure 5: Estimation of E[SAND((τ k ), (τ k ))] and P( K = K) in the segment setting with s = 20.

Figure 6 :

 6 Figure 6: Estimation of E[SAND((τ k ), (τ k ))] and P( K = K) in the segment setting with s = 100.

Figure 7 :

 7 Figure 7: Estimation of E[SAND((τ k ), (τ k ))] and P( K = K) in a multiple change-point setting with K = 10 where change-points have random norms in [1, 5] and random sparsities in [1, p].

Figure 8 :

 8 Figure 8: Estimation of E[SAND((τ k ), (τ k ))] and P( K = K) in the segment setting with s = 20 but with time-dependent noise that have an auto-correlation of ρ = 5%.

Algorithm 2 :

 2 Variant bottom-up aggregation procedure of multiscale tests B Proofs B.1 Proof of Theorem 1

sincen ≤ 1 .

 1 |D r | ≤ 2n/r. And so with probability larger than 1 -δ, for all r ∈ R and l∈ D r r 2 ε l,+r -ε l,-r 2 -σ 2 p ≤ 2σ 2 p log(2/δ r ) + 2σ 2 log(2/δ r ) ,since r∈R r And so finally for δ ≤ 1 and with probability larger than 1 -δ, for all r ∈ R and l ∈ D r r 2 ε l,+r -ε l,-r 2 -σ 2 p ≤ 4σ 2 p log 2 n r δ -1 + log 2 n r δ -1 .

.•.

  There exists s ∈ Z such that s ≤ sr(s) Proof of Proposition 11. The first part of the proposition is a simple consequence of the definition together with an union bound.

Lemma 5 .

 5 all (l, r) ∈ H[θ].Let us now provide a more explicit characterisation of H[θ] with the following Lemma. For any 1 ≤ s ≤ p and r ∈ R define x s byx s := x (BJ)r,s = min x ≥ 2 : Φ(x) ≤ s 2 28 2 p log(2α -1

ξ (p) 2 =, 2

 22 ∀k ∈ K * : ∃s ∈ Z s.t. Ψ holds with probability higher than 1 -δ.Lemmas 6 and 7 directly imply the result of the proposition.Proof of Lemma 6. Let r ∈ R, l ∈ D r , s ≤ sr and S ∈ Cs p . Let δ > 0, δ r,s = (ε l,+r,i -εl,

2 δ≥ 1

 21 -δ , which yields the result. Proof of Lemma 7. Let k ∈ K * , and s ∈ Z such that

1 . 2 .

 12 (No false positive): for every r ∈ R and l ∈ D r , if Θ is constant on [l -r, l + r) then T l,r = T (High-energy change-point detection): for every k such that τ k has c 0 -high-energy, it holds by definition of r(d) k and r(s) k that 4(r k -1) ≤ r k .

  probability. Lemma 15. For k ∈ [K], let us write S k ⊂ [K] for the support of µ k -µ k-1 . Assume that c 0 is a large enough universal constant. The event ξ (p) 1

1 .

 1 (No false positive): T l,r = T (p) l,r ∨ T (d) l,r = 0 for any (l, r) ∈ G F ∩ H 0 . by Proposition 3 and Proposition 4.

2 .

 2 (Significant change-point detection): for every k ∈ K * (see (20)), we have by definition of rk : 4(r k -1) ≤ r k . Now if s k log ep s k ≥ p log n r k δ , we have T (d) τk ,r k = 1 by Proposition 3, by definition of c 0 , and for c(d) thresh as in Proposition 3. If s k log ep s k ≤ p log n r k δ , we have T (p) τk ,r k = 1 by Proposition 4, by definition of c 0 , and for c(p) thresh as in Proposition 4. Theorem 1 ensures that for all k ∈ K * , there exists k ∈ [ K] such that |τ k -τ k | ≤ rk -1. This concludes the proof since 4(r k -1) ≤ r k for k ∈ K * . B.4 Proof of Theorem 2 Let us fix (r, s) ∈ [1, n/4] × [1, p]. Let ∆ be such that

Case 1 : u log n r ≤ s log 1

 1

E a,a e r∆ 2 sσ 2

 22

χ 2 (

 2 Pπ 1 , P 0 )

Case 2 : 2 (

 22 In that case, r∆ 2 ≤ σ 2 u p log n r . Let s 0 = u p log n r and b be a random variable uniformly distributed in {x ∈ {0, 1} p , |x| 0 = s 0 } and ν be defined as in Case 1. LetΘ(2) = ∆ √ p bν T ,let π 2 be the distribution of Θ(2) and Pπ 2 be the associated probability distribution of the data. Doing the same reasoning and similar computations as for Case 1, see in particular the steps of Equations (43) and (44) -replacing s by s 0 and a by b -we have χ Pπ 2 , P 0 ) = E Θ(2) , Θ

  e

1 σ 2 Θ≤ 1 ,

 121 [START_REF] Wu | Lecture notes for ece598yw: Information-theoretic methods for high-dimensional statistics[END_REF]

  ). For any σ > 0, n ≥ 2, p ≥ 1, any length 1 ≤ r ≤ n/4, and any sparsity 1 ≤ s ≤ p, we have inf

τ sup Θ∈ P(u,r,s)

  r (s)for cthresh ≥ 4c conc -note that cconc > 0 is a universal constant. And so on ξ (p) , combining the three previous displayed equations implies Ψ

												2
												.
												k
	Moreover we have on ξ (p) that -see Equation (39)
	r(s) k 2	ε(S k ) τ k ,+r k (s)	-	ε(S k ) τ k ,-r	(s) k	2	-σ 2 s ≤ 4c conc L 2 log	n r(s) k δ	+ 2s k log	2ep s k	(p) ≤ σ 2 x r(s)
		(p) τ k ,r k (s)	≥	r(d) k 4σ 2	θ(S k ) τ k ,+r	(s) k	-	θ(S k ) τ k ,-r k (s)	2	(p) -x r(s) k
					≥	κ 16	-cthresh	L 2 σ 2 log	n r(s) k δ	+ s k log	2ep s k	(p) > x r(s)

k , k , since κ > 32c thresh . And so on ξ (p) T (p)

See Equation[START_REF] Hu | Sparsity likelihood for sparse signal and change-point detection[END_REF] as the energy condition is slightly different in the sub-Gaussian setting.

Re-defined in Equation[START_REF] Jirak | Uniform change point tests in high dimension[END_REF].

Since the minimax separation distance is defined as an infimum, it is not necessarily achieved by a test. Still, we can build a test whose separation distance is arbitrarily close to the optimal one. We neglect the additive error term for the purpose of the discussion.

Acknowledgements. The work of A. Carpentier is partially supported by the Deutsche Forschungsgemeinschaft (DFG) Emmy Noether grant MuSyAD (CA 1488/1-1), by the DFG -314838170, GRK 2297 MathCoRe, by the FG DFG, by the DFG CRC 1294 'Data Assimilation', Project A03, by the Forschungsgruppe FOR 5381 "Mathematical Statistics in the Information Age -Statistical Efficiency and Computational Tractability", Project TP 02, by the Agence Nationale de la Recherche (ANR) and the DFG on the French-German PRCI ANR ASCAI CA 1488/4-1 "Aktive und Batch-Segmentierung, Clustering und Seriation: Grundlagen der KI" and by the UFA-DFH through the French-German Doktorandenkolleg CDFA 01-18 and by the SFI Sachsen-Anhalt for the project RE-BCI. The work of E. Pilliat and N. Verzelen has been partially supported by ANR-21-CE23-0035 (ASCAI). The authors are grateful to two anonymous referees for their helpful comments that improved the presentation of the manuscript.

The proof of this lemma relies on the classical Hanson Wright inequality that is proved for example in [START_REF] Rudelson | Hanson-wright inequality and sub-gaussian concentration[END_REF]. To prove the proposition, we will use a chaining argument. To this end, we let (N u ) u≥0 be the following covering sets of J n :

where we define κ 1 = log 2 (n) , and more generally κ r = log 2 (n/r) for r = 1, . . . n. Remark that the higher u is, the finer the covering set N u is, and N κ 1 = J n . For all u ≥ 0, we define the projection map π u from J n to N u by π u (l, r) = arg min ( l,r)∈Nu

| l -l| + |r -r| .

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

(l u , r u ) = π u (l, r) .

A useful lemma to control the distance between (l, r) and its projection (l u , r u ) can be stated as follow.

Lemma 11. For all (l, r) ∈ J n and 0 ≤ u ≤ κ 1 such that N u = ∅,

Let (l, r) ∈ J n . From know on, we write ε l,+r = rε l,+r = l+r-1 t=l ε t and ε l,-r = rε l,+r . The chaining relation can be written as

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

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

Then

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

Lemma 13. There exists a constant C N such that for all n, the event

holds with probability higher than 1 -δ.

For u = κ r , (l u , r u ) ∈ N u Lemma 11 gives r u ≤ r + 2 n 2 u ≤ 3 n 2 u . Consequently, on the event ξ

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

Lemma 14. For all (l, r) and (l , r ) in J n , set

There exists a constant C ∆ such that, for all n, the event

∆,v l, r, l , r holds for all ((l, r), (l , r ))

holds with probability higher than 1 -δ.

For v ≥ κ r , ((l v , r v ), (l v+1 , r v+1 )) ∈ N v × N v+1 and by Lemma 11,

Therefore, on the event ξ

where C ∆ , C ∆ are large absolute constants. Hence, letting cconc = C N + C ∆ we obtain

, which must be of probability higher than 1 -2δ.

Proof of Lemma 11. Since the mesh of the grid N u is equal to 2

Proof of Lemma 12. Let us write

where

This gives the first inequality.

For the second inequality, assume without loss of generality that l ≤ l . As for the first inequality, b ij ≤ 2 for all i, j ∈ [m 1 , m 2 ). Remark that b ij can be non zero only if (i, j) is in one of the following cases :

Hence there is at most (4(|l

and we obtain the second inequality.

Proof of Lemma 13. The probability of (ξ

N ) c can be written as :

First, fix u ≥ 0 and (l, r) ∈ N u such that r ≤ 3 n 2 u . Applying the first inequality of Lemma 12 and the Hanson-Wright inequality -see Lemma 10, we obtain for all t ≥ 0

where c is an absolute constant. Choosing

we obtain

where c, C are absolute constants. Since the cardinal of N u is upper bounded by 2 2u+2 , A union bound on each N u for each u ≥ 0 gives :

which is convergent. For C N large enough, we obtain P (ξ c N ) ≤ 1 -δ.

Proof of Lemma 14.

∆,v l, r, l , r ) c holds .

First fix v ≥ 0 and ((l, r), (l , r ))

Then by Lemma 12, letting B be the matrix such that ε T B ε = ε l ,+r -ε l ,-r 2ε l,+r -ε l,-r 2 , we obtain

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

From now on, we choose

There are at most 2 4v+6 elements in N v × N v+1 . Therefore, a union bound on v ≥ 0 and N v × N v+1 gives

where the last inequality holds if C ∆ is large enough, for c, C universal constants.

Thus, in all cases -combining Equations ( 40) and [START_REF] Wang | Optimal change point detection and localization in sparse dynamic networks[END_REF] with Equations ( 45), ( 46) and ( 47) -we obtain in all three cases sup Θ∈P(r,s)

.

and this concludes the proof.

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

Proof of Proposition 5. Consider an r-sample (z 1 , . . . z r ) with mean zero and covariance matrix Σ and Orlicz norm B. Koltchinskii and Lounici [START_REF] Koltchinskii | Concentration inequalities and moment bounds for sample covariance operators[END_REF] have proved that, for any x > 0, the empirical

with probability higher than 1 -exp(-x). Here c is a suitable positive constant. Considering a union bound over all (l, r) ∈ G D such that Σ t is constant over [l -r, l + r), we have, with probability higher than 1 -δ/2, that simultaneously on all such r ∈ R and l ∈ D r ,

where the constant 8 comes from the union bound on all elements of the grid. As a consequence, the FWER of the multiple testing collection is at most δ/2 provided that we choose c 0 ≤ 8c . Conversely, consider any high-energy change-point τ k . Let r k be the smallest radius r ∈ R such that

and consider the closest location l ∈ D r of τ k so that |l -τ k | ≤ r/2. To ease the notation, we still write r for r k . Without loss of generality, we assume that l ≥ τ k . Let us decompose the statistic

and over [τ k , l + r). Then, we apply three times the deviation inequality of Koltchinskii and Lounici [START_REF] Koltchinskii | Concentration inequalities and moment bounds for sample covariance operators[END_REF] to get

with probability higher than 1 -0.5δ[r/(2n)] 2 . As a consequence, we have T l,r = 1 provided that

Since Σ τ k -Σ τ k-1 op ≤ 2B 2 and if we choose c 1 ≥ 17 ∨ 32(c + c 0 ), the bound ( 48) is achievable only if r ≥ p + log(2n/(rδ)) and we deduce from (48) that T l,r = 1.

Applying two-times DKW inequality to each statistic T l,r such that no-change-point occurs on (l -r, l + r), we deduce that, setting c 1 sufficiently larger, the FWER of (T l,r ) is at most δ/2 by summing the probabilities over all scales r ∈ R and by a union bound on all l ∈ D r . Turning to the high-energy change points, we consider τ k satisfying [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF]. Let r k be the smallest radius r ∈ R such that

and consider the closest location l ∈ D r of τ k so that |l -τ k | ≤ r/2 and 2r ≤ r k . To ease the notation, we still write r for r k . As in the proof of Proposition 5, we decompose the statistic

and apply DKW inequality to each of three sums. Taking the union bound over all possible T l,r we deduce that, with probability higher than 1 -δ/2 r -1

so that in view of Condition (49) implies that T l,r = 1. Applying Theorem 1 allows us to conclude.

We focus on a testing problem where, under the null, F t = U for all t = 1, . . . , n, whereas under the alternative there exists τ 1 ∈ { n/4 , n/4 + r, . . . , n/4 + (r -1) n/(2r) } such that F t = U ζ for t = τ 1 , . . . , τ 1 +r -1 and F t = U otherwise. Defining q = n/(2r) , we observe that this amounts to testing whether q samples of size rm are distributed according the null distribution or whether exactly one of them is distributed according to U ζ . Arguing again in the proof of Proposition 6, we only need to bound the total variation distance between the distribution P 0 under the null and the mixture distribution q -1 q j=1 P j of the q possible alternatives -here P 0 = ⊗ q k=1 U ⊗(rm) is the distribution of the samples when F t = U and P rm) , is for j ≥ 1 the distribution of the samples when F t = U except for t ∈ [jr, (j + 1)r), in which case

Let z be a uniform random variable over [0, 1] and w be an independent Bernoulli random variable with parameter 1/2. Then, one easily checks that z/2 + w/2 is uniformly distributed on [0, 1]. If w is a Bernoulli random variable with parameter 1/2 -2ζ, then one easily checks that the cumulative distribution function of z/2 + w/2 is F ζ . As a consequence, by a standard data-processing inequality [START_REF] Wu | Lecture notes for ece598yw: Information-theoretic methods for high-dimensional statistics[END_REF], one derives that P 0 -q -1 q j=1 P j T V ≤ P 0 -q -1 q j=1 P j T V , where under P 0 one observes q independent Binomial random variables with parameter (mr, 1/2), whereas under P j , the j-th observation follows a Binomial distribution with parameter (mr, 1/2 -62 2ζ). Using Cauchy-Schwarz inequality, we upper bound the square of the total variation distance by the χ 2 distance and then compute it explicitly. This leads us to P 0 -q -1 q j=1 P j 2 T V ≤ 1 q

(1 + 16ζ 2 ) rm -1 , which is smaller than 1/4 provided that 16rmζ 2 ≤ log(q/4 + 1). If we choose c small enough in the statement of the proposition, this last condition holds and the result follows.