Damien Garreau
email: damien.garreau@ens.fr

Sylvain Arlot
email: sylvain.arlot@math.u-psud.fr

Consistent change-point detection with kernels

Keywords: MSC 2010 subject classifications: Primary 62M10; secondary 62G20 change-point detection, kernel methods, penalized least-squares

In this paper we study the kernel change-point algorithm (KCP) proposed by Arlot, Celisse and Harchaoui [4], which aims at locating an unknown number of change-points in the distribution of a sequence of independent data taking values in an arbitrary set. The change-points are selected by model selection with a penalized kernel empirical criterion. We provide a non-asymptotic result showing that, with high probability, the KCP procedure retrieves the correct number of change-points, provided that the constant in the penalty is well-chosen; in addition, KCP estimates the change-points location at the optimal rate. As a consequence, when using a characteristic kernel, KCP detects all kinds of change in the distribution (not only changes in the mean or the variance), and it is able to do so for complex structured data (not necessarily in R d ). Most of the analysis is conducted assuming that the kernel is bounded; part of the results can be extended when we only assume a finite second-order moment.

Introduction

In many situations, some properties of a time series change over time, such as the mean, the variance or higher-order moments. Change-point detection is the long standing question of finding both the number and the localization of such changes. This is an important front-end task in many applications. For instance, detecting changes occuring in comparative genomic hybridization array data (CGH arrays) is crucial to the early diagnosis of cancer [START_REF] Lai | Comparative analysis of algorithms for identifying amplifications and deletions in array CGH data[END_REF]. In finance, some intensively examined time series like the volatility process exhibit local homogeneity and it is useful to be able to segment these time series both for modeling and forecasting [START_REF] Lavielle | Detection of multiple changepoints in multivariate time series[END_REF][START_REF] Spokoiny | Multiscale local change point detection with applications to value-at-risk[END_REF]. Change-point detection can also be used to detect changes in the activity of a cell [START_REF] Ritov | Detection of onset of neuronal activity by allowing for heterogeneity in the change points[END_REF], in the structure of random Markov fields [START_REF] Liu | Support consistency of direct sparse-change learning in Markov networks[END_REF], or a sequence of images [START_REF] Kim | Using labeled data to evaluate change detectors in a multivariate streaming environment[END_REF][START_REF] Abou-Elailah | Detection of Abrupt Changes in Spatial Relationships in Video Sequences[END_REF]. Generally speaking, it is of interest to the practitioner to segment a time series in order to calibrate its model on homogeneous sets of datapoints.

Addressing the change-point problem in practice requires to face several important challenges. First, the number of changes can not be assumed to be known in advance -in particular, it can not be assumed to be equal to 0 or 1 -, hence a practical change-point procedure must be able to infer the number of changes from the data. Second, changes do not always occur in the mean or the variance of the data, as assumed by most change-point procedures. We need to be able to detect changes in other features of the distribution. Third, parametric assumptions -which are often made for building or for analyzing change-point procedures -are often unrealistic, so that we need a fully non-parametric approach. Fourth, data points in the time series we want to segment can be high-dimensional and/or structured. If the dimensionality is larger than the number of observations, a non-asymptotic analysis is mandatory for theoretical results to be meaningful. When data are structured -for instance, histograms, graphs or strings -, taking their structure into account seems necessary for detecting efficiently the change-points.

We focus only on the offline problem in this article, that is, when all observations are given at once, as opposed to the situation where data come as a continuous stream. We refer to Tartakovsky, Nikiforov and Basseville [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF] for an extensive review of sequential methods, which are adapted to the later situation. Numerous offline change-point procedures have been proposed since the seminal works of Page [START_REF] Page | A test for a change in a parameter occurring at an unknown point[END_REF], Fisher [START_REF] Fisher | On grouping for maximum homogeneity[END_REF] and Bellman [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF], which are mostly parametric in essence. We refer to Brodsky and Darkhovsky [START_REF] Brodsky | Nonparametric methods in change point problems 243[END_REF]Chapter 2] for a review of non-parametric offline change-point detection methods. Among recent works in this direction, we can mention the Wild Binary Segmentation (WBS, [START_REF] Fryzlewicz | Wild binary segmentation for multiple changepoint detection[END_REF]) and the non-parametric multiple change-point detection procedure (NMCD, [START_REF] Zou | Nonparametric maximum likelihood approach to multiple change-point problems[END_REF]). Some authors also consider the case of high-dimensional data when only a few coordinates of the mean change at each change-point [53, and references therein], or the problem of detecting gradual changes [START_REF] Vogt | Detecting gradual changes in locally stationary processes[END_REF]; this paper does not address these slightly different problems.

To the best of our knowledge, no offline change-point procedure addressed simultaneously the four challenges mentioned above, until the kernel changepoint procedure (KCP) was proposed by Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF]. In short, KCP mixes the penalized least-squares approach to change-point detection [START_REF] Comte | A new algorithm for fixed design regression and denoising[END_REF][START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF] with semi-definite positive kernels [START_REF] Aronszajn | Theory of reproducing kernels[END_REF]. It is not the only procedure that uses positive semi-definite kernels to detect changes in a times series. Apart from Harchaoui and Cappé [START_REF] Harchaoui | Retrospective multiple changepoint estimation with kernels[END_REF], who introduced KCP for a fixed number of change-point, and Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF] who extended KCP to an unknown number of change-points, we are aware of several closely related work.

Maximum Mean Discrepancy [MMD,[START_REF] Gretton | A kernel method for the two-sample-problem[END_REF] has been used for building two sample tests; a block average version of the MMD, named the M -statistic, has lead to an online change-point detection procedure [START_REF] Li | M -Statistic for Kernel Change-Point Detection[END_REF]. A kernel-based statistic, named kernel Fisher discriminant ratio, has been used by Harchaoui, Moulines and Bach [START_REF] Harchaoui | Kernel changepoint analysis[END_REF] for homogeneity testing and for detecting one change-point. Sharipov, Tewes and Wendler [START_REF] Sharipov | Sequential block bootstrap in a Hilbert space with application to change point analysis[END_REF] build an analogue of the CUSUM statistic for Hilbert-valued random variables in order to detect a single change in the mean, and could be applied in our setting to the images of the observations in the feature space. Kernel change detection [START_REF] Desobry | An online kernel change detection algorithm[END_REF] is an online procedure that uses a kernel to build a dissimilarity measure between the near past and future of a data-point.

On the computational side, the KCP segmentation can be computed efficiently thanks to a dynamic programming algorithm [START_REF] Harchaoui | Retrospective multiple changepoint estimation with kernels[END_REF][START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], which can be made even faster [START_REF] Celisse | New efficient algorithms for multiple change-point detection with kernels[END_REF]. An oracle inequality for KCP is proved by Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF]; this is not exactly a result on change-point estimation, but a guarantee on estimation of the "mean" of the time series in the RKHS associated with the kernel chosen. The good numerical performance of KCP in terms of change-point estimation is also demonstrated in several experiments.

So, a key theoretical question remains open: does KCP estimate correctly the number of change-points and their locations with a large probability? If yes, at which speed does KCP estimate the change-point locations?

This paper answers these questions, showing that KCP has good theoretical properties for change-point estimation with independent data, under a boundedness assumption (Theorem 3.1 in Section 3.1). This result is non-asymptotic, hence meaningful for high-dimensional or complex data. In the asymptotic setting -with a fixed true segmentation and more and more data points observed within each segment -, Theorem 3.1 implies that KCP estimates consistently all changes in the "kernel mean" of the distribution of data, at speed log(n)/n with respect to the sample size n. Since we make no assumptions on the minimal size of the true segments, this matches minimax lower bounds [START_REF] Brunel | Convex set detection[END_REF]. We also provide a partial result under a weaker finite variance assumption (Theorem 3.2 in Section 3.3) and explain in Section 5 how our proofs could be extended to other settings, including the dependent case. These findings are illustrated by numerical simulations in Section 4.

An important case is when KCP is used with a characteristic kernel [START_REF] Fukumizu | Kernel Measures of Conditional Dependence[END_REF], such as the Gaussian or the Laplace kernel. Then, any change in the distribution of data induces a change in the "kernel mean". So, Theorem 3.1 implies that KCP then estimates consistently and at the minimax rate all changes in the distribution of the data, without any parametric assumption and without prior knowledge about the number of changes.

Our results also are interesting regarding to the theoretical understanding of least-squares change-point procedures. Indeed, when KCP is used with the linear kernel, it reduces to previously known penalized least-squares changepoint procedures [START_REF] Yao | Estimating the number of change-points via Schwarz' criterion[END_REF][START_REF] Comte | A new algorithm for fixed design regression and denoising[END_REF][START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF], for instance]. There are basically two kinds of results on such procedures in the change-point literature: (i) asymptotic statements on change-point estimation [START_REF] Yao | Estimating the number of change-points via Schwarz' criterion[END_REF][START_REF] Yao | Least-squares estimation of a step function[END_REF][START_REF] Bai | Estimating and testing linear models with multiple structural changes[END_REF][START_REF] Lavielle | Least-squares Estimation of an Unknown Number of Shifts in a Time Series[END_REF] and (ii) non-asymptotic oracle inequalities [START_REF] Comte | A new algorithm for fixed design regression and denoising[END_REF][START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF][START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], which are based upon concentration inequalities and model selection theory [START_REF] Birgé | Gaussian model selection[END_REF] but do not directly provide guarantees on the estimated changepoint locations. Our results and their proofs show how to reconciliate the two approaches when we are interested in change-point locations, which is already new for the case of the linear kernel, and also holds for a general kernel.

Kernel change-point detection

This section describes the general change-point problem and the kernel changepoint procedure [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF].

Change-point problem

Set 2 ≤ n < +∞ and consider X 1 , . . . , X n independent X -valued random variables, where X is an arbitrary (measurable) space. The goal of change-point detection is to detect abrupt changes in the distribution of the X i s. For any D ∈ {1, . . . , n} and any integers 0 = τ 0 < τ 1 < • • • < τ D = n, we define the segmentation τ := τ 0 , . . . , τ D of {1, . . . , n} as the collection of segments λ = {τ -1 + 1, . . . , τ }, ∈ {1, . . . , D}. We call change-points the right-end of the segments, that is the τ , ∈ {1, . . . , D}. We denote by T D n the set of segmentations with D segments and T n := n D=1 T D n the set of all segmentations of {1, . . . , n}. For any τ ∈ T n , we write D τ for the number of segments of τ . Figure 1 provides a visual example.

• • • • • • • • • • τ Fig 1.
We often represent the segmentations as above. The bullet points stand for the elements of {1, . . . , n}. Here, n = 10, Dτ = 3, τ 0 = 0, τ 1 = 3, τ 2 = 7 and τ 3 = 10.

An important example to have in mind is the following.

Example 2.1 (Asymptotic setting). Let K ≥ 1, 0 = b 0 < b 1 < • • • < b K < b K+1 =
1 and P 1 , . . . , P K+1 some probability distributions on X be fixed. Then, for any n and i ∈ {1, . . . , n}, we set t i := i/n and the distribution of X i is P j(i) where j(i) is such that t i ∈ [b j , b j+1 ). In other words, we have a fixed segmentation of [0, 1], given by the b j , a fixed distribution over each segment, given by the P j , and we observe independent realizations from the distributions at discrete times t 1 , . . . , t n . The corresponding true change-points in {0, . . . , n} are the nb j , j = 1, . . . , K. For n large enough, there are K + 1 segments. Figure 2 shows an example. Let us emphasize that in this setting, n going to infinity does not mean that new observations are observed over time. Recall that we consider the change-point problem a posteriori : a larger n means that we have been able to observe the phenomenon of interest with a finer time discretization. Also note that this asymptotic setting is restrictive in the sense that segments size asymptotically are of order n; we do not make this assumption in our analysis, which also covers asymptotic settings where some segments have a smaller size.

0.0 0.2 0.4 0.6 0.8 1.0 -2 -1 0 1 2 3 Fig 2.
Illustration of the asymptotic setting (Example 2.1) in the case of changes in the mean of the X i . Here, X = R, X i = f (t i ) + ε i with ε 1 , . . . , εn i.i.d. and centered, and f : [0, 1] → R is a (fixed) piecewise constant function (shown in red). The goal is to recover the number of abrupt changes of f (here, 2) and their locations (b 1 = 0.5 and b 2 = 0.7). Note that other kinds of changes in the distribution of the X i can be considered, see Section 4.

Kernel change-point procedure (KCP)

Let k : X × X → R be a positive semidefinite kernel, that is, a measurable function such that the matrix (k(x i , x j )) 1≤i,j≤m is positive semidefinite for any m ≥ 1 and x 1 , . . . , x m ∈ X [START_REF] Schölkopf | Learning with kernels: Support vector machines, regularization, optimization, and beyond[END_REF]. Classical examples of kernels are given by [4, section 3.2], among which:

-the linear kernel :

k lin (x, y) = x, y R p for x, y ∈ X = R p .
-the polynomial kernel of order d ≥ 1:

k poly d (x, y) = x, y R p + 1) d for x, y ∈ X = R p . -the Gaussian kernel with bandwidth h > 0: k G h (x, y) = exp[-x-y 2 /(2h 2 )] for x, y ∈ X = R p . -the Laplace kernel with bandwidth h > 0: k L h (x, y) = exp[-x -y /(2h 2 )] for x, y ∈ X = R p . -the χ 2 -kernel: k χ 2 (x, y) = exp -1 2 p i=1 (xi-yi) 2 xi+yi for x, y ∈ X the p- dimensional simplex.
As done by Harchaoui and Cappé [START_REF] Harchaoui | Retrospective multiple changepoint estimation with kernels[END_REF] and Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], for a given segmentation τ ∈ T D n , we assess the adequation of τ with the kernel least-squares criterion

R n (τ ) := 1 n n i=1 k(X i , X i ) (2.1) - 1 n D =1   1 τ -τ -1 τ i=τ -1 +1 τ j=τ -1 +1 k(X i , X j )   .
Elementary algebra shows that, when X = R p and k = k lin , R n is the usual least-squares criterion. Minimizing this criterion over the set of all segmentations always outputs the segmentation with n segments reduced to a point, that is [0, . . . , n]; this is a well-known overfitting phenomenon. To counteract this, a classical idea [36, for instance] is to minimize a penalized criterion crit(τ ) := R n (τ ) + pen(τ ), where pen : T n → R + is called the penalty. Formally, the kernel change-point procedure (KCP) of Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF] selects the segmentation

τ ∈ arg min τ ∈Tn crit(τ ) where crit(τ ) = R n (τ ) + pen(τ ) . (2.2)
In this paper, we focus on the classical choice of a penalty proportional to the number of segments, similarly to AIC, BIC and C p criteria. Namely, we consider pen(τ ) = pen (τ

) := CM 2 D τ n , (2.3)
where C is a positive constant and M is specified in Assumption 1 later on.

As mentioned in the Introduction, slightly different penalty shapes can be considered, as suggested by Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF]. Our results could be extended to the penalty of Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], but we choose to consider the linear penalty (2.3) only for simplicity.

The reproducing kernel Hilbert space

Let H be the reproducing kernel Hilbert space (RKHS) associated with k [5], together with the canonical feature map Φ : X → H

Φ : X → H x → Φ(x) := k(•, x) .
We write •, • H (resp. • H ) for the inner product (resp. the norm) of H. For any i ∈ {1, . . . , n}, define Y i := Φ(X i ) ∈ H. In the case where k = k lin , then Y i = •, X i R p and the empirical risk R n reduces to the least-squares criterion

R n (τ ) = 1 n Dτ =1 τ i=τ -1 +1 X i -X 2 ,
where X is the empirical mean of the X i over the segment {τ -1 + 1, . . . , τ }.

It is well-known that penalized least-squares procedures detect changes in the mean of the observations X i , see Yao [START_REF] Yao | Estimating the number of change-points via Schwarz' criterion[END_REF]. Hence the kernelized version of this least-squares procedure, KCP, should detect changes in the "mean" of the Y i = Φ(X i ), which are a nonlinear transformation of the X i . More precisely, assume that H is separable and that ∀i ∈ {1, . . . , n}, E k(X i , X i ) < +∞ .

Then µ i , the Bochner integral of Y i , is well-defined [START_REF] Ledoux | Probability in Banach Spaces: isoperimetry and processes 23[END_REF]. The condition above is satisfied in our setting (when either Assumption 1 or Assumption 2 holds true, see Section 2.5), and H is separable in most cases [START_REF] Dieuleveut | Nonparametric stochastic approximation with large step-sizes[END_REF]. The Bochner integral commutes with continuous linear operators, hence the following property holds, which will be of common use:

∀g ∈ H, µ i , g H = E g(X i ) = E Y i , g H .
We now define the "true segmentation" τ ∈ T n by

µ 1 = • • • = µ τ 1 , µ τ 1 +1 = • • • = µ τ 2 , • • • µ τ D τ -1 +1 = • • • = µ n and ∀i ∈ {1, . . . , D τ -1}, µ τ i = µ τ i+1 (2.4) with 1 ≤ τ 1 < • • • < τ D τ -1 ≤ n.
We call the τ i s the true change-points. It should be clear that it is always possible to define τ . A kernel is said to be characteristic if the mapping P → E X∼P [Φ(X)] is injective, for P belonging to the set of Borel probability measures on X [START_REF] Sriperumbudur | Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions[END_REF]. In simpler terms, when k is a characteristic kernel, X i and X i+1 have the same distribution if and only if µ i = µ i+1 , and τ indeed corresponds to the set of changes in the distribution of the X i . For instance, all strictly positive definite kernels are characteristic, including the Gaussian kernel, see Sriperumbudur et al. [START_REF] Sriperumbudur | Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions[END_REF]. Therefore, in the setting of Example 2.1, for n large enough, D τ = K + 1 and τ = nb for = 1, . . . , K.

For a general kernel, some changes of P Xi , the distribution of X i , might not appear in τ . For instance, with the linear kernel, τ only corresponds to changes of the mean of the X i . In most cases, a characteristic kernel is known and we can choose to use KCP with a characteristic kernel; then, as we prove in the following, KCP eventually detects any change in the distribution of the observations. But one can also choose a non-characteristic kernel on purpose, hence focusing only on some changes in the distribution of the X i . For instance, the polynomial kernel of order d is not characteristic and leads to the detection of changes in the first d moments of the distribution; with the linear kernel, KCP detects changes in the mean of the X i .

From now on, we focus on the problem of detecting the changes of τ only, whether the kernel is characteristic or not.

Rewriting the empirical risk

It is convenient to see the images of the observations by the feature map as an element of H n . To this extent, we define Y := (Y 1 , . . . , Y n ), as well as µ := (µ 1 , . . . , µ n ) ∈ H n and ε := Y -µ ∈ H n . We identify the elements of H n with the set of applications {1, . . . , n} → H, naturally embedded with the inner product and norm given by ∀x, y ∈ H n , x, y := n i=j

x j , y j H and

x 2 := n j=1 x j 2 H .
We now rewrite the empirical risk as a function of τ and Y . For any segmentation τ ∈ T n , define F τ the set of applications {1, . . . , n} → H that are constant over the segments of τ . We see F τ as a subspace of H n as a vector space. Take f ∈ H n , we define Π τ f the orthogonal projection of f onto F τ with respect to

• : Π τ f ∈ arg min g∈Fτ f -g .
It is shown by Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF] that for any f ∈ H n and any

∈ {1, . . . , D τ }, ∀i ∈ {τ -1 + 1, . . . , τ }, (Π τ f ) i = 1 |τ -τ -1 | τ j=τ -1 +1 f j . (2.5)
We are now able to write the empirical risk as

R n (τ ) = 1 n Y -µ τ 2 , (2.6)
where µ τ = Π τ Y , following [START_REF] Harchaoui | Retrospective multiple changepoint estimation with kernels[END_REF][START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF].

Assumptions

A key ingredient of our analysis is the concentration of ε. Intuitively, the performance of KCP is better when ε concentrates strongly around its mean, since without noise we are just given the task to segment a piecewise-constant signal.

It is thus natural to make assumptions on ε in order to obtain concentration results. We actually formulate assumptions on the kernel k, which translate automatically onto ε.

As done by Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], the main hypothesis used in our analysis is the following.

Assumption 1. A positive constant M exists such that ∀i ∈ {1, . . . , n}, k(X i , X i ) ≤ M 2 < +∞ a.s. If Assumption 1 holds true, ∀i ∈ {1, . . . , n}, Y i H = k(X i , X i ) ≤ M a.s.
and Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF] show that ε i H ≤ 2M almost surely. Assumption 1 is always satisfied for a large class of commonly used kernels, such as the Gaussian, Laplace and χ 2 kernels.

Note that Assumption 1 is weaker than assuming k to be bounded -that is, k(x, x) ≤ M for any x ∈ X , which is equivalent to k(x, x ) ≤ M for any x, x ∈ X since k is positive definite. For instance, if X = R p and the data X i are bounded almost surely, Assumption 1 holds true for the linear kernel and all polynomial kernels, which are not bounded on R p .

In the setting of Example 2.1, Assumption 1 holds true when ∀j ∈ {1, . . . , K}, k(x, x) ≤ M 2 for P j -a.e. x ∈ X .

It is sometimes possible to weaken Assumption 1 into a finite variance assumption.

Assumption 2. A positive constant V < +∞ exists such that max 1≤i≤n E ε i 2 H ≤ V. Since v i := E[ ε i 2 H ] = E [k(X i , X i )] -µ i 2 H , Assumption 2 holds true when ∀i ∈ {1, . . . , n}, E k(X i , X i ) ≤ V .
As a consequence, Assumption 1 implies Assumption 2 with V = M 2 . Note that Assumption 2 is satisfied for the polynomial kernel of order d provided that ∀i ∈ {1, . . . , n}, E X i 2d < +∞.

In the setting of Example 2.1, Assumption 2 holds true with

V = max 1≤ ≤K+1 E X∼P k(X, X) ,
provided this maximum is finite.

Theoretical guarantees for KCP

We are now able to state our main results. In Section 3.1, we state the main result of the paper, Theorem 3.1, which provides simple conditions under which KCP recovers the correct number of segments and localizes the true changepoints with high probability, under the bounded kernel Assumption 1. Then, Section 3.2 details a few classical losses between segmentations which can be considered in addition to the one used in Theorem 3.1. Corollary 3.1 formulates a result on τ in terms of the Frobenius loss. Finally, Section 3.3 states a partial result on KCP -requiring the number of change-points D τ to be knownunder the weaker Assumption 2.

Main result

We first need to define some quantities. The size of the smallest jump of

µ in H is ∆ := min i / µ i =µ i+1 µ i -µ i+1 H . (3.1)
Intuitively, the higher ∆ is, the easier it is to detect the smallest jump with our procedure. The quantity µ i -µ i+1 H is often called the (population) maximum mean discrepancy [MMD,[START_REF] Gretton | A kernel method for the two-sample-problem[END_REF] between the distributions of X i and X i+1 .

In the scalar setting (with the linear kernel), the ratio ∆/σ (where σ 2 is the variance of the noise) is called the signal-to-noise ratio [START_REF] Basseville | Detection of abrupt changes: theory and application[END_REF] and is often used as a measure of the magnitude of a change in the signal. In Example 2.1,

∆ = min 1≤j≤K µ Pj -µ Pj+1 H
where µ Pj denotes the (Bochner) expectation of Φ(X) when X ∼ P j .

For any τ ∈ T n , we denote the (normalized) sizes of its smallest and of its largest segment by

Λ τ := 1 n min 1≤ ≤Dτ |τ -τ -1 | and Λ τ := 1 n max 1≤ ≤Dτ |τ -τ -1 | . (3.2)
It should be clear that the smaller Λ τ is, the harder it is to detect the segment that achieves the minimum in equation (3.2). For instance, in the particular case of Example 2.1,

Λ τ -----→ n→+∞ min 0≤j≤K |b j+1 -b j | and Λ τ -----→ n→+∞ max 0≤j≤K |b j+1 -b j | .
For any τ 1 and τ 2 ∈ T n , we define

d (1) ∞ (τ 1 , τ 2 ) := max 1≤i≤D τ 1 -1 min 1≤j≤D τ 2 -1 τ 1 i -τ 2 j ,
which is a loss function (a measure of dissimilarity) between the segmentations τ 1 and τ 2 . Note that d

∞ is not a distance; other possible losses between segmentations and their relationship with d

∞ are discussed in Section 3.2. Theorem 3.1. Suppose that Assumption 1 holds true. For any y > 0, an event Ω of probability at least 1 -e -y exists on which the following holds true. For any C > 0, let τ be defined as in Eq. (2.2) with pen defined by Eq. (2.3). Set

C min := 74 3 (D τ + 1)(y + log n + 1) and C max := ∆ 2 M 2 Λ τ 6D τ n .
Then, if

C min < C < C max , (3.3)
on Ω, we have

D τ = D τ and 1 n d (1) ∞ τ , τ ≤ v 1 (y) := 148D τ M 2 ∆ 2 • y + log n + 1 n .
We delay the proof of Theorem 3.1 to Section 6.4. Some remarks follow.

Theorem 3.1 is a non-asymptotic result: it is valid for any n ≥ 1 and there is nothing hidden in o(1) remainder terms. The latter point is crucial for complex data -for instance, X = R p with p > n -since in this case, assuming X fixed while n → +∞ is not realistic.

Nevertheless, it is useful to write down what Theorem 3.1 becomes in the asymptotic setting of Example 2.1. As previously noticed, D τ , Λ τ , ∆ 2 and M 2 then converge to positive constants as n → +∞. Therefore, C min is of order log(n), C max is of order n and we always have C min < C max for n large enough. The upper bound on C matches classical asymptotic conditions for variable selection [START_REF] Shao | An asymptotic theory for linear model selection[END_REF]. The necessity of taking C of order at least log(n) is shown by Birgé and Massart [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] in a variable selection setting, which includes changepoint detection as a particular example; Birgé and Massart [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF], Abramovich et al. [START_REF] Abramovich | Adapting to unknown sparsity by controlling the false discovery rate[END_REF] provide several arguments for the optimality of taking a constant C of order log(n). When C satisfies (3.3), the result of Theorem 3.1 implies that P (D τ = D τ ) → 1. For the linear kernel in R d , this is a well-known result when the distribution of the X i changes only through its mean. The first result dates back to Yao [54, Section 2] for a Gaussian noise, later extended by Liu, Wu and Zidek [START_REF] Liu | On segmented multivariate regression[END_REF] and Bai and Perron [6, Section 3.1] under mixingale hypothesis on the error, and Lavielle and Moulines [START_REF] Lavielle | Least-squares Estimation of an Unknown Number of Shifts in a Time Series[END_REF] under very mild assumptions satisfied for a large family of zero-mean processes [for the precise statement of the hypothesis, see 37, Section 2.1]. Theorem 3.1 also shows that the normalized estimated change-points of τ converge towards the normalized true change-points at speed at least log(n)/n.

Up to a logarithmic factor, this speed matches the minimax lower bound n -1 which has been obtained previously for various change-point procedures [32, 12, 33, for instance] including least-squares [START_REF] Lavielle | Least-squares Estimation of an Unknown Number of Shifts in a Time Series[END_REF], assuming that Λ τ ≥ κ > 0. When D τ ≥ 3 and the assumption on Λ τ is removed -that is, segments of length much smaller than n are allowed, which is compatible with Theorem 3.1 since it is non-asymptotic-, Brunel [START_REF] Brunel | Convex set detection[END_REF]Theorem 6] shows a minimax lower bound of order log(n)/n. Therefore, in this setting, KCP achieves the minimax rate. We do not know whether KCP remains minimax optimal (without the log factor) under the assumption Λ τ ≥ κ > 0.

Note finally that KCP also performs well for finite samples, according to the simulation experiments of Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF]. Theorem 3.1 emphasizes the key role of ∆ 2 /M 2 , which can be seen as a generalization of the signal-to-noise ratio, for the change-point detection performance of KCP. The larger is this ratio, the easier it is to have Eq. (3.3) satisfied and the smaller is v 1 (y). This suggests to choose k (theoretically at least) by maximizing ∆ 2 /M 2 , as we discuss in Section 5. Note that ∆ 2 /M 2 is invariant by a rescaling of k, hence the result of Theorem 3.1 is unchanged when k is rescaled.

The hypothesis in Eq. (3.3) is actually three-fold. First, we use that C > C min to get D τ ≤ D τ . We have to assume C large enough since a too small penalty leads to selecting (with KCP or any other penalized least-squares procedure) the segmentation with n segments, that is D τ = n. Second, C < C max is used to get D τ ≥ D τ . Such an assumption is required since taking a penalty function too large in Eq. (2.2) would result in selecting the segmentation with only one segment, that is, D τ = 1. Third, C max has to be greater than C min for providing a non-empty interval of possible values for C. This inequality is also used in the proof of the upper bound on d

(1)
∞ τ , τ when we already know that D τ = D τ . In Example 2.1, the C min < C max hypothesis translates into Λ τ log(n)/n. That is, the size of the smallest segment has to be of order log n/n. This is known to be a necessary condition to obtain the minimax rate in multiple change-point detection [14, section 2].

Theorem 3.1 helps choosing C, which is a key parameter of KCP, as in any penalized model selection procedure. However, in practice, we do not recommend to directly use equation (3.3) for choosing C for two reasons: C min , C max depend on unknown quantities D τ , Λ τ , ∆, and the exact values of the constants in C min , C max might be pessimistic compared to what we can observe from simulation experiments. We rather suggest to use a data-driven method for choosing C, see Section 5.

If we know D τ , we can replace τ by

τ (D τ ) ∈ arg min τ ∈T D τ n R n (τ ) .
Then, assuming that Λ τ > v 1 (y) -which is weaker than assuming C min < C max -, the proof of Theorem 3.1 shows that, on Ω, we have

1 n d (1) ∞ τ , τ (D τ ) ≤ v 1 (y) .

Loss functions between segmentations

Theorem 3.1 shows that τ is close to τ in terms of d

∞ . Several other loss functions (measures of dissimilarity) can be defined between segmentations [START_REF] Hubert | Comparing partitions[END_REF]. We here consider a few of them, which are often used or natural for the changepoint problem.

Let us first consider losses related to the Hausdorff distance. For any τ 1 and τ 2 ∈ T n , we define

d (1) ∞ (τ 1 , τ 2 ) := max 1≤i≤D τ 1 -1 min 1≤j≤D τ 2 -1 τ 1 i -τ 2 j d (2) ∞ (τ 1 , τ 2 ) := max 1≤i≤D τ 1 -1 min 0≤j≤D τ 2 τ 1 i -τ 2 j d (i) H (τ 1 , τ 2 ) := max d (i) ∞ (τ 1 , τ 2 ), d (i) ∞ (τ 2 , τ 1 ) for i ∈ 1, 2 . Whenever D τ 1 = D τ 2 , we define d (3) ∞ (τ 1 , τ 2 ) := max 1≤i≤D τ 1 -1 τ 1 i -τ 2 i . Note that d (3)
∞ is symmetric thus there is no need to define d

H . One could also define d [START_REF] Abou-Elailah | Detection of Abrupt Changes in Spatial Relationships in Video Sequences[END_REF] H as the Hausdorff distance between the subsets {τ 1 1 , . . . , τ 1 D τ 1 -1 } and {τ 2 1 , . . . , τ 2 D τ 2 -1 } with respect to the distance δ(x, y) = |x -y| on R. These definitions are illustrated by Figure 3.

• • • • • • • • • • • • • • • • • • • τ 1 τ 2 d (2) ∞ (τ 2 , τ 1 ) d (1) ∞ (τ 1 , τ 2 ) d (2)
∞ (τ 1 , τ 2 ) Fig 3. Illustration of the definition of d (i)
∞ , with n = 19, τ 1 = 0, 8, 17, 19 and τ 2 = 0, 7, 14, 19 . In this example,

D τ 1 = D τ 2 = 3. We can compute d (1) ∞ (τ 1 , τ 2 ) = d (1) ∞ (τ 2 , τ 1 ) = d (2) ∞ (τ 2 , τ 1 ) = d (3) ∞ (τ 1 , τ 2 ) = 3 and d (2) ∞ (τ 1 , τ 2 ) = 2.
Interestingly, all these loss functions coincide whenever n

-1 d (1) ∞ (τ 1 , τ 2
) is small enough. The following lemma makes this claim rigorous. Lemma 3.1. We have the following two properties.

(i) For any τ 1 , τ 2 ∈ T n such that

1 n d (1) ∞ (τ 1 , τ 2 ) < 1 2 min Λ τ 1 , Λ τ 2 ,
we have

D τ 1 = D τ 2 and d (1) ∞ (τ 1 , τ 2 ) = d (2) ∞ (τ 1 , τ 2 ) = d (3) ∞ (τ 1 , τ 2 ) = d (1)
H (τ 1 , τ 2 ) = d (2)
H (τ 1 , τ 2 ).

(ii) For any τ 1 , τ 2 ∈ T n such that

D τ 1 = D τ 2 and 1 n d (1) ∞ (τ 1 , τ 2 ) < Λ τ 1 2 , we have d (1) ∞ (τ 1 , τ 2 ) = d (1) ∞ (τ 2 , τ 1 ) = d (1)
H (τ 1 , τ 2 ) . Lemma 3.1 is proved in Section B.1. As a direct application of Lemma 3.1 we see that the statement of Theorem 3.1 holds true with d

(1)
∞ replaced by any of the loss functions that we defined above, at least for n large enough.

Another loss between segmentations is the Frobenius loss [START_REF] Lajugie | Large-margin metric learning for constrained partitioning problems[END_REF], which is defined as follows. For any

τ 1 , τ 2 ∈ T n , d F (τ 1 , τ 2 ) := Π τ 1 -Π τ 2 F ,
where Π τ is the orthogonal projection onto F τ , as defined in Section 2.4, and

• F denotes the Frobenius norm of a matrix:

∀A ∈ R N ×M , A 2 F := N i=1 M j=1 A 2 ij .
A closed-form formula for d F can be derived from the matrix representation of Π τ that is given by (2.5): for any i, j ∈ {1, . . . , n},

(Π τ ) i,j = 1 |λ|
if i and j belong to the same segment λ of τ 0 otherwise.

An interesting feature of the Frobenius loss is that it is smaller than one only when τ 1 and τ 2 have the same number of segments, whereas Hausdorff distances can be small with very diffferent numbers of segments. Indeed, we prove in Section B.2 that

|D τ 1 -D τ 2 | ≤ d F (τ 1 , τ 2 ) 2 ≤ D τ 1 + D τ 2 .
(3.4)

The next proposition shows that there is an equivalence (up to constants) between the Hausdorff and Frobenius losses between segmentations, provided that they are close enough.

Proposition 3.1. Suppose that D τ 1 = D τ 2 and 1 n d (1)
∞ (τ 1 , τ 2 ) < Λ τ 1 /2, then d F (τ 1 , τ 2 ) 2 ≤ 12D τ 1 Λ τ 1 1 n d (1) ∞ (τ 1 , τ 2 ) . If in addition 1 n d (1)
∞ (τ 1 , τ 2 ) < Λ τ 1 /3, then 2 3Λ τ 1 1 n d (1) ∞ (τ 1 , τ 2 ) ≤ d F (τ 1 , τ 2 ) 2 .
Proposition 3.1 was first stated and proved by [START_REF] Lajugie | Large-margin metric learning for constrained partitioning problems[END_REF]Theorem B.2]. We prove it in Section B.2 for completeness.

As a corollary of Theorem 3.1 and Proposition 3.1, we get the following guarantee on the Frobenius loss between τ and the segmentation τ estimated by KCP.

Corollary 3.1. Under the assumptions of Theorem 3.1, on the event Ω defined by Theorem 3.1, for any τ satisfying (2.2) with pen defined by (2.3), we have:

d F (τ , τ ) ≤ 43D τ Λ τ • M ∆ y + log n + 1 n .
Note that Corollary 3.1 gives a better result (at least for large n) than the obvious bound

d F (τ , τ ) ≤ D τ + D τ -2 .
Proof. On the event Ω, we have

1 n d (1)
∞ (τ , τ ) < Λ τ /(D τ + 1) and D τ = D τ . Therefore, according to Proposition 3.1,

d F (τ , τ ) 2 ≤ 12D τ Λ τ 1 n d (1) ∞ (τ , τ ) ≤ 1776D 2 τ (y + log n + 1) nΛ τ • M 2 ∆ 2 .
Up to this point, we assessed the quality of the segmentation τ by considering the proximity of τ with τ . Another natural idea is to measure the distance between µ and µ τ in H n . It is closely related to the oracle inequality proved by Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], which implies an upper bound on µ -µ τ 2 .

We can also observe that there is a simple relationship between µ -µ τ 2 and the Frobenius distance between τ and τ . Indeed,

µ -µ τ 2 = (Π τ -Π τ )µ 2 ≤ Π τ -Π τ 2 2 µ 2 ≤ d F (τ , τ ) 2 µ 2 .
(3.5) Equation (6.9) in the proof of Theorem 3.1 shows that on Ω, under the assumptions of Theorem 3.1,

µ -µ τ 2 ≤ 74 y + log(n) + 1 D τ M 2
which is slightly better (but similar) to what Corollary 3.1, equation (3.5) and the bound µ 2 ≤ M 2 n imply.

Extension to the finite variance case

Theorem 3.1 is valid under a boundedness assumption (Assumption 1). What happens under the weaker Assumption 2? As a first step, we provide a result for

τ (D τ , δ n ) ∈ arg min τ ∈T D τ n / Λ τ ≥δn R n (τ ) (3.6)
for some δ n > 0. In other words, we restrict our search to segmentations τ of the correct size -hence D τ must be known a priori -and having no segment with less than nδ n observations. We discuss how to relax this restriction right after the statement of Theorem 3.2. Note that the dynamic programming algorithm of Harchaoui and Cappé [START_REF] Harchaoui | Retrospective multiple changepoint estimation with kernels[END_REF] can be used for computing τ (D τ , δ n ) efficiently.

Similarly to ∆, we define ∆ := max i µ i -µ i+1 H .

Theorem 3.2. Suppose that Assumption 2 holds true. For any δ n , y > 0, define:

v 2 (y, δ n ) := 24(D τ ) 2 ∆ √ V ∆ 2 y √ n + 8D τ V ∆ 2 y 2 nδ n .
For any y > 0, an event Ω 2 exists such that

P (Ω 2 ) ≥ 1 - 1 y 2
and, on Ω 2 , we have the following: for any δ n ∈ (0, Λ τ ] and any τ (D τ , δ n ) satisfying Eq.

(3.6), if v 2 (y, δ n ) ≤ Λ τ , 1 n d (1) ∞ τ , τ (D τ , δ n ) ≤ v 2 (y, δ n ) . (3.7)
We postpone the proof of Theorem 3.2 to Section 6.5. Let us make a few remarks.

As for Theorem 3.1, our result is non-asymptotic. However, it is interesting to write it down in the setting of Example 2.1. If n goes to infinity, then the assumption Λ τ ≥ δ n is satisfied whenever δ n → 0. If we furthermore require that nδ n → ∞, then Eq. (3.7) implies that

1 n d (1) ∞ τ , τ (D τ , δ n ) P -----→ n→+∞ 0 ,
by taking a well-chosen y of order √ n + √ nδ n . In the particular case of the linear kernel, this result is known under various hypothesis [37, for instance]; it is new for a general kernel.

More precisely, if we take δ n = n -1/2 , Theorem 3.2 implies that

1 n d (1) ∞ τ , τ (D τ , n -1/2 )
goes to zero at least as fast as n / √ n, where ( n ) n≥1 is any sequence tending to infinity, for instance n = log(n). This speed seems suboptimal compared to previous results [37, for instance] -which do not consider the case of a general kernel -, but we have not been able to prove tight enough deviation bounds for getting the localization rate log(n)/n under Assumption 2.

How does Theorem 3.2 compares to Theorem 3.1? First, as noticed by Remark 6.4 in Section 6.4, the result of Theorem 3.1 also holds true for τ (D τ , δ n ) as long as Λ τ ≥ δ n . Second, v 1 (y) is usually smaller than v 2 (y, δ n ) -its order of magnitude is smaller when n → +∞ -, and the lower bound on the probability of Ω is better than the one for Ω 2 . There is no surprise here: the stronger Assumption 1 helps us proving a stronger result for τ (D τ , δ n ). Nevertheless, these only are upper bounds, so we do not know whether the performance of τ (D τ , δ n ) actually changes much depending on the noise assumption. For instance, as already noticed, we do not believe that the localization speed log(n)/n requires a boundedness assumption; in particular cases at least, it has been obtained for unbounded data [START_REF] Lavielle | Least-squares Estimation of an Unknown Number of Shifts in a Time Series[END_REF][START_REF] Boysen | Consistencies and rates of convergence of jump-penalized least squares estimators[END_REF].

The dependency in k of the speed of convergence of τ (D τ , δ n ) is slightly less clear than in Theorem 3.1. The signal-to-noise ratio appears through ∆ 2 /V , as expected, but the size ∆ of the largest true jump also appears in v 2 . At the very least, it is clear that ∆ 2 /V should not be too small.

As noted by Lavielle and Moulines [START_REF] Lavielle | Least-squares Estimation of an Unknown Number of Shifts in a Time Series[END_REF], it may be possible to get rid of the minimal segment length δ n , either by imposing stronger conditions on εwhich are not met in our setting -or by constraining the values of µ to lie in a compact subset Θ ⊂ H D τ +1 .

Numerical simulations

One consequence of our main result, Theorem 3.1, is that for a bounded kernel, the KCP procedure is consistent in the asymptotic setting presented in Example 2.1. We now illustrate this fact by a simulation study. Detecting changes in the mean with the Gaussian kernel Let us consider the archetypic change-point detection problem -finding changes in the mean of a sequence of independent random variables-and show how these changes are localized more precisely when more data are available. We define three functions µ m : [0, 1] → R, 1 ≤ m ≤ 3, previously used by Arlot and Celisse [START_REF] Arlot | Segmentation of the mean of heteroscedastic data via cross-validation[END_REF], which cover a variety of situations (see Fig. 4). For each m ∈ {1, 2, 3} and several values of n between 10 2 and 10 3 , we repeat 10 3 times the following:

-Sample n independent Gaussian random variables g i ∼ N (0, 1); -Set X i = µ m (i/n) + g i -Fig. 4 shows one sample for each m ∈ {1, 2, 3}; -Perform KCP with Gaussian kernel and linear penalty on X 1 , . . . , X n ; the penalty constant is chosen as indicated in Section 5, the bandwidth is set to 0.1, and the maximum number of change-points is set to 30; -Compute d

(2) H (τ , τ n ).
The results are collected in Fig. 5, where each graph corresponds to a regression function µ m . We represent in logarithmic scale the mean distance between the true segmentation and the estimated segmentation for each value of n. The error bars are ± σ/ √ N , where σ is the empirical standard deviation over N = 10 3 repetitions. We want to emphasize that, though these experiments illustrate our main result Theorem 3.1, they are carried out in a slightly different setting since the penalty constant C is not chosen according to equation (3.3), but using the dimension jump heuristic [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF].

H (τ , τn) towards 0 when the number of data points n is increasing. A linear regression between log n and 1 n d

H (τ , τn) for n ≥ 300 yields slope estimates -0.97, -1.04 and -1.00, respectively.

The three segmentation problems considered here are quite different in nature, but all lead to a linear convergence rate (slopes close to -1 on the graphs of Figure 5) with different constants (different values for the intercept on the graphs of Figure 5). Recall that Theorem 3.1 combined with Lemma 3.1 states that, with high probability,

1 n d (2)
H (τ , τ n ) v 1 = D τ M 2 ∆ 2 • log n n .
Hence, whenever D τ , ∆ and M are fixed, 1 n d

H (τ , τ n ) converges to 0 at rate at least log n/n when the number of data points increases. In our experimental setting, these quantities are fixed, and the observed convergence rate matches our theoretical upper bound. The performance of KCP still depends on the regression function µ m experimentally, by a constant multiplicative factor, like the theoretical bound v 1 .

Detecting changes in the number of modes Let us now consider data X 1 , . . . , X n ∈ R whose distribution vary only through the number of modes. Can we accurately detect such changes with the KCP procedure? The data are generated according to the following process for several n:

-Set τ 1 = n/3 and τ 2 = 2n/3 ; -Draw X 1 , . . . , X τ 1 , X τ 2 +1 , . . . , X n according to a standard Gaussian distribution, and X τ 1 +1 , . . . , X τ 2 according to a (1/2, 1/2)-mixture of Gaussian distributions N (δ, 1 -δ 2 ) and N (-δ, 1 -δ 2 ), with δ = 0.999; the X i are independent.

We test KCP with various kernels assuming that the number of change-points (D τ = 3) is known; this simplification avoids possible artifacts linked to the choice of the penalty constant. Results are shown on Figure 6. The X i all have zero mean and unit variance, hence a classical penalized least-squares procedure -KCP with the linear kernel-is expected to detect poorly the changes in the distribution of the X i , as confirmed by Figure 6 (for instance, according to the right panel, it is not consistent). On the contrary, a Gaussian kernel with wellchosen bandwidth yields much better performance according to the middle and right panels of Figure 6 (with a rate of order 1/n).

H (τ , τn) vs. n in log scale, for KCP with a Gaussian kernel with bandwidth 0.01 (blue solid line; estimated slope -1.05) and with the linear kernel (red dashed line; estimated slope 0.16).

Discussion

Before proving our main results, let us discuss some of their consequences regarding the KCP procedure.

Fully non-parametric consistent change-point detection We have proved that for any kernel satisfying some reasonably mild hypotheses, the KCP procedure outputs a segmentation closeby the true segmentation with high probability.

An important particular example is the "asymptotic setting" of Example 2.1, where we have a fixed true segmentation τ and fixed distributions P 1 , . . . , P K+1 from which more and more points are sampled. How fast can KCP recover τ , without any prior information on the number of segments D τ or on the distributions P 1 , . . . , P K+1 ?

Let us take a bounded characteristic kernel -for instance the Gaussian or the Laplace kernel if X = R d -, so that Assumption 1 holds true. Then, Theorem 3.1 shows that KCP detects consistently all changes in the distribution of the X i , and localizes them at speed log(n)/n. This speed also depends on the adequation between the kernel k and the differences between the P j , through the ratio ∆ 2 /M 2 . Obtaining such a fully non-parametric result for multiple changepoints with a general set X -we only need to know a bounded characteristic kernel on X -has never been obtained before. To the best of our knowledge, non-parametric consistency results for the detection of arbitrary changes in the distribution of the data have only been obtained for real-valued data [START_REF] Zou | Nonparametric maximum likelihood approach to multiple change-point problems[END_REF] or for the case of a single change-point [START_REF] Carlstein | Nonparametric change-point estimation[END_REF][START_REF] Brodsky | Nonparametric methods in change point problems 243[END_REF].

Choice of k An important question remains: how to choose the kernel k? In Theorem 3.1, k only appears through the "signal-to-noise ratio" ∆ 2 /M 2 , leading to better theoretical guarantees when this signal-to-noise ratio is larger: a larger value for C max and a smaller bound v 1 on d

(1)
∞ τ , τ . Therefore, a simple strategy for choosing the kernel is to pick k that maximizes ∆ 2 /M 2 , at least among a family of kernels, for instance Gaussian kernels. This first idea requires to know the distributions of the X i , or at least to have prior information on them. Interestingly, when the change-points locations are known, ∆ 2 corresponds to the maximum mean discrepancy [MMD,[START_REF] Gretton | A kernel method for the two-sample-problem[END_REF] between the distributions of the X i over contiguous segments. In this particular setting, it is feasible to estimate and to maximize ∆ 2 with respect to the kernel k, as done by Gretton et al. [START_REF] Gretton | Optimal kernel choice for large-scale two-sample tests[END_REF]. An interesting future development would be to build an estimator of ∆ 2 without knowing the change-point locations and to maximize this estimator with respect to the kernel k. We refer to Arlot, Celisse and Harchaoui [4, section 7.2] for a complementary discussion about the choice of k for KCP.

Choice of C Another important parameter of the KCP procedure is the constant C that appears in the penalty function. As mentioned below Theorem 3.1, our theoretical guarantees provide some guidelines for choosing C, but these are not sufficient to choose precisely C in practice. We recommend to follow the advice of [4, section 6.2] on this point, which is to choose C from data with the "slope heuristic" [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF].

Modularity of the proofs and possible extensions Finally, we would like

to emphasize what we believe to be an important contribution of this paper. The structure of the proofs of Theorems 3.1 and 3.2 -which follow the same strategy -is modular, so that one can easily adapt it to different sets of assumptions.

Our proof strategy is not fully new, since it is similar to the one of almost all previous papers analyzing the consistency of least-squares change-point detection procedures. In particular, we adapted some ideas of the proofs of Lavielle and Moulines [START_REF] Lavielle | Least-squares Estimation of an Unknown Number of Shifts in a Time Series[END_REF] to the Hilbert space setting. Nevertheless, these papers formulate their main results in asymptotic terms, which can be seen as a limitation -especially when n is small or X is of large dimension. Another approach is the one of Lebarbier [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF], Comte and Rozenholc [START_REF] Comte | A new algorithm for fixed design regression and denoising[END_REF], Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF] where non-asymptotic oracle inequalities -using concentration inequalities and following the model selection results of Birgé and Massart [START_REF] Birgé | Gaussian model selection[END_REF] -are provided as theoretical guarantees on some penalized least-squares change-point procedures. Up to now, these two approaches seemed difficult to combine. The proofs of Theorems 3.1 and 3.2 show how they can be reconciled, which allows us to mix their strengths. Indeed, the assumptions on the distributions of the X i -Assumptions 1 and 2-are only used for proving bounds on two quantities -a linear term L τ and a quadratic term Q τ -, uniformly over τ ∈ T n . Under Assumption 1, this is done thanks to concentration inequalities (Lemmas 6.7 and 6.8) which have been proved first by Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF] in order to get an oracle inequality. Under Assumption 2, this is done by generalizing the method of Lavielle and Moulines [START_REF] Lavielle | Least-squares Estimation of an Unknown Number of Shifts in a Time Series[END_REF] to Hilbert-space valued data, through two deterministic bounds (Lemmas 6.5 and 6.6) and a deviation inequality for

M n := max 1≤k≤n k j=1
ε j H (Lemma 6.10). The rest of the proofs does not use anything about the distribution of X 1 , . . . , X n .

As a consequence, if one can generalize these bounds to another setting, a straightforward consequence is that a result similar to Theorem 3.1 or 3.2 holds true for the KCP procedure in this new setting. In particular, this could be used for dealing with the case of dependent data X 1 , . . . , X n . We could also consider an intermediate assumption between Assumption 2 and Assumption 1, of the form: max

1≤i≤n E k(X i , X i ) α ≤ B α < +∞
for some α ∈ (1, +∞).

Proofs

Let us start by describing our general strategy for proving our main results. Our goal is to build a large probability event on which any τ ∈ arg min τ ∈Tn crit(τ ) belongs to some subset E of T n . For proving this, we use the key fact that crit(τ ) ≥ crit( τ ), together with a lower bound on crit(τ ) holding simultaneously for all τ ∈ T n -hence for τ = τ . In order to get such a lower bound on the empirical penalized criterion, we start by decomposing it in Section 6.1 into terms that are simpler to control individually: two random terms -a linear function of ε and a quadratic function of ε -, and two deterministic terms -the approximation error and the penalty. Then, we control these terms thanks to deterministic bounds (Section 6.2) and deviation/concentration inequalities (Section 6.3). Finally, we prove Theorem 3.1 in Section 6.4 and Theorem 3.2 in Section 6.5.

Decomposition of the empirical risk

The first step in the proofs of Theorems 3.1 and 3.2 is to decompose the empirical risk (2.6). Lemma 6.1. Let τ ∈ T n be a segmentation. Define µ τ = Π τ µ . Then we can write

n R n (τ ) = Y -µ τ 2 = µ -µ τ 2 + 2 µ -µ τ , ε -Π τ ε 2 + ε 2 . (6.1) Proof. First, recall that µ τ = Π τ Y and that Y = µ + ε, hence Y -µ τ 2 = Y -Π τ Y 2 = µ + ε -Π τ (µ + ε) 2 = µ -Π τ µ 2 + ε -Π τ ε 2 + 2 µ -Π τ µ , ε -Π τ ε .
Since Π τ is an orthogonal projection,

Y -µ τ 2 = µ -µ τ 2 + ε 2 -2 ε, Π τ ε + Π τ ε 2 + 2 (Id -Π τ )µ , ε = µ -µ τ 2 + ε 2 -Π τ ε 2 + 2 (Id -Π τ )µ , ε .
Since each term of Eq. (6.1) behaves differently and is controlled via different techniques depending on the result to be proven, we name each of these terms:

L τ := µ -µ τ , ε , Q τ := Π τ ε 2 and A τ := µ -µ τ 2 . (6.2)
It should be clear that L stands for "linear", Q stands for "quadratic" and A stands for "approximation error". We also define

ψ τ := 2L τ -Q τ + A τ . (6.3)
Therefore a reformulation of Lemma 6.1 is

n R n (τ ) = ψ τ + ε 2 .
Notice that L τ = A τ = 0 and Q τ ≥ 0, hence ψ τ ≤ 0. Also note that ψ, L and Q are random quantities depending on ε.

Deterministic bounds

In this section, we provide some deterministic bounds that are used in the proofs of Theorems 3.1 and 3.2.

Approximation error A τ

We begin by the following result, which is the reason for the Λ τ ∆ 2 term in Theorem 3.1.

Lemma 6.2. Let τ ∈ T n be a segmentation such that D := D τ < D τ . Then

1 n A τ = 1 n µ -µ τ 2 ≥ 1 2 Λ τ ∆ 2 . ( 6.4)
The proof of Lemma 6.2 can be found in Section B.3.2.

Remark 6.1. Lemma 6.2 is tight. Indeed, consider the simple case D τ = 1 and D τ = 2. Assume that n = 2m is an even number, and let τ 1 = m. It follows from definitions (3.1) and (3.2) that, in this case,

∆ = µ 1 -µ n H and Λ τ = 1 2 .
According to Eq. (2.5), (µ τ ) i = 1 2 (µ 1 + µ n ), which yields

1 n A τ = 1 4 µ 1 -µ n 2 H = 1 2 Λ τ ∆ 2 .
Thus, in this particular class of examples, equality holds in (6.4).

We next state an analogous result, valid for any τ ∈ T n , which plays a key role in the proofs of Theorems 3.1 and 3.2. Lemma 6.3. For any τ ∈ T n ,

1 n A τ ≥ 1 2 min Λ τ , 1 n d (1) ∞ (τ , τ ) ∆ 2 . (6.5)
Lemma 6.3 is proved in Section B.4.

Linear term L τ and quadratic term Q τ

The proof of Theorem 3.2 relies on some deterministic bounds on L τ and Q τ . We start with a preliminary lemma.

Lemma 6.4. For any ε 1 , . . . , ε n ∈ H,

1 2 max 1≤a<b≤n b j=a ε j H ≤ max 1≤k≤n k j=1 ε j H =: M n . (6.6)
Proof. For every a < b, we have:

b j=a ε j H = b j=1 ε j - a-1 j=1 ε j H ≤ b j=1 ε j H + a-1 j=1 ε j H ≤ 2M n .
The following result is a deterministic bound on Q τ in terms of M n . Lemma 6.5. Let τ ∈ T n be a segmentation. Then

Q τ ≤ 4D τ M 2 n nΛ τ .
Proof. By Eq. (2.5),

Q τ = Dτ =1 1 |τ -τ -1 | τ j=τ -1 +1 ε j 2 H ≤ D τ max 1≤ ≤Dτ      1 |τ -τ -1 | τ j=τ -1 +1 ε j 2 H      ≤ D τ nΛ τ max 1≤ ≤Dτ τ j=τ -1 +1 ε j 2 H ≤ 4D τ nΛ τ M 2 n ,
where we used Lemma 6.4 for the last inequality.

The following result is a deterministic bound on L τ . Lemma 6.6. For any τ ∈ T n ,

|L τ | ≤ 6D τ max {D τ , D τ } ∆M n .
Lemma 6.6 is proved in Section B.5.

Concentration

In this subsection, we present concentration results on Q τ , L τ , and deviation bounds for M n -which will imply deviation bounds on Q τ and L τ by Lemmas 6.5 and 6.6). For any j ∈ {1, . . . , n}, τ ∈ T n and ∈ {1, . . . , D τ }, we define

v j := E ε j 2 H v τ, := 1 τ -τ -1 τ j=τ -1 +1 v j and v τ := D =1 v τ, .
Concentration under Assumption 1 The first result takes care of the linear term L τ when Assumption 1 is satisfied. Lemma 6.7 (Prop. 3 of Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF]). Suppose that Assumption 1 holds true. Then for any x > 0, with probability at least 1 -2 e -x , for any θ > 0,

|L τ | ≤ θA τ + 4 3 + 1 2θ M 2 x .
The next result deals with the quadratic term Q τ when Assumption 1 is satisfied. Lemma 6.8 (Prop. 1 of Arlot, Celisse and Harchaoui [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF]). Suppose that Assumption 1 holds true. Then for any x > 0, with probability at least 1 -e -x ,

Q τ -v τ ≤ x + 2 2xD τ 14M 2 3 .
We merge Lemmas 6.7 and 6.8 for convenience.

Lemma 6.9. Suppose that Assumption 1 holds true. Take any λ > 1 and τ ∈ T n be a segmentation. Then, there exists an event Ω

τ,λ of probability greater than 1 -3 e -λDτ on which:

ψ τ ≥ 1 3 A τ - 74 3 λD τ M 2 .
Proof. According to Lemma 6.7 with θ = 1/3 and x = λD τ , there exists an event Ω

(1)

τ,λ on which |L τ | ≤ 1 3 A τ + 17 6 λD τ M 2 , with P Ω (1) τ,λ ≥ 1 -2 e -λDτ .
Lemma 6.8 with x = λD τ gives Ω

τ,λ on which

Q τ -v τ ≤ 14 3 λ + 2 √ 2λ D τ M 2 , with P Ω (2)
τ,λ ≥ 1 -e -λDτ . Then, Ω

τ,λ := Ω

τ,λ ∩ Ω

τ,λ has a probability larger than 1 -3 e -λDτ by the union bound. Since for any 1

≤ ≤ D τ , v τ, ≤ M 2 , we have v τ = Dτ =1 v τ, ≤ D τ M 2 .
Hence, by definition (6.3) of ψ τ and using that λ ≥ 1, on the event Ω (0) τ,λ , we have:

ψ τ ≥ 1 3 A τ - 31 3 λ + 28 3 √ 2 √ λ + 1 D τ M 2 ≥ 1 3 A τ -λ 31 3 + 28 3 √ 2 + 1 D τ M 2 .
Remark 6.2. It is also possible to obtain an upper bound for ψ τ : by Lemma 6.7, for every λ ≥ 0, on the event Ω

(2)

τ,λ ⊂ Ω (0) τ,λ , ψ τ ≤ 5 3 A τ + 17 3 λD τ M 2 .
However, we do not need this result thereafter.

Concentration under Assumption 2 Lemma 6.5 and 6.6 directly translate upper bounds on M n into controls of L τ and Q τ . Under Assumption 2, this is achieved via the following lemma, a Kolmogorov-like inequality for the noise in the RKHS. This result is a straightforward generalization of the inequality obtained by Kolmogorov [31] into the Hilbert setting. A more precise result (for real random variables only) can be found in [START_REF] Hájek | Generalization of an inequality of Kolmogorov[END_REF], of which we follow the proof. The scheme of Hájek and Rényi [START_REF] Hájek | Generalization of an inequality of Kolmogorov[END_REF] adapts well in our setting even though we do not need the full result.

Lemma 6.10. If Assumption 2 holds true, then, for any x > 0,

P (M n ≥ x) ≤ 1 x 2 n j=1 v j . (6.7)
We prove Lemma 6.10 in Section B.6.

Remark 6.3. We can reformulate Lemma 6.10 as follows. For any y > 0, there exists an event of probability at least 1 -y -2 on which M n < y n i=j v j ≤ y √ nV . Equivalently, for any z ≥ 0, there exists an event of probability at least 1 -e -z such that M n < e z/2 n i=j v j ≤ e z/2 √ nV .

6.4. Proof of Theorem 3.1

We follow the strategy described at the beginning of Section 6.

Definition of Ω Let us define Ω := τ ∈Tn Ω (0) τ,λ with λ = y + log n + 1 > 1, where we recall that Ω (0) τ,λ is defined in Lemma 6.9. By the union bound, and since the Ω where the last inequality uses that n ≥ 2. From now on we work exclusively on Ω.

Key argument

We now make the simple (but crucial) observation that crit(τ ) ≥ crit( τ ), hence

n pen( τ ) + ψ τ ≤ n pen(τ ) + ψ τ ≤ n pen(τ ) = CD τ M 2 .
Since we work on Ω, by definition of Ω (0) τ,λ in Lemma 6.9, for any τ ∈ T n , we have:

ψ τ ≥ 1 3 A τ - 74 3 λD τ M 2 .
Therefore, we get:

CD τ M 2 ≥ 1 3 A τ + C - 74 3 λ D τ M 2 . (6.8)
Proof that D τ ≤ D τ Since C > 74λ/3 (by the lower bound in assumption (3.3)), M 2 > 0 and A τ ≥ 0, Eq. (6.8) implies that

D τ ≤ C C -74 3 λ D τ .
The lower bound in assumption (3.3) ensures that

C C -74 3 λ < D τ + 1 D τ hence D τ ≤ D τ on Ω.
Proof that D τ ≥ D τ Since C > 74λ/3 (by the lower bound in assumption (3.3)), Eq. (6.8) implies that

A τ ≤ 3CD τ M 2 . A direct consequence of (3.3) is that A τ < 1 2 nΛ τ ∆ 2 , hence D τ ≥ D τ by Lemma 6.2.

Loss between τ and τ

We have proved that D τ = D τ on Ω, therefore, Eq. (6.8) can be rewritten

A τ ≤ 74λD τ M 2 .
(6.9) By Lemma 6.3 and the definition of λ, we get min Λ τ ,

1 n d (1) ∞ (τ , τ ) ≤ 148D τ M 2 ∆ 2 • y + log n + 1 n = v 1 (y) . (6.10)
Remark that assumption (3.3) implies that

∆ 2 M 2 Λ τ 6D τ n > 74 3 (D τ + 1)(y + log n + 1) hence Λ τ > (D τ + 1) 148D τ M 2 ∆ 2 • y + log n + 1 n > v 1 (y) .
Therefore, Eq. (6.10) can be simplified into instead of (2.2), for any δ n ≥ 0 such that Λ τ ≥ δ n . Indeed, this assumption allows to write crit(τ ) ≥ crit( τ ) in the key argument, and the rest of the proof can stay unchanged (with the same event Ω). More generally, any constraint can be added in the argmin defining τ , provided that τ satisfies this constraint.

1 n d (1) ∞ (τ , τ ) ≤ v 1 (y) .
Proof of (ii) Since D τ 1 = D τ 2 , we can set D = D τ 1 = D τ 2 . Next, define φ(i) := arg min 1≤j≤D-1 τ 1 i -τ 2 j and C φ (i) := |φ(i)| for all i ∈ {1, . . . , D -1}. Clearly, C φ (i) ≥ 1 for any i. Let us show that we actually have C φ (i) = 1.

Take i and j distincts elements of {1, . . . , D -1}, and suppose that φ(i)∩φ(j) is non-empty. Let k be any element of φ(i) ∩ φ(j). By the triangle inequality and the definition of d

(1) ∞ , nΛ τ 1 ≤ τ 1 i -τ 1 j ≤ τ 1 i -τ 2 k + τ 2 k -τ 1 j ≤ 2d (1) ∞ (τ 1 , τ 2 ) < nΛ τ 1 .
Hence, the φ(i) are disjoint and we can write

D-1 i=1 C φ (i) = D-1, which clearly implies that C φ (i) = 1.
From now on, we identify φ(i) with its unique element. Let us show that φ is increasing similarily to what we have done for proving (i). Take i, j ∈ {1, . . . , D -1} such that i < j. We showed that

τ 2 φ(i) -τ 2 φ(j) ≤ 2d (1) ∞ (τ 1 , τ 2 ) -τ 1 i -τ 1 j ,
thus according to the definition of Λ τ 1 , and our assumption,

τ 2 φ(i) -τ 2 φ(j) < nΛ τ 1 -nΛ τ 1 ≤ 0.
Hence φ(i) < φ(j): φ is increasing. As a consequence, d

∞ (τ 1 , τ 2 ) = d (1) ∞ (τ 2 , τ 1 ) = d (1)
H (τ We start by proving a general formula for d F , which is stated by Lajugie, Arlot and Bach [START_REF] Lajugie | Large-margin metric learning for constrained partitioning problems[END_REF], we prove it here for completeness:

∀τ 1 , τ 2 ∈ T n , d F (τ 1 , τ 2 ) 2 = D τ 1 + D τ 2 -2 D τ 1 k=1 D τ 2 =1 λ 1 k ∩ λ 2 2 |λ 1 k | × |λ 2 | . (B.1)
Indeed, by definition, we have

d F (τ 1 , τ 2 ) 2 = Tr (Π τ 1 -Π τ 2 ) 2 = Tr(Π τ 1 ) =D τ 1 + Tr(Π τ 2 ) =D τ 2 -2 Tr(Π τ 1 Π τ 2 )
and Tr(Π

τ 1 Π τ 2 ) = n i=1 n j=1 1 {λ1(i)=λ1(j) and λ2(i)=λ2(j)} |λ 1 (i)| |λ 2 (i)| = D τ 1 k=1 D τ 2 =1 λ 1 k ∩ λ 2 2 |λ 1 k | × |λ 2 |
, where we denoted by λ k (i) the segment of τ k to which i ∈ {1, . . . , n} belongs.

B.2.2. Proof of Eq. equation (3.4) Eq. equation (3.4) is stated by Lajugie, Arlot and Bach [START_REF] Lajugie | Large-margin metric learning for constrained partitioning problems[END_REF]. The upper bound is a straightforward consequence of Eq. (B.1). We prove the lower bound here for completeness. We remark that

D τ 1 k=1 D τ 2 =1 λ 1 k ∩ λ 2 2 |λ 1 k | × |λ 2 | ≤ D τ 1 k=1 D τ 2 =1 λ 1 k ∩ λ 2 |λ 1 k | = D τ 1 ,
hence Eq. (B.1) shows that

d F (τ 1 , τ 2 ) 2 ≥ D τ 2 -D τ 1 .
The lower bound follows since τ 1 and τ 2 play symmetric roles.

B.2.3. Proof of Proposition 3.1

Throughout the proof, we write

D = D τ 1 = D τ 2 , = n -1 d (1)
∞ (τ 1 , τ 2 ) and we denote by (λ 1 k ) 1≤k≤D and (λ 2 k ) 1≤k≤D the segments of τ 1 and τ 2 , respectively.

Preliminary remark Since we assume that D τ 1 = D τ 2 and 1 n d

∞ (τ 1 , τ 2 ) = < Λ τ 1 /2, point (ii) in Lemma 3.1 shows that d (1) ∞ (τ 1 , τ 2 ) = d (1) H (τ 1 , τ 2 ) = d (1)
∞ (τ 1 , τ 2 ). In other words, for every k ∈ {1, . . . , D-1}, we have τ 1 k -τ 2 k ≤ n , and some k 0 ∈ {1, . . . , D-1} exists such that τ 1 k0 -τ 2 k0 = n . As a consequence, for every k ∈ {1, . . . , D -1},

λ 1 k -λ 2 k ≤ 2n and λ 1 k ∩ λ 2 k ≥ λ 1 k -2n . (B.2)
Upper bound for d F (τ 1 , τ 2 ) 2 We focus on the sum appearing in the righthand side of Eq. (B.1). Using Eq. (B.2), we get:

D k=1 D =1 λ 1 k ∩ λ 2 2 |λ 1 k | × |λ 2 | ≥ D k=1 λ 1 k ∩ λ 2 k 2 |λ 1 k | × |λ 2 k | ≥ D k=1 λ 1 k -2n 2 |λ 1 k | × (|λ 1 k | + 2n ) = D k=1 1 -2n |λ 1 k | 2 1 + 2n |λ 1 k | ≥ D k=1 1 - 6n |λ 1 k | ≥ D - 6 D Λ τ 1 ,
since for any x ≥ 0, (1-x) 2 1+x ≥ 1 -3x. The upper bound follows, using Eq. (B.1).

Lower bound for d F (τ 1 , τ 2 ) 2 As shown in the preliminary remark, there exists some k 0 ∈ {1, . . . , D -1} such that τ 1 k0 -τ 2 k0 = n . First consider the case where τ 1 k0 < τ 2 k0 . Then, by definition of d F and Π τ , we have:

d F (τ 1 , τ 2 ) 2 := 1≤i,j≤n (Π τ 1 -Π τ 2 ) 2 i,j ≥ i∈λ 1 k 0 +1 ∩λ 2 k 0 j∈λ 1 k 0 +1 ∩λ 2 k 0 +1 1 λ 1 k0+1 2 + i∈λ 1 k 0 +1 ∩λ 2 k 0 +1 j∈λ 1 k 0 +1 ∩λ 2 k 0 1 λ 1 k0+1 2 = 2 λ 1 k0+1 ∩ λ 2 k0 • λ 1 k0+1 ∩ λ 2 k0+1 λ 1 k0+1 2 .
Now, remark that λ 1 k0+1 ∩ λ 2 k0 = n , by the preliminary remark and our assumption τ 2 k0 > τ 1 k0 . Using also Eq. (B.2), we get:

d F (τ 1 , τ 2 ) 2 ≥ 2n λ 1 k0+1 -2n λ 1 k0+1 2 ≥ 2n 3Λ τ 1 , since λ 1 k0+1 -2n ≥ λ 1 k0+1 /3 and λ 1 k0+1 ≤ Λ τ 1 . When τ 1 k0 > τ 2 k0
, we apply the same reasoning, restricting the sum over i, j in the definition of d F to i ∈ λ 1 k0 ∩ λ 2 k0 and j ∈ λ 1 k0 ∩ λ 2 k0+1 (plus its symmetric). We obtain the same lower bound, which concludes the proof.

B.3. Lower bounds on the approximation error

This section provides the proofs of Lemmas 6.2 and 6.3.

B.3.1. Preliminary lemma

We start with a lemma useful in the two proofs.

Lemma B.1. If a segment λ ⊂ {1, . . . , n} intersects only two segments of τ , λ i and λ i+1 , then we have:

j∈λ µ j -µ λ 2 H = |λ ∩ λ i | • λ ∩ λ i+1 |λ ∩ λ i | + λ ∩ λ i+1 µ λ i+1 -µ λ i 2 H (B.3) ≥ |λ ∩ λ i | |λ i | ∧ λ ∩ λ i+1 λ i+1 • |λ i | • λ i+1 |λ i | + λ i+1 • µ λ i+1 -µ λ i 2 H . (B.4)
Proof. We first prove Eq. (B.3). Since λ only intersects λ i and λ i+1 , we have:

j∈λ µ j -µ λ 2 H = j∈λ∩λ i µ j -µ λ 2 H + j∈λ∩λ i+1 µ j -µ λ 2 H = |λ ∩ λ i | • µ λ i -µ λ 2 H + λ ∩ λ i+1 • µ λ i+1 -µ λ 2 H . (B.5)
Since µ λ is given by Eq. (A.1), we obtain

µ λ i -µ λ 2 H = 1 |λ| j∈λ µ λ i -µ j 2 H = 1 |λ| j∈λ∩λ i+1 µ λ i -µ λ i+1 2 H = λ ∩ λ i+1 2 |λ| 2 µ λ i+1 -µ λ i 2 H .
The same computation on λ ∩ λ i+1 yields In fact, we prove a slightly stronger statement. We show that, for any n ≥ 2, for any D τ ∈ {2, . . . , n}, for any D ∈ {1, . . . , D τ -1} and any τ ∈ T

µ λ i+1 -µ λ 2 H = |λ ∩ λ i | 2 |λ| 2 µ λ i+1 -µ λ i 2
D n , µ -µ τ 2 ≥ min 1≤i≤D τ -1 |λ i | • λ i+1 |λ i | + λ i+1 • µ λ i+1 -µ λ i 2 H . (B.6) Then, µ -µ τ 2 ≥ Γ • ∆ 2 where Γ = n max 1≤i≤D τ -1 1 |λ i | + 1 λ i+1 -1 . Since we always have Λ τ ≥ Γ ≥ 1 2 Λ τ ,
Eq. equation (6.4) follows.

∩ λ 1 | |λ 1 | = |λ ∩ λ 2 | |λ 2 | = 1 .
Suppose now that the result is proved for all D τ ∈ {2, . . . , p} and consider a change-point problem (τ , µ ) with D τ = D τ = p + 1 and n ≥ p + 1. Let D < p + 1 and some segmentation τ ∈ T D n be fixed. Then one of these two scenarios occurs: (i) there exists λ i with 2 ≤ i ≤ D τ -1 that does not contain any change-point of τ , or (ii) λ 2 ,...,λ D τ -1 all contain a change-point of τ .

Case (i) Suppose that there exists an inner segment λ i of τ , 2 ≤ i ≤ D τ -1, that does not contain any change-point of τ (see Figure 7). Therefore, there exists k ∈ {1, . . . , D} such that λ i λ k . By definition, there are i -1 changepoints of τ to the left of λ i and k-1 change-points of τ to the left of λ i . Suppose that k < i. We define τ • as the segmentation obtained by adding τ i to τ (see Figure 7). Then µ -µ τ 2 ≥ µ -µ τ • 2 because τ • is finer than τ . Reducing τ • to a segmentation τ • of {1, 2, . . . , τ i } in k segments and τ to a segmentation τ of {1, 2, . . . , τ i } in i segments and defining µ = (µ 1 , . . . , µ τ i ) ∈ H i , we get back to a situation covered by the induction since i ≤ D τ -1 and k < i. So,

µ -µ τ • 2 ≥ inf 1≤j≤i-1 λ j • λ j+1 λ j + λ j+1 • µ λ j+1 -µ λ j 2 H ≥ inf 1≤j≤D τ -1 λ j • λ j+1 λ j + λ j+1 • µ λ j+1 -µ λ j 2 H
and we get the result since µ -µ τ

• 2 ≥ µ -µ τ • 2 .
A symmetric reasonning can be applied if k ≥ i, considering change-points to the right of λ i and using that D

-k + 1 < D τ -i + 1 since D < D τ . λ i λ k τ τ τ τ • τ • • • • • • • • • • • • • • • • • • • • • • • • • Fig 7.
Proof of Lemma 6.2, Case (i): λ i is a segment of τ that is included in a segment of τ . The segmentation τ • is obtained by joining τ i to the segmentation τ .

Case (ii) Suppose that each inner segment of τ contains a change-point of τ . Since there are D τ -2 inner segments of τ and D -1 ≤ D τ -2 change-points of τ , there is at most (hence exactly) one change-point of τ in each inner segment of τ . Then D = D τ -1 and we are in the situation depicted in Figure 8.

τ τ • • • • • • λ 1 λ 2 λ D λ D+1 λ 1 λ 2 λ D α 2 λ 2 (1 -α 2 ) λ 2 α D λ D (1 -α D ) λ D
µ -µ τ 2 ≥ (1 ∧ α 2 ) |λ 1 | • |λ 2 | |λ 1 | + |λ 2 | • µ λ 2 -µ λ 1 2 H + D-1 j=2 (1 -α j ) ∧ α j+1 • λ j • λ j+1 λ j + λ j+1 • µ λ j+1 -µ λ j 2 H + (1 -α D ) ∧ 1 |λ D | • λ D+1 |λ D | + λ D+1 • µ λ D+1 -µ λ D 2 H ≥ [1 ∧ α 2 +(1 -α 2 ) ∧ α 3 + • • • + (1 -α D-1 ) ∧ α D + (1 -α D ) ∧ 1]
× inf

∞ (τ , τ ) . If δ = 0, then Eq. equation (6.5) holds true. We assume from now on that δ > 0.

Because nΛ τ ≥ δ, for any 1 ≤ i ≤ D τ -1, we can write τ i+1 -τ i ≥ δ. On the other hand, because d ∞ (τ , τ ) ≥ δ, there exists i ∈ {1, . . . , D τ -1} such that, for any j ∈ {1, . . . , D -1}, |τ i -τ j | ≥ δ. Since δ ≤ nΛ τ , this also holds true for j = 0 and j = D. Let us define, as illustrated by Figure 9, λ • := {τ i -δ + 1, . . . , τ i , τ i + 1, . . . , τ i + δ} . Since λ • is included in a segment of τ ,

• × • × • • • • • × • • × • τ τ λ • τ i τ i+1
µ -µ τ 2 ≥ j∈λ • µ j -(µ τ ) j 2 H ≥ j∈λ • µ j -µ λ • 2 H .
Because of the hypothesis we made, λ • only intersects λ i and λ i+1 among the segments of τ , so Eq. (B.3) in Lemma B.1 shows that

j∈λ • µ j -µ λ • 2 H = |λ • ∩ λ i | • λ • ∩ λ i+1 |λ • ∩ λ i | + λ • ∩ λ i+1 µ λ i+1 -µ λ i 2 H = δ 2 µ λ i+1 -µ λ i 2 H ≥ δ 2 ∆ 2 ,
hence the result.

B.5. Proof of Lemma 6.6

In this proof, since τ is fixed, we denote by λ 1 , . . . , λ D the segments of τ , that is, λ i = {τ i-1 + 1, . . . , τ i }.

First, notice that

L τ = µ -µ τ , ε = D τ i=1 µ λ i ,
L τ = D + i=1 µ λ i , j∈λ i ε j H - D + i=1 µ λi , j∈λi ε j H = D + i=1 µ λ i -µ λi , j∈λ i ε j H + D + i=1 µ λi , j∈λ i ε j - j∈λi ε j H = D + i=1 µ λ i -µ λi ,
E [ζ] = E ε 1 + • • • + ε n 2 H = n j=1 v j .
We recognize the right-hand side of equation (6.7) up to 1/x 2 . For any r > 1, let us denote by A r the event

∀1 ≤ s < r, ε 1 + • • • + ε s H < x and ε 1 + • • • + ε r H ≥ x ,
and by A 1 the event ε 1 H ≥ x. These events are disjoints, thus we can write Finally, let ≤ r < k be integers. Since ε is independent from ε k conditionally to σ(ε 1 , . . . , ε r ), ε is independent from ε k conditionally to A r . Furthermore, ε k is independent from A r and

P max 1≤k≤n ε 1 + • • • + ε k H ≥ x = P
E ε k , ε H A r = E [ε k ] , E ε A r H = 0 .
Because of this relation and the positivity of the (real) conditional expectation, for any integers r ≤ k ≤ j,

E ζ A r = E ε 1 + • • • + ε n 2 H A r ≥ E ε 1 + • • • + ε r 2 H A r ≥ x 2 .
Therefore, E ζ A r ≥ x 2 , which gives E [ζ] ≥ x 2 P (A r ). This concludes the proof, thanks to Eq. (B.8).

Remark B.1. The independence between ε j and ε k for j = k yields E ε j , ε k H = 0. Indeed, we dispose of a conditional expectation on H [19, chapter 5], which satisfies the same properties than the conditional expectation with real random variables. Hence we can write

E ε j , ε k H = E E ε j , ε k H ε k = E E ε j ε k , ε k H = E E [ε j ] , ε k H = 0.
Note that the ε j s expectation vanishes by hypothesis.

3 Fig 4 .

 34 Fig 4. In red, the three piecewise constant functions used in the simulations of Section 4. In blue, a noisy version of these functions. Both µ 1 and µ 2 have 4 jumps; µ 3 has 9 jumps.

3 Fig 5 .

 35 Fig 5. Convergence of 1 n d

Fig 6 .

 6 Fig 6. Left: One sample X 1 , . . . , Xn for n = 10 3 . Middle: Performance of KCP with various kernels (n = 200). Methods 1 to 8: Gaussian kernel with bandwidth set via the median heuristic (method 1 ), or fixed equal to 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1 (methods 2, . . . , 9, respectively). Method 9 : linear kernel. Right: Estimated values of n -1 d

≤

  have probability greater than 1 -3 e -λDτ ,P (Ω) ≥ 1 -3 τ ∈Tn e -λDτThe inequality P (Ω) ≥ 1 -e -y follows sinceτ ∈Tn e -λDτ = n d=1 n -1 d -1 e -λd = e -λ 1 + e -λ n-1≤ e -λ exp (n -1) e -λ e -y exp(e -1 ) n e ≤ 0.27 e -y ,

Remark 6 . 4 .

 64 The proof of Theorem 3.1 generalizes to τ defined by τ ∈ arg min τ ∈Tn / Λ τ ≥δn crit(τ )

  . (B.5) and the fact that |λ| = |λ ∩ λ i |+ λ ∩ λ i+1 yield Eq. (B.3). Now, we remark that for any a, b, c, d > 0, abcd ab + cd = 1 ab max(a,c) + cd max(a,c) × min(a, c) × bd ≥ min(a, c) bd b + d . Taking a = |λ ∩ λ i | / |λ i |, b = |λ i |, c = λ ∩ λ i+1 / λ i+1 and d = λ i+1 , we get Eq. (B.4). B.3.2. Proof of Lemma 6.2

  Proof of Eq. (B.6) by induction We show by strong induction on D τ that, for any D τ ≥ 2, for any D ∈ {1, . . . , D τ -1}, any n ≥ D τ and any τ ∈ T D n , Eq. (B.6) holds true. First, if D τ = 2, the result follows by Eq. (B.4) in Lemma B.1 since we then have i = 1 and |λ

Fig 8 .

 8 Fig 8. Proof of Lemma 6.2, Case (ii): D = D τ -1 and each inner segment of τ contains exactly one change-point of τ .

1≤j≤D τ - 1 λ j • λ j+1 λ j + λ j+1 • µ λ j+1 -µ λ j 2 H.

 12 Since α i ≥ 0 for any 2 ≤ i ≤ D τ -1, it is straightforward to show thatα 2 + (1 -α 2 ) ∧ α 3 + • • • + (1 -α D ) ≥ 1 ,which concludes the proof.B.4. Proof of Lemma 6.3Let us define δ := min nΛ τ , d

Fig 9 .

 9 Fig 9. Construction of λ • in the proof of Lemma 6.3. In this case, δ = 2 since Λ τ = 2/10 (the rightmost segment of τ is of size 2) and d∞(τ , τ ) = 3 (achieved in τ i ).

  D τ < D τ we arbitrarily define λ Dτ +1 = • • • = λ D τ = ∅, so that j∈λi ε j = 0 for every i ∈ {D τ + 1, . . . , D τ }. Similarly, if D τ < D τ , we define λ D τ +1 = • • • = λ Dτ = ∅.We also define µ ∅ = µ n by convention. Then, defining D + := max D τ , D τ , we can rewrite Eq. (B.7) as follows:

≤≤ 2 H

 2 the triangle inequality and Cauchy-Schwarz inequality,|L τ | ≤ D + i=1 µ λ i -µ λi H diam conv µ j / j ∈ {1, . . . , n} × 3D + diam conv µ j / j ∈ {1, . . . , n} × sup 1≤a<b≤n b j=a ε j Hwhere we used that µ λ ∈ conv µ j / j ∈ {1, . . . , n} for any segment λ. Since the diameter of the convex hull of a finite set of points is equal to the diameter of the set, we have diam conv µ j / j ∈ {1, . . . , n} = diam µ j / j ∈ {1, . . . , n}≤ (D τ -1)∆ < D τ ∆ .Using also Lemma 6.4, we get the result. B.6. Proof of Lemma 6.10 Let us put ζ := ε 1 + • • • + ε n . Since for any j = k, E ε j , ε k H = 0 (see Remark B.1), by definition of v j ,

8 )

 8 The law of total expectation and the positiveness of ζ yieldE [ζ] ≥ n r=1 E ζ A r P (A r ) .

  1 , τ 2 ) .

	B.2. The Frobenius loss
	B.2.1. A formula for d 2 F

Acknowledgments

Damien Garreau PhD scholarship is financed by DGA / Inria. Sylvain Arlot is also member of the Select project-team of Inria Saclay. At the beginning of this work, Sylvain Arlot was financed by CNRS and member of the Sierra team in the Département d'Informatique de l' École normale supérieure (CNRS / ENS / Inria UMR 8548), 45 rue d'Ulm, 75005 Paris, France. This work was also partly done while Sylvain Arlot was supported by Institut des Hautes Études Scientifiques (IHES, Le Bois-Marie, 35, route de Chartres, 91440 Bures-Sur-Yvette, France). The authors thank Alain Celisse and Aymeric Dieuleveut for helpful discussions.

Proof of Theorem 3.2

We follow the strategy described at the beginning of Section 6. Throughout the proof, we write τ 2 as a shortcut for τ (D τ , δ n ).

Key argument By definition (3.6)

By Lemma 6.5, Lemma 6.6 and the facts that D τ2 = D τ and Λ τ2 ≥ δ n , we get

By Lemma 6.10, under Assumption 2, P (Ω 2 ) ≥ 1 -y -2 .

Conclusion By definition of Ω 2 , Eq. (6.11) implies that on Ω 2 :

Since we assume v 2 (y, δ n ) < Λ τ , the result follows.

Appendix A: Additional notation

In this appendix are collected a large part of the technical details of the proofs that precede. Some additional notation used solely in the appendix are introduced below. We denote by λ 1 , . . . , λ D τ the segments of τ , that is,

For any segment λ of τ ∈ T n , we denote by µ λ the value of µ τ on λ, which does not depend on τ and is given by equation (2.5):

Appendix B: Proofs

∞ (τ 1 , τ 2 ). Take any i ∈ 1, . . . , D 1 -1 , by the definition of Λ τ 1 ,

which is greater than d

∞ (τ 1 , τ 2 ) by assumption. In the same fashion we can prove that

∞ (τ 1 , τ 2 ). Hence, for any i ∈ {1, . . . , D 1 -1},

which proves that d

(2)

∞ (τ 1 , τ 2 ). Next, we prove that D 1 = D 2 and d

for all i ∈ {1, . . . , D 1 -1}. This mapping is well-defined: indeed, suppose that j, k ∈ 1, . . . , D 2 -1 both realize the minimum for some i ∈ 1, . . . , D 1 -1 .

Since we assumed 1 n d

By the triangle inequality,

hence j = k. Next, we show that φ is increasing. Take i, j ∈ 1, . . . , D 1 -1 such that i < j. Recall that τ k • is increasing (k = 1, 2). Then

Hence φ(i) < φ(j), so φ is increasing. As a consequence, φ is injective and we get D 1 ≤ D 2 . The same argument, exchanging τ 1 and τ 2 , shows that D 2 ≤ D 1 . Therefore, D 1 = D 2 and φ is an increasing permutation of 1, . . . , D 1 -1 , hence it is the identity. As a consequence, d

∞ (τ 1 , τ 2 ). Finally, since d


J Gouin

T Augé

L Bailly

P D'hugues

J R Disnar

D Keravis

Organic and mineral characteristics of Kupferschiefer ore from Lubin mine (Poland): implications for bioleaching of the ore

Keywords: mineralization, organic matter, black shale deposit, copper concentrate

The ore mineral and organic matter content of the Lubin black shale (LBS) are compared with copper concentrate (LC) obtained by flotation. Study of a mineralized profile shows a good correlation between the S, TOC and Cu, Co and Ag content, suggesting syngenetic bacterial sulfate reduction (BSR) accumulation. The presence of disseminated and fracture filling rather than framboidal Cu-minerals, suggests formation via diagenetic processes. Compared to the black shale, the LC shows a lower HI and a higher OI, and a much more diverse ore mineral content. The black shale ore is composed of 15 vol. % sulfide, this proportion reaches 27 % in the LC whereas the TOC is similar in the LC and LBS. The ore mineral diversity in the LC is due to the contribution of mineralized sandstone and dolomite adjacent the black shale ore.

INTRODUCTION AND GEOLOGICAL SETTING

The Lubin mine belongs to the Kupferschiefer organic and copper-rich black shale deposit, which covers about 54.5% of Poland (Piestrzyński and Sawlowicz 1999). This deposit is located in southwestern part of Poland (Fig. 1). It is the largest copper deposit in Europe and one the largest in the world as regard to the copper reserves.

In the framework of the European BioShale project (http://bioshale.brgm.fr), aiming at evaluating biotechnology for beneficiation of black shale ore, we had the opportunity to study the Lubin black shale and various samples in order to characterize the product before and after the bioleaching treatment.

The Lubin ore deposit is of the stratabound polymetallic type, with a size of about 550km². The Kupferschiefer mineralization occurs between the uppermost Lower Permian Rotliegendes terrestrial redbeds and the Upper Permian Zechstein marine sequence (Oszczepalski 1999), in the southwestern part of Poland, within the North Sudetic basin and the Foresudetic Monocline. These polymetallic orebearing sediments are developed in two distinct facies, a reduced one which consists of an organic-rich black shale containing base metal sulfides and an oxidized one (Rote Fäule) which consists of red-coloured organicdeficient shale containing most of the precious metals [START_REF] Oszczepalski | Origin of the Kupferschiefer polymetallic mineralization in Poland[END_REF]Piestrzyński et al. 2002). Results are presented for a 110cm thick profile through the reduced zone in the Lubin mine (LUP2-1 lowermost sample: boundary dolo-mite, LUP2-2 to 9: black shales, LUP2-10 to 12 uppermost sample: dolomites), analyzed to study sulfide distribution and relationships between metal enrichments and organic matter. An "average black shale sample" (LBS) and the Lubin copper concentrate (LC) were also analyzed to compare the black shale ore and the industrial metal-enriched material for copper recovery. The Lubin copper concentrate (LC) is the final industrial product of the Lubin mine, obtained by flotation processes of a composite run of mine constituted by the three main formations of the Kupferschiefer: dolomite, black shale and sandstone.

MINERALIZATION

The most mineralized part of the orebody is the Kupferschiefer laminated black shale, with an average copper content of 7.1% (Piestrzyński and Sawlowicz 1999) on an average thickness of about 80cm. It shows a high organic content (TOC of 7-8% in average), clay minerals (illite), calcite/dolomite, detrital quartz and feldspars, and base metal sulfides. The organic matter is mainly represented by amorphous material of bituminite type, with vitrinite in various proportion and inertinite particles [START_REF] Koch | Organic petrographic investigations of the Kupferschiefer in northern Germany[END_REF]. The main ore minerals are chalcocite, digenite, covellite, bornite, chalcopyrite, pyrite, tennantite, galena, sphalerite and silver minerals (Piestrzyński et al. 2002).

METHODS

Rock-Eval Pyrolysis assay performed with a "Turbo" model RE6 pyrolyzer. Sulfide minerals were analyzed using a Camebax SX50 electron probe microanalyzer (EPMA) in routine conditions. For LBS and LC samples, sulfides minerals were concentrated by bromoform densimetric separation. The heavy fraction was compacted with a hydraulic press to obtain a disk which was then polished and analyzed by counting point technique with EPMA with a step of 200µm in same conditions as described above in order to accurately determine the proportion of each mineral. Chemical analysis of the bulk samples was carried out by atomic absorption spectrophotometry and induced coupled plasma spectrophotometry. Loss of ignition was measured by heating the samples at 1000°C for 1h.

LUBIN PROFILE

Organic matter characterization

Two different types of organic matter (OM) can be distinguished in the profile of the reduced zone between black shale and dolomite samples. The black shale horizon is rich in OM, the TOC ranges from 5.27% to 13.7% (Fig. 2). This OM is typically of marine origin (type II kerogen) with high values of hydrogen index (HI up to 361 mg HC/g TOC) and low values of oxygen index (OI below 10 mg CO 2 /g TOC) (Fig. 2). To the contrary, in all dolomite samples, the OM seems to be of terrigenous origin (type III kerogen). The TOC and HI are much lower (up to 1.11% and 93 mg HC/g TOC) and OI much higher (above 10 mg CO 2 /g TOC). This is probably due to the low TOC contents with an artificial contamination of OI by carbonate material [START_REF] Katz | Limitations of « Rock-Eval » pyrolysis for typing organic matter[END_REF].

Figure 2. Hydrogen Index vs. Oxygen Index for recognition of genetic type of organic matter. Genetic paths after [START_REF] Espitalie | La pyrolyse Rock-Eval et ses applications[END_REF].

Metal distribution

The boundary dolomite (LUP2-1) and the upper dolomite (LUP2-10 to 12) are poor in organic matter, and show very low metal contents: less than 1 wt.% Cu, less than 2 wt.% S, and less than 100-200 ppm As, Co, Ni, Ag. Organic-rich black shales (LUP2-2 to 9) exhibit, to the contrary higher contents of S (up to 7.5 wt.%), Cu (up to 14.4 wt.%) and hundreds of ppm As, Co, Ni, Ag.

The highest TOC, and metal content is observed in sample 2, except for S, and, there is a global tendency of decrease in metal contents toward the top of the profile (Fig. 3). Some en-richments in As, Co, Ni are observed in the middle of the profile corresponding to a higher content in cobaltite-gersdorffite group minerals. The top of the profile is marked by an enrichment in S, Cu, Ag.

The metal patterns are globally in agreement with the S and TOC content, indicating that these metals were accumulated by bacterial sulfate-reduction during shale ore formation [START_REF] Sun | Metal accumulation during and after deposition of the Kupferschiefer from the Sangerhausen Basin[END_REF]. This process would however result in the formation of framboidal texture for the Cu-minerals as described by [START_REF] Sawlowicz | Primary copper sulphides from Kupferschiefer, Poland[END_REF]. With the exception of framboidal pyrite occurrences in black shale (mostly in algal filaments), the mineralization occurs as fine-grained disseminations and as fracture fillings indicating a base metal enrichment of diagenetic origin [START_REF] Sun | Metal accumulation during and after deposition of the Kupferschiefer from the Sangerhausen Basin[END_REF].

COMPARISON OF LBS VS. LC

Geochemistry

LBS has a TOC value of 6.89%, lower than the mean value for the black shale ore of the profile (TOC = 7.98%), whereas TOC for LC is in the range with 7.63%. The OM, which composes LBS and LC is of marine origin as supported by the HI (254 and 237 mg HC/g TOC respectively) and OI (47 and mg CO 2 /g TOC) (Fig. 2). Compared to the black shale of the profile, the two samples (LBS and LC) exhibit lower HI and higher OI (Fig. 2). LBS sample was probably collected in a more oxidized zone.

Table 1 shows that the Lubin black shale has a similar composition to the average black shale of the profile. Compared to black shale ore, LC is enriched in total S and base metals, and depleted in V. The highest metal content in LC, (As -Pb -Zn being more than 10-times higher in the concentrate than in black shale ore), point to a probable input of metals from sandstones and/or dolomites, and the V depletion seems to be due to an effect of dilution (by the contribution of dolomite and sandstone in the concentrate) or a stronger affinity with gangue minerals.

Sulfide quantification

As mentioned previously, LC is enriched in metal compared to black shale ore. This is confirmed by the fraction of heavy minerals (mainly sulfides) extracted from each sample. LBS is composed of 15% of sulfides and 85% of gangue minerals (OM, quartz, clay minerals, carbonates), whereas LC contains 27% of sulfides and 73% of gangue minerals. The differences observed in the chemical composition are reflected by the mineral composition. The sulfide fraction of LBS is mainly composed of 3 main minerals (Fig. 4): chalcocite/digenite (>90%) -the distinction between the two was not possible with the technique used -and bornite (9%), with traces of Co-Ni-sulfarsenides (0.6%).

On the contrary, the sulfide fraction of LC is composed of about 11 minerals (Fig. 4). The 4 most abundant minerals are chalcocite/digenite (24.4%), bornite (24.5%) and chalcopyrite (20.6%), representing roughly 70% of the sulfide fraction. Three other minerals representing more than 20% of the sulfide fraction are pyrite (8.3%), tennantite (8.3%), covellite (5.8%). Less common include galena (2.7%), sphalerite (3.3%), Co-Nisulfarsenides (1.2%). Rare Ag-and Pb-bearing minerals represent less than 1% of the sulfide fraction, and are poorly characterized.

The LBS is composed of 85% gangue minerals, 13.6% chalcocite/digenite, 1.4% bornite and 0.1% Co-Ni-sulfarsenide. The LC is more complex. It contains 73% gangue minerals, 6.6% chalcocite/digenite and bornite, 5.6% chalcopyrite, 2.2% pyrite and tennantite, 1.6% covellite, and less than 1% of other minor minerals (Table 2).

CONCLUSIONS

The black shale from the reduced zone of Lubin mine is rich in OM (marine origin) and base metals. The element enrichment (Cu, S, Co, Ni, Ag, V) is correlated with the presence of OM. Some metals such as Pb, Zn, As are however preferentially concentrated in sandstone and/or dolomite.

The bl ack shales and Cu-concentrate from Lubin have similar organic material, but are different with regard to their metal contents and mineralization.

Some Cu-bearing sulfides, such as chalcopyrite, are known to degrade poorly during industrial bioleaching processes. It is thus important to quantify the sulfide, content and composition, in the black shale ore and Cu-concentrate to evaluate bioleaching efficiency for metal recovery.

Figure

  Figure 1. Geological……….

Figure 1 .

 1 Figure 1. Geological map of Southwestern Poland, location of the Lubin deposit.

Figure 3 .

 3 Figure 3. TOC and major elements distribution in LUP2.

Figure 4 .

 4 Figure 4. Relative proportion of each mineral phase in the heavy fraction in A) LBS and B) LC.

Table 1 .

 1 Geochemical data of average LUP2 black shales, LBS and LC.

		Avg. LUP2-BS	LBS	LC
	TOC (%)	7.98	6.89	7.63
	S tot. (%)	3.9	2.56	12.5
	Ag (ppm)	372.3	340	910
	As (ppm)	522.6	206	4930
	Co (ppm)	334.5	234	1384
	Cu (%)	7.73	8.6	17.1
	Ni (ppm)	292.6	304	534
	Pb (ppm)	121.1	112	4.74 %
	V (ppm)	1084.3	1530	854
	Zn (ppm)	117.6	10	8330

Table 2 .

 2 Mineral composition and relative proportions in LBS and LC.

		LBS	LC
	Chalcocite/Digenite (%)	13.6	6.6
	Covellite (%)		1.6
	Bornite (%)	1.4	6.6
	Chalcopyrite (%)		5.6
	Pyrite (%)		2.2
	Galena (%)		0.7
	Sphalerite (%)		0.9
	Tennantite (%)		2.2
	Co-Ni-sulfarsenide (%)	0.1	0.3
	Ag-mineral (%)		0.2
	Pb-mineral (%)		0.1
	Gangue (%)	85	73

ACKNOWLEDGEMENTS

This work was financially supported by the European Commission in the frame of Bioshale European project (6th Framework program -NMP2- CT-2004-505710), in collaboration with CUPRUM (Poland).