# Étude du compromis précision statistique-temps de calcul

Maxime Brunin, École Ed, Régionale Spi, Soutenue Le 16 Janvier

► To cite this version:

Maxime Brunin, École Ed, Régionale Spi, Soutenue Le 16 Janvier. Étude du compromis précision statistique-temps de calcul. Statistiques [stat]. Université de Lille 1 - Sciences et Technologies, 2018. Français. NNT: . tel-01657546

HAL Id: tel-01657546

https://inria.hal.science/tel-01657546

Submitted on 29 Apr 2022

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

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

École doctorale ED Régionale SPI 72

Unité de recherche Laboratoire Paul Painlevé

Thèse présentée par Maxime BRUNIN

Soutenue le 16 janvier 2018

En vue de l'obtention du grade de docteur de l'Université de Lille

Discipline **Mathématiques et leurs interactions**

Spécialité **Statistique**

Titre de la thèse

# Étude du compromis précision
statistique-temps de calcul

Thèse dirigée par

<table><tr><td>Christophe BIERNACKI</td><td>directeur</td></tr><tr><td>Alain CELISSE</td><td>co-directeur</td></tr></table>

Composition du jury

<table><tr><td rowspan="2">Rapporteurs</td><td>Cécile DUROT</td><td>professeur à l'Université Paris Nan-terre</td></tr><tr><td>Jérôme SARACCO</td><td>professeur à l'Institut Polytechnique de Bordeaux</td></tr><tr><td rowspan="2">Examinateurs</td><td>Bertrand MICHEL</td><td>professeur à l'École Centrale Nantes</td></tr><tr><td>Guillem RIGAILL</td><td>MCF à l'Université d'Evry Val d'Es-sonne</td></tr><tr><td rowspan="2">Directeurs de thèse</td><td>Christophe BIERNACKI</td><td>professeur à l'Université de Lille, Sciences et Technologies</td></tr><tr><td>Alain CELISSE</td><td>MCF à l'Université de Lille, Sciences et Technologies</td></tr></table>
**Mots clés :** algorithme itératif, règle d'arrêt, détection de ruptures, régression linéaire, estimateur sous contrainte de temps

**Keywords:** iterative algorithm, stopping rule, change-point detection, linear regression, estimate under time constraint
Cette thèse a été préparée au

Laboratoire Paul Painlevé

CNRS U.M.R. 8524
59655 Villeneuve d'Ascq Cedex
France

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

(+33) 03 20 43 48 50

Site https://math.univ-lille1.fr/

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

Laboratoire
Paul Painlevé
# ÉTUDE DU COMPROMIS PRÉCISION STATISTIQUE-TEMPS DE CALCUL

## Résumé

Dans le contexte actuel, il est nécessaire de concevoir des algorithmes capables de traiter des données volumineuses en un minimum de temps de calcul. Par exemple, la programmation dynamique appliquée au problème de détection de ruptures ne permet pas de traiter rapidement des données ayant une taille d'échantillon supérieure à $10^6$ pour des modèles complexes. Les algorithmes itératifs fournissent une famille ordonnée d'estimateurs indexée par le nombre d'itérations. Dans cette thèse, nous avons étudié statistiquement cette famille d'estimateurs afin de sélectionner un estimateur ayant de bonnes performances statistiques et peu coûteux en temps de calcul. Pour cela, nous avons suivi l'approche utilisant les règles d'arrêt pour proposer un tel estimateur dans le cadre du problème de détection de ruptures dans la distribution et le problème de régression linéaire. Il est d'usage de faire un grand nombre d'itérations pour calculer un estimateur usuel. Une règle d'arrêt est l'itération à laquelle nous stoppons l'algorithme afin de limiter le phénomène de surapprentissage dont souffre ces estimateurs usuels. En stoppant l'algorithme plus tôt, les règles d'arrêt permettent aussi d'économiser du temps de calcul. Lorsque le budget de temps est limité, il se peut que nous n'ayons pas le temps d'itérer jusqu'à la règle d'arrêt. Dans ce contexte, nous avons étudié le choix optimal du nombre d'itérations et de la taille d'échantillon pour atteindre une précision statistique optimale. Des simulations ont mis en évidence un compromis entre le nombre d'itérations et la taille d'échantillon pour atteindre une précision statistique optimale à budget de temps limité.

**Mots clés:** algorithme itératif, règle d'arrêt, détection de ruptures, régression linéaire, estimateur sous contrainte de temps

## Abstract

In the current context, we need to develop algorithms which are able to treat voluminous data with a short computation time. For instance, the dynamic programming applied to the change-point detection problem in the distribution can not treat quickly data with a sample size greater than $10^6$ for complex models. The iterative algorithms provide an ordered family of estimators indexed by the number of iterations. In this thesis, we have studied statistically this family of estimators in oder to select one of them with good statistics performance and a low computation cost. To this end, we have followed the approach using the stopping rules to suggest an estimator within the framework of the change-point detection problem in the distribution and the linear regression problem. We use to do a lot of iterations to compute an usual estimator. A stopping rule is the iteration to which we stop the algorithm in oder to limit overfitting whose some usual estimators suffer from. By stopping the algorithm earlier, the stopping rules enable also to save computation time. Under time constraint, we may have no time to iterate until the stopping rule. In this context, we have studied the optimal choice of the number of iterations and the sample size to reach an optimal accuracy. Simulations highlight the trade-off between the number of iterations and the sample size in order to reach an optimal accuracy under time constraint.

**Keywords:** iterative algorithm, stopping rule, change-point detection, linear regression, estimate under time constraint
Remerciements

Je remercie tout d'abord Christophe BIERNACKI et Alain CELISSE d'avoir accepté de me suivre pendant ces trois années de thèse. Grâce à eux, j'ai pu poursuivre mon objectif : travailler dans un laboratoire en statistique.

Je remercie également Cécile DUROT et Jérôme SARACCO d'avoir accepté de rapporter cette
thèse. Je remercie Guillem RIGAILL et Bertrand MICHEL pour avoir bien voulu compléter le
jury de thèse en tant qu'examineurs.

Je remercie également les membres de l'équipe MƏDAL qui m'ont accompagné pendant ces trois années de thèse et notamment Alain CELISSE d'avoir continué le cours de statistique de Master 2 de mathématiques bien que j'étais son seul élève et de m'avoir proposé ce sujet de thèse.

Merci à Maxime BAELDE d'avoir pu échanger scientifiquement de manière conviviale. Un grand merci à Quentin GRIMONPREZ d'avoir été disponible pour répondre à mes nombreuses questions de statistique et d'informatique. Avec Quentin, nous avons eu l'occasion de faire quelques tours à vélo ainsi que des randonnées. Avec d'autres membres de l'équipe MƏDAL, Samuel, Bhargav, nous avons été voir des matchs au stade Bollaert et notamment le fameux classico de l'année dernière Lens-Sochaux riche en rebondissement au désespoir de Samuel.

Comment ne pas remercier Bernard BOLZANO et Karl WEIERSTRASS d'avoir démontré le théorème qui porte leurs noms. J'ai découvert ce théorème il y a bien des années, en Maths Sup au lycée Faidherbe de Lille, et je n'ai pas compris à ce moment là, la puissance de ce théorème. C'est l'année suivante, en décortiquant les liens entre les théorèmes et propriétés, que j'ai compris l'importance de ce théorème pour introduire les compacts en Analyse fonctionnelle. Ce théorème a servi aussi à démontrer la complétude de (ℝ,|·|) et a ouvert ainsi le champ immense de l'étude des espaces de Banach. Ces deux grands mathématiciens sont pour moi des héros anonymes, méconnus, oubliés dans l'indifférence générale. C'est pourquoi je leur rend hommage.

Je remercie ma famille pour son soutien et en particulier, mon oncle Henri BRUNIN, profes-
seur agrégé de mathématiques, d'avoir été mon enseignant au lycée et de m'avoir aidé pendant le
Master 1 de mathématiques.
x

Remerciements
# Sommaire

<table><tr><td>Résumé</td><td>vii</td></tr><tr><td>Remerciements</td><td>ix</td></tr><tr><td>Sommaire</td><td>xi</td></tr><tr><td>Introduction</td><td>1</td></tr><tr><td>1 État de l'art</td><td>5</td></tr><tr><td>1.1 Algorithmes d'optimisation itératifs</td><td>5</td></tr><tr><td>1.2 Détection de ruptures dans la distribution</td><td>6</td></tr><tr><td>1.2.1 Rappels sur les espaces à noyau</td><td>6</td></tr><tr><td>1.2.2 Problème de détection de ruptures dans la distribution</td><td>10</td></tr><tr><td>1.2.3 Modèles</td><td>12</td></tr><tr><td>1.2.4 Algorithmes pour le problème de détection de ruptures</td><td>13</td></tr><tr><td>1.2.5 Règles d'arrêt pour le problème de détection de ruptures</td><td>19</td></tr><tr><td>1.3 Régression linéaire</td><td>22</td></tr><tr><td>1.3.1 Modèle linéaire</td><td>22</td></tr><tr><td>1.3.2 Algorithmes pour le problème de régression linéaire</td><td>22</td></tr><tr><td>1.3.3 Règles d'arrêt pour le problème de régression linéaire</td><td>25</td></tr><tr><td>1.4 Conclusion</td><td>29</td></tr><tr><td>2 Règle d'arrêt et segmentation binaire à noyau</td><td>31</td></tr><tr><td>2.1 Segmentation binaire</td><td>31</td></tr><tr><td>2.1.1 Segmentation binaire dans la moyenne d'un signal réel</td><td>32</td></tr><tr><td>2.1.2 Ruptures dans la distribution et segmentation binaire</td><td>33</td></tr><tr><td>2.2 Consistance de l'estimateur</td><td>36</td></tr><tr><td>2.2.1 Hypothèses</td><td>36</td></tr><tr><td>2.2.2 Résultat principal</td><td>37</td></tr><tr><td>2.3 Résultats numériques</td><td>38</td></tr><tr><td>2.3.1 Objectifs</td><td>38</td></tr><tr><td>2.3.2 Cadre de simulations</td><td>38</td></tr><tr><td>2.3.3 Interprétation</td><td>39</td></tr><tr><td>2.4 Conclusion</td><td>40</td></tr><tr><td>2.5 Preuves</td><td>40</td></tr><tr><td>2.5.1 Schéma de la preuve du théorème 2.2.1</td><td>41</td></tr><tr><td>2.5.2 Résultats principaux</td><td>44</td></tr><tr><td>2.5.3 Résultats secondaires</td><td>59</td></tr></table>
3 Règle d'arrêt et descente de gradient dans le modèle linéaire 69

3.1 Règle d'arrêt comme compromis biais-variance 70

3.1.1 Estimateurs obtenus par l'algorithme de descente de gradient 70

3.1.2 Intérêt de la règle d'arrêt 71

3.1.3 Interprétation 72

3.1.4 Contrôle du biais et de la variance 73

3.1.5 Règle d'arrêt proposée 75

3.1.6 Évolution de la règle d'arrêt 76

3.2 Résultats numériques 77

3.2.1 Objectifs 77

3.2.2 Cadre de simulations 78

3.2.3 Interprétation 78

3.3 Conclusion 80

3.4 Preuves 80

3.4.1 Formules closes de $\hat{\Theta}^{(t)}$ et $\hat{Y}^{(t)}$ 80

3.4.2 Preuve de la propriété 3.1.1 85

3.4.3 Preuve de la propriété 3.1.2 86

3.4.4 Preuve du lemme 3.1.1 87

3.4.5 Preuve du lemme 3.1.2 90

3.4.6 Preuve de la propriété 3.1.3 94

4 Estimateur à budget de temps limité 103

4.1 Compromis entre temps et taille de l'échantillon 103

4.1.1 État de l'art pour les estimateurs à budget de temps limité 103

4.1.2 Critère de qualité de l'estimateur 104

4.1.3 Optimisation du critère en temps et taille de l'échantillon 104

4.2 Simulations 105

4.2.1 Objectifs 105

4.2.2 Cadre de simulations 105

4.2.3 Interprétation 105

4.3 Conclusion 108

4.4 Preuves 109

4.4.1 Formule close du critère $Q(\hat{\Theta}_n^{(t)})$ 109

4.4.2 Asymptotique de $\log_{10}(Q(\hat{\Theta}_n^{(t)}))$ en t 110

Conclusion 113

Bibliographie 117

Table des matières 121
# Introduction

Grâce à la capacité de calcul grandissante des ordinateurs, les données sont de plus en plus volumineuses. Par exemple, en biologie, dans l'étude des variations du nombre de copies d'ADN le long du génome, la taille des échantillons est typiquement de $n = 10^5-10^6$ (BLEAKLEY et VERT 2011). Dans ce contexte, il est nécessaire de concevoir des algorithmes itératifs capables de traiter des données volumineuses en un minimum de temps de calcul. Pour l'exemple cité ci-dessus, la programmation dynamique appliquée au problème de détection de ruptures dans la distribution permet de traiter des échantillons de taille $n = 10^5$ car elle a une complexité en temps quadratique en $n$ (CELISSE et al. 2016). Ce problème soulève la question de mieux comprendre le lien entre précision statistique et temps de calcul des estimateurs issus de ces algorithmes. En statistique, les algorithmes itératifs sont souvent appliqués au risque empirique, critère qui possède des propriétés asymptotiques. Ces algorithmes itératifs fournissent ainsi une famille ordonnée d'estimateurs qui sont des bons candidats parmi l'ensemble des estimateurs possibles. Dans cette thèse, on étudie statistiquement ces estimateurs afin d'obtenir un estimateur ayant à la fois de bonnes performances statistiques et peu coûteux en temps de calcul. Pour étudier le lien entre précision statistique et temps de calcul, la problématique est de savoir :

1. Quel temps de calcul est-il nécessaire pour obtenir une précision prescrite à distance finie (i.e. lorsque la taille des échantillons $n$ est finie)? Il s'agit de sélectionner un estimateur parmi cette famille d'estimateurs ayant une précision statistique prescrite si nous disposons d'un budget de temps illimité. Nous proposons un tel estimateur dans les chapitres 2 et 3 dans le problème de détection de ruptures dans la distribution et le problème de régression linéaire respectivement. Il est à noter que l'on réalise de la sélection de modèle dans le cadre du problème de détection de ruptures dans la distribution car la vraie segmentation est un ensemble discret tandis que, pour le problème de régression linéaire, on estime un paramètre continu.

2. Quelle taille d'échantillon $n$ garantit une précision prescrite à budget de temps fixé? Il s'agit de déterminer la taille d'échantillon $n$ à utiliser pour obtenir le meilleur estimateur parmi une famille d'estimateurs à budget de temps fixé. Nous n'avons pas abordé cette question dans cette thèse. Nous avons choisi de nous concentrer sur la troisième question où nous cherchons, en plus du choix de $n$, à déterminer le nombre d'itérations $t$ de l'algorithme afin de contrôler à la fois la complexité en mémoire (quantifiée par $n$) et la complexité en temps (quantifiée par $t$ et $n$).

3. Quel est le choix du couple $(t, n)$ garantissant une précision optimale à budget de temps fixé? Le but est de fournir des recommandations à l'utilisateur pour obtenir le meilleur estimateur d'une quantité d'intérêt $\theta^*$ à budget temps fixé. Il est donc notamment utile de connaître le nombre d'itérations $t'$ et la longueur des échantillons $n'$ optimaux garantissant une précision statistique optimale à budget de temps fixé. Nous avons abordé cette question dans le chapitre 4 dans le cas simple du problème de régression linéaire.
Concernant la première question, il est d'usage de faire un grand nombre d'itérations d'un algo-
rithme itératif pour obtenir un estimateur ayant de bonnes propriétés statistiques. Néanmoins,
si on réalise un trop grand nombre d'itérations, on engendre un coût en temps de calcul plus
important. De plus, cela détériore parfois la précision statistique à cause du phénomène de
surapprentissage. Par exemple, ce phénomène est illustré dans le cas de la régression (RASKUTTI,
WAINWRIGHT et YU 2014; BLANCHARD, HOFFMANN et REISS 2016). Il est donc utile de stopper plus
tôt l'algorithme pour réduire le temps de calcul et améliorer la précision statistique de l'esti-
mateur obtenu. Ceci peut être fait grâce à des règles d'arrêts. En plus de limiter le phénomène
de surapprentissage, les règles d'arrêts permettent de contrôler le biais de l'estimateur car elles
traduisent un compromis biais-variance. En effet, les règles d'arrêt ont souvent pour but de
stopper des algorithmes minimisant le risque empirique : si on stoppe trop tôt l'algorithme, le
biais de l'estimateur est élevé, si on stoppe trop tard l'algorithme, la variance de l'estimateur
est trop grande. La figure 1 illustre la remarque précédente pour un algorithme de descente de
gradient à pas fixe α appliqué aux moindres carrés dans le cadre du problème de régression
linéaire. Cet algorithme de descente de gradient fournit une famille d'estimateur {$\hat{\theta}^{(t)}$}$_{t \in \mathbb{N}}$ de la
quantité d'intérêt $\theta^*$ définie par

$$
Y = X\Theta^* + \epsilon,
$$

où $Y \in \mathbb{R}^n$ est la variable à expliquer, $X \in \mathcal{M}_{n,d}(\mathbb{R})$ a pour $i^e$ ligne les réalisations des $d$ variables ex-
plicatives associées au $i^e$ individu, $\epsilon \in \mathbb{R}^n$ est un terme d'erreur. La figure 1 représente l'évolution
de l'erreur de prédiction en fonction du nombre d'itérations $t$. On observe que l'estimateur le plus
proche de $Y^* = X\Theta^*$ ne se situe ni lorsque le nombre d'itérations $t$ est grand ni lorsque $t$ est petit.
Cette observation a suggéré d'utiliser les règles d'arrêt pour estimer $t^* = \underset{t \in \mathbb{N}}{\operatorname{argmin}} \frac{1}{n} \|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$
($\hat{Y}^{(t)} = X\Theta^{(t)}$; $\|\cdot\|_{2,n}^2$ est la norme Euclidienne sur $\mathbb{R}^n$). De plus, la propriété 3.1.3 montre que, avec
grande probabilité, pour $n$ suffisamment grand, $t^*$ est de l'ordre de $\log(n)$ car $t^*$ est encadré par
deux fonctions équivalentes à $\log(n)$ à une constante près lorsque $n$ tend vers $+\infty$. Ainsi, la règle
d'arrêt qui estime $t^*$ aura tendance à être de l'ordre de $\log(n)$. Donc lorsque $n$ augmente, le temps
de calcul de l'estimateur obtenu par la règle d'arrêt augmentera lentement.

D'autres méthodes statistiques telles que la régularisation (e.g. la régression ridge) permettent
de limiter le phénomène de surapprentissage. RASKUTTI, WAINWRIGHT et YU 2014 ont illustré un
lien entre le paramètre de régularisation $\lambda$ et l'itération $t$ de l'algorithme de descente de gradient
présenté ci-dessus. De plus, ils ont montré que le choix du paramètre de régularisation $\lambda$ peut se
faire au moyen d'une règle d'arrêt et que ce choix possède des propriétés caractéristiques des
règles d'arrêt (cf. proposition 5 RASKUTTI, WAINWRIGHT et YU 2014).

Le plan du manuscrit est le suivant :

Le chapitre 1 est consacré à l'état de l'art sur les algorithmes d'optimisation itératifs et des règles d'arrêts associées. Leurs performances statistiques et leurs complexités en temps sont détaillées en vue de les comparer aux algorithmes étudiés pendant cette thèse.

Le chapitre 2 et le chapitre 3 présentent les algorithmes d'optimisation itératifs associés à
des règles d'arrêt étudiées pendant cette thèse. Le chapitre 2 traite d'une méthode basée sur
la segmentation binaire à noyau avec règle d'arrêt dans le cadre du problème de détection de
ruptures dans la distribution. Le chapitre 3 expose une méthode basée sur un algorithme de
descente de gradient dans le cadre du problème de régression linéaire.

Le chapitre 4 présente, sur des résultats numériques, l'évolution de *t' et *n' en fonction
du budget de temps pour un algorithme de descente de gradient dans le cas du problème de
régression linéaire.
<figure><img src="image_3.png" /><figcaption>FIGURE 1 – Erreur de prédiction $\frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$ en fonction de l'itération $t$ pour $n = 30, d = 20$. $\|\cdot\|_{2,n}$ est la norme Euclidienne sur $\mathbb{R}^n$; $\hat{Y}^{(t)} = X\hat{\theta}^{(t)}$ et $Y^* = X\theta^*$; $t^* = \arg\min_{t \in \mathbb{N}}\{\frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2\}$; $\alpha = 0.01$.</figcaption></figure>

Finalement, on termine par un chapitre de conclusion ouvrant les perspectives au travail effectué pendant cette thèse.
# Chapitre 1

## État de l'art

Dans ce chapitre, nous présentons des algorithmes itératifs utilisant des règles d'arrêts dans le cadre des problèmes étudiés dans cette thèse : le problème de détection de ruptures dans la distribution et le problème de régression linéaire. Ces problèmes se distinguent notamment du point de vue de l'estimation de la quantité d'intérêt qui est discrète pour le problème de détection de ruptures (liste de vrais instants de ruptures) et continue dans le cadre de la régression. Puis, nous détaillons les performances statistiques et en temps de calcul des estimateurs issus de ces algorithmes.

### 1.1 Algorithmes d'optimisation itératifs

Dans cette partie, nous présentons dans un premier temps les notations utilisées pour désigner la quantité d'intérêt $\theta^*$ que l'on cherche à estimer, l'estimateur pour une taille d'échantillon $n$ noté $\hat{\theta}_n^{A(t)} = \hat{\theta}_n^{(t)} = \hat{\theta}^{(t)}$ obtenu grâce à l'algorithme A à l'itération $t$ (si il n'y a pas d'ambiguïté concernant la dépendance de l'estimateur en $n$ et en l'algorithme A) et l'estimateur du risque empirique $\hat{\theta}_n$.

Nous cherchons à estimer une quantité d'intérêt notée $\theta^*$ définie comme le point de minimum global d'une fonction $C(\theta)$ sur un ensemble $\Theta$ :

$$ \theta^* = \arg \min_{\theta \in \Theta} C(\theta). $$

Par exemple, dans le cadre du modèle linéaire (1.9), $\Theta = \mathbb{R}^d$, la fonction à optimiser $C(\theta)$ est la perte définie par $C(\theta) = E_{\epsilon}[(y - x^T\theta)^2]$ (on intègre par rapport à la loi de probabilité de $\epsilon$) où $x \in \mathbb{R}^d$, $y = x^T\theta^* + \epsilon$ avec $\epsilon \in \mathbb{R}$ est un terme d'erreur centré et de variance $\sigma^2$.

Pour estimer $\theta^*$, nous cherchons à optimiser le risque empirique $C_n$ plutôt que $C$ car la fonction $C$ dépend souvent de lois de probabilités qui sont inconnues. Nous définissons l'estimateur du risque empirique $\hat{\theta}_n$ comme le point de minimum global du risque empirique $C_n(\theta)$ sur l'ensemble $\Theta$ :

$$ \hat{\theta}_n = \arg \min_{\theta \in \Theta} C_n(\theta). $$
Deux cas peuvent se produire. Dans le premier cas, le point de minimum global de $C_n$ a une formule explicite. Par exemple, pour le modèle linéaire (1.9), pour le risque empirique $C_n(\theta) = \frac{1}{n} \sum_{i=1}^n (Y_i - \bar{X}_i^T \theta)^2$, l'estimateur $\hat{\theta}_n$ a une formule explicite si $rg(X) = d$. Dans le deuxième cas, nous ne disposons pas de formules explicites de $\hat{\theta}_n$ et nous utilisons un algorithme itératif pour l'approcher. Nous définissons une famille d'estimateurs $\{\hat{\theta}^{(t)}\}_{t \in \mathbb{N}}$ où $\hat{\theta}^{(t)}$ est l'estimateur obtenu par l'algorithme itératif à l'itération $t$ appliqué au risque empirique $C_n(\theta)$. Il s'agit ensuite de choisir l'itération à laquelle stopper l'algorithme itératif : ce choix peut être fait au moyen de règles d'arrêt. Une règle d'arrêt correspond à l'itération à laquelle il faut stopper un algorithme itératif. Les règles d'arrêts peuvent dépendre uniquement des données ou de constantes à calibrer. Nous verrons, au chapitre 2, que la calibration de ces constantes influence la performance statistique de l'estimateur obtenu.

# 1.2 Détection de ruptures dans la distribution

## 1.2.1 Rappels sur les espaces à noyau

Dans cette partie, nous faisons quelques rappels de résultats sur espaces à noyau reproduisant. Ces résultats sont utilisés dans les chapitres 1 et 2 qui abordent le problème de détection de ruptures dans la distribution en utilisant les noyaux. Ces résultats sont aussi utilisés dans le chapitre 3 dans l'approche étudiée (RASKUTTI, WAINWRIGHT et Yu 2014) pour fournir une règle d'arrêt associée à un algorithme de descente de gradient.

### Espaces à noyau reproduisant

Nous donnons la définition d'un espace à noyau reproduisant (RKHS en anglais) utilisé notamment dans le problème de détection de ruptures dans la distribution pour recoder les observations initiales.

**Definition 1.2.1 (RKHS).** Soit $\mathcal{X}$ un ensemble quelconque et $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$.

Soit $(\mathcal{H}, \langle \cdot, \cdot \rangle_{\mathcal{H}})$ un espace de Hilbert de fonctions $(\mathcal{H} \subset \mathbb{R}^{\mathcal{X}})$, $k$ est appelé un noyau reproduisant si :

(a) $\forall x \in \mathcal{X}, k_x = k(x, \cdot)$ appartient à \textcolor{red}{\textit{\textbf{H}}}.

(b) $\forall f \in \mathcal{H}, \forall x \in \mathcal{X},$

$$f(x) = \langle f, k_x \rangle_{\mathcal{H}} \text{ (propriété de reproduisance).}$$

Si un noyau reproduisant $k$ existe, alors $\mathcal{H}$ est appelé un Espace de Hilbert à Noyau Reproduisant (RKHS en anglais) de noyau reproduisant $k$ (SCHOLKOPF et Alexander J. SMOLA 2001; TSUDA et SCHÖLKOPF 2004).

Pour vérifier qu'un espace de Hilbert $\mathcal{H} \subset \mathbb{R}^{\mathcal{X}}$ est un RKHS, nous disposons de la caractérisation fournie par le théorème suivant.

**Théorème 1.2.1.** L'espace de Hilbert $\mathcal{H} \subset \mathbb{R}^{\mathcal{X}}$ est un RKHS de noyau reproduisant $k$ si et seulement si $\forall x \in \mathcal{X},$

$$F_x: \begin{array}{rcl} \mathcal{H} & \rightarrow & \mathbb{R} \\ f & \mapsto & f(x) \end{array}$$

est continue sur $\mathcal{H}$.
**Démonstration.** Si $\mathcal{H}$ est un RKHS de noyau reproduisant $k$, alors, d'après la propriété de reproduisance, $\forall f \in \mathcal{H}, \forall x \in \mathcal{X}$,

$$ 
\begin{aligned}
|F_x(f)| &= |f(x)| \\
&= |\langle f, k_x \rangle_{\mathcal{H}}| \\
&\le \|f\|_{\mathcal{H}} \|k_x\|_{\mathcal{H}} \quad (\text{d'après l'inégalité de Cauchy-Schwarz}) \\
&\le \|f\|_{\mathcal{H}} \sqrt{k(x, x)}.
\end{aligned}
$$

Donc, $\forall x \in \mathcal{X}, F_x$ est continue sur $\mathcal{H}$.

Si $\forall x \in \mathcal{X}, F_x$ est continue sur $\mathcal{H}$. Comme $(\mathcal{H}, \langle \cdot, \cdot \rangle_{\mathcal{H}})$ est un espace de Hilbert et $F_x$ est une forme linéaire continue sur $\mathcal{H}$ donc d'après le théorème de Représentation de Riesz, $\exists! g_x \in \mathcal{H}, \forall f \in \mathcal{H}, F_x(f) = \langle f, g_x \rangle_{\mathcal{H}}$. Ainsi la fonction $k$ définie par $\forall x, y \in \mathcal{X}, k(x, y) = g_x(y)$ est un noyau reproduisant. Donc $\mathcal{H}$ est un RKHS de noyau reproduisant $k$.

□

### Existence de RKHS

Après avoir défini les RKHS, nous présentons le théorème de Moore - Aronszajn (ARONSZAJN 1950) utilisé dans la pratique pour montrer l'existence d'un RKHS $\mathcal{H}$ de noyau $k$ à la condition que $k$ est un noyau semi - défini positif.

**Definition 1.2.2** (noyau symétrique et semi - défini positif). *Soit $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$. $k$ est un noyau symétrique et semi - défini positif si*

(a) $\forall x, y \in \mathcal{X}, k(x, y) = k(y, x)$.

(b) $\forall (a_1, \dots, a_n) \in \mathbb{R}^n, \forall (x_1, \dots, x_n) \in \mathcal{X}^n,$

$$ \sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j k(x_i, x_j) \ge 0. $$

**Exemple 1.2.1.** Les noyaux suivants sont symétriques et semi - définis positifs :

— $\mathcal{X} = \mathbb{R}^d$. Le noyau linéaire $k_d^{\text{lin}}$ est défini par $\forall x, y \in \mathbb{R}^d, k_d^{\text{lin}}(x, y) = \langle x, y \rangle_{\mathbb{R}^d}$.

— $\mathcal{X} = \mathbb{R}^d$. Le noyau polynomial d'ordre $p \ge 1$ $k_{d,p}^{\text{poly}}$ est défini par $\forall x, y \in \mathbb{R}^d, k_{d,p}^{\text{poly}}(x, y) = (1 + \langle x, y \rangle_{\mathbb{R}^d})^p$.

— $\mathcal{X} = \mathbb{R}^d$. Le noyau gaussien $k_{h,d}^{\text{G}}$ de paramètre $h > 0$ est défini par $\forall x, y \in \mathbb{R}^d, k_h^{\text{G}}(x, y) = \exp(-\|x - y\|_{2,d}^2/(2h^2))$ avec $\forall x \in \mathbb{R}^d, \|x\|_{2,d}^2 = \sum_{i=1}^d x_i^2$.

— $\mathcal{X} = \mathbb{R}^d$. Le noyau de Laplace $k_{h,d}^{\text{L}}$ de paramètre $h > 0$ est défini par $\forall x, y \in \mathbb{R}^d, k_h^{\text{L}}(x, y) = \exp(-\|x - y\|_{2,d}^2/(2h^2))$.

Nous rappelons le théorème de Moore - Aronszajn et nous donnons des éléments de la preuve de ce théorème.

**Théorème 1.2.2** (Théorème de Moore - Aronszajn). Si $k$ est noyau symétrique et défini positif alors il existe un unique RKHS $\mathcal{H}$ de noyau reproduisant $k$.

**Démonstration.** La preuve se décompose en plusieurs étapes. Il s'agit de démontrer que $\mathcal{H}_0 = \text{vect}(|k(x, \cdot)|_{x \in \mathcal{X}})$ est un espace préhilbertien muni du produit scalaire $\langle \cdot, \cdot \rangle_{\mathcal{H}_0}$. On montre ensuite que tout suite de Cauchy de $\mathcal{H}_0$ converge simplement. Nous rappellerons la preuve des
propositions énoncées ci-dessus. On définit ensuite $\mathcal{H}$ par :

$$ \mathcal{H} = \{ f \in \mathbb{R}^{\mathcal{X}} : \exists \{f_n\}_{n \in \mathbb{N}} \text{ suite de Cauchy convergeant simplement vers } f \}. $$

Le reste de la preuve consiste à montrer que $\mathcal{H}$ est un RKHS de noyau reproduisant $k$. Des éléments de preuves des propositions énoncées ci-dessous sont disponibles dans (BERLINET et THOMAS-AGNAN 2004). Pour cela, on montre que l'on peut définir sur $\mathcal{H}$ le produit scalaire $\langle \cdot, \cdot \rangle_{\mathcal{H}}$ par, $\forall f, g \in \mathcal{H}$,

$$ \langle f, g \rangle_{\mathcal{H}} = \lim_{n \to +\infty} \langle f_n, g_n \rangle_{\mathcal{H}_0}, $$

où $\{f_n\}_{n \in \mathbb{N}} \in \mathcal{H}_0^{\mathbb{N}}$ et $\{g_n\}_{n \in \mathbb{N}} \in \mathcal{H}_0^{\mathbb{N}}$ sont les suites de Cauchy associées à $f$ et $g$. On peut ensuite montrer que $\mathcal{H}_0$ est dense dans $\mathcal{H}$ (i.e. $\overline{\mathcal{H}_0} = \mathcal{H}$). Puis, on peut montrer que $\mathcal{H}$ est complet. $(\mathcal{H}, \langle \cdot, \cdot \rangle_{\mathcal{H}})$ est donc un espace de Hilbert car $(\mathcal{H}, \langle \cdot, \cdot \rangle_{\mathcal{H}})$ est un espace préhilbertien complet. Enfin, on peut montrer que $\mathcal{H}$ vérifie la propriété de reproduisance et $\forall x \in \mathcal{X}, k_x = k(x, \cdot) \in \mathcal{H}$ (car $k_x \in \mathcal{H}_0 \subset \overline{\mathcal{H}_0} = \mathcal{H}$). Donc $\mathcal{H}$ est un RKHS de noyau reproduisant $k$.

On montre d'abord que $\mathcal{H}_0$ est un espace préhilbertien muni du produit scalaire, $\forall f, g \in \mathcal{H}_0$,

$$ \langle f, g \rangle_{\mathcal{H}_0} = \sum_{i=1}^{n} \sum_{j=1}^{m} a_i b_j k(x_i, y_j), $$

où $f = \sum_{i=1}^{n} a_i k_{x_i}$ et $g = \sum_{i=1}^{m} b_i k_{y_i}$.

On montre tout d'abord que $\langle \cdot, \cdot \rangle_{\mathcal{H}_0}$ est un produit scalaire. Comme $k$ est un noyau symétrique et semi-défini positif, il est clair que $\langle \cdot, \cdot \rangle_{\mathcal{H}_0}$ est une forme bilinéaire symétrique dont la forme quadratique est positive. Il reste à montrer que $\langle f, f \rangle_{\mathcal{H}_0} = 0 \Rightarrow f = 0$. Comme $\langle \cdot, \cdot \rangle_{\mathcal{H}_0}$ est une forme bilinéaire symétrique dont la forme quadratique est positive donc, d'après l'inégalité de Cauchy-Schwarz, $\forall x \in \mathcal{X}$,

$$ \begin{aligned} |f(x)| &= |\langle f, k_x \rangle_{\mathcal{H}_0}| \\ &\le \sqrt{k(x, x)} \sqrt{\langle f, f \rangle_{\mathcal{H}_0}} = 0 \\ \Rightarrow \forall x \in \mathcal{X}, f(x) = 0. \end{aligned} $$

Ainsi $\langle \cdot, \cdot \rangle_{\mathcal{H}_0}$ est un produit scalaire.

Soit $\{f_n\}_{n \in \mathbb{N}}$ une suite de Cauchy de $\mathcal{H}_0$, on montre que $\forall x \in \mathcal{X}, \{f_n(x)\}_{n \in \mathbb{N}}$ est une suite de Cauchy de $(\mathbb{R}, |\cdot|)$. En effet, d'après la propriété de reproduisance, $\forall x \in \mathcal{X}$ :

$$ \begin{aligned} |f_n(x) - f_m(x)| &= |\langle f_n - f_m, k_x \rangle_{\mathcal{H}_0}| \\ &\le \|f_n - f_m\|_{\mathcal{H}_0} \sqrt{k(x, x)}. \end{aligned} $$

Donc $\forall x \in \mathcal{X}, \{f_n(x)\}_{n \in \mathbb{N}}$ est une suite de Cauchy de $(\mathbb{R}, |\cdot|)$ qui est complet donc $\exists f \in \mathbb{R}^{\mathcal{X}}, \forall x \in \mathcal{X}, \lim_{n \to +\infty} f_n(x) = f(x)$. $\square$

## Intérêt pratique des noyaux

**Astuce du noyau** Si $\mathcal{H}$ est un RKHS de noyau reproduisant $k$ alors, d'après la propriété de reproduisance et le fait que $\forall x \in \mathcal{X}, k_x \in \mathcal{H}$, on obtient $\forall (x, y) \in \mathcal{X}^2, k(x, y) = \langle k_x, k_y \rangle_{\mathcal{H}}$.
Cette dernière est souvent appelée “kernel trick” ou “astuce du noyau”. Si nous disposons de $n$ observations $x_1, \dots, x_n \in \mathcal{X}$ alors toute procédure ne dépendant que de la connaissance des $\langle k_{x_i}, k_{x_j} \rangle_{\mathcal{H}}$ peut s’écrire avec la matrice de Gram $K$ définie par

$$K = [k(x_i, x_j)]_{(i,j) \in \llbracket 1, n \rrbracket^2}.$$

Par exemple, dans le chapitre 2, nous utilisons $\tilde{Y}_{s,e}^b \in \mathcal{H}$ pour déterminer si un instant de ruptures candidat est un instant de ruptures estimé ou non. $\tilde{Y}_{s,e}^b \in \mathcal{H}$ est définie, pour $b \in \llbracket s, e-1 \rrbracket$ ($1 \le s < e \le n$),

$$\tilde{Y}_{s,e}^b = \sqrt{\frac{(e-b)}{T(b-s+1)}} \sum_{i=s}^{b} Y_i - \sqrt{\frac{(b-s+1)}{T(e-b)}} \sum_{i=b+1}^{e} Y_i,$$

où $\forall i \in \llbracket s, e \rrbracket$, $Y_i = k_{X_i}$; $X_{1,n} = \{X_1, \dots, X_n\}$ un échantillon de variables aléatoires i.i.d. (indépendantes et identiquement distribuées); $T = e-s+1$. Ainsi, $\|\tilde{Y}_{s,e}^b\|_{\mathcal{H}}$ peut être calculé uniquement grâce à la matrice de Gram $K$.

**Noyaux caractéristiques** Nous présentons dans cette partie les noyaux caractéristiques utilisés pour déterminer si deux variables aléatoires $X$ et $X'$ ont même loi de probabilité.

**Definition 1.2.3** (élément moyen d'une variable aléatoire). Soit $(\mathcal{X}, \mathcal{B})$ un espace mesurable et $X$ une variable aléatoire définie sur $(\mathcal{X}, \mathcal{B})$. Si $E_{X \sim P}[k(X, X)] < +\infty$, alors l'élément moyen de $X$ (noté $m_X$) est défini comme l'unique élément de $\mathcal{H}$ tel que $\forall f \in \mathcal{H}, \langle m_X, f \rangle_{\mathcal{H}} = E[f(X)] = E[\langle f, k_X \rangle_{\mathcal{H}}]$ (FUKUMIZU et al. 2007).

**Definition 1.2.4** (Noyau caractéristique). Soit $(\mathcal{X}, \mathcal{B})$ un espace mesurable, $P$ l'ensemble des mesures de probabilités définies sur $(\mathcal{X}, \mathcal{B})$ et $\mathcal{H} \subset \mathbb{R}^\mathcal{X}$ un RKHS de noyau reproduisant $k$. Soit $X$ une variable aléatoire de loi de probabilité $P$. Nous notons $m_P$ pour désigner l'élément moyen de $X$. On suppose $\sup_{x \in \mathcal{X}} k(x, x) < +\infty$. $k$ est un noyau caractéristique si : $M_k : \mathcal{P} \to \mathbb{R}$ $P \mapsto m_P$ est injective (FUKUMIZU et al. 2007; GRETTON et al. 2012).

De manière équivalente $M_k$ est injective si et seulement si pour deux mesures de probabilité $P$ et $Q$, $\forall f \in \mathcal{H}$, $E_{X \sim P}[f(X)] = E_{X \sim Q}[f(X)] \Rightarrow P = Q$. L'existence de $E_{X \sim P}[f(X)]$ est garantie grâce à la propriété de reproduisance et l'hypothèse $\sup_{x \in \mathcal{X}} k(x, x) < +\infty$. En effet, $\forall f \in \mathcal{H}$,

$$ \begin{aligned} E_{X \sim P}[|f(X)|] &= E_{X \sim P}[|\langle f, k_X \rangle_{\mathcal{H}}|] \\ &\le \|f\|_{\mathcal{H}} E_{X \sim P}[\sqrt{k(X, X)}] \text{ d'après l'inégalité de Cauchy-Schwarz} \\ &\le \|f\|_{\mathcal{H}} \sqrt{\sup_{x \in \mathcal{X}} k(x, x)} < +\infty \end{aligned} $$

Ainsi les noyaux caractéristiques peuvent être utilisés pour déterminer si deux variables aléatoires $X$ et $X'$ ont même distributions. En effet, pour des noyaux caractéristiques, les éléments moyens de $X$ et $X'$ sont égaux si et seulement si $X$ et $X'$ sont identiquement distribuées. Par exemple, on peut utiliser les noyaux caractéristiques, dans le cadre du problème de détection de ruptures dans la distribution étudié au chapitre 2, pour détecter des changements dans la distribution car $P_X = P_{X'} \Leftrightarrow m_{P_X} = m_{P_{X'}}$.
Il existe des conditions suffisantes pour que le noyau $k$ soit caractéristique (FUKUMIZU et al. 2007; SRIPERUMBUDUR et al. 2010). Par exemple, les noyaux gaussien et de Laplace sur $\mathbb{R}^d$ sont des noyaux caractéristiques. SRIPERUMBUDUR et al. 2010 ont noté que ces conditions sont difficiles à vérifier car elles sont basées sur des résultats de densité difficile à démontrer. De plus, une condition pour que $k$ soit caractéristique suppose que $\mathcal{X}$ est compact : ce qui est une hypothèse restrictive.

### 1.2.2 Problème de détection de ruptures dans la distribution

Après des rappels sur les RKHS, nous présentons le problème de détection de ruptures dans la distribution. Puis, nous réalisons un état de l'art sur les algorithmes utilisés pour résoudre ce problème. Ces algorithmes sont soit basés sur la méthode de programmation dynamique (AUGER et LAWRENCE 1989) soit basés l'heuristique de segmentation binaire (SCOTT et KNOTT 1974).

#### Notations

Dans le cadre du problème de détection de ruptures dans la distribution, nous disposons d'un échantillon de variables aléatoires i.i.d. (indépendantes et identiquement distribuées) $X_{1,n} = \{X_1, ..., X_n\}$ à valeurs dans $\mathcal{X}$ ($\mathcal{X}$ est un ensemble quelconque), recueillies au cours du temps entre les instants $1, ..., n$, ayant des changements dans leurs lois de probabilité $P_{X_1}, P_{X_2}, ..., P_{X_n}$ à des instants de ruptures inconnus appelés vrais instants de ruptures notés $\{\tau_i^*\}_{i \in [0, D^*]}$ avec la convention $\tau_0^* = 0$ et $\tau_{D^*}^* = n$ (ZOU et al. 2014; BIAU, BLEAKLEY et MASON 2015; ARLOT, CELISSE et HARCHAOUI 2016). Ces vrais instants de ruptures vérifient :

$$0 = \tau_0^* < \tau_1^* < \dots < \tau_{D^*}^* = n.$$

La vraie segmentation $\tau^* = \{\tau_i^*\}_{i \in [1, D^*]}$ est la quantité que l'on cherche à estimer. La suite des distributions de $\{X_i\}_{i \in [1, n]}$ vérifie

$$P_{X_{\tau_0^*+1}} = \dots = P_{X_{\tau_1^*}} \neq P_{X_{\tau_1^*+1}} = \dots = P_{X_{\tau_2^*}} \neq \dots \neq P_{X_{\tau_{D^*-1}^*+1}} = \dots = P_{X_{\tau_{D^*}^*}},$$

où, $\forall i \in [1, n]$, $P_{X_i}$ est la loi de probabilité de la variable aléatoire $X_i$.

#### Détection de ruptures dans la moyenne d'un signal réel
Dans le cas où seule la moyenne des $\{P_{X_i}\}_{i \in [1, n]}$ change, le modèle s'écrit :

$$\forall i \in [1, n], \quad X_i = f_i + \epsilon_i, \qquad (1.1)$$

où $\{f_i\}_{i \in [1, n]}$ est la fonction de régression et $\forall i \in [1, n]$, $\epsilon_i$ est un terme d'erreur centré et de variance $\sigma^2$. La fonction de régression est supposée constante par morceaux avec des discontinuités à chaque vrai instant de ruptures $\{\tau_i^*\}_{i \in [0, D^*]}$. Ainsi, le signal $X_{1,n} = \{X_1, ..., X_n\}$ présente des changements dans la moyenne.

La figure 1.1 est un exemple de signal $X_{1,n}$ ayant des changements dans la moyenne.

#### Reformulation des ruptures dans la distribution à l'aide des noyaux
Dans le cas de changement dans la distribution, on peut utiliser les noyaux pour faire, à l'instar de la détection de ruptures dans la moyenne d'un signal réel, de la détection de ruptures dans les éléments moyens d'un RKHS $\mathcal{H}$. La figure 1.2 est un exemple de signal $X_{1,n}$ ayant des changements dans la distribution.
<figure><img src="image_4.png" /><figcaption>FIGURE 1.1 – Graphique du signal $X_{1,n} = \{X_1, \dots, X_n\}$ pour $n = 600$ ayant uniquement des changements dans la moyenne. Le terme d'erreur vérifie $\epsilon \sim N(0, I_n)$. Les vrais instants de ruptures $\tau_1^*$ et $\tau_2^*$ sont matérialisés par des lignes verticales bleues.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>FIGURE 1.2 – Graphique du signal $X_{1,n} = \{x_1, \dots, x_n\}$ pour $n = 600$ ayant des changements dans la distribution. Le signal $X_{1,n}$ a la moyenne et la variance égales sur chaque segment : le premier et le dernier segment contiennent des réalisations d'une loi Gaussienne de moyenne et de variance égales à 1 ; le deuxième segment contient des réalisations d'une loi de Poisson de paramètre 1. Les vrais instants de ruptures $\tau_1^*$ et $\tau_2^*$ sont matérialisés par des lignes verticales bleues.</figcaption></figure>

**Noyau symétrique défini positif** On recode les observations initiales $\{X_1, \dots, X_n\}$ par de nouvelles “observations” $\{Y_1, \dots, Y_n\}$. Elles sont définies par $\forall i \in [1, n]$, $Y_i = k(X_i, \cdot) \in \mathcal{H}$, où $k$ est un noyau symétrique semi-défini positif. Le théorème de Moore - Aronszajn (cf. théorème 1.2.2) assure l'existence d'un RKHS $\mathcal{H}$ de noyau reproduisant $k$ si $k$ est un noyau symétrique semi-défini positif.
**Détection de ruptures dans les éléments moyens d'un RKHS $\mathcal{H}$**
Nous donnons dans un premier temps les éléments permettant de définir le modèle de régression. Si $E[k(X_i, X_i)] < +\infty$, alors $g \in \mathcal{H} \mapsto E[\langle Y, g\rangle_{\mathcal{H}}]$ est une forme linéaire et continue sur $\mathcal{H}$ (ARLOT, CELISSE et HARCHAOUI 2016). En effet, $\forall g \in \mathcal{H}$,

$$|E[\langle Y_i, g \rangle_{\mathcal{H}}]| \le \sqrt{E[\|Y_i\|_{\mathcal{H}}^2]} \|g\|_{\mathcal{H}} = \sqrt{E[k(X_i, X_i)]} \|g\|_{\mathcal{H}},$$

d'après l'inégalité de Cauchy-Schwarz.

Comme $g \mapsto E[\langle Y, g \rangle_{\mathcal{H}}]$ est une forme linéaire continue sur l'espace de Hilbert $\mathcal{H}$, d'après le théorème de Représentation de Riesz, $\exists! \mu_i \in \mathcal{H}$, tel que, $\forall g \in \mathcal{H}$ :

$$E[\langle Y_i, g \rangle_{\mathcal{H}}] = E[g(X_i)] = \langle \mu_i, g \rangle_{\mathcal{H}}, \quad (1.2)$$

où, avec les notations de la section 1.2.1, $\mu_i = m_{P_{X_i}}$ est l'élément moyen de la mesure de probabilité $P_{X_i}$. Le résultat donné par l'équation (1.2) est valable si on fait l'hypothèse classique $\exists M \in \mathbb{R}^+$, $\forall i \in [1, n]$, $\|Y_i\|_{\mathcal{H}}^2 = k(X_i, X_i) \le M$ presque sûrement.

Avec cette dernière hypothèse, on obtient le modèle de régression :

$$\forall i \in [1, n], \quad Y_i = \mu_i + \epsilon_i, \quad (1.3)$$

en posant $\forall i \in [1, n]$, $\epsilon_i = Y_i - \mu_i$.

Pour des noyaux caractéristiques (par exemple le noyau gaussien ou le noyau de laplace), d'après l'équation (1.2), un changement entre les éléments moyens de $P_{X_i}$ et $P_{X_j}$ entraîne que les mesures de probabilités $P_{X_i}$ et $P_{X_j}$ sont différentes (FUKUMIZU et al. 2007) :

$$P_{X_i} \neq P_{X_j} \Leftrightarrow \mu_i \neq \mu_j.$$

Ainsi, pour les noyaux caractéristiques, faire de la détection de ruptures dans la distribution est équivalente à faire de la détection de ruptures dans les éléments moyens d'un RKHS $\mathcal{H}$.

### 1.2.3 Modèles

Nous avons choisi de noter $\hat{\tau}_D$ l'estimateur de $\tau^*$ obtenu par l'algorithme A pour un nombre de segments $D$. Dans cette partie, nous définissons les modèles associés à une segmentation $\tau$, l'estimateur du risque empirique et le risque empirique associés à la segmentation $\tau$ pour un signal où seule la moyenne change. Le risque empirique associé à la segmentation $\tau$ est noté $C_n(\tau)$. Ces définitions seront utilisés dans la section 1.2.4.

Nous notons $M_{1:n}$ l'ensemble des segmentations de $\{1, \dots, n\}$ et $M_{1:n}(D)$ l'ensemble des segmentations $\tau = \{\tau_d\}_{d \in [0, D]}$ de $\{1, \dots, n\}$ en $D$ segments avec la convention $\tau_0 = 0$ et $\tau_D = n$. Pour $\tau \in M_{1:n}$, nous définissons $\{S_\tau, \tau \in M_{1:n}\}$ la famille des modèles avec $S_\tau$ l'ensemble des $(u_1, \dots, u_n) \in \mathbb{R}^n$ défini par :

$$u_1 = \dots = u_{\tau_1} \neq u_{\tau_1+1} = \dots = u_{\tau_2} \neq \dots \neq u_{\tau_{D-1}+1} = \dots = u_n.$$

Pour $\tau \in M_{1:n}$, nous construisons un estimateur de $\mu = (\mu_1, \dots, \mu_n)$, noté $\hat{\mu}_\tau \in S_\tau$. $\hat{\mu}_\tau$ est le vecteur $u \in S_\tau$ qui minimise la distance dans $\mathbb{R}^n$ à $X_{1,n} = (X_1, \dots, X_n)$ : $\hat{\mu}_\tau$ est l'estimateur du risque
empirique. Formellement, $\hat{\mu}_{\tau}$ est défini par :

$$ \hat{\mu}_{\tau} = \arg \min_{u \in S_{\tau}} \|X_{1,n} - u\|_{2,n}^2 \quad (1.4) $$

Il a été montré que (ARLOT, CELISSE et HARCHAOUI 2016), comme $X_{1,n} \in \mathbb{R}^n$, $\forall i \in [0, D - 1]$, $\forall l \in [\tau_i + 1, \tau_{i+1}]$, alors

$$ (\hat{\mu}_{\tau})_l = \frac{1}{\tau_{i+1} - \tau_i} \sum_{j=\tau_i+1}^{\tau_{i+1}} X_j. $$

Nous pouvons ainsi définir le risque empirique noté $C_n(\tau)$ associé à la segmentation $\tau \in \mathcal{M}_{1:n}$ :

$$ C_n(\tau) = \frac{1}{n} \|X_{1,n} - \hat{\mu}_{\tau}\|_{2,n}^2, $$

où $\forall f \in \mathbb{R}^n$, $\|f\|_{2,n}^2 = \sum_{i=1}^n f_i^2$. En particulier, le risque empirique $C_n(\tau)$ est "segment additif", où $\forall \tau \in \mathcal{M}_{1:n}(D)$,

$$ \|X_{1,n} - \hat{\mu}_{\tau}\|_{\mathbb{R},n}^2 = \sum_{d=0}^{D-1} C_{\tau_d, \tau_{d+1}} \quad C_{\tau, \tau'} = \sum_{i=\tau+1}^{\tau'} X_i^2 - \frac{1}{\tau' - \tau} \left( \sum_{i=\tau+1}^{\tau'} X_i \right)^2, \quad (1.5) $$

$$ \text{si } 0 \le \tau < \tau' \le n. $$

### 1.2.4 Algorithmes pour le problème de détection de ruptures

#### Méthodes basées sur la programmation dynamique

Dans cette partie, nous présentons la méthode de programmation dynamique (AUGER et LAWRENCE 1989) appliquée au problème de détection de ruptures dans la moyenne d'un signal réel. En remarque, nous indiquons comment utiliser la méthode de programmation dynamique pour un signal ayant des changements dans la distribution. Puis, nous présentons deux méthodes de programmation dynamique qui utilisent la stratégie d'élagage dans le but de réduire le temps de calcul.

**programmation dynamique** Nous détaillons la méthode basée sur le principe de programmation dynamique pour un signal où seule la moyenne change (LEBARBIER 2003).

La programmation dynamique appliquée au problème de détection de ruptures dans la distribution permet de récupérer la meilleure segmentation en $D$ segments notée $\hat{\tau}_D$ qui minimise le risque empirique pour $\tau \in \mathcal{M}_{1:n}(D)$. Étant donné que le cardinal de l'ensemble $\mathcal{M}_{1:n}(D)$ est égale à $(\tau_{D-1}^{n-1})$, le calcul de $\hat{\tau}_D$ est prohibitif en temps de calcul lorsque $n$ et $D$ sont élevés. La programmation dynamique appliquée au problème de détection de ruptures permet de réduire la complexité en temps de $\{\hat{\tau}_D\}_{D \in [1, D_{\max}]}$ (CELISSE et al. 2016).

Une implémentation naïve de la méthode basée sur la programmation dynamique est donnée par l'algorithme 1. Dans cet algorithme, $L_{D,\tau}$ est défini comme le minimum du risque empirique
**Algorithme 1 programmation dynamique**

**Entrée** : donnée $(x_1, \dots, x_n) \in \mathcal{X}^n$, nombre de segments $D_{\max}$.

**Pour** $D = 2, \dots, D_{\max}$

**Pour** $\tau' = D, \dots, n$

**Faire** $L_{D,\tau'} = \min_{\tau \le \tau'} \{L_{D-1,\tau} + C_{\tau,\tau'}\}$.

**Faire** $m_{D,\tau'} = \arg\min_{\tau \le \tau'} \{L_{D-1,\tau} + C_{\tau,\tau'}\}$.

**Fin Pour**

**Fin Pour**

$\hat{\tau}_D = m_{D,n}$.

sur l'ensemble $M_{1:\tau}(D)$. $L_{D,\tau}$ est défini par $\forall D \in [1, D_{\max}]$, $\forall \tau \in [D, n]$ :

$$L_{D,\tau} = \min_{\tau \in M_{1:\tau}(D)} \left\{ \sum_{d=0}^{D-1} C_{\tau_d, \tau_{d+1}} \right\}. \qquad (1.6)$$

Pour calculer les segmentations $\{\hat{\tau}_D\}_{D \in [1, D_{\max}]}$, l'algorithme 1 utilise le principe d'optimalité de Bellman : toute solution optimale s'appuie elle-même sur des sous-problèmes résolus localement de façon optimale (BELLMAN 1954). En effet, le minimum et le point de minimum global du risque empirique sur $M_{1,\tau'}(D)$ (i.e. $L_{D,\tau'}$ et $m_{D,\tau'}$ respectivement) peuvent être calculés à partir des minimums et des points de minimum globaux du risque empirique sur $M_{1,\tau}(D-1)$ (i.e. $L_{D-1,\tau}$ et $m_{D-1,\tau}$ respectivement). Dans l'algorithme 1, $\tau$ désigne le dernier instants de ruptures candidats d'une segmentation appartenant à $M_{1,\tau'}(D)$. Ainsi, on peut calculer la meilleure segmentation en $D$ segments à partir des calculs réalisés pour déterminer la meilleure segmentation en $D-1$ segments. Il est à noter que les instants de ruptures estimés de $\hat{\tau}_{D-1}$ sont remis en cause lorsque l'on calcule $\hat{\tau}_D$.

L'algorithme 1 permet de récupérer les meilleurs segmentations $\{\hat{\tau}_D\}_{D \in [1, D_{\max}]}$ en $D$ segments avec une complexité en temps de $O(D_{\max}n^2)$ si les $\{C_{\tau,\tau'}\}$ pour $1 \le \tau < \tau' \le n$ ont déjà été calculés.

**Remarque 1.2.1** (détection de ruptures dans la distribution). Les résultats énoncés dans cette partie concernant la détection de ruptures dans la moyenne pour un signal réel sont valables dans le cas de la détection de ruptures dans la distribution à condition que l'on remplace :

1. $X_{1,n} = \{X_1, \dots, X_n\}$ par $Y_{1,n} = \{Y_1, \dots, Y_n\}$ où $\forall i \in [1, n]$, $Y_i = k_{X_i} \in \mathcal{H}$ et $\mathcal{H}$ est un RKHS de noyau reproduisant $k$.

2. La norme euclidienne sur $\mathbb{R}^n \|\cdot\|_{2,n}$ par la norme dans le RKHS $\mathcal{H}^n$ définie par $\forall f \in \mathcal{H}^n$, $\|f\|_{\mathcal{H},n}^2 = \sum_{i=1}^n \|f_i\|_{\mathcal{H}}^2$.

3. Pour $0 \le \tau < \tau' \le n$, $C_{\tau,\tau'} = \sum_{i=\tau+1}^{\tau'} X_i^2 - \frac{1}{\tau'-\tau} \left(\sum_{i=\tau+1}^{\tau'} X_i\right)^2$ par $C_{\tau,\tau'} = \sum_{i=\tau+1}^{\tau'} k(x_i, x_i) - \frac{1}{\tau'-\tau} \sum_{i=\tau+1}^{\tau'} \sum_{j=\tau+1}^{\tau'} k(x_i, x_j)$.

Il est à noter que la première étape de la méthode kernel-change point (KCP) utilise la programmation dynamique dans ce cadre (ARLOT, CELISSE et HARCHAOUI 2016).

**Méthode pDPA** Nous présentons la méthode *pruned dynamic programming algorithm* (pDPA) développée par (RIGAILL 2010). Dans la détection de ruptures dans la moyenne d'un signal réel,
la méthode pDPA permet de récupérer les meilleures segmentations notées $\hat{\tau}_D$ en $D$ segments pour $1 \le D \le D_{max}$ minimisant le risque empirique :

$$ \hat{\tau}_D = \arg \min_{\tau \in \mathcal{M}_{1:n}(D)} \|X_{1,n} - \hat{\mu}_{\tau}\|_{2,n}^2 $$

pDPA permet donc de récupérer les mêmes segmentations que la méthode basée sur la programmation dynamique. L'apport principal de pDPA est de réduire le temps de calcul des segmentations $\hat{\tau}_D$ grâce à une stratégie d'élagage détaillée ci-dessous. Nous introduisons des notations avant d'expliquer cette stratégie d'élagage.

pDPA est une méthode s'appuyant sur un risque empirique fonctionnel $C_n(\tau, \mu)$ associé à la segmentation $\tau \in \mathcal{M}_{1:n}(D)$. Le risque empirique fonctionnel dépend du paramètre $\mu \in \mathbb{R}$ et est défini par :

$$ C_n(\tau, \mu) = \sum_{d=0}^{D-2} C_{\tau_d, \tau_{d+1}} + \tilde{C}_{\tau_{D-1}, \tau_D}(\mu), $$

où pour $1 \le \tau < \tau' \le n$, $C_{\tau, \tau'}$ est défini par l'équation (1.5) et $\tilde{C}_{\tau, \tau'}(\mu)$ est défini, quant à lui, par :
$$ \tilde{C}_{\tau, \tau'}(\mu) = \sum_{i=\tau+1}^{\tau'} (X_i - \mu)^2 \text{si } \tau' > \tau \text{ et } 0 \text{ sinon. La fonction de perte } \gamma \text{ utilisée dans ce cas est la fonction de perte quadratique définie par } \forall Y, \mu \in \mathbb{R}, \gamma(Y, \mu) = (Y - \mu)^2. $$

Le paramètre $\mu \in \mathbb{R}$ correspond au dernier palier potentiel de la fonction de régression $\{f_i\}_{i \in [1,n]}$. En particulier, le risque empirique $C_n(\tau)$ est égal à $C_n(\tau, \hat{\mu})$ pour $\hat{\mu} = \min_{\mu \in \mathbb{R}} \tilde{C}_{\tau_{D-1}, \tau_D}(\mu)$.

Pour $\tau \in \mathcal{M}_{1:t}(D)$, nous définissons aussi $L_{D,t}(\tau, \mu)$ le risque empirique fonctionnel optimal si le dernier instant de ruptures est $\tau$

$$ L_{D,t}(\tau, \mu) = L_{D-1,\tau}(\mu) + \tilde{C}_{\tau,t}(\mu) $$

La méthode pDPA repose sur l'élimination des derniers instants de ruptures $\tau$ de segmentations candidates afin de réduire le temps de calcul par rapport à la méthode basée sur la programmation dynamique. Pour une valeur de $\mu$ tel que le minimum de $C_n(\tau, \mu)$ pour des segmentations $\tau \in \mathcal{M}_{1:t}(D)$ (e.g. les segmentations $\tau^1$ et $\tau^2$) soit égal à $L_{D,t}(\tau, \mu)$ (où $\tau$ est le dernier instant de ruptures estimé de $\tau$), si les deux derniers instants de ruptures $\tau^1$ et $\tau^2$ des segmentations $\tau^1$ et $\tau^2$ vérifient à l'instant $t$ :

$$ \begin{cases} L_{D-1,\tau^1} + \tilde{C}_{\tau^1,t}(\mu) \le L_{D-1,\tau^2} + \tilde{C}_{\tau^2,t}(\mu) \\ L_{D-1,\tau^1} + \tilde{C}_{\tau^1,t'}(\mu) \le L_{D-1,\tau^2} + \tilde{C}_{\tau^2,t'}(\mu) \end{cases} $$

alors, pour cette valeur de $\mu$ donnée, si le risque empirique fonctionnel optimal d'une segmentation en $D$ segments avec pour dernier instant de ruptures $\tau^1 < t$ est plus petit que celui de $\tau^2 < t$, alors il en sera de même pour n'importe quel instant $t' > t$. Alors la segmentation $\tau^2$ est éliminée car elle ne peut pas correspondre à une segmentation minimisant le risque empirique $C_n(\tau)$ pour $\tau \in \mathcal{M}_{1:n}(D)$.

**Méthode PELT** Nous présentons la méthode *pruned exact linear time* (PELT) développée par (KILLICK, FEARNEHEAD et ECKLEY 2012).
La méthode PELT est une méthode cherchant à déterminer $\hat{\tau}_D$ défini comme le point de maximum global d'un critère pénalisé pour $\tau \in \mathcal{M}_{1:n}$ :

$$ \sum_{d=0}^{D_{\tau}-1} C_{\tau_d, \tau_{d+1}} + \lambda D_{\tau}, \qquad (1.7) $$

où, pour $\tau' > \tau$, $C_{\tau,\tau'}$ est une fonction de coût associé au segment $[\tau + 1, \tau']$. Par exemple, dans le cas de la détection de ruptures dans la moyenne d'un signal réel, pour $0 \le \tau < \tau' \le n$, $C_{\tau,\tau'}$ est défini par l'équation (1.5). $\lambda > 0$ est le paramètre de régularisation. $D_{\tau}$ est le nombre de segments de la segmentation $\tau$.

Ce critère pénalisé réalise un compromis entre l'ajustement au modèle traduit par le terme $\sum_{d=0}^{D_{\tau}-1} C_{\tau_d, \tau_{d+1}}$ et la complexité du modèle traduit par $\lambda D_{\tau}$ : plus $D_{\tau}$ est grand, plus $\sum_{d=0}^{D_{\tau}-1} C_{\tau_d, \tau_{d+1}}$ est petit devant $\lambda D_{\tau}$. Si l'on choisit un paramètre de régularisation $\lambda > 0$ élevé, $\hat{\tau}_D$ aura un faible nombre de segments. A l'inverse, si on choisit un paramètre de régularisation $\lambda$ petit, $\hat{\tau}_D$ aura un grand nombre de segments.

Comme la méthode pDPA, la méthode PELT repose sur l'élimination des segmentations candidates qui ne sont pas des points de minimum global de (1.7). De manière analogue à la méthode de programmation dynamique (cf. algorithme 1), PELT cherche à minimiser (1.7) pour $\tau \in \mathcal{M}_{1:u}$ ($u \in [2, n]$) :

$$ \begin{aligned} F(u) &= \min_{\tau \in \mathcal{M}_{1:u}} \left\{ \sum_{d=0}^{D_{\tau}-1} \left[ C_{\tau_d, \tau_{d+1}} + \lambda \right] \right\} \\ &= \min_{0 \le t < u} \left\{ \min_{\tau \in \mathcal{M}_{1:t}} \left\{ \sum_{d=0}^{D_{\tau}-2} \left[ C_{\tau_d, \tau_{d+1}} + \lambda \right] \right\} + C_{t,u} + \lambda \right\} \\ &= \min_{0 \le t < u} \{ F(t) + C_{t,u} + \lambda \}, \end{aligned} $$

où $F(0) = -\lambda$.

A la condition qu'il existe une constante $K \in \mathbb{R}$ telle que pour tous $0 \le t < s < u \le n$, $C_{t,s} + C_{s,u} + K \le C_{t,u}$, le théorème 3.1 (KILLICK, FEARNHEAD et ECKLEY 2012) montre que la segmentation $\tau \in \mathcal{M}_{1:u}$ ayant pour dernier instant de ruptures candidat $t$ n'est pas un point de minimum global de (1.7) si couple $(t,s)$ vérifie la condition $F(t) + C_{t,s} + K \ge F(s)$.

En effet, si $\begin{cases} F(t) + C_{t,s} + K \ge F(s) \\ C_{t,s} + C_{s,u} + K \le C_{t,u} \end{cases}$ $\Rightarrow F(s) + C_{s,u} + \lambda \le F(t) + C_{t,u} + \lambda$. Ainsi, on gardera la segmentation $\tau \in \mathcal{M}_{1:u}$ ayant son dernier instant de ruptures candidat en $s$.

Dans le cas de la détection de ruptures dans la moyenne d'un signal réel, la condition $C_{t,s} + C_{s,u} + K \le C_{t,u}$ est vérifiée avec $K = 0$.

PELT ne permet pas de récupérer facilement $\{\hat{\tau}_D\}_{D \in [1, D_{\max}]}$: PELT (cf algorithme (2)) renvoie directement $\hat{\tau}_D$. C'est pourquoi, nous ne présenterons pas de règles d'arrêt pour PELT.

PELT a une complexité en temps de $O(n)$ si le nombre de vrais instants de ruptures augmente linéairement avec $n$ (KILLICK, FEARNHEAD et ECKLEY 2012). Dans le pire des cas, la complexité en temps de PELT est en $O(n^2)$ donc la complexité en temps de PELT est inférieure à celle de l'algorithme 1.
## Algorithme 2 méthode PELT

**Entrée** : donnée $(x_1, ..., x_n) \in \mathbb{R}^n; R_1 = \{0\}; cp(0) = \emptyset; F(0) = -\lambda$.

**Pour** $\tau^* = 1, ..., n$

**Faire** $F(\tau^*) = \min_{\tau \in R_{\tau^*}} [F(\tau) + C_{\tau, \tau^*} + \lambda]$.

**Faire** $\tau^1 = \arg\min_{\tau \in R_{\tau^*}} [F(\tau) + C_{\tau, \tau^*} + \lambda]$.

**Faire** $cp(\tau^*) = [cp(\tau^1), \tau^1]$.

**Faire** $R_{\tau^*+1} = \{\tau \in R_{\tau^*} \cup \{\tau^*\} : F(\tau) + C_{\tau, \tau^*} + K \le F(\tau^*)\}$.

**Fin Pour**

$\hat{\tau}_{\hat{D}} = cp(n)$.

Du point de vue des performances statistiques, PELT permet de récupérer le point de minimum global du critère 1.7. Cependant, l'inconvénient de PELT est qu'il faut calibrer le paramètre de régularisation $\hat{\lambda}$ pour récupérer $\hat{\tau}_{\hat{D}}$.

## Méthode basée sur l'heuristique de segmentation binaire

Nous présentons la première étape de la procédure de classification and regression trees (CART) et la première étape de ECP qui sont basées sur l'heuristique de segmentation binaire (SCOTT et KNOTT 1974). Pour ces deux procédures, nous avons choisi de les présenter séparément, bien que seul le critère diffère, car le critère de ECP est spécifique.

**Méthode CART** GÉY et LEBARBIER 2008 ont étudié CART avec ordonnancement dans le problème de détection de ruptures dans la moyenne d'un signal réel (cf. modèle (1.1)).

CART calcule des segmentations candidates en D segments $\hat{\tau}_D$ par dichotomie. CART cherche initialement à déterminer l'instant de ruptures candidat $j_1$ défini par :

$$j_1 = \arg \min_{j \in [1, n-1]} \{C_n(\tau_j)\},$$

où $\tau_j = (0, j, n)$ et $C_n(\tau_j) = \|X_{1,n} - \hat{\mu}_{\tau_j}\|_{\mathbb{R}, n}^2$ est le risque empirique associé à la segmentation $\tau_j$. On note $\hat{\tau}_1 = j_1$ le premier instant de ruptures estimé. Puis, on définit $\hat{\tau}_2 = (0, \hat{\tau}_1, n)$.

On cherche ensuite $j_2$ et $j_3$ dont les segmentations $\tau_{j_2} = (0, j_2, \hat{\tau}_1, n)$ et $\tau_{j_3} = (0, \hat{\tau}_1, j_3, n)$ minimisent le risque empirique sur chacun des segments $[[1, \hat{\tau}_1 - 1]]$ et $[[\hat{\tau}_1 + 1, n - 1]]$. On choisit parmi les instants de ruptures candidats $j_2$ et $j_3$ celui dont la segmentation $\tau_{j_2}$ et $\tau_{j_3}$ minimise le plus le risque empirique et on le note $\hat{\tau}_2$. On définit ainsi $\hat{\tau}_3 = (0, \hat{\tau}_1, \hat{\tau}_2, n)$. Nous continuons ensuite de manière récursive cette procédure jusqu'à récupérer les segmentations candidates jusqu'à un nombre de segments $D_{max}$. Il est à noter que contrairement à l'algorithme 1 et pDPA, CART ne remet pas en cause un instant de ruptures estimé : les instants de ruptures qui sont des faux positifs pour un nombre de segments $D = D_1$ seront présents dans les segmentations estimées $\hat{\tau}_D$ pour $D \ge D_1$. La figure 1.3 illustre la méthode CART jusqu'à la dimension $D = 3$. Pour $D = 3$, on choisira l'instant de ruptures $\hat{\tau}_3$ celui qui minimise le plus le risque empirique parmi les instants de ruptures candidats.

**Méthode ECP** La méthode ECP est basée sur l'heuristique de segmentation binaire appliquée au critère energy-based distance empirique afin d'estimer les vrais instants de ruptures
<figure><img src="image_6.png" /><figcaption>FIGURE 1.3 – Illustration de la première étape de CART pour $D \in [1, 3]$.</figcaption></figure>

$\{\tau_i^*\}_{i \in [0, D^*]}$ (MATTESON et JAMES 2014). Nous détaillons comment on récupère les segmentations $\{\hat{\tau}_D\}_{D \in [1, D_{max}]}$ par la méthode ECP.

Pour $L, L', M, M'$ i.i.d. et $M, M'$ i.i.d. telles que $L, L', M, M'$ sont mutuellement indépendantes et $E[\|L\|_{2,d}^\beta + \|M\|_{2,d}^\beta] < +\infty$ (pour $\beta \in ]0, 2[$), le critère energy-based distance noté $\varepsilon(L, M; \beta)$ est défini par :

$$ \varepsilon(L, M; \beta) = 2E\left[\|L - M\|_{2,d}^{\beta}\right] - E\left[\|L - L'\|_{2,d}^{\beta}\right] - E\left[\|M - M'\|_{2,d}^{\beta}\right]. $$

$\varepsilon(L, M; \beta)$ sert à déterminer si les variables aléatoires $L$ et $M$ sont de même loi. En effet, pour deux variables aléatoires $L, M$ indépendantes à valeurs dans $\mathbb{R}^d$, le critère energy-based distance $\varepsilon(L, M; \beta)$ vaut 0 si et seulement si $L$ et $M$ sont identiquement distribuées. La loi de $L$ et de $M$ étant inconnues, ECP utilise le critère empirique associé à $\varepsilon(L, M; \beta)$ noté $\hat{\varepsilon}(L_{1,n}, M_{1,m}; \beta)$ où $L_{1,n} = \{L_1, \dots, L_n\}$ et $M_{1,m} = \{M_1, \dots, M_m\}$ sont des échantillons de variables aléatoires i.i.d. ayant pour distributions respectives celle de $L$ et $M$. Formellement, $\hat{\varepsilon}(L_{1,n}, M_{1,m}; \beta)$ est défini par :

$$ \hat{\varepsilon}(L_{1,n}, M_{1,m}; \beta) = \frac{2}{mn} \sum_{i=1}^{n} \sum_{j=1}^{m} \|L_i - M_j\|_{2,d}^{\beta} - \left(\frac{n}{2}\right)^{-1} \sum_{1 \le i < j \le n} \|L_i - L_j\|_{2,d}^{\beta} - \left(\frac{m}{2}\right)^{-1} \sum_{1 \le i < j \le m} \|M_i - M_j\|_{2,d}^{\beta}. $$

Ainsi, ECP utilise le critère $\hat{\varepsilon}(L_{1,n}, M_{1,m}; \beta)$ pour déterminer si les échantillons $L_{1,n}$ et $M_{1,m}$ sont issus de distributions différentes. En effet, sous l'hypothèse nulle $H_0: L$ et $M$ ont la même
distribution (i.e. $\varepsilon(L, M; \beta) = 0$), $\frac{mn}{m+n} \hat{\varepsilon}(L_{1,n}, M_{1,m}; \beta)$ converge vers la distribution d'une loi non dégénérée (i.e. une distribution différente d'une masse de Dirac) lorsque $\min(m, n)$ tend vers $+\infty$. Sous l' hypothèse alternative, les variables aléatoires $L$ et $M$ sont issues de distributions différentes (i.e. $\varepsilon(L, M; \beta) > 0$), $\frac{mn}{m+n} \hat{\varepsilon}(L_{1,n}, M_{1,m}; \beta)$ converge presque sûrement vers $+\infty$ lorsque $\min(m, n)$ tend vers $+\infty$.

Appliqué au problème de détection de ruptures dans la distribution, ce résultat permet de déterminer des instants de ruptures estimés. En effet, soit l'échantillon $X_1, \dots, X_n \in \mathbb{R}^d$, $L_{1,\tau} = \{X_1, \dots, X_\tau\}$ et $M_{\tau+1,\nu} = \{X_{\tau+1}, \dots, X_\nu\}$ ($1 \le \tau < \nu \le n$), on cherche à savoir si les échantillons $L_{1,\tau}$ et $M_{\tau+1,\nu}$ sont issus de distributions différentes (i.e. si $\tau$ est un instant de ruptures candidat). $\tau_0$ est un instant de ruptures candidat si le couple $(\tau_0, v_0)$ maximise $\hat{\varepsilon}(L_{1,\tau}, M_{\tau+1,\nu}; \beta)$ parmi l'ensemble des valeurs possibles de $\tau$ et $\nu$ ($1 \le \tau < \nu \le n$). Formellement, on obtient

$$ (\tau_0, v_0) = \arg \max_{1 \le \tau < v \le n} \hat{H}(L_{1,\tau}, M_{\tau+1,\nu}; \beta), $$

$$ \text{où } \hat{H}(L_{1,\tau}, M_{\tau+1,\nu}; \beta) = \frac{\tau(v-\tau)}{v} \hat{\varepsilon}(L_{1,\tau}, M_{\tau+1,\nu}; \beta). $$

ECP utilise l'heuristique de segmentation binaire pour déterminer les instants de ruptures estimés. Supposons que $D-1$ instants de ruptures aient été estimés $0 < \hat{\tau}_1 < \dots < \hat{\tau}_{D-1} < n$, sur les $D$ segments délimités par ces instants de ruptures, on détermine le couple $(\hat{\tau}(i), \hat{v}(i))$ qui maximise $\hat{H}(L_{1,\tau}, M_{\tau+1,\nu}; \beta)$ pour $\hat{\tau}_i + 1 \le \tau < v \le \hat{\tau}_{i+1}$. Puis on calcule

$$ i^* = \arg \max_{i \in [0, D-1]} \hat{H}(L_{1,\hat{\tau}(i)}, M_{\hat{\tau}(i)+1,\hat{v}(i)}; \beta). $$

On définit ainsi le $D^e$ instant de ruptures estimé $\hat{\tau}_D = \hat{\tau}(i^*)$ et $\hat{v}_D = \hat{v}(i^*)$. $\hat{q}_D$ est défini par :

$$ \hat{q}_D = \hat{H}(L_{1,\hat{\tau}_D}, M_{\hat{\tau}_D+1,\hat{v}_D}; \beta). \qquad (1.8) $$

Ainsi, on récupère $\{\hat{\tau}_D\}_{D \in [1, D_{\max}]}$ par la première étape de la méthode ECP.

### 1.2.5 Règles d'arrêt pour le problème de détection de ruptures

Dans cette partie, nous présentons les règles d'arrêt associées aux méthodes KCP, pDPA, CART et ECP. Il est à noter que l'on peut utiliser l'heuristique de pente, pour les méthodes KCP, pDPA et CART, afin de déterminer la règle d'arrêt $\hat{D}$.

**Règles d'arrêt basées sur l'heuristique de pente** La deuxième étape des méthodes KCP, pDPA et CART utilisent le formalisme de la sélection de modèles : chaque segmentation candidate (liste d'instants de ruptures candidats) est reliée à un modèle qu'il faut choisir. Ces trois méthodes ont permis de récupérer des segmentations candidates dont le nombre de segments est inférieur à $D_{\max}$ noté $\{\hat{\tau}_D\}_{D \in [1, D_{\max}]}$.

La deuxième étape de ces 3 méthodes réalise la sélection de modèle en sélectionnant le modèle $\hat{\tau}_{\hat{D}}$ parmi $\{\hat{\tau}_D\}_{D \in [1, D_{\max}]}$ où $\hat{D}$ est un estimateur du vrai nombre de segments $D^*$. Formellement, $\hat{D}$ est défini par :

$$ \hat{D} = \arg \min_{D \in [1, D_{\max}]} \{C_n(\hat{\tau}_D) + \text{pen}(\hat{\tau}_D)\}, $$
où $\forall \tau \in \mathcal{M}_{1:n}, C_n(\tau) = \|Y_{1,n} - \hat{\mu}_{\tau}\|_{H,n}^2$ pour KCP et $\forall \tau \in \mathcal{M}_{1:n}, C_n(\tau) = \|X_{1,n} - \hat{\mu}_{\tau}\|_{2,n}^2$ pour pDPA et CART.

$\hat{D}$ minimise un critère pénalisé pour $D \in [[1, D_{\text{max}}]]$. Ce critère pénalisé est un compromis entre l'ajustement au modèle $\mathcal{M}_{1:n}(D)$ traduit par $C_n(\hat{\tau}_D)$ et la complexité du modèle $\mathcal{M}_{1:n}(D)$ traduite par la pénalité pen($\hat{\tau}_D$).

Pour ces 3 méthodes, il est nécessaire de calibrer les constantes de la pénalité pen($\hat{\tau}_D$). Dans les cas que nous étudions, la pénalité pen($\hat{\tau}_D$) ne dépend que du nombre de segments $D$ de $\hat{\tau}_D$: nous noterons désormais cette pénalité pen($D$). Il existe deux approches de l'heuristique de pente pour calibrer les constantes de la pénalité que nous allons détailler ci-dessous.

La première approche est adaptée aux méthodes KCP, pDPA et CART. La pénalités de ces 3 méthodes s'écrit sous la forme suivante

$$\text{pen}_C(D) = C \times \text{pen}_{\text{shape}}(D),$$

où $\text{pen}_{\text{shape}}(D) = \frac{D}{n}(c_1 \log(\frac{n}{d}) + c_2)$ pour KCP et pDPA (on suppose dans cette première approche que $c_1 = 2$ et $c_2 = 5$) et $\text{pen}_{\text{shape}}(D) = \frac{D}{n}$. C est la constante à calibrer.

Le but de cette première approche est de calibrer la constante $C$ grâce à l'heuristique de pente (BIRGÉ et MASSART 2007; GEY et LEBARBIER 2008). La méthode consiste à calculer $\hat{D}_C$ pour différentes valeurs de $C$ appartenant à un ensemble $\mathcal{N}_C$ avec $\hat{D}_C$ défini tel que :

$$\hat{D}_C = \arg \min_{D \in [[1, D_{\text{max}}]]} \{C_n(\hat{\tau}_D) + \text{pen}_C(D)\}$$

GEY et LEBARBIER 2008 calculent $\hat{D}_C$ en augmentant lentement les valeurs de $C$ à partir de 0. On détermine $\hat{C}$ la valeur de $C$ pour laquelle $\{\hat{D}_C\}_{C \in \mathcal{N}_C}$ a le plus grand saut. La pénalité retenue est alors $\text{pen}_{2\hat{C}}(D)$.

Pour la deuxième approche, ARLOT, CELISSE et HARCHAOUI 2016 utilise une variante de l'heuristique de pente (LEBARBIER 2002) pour éviter de fixer les constantes $c_1$ et $c_2$. Cette variante de l'heuristique de pente consiste à faire la régression linéaire de $C_n(\hat{\tau}_D)$ en fonction des variables explicatives $\frac{D}{n}$ et $(\frac{n-1}{D-1})$ pour $D \in [[0.6 \times D_{\text{max}}, D_{\text{max}}]]$. Il pose ensuite $\forall i \in [[1, 2]]$, $c_i = -2\hat{s}_i$ où $\{\hat{s}_i\}_{i \in [[1, 2]]}$ sont les coefficients de régression obtenus par la régression linéaire.

Finalement, on récupère l'estimateur de la vraie segmentation $\tau^*$ noté $\hat{\tau}_D$.

Nous détaillons maintenant les performances statistiques de $\hat{\tau}_D$ pour les méthodes KCP, pDPA et CART.

**Méthode KCP** Concernant les performances en temps de calcul, l'heuristique de pente nécessite le calcul de $\hat{\tau}_D$ pour $D \in [[1, D_{\text{max}}]]$ qui est prohibitif en temps de calcul lorsque $D_{\text{max}}$ et $n$ sont élevés. En effet, une implémentation naïve de l'étape 1 (cf. algorithme 1) est coûteuse en complexité en temps et en complexité en mémoire : elles sont respectivement $O(D_{\text{max}}n^4)$ et $O(n^2)$. En effet, cet algorithme nécessite le calcul $C_{\tau, \tau'}$ pour $(\tau, \tau') \in [[0, n]]^2$. Or le calcul de $C_{\tau, \tau'}$ a une complexité en temps de $O(n^2)$ et le stockage de $(C_{\tau, \tau'})(\tau, \tau') \in [[0, n]]^2$ a une complexité en mémoire de $O(n^2)$. Ainsi les deux boucles for de l'algorithme 1 entraîne que cet algorithme a une complexité en temps de $O(D_{\text{max}}n^4)$. Il est à noter qu'une optimisation de l'algorithme 1 a une complexité en temps de $O(D_{\text{max}}n^2)$ et une complexité en mémoire de $O(D_{\text{max}}n)$ (CELISSE et al. 2016).
Concernant les performances statistiques, une inégalité oracle (ARLOT, CELISSE et HARCHAOUI 2016) garantit que le risque quadratique de $\hat{\mu}_{\tau}$ pour $\tau = \hat{\tau}_{D}$ est du même ordre de grandeur que le plus petit risque quadratique associé à $\hat{\mu}_{\tau}$ pour $\tau$ parcourant $M_{1:n}$. Cette inégalité oracle est un résultat non-asymptotique et donc garantissant des performances statistiques de KCP à distance finie (i.e. lorsque la taille de l'échantillon est finie).

**Méthode pDPA** La méthode pDPA renvoie les mêmes estimateurs que la méthode KCP donc les performances statistiques des estimateurs obtenus par pDPA sont les mêmes que celles de KCP. Nous détaillons donc les différences en matière de performances en temps de calcul. Pour des fonctions de perte avec un paramètre $\mu \in \mathbb{R}$ unidimensionnel, pDPA a une complexité en temps de $O(D_{max}n^2)$ et en mémoire de $O(D_{max}n)$ dans le pire des cas (RIGAILL 2010). Des résultats numériques montrent que, en moyenne, pDPA est moins coûteux en temps de calcul que la première étape de KCP : des segmentations candidates ne pouvant pas être des meilleures segmentations en $D$ segments sont éliminées par la stratégie d'élagage de pDPA. Pour la deuxième étape de sélection de modèle, pDPA utilise l'heuristique de pente comme KCP. Donc ces 2 méthodes ont la même complexité en temps et en mémoire pour cette étape de sélection de modèle.

pDPA a l'inconvénient de traiter uniquement le cas où $\mu$ est un paramètre unidimensionnel ($\mu \in \mathbb{R}$) qui correspond au cas de la détection de ruptures dans la moyenne d'un signal réel. pDPA ne traite pas, par exemple, le cas $\chi = \mathbb{R}^d$. De plus, pDPA peut être uniquement utilisée sous certaines hypothèses sur la fonction de perte $\gamma$ vérifiées par la fonction de perte quadratique (RIGAILL 2010).

**méthode CART** La complexité de la première étape de CART est de $O(D_{max}n)$ dans le pire des cas et de $O(\log(D_{max})n)$ dans le cas favorable. Donc, dans tous les cas, la complexité de la première étape de CART est inférieure à celle de l'algorithme 1 et à pDPA.

La première étape de CART permet de récupérer des points de minimum local du risque empirique alors que pDPA et l'algorithme 1 permettent de récupérer des points de minimum global du risque empirique. Ainsi, la première étape de CART fournit des estimateurs ayant de moins bonnes performances statistiques que pDPA et l'algorithme 1.

De plus, un autre inconvénient de CART est de ne proposer une solution que pour le problème de détection de ruptures dans la moyenne d'un signal réel.

## Règle d'arrêt pour la méthode ECP

A la suite de la première étape de ECP décrite dans la section 1.2.4, ECP utilise un test d'hypothèse pour déterminer si le nouvel instant de ruptures estimé $\hat{\tau}_D$ appartient à la segmentation $\hat{\tau}_D$ conditionnellement au fait que les instants de ruptures estimés $\hat{\tau}_1, \dots, \hat{\tau}_{D-1}$ appartiennent à la segmentation $\hat{\tau}_D$. Ce test d'hypothèses a pour hypothèse nulle $H_0$ : il n'y a pas d'autres vrais instants de ruptures dans les segments courants contre l'hypothèse alternative $H_1$ : $\hat{\tau}_D$ est un instant de ruptures estimé appartenant à la segmentation $\hat{\tau}_D$.

Un réarrangement des observations à l'intérieur de chacun des $D$ segments courants à l'aide de permutations construit une suite de longueur $n$. Pour la $r^{e}$ permutation, on calcule $\hat{q}_{D}^{(r)}$ la valeur de la statistique de test associée à $\hat{\tau}_{D}$ à l'aide d'une équation semblable à (1.8). On réalise $R$ permutations et on calcule une p-valeur égale à $|(r \in \llbracket 1, R \rrbracket : \hat{q}_{D}^{(r)} \ge \hat{q}_{D})|/(R+1)$ (pour un ensemble $A$, $|A|$ désigne le cardinal de $A$). Une valeur élevée de cette p-valeur signifie que,
pour un certain nombre de permutations, les segments délimités par ces instants de ruptures estimés contiennent des observations ayant des changements dans la distribution plus nets que $\hat{t}_D$. On fixe classiquement un risque de première espèce $p_0$ égal à 5% et si la p-valeur est plus grande que $p_0$, on ne rejette pas l'hypothèse nulle $H_0$. Cela signifie que $\hat{t}_D$ n'appartient pas à la segmentation $\hat{t}_{\hat{D}}$ et la recherche d'instants de ruptures estimés appartenant à $\hat{t}_{\hat{D}}$ s'arrête. Dans le cas contraire, on rejette l'hypothèse nulle au profit de l'hypothèse alternative et $\hat{t}_D$ appartient à $\hat{t}_{\hat{D}}$ et on réitère le processus.

Nous détaillons maintenant les performances statistiques et en temps de calcul de ECP. ECP a une complexité en temps de $O(R\hat{D}n^2)$ où $R$ est le nombre de permutations utilisés dans le test d'hypothèses (cf. section 1.2.5). La complexité en temps de ECP est donc supérieure aux méthodes KCP, pDPA, PELT lorsque $R$ est élevé (e.g. $R\hat{D} \ge D_{max}$). Sous l'hypothèse restrictive que le nombre de vrais instants de ruptures reste constant lorsque $n$ augmente, les instants de ruptures estimés sont fortement consistants (i.e. les instants de ruptures estimés convergent presque sûrement vers les vrais instants de ruptures) (MATTESON et JAMES 2014).

En comparaison aux méthodes KCP et pDPA, la méthode ECP ne peut pas faire de la détection de ruptures dans distribution pour un ensemble $\mathcal{X}$ quelconque car les observations $x_1, \dots, x_n$ appartiennent à $\mathbb{R}^d$.

## 1.3 Régression linéaire

Nous définissons le modèle linéaire et les hypothèses faites sur ce modèle. Puis, nous présentons des algorithmes qui peuvent être utilisés dans le cadre du problème de régression linéaire. Enfin, nous présentons des règles d'arrêt associées à l'algorithme de descente de gradient.

### 1.3.1 Modèle linéaire

Dans le problème de régression linéaire, on suppose une relation linéaire entre la variable à expliquer $Y$ et les variables explicatives regroupées dans la matrice d'incidence $X$ (SEBER et LEE 2012). Le but de la régression linéaire est d'estimer la fonction de régression $f^*(x) = x^T\theta^*$ ($x \in \mathbb{R}^d$). Le modèle linéaire s'écrit

$$Y = X\theta^* + \epsilon, \quad (1.9)$$

où $\theta^*$ est le paramètre à estimer; $X \in \mathcal{M}_{n,d}(\mathbb{R})$ dont la $i$-ligne est $X_i^T \in \mathbb{R}^d$, la $i$-coordonnée du vecteur $Y \in \mathbb{R}^n$ est $Y_i$, où $(X_1, Y_1), \dots, (X_n, Y_n)$ sont des variables aléatoires i.i.d. . Nous faisons les hypothèses suivantes : la matrice $X$ est supposée de rang plein ($\mathrm{rg}(X) = d$) et le terme d'erreur $\epsilon \in \mathbb{R}^n$ vérifie $\epsilon \sim \mathcal{N}(0, \sigma^2 I_n)$. Avec ces hypothèses, l'estimateur usuel est l'estimateur des moindres carrés (EMC) $\hat{\theta}_n = (X^T X)^{-1} X^T Y$.

### 1.3.2 Algorithmes pour le problème de régression linéaire

**Descente de gradient** L'algorithme de descente de gradient (steepest descent algorithm en anglais) a pour but de minimiser une fonction $f: \mathbb{R}^d \to \mathbb{R}$ qui est différentiable sur $\mathbb{R}^d$ (YUAN 1999; SNYMAN 2009). On note $\{\hat{\theta}^{(t)}\}_{t \in [1, t_{\max}]}$ la suite obtenue par l'algorithme de descente de gradient (GD). A chaque itération de l'algorithme de descente de gradient (cf. algorithme 3), le point courant est déplacé dans la direction opposée au gradient (le gradient est noté $\nabla f$) afin de
**Algorithme 3** Algorithme de descente de gradient

**Entrée** : Initialisation $\theta^{(0)}$, fonction $f$ différentiable.

**Pour** $t = 1, \dots, t_{\max}$

**Faire** Calcul de $\alpha_t$.

$$ \text{Faire } \hat{\theta}^{(t+1)} = \hat{\theta}^{(t)} - \alpha_t \nabla f(\hat{\theta}^{(t)}). $$

**Fin Pour**

**Algorithme 4** Algorithme de descente de sous-gradient

**Entrée** : Initialisation $\theta^{(0)}$, fonction $f$ convexe.

**Pour** $t = 1, \dots, t_{\max}$

**Faire** Calcul de $\alpha_t$.

$$ \text{Faire } \hat{\theta}^{(t+1)} = \hat{\theta}^{(t)} - \alpha_t g^{(t)}. $$

**Fin Pour**

faire décroître la fonction $f$. En effet, comme $f$ est différentiable sur $\mathbb{R}^d$ alors, $\forall \theta \in \mathbb{R}^d$,

$$ f(\theta + h) = f(\theta) + \langle \nabla f(\theta), h \rangle_{\mathbb{R}^d} + o(\|h\|_{2,d}) $$

Donc, pour minimiser $f$, il est naturel de rechercher $v = \operatorname*{argmin}_{h \in \mathbb{R}^d} \{\langle \nabla f(\theta), h \rangle\}$. De plus, $v = -\nabla f(\theta)$ d'après l'inégalité de Cauchy-Schwarz. On retrouve la relation entre $\hat{\theta}^{(t+1)}$ et $\hat{\theta}^{(t)}$ donnée par l'algorithme GD (cf. algorithme 3). GD nécessite le choix ou le calcul du pas $\alpha_t > 0$ à chaque itération. Celui-ci peut être choisi par l'utilisateur. $\alpha_t$ peut être aussi calculé par la méthode de la recherche linéaire (YUAN 1999; NESTEROV 2004) :

$$ \alpha_t = \arg \min_{\alpha \in \mathbb{R}_+^*} \{ f(\hat{\theta}^{(t)} - \alpha \nabla f(\hat{\theta}^{(t)})) \} $$

$\alpha_t$ est dans ce cas la valeur du pas $\alpha$ qui fera le plus décroître $f$. GD permet d'approcher un point stationnaire de la fonction $f$ (i.e. un point qui annule le gradient de $f$). Étant donné qu'un point de minimum local est un point stationnaire, GD recherche les éventuels points de minimum local. Si de plus $f$ est deux fois différentiable et GD approche un point stationnaire dont la matrice Hessienne évaluée en ce point est positive, alors ce point stationnaire est un point de minimum local de $f$. Si la fonction $f$ est convexe, on sait que les points stationnaires coïncident avec les points de minimums globaux. Ainsi, si $f$ est convexe, GD permet d'approcher les points de minimums globaux.

**descente de sous gradient** L'algorithme de descente de sous-gradient (subGD) permet de minimiser une fonction $f: \mathbb{R}^d \to \mathbb{R}$ qui est convexe non différentiable. subGD (cf. algorithme 4) utilise la notion de sous gradient au point $\theta$ défini par :

$$ f(\theta') \geq f(\theta) + \langle g, \theta' - \theta \rangle_{\mathbb{R}^d}, $$

où $g$ est un sous gradient de $f$ au point $\theta$. Le sous gradient de $f$ au point $\theta$ existe si $f$ est convexe. On remarque que, si $f$ est différentiable, le sous gradient de $f$ au point $\theta$ coïncide avec le gradient de $f$ au point $\theta$. L'avantage de subGD est qu'il peut s'appliquer à des fonctions convexes non différentiables. On peut donc appliquer subGD au critère lasso, i.e. $\theta \in \mathbb{R}^d \mapsto \|Y - X\theta\|_{2,n}^2 + \lambda \|\theta\|_{1,d}$ ($\forall \theta \in \mathbb{R}^d$, $\|\theta\|_{1,d} = \sum_{i=1}^d |\theta_i|$) pour obtenir une approximation de $\hat{\theta}^L$ défini
**Algorithmhe 5** Algorithme de descente de gradient stochastique

Entrée : Initialisation θ⁽¹⁾, fonction j différentiable par rapport à θ.

Pour t = 1,..., t<sub>max</sub>

Faire Calcul de α<sub>t</sub>.

Faire $\hat{\theta}^{(t+1)} = \hat{\theta}^{(t)} - \alpha_t \nabla_j(\hat{\theta}^{(t)})$.

Fin Pour

par

$$
\hat{\theta}^L = \arg \min_{\theta \in \mathbb{R}^d} \{ \|Y - X\theta\|_{2,n}^2 + \lambda \|\theta\|_1 \}.
$$

Nous comparons maintenant GD et subGD en matière de performance statistique. Sous l'hypothèse que $f$ est convexe, $f(\hat{\theta}^{(t)})$ converge vers le minimum de $f$ à la vitesse $1/\sqrt{t}$ pour l'algorithme subGD (GORDON et TIBSHIRANI 2012; ASPREMONT 2016). Sous l'hypothèse que $f$ est différentiable, on dispose de la même vitesse de convergence de $f(\hat{\theta}^{(t)})$ vers le minimum de $f$ pour GD. Néanmoins, si on rajoute l'hypothèse que la gradient de $f$ est Lipschitzien alors $f(\hat{\theta}^{(t)})$ converge vers le minimum de $f$ à la vitesse $1/t^2$ pour GD (ASPREMONT 2016). Ainsi, avec des hypothèses supplémentaires, GD a des vitesses de convergence plus rapides que subGD.

**Descente de gradient stochastique** L'algorithme de descente de gradient stochastique (SGD) a pour but de minimiser la fonction $C(\theta) = E[j(\theta, W)]$ pour $\theta \in \Theta = \mathbb{R}^d$ où $W$ est une variable aléatoire et $j$ est une fonction différentiable sur $\mathbb{R}^d$ (CARPENTIER 2014). On note $\{\hat{\theta}^{(t)}\}_{t \in [1, t_{\max}]}$ la suite obtenue par l'algorithme de descente de gradient stochastique : l'algorithme 5 donne la relation entre $\hat{\theta}^{(t+1)}$ et $\hat{\theta}^{(t)}$. Nous expliquons le fonctionnement de SGD dans le cas du modèle linéaire (1.9) : on pose $j(\theta, W) = (Y - X^T \theta)^2$ où $W = (X, Y)$. La fonction $C$ que l'on cherche à minimiser sur $\Theta$ est donc définie par $C(\theta) = E_W[(Y - X^T \theta)^2]$ (on intègre par rapport à la loi de $W$).

Nous comparons maintenant GD et SGD en matière de performance statistique et en
temps de calcul dans le cas de la régression linéaire. GD est appliqué à la fonction objectif
$C_n(\theta) = \frac{1}{n} \sum_{i=1}^n (Y_i - X_i^T \theta)^2$ et donc a un coût de $n$ fois le calcul du gradient de $j$ par itération.
Comparativement à GD, l'avantage de SGD est d'avoir un coût d'un gradient de $j$ par itération.
Sous des hypothèses restrictives (notamment le gradient de $j$ est uniformément borné en $\theta$ et
$w$), $\hat{\theta}^{(t)}$ obtenu par SGD converge en moyenne quadratique vers $\theta^*$ à la vitesse $\frac{1}{t}$ (CARPENTIER
2014) alors que $\hat{\theta}^{(t)}$ obtenu par GD converge en $\exp(-t)$ vers l'estimateur des moindres carrés
$\hat{\theta}_n$. Ainsi, en raison de ces hypothèses restrictives et aussi pour sa simplicité, nous avons choisi
d'étudier GD.

**Newton-Raphson** L'algorithme de Newton-Raphson (NR) a pour but de minimiser une fonction $f: \mathbb{R}^d \to \mathbb{R}$ qui est deux fois différentiable sur $\mathbb{R}^d$ (BUBECK 2014). On note $\{\hat{\theta}^{(t)}\}_{t \in [1, t_{\max}]}$ la suite obtenue par l'algorithme de Newton Raphson (NR). NR (cf. algorithme 6) nécessite que la matrice Hessienne de $f$ au point $\theta$ notée $\nabla^2 f(\theta)$ soit inversible pour tout $\theta \in \mathbb{R}^d$. La relation entre $\hat{\theta}^{(t+1)}$ et $\hat{\theta}^{(t)}$ provient du fait que NR cherche à minimiser les termes d'ordre 1 et 2 issus d'un développement de limité de $f$ au point $\theta$. En effet, comme $f$ est deux fois différentiable sur
**Algorithme 6** Algorithme Newton-Raphson

**Entrée** : Initialisation $\theta^{(0)}$, fonction $f$ deux fois différentiable.

**Pour** $t = 1, \dots, t_{\max}$

**Faire** $\hat{\theta}^{(t+1)} = \hat{\theta}^{(t)} - (\nabla^2 f(\hat{\theta}^{(t)}))^{-1} \nabla f(\hat{\theta}^{(t)})$.

**Fin Pour**

$\mathbb{R}^d$ donc, d'après la formule de Taylor Young, $\forall \theta \in \mathbb{R}^d$,

$$f(\theta + h) = f(\theta) + \langle \nabla f(\theta), h \rangle_{\mathbb{R}^d} + \frac{1}{2} h^T \nabla^2 f(\theta) h + o(\|h\|_{2,d}^2)$$

NR cherche, à partir du point courant $\theta$ à minimiser $f$. Donc NR cherche à minimiser les termes d'ordre 1 et 2 du développement ci-dessus, à savoir $h \in \mathbb{R}^d \mapsto \langle \nabla f(\theta), h \rangle_{\mathbb{R}^d} + \frac{1}{2} h^T \nabla^2 f(\theta) h$. La solution de ce problème de minimisation est $h = -(\nabla^2 f(\theta))^{-1} \nabla f(\theta)$. On retrouve la relation entre $\hat{\theta}^{(t+1)}$ et $\hat{\theta}^{(t)}$ donnée par l'algorithme NR (cf. algorithme 6).

NR permet d'approcher des points stationnaires de la fonction $f$. Donc, comme pour GD, si $f$ est convexe, NR permet d'approcher un point de minimum global de $f$.

Le fait que NR impose que la matrice Hessienne de $f$ soit inversible en tout point $\theta \in \mathbb{R}^d$ est une hypothèse restrictive. De plus, la complexité en temps du calcul de l'inverse de la matrice Hessienne de $f$ au point $\hat{\theta}^{(t)} \nabla^2 f(\hat{\theta}^{(t)})$ est de $O(d^3)$ : ce qui est coûteux en temps de calcul lorsque $d$ est grand. C'est pourquoi, nous avons choisi d'étudier GD plutôt que NR car GD ne requiert pas l'hypothèse d'inversibilité de la matrice $\nabla^2 f(\hat{\theta}^{(t)})$ et a une complexité en temps inférieure à celle de NR.

### 1.3.3 Règles d'arrêt pour le problème de régression linéaire

Dans cette partie, nous présentons 3 règles d'arrêt associées à un algorithme étudié dans cette thèse, i.e l'algorithme de descente de gradient.

**Première règle d'arrêt** En régression, RASKUTTI, WAINWRIGHT et Yu 2014 ont utilisé une règle d'arrêt associée à un algorithme de descente de gradient. Cet algorithme de descente de gradient est appliqué au risque empirique défini sur un RKHS $\mathcal{H}$ de noyau reproduisant $k$.

Dans le cadre du modèle linéaire (1.9), si on utilise le noyau linéaire en dimension $d$ $k_{\mathrm{d}}^{\mathrm{lin}}$, le risque empirique est égal à $\forall \theta \in \Theta (\Theta = \mathbb{R}^d), C_n(\theta) = \frac{1}{2n} \|Y - X\theta\|_{2,n}^2$. On note $\hat{\theta}^{(t)}$ l'estimateur de $\theta^*$ obtenu par l'algorithme de descente de gradient à l'itération $t$ et $\hat{Y}^{(t)} = X\hat{\theta}^{(t)}$. La précision de $\hat{\theta}^{(t)}$ est mesurée par l'erreur de prédiction $\Delta(\hat{Y}^{(t)}) = \frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$ (avec $Y^* = X\theta^*$). RASKUTTI, WAINWRIGHT et Yu 2014 ont défini une règle d'arrêt $\hat{t}_W$ dont le but est d'estimer $t^* = \underset{t \in \mathbb{N}}{\operatorname{argmin}} \frac{1}{n} \|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$. La règle d'arrêt $\hat{t}_W$ a pour but de minimiser l'erreur de prédiction en minimisant l'un de ses majorants avec grande probabilité. Un majorant de l'erreur de prédiction est $\bar{B}_t^2 + \bar{V}_t$ où $\bar{B}_t^2$ et $\bar{V}_t$ sont respectivement des majorants du biais au carré de et de la variance de $\hat{Y}^{(t)}$ avec grande probabilité. La règle d'arrêt $\hat{t}_W$ réalise donc un compromis entre le biais et la variance de $\hat{Y}^{(t)}$ :

$$\hat{t}_W = \min \left\{ t \in \mathbb{N} : \bar{V}_t > \frac{5}{4e} \bar{B}_t^2 \right\} - 1. \quad (1.10)$$
La figure 1.4 représente l'erreur de prédiction, $\bar{B}_t^2$, $\bar{V}_t$ et $\bar{B}_t^2 + \bar{V}_t$ en fonction de l'itération $t$. Nous avons positionné sur cette figure $t^*$, $\hat{t}_W$. La règle d'arrêt $\hat{t}_W$ est l'itération à partir de laquelle le majorant $\bar{V}_t$ de la variance de $\hat{Y}^{(t)}$ est $\frac{5}{4e} \approx 0.45$ plus grand que le majorant $\bar{B}_t^2$ du biais au carré de $\hat{Y}^{(t)}$. Nous observons que $\hat{t}_W$ se situe lorsque $t \mapsto \Delta(\hat{Y}^{(t)})$ décroît, i.e. lorsque le biais de $\hat{Y}^{(t)}$ est grand. Cette figure est donc une illustration de l'assertion (a) du théorème 1 (RASKUTTI, WAINWRIGHT et YU 2014) qui affirme que l'erreur de prédiction tend à décroître avant la règle d'arrêt $\hat{t}_W$. Finalement, nous observons qu'un majorant de $\Delta(\hat{Y}^{(t)})$ (i.e. $\bar{B}_t^2 + \bar{V}_t$) est éloigné de $\Delta(\hat{Y}^{(t)})$. Nous proposerons dans le chapitre 3 un majorant plus précis de $\Delta(\hat{Y}^{(t)})$.

Pour $d = 20, n = 30, \alpha = 0.01$

<figure><img src="image_7.png" /><figcaption>FIGURE 1.4 – Erreur de prédiction $\frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$ en fonction de l'itération $t$ pour $n = 30, d = 20, \alpha = 0.01$. Tracé de $\bar{B}_t^2, \bar{V}_t$ et $\bar{B}_t^2 + \bar{V}_t$ en fonction de $t$.</figcaption></figure>

Le coût en temps de calcul de $\hat{\theta}^{(t_W)}$ obtenu par l'algorithme GD associé à la règle d'arrêt $\hat{t}_W$ (cf. équation (1.10)) est la somme du coût du calcul de $\hat{t}_W$ et du calcul de $\hat{\theta}^{(t_W)}$ par l'algorithme 3. $\hat{t}_W$ nécessite une décomposition en valeurs singulières de la matrice $X^T X$. $\hat{\theta}^{(t_W)}$ est, quant à lui, calculé grâce à l'algorithme 3. La complexité en temps de $\hat{\theta}^{(t_W)}$ est donc de $O(\hat{t}_W n d^2)$. La complexité en mémoire de $\hat{\theta}^{(t_W)}$ est de $O(d n)$ à cause du stockage de matrice $X$.

Concernant les performances statistiques, le théorème 1 (RASKUTTI, WAINWRIGHT et YU 2014) montre que l'erreur de prédiction est majorée par une fonction décroissante en $t$ pour tout $t \in [1, \hat{t}_W]$. Ainsi, l'erreur de prédiction en $t = \hat{t}_W$ tend à être minimale. De plus, pour $t > \hat{t}_W$ l'espérance de l'erreur de prédiction ou l'erreur moyenne quadratique de $\hat{Y}^{(t)}$ (notée EQM($\hat{Y}^{(t)}$)) est majorée par une fonction croissante de $t$ donc suggère que la précision statistique de l'estimateur $\hat{\theta}^{(t)}$ se détériore si on effectue trop d'itérations. Ces deux résultats théoriques sont illustrés par la figure 1.5 et justifient d'utiliser une règle d'arrêt pour améliorer la précision de l'estimateur $\hat{\theta}^{(t)}$.

**Deuxième règle d'arrêt** En régression, BLANCHARD, HOFFMANN et REISS 2016 ont proposé une règle d'arrêt associée à un algorithme de descente de gradient à pas fixe $\alpha > 0$. Cet algorithme
<figure><img src="image_8.png" /><figcaption>FIGURE 1.5 – Erreur de prédiction $\frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$ en fonction de l'itération $t$ pour $n = 30$, $d = 20$ et un pas constant $\alpha$ égal à 0.01.</figcaption></figure>

de descente de gradient a pour fonction objectif la fonction des moindres carrés dans le cadre du modèle linéaire (1.9) : cet algorithme calcule donc les mêmes estimateurs $\hat{\theta}^{(t)}$ que ceux obtenus par RASKUTTI, WAINWRIGHT et Yu 2014 au paragraphe précédent. La précision de l'estimateur $\hat{\theta}^{(t)}$ est mesurée par $\|\hat{\theta}^{(t)} - \theta^*\|_{2,d}^2$.

La règle d'arrêt $\hat{t}_B$ est définie par :

$$ \hat{t}_B = \inf\{t \in [t_0, +\infty[: R_t^2 \le \eta]\}, \quad (1.11) $$

où $R_t^2 = \|Y - X\hat{\theta}^{(t)}\|_{2,n}^2$ représente les résidus; $t_0$ et $\eta$ sont des constantes à calibrer.

$\hat{t}_B$ est donc l'itération à partir de laquelle les résidus $R_t$ deviennent petit. Cela signifie que, pour $t > \hat{t}_B$, le phénomène de surapprentissage se produit. La règle d'arrêt $\hat{t}_B$ a donc pour but de limiter le phénomène de surapprentissage en stoppant l'algorithme avant qu'il se produise. On remarque aussi que, à la différence de la règle d'arrêt $\hat{t}_W$, $\hat{t}_B$ n'a pas été bâtie sur des majorants. La règle d'arrêt $\hat{t}_B$ a pour but d'imiter le comportement de la règle d'arrêt $t_B$ (BLANCHARD, HOFFMANN et REISS 2016) définie par :

$$ t_B = \inf\{t \in [t_0, +\infty[: b(\hat{Y}^{(t)})^2 \le \text{var}(\hat{Y}^{(t)})\}, \quad (1.12) $$

où $b(\hat{Y}^{(t)})^2$ et $\text{var}(\hat{Y}^{(t)})$ sont respectivement le biais au carré et la variance de $\hat{Y}^{(t)}$.

Le coût en temps de calcul de $\hat{\theta}^{(\hat{t}_B)}$ obtenu par l'algorithme GD avec la règle d'arrêt $\hat{t}_B$ (cf. équation 1.11) est la somme du calcul de $\hat{t}_B$ et du calcul de $\hat{\theta}^{(\hat{t}_B)}$ par l'algorithme 3. $\hat{t}_B$ nécessite une décomposition en valeurs singulières de la matrice $X^T X$ à cause de la calibration du paramètre $t_0$. $\hat{\theta}^{(\hat{t}_B)}$ est, quant à lui, calculé par l'algorithme 3. La complexité en temps de $\hat{\theta}^{(\hat{t}_B)}$ est donc de $O(\hat{t}_B n d^2)$. La complexité en mémoire de $\hat{\theta}^{(\hat{t}_B)}$ est de $O(dn)$ à cause du stockage de la
matrice X.

Une inégalité oracle a été obtenue pour l'estimateur $\hat{\theta}^{(t_B)}$ (BLANCHARD, HOFFMANN et REISS 2016). Cette inégalité oracle est un résultat à distance finie garantissant que l'erreur moyenne quadratique (dans ce cas, l'erreur moyenne quadratique est définie par $\text{EQM}(\hat{\theta}^{(t)}) = E_{\epsilon}[\|\hat{\theta}^{(t)} - \theta^*\|_{2,d}^2]$) ($E_{\epsilon}[\cdot]$ est calculée en intègrant par rapport à la loi de probabilité de $\epsilon$) de $\hat{\theta}^{(t_B)}$ est proche de l' erreur moyenne quadratique optimale parmi l'ensemble des estimateurs $\{\hat{\theta}^{(t)}\}_{t \in \mathbb{N}}$.

La règle d'arrêt $\hat{t}_B$ présente au moins deux inconvénients. $\hat{t}_B$ a été défini pour imiter le comportement de la règle d'arrêt $t_B$ (cf. équation (1.12)). $t_B$ est l'itération $t$ pour laquelle le biais au carré de $\hat{Y}^{(t)}$ est environ égal à la variance de $\hat{Y}^{(t)}$. Or, la figure 1.6 montre, dans un cas particulier, que $\bar{t} = \underset{t \in \mathbb{N}}{\operatorname{argmin}}\{\text{EQM}(\hat{Y}^{(t)})\} (\text{EQM}(\hat{Y}^{(t)})$ est l'erreur moyenne quadratique de $\hat{Y}^{(t)})$ ne se situe pas à l'itération à laquelle $b(\hat{Y}^{(t)})^2 = \text{var}(\hat{Y}^{(t)})$.

De plus, $\hat{t}_B$ dépend de constantes que l'utilisateur doit choisir : ce qui pose le problème délicat

Pour $d = 20$, $n = 30$

<figure><img src="image_9.png" /><figcaption>FIGURE 1.6 – Erreur moyenne quadratique de $\hat{Y}^{(t)}$ ou $E[\frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2]$ ($Y^* = X\theta^*$) en fonction de l'itération $t$ pour $n = 30$, $d = 20$ et $\alpha = 0.01$.</figcaption></figure>

de leur calibration pour obtenir un estimateur $\hat{\theta}^{(t_B)}$ ayant de bonnes performances statistiques.

Troisième règle d'arrêt

En régression non - paramétrique utilisant les noyaux, YAO, ROSASCO et CAPONNETTO 2007 ont utilisé une règle d'arrêt associée à un algorithme de descente de gradient de pas $\alpha_t = \frac{1}{\kappa^2(1+t)^\alpha}$ où $a \in [0,1[$ et $\kappa := \max(\sup_{x \in \mathcal{X}} \sqrt{k(x,x)}, 1)$. Cet algorithme de descente de gradient est appliqué au risque empirique définie par, pour tout $f \in \mathcal{H}$, $C_n(f) = \frac{1}{n} \sum_{i=1}^n (Y_i - f(X_i))^2$ où $\mathcal{H}$ est un RKHS de noyau reproduisant $k$ et $(X_1, Y_1), \dots, (X_n, Y_n)$ sont des variables aléatoires indépendantes de loi de probabilité $\rho$ définie sur $\mathcal{X} \times \mathbb{R}$.

Dans le cas du modèle linéaire (1.9), pour le noyau linéaire en dimension $d k_{\text{d}}^{\text{lin}}$, $\mathcal{X} = \mathbb{R}^d$, $\mathcal{H}$ est l'ensemble des formes linéaire définies sur $\mathbb{R}^d$. Donc $\hat{f}^{(t)}$ définie par, $\forall x \in \mathbb{R}^d$, $\hat{f}^{(t)}(x) = x^T \hat{\theta}^{(t)}$, est l'estimateur obtenu par l'algorithme de descente de gradient à l'itération $t$.
La règle d'arrêt est définie par (YAO, ROSASCO et CAPONNETTO 2007) :

$$ \hat{t}_R = \lfloor n^{\frac{1}{(2r+2)(1-a)}} \rfloor + 1, \qquad (1.13) $$

où $r$ est un paramètre de régularité dépendant de la fonction de régression $f^*$ définie par, $\forall x \in \mathbb{R}^d$, $f^*(x) = x^T \theta^*$. $\forall x \in \mathbb{R}$, $\lfloor x \rfloor$ est la partie entière inférieure de $x$.

Il est à noter que la règle d'arrêt $\hat{t}_R$ traduit un compromis biais - variance et est construite de sorte à majorer le risque minimax.

Comme $\hat{t}_R$ a une formule close (cf. équation 1.13), donc la règle d'arrêt $\hat{t}_R$ n'engendre pas un coût en temps de calcul supplémentaire. Comme $\hat{\theta}^{(\hat{t}_R)}$ est obtenu par l'algorithme GD (cf. algorithme 3) appliqué aux moindres carrés dans le cadre du modèle linéaire (1.9), la complexité en temps de $\hat{\theta}^{(\hat{t}_R)}$ est $O(\hat{t}_R n d^2)$.

Nous détaillons les performances statistiques de l'estimateur $\hat{\theta}^{(\hat{t}_R)}$. Sous des hypothèses restrictives sur la fonction de régression $f^* \in \mathcal{H}$, $\kappa < +\infty$ et le support de $\rho$ est inclus dans $\mathcal{X} \times [-M, M]$ ($M \ge 0$), la norme dans $L_{\rho_X}^2$ ($\rho_X$ est la mesure marginale de $\rho$) de la différence entre $\hat{f}^{(\hat{t}_R)}$ et $f^*$ est majorée par $n^{-1/6}$ (YAO, ROSASCO et CAPONNETTO 2007). En effet, $f^* \in \mathcal{H}$ vérifie les hypothèses du théorème principal avec $r = \frac{1}{2}$ (YAO, ROSASCO et CAPONNETTO 2007; BAUER, PEREVERZEV et ROSASCO 2007). YAO, ROSASCO et CAPONNETTO ont défini la règle d'arrêt 1.13 afin d'obtenir une majoration du risque minimax, i.e. une majoration de la norme dans $L_{\rho_X}^2$ de la différence entre $\hat{f}^{(\hat{t}_R)}$ et $f^*$ pour $f^*$ appartenant à une certaine classe de fonctions dans le pire des cas.

La règle d'arrêt $\hat{t}_R$ présente les inconvénients suivants dans le cadre du modèle linéaire (cf. modèle (1.9)). Certaines hypothèses du théorème principal (YAO, ROSASCO et CAPONNETTO 2007) ne sont pas vérifiées lorsque $\mathcal{X} = \mathbb{R}^d$ et pour le noyau linéaire $k_d^{\text{lin}}$. En effet, pour $\mathcal{X} = \mathbb{R}^d$ et pour le noyau $k_d^{\text{lin}}$, $\kappa = +\infty$. De plus, ils supposent que $\forall i \in [1, n]$, $Y_i \in [-M, M]$ presque sûrement. Ces deux hypothèses restrictives nous empêchent d'utiliser la règle d'arrêt $\hat{t}_R$ dans le cadre du modèle linéaire (1.9).

## 1.4 Conclusion

Les algorithmes d'optimisation itératifs et les règles d'arrêt associées $\hat{t}$ et $\hat{D}$ permettent de fournir des estimateurs $\hat{\theta}^{(\hat{t})}$ et $\hat{\tau}_{\hat{D}}$ respectivement pour le problème de régression linéaire et pour le problème de détection de ruptures ayant de bonnes performances statistiques et peu coûteux en temps de calcul.

Par exemple, dans le cadre du problème de détection de ruptures, l'heuristique de segmentation binaire utilisée par la méthode ECP ou BinSeg (FRYZLEWICZ 2014) que nous étudierons au chapitre suivant permet d'obtenir des estimateurs ayant à la fois de bonnes performances statistiques (consistance forte et consistance) en stoppant l'algorithme à l'itération $\hat{D}$. Dans le cadre du problème de détection de ruptures dans la distribution, nous avons développé au chapitre 2 la méthode *kernel stopping rule binary segmentation* (KSRBS) basée sur l'heuristique de segmentation binaire pour répondre au besoin de concevoir des algorithmes ayant une plus faible complexité en temps que la méthode KCP. En effet, la méthode KCP nécessite de calculer toutes les meilleures segmentations en $D$ segments jusqu'à un nombre de segments $D_{\text{max}}$ potentiellement élevé : ce qui engendre un coût important en temps de calcul.
Il est à noter qu'il est a priori plus facile d'obtenir des estimateurs construits à l'aide de règles d'arrêt ayant de bonnes performances statistiques lorsque la quantité à estimer est discrète (e.g. pour le problème de détection de ruptures dans la distribution) plutôt que continu (e.g. la régression linéaire). Nous avons exploré au chapitre 3, dans le cadre simple de la régression linéaire, le fonctionnement d'une règle d'arrêt pour estimer le paramètre continu θ* et obtenu un estimateur ayant de bonnes performances statistiques et peu coûteux en temps de calcul.
Chapitre 2

# Règle d’arrêt et segmentation binaire à noyau

Dans ce chapitre, nous proposons un algorithme itératif avec une règle d’arrêt dans le cadre du problème de détection de ruptures dans la distribution. Cette méthode appelée *kernel stopping rule binary segmentation* (KSRBS) est basée sur l’heuristique de segmentation binaire (Scott et Knott 1974). Les méthodes basées sur la segmentation binaire sont particulièrement pertinentes dans le cadre de données volumineuses car elles ont une complexité en temps inférieure aux méthodes basées sur la programmation dynamique vues au chapitre précédent. De plus, KSRBS utilise une règle d’arrêt $\hat{D}$ pour choisir le nombre de segments. Nous présentons, dans un premier temps, la méthode de segmentation binaire dans la moyenne d’un signal réel. Puis, nous détaillons le fonctionnement de KSRBS qui est une version “à noyau” de l’algorithme BinSeg (Fryzlewicz 2014). Nous avons aussi transposé le théorème 3.1 de Fryzlewicz 2014 assurant la consistance des estimateurs $\hat{\tau}_{\hat{D}}$ où $\hat{D}$ est la règle d’arrêt de KSRBS. Enfin, des simulations permettent de comparer les performances statistiques et en temps de calcul de KSRBS à la méthode KCP.

## 2.1 Segmentation binaire

Dans cette partie, nous faisons tout d’abord un état de l’art spécifique à l’algorithme BinSeg (Fryzlewicz 2014) proposé dans le cadre de la détection de ruptures dans la moyenne d’un signal réel. Puis, nous expliquons l’algorithme KSRBS adapté au cadre de la détection de ruptures dans la distribution. Nous rappelons le modèle

$$ \forall i \in [1, n], Y_i = \mu_i + \epsilon_i, \qquad (2.1) $$

où $\forall i \in [1, n]$, $\mu_i = m_{P_{X_i}}$ est l’élément moyen de la variable aléatoire $X_i$ (cf. partie 1.2.1).

Nous détaillons uniquement dans la partie traitant de BinSeg les remarques que l’on peut faire sur le fonctionnement de BinSeg. En effet, utiliser BinSeg revient à utiliser KSRBS avec le noyau linéaire en dimension $1 k_{\text{lin}}^1$.
### 2.1.1 Segmentation binaire dans la moyenne d'un signal réel

Nous expliquons comment l'algorithme BinSeg récupère des instants de ruptures estimés grâce à la segmentation binaire et une règle d'arrêt.

Pour déterminer ces instants de ruptures estimés sur un segment $[[s, e]]$ où $1 \le s < e \le n$, BinSeg utilise la statistique $\tilde{X}_{s,e}^b$ définie par :

$$ \tilde{X}_{s,e}^b = \sqrt{\frac{(e-b)}{T(b-s+1)}} \sum_{i=s}^{b} X_i - \sqrt{\frac{(b-s+1)}{T(e-b)}} \sum_{i=b+1}^{e} X_i, \quad (2.2) $$

où $\{X_i\}_{i \in [1,n]}$ est définie par le modèle (1.1), $b \in [[s, e-1]]$ est un instant de ruptures candidat et $T = e-s+1$ est la longueur du segment $[[s, e]]$.

Pour déterminer un instant de ruptures estimé, BinSeg procède en deux étapes. Pour la première étape, BinSeg recherche, comme pour la méthode CART, l'instant de ruptures candidat qui minimise le plus le risque empirique sur le segment $[[s, e]]$. La détermination de cet instant de ruptures candidat est faite par la recherche du point de maximum global de $|\tilde{X}_{s,e}^b|$ noté $b_0$ pour $b \in [[s, e-1]]$ grâce à la propriété suivante (FRYZLEWICZ 2014) :

$$ b_0 = \arg \max_{b: s \le b < e} |\tilde{X}_{s,e}^b| = \arg \min_{b: s \le b < e} \|X_{s,e} - \hat{\mu}_{\tau_b}\|_{2,T}^2, \quad (2.3) $$

où $\tau_b = \{s-1, b, e\}$. $X_{s,e} = \{X_s, \dots, X_e\}$. T est égal à $e-s+1$. $\hat{\mu}_{\tau_b} \in \mathbb{R}^T$ est défini par l'équation (1.4) (i.e. $\hat{\mu}_{\tau_b} = \underset{u \in \tau_b}{\operatorname{argmin}} \|X_{s,e} - u\|_{2,T}^2$). On peut montrer que $\hat{\mu}_{\tau_b}$ peut s'exprimer de la façon suivante : $\forall i \in [[s, b]], (\hat{\mu}_{\tau_b})_i = \bar{X}_{s,b} = \frac{1}{b-s+1} \sum_{i=1}^{s} X_i$ et $\forall i \in [[b+1, e]], (\hat{\mu}_{\tau_b})_i = \bar{X}_{b+1,e} = \frac{1}{e-b} \sum_{i=b+1}^{e} X_i$.

Une réécriture $|\tilde{X}_{s,e}^b|$ montre que $|\tilde{X}_{s,e}^b|$ est d'autant plus grand que la différence en valeur absolue entre la moyenne empirique de $X_{1,n} = \{X_1, \dots, X_n\}$ sur le segment $[[s, b]]$ et la moyenne empirique de $X_{1,n}$ sur le segment $[[b+1, e]]$ est grande. En effet, $\tilde{X}_{s,e}^b$ peut s'écrire :

$$ \tilde{X}_{s,e}^b = \sqrt{\frac{(e-b)(b-s+1)}{T}} \sum_{i=s}^{b} X_i - \sqrt{\frac{(b-s+1)}{T(e-b)}} \sum_{i=b+1}^{e} X_i \\ \Rightarrow \tilde{X}_{s,e}^b = \sqrt{\frac{(b-s+1)(e-b)}{T}} \left[ \frac{1}{b-s+1} \sum_{i=s}^{b} X_i - \frac{1}{e-b} \sum_{i=b+1}^{e} X_i \right], $$

De plus, comme $\frac{(e-b)(b-s+1)}{T} = T(1 - \frac{b-s+1}{T})\left(\frac{b-s+1}{T}\right)$ et $x \mapsto x(1-x)$ a un maximum en $x = \frac{1}{2}$ alors le facteur $\frac{(e-b)(b-s+1)}{T} = T(1 - \frac{b-s+1}{T})\left(\frac{b-s+1}{T}\right)$, présent dans l'expression de $\tilde{X}_{s,e}^b$, favorise b loin des bords de $[[s, e]]$. Une illustration de $\tilde{X}_{s,e}^b$ (cf. figure 2.1) confirme la remarque faite ci-dessus.

La récupération des instants de ruptures candidats grâce à la segmentation binaire est expliquée dans la section suivante car utiliser BinSeg revient à utiliser KSRBS avec le noyau linéaire en dimension $1$ $k_1^{\text{lin}}$.

De même, la deuxième étape de l'algorithme BinSeg est l'étape de sélection de modèle. Cette deuxième étape est détaillée dans la partie traitant de KSRBS pour les raisons citées dans le paragraphe précédent.

Grâce à l'algorithme BinSeg, FRYZLEWICZ 2014 a obtenu un résultat de consistance de $\hat{\tau}_{\hat{D}} = \{\hat{\tau}_0, \dots, \hat{\tau}_{\hat{D}}\}$, i.e. $\forall \delta > 0$, $P(|\frac{\hat{\tau}_i - \tau_i^*}{n}| \ge \delta) \to 0$. Nous avons étudié une version "à noyau" de
<figure><img src="image_10.png" /><figcaption>FIGURE 2.1 – Illustration de $\tilde{X}_{s,e}^{b_0}$ pour $n = 200$. $\bar{X}_{s,b_0}$ et $\bar{X}_{b_0+1,e}$ sont respectivement les moyennes empiriques de $X_{1,n} = \{X_1, \dots, X_n\}$ sur les segments $[[s, b_0]]$ et $[[b_0 + 1, e]]$.</figcaption></figure>

l'algorithme BinSeg appelé KSRBS et transposé le résultat de consistance $\hat{\tau}_D$ au cadre de la détection de ruptures dans la distribution.

## 2.1.2 Ruptures dans la distribution et segmentation binaire

Pour réaliser de la détection de ruptures dans la distribution, nous avons vu au chapitre précédent que nous pouvions utiliser les noyaux semi définis positifs. Les nouvelles variables aléatoires étudiées $\{Y_i\}_{i \in [1,n]}$ sont définies par le modèle (2.1). Etant donné que, pour des noyaux caractéristiques, faire de la détection de ruptures dans la distribution est équivalente à faire de la détection de ruptures dans les éléments moyens d'un RKHS $\mathcal{H}$, nous avons transposé à l'aide des noyaux semi définis positifs l'algorithme BinSeg réalisant de la détection de ruptures dans la moyenne d'un signal réel. Il est à noter qu'il peut être utile de détecter des changements dans certains moments de $X_i$ ($i \in [1,n]$) à l'aide de noyaux qui ne sont pas caractéristiques. Par exemple, le noyau polynomial d'ordre $p \ge 1$ (cf partie 1.2.1) n'est pas caractéristique et permet de détecter des changements dans les $p$ premiers moments de $X_i$ ($i \in [1,n]$) (GARREAU et ARLOT 2016).

Nous avons défini le vecteur $\tilde{Y}_{s,e}^b \in \mathcal{H}$ de manière analogue à $\tilde{X}_{s,e}^b$ (cf. équation (2.2)) :

$$ \tilde{Y}_{s,e}^b = \sqrt{\frac{(e-b)}{T(b-s+1)}} \sum_{i=s}^{b} Y_i - \sqrt{\frac{(b-s+1)}{T(e-b)}} \sum_{i=b+1}^{e} Y_i, $$

pour $b \in [[s, e-1]]$ et $T = e-s+1$.

KSRBS procède comme BinSeg en deux étapes. La première étape consiste à chercher l'instant de ruptures candidat $b_0$ qui minimise le plus le risque empirique sur le segment $[[s, e]]$. De la même manière que pour $\tilde{X}_{s,e}^b$ (cf. équation (2.3)), d'après la propriété 2.1.1, nous savons que $b_0$ est le point de maximum global de $||\tilde{Y}_{s,e}^b||_\mathcal{H}$ pour $b \in [[s, e-1]]$ :
### Propriété 2.1.1.

$$b_0 = \arg \max_{b: s \le b < e} \| \tilde{Y}_{s,e}^b \|_{\mathcal{H}} = \arg \min_{b: s \le b < e} \| Y_{s,e} - \hat{\mu}_{\tau_b} \|_{\mathcal{H}, T}^2 \quad (2.4)$$

où $\tau_b = \{s-1, b, e\}$. $Y_{s,e} = \{Y_s, \dots, Y_e\}$. T est égal à $e-s+1$. $\hat{\mu}_{\tau_b}$ est défini de manière analogue à l'équation (1.4) (i.e. $\hat{\mu}_{\tau_b} = \argmin_{u \in S_{\tau_b}} \|Y_{s,e} - u\|_{2,T}^2$). Pour rappel, on peut montrer que $\hat{\mu}_{\tau_b}$ a l'expression suivante : $\forall i \in \llbracket s, b \rrbracket$, $(\hat{\mu}_{\tau_b})_i = \frac{1}{b-s+1} \sum_{i=s}^b Y_i$ et $\forall i \in \llbracket b+1, e \rrbracket$, $(\hat{\mu}_{\tau_b})_i = \frac{1}{b-s+1} \sum_{i=s}^b Y_i$ (ARLOT, CELISSE et HARCHAoui 2012). La preuve de la propriété 2.1.1 est disponible à la partie 2.5.2.

La deuxième étape de l'algorithmme KSRBS consiste à définir le seuil $\zeta_n$ tel que $b_0$ est retenu comme un instant de ruptures estimé à la condition que $\|\tilde{Y}_{s,e}^{b_0}\|_{\mathcal{H}}$ soit plus grand que $\zeta_n$. Par exemple, dans le cas de la détection de ruptures dans la moyenne d'un signal réel, pour le noyau linéaire en dimension $1$ $k_1^{\text{lin}}$, $\|\tilde{Y}_{s,e}^{b_0}\|_{\mathcal{H}} = |\tilde{X}_{s,e}^{b_0}|$. Ainsi, compte tenu des remarques de la section 2.1.1, cela signifie que $|\tilde{X}_{s,e}^{b_0}|$ doit être suffisamment grand, i.e. $b_0$ est situé loin des bords de $\llbracket s, e \rrbracket$ et le changement dans la moyenne du signal $X_{1,n}$ est suffisamment important en $b_0$ pour que $b_0$ soit un instant de ruptures estimé. KSRBS poursuit ensuite récursivement la recherche d'instants de ruptures estimés potentiels sur chacun des deux sous segments délimités par $b_0$ (i.e. $\llbracket s, b_0 \rrbracket$ et $\llbracket b_0 + 1, e \rrbracket$). Il est à noter que, comme pour la méthode CART et ECP décrite dans la section 1.2.4, les instants de ruptures estimés ne sont pas remis en cause. Si $|\tilde{X}_{s,e}^{b_0}|$ est plus petit que le seuil $\zeta_n$, $b_0$ n'est pas défini comme un instant de ruptures estimé et plus aucun instant de ruptures ne sera estimé sur le segment $\llbracket s, e \rrbracket$. L'algorithmme KSRBS s'arrête lorsque tous les segments de $\llbracket 1, n \rrbracket$ délimités par les instants de ruptures estimés ne contiennent plus d'instants de ruptures estimés potentiels.

Pour plus de clarté, nous expliquons les 2 premières itérations de l'algorithmme KSRBS. KSRBS est exécuté par KSRBS(1, n, $\zeta_n$) (cf. algorithme 7).

**Première itération** On cherche $j_1$ l'instant de ruptures candidat minimisant le plus le risque empirique sur $\llbracket 1, n-1 \rrbracket$. Compte tenu de l'équation (2.4), $j_1$ est défini par :

$$j_1 = \arg \min_{1 \le j < n} \| \tilde{Y}_{1, n-1}^j \|_{\mathcal{H}}^2.$$

Si $\|\tilde{Y}_{1,n-1}^{j_1}\|_{\mathcal{H}} > \zeta_n$, alors $j_1$ est un instant de ruptures estimé et on note $\hat{\tau}_1 = j_1$. Sinon l'algorithmme KSRBS stoppe ($\hat{D} = 1$).

**Deuxième itération** On cherche ensuite les instants de ruptures candidats $j_2$, $j_3$ minimisant le plus le risque empirique sur les segments $\llbracket 1, \hat{\tau}_1 - 1 \rrbracket$ et $\llbracket \hat{\tau}_1, n-1 \rrbracket$ respectivement. $j_2$ et $j_3$ sont définis par :

$$j_2 = \arg \min_{1 \le j < \hat{\tau}_1} \| \tilde{Y}_{s_2, e_2}^j \|_{\mathcal{H}}^2 \quad \text{et} \quad j_3 = \arg \min_{\hat{\tau}_1 \le j < n} \| \tilde{Y}_{s_3, e_3}^j \|_{\mathcal{H}}^2$$

où $s_2 = 1$, $e_2 = \hat{\tau}_1$ et $s_3 = \hat{\tau}_1 + 1$, $e_3 = n$.

Si $\exists l \in \{2, 3\}$, $\|\tilde{Y}_{s_l, e_l}^{j_l}\|_{\mathcal{H}} > \zeta_n$, alors $j_l$ est un instant de ruptures estimé. Si $j_2$ et $j_3$ sont des instants de ruptures estimés, on ordonne $j_2$ et $j_3$, i.e. on choisit parmi les instants $j_2$ et $j_3$ celui qui
**Algorithme 7 algorithme KSRBS**

**Entrée** : donnée $(x_1, \dots, x_n) \in \mathcal{X}^n$.

KSRBS(s, e, $\zeta_n$)

Si $(e-s < 1)$

KSRBS stoppe.

**Sinon**

Faire $b_0 = \arg \max_{b \in [s, e-1]} \|\tilde{Y}_{s,e}^b\|_H$.

Si $\|\tilde{Y}_{s,e}^{b_0}\|_H > \zeta_n$

Faire $b_0$ est un instant de ruptures estimé.

Faire KSRBS(s, $b_0$, $\zeta_n$).

Faire KSRBS($b_0 + 1$, $e$, $\zeta_n$).

**Sinon**

KSRBS stoppe.

**Fin Si**

**Fin Si**

minimise le plus le risque empirique. Si $\forall l \in \{2, 3\}, \|\tilde{Y}_{s,l,e}^j\|_H \le \zeta_n$ alors KSRBS stoppe ($\hat{D} = 2$). Ainsi KSRBS permet de récupérer les segmentations $\{\hat{\tau}_D\}_{D \in [1, \hat{D}]}$ où $\hat{\tau}_D$ et $\hat{D}$ sont définis par :

$$ \hat{\tau}_D = \arg \min_{\tau \in \mathcal{M}_D(\hat{\tau}_1, \dots, \hat{\tau}_{D-2})} \|Y - \hat{\mu}_{\tau}\|_{H, \tau}^2 \quad (2.5) $$

$$ \hat{D} = \min \left\{ D \in \mathbb{N}^* : \forall i \in [0, D-1], \left\| \tilde{Y}_{\hat{\tau}_i, \hat{\tau}_{i+1}}^{j(i)} \right\|_H < \zeta_n \right\} $$

où $\mathcal{M}_D(\hat{\tau}_1, \dots, \hat{\tau}_{D-2})$ est l'ensemble des segmentations en $D$ segments ayant $D$ instants de ruptures déjà fixés. Formellement, $\mathcal{M}_D(\hat{\tau}_1, \dots, \hat{\tau}_{D-2})$ est défini par $\mathcal{M}_D(\hat{\tau}_1, \dots, \hat{\tau}_{D-2}) = \{\tau \in \mathcal{M}_{1:n}(D) : \tau \cap \hat{\tau}_{D-1} = \hat{\tau}_{D-1}\}$. $\forall i \in [0, D-1]$, $j(i) = \underset{j \in [\hat{\tau}_i+1, \hat{\tau}_{i+1}-1]}{\operatorname{argmax}} \{\|\tilde{Y}_{\hat{\tau}_i+1, \hat{\tau}_{i+1}}^j\|_H\}$.

Ainsi, l'équation (2.5) montre que KSRBS fournit un point de minimum local du risque empirique $\|Y - \hat{\mu}_{\tau}\|_{H, \tau}^2$ sur l'espace des segmentations en $D$ segments. En effet, l'équation (2.5) montre que KSRBS fournit un point de minimum sur le voisinage $\mathcal{M}_D(\hat{\tau}_1, \dots, \hat{\tau}_{D-2}) \subset \mathcal{M}_{1:n}(D)$. La méthode exacte de programmation dynamique fournit quant à elle un point de minimum global du risque empirique.

À des fins d'illustration, on peut aussi exécuter KSRBS jusqu'à un nombre de segments égal à $D_{max}$ par minimisation du risque empirique. La figure 2.2 montre que la distance de Frobenius entre la segmentation $\hat{\tau}_D$ et $\tau^*$ en fonction du nombre de segments $D$. La distance de Frobenius entre $\tau$ et $\tau^*$ est définie par (LAJUGIE, ARLOT et BACH 2014) :

$$ d_F(\tau, \tau') = \|M^\tau - M^{\tau'}\|_F \quad (2.6) \\ = \sqrt{\sum_{i=1}^n (M_{ij}^\tau - M_{ij}^{\tau'})^2} $$

$$ \text{où } M_{ij}^{\tau} = \frac{1_{\{i,j \text{ appartiennent au même segment de } \tau\}}}{\text{card}(\text{segment de } \tau \text{ contenant } i \text{ et } j)}. $$

La figure 2.2 montre que si le nombre de segments $D$ de la segmentation $\hat{\tau}_D$ est trop grand alors la
<figure><img src="image_11.png" /><figcaption>FIGURE 2.2 – Distance de Frobenius entre $\hat{\tau}_D$ et $\tau^*$ pour $1 \le D \le D_{max}$ où $D_{max} = 100$, $n = 1000$ et le noyau Gaussien $k_{h,d}^G$ en dimension 1 pour $h = 0, 1$. $D_{minF}$ est le nombre de segments minimisant la distance de Frobenius entre $\hat{\tau}_D$ et $\tau^*$.</figcaption></figure>

distance de Frobenius de $\hat{\tau}_D$ à $\tau^*$ est trop grande. Ceci illustre le phénomène de surapprentissage car lorsque $D$ tend vers $n-1$, $\hat{\mu}_{\tau}$ pour $\tau = \hat{\tau}_D$ tend vers $Y$. Ce phénomène de surapprentissage justifie d'utiliser une règle d'arrêt $\hat{D}$ pour stopper KBS afin de ne pas détériorer la qualité de la segmentation $\hat{\tau}_D$.

## 2.2 Consistance de l'estimateur

Dans cette partie, nous présentons notre résultat principal et les hypothèses garantissant celui-ci. Il s'agit d'un résultat de consistance de l'estimateur $\hat{\tau}_{\hat{D}}$ obtenu par KSRBS. Ce théorème est issu d'une transposition du théorème 3.1 de (FRYZLEWICZ 2014) au cadre des noyaux.

### 2.2.1 Hypothèses

Nous présentons dans cette section les hypothèses que l'on doit faire sur les termes d'erreur $\{\epsilon_i\}_{i \in [1,n]}$ et les "nouvelles" observations $\{Y_i\}_{i \in [1,n]}$ définies par (2.1) puis celle sur les vrais instants de ruptures $\{\tau_i^*\}_{i \in [0,D^*]}$ et les éléments moyens de $\{X_i\}_{i \in [1,n]}$ $\{\mu_i\}_{i \in [1,n]}$.

On fait les hypothèses suivantes :

(Bd) $\exists M \in \mathbb{R}_+$, $\forall i \in [1, n]$, $\|Y_i\|_{\mathcal{H}}^2 = k(X_i, X_i') \le M^2$ presque sûrement.

(G) $\{\epsilon_i\}_{i \in [1,n]}$ sont i.i.d et $\forall i \in [1,n]$, $\epsilon_i \in \mathcal{H}$ est une variable aléatoire gaussienne centrée (i.e. $\forall h \in \mathcal{H}, E[\langle\epsilon_i, h\rangle_{\mathcal{H}}] = 0$) et d'opérateur de covariance $\Sigma$ défini par $\forall h, h' \in \mathcal{H}, \langle\Sigma h, h'\rangle_{\mathcal{H}} = \text{cov}(\langle\epsilon_i, h\rangle_{\mathcal{H}}, \langle\epsilon_i, h'\rangle_{\mathcal{H}})$. On suppose que $\Sigma$ vérifie $\text{Tr}(\Sigma) = 1$.

(Sep) $\mathcal{H}$ est un espace séparable (i.e. $\mathcal{H}$ admet un sous ensemble dense dénombrable).

(tau) L'espace minimum entre deux vrais instants de ruptures vérifie $\forall i \in [1, D^*]$, $|\tau_i^* - \tau_{i-1}^*| \ge \delta_n$ où $\delta_n \ge C_1 n^\Theta$, $\Theta \le 1$ et $C_1$ est une constante ne dépendant pas de $n$.

(mu) $\{\mu_i\}_{i \in [1,n]}$ vérifie $\forall i \in [1, D^* - 1]$, $\mu_i^* = \|\mu_{\tau_{i+1}^*} - \mu_{\tau_i^*}\|_{\mathcal{H}} \ge \mu_n \ge C_2 n^{-w}$ où $w \ge 0$ et $C_2$ est une constante ne dépendant pas de $n$. Les paramètres $\Theta$ et $w$ vérifient $\Theta - \frac{w}{2} > \frac{3}{4}$.
L'hypothèse (Bd) est classique dans le cadre du problème de détection de ruptures dans la distribution (ARLOT, CELISSE et HARCHAOUI 2016; GARREAU et ARLOT 2016) : cette hypothèse permet de justifier l'existence de l'élément moyen de la variable aléatoire $X_i$. L'hypothèse (G) est utilisée dans la preuve du théorème 2.2.1 pour montrer que des événements se produisent avec grande probabilité. L'hypothèse (Sep) est classique dans le cadre des méthodes à noyaux (BAUER, PEREVERZEV et ROSASCO 2007; ARLOT, CELISSE et HARCHAOUI 2016). Il est à noter qu'un RKHS $\mathcal{H}$ est séparable si, par exemple, $k$ est continue sur $\mathcal{X}^2$ et $\mathcal{X}$ est séparable. Le noyau gaussien $k_{h,d}^G$ sur l'espace séparable $\mathcal{X} = \mathbb{R}^d$ est continue sur $\mathcal{X}^2$, donc le RKHS $\mathcal{H}$ associé à $k_{h,d}^G$ est séparable. Les hypothèses (tau) et (mu) sont les versions “à noyau” des hypothèses du théorème 3.1 (FRYZLEWICZ 2014). Elles supposent notamment que la distance minimale entre deux vrais instants de ruptures est assez grande. Ici cette distance est minorée par $n^{3/4}$. Une hypothèse analogue est faite par GARREAU et ARLOT 2016 et sera discuté dans les commentaires du résultat principal suivant.

## 2.2.2 Résultat principal

**Théorème 2.2.1.** {$Y_i$}$_{i\in[1,n]}$ vérifie le modèle (2.1) et on suppose les hypothèses (Bd), (G), (Sep), (tau), (mu). On suppose $\Theta - \frac{w}{2} > \frac{3}{4}$. Le paramètre de seuil $\zeta_n$ vérifie

$$1. \text{ Si } \Theta \in [\frac{3}{4}, 1[, \text{ pour } \theta \in ]1 - \Theta, \Theta - 1/2 - w[, \zeta = c_1 n^{\theta}$$

$$2. \text{ Si } \Theta = 1, \text{ pour } \theta < 1/2 - w, c_2(\log(n))^p \le \zeta_n \le c_3 n^{\theta} \quad (p>1/2),$$

pour des constantes strictement positives $c_1, c_2, c_3$. Alors, il existe des constantes strictement positives $c_4, c_5$ et un événement $C_n$ tels que $P(C_n) \ge 1 - c_4 n^{-1}$, où

$$C_n = \{\hat{D} = D^*, \max_{i \in [1, \hat{D}-1]} |\hat{\tau}_i - \tau_i^*| \le c_5 \varepsilon_n\},$$

$$\text{où } \varepsilon_n = \lambda_2^2 n^2 \delta_n^{-2} \mu_n^{-2} \quad (\lambda_2 \text{ doit être supérieur à } \sqrt{6 \log(n)}).$$

Le théorème 2.2.1 est un résultat de consistance du nombre et de la position des instants de ruptures estimés. Comme, compte tenu des hypothèses (tau) et (mu), $\frac{\varepsilon_n}{n}$ tend vers 0 lorsque $n$ tend vers $+\infty$, alors ce résultat de consistance signifie que $\forall i \in [1, \hat{D} - 1]$, $\frac{|\tau_i^* - \hat{\tau}_i|}{n}$ converge en probabilité vers 0, i.e. $\forall \delta > 0$, $P(\frac{|\tau_i^* - \hat{\tau}_i|}{n} \ge \delta) \xrightarrow{n \to +\infty} 0$. Ce résultat garantit aussi que, à distance finie, avec une probabilité supérieure à $1 - c_4 n^{-1}$, chaque instant de ruptures estimé $\hat{\tau}_i$ est dans un voisinage des $\tau_i^*$.

Nous faisons l'hypothèse que la distance minimale entre deux vrais instants de ruptures est minorée par $n^{3/4}$. GARREAU et ARLOT 2016 ont étudié la méthode KCP et, dans le théorème 1, supposent que la distance minimale entre deux vrais instants de ruptures est minorée par $\log(n)$ : ce qui est une hypothèse moins restrictive que la nôtre. GARREAU et ARLOT 2016 obtiennent également que $\hat{\tau}_{\hat{D}}$ converge vers $\tau^*$ à la vitesse $\log(n)/n$ : ce qui est une vitesse de convergence plus rapide que la nôtre. Néanmoins, pour choisir la constante de la pénalité et ainsi obtenir $\hat{\tau}_{\hat{D}}$, GARREAU et ARLOT 2016 utilisent l'heuristique de pente pour la calibration de la constante de la pénalité. Or, nous avons vu, au chapitre 1 que l'heuristique de pente est une méthode coûteuse en temps de calcul.

Un schéma de la preuve regroupant les idées de la preuve est donnée dans la partie 2.5.1. La preuve du théorème 2.2.1 est disponible en section 2.5.
## 2.3 Résultats numériques

Nous définissons, dans un premier temps, les objectifs de ces simulations et le cadre de simulations. Puis, nous interprétons les résultats numériques obtenus.

### 2.3.1 Objectifs

L'objectif de ces simulations est d'illustrer la performance statistique de la méthode KSRBS mesurée par la distance de Frobenius (cf. équation 2.6) et la distance de Haussdorf (cf équation (2.7)) entre les segmentations {$\hat{\tau}_D$}$_{D\in[1,D_{max}]}$ obtenues par KSRBS et la vraie segmentation $\tau^*$. La distance de Haussdorf entre les segmentations $\tau = \{\tau_0, \dots, \tau_D\}$ et $\tau' = \{\tau'_0, \dots, \tau'_{D'}\}$ est définie par :

$$d_H(\tau, \tau') = \max \left\{ \max_{1 \le i \le D-1} \min_{1 \le j \le D'-1} |\tau_i - \tau'_j|, \max_{1 \le j \le D'-1} \min_{1 \le i \le D-1} |\tau_i - \tau'_j| \right\}. \quad (2.7)$$

Nous évaluons l'influence du choix du noyau sur la précision des segmentations {$\hat{\tau}_D$}$_{D\in[1,D_{max}]}$ en réalisant ces simulations pour le noyau gaussien et le noyau linéaire en dimension 1. Nous n'avons pas comparé en temps de calcul KSRBS à la principale méthode concurrente KCP. En effet, la complexité en temps de KSRBS est de $O(\hat{D}n^2)$ dans le pire des cas et est donc inférieure à celle KCP ($O(D_{max}n^2)$) tant que $\hat{D}$ est plus petit que $D_{max}$. Nous avons vu, au chapitre 1 que la méthode KCP utilise l'heuristique de pente. L'heuristique de pente nécessite de calculer $\hat{\tau}_{\hat{D}}$ jusqu'à un nombre de segments $D_{max}$ potentiellement élevé : ce qui engendre un coût important en temps de calcul. Nous comparons KSRBS et KCP en calculant la distance de Haussdorf entre $\hat{\tau}_{\hat{D}}$ et $\tau^*$ pour différentes valeurs de $n$. Pour KCP, nous avons utilisé la variante de l'heuristique de pente utilisant la régression linéaire pour éviter de fixer les constantes $c_1$ et $c_2$ de la pénalité (cf partie 1.2.5).

### 2.3.2 Cadre de simulations

Pour évaluer la performance de KSRBS, nous fixons la taille de l'échantillon égale à $n = 1000$. La vraie segmentation $\tau^*$ a pour dimension $D^* = 11$ et les vrais instants de ruptures sont : $\tau_1^* = 100, \tau_2^* = 130, \tau_3^* = 220, \tau_4^* = 320, \tau_5^* = 370, \tau_6^* = 520, \tau_7^* = 620, \tau_8^* = 740, \tau_9^* = 790, \tau_{10}^* = 870$. $D_{max}$ est choisi égale à 100. Pour comparer la précision statistique de KSRBS et KCP, pour chaque valeur de $n \in \{200, 500, 1000, 1500, 2000, 3000\}$, nous fixons les vrais instants de ruptures écartés d'une distance constante égale à 100.

Le noyau gaussien en dimension $d = 1$ $k_{h,d}^G$ a pour paramètre $h = 0.1$. Le paramètre $\zeta_n$ est choisi égal à $C\sqrt{2\log(n)}\hat{\sigma}$ où $\hat{\sigma}$ est un estimateur du terme d'erreur ($\hat{\sigma}^2 = \frac{1}{n}\sum_{i=1}^n \|Y_i - \frac{1}{n}\sum_{j=1}^n Y_j\|_H^2$). La constante C a été calibrée empiriquement telles que $|\hat{D} - D^*|$ est minimale pour différentes tailles d'échantillons $n \in \{100, 200, 500\}$, pour $B = 100$ répétitions et pour le noyau gaussien et le noyau linéaire en dimension 1. Nous avons obtenu $C = 0.4$ pour le noyau gaussien et $C = 0.3$ pour le noyau linéaire.

On considère deux scénarios (ARLOT, CELISSE et HARCHAOUI 2016). Pour le scénario 1, le signal présente des changements dans la paire (moyenne, variance), tandis que pour le scénario 2, le signal a une moyenne et une variance constante. Un exemple des scénarios 1 et 2 est illustré sur la figure 2.3.

**Scénario 1** : La loi de probabilité de $X_i$ est soit : une loi binomiale de paramètre $N = 10$ et $p = 0.2$ ($B(10, 0.2)$), une loi binomiale négative de paramètres $N = 3$ et $p = 0.7$ ($NB(3, 0.7)$),
une loi hypergéométrique de paramètres $N = 10, b = 5$ et $r = 2$ ($\mathcal{H}(10, 5, 2)$), une loi normale de paramètre $m = 2.5$ et $\sigma^2 = 0.25$ ($\mathcal{N}(2.5, 0.25)$), une loi gamma de paramètres $k = 0.5$ et $\theta = 5$ ($\gamma(0.5, 5)$), une loi de Weibull de paramètres $k = 5$ et $\lambda = 2$ ($\mathcal{W}(5, 2)$), une loi de Pareto de paramètres $a = 1.5$ et $k = 3$ ($\mathcal{P}(1.5, 3)$).

**Scénario 2** : La loi de probabilité de $X_i$ est soit : une loi de Bernoulli de paramètre $p = 0.5$ ($\mathcal{B}(0.5)$), une loi normale de paramètres $m = 0.5$ et $\sigma^2 = 0.25$ ($\mathcal{N}(0.5, 0.25)$), une loi exponentielle de paramètre $\lambda = 2$ ($\mathcal{E}(2)$).

Pour les scénarios 1 et 2, la distribution à l'intérieur d'un segment est choisie différente de celle du segment précédent. Le scénario 1 est un cadre de simulations plus facile que le scénario 2 pour détecter des changements dans la distribution. En effet, la paire (moyenne, variance) est différente pour deux segments consécutifs pour le scénario 1 alors que cette paire est égale pour deux segments consécutifs pour le scénario 2. Pour le scénario 2, seule la loi de probabilité des variables aléatoires $X_i$ change entre deux segments consécutifs.

<figure><img src="image_12.png" /><figcaption>FIGURE 2.3 – Signaux du scénario 1 et 2. La position des vrais instants de ruptures est matérialisée par des lignes verticales rouges.</figcaption></figure>

### 2.3.3 Interprétation

Nous étudions l'influence du choix du nombre de segments $D$ sur la performance statistique de $\hat{\tau}_D$. Nous étudions aussi l'influence du choix du noyau sur la qualité des segmentations $\{\hat{\tau}_D\}_{D \in \llbracket 1, D_{max} \rrbracket}$. La figure 2.4 montre que, excepté pour le cas du noyau linéaire et le scénario 2, les distances de Frobenius et de Haussdorf entre $\hat{\tau}_D$ et $\tau^*$ décroissent puis croissent en fonction du nombre de segments $D$. De plus, la croissance de la distance de Frobenius entre $\hat{\tau}_D$ et $\tau^*$ est plus marquée que pour la distance de Haussdorf entre $\hat{\tau}_D$ et $\tau^*$. Excepté pour le cas du noyau linéaire et le scénario 2, nous observons que la segmentation la plus proche de $\tau^*$ parmi $\{\hat{\tau}_D\}_{D \in \llbracket 1, D_{max} \rrbracket}$ a un nombre de segments $D$ proche de $D^*$ : ainsi, une segmentation dont le nombre de segments estime $D^*$ aura tendance à avoir de bonnes performances statistiques. La figure 2.4 confirme que le noyau gaussien est plus adapté que le noyau linéaire pour faire de la détection dans la distribution. En effet, le noyau linéaire est performant pour faire de la détection de
ruptures dans la moyenne d'un signal réel. De plus, KSRBS est performant pour des noyaux caractéristiques qui permettent de faire de la détection de ruptures dans les éléments moyens d'un RKHS. Or, on sait que le noyau gaussien est un noyau caractéristique alors que le noyau linéaire ne l'est pas. Cette dernière remarque explique les différences en matière de performance statistique entre le noyau gaussien et le noyau linéaire, en particulier pour le scénario 2.

Nous étudions la qualité des instants de ruptures de la segmentation $\hat{\tau}_{\hat{D}}$ en les comparant à ceux de la vraie segmentation $\tau^*$. La figure 2.5 montre, pour chaque position $i \in [1, n]$, la probabilité d'obtenir un instant de ruptures estimé de la segmentation $\hat{\tau}_{\hat{D}}$. Dans le cas facile (scénario 1), nous observons que la probabilité que l'un des instants de ruptures estimé de $\hat{\tau}_{\hat{D}}$ soit un vrai instant de ruptures de la segmentation $\tau^*$ est comprise entre 0.5 et 0.6 pour le noyau gaussien et est comprise entre 0.4 et 0.5 pour le noyau linéaire avec un bruit de fond important. Dans le cas plus difficile (scénario 2), cette probabilité est plus faible : elle est respectivement comprise entre 0.4 et 0.5, et de l'ordre de 0.1 pour le noyau gaussien et le noyau linéaire. La figure 2.6 montre les histogrammes de $\hat{D}$ pour les scénarios 1 et 2. On observe, sur chacun de ces histogrammes, que la moyenne de $\hat{D}$ est plus grande que $D^*$. Cela signifie que KSRBS a tendance à surestimer le vrai nombre de segments. Néanmoins, pour le noyau gaussien, la probabilité de récupérer exactement les vrais instants de ruptures est satisfaisante pour les scénarios 1 et 2 bien que KSRBS suretime le vrai nombre de segments.

Nous comparons maintenant la précision statistique de KSRBS et KCP évaluée par $\frac{1}{n} d_H(\hat{\tau}_{\hat{D}}, \tau^*)$ où $d_H(\hat{\tau}_{\hat{D}}, \tau^*)$ est la distance de Haussdorf entre $\hat{\tau}_{\hat{D}}$ et $\tau^*$. Nous nous sommes placés dans le cas où la distance entre deux vrais instants de ruptures est constante. On observe sur la figure 2.7 que KSRBS a une meilleure précision statistique que KCP pour certaines valeurs de $n$ pour le scénario 2.

## 2.4 Conclusion

Dans ce chapitre, nous avons proposé un algorithme itératif avec une règle d'arrêt qui assure que $\hat{\tau}_{\hat{D}}$ soit précis et peu coûteux en temps de calcul. En effet, le théorème 2.2.1 garantit la consistance des instants de ruptures estimés et les résultats numériques démontrent la performance statistique de KSRBS. En particulier, les simulations montrent, pour le scénario 2, que KSRBS a une meilleur précision statistique que KCP pour certaines valeurs de $n$. De plus, KSRBS a une complexité en temps inférieure aux méthodes vues au chapitre précédent traitant de la détection de ruptures dans la distribution (KCP, PELT, ECP). La méthode PELT a une complexité inférieure à celle de KSRBS si le paramètre de régularisation de la méthode PELT est connu, ce qui n'est pas le cas. Ainsi, on doit ajouter la complexité en temps associée à la calibration du paramètre de régularisation pour obtenir la complexité de la méthode PELT. La faible complexité en temps de KSRBS est particulièrement pertinente dans le contexte de données volumineuses. KSRBS est donc une méthode alternative à la méthode basée sur la programmation dynamique qui est coûteuse en temps de calcul.

## 2.5 Preuves

Dans cette partie, nous donnons le schéma de la preuve du théorème 2.2.1 ainsi que les preuves des lemmes et des propriétés de ce théorème (VENKATRAMAN 1992; CHO et FRYZLEWICZ 2012; FRYZLEWICZ 2014).
<figure><img src="image_13.png" /><figcaption>FIGURE 2.4 – Tracé de la distance de Frobenius et de Haussdorf entre $\tilde{\tau}_D$ ($\tilde{\tau}_D$ est calculée par KSRBS) et $\tau^*$ pour $1 \le D \le D_{max}$ pour le noyau gaussien et le noyau linéaire et pour les scénarios 1 et 2. Les paramètres sont $n = 1000$, $D_{max} = 100$, $B = 500$ répétitions et $h = 0.1$ pour le noyau gaussien $k_{h,d}^G$.</figcaption></figure>

Nous définissons, tout d'abord, $\forall v = (v_s, ..., v_e) \in \mathcal{H}^T$, pour $b \in [[s, e-1]]$, le vecteur $\tilde{v}_{s,e}^b$ par

$$ \tilde{v}_{s,e}^b = \sqrt{\frac{e-b}{T(b-s+1)}} \sum_{i=s}^{b} v_i - \sqrt{\frac{b-s+1}{T(e-b)}} \sum_{i=b+1}^{e} v_i, \quad (2.8) $$

où $T = e-s+1$.

### 2.5.1 Schéma de la preuve du théorème 2.2.1

Initialement, pour $s = 1$ et $e = n$, deux cas peuvent se produire : il n'y a pas de vrais instants de ruptures dans le segment $[[1, n]]$ ou il y a des vrais instants de ruptures dans le segment $[[1, n]]$.
<figure><img src="image_14.png" /><figcaption>FIGURE 2.5 – Probabilité d'obtenir à la position $i \in [1, n]$ un instant de ruptures estimés de la segmentation $\hat{\tau}_{\hat{D}}$ ($\hat{\tau}_{\hat{D}}$ est calculée par KSRBS), pour le noyau gaussien et le noyau linéaire, et pour les scénarios 1 et 2. Les paramètres sont $n = 1000$, $D_{max} = 100$, $B = 500$ répétitions et $h = 0.1$ pour le noyau gaussien $k_{h,d}^G$. La position des vrais instants de ruptures est matérialisée par des lignes verticales rouges.</figcaption></figure>

Pour le premier cas, si il n'y a pas de vrais instants de ruptures dans le segment $[1, n]$, alors d'après le lemme 2.5.6, sur l'événement $A_n \cap B_n$ (les événements $B_n$ et $A_n$ sont définis par les lemmes 2.5.1 et 2.5.2), KSRBS stoppe ($\hat{D} = 1$).

Pour le deuxième cas, si il y a de vrais instants de ruptures dans le segments $[1, n]$ alors, comme $s = \tau_0^* + 1$ et $e = \tau_{D^*}$, $\exists i_0 \in [0, D^* - q - 1] (0 \le q \le D^* - 1)$,

$$ \tau_{i_0}^* \le s < \tau_{i_0+1}^* < \dots < \tau_{i_0+q}^* < e \le \tau_{i_0+q+1}^* \quad (2.9) $$
<figure><img src="image_15.png" /><figcaption>FIGURE 2.6 – Histogramme de $\hat{D}$ obtenu par KSRBS pour les scénarios 1 et 2. Les paramètres sont $n = 1000$, $B = 500$ répétitions et $h = 0.1$ pour le noyau gaussien $k_{h,d}^G$. La valeur de $D^* = 11$ est matérialisée par une ligne verticale rouge.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>FIGURE 2.7 – Figures 2.7a et 2.7b : $\frac{1}{n}d_H(\hat{\tau}_D, \tau^*)$ où $d_H(\hat{\tau}_D, \tau^*)$ désigne la distance de Haussdorf entre $\hat{\tau}_D$ et $\tau^*$. $\hat{\tau}_D$ est calculé par les méthodes KSRBS et KCP. Les paramètres sont $B = 100$ répétitions et $h = 0.1$ pour le noyau gaussien $k_{h,d}^G$.</figcaption></figure>

il existe $r \in [1, q]$,

$$s < \tau_{i_0+r}^* - C_3 \delta_n < \tau_{i_0+r}^* + C_3 \delta_n < e. \quad (2.10)$$

$$\max(\min(\tau_{i_0+1}^* - s, s - \tau_{i_0}^*), \min(\tau_{i_0+q+1}^* - e, e - \tau_{i_0+q}^*)) \le C_4 \epsilon_n. \quad (2.11)$$
En effet, comme $\delta_n$ est la plus petite distance entre deux vrais instants de ruptures et, $s = \tau_0^* + 1$ et $e = \tau_{D^*}$ alors l'hypothèse (2.10) est vérifiée. Comme $\epsilon_n$ tend vers $+\infty$ lorsque $n$ tend vers $+\infty$ et, $s = \tau_0^* + 1$ et $e = \tau_{D^*}$ alors l'hypothèse 2.11 est vérifiée.

Sur l'événement $A_n \cap B_n$, comme $s$ et $e$ vérifient les hypothèses 2.9, 2.10 et 2.11 alors, par le lemme 2.5.4, $b_0 = \arg \max_{s \le b < e} \|\tilde{Y}_{s,e}^b\|_H$ est à une distance $C_4\epsilon_n$ de $\tau_{i_0+r}^*$ et par le lemme 2.5.5, $\|\tilde{Y}_{s,e}^{b_0}\|_H > \zeta_n$. Par conséquent, $b_0$ est un estimateur de $\tau_{i_0+r}^*$. On remarque que $b_0$ ne peut pas être un estimateur d'un autre vrai instant de ruptures car $b_0$ est éloigné du vrai instant de ruptures le plus proche d'une distance supérieure à $\delta_n - C\epsilon_n$, quantité qui est supérieure à $C\epsilon_n$ car $\epsilon_n = o(\delta_n)$.

Par conséquent, KSRBS recherche d'autres vrais instants de ruptures sur $[[s, b_0]]$ et $[[b_0 + 1, e]]$. Supposons qu'il y a des vrais instants de ruptures non détectés sur $[[s, b_0]]$, nous allons démontrer que $s$ et $b_0$ vérifient les hypothèses 2.10 et 2.11. Comme $|b_0 - \tau_{i_0+r}^*| \le C_4\epsilon_n$ alors pour tout vrai instant de ruptures non détectés $\tau_{i_1}^* \in [[s, b_0]]$, $b_0 - \tau_{i_1}^* \ge \delta_n - C_4\epsilon_n$. La quantité $\delta_n - C_4\epsilon_n$ est supérieure à $C\delta_n$ pour une certaine constante $C > 0$ car $\epsilon_n = o(\delta_n)$. De plus, $\tau_{i_1}^* - s + 1 = \tau_{i_1}^* - \tau_{i_0+r}^* + \tau_{i_0+r}^* - s + 1 \ge (1 + C_3)\delta_n$. Ainsi, $s$ et $b_0$ vérifient l'hypothèse 2.10. $s$ et $b_0$ vérifient l'hypothèse 2.11 car $|b_0 - \tau_{i_0+r}^*| \le C_4\epsilon_n$.

Ainsi, KSRBS continue sur chaque $[[s, e]]$ qui contient des vrais instants de ruptures non détectés. KSRBS s'arrête lorsque $\|\tilde{Y}_{s,e}^{b_0}\|_H < \zeta_n$, i.e. d'après le lemme 2.5.6, lorsqu'il n'y a plus de vrais instants de ruptures non détectés sur le segment $[[s, e]]$.

Dans la suite de cette partie, nous donnons les preuves des lemmes et des propriétés permettant de démontrer le théorème 2.2.1.

## 2.5.2 Résultats principaux

**Propriété 2.5.1.** Un instant de ruptures candidat $b_0$ est défini comme le point de minimum du risque empirique sur le segment $[[s, e-1]]$ :

$$ 
\begin{aligned}
b_0 &= \arg \max_{b:s \le b < e} \|\tilde{Y}_{s,e}^b\|_H^2 \\
&= \arg \min_{b:s \le b < e} \min_{f_{s,e}^b \in \mathcal{F}_{s,e}^b} \|Y_{s,e} - f_{s,e}^b\|_{H,T}^2,
\end{aligned}
$$

où $Y_{s,e} = (Y_s, \dots, Y_e) \in \mathcal{H}^T$ ; $T = e - s + 1$ ; $\mathcal{F}_{s,e}^b$ est l'espace des vecteurs $u \in \mathcal{H}^T$ dont les coordonnées sont constantes sur chaque segment de la segmentation $(s-1, b, e)$.

Démonstration.

On remarque que, $\forall b \in [[s, e-1]]$,

$$ \min_{f_{s,e}^b \in \mathcal{F}_{s,e}^b} \|Y_{s,e} - f_{s,e}^b\|_{H,T}^2 = \|Y_{s,e} - \bar{Y}_{s,e}^b\|_{H,T}^2 = \|Y_{s,e}\|_{H,T}^2 - \|\bar{Y}_{s,e}^b\|_{H,T}^2, \quad (2.12) $$

où $\bar{Y}_{s,e}^b$ est la projection orthogonale de $Y_{s,e}$ sur $\mathcal{F}_{s,e}^b$. $\bar{Y}_{s,e}^b$ a pour expression (ARLOT, CELISSE et
HARCHAoui 2016) :

$$
\begin{aligned}
\| \bar{Y}_{s,e}^b \|_{\mathcal{H},T}^2 &= (b-s+1) \| \bar{Y}_{s,b} \|_{\mathcal{H}}^2 + (b-s+1) \| \bar{Y}_{b+1,e} \|_{\mathcal{H}}^2 \\
&= \frac{1}{b-s+1} \left\| \sum_{i=s}^{b} Y_i \right\|_{\mathcal{H}}^2 + \frac{1}{e-b} \left\| \sum_{i=b+1}^{e} Y_i \right\|_{\mathcal{H}}^2,
\end{aligned}
$$

où $\bar{Y}_{s,b}$ et $\bar{Y}_{b+1,e}$ sont les moyennes empiriques de $Y_{s,e}$ sur $[[s, b]]$ et $[[b+1, e]]$ respectivement.

Nous calculons $\|\tilde{Y}_{s,e}^b\|_H$ :

$$
\begin{aligned}
\tilde{Y}_{s,e}^b &= \sqrt{\frac{e-b}{T(b-s+1)}} \sum_{i=s}^{b} Y_i - \sqrt{\frac{b-s+1}{T(e-b)}} \sum_{i=b+1}^{e} Y_i \\
\Rightarrow \|\tilde{Y}_{s,e}^b\|_H^2 &= \frac{e-b}{T(b-s+1)} \left\| \sum_{i=s}^{b} Y_i \right\|_H^2 + \frac{b-s+1}{T(e-b)} \left\| \sum_{i=b+1}^{e} Y_i \right\|_H^2 - \frac{2}{T} \left\langle \sum_{i=s}^{b} Y_i, \sum_{i=b+1}^{e} Y_i \right\rangle_H.
\end{aligned}
$$

Nous remarquons que

$$
\begin{aligned}
\left\| \sum_{i=s}^{e} Y_i \right\|_{\mathcal{H}}^{2} &= \left\langle \sum_{i=s}^{b} Y_i + \sum_{i=b+1}^{e} Y_i, \sum_{i=s}^{b} Y_i + \sum_{i=b+1}^{e} Y_i \right\rangle_{\mathcal{H}} \\
&= \left\| \sum_{i=s}^{b} Y_i \right\|_{\mathcal{H}}^{2} + \left\| \sum_{i=b+1}^{e} Y_i \right\|_{\mathcal{H}}^{2} + 2 \left\langle \sum_{i=s}^{b} Y_i, \sum_{i=b+1}^{e} Y_i \right\rangle_{\mathcal{H}}.
\end{aligned}
$$

Par conséquent,

$$
\begin{aligned}
\| \tilde{Y}_{s,e}^b \|_{\mathcal{H}}^2 &= \frac{e-b}{T(b-s+1)} \left\| \sum_{i=s}^{b} Y_i \right\|_{\mathcal{H}}^2 + \frac{b-s+1}{T(e-b)} \left\| \sum_{i=b+1}^{e} Y_i \right\|_{\mathcal{H}}^2 - \frac{2}{T} \left\langle \sum_{i=s}^{b} Y_i, \sum_{i=b+1}^{e} Y_i \right\rangle_{\mathcal{H}} \\
&= \frac{e-b}{T(b-s+1)} \left\| \sum_{i=s}^{b} Y_i \right\|_{\mathcal{H}}^2 + \frac{b-s+1}{T(e-b)} \left\| \sum_{i=b+1}^{e} Y_i \right\|_{\mathcal{H}}^2 \\
&\quad + \frac{1}{T} \left\| \sum_{i=s}^{b} Y_i \right\|_{\mathcal{H}}^2 + \frac{1}{T} \left\| \sum_{i=b+1}^{e} Y_i \right\|_{\mathcal{H}}^2 - \frac{1}{T} \left\| \sum_{i=s}^{e} Y_i \right\|_{\mathcal{H}}^2 \\
&= \frac{1}{b-s+1} \left\| \sum_{i=s}^{b} Y_i \right\|_{\mathcal{H}}^2 + \frac{1}{e-b} \left\| \sum_{i=b+1}^{e} Y_i \right\|_{\mathcal{H}}^2 - \frac{1}{T} \left\| \sum_{i=s}^{e} Y_i \right\|_{\mathcal{H}}^2 \\
&= \| \bar{Y}_{s,e}^b \|_{\mathcal{H},T}^2 - \frac{1}{T} \left\| \sum_{i=s}^{e} Y_i \right\|_{\mathcal{H}}^2.
\end{aligned}
$$
D'après l'équation (2.12), nous obtenons

$$
\begin{align*}
\min_{f_{s,e}^b \in \mathcal{F}_{s,e}^b} \|Y_{s,e} - f_{s,e}^b\|_{\mathcal{H},T}^2 &= \|Y_{s,e} - \bar{Y}_{s,e}^b\|_{\mathcal{H},T}^2 \\
&= \|Y_{s,e}\|_{\mathcal{H},T}^2 - \|\bar{Y}_{s,e}^b\|_{\mathcal{H},T}^2 \\
&= \|Y_{s,e}\|_{\mathcal{H},T}^2 - \|\tilde{Y}_{s,e}^b\|_{\mathcal{H}}^2 - \frac{1}{T} \left\| \sum_{i=s}^{e} Y_i \right\|_{\mathcal{H}}^2.
\end{align*}
$$

Ainsi,

$$
\arg\max_{b:s\le b<e} \|\tilde{Y}_{s,e}^b\|_{\mathcal{H}}^2 = \arg\min_{b:s\le b<e} \min_{f_{s,e}^b \in \mathcal{F}_{s,e}^b} \|Y_{s,e} - f_{s,e}^b\|_{\mathcal{H},T}^2.
$$

□

**Lemme 2.5.1.** {Yᵢ}ᵢ∈[1,n] vérifie le modèle (1.3) et nous supposons vérifier les hypothèses du théorème 2.2.1. Alors, nous avons P(Bₙ) ≥ 1 - C₅n⁻¹, où

$$
\mathcal{B}_n = \left\{ \max_{s,b,e:1 \le s \le b < e \le n} \| \tilde{Y}_{s,e}^b - \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} \le \lambda_1 \right\},
$$

où $\lambda_1 \ge \sqrt{8 \log(n)}$, $C_5$ est une constante strictement positive et $\tilde{\mu}_{s,e}^b$ est défini par l'équation (2.8).

Démonstration. On remarque

$$
\begin{align*}
\omega \in \mathcal{B}_n &\Leftrightarrow \text{ pour } 1 \le s \le b < e \le n, \quad \|\tilde{\epsilon}_{s,e}^b\|_{\mathcal{H}} \le \lambda_1 \\
\Rightarrow \omega \in \mathcal{B}_n^c &\Leftrightarrow \exists (s,b,e) \in [1,n], \quad \|\tilde{\epsilon}_{s,e}^b\|_{\mathcal{H}} > \lambda_1
\end{align*}
$$

Alors,

$$
P(\mathcal{B}_n^c) \le \sum_{s,e,b=1}^{n} P(\|\tilde{\epsilon}_{s,e}^b\|_{\mathcal{H}} > \lambda_1)
$$

On remarque que $\tilde{\epsilon}_{s,e}^b \in \mathcal{H}$ est une variable aléatoire Gaussienne centrée et d'opérateur de covariance $\Sigma'$ car $\{\epsilon_i\}_{i \in [1,n]}$ sont des variables aléatoires Gaussiennes i.i.d. centrée et d'opérateur de covariance $\Sigma$. Nous montrons que $\Sigma = \Sigma'$.
En effet, $\forall h, h' \in \mathcal{H}$,

$$ 
\begin{align*}
\langle \Sigma' h, h' \rangle_{\mathcal{H}} \\
&= E \left[ \langle \tilde{\epsilon}_{s,e}^b, h \rangle_{\mathcal{H}} \langle \tilde{\epsilon}_{s,e}^b, h' \rangle_{\mathcal{H}} \right] \\
&= E \left[ \sum_{i,j=s}^{e} \left( \psi_{s,e}^b \right)_i \left( \psi_{s,e}^b \right)_j \langle \epsilon_i, h \rangle_{\mathcal{H}} \langle \epsilon_j, h' \rangle_{\mathcal{H}} \right] \quad \text{où } \tilde{\epsilon}_{s,e}^b = \sum_{i=s}^{e} \left( \psi_{s,e}^b \right)_i \epsilon_i \\
&= E \left[ \sum_{i=s}^{e} \left( \psi_{s,e}^b \right)_i^2 \langle \epsilon_i, h \rangle_{\mathcal{H}} \langle \epsilon_i, h' \rangle_{\mathcal{H}} \right] \quad \text{car } \{\epsilon_i\}_{i \in [1,n]} \text{ sont i.i.d.} \\
&= \langle \Sigma h, h' \rangle_{\mathcal{H}} \quad \text{car} \quad \sum_{i=s}^{e} \left( \psi_{s,e}^b \right)_i^2 = 1 \\
&\Rightarrow \Sigma = \Sigma'.
\end{align*}
$$

On a supposé que $\mathcal{H}$ est séparable donc $\mathcal{H}$ admet une base Hilbertienne $\{e_k\}_{k \in \mathbb{N}^*}$. On montre maintenant que $\Sigma$ est un opérateur de Hilbert Schmidt sur $\mathcal{H}$. En effet,

$$ 
\begin{align*}
\sum_{k=1}^{+\infty} \|\Sigma e_k\|_{\mathcal{H}}^2 &= \sum_{k=1}^{+\infty} \sum_{l=1}^{+\infty} \langle \Sigma e_k, e_l \rangle_{\mathcal{H}}^2 \\
\langle \Sigma e_k, e_l \rangle_{\mathcal{H}}^2 &= (E [ \langle \epsilon_i, e_k \rangle_{\mathcal{H}} \langle \epsilon_i, e_l \rangle_{\mathcal{H}} ] )^2 \\
&\le E [ \langle \epsilon_i, e_k \rangle_{\mathcal{H}}^2 ] E [ \langle \epsilon_i, e_l \rangle_{\mathcal{H}}^2 ] \quad \text{d'après l'inégalité de Cauchy-Schwarz} \\
\Rightarrow \sum_{k=1}^{+\infty} \sum_{l=1}^{+\infty} \langle \Sigma e_k, e_l \rangle^2 &\le \sum_{k=1}^{+\infty} E [ \langle \epsilon_i, e_k \rangle_{\mathcal{H}}^2 ] \sum_{l=1}^{+\infty} E [ \langle \epsilon_i, e_l \rangle_{\mathcal{H}}^2 ] \\
&\le \sum_{k=1}^{+\infty} \langle \Sigma e_k, e_k \rangle_{\mathcal{H}} \sum_{l=1}^{+\infty} \langle \Sigma e_l, e_l \rangle_{\mathcal{H}} \\
&\le (\text{Tr}\Sigma)^2 \\
&\le 1 < +\infty,
\end{align*}
$$

car on a supposé $\text{Tr}(\Sigma) = 1$.

Donc $\Sigma$ est un opérateur de Hilbert-Schmidt : en particulier, $\Sigma$ est un opérateur compact. Comme $\mathcal{H}$ est un espace de Hilbert séparable et $\Sigma$ est un opérateur compact auto-adjoint alors, d'après le théorème spectral, nous savons que $\Sigma$ admet des vecteurs propres $\{\phi_r\}_{r \in \mathbb{N}^*}$ avec des valeurs propres $\{v_r\}_{r \in \mathbb{N}^*}$. Alors,

$$ \| \tilde{\epsilon}_{s,e}^b \|_{\mathcal{H}}^2 = \sum_{r \in \mathbb{N}^*} \langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}}^2 $$

Ainsi, $\langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}} \sim \mathcal{N}(0, v_r)$ car $\text{var}(\langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}}) = \langle \Sigma \phi_r, \phi_r \rangle_{\mathcal{H}} = v_r$. De plus, pour $r \neq s$, $\text{cov}(\langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}}, \langle \tilde{\epsilon}_{s,e}^b, \phi_s \rangle_{\mathcal{H}}) = \langle \Sigma \phi_r, \phi_s \rangle = 0$ car $\{\phi_r\}_{r \in \mathbb{N}^*}$ est une base Hilbertienne. Donc comme $\text{cov}(\langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}}, \langle \tilde{\epsilon}_{s,e}^b, \phi_s \rangle_{\mathcal{H}}) = 0$ pour $r \neq s$ et $\langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}}$ est une variable Gaussienne pour $r \in \mathbb{N}^* \Rightarrow \forall r \in \mathbb{N}^*, \langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}}$ sont des variables aléatoires indépendantes.

**cas 1** : $v_1 = \sup_{r \in \mathbb{N}^*} v_r = 1$.

Come $\text{Tr}(\Sigma) = 1 \Rightarrow \forall r > 1$, $v_r = 0 \Rightarrow \langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}} \sim \mathcal{N}(0,0) \Rightarrow E[\langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_{\mathcal{H}}^2] = 0$. Alors, $\|\tilde{\epsilon}_{s,e}^b\|_{\mathcal{H}} =$
$|\langle \tilde{\epsilon}_{s,e}^b, \phi_1 \rangle_H| = |Z|$ presque sûrement où $Z \sim \mathcal{N}(0,1)$. Nous prouvons que $P(\|\tilde{\epsilon}_{s,e}^b\|_H > \lambda_1) \le \frac{C}{n^4}$ où $C$ est une constante positive.

$$
\begin{align*}
P(\|\tilde{\epsilon}_{s,e}^b\|_H > \lambda_1) &= P(|Z| \ge \lambda_1) \\
&= \frac{2}{\sqrt{2\pi}} \int_{\lambda_1}^{+\infty} e^{-\frac{x^2}{2}} dx \\
&= \frac{2}{\sqrt{2\pi}\lambda_1} \int_{\lambda_1}^{+\infty} \lambda_1 e^{-\frac{x^2}{2}} dx \\
&\le \frac{2}{\sqrt{2\pi}\lambda_1} \int_{\lambda_1}^{+\infty} x e^{-\frac{x^2}{2}} dx \\
&\le \frac{2}{\sqrt{2\pi}\lambda_1} \left[-e^{-\frac{x^2}{2}}\right]_{\lambda_1}^{+\infty} \\
&\le \frac{2}{\sqrt{2\pi}\lambda_1} e^{-\frac{\lambda_1^2}{2}} \\
&\le \frac{2}{\sqrt{2\pi}\lambda_1} \frac{1}{n^4} \operatorname{car} \lambda_1 \ge \sqrt{8 \log(n)} \\
&\le \frac{2}{\sqrt{2\pi}\sqrt{8 \log(2)}} \frac{1}{n^4} \operatorname{car} n \ge 2
\end{align*}
$$

cas 2 : $v_1 = \sup_{r \in \mathbb{N}^*} v_r < 1$.

Nous prouvons que $P(\|\tilde{\epsilon}_{s,e}^b\|_H > \lambda_1) \le \frac{C}{n^4}$ où $C$ est une constante positive.

$$
\begin{align*}
& P(\|\tilde{\epsilon}_{s,e}^b\|_H > \lambda_1) \\
&= P\left(\frac{1}{2} \|\tilde{\epsilon}_{s,e}^b\|_H^2 > \frac{1}{2} \lambda_1^2\right) \\
&\le \frac{E\left[e^{\frac{1}{2} \|\tilde{\epsilon}_{s,e}^b\|_H^2}\right]}{e^{\frac{1}{2} \lambda_1^2}} \text{ d'après l'inégalité de Markov} \\
&\le \frac{E\left[e^{\frac{1}{2} \sum_{r \in \mathbb{N}^*} \langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_H^2}\right]}{n^4} \operatorname{car} \lambda_1 \ge \sqrt{8 \log(n)}
\end{align*}
$$

Afin de prouver $P(\|\tilde{\epsilon}_{s,e}^b\|_H > \lambda_1) \le \frac{C}{n^4}$, il est suffisant de prouver $E\left[e^{\frac{1}{2} \sum_{r \in \mathbb{N}^*} \langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_H^2}\right] \le C$. Soit
I= {r ∈ $\mathbb{N}^*$ : $v_r \neq 0$}. Nous remarquons que, si $r \in \mathbb{I}^c$, $\langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_H = 0$ presque sûrement.

$$
\begin{align*}
E \left[ e^{\frac{1}{2} \sum_{r \in \mathbb{N}^*} \langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_H^2} \right] &= \prod_{r \in \mathbb{N}^*} E \left[ e^{\frac{1}{2} \langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_H^2} \right] \\
&= \prod_{r \in \mathbb{I}} E \left[ e^{\frac{v_r}{2} \left( \frac{\langle \tilde{\epsilon}_{s,e}^b, \phi_r \rangle_H}{\sqrt{v_r}} \right)^2} \right] \\
&= \prod_{r \in \mathbb{I}} (1 - v_r)^{-1/2} \\
&= e^{\frac{1}{2} \sum_{r \in \mathbb{I}} \log\left(\frac{1}{1-v_r}\right)} \\
&\le e^{\frac{1}{2} \sum_{r \in \mathbb{I}} \left(\frac{1}{1-v_r} - 1\right)} \quad \text{car } \forall x \ge 1, \log(x) \le x - 1 \\
&\le e^{\frac{1}{2} \sum_{r \in \mathbb{I}} \left(\frac{v_r}{1-v_r}\right)} \\
&\le e^{\frac{1}{2} \sum_{r \in \mathbb{N}^*} \frac{Tr(\Sigma)}{1-v_1}} \quad \text{où } v_1 = \sup_{r \in \mathbb{N}^*} v_r < 1.
\end{align*}
$$

□

**Lemme 2.5.2.** Nous définissons $\mathcal{A}_n$

$$
\mathcal{A}_n = \left\{ \left\| \frac{1}{\sqrt{e-b+1}} \sum_{i=b}^{e} \epsilon_i \right\|_{\mathcal{H}} < \lambda_2, \forall 1 \le b \le e \le n \right\},
$$

où $\lambda_2 \ge \sqrt{6\log(n)}$. Alors, $P(\mathcal{A}_n) \ge 1 - C_6 n^{-1}$ où $C_6$ est une constante positive.

Démonstration. Nous remarquons que :

$$
\begin{align*}
w \in \mathcal{A}_n &\Leftrightarrow \text{ pour } 1 \le b \le e \le n, \quad \left\| \frac{1}{\sqrt{e-b+1}} \sum_{i=b}^{e} \epsilon_i \right\|_{\mathcal{H}} < \lambda_2 \\
\Rightarrow w \in \mathcal{A}_n^c &\Leftrightarrow \exists b, e \in [1, n], \quad \left\| \frac{1}{\sqrt{e-b+1}} \sum_{i=b}^{e} \epsilon_i \right\|_{\mathcal{H}} \ge \lambda_2.
\end{align*}
$$

Ainsi,

$$
P(\mathcal{A}_n^c) \le \sum_{b,e=1}^{n} P\left(\left\| \frac{1}{\sqrt{e-b+1}} \sum_{i=b}^{e} \epsilon_i \right\|_{\mathcal{H}} \ge \lambda_2\right).
$$

Soit $V = \frac{1}{\sqrt{e-b+1}} \sum_{i=b}^{e} \epsilon_i$. Comme $\{\epsilon_i\}_{i \in [1,n]}$ sont des variables aléatoires i.i.d. Gaussiennes centrées d'opérateur de covariance $\Sigma$ alors $V$ est une variable aléatoire Gaussienne centrée d'opérateur de
covariance $\Sigma'$. On montre que $\Sigma = \Sigma', \forall h, h' \in \mathcal{H}$,

$$ 
\begin{align*}
\langle \Sigma' h, h' \rangle_{\mathcal{H}} \\
&= E[\langle V, h \rangle_{\mathcal{H}} \langle V, h' \rangle_{\mathcal{H}}] \\
&= \frac{1}{e-b+1} E\left[\left\langle \sum_{i=b}^{e} \epsilon_i, h \right\rangle_{\mathcal{H}} \left\langle \sum_{j=b}^{e} \epsilon_j, h' \right\rangle_{\mathcal{H}}\right] \\
&= \frac{1}{e-b+1} \sum_{i,j=b}^{e} E\left[\left\langle \epsilon_i, h \right\rangle_{\mathcal{H}} \left\langle \epsilon_j, h' \right\rangle_{\mathcal{H}}\right] \\
&= \frac{1}{e-b+1} \sum_{i=b}^{e} E\left[\left\langle \epsilon_i, h \right\rangle_{\mathcal{H}} \left\langle \epsilon_i, h' \right\rangle_{\mathcal{H}}\right] \quad \text{car } \{\epsilon_i\}_{i \in \llbracket 1, n \rrbracket} \text{ sont i.i.d et centrées} \\
&= \langle \Sigma h, h' \rangle_{\mathcal{H}} \\
&\Rightarrow \Sigma = \Sigma'.
\end{align*}
$$

D'après le lemme 2.5.1, on sait que $\Sigma$ admet une base hilbertienne de vecteurs propres $\{\phi_r\}_{r \in \mathbb{N}^*}$ associés aux valeurs propres $\{v_r\}_{r \in \mathbb{N}^*}$. Ainsi, $\|V\|_{\mathcal{H}}^2$ s'écrit

$$ \|V\|_{\mathcal{H}}^2 = \sum_{r \in \mathbb{N}^*} \langle V, \phi_r \rangle_{\mathcal{H}}^2 $$

On remarque que $\langle V, \phi_r \rangle_{\mathcal{H}} \sim \mathcal{N}(0, v_r)$ car var($\langle V, \phi_r \rangle_{\mathcal{H}}$) = $\langle \Sigma \phi_r, \phi_r \rangle_{\mathcal{H}} = v_r$. De plus, pour $r \neq s$, cov($\langle V, \phi_r \rangle_{\mathcal{H}} \langle V, \phi_s \rangle_{\mathcal{H}}$) = $\langle \Sigma \phi_r, \phi_s \rangle_{\mathcal{H}} = 0$. Donc, comme pour $r \neq s$, cov($\langle V, \phi_r \rangle_{\mathcal{H}} \langle V, \phi_s \rangle_{\mathcal{H}}$) = 0 et $\forall r \in \mathbb{N}^*, \langle V, \phi_r \rangle_{\mathcal{H}}$ sont des variables aléatoires Gaussiennes $\Rightarrow \{\langle V, \phi_r \rangle_{\mathcal{H}}\}_{r \in \mathbb{N}^*}$ sont indépendantes. Deux cas peuvent se produire :

**Cas 1 :** $v_1 = \sup_{r \in \mathbb{N}^*} v_r = 1$

Comme Tr($\Sigma$) = 1 $\Rightarrow \forall r > 1$, $v_r = 0 \Rightarrow E[\langle V, \phi_r \rangle_{\mathcal{H}}^2] = 0 \Rightarrow \langle V, \phi_r \rangle_{\mathcal{H}} = 0$ presque sûrement. Donc $\|V\|_{\mathcal{H}} = |\langle V, \phi_1 \rangle_{\mathcal{H}}| = |Z|$ presque sûrement où $Z \sim \mathcal{N}(0,1)$. De la même manière qu'au lemme 2.5.1, on aboutit au résultat.

**Cas 2 :** $v_1 = \sup_{r \in \mathbb{N}^*} v_r < 1$

D'après l'inégalité de Markov,

$$ P(\|V\|_{\mathcal{H}} \ge \lambda_2) = P\left(\frac{1}{2} \|V\|_{\mathcal{H}}^2 \ge \frac{1}{2} \lambda_2^2\right) \le \frac{E\left[e^{\frac{1}{2} \|V\|_{\mathcal{H}}^2}\right]}{e^{\frac{\lambda_2^2}{2}}} \le \frac{E\left[e^{\frac{1}{2} \|V\|_{\mathcal{H}}^2}\right]}{n^3}, $$

car $\lambda_2 \ge \sqrt{6 \log(n)}$. Il suffit de montrer que $E\left[e^{\frac{1}{2} \|V\|_{\mathcal{H}}^2}\right]$ est majoré par une constante pour aboutir au résultat. On pose $I = \{r \in \mathbb{N}^* : v_r \neq 0\}$. On majore $E\left[e^{\frac{1}{2} \|V\|_{\mathcal{H}}^2}\right]$ :

$$ E\left[e^{\frac{1}{2} \|V\|_{\mathcal{H}}^2}\right] = \prod_{r \in \mathbb{N}^*} E\left[e^{\frac{1}{2} \langle V, \phi_r \rangle_{\mathcal{H}}^2}\right] = \prod_{r \in I} E\left[e^{\frac{1}{2} \langle V, \phi_r \rangle_{\mathcal{H}}^2}\right] = \prod_{r \in I} E\left[e^{\frac{v_r}{2} \left( \frac{\langle V, \phi_r \rangle_{\mathcal{H}}}{\sqrt{v_r}} \right)^2}\right] = \prod_{r \in I} (1 - v_r)^{-1/2}. $$

On procède ensuite comme dans le lemme 2.5.1 pour aboutir au résultat. $\square$

<figure><img src="image_17.png" /></figure>
**Lemme 2.5.3.** {Yᵢ}ᵢ∈[1,n] vérifie le modèle (1.3). On suppose les hypothèses du théorème 2.2.1 vérifiées. De plus, on suppose que (2.9), (2.10), (2.11) sont vraies. Sur l'événement B_n du lemme 2.5.1, pour b₀ = arg max b:s≤b<b:e ||Ỹ_{s,e}ᵇ||_H, il existe r ∈ [1, q] tel que pour n au voisinage de +∞, |b₀ - τᵢ₀+r*| ≤ C₈γₙ où γₙ = n¹/²λ₁/μ'ᵢ₀+r. De plus, b ↦ ||μ̃_{s,e}ᵇ||_H atteint un maximum local au point b = τᵢ₀+r* et nous avons

$$ \frac{\left\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}} \right\|_{\mathcal{H}}}{\max_{b:s \le b < e} \left\| \tilde{\mu}_{s,e}^{b} \right\|_{\mathcal{H}}} \ge C_9, $$

où C₈, C₉ sont des constantes positives.

Démonstration.

**Pour le premier point**

Nous définissons b₁ = arg max b:s≤b<b:e ||μ̃_{s,e}ᵇ||_H. D'après le lemme 2.5.1, nous obtenons

$$ \| \tilde{\mu}_{s,e}^{b_1} \|_{\mathcal{H}} \le \| \tilde{Y}_{s,e}^{b_1} \|_{\mathcal{H}} + \lambda_1 \le \| \tilde{Y}_{s,e}^{b_0} \|_{\mathcal{H}} + \lambda_1 \le \| \tilde{\mu}_{s,e}^{b_0} \|_{\mathcal{H}} + 2\lambda_1. \quad (2.13) $$

Nous supposons par l'absurde que b₀ ∈ [τᵢ₀+i* + C₈γₙ, τᵢ₀+i* + C₈γₙ] pour i ∈ [1, q - 1]. D'après le lemme 2.5.8, on sait que ∀b ∈ [s, e - 1], μ̃_{s,e}ᵇ = 1/√T g(b - (b-s+1)/T) (g est défini dans le lemme 2.5.8 et la propriété 2.5.2). D'après les propriétés 2.5.2, x ↦ ||g(x)||²_H est strictement convexe sur [aᵢ, aᵢ+1] pour i ∈ [1, q - 1].

Par conséquent, b ↦ ||μ̃_{s,e}ᵇ||_H est strictement monotone ou décroît puis croît sur [τᵢ₀+i*, τᵢ₀+i*] pour i ∈ [1, q - 1].

Deux cas peuvent se produire :

**Cas 1 :**

Si b ↦ ||μ̃_{s,e}ᵇ||_H décroît dans un voisinage de b₀. Nous définissons b' tel que b' - τᵢ₀+i* = C₈γₙ. En tenant compte des variations de b ↦ ||μ̃_{s,e}ᵇ||_H et τᵢ₀+i* < b' < b₀, alors ||μ̃_{s,e}τᵢ₀+i*||_H > ||μ̃_{s,e}ᵇ||_H > ||μ̃_{s,e}ᵇ||_H. D'après le lemme 2.5.7, comme |b' - τᵢ₀+i*| = C₈γₙ (où C₈ est aussi grand que l'on veut car γₙ = o(δₙ)), nous obtenons

$$ \begin{align*} \left\| \tilde{\mu}_{s,e}^{\tau_{i_0+i}} \right\|_{\mathcal{H}} - \left\| \tilde{\mu}_{s,e}^{b'} \right\|_{\mathcal{H}} & \ge \frac{|b' - \tau_{i_0+i}^*|}{\sqrt{2}\delta_n} \left\| \tilde{\mu}_{s,e}^{\tau_{i_0+i}^*} \right\|_{\mathcal{H}} \\ & \ge C' \frac{|b' - \tau_{i_0+i}^*|}{\sqrt{2n}} \\ & \ge C' C_8 \frac{\lambda_1}{\sqrt{2}\mu'_{i_0+i}} \operatorname{car} |b' - \tau_{i_0+i}^*| = C_8 \frac{\lambda_1 \sqrt{n}}{\mu_{i_0+r}} \\ & \ge \frac{C_8 C'}{2\sqrt{2M}} \lambda_1, \end{align*} $$

car ||μ̃_{s,e}τᵢ₀+r*||_H ≥ C' δₙ/√n en utilisant des arguments similaires au lemme 1 (CHO et FRYZLEWICZ 2012).
$\frac{C_8 C'}{2\sqrt{2M}}$ peut être pris plus grand que 2 car $C_8$ peut être pris aussi grand que l'on veut.

Ainsi, $\|\tilde{\mu}_{s,e}^{\tau_{i_0+i}^*}\|_{\mathcal{H}} \ge \|\tilde{\mu}_{s,e}^{b'}\|_{\mathcal{H}} + 2\lambda_1 \Rightarrow \|\tilde{\mu}_{s,e}^{b_1}\|_{\mathcal{H}} > \|\tilde{\mu}_{s,e}^{b_0}\|_{\mathcal{H}} + 2\lambda_1$. Cette dernière inégalité contredit l'inégalité (2.13). On obtient le résultat avec $r = i \in [1, q-1]$.

**Cas 2 :**

Si $b \mapsto \|\tilde{\mu}_{s,e}^b\|_{\mathcal{H}}$ croît dans un voisinage de $b_0$. Nous définissons $\tau_{i_0+i+1}^* - b' = C_8\gamma_n$. En tenant compte des variations de $b \mapsto \|\tilde{\mu}_{s,e}^b\|_{\mathcal{H}}$ et $b_0 < b' < \tau_{i_0+i+1}^*$, alors $\|\tilde{\mu}_{s,e}^{\tau_{i_0+i+1}^*}\|_{\mathcal{H}} > \|\tilde{\mu}_{s,e}^{b'}\|_{\mathcal{H}} > \|\tilde{\mu}_{s,e}^{b_0}\|_{\mathcal{H}}$. D'après le lemme 2.5.7, comme $|b' - \tau_{i_0+i+1}^*| = C_8\gamma_n$), nous obtenons :

$$ \begin{aligned} \left\| \tilde{\mu}_{s,e}^{\tau_{i_0+i+1}^*} \right\|_{\mathcal{H}} - \left\| \tilde{\mu}_{s,e}^{b'} \right\|_{\mathcal{H}} & \ge \frac{|b' - \tau_{i_0+i+1}^*|}{\sqrt{2}\delta_n} \left\| \tilde{\mu}_{s,e}^{\tau_{i_0+i+1}^*} \right\|_{\mathcal{H}} \\ & \ge \frac{C_8 C'}{2\sqrt{2M}} \lambda_1 \operatorname{car} |b' - \tau_{i_0+i+1}^*| = C_8 \gamma_n. \end{aligned} $$

Ainsi, $\|\tilde{\mu}_{s,e}^{\tau_{i_0+i}^*}\|_{\mathcal{H}} \ge \|\tilde{\mu}_{s,e}^{b'}\|_{\mathcal{H}} + 2\lambda_1 \Rightarrow \|\tilde{\mu}_{s,e}^{b_1}\|_{\mathcal{H}} > \|\tilde{\mu}_{s,e}^{b_0}\|_{\mathcal{H}} + 2\lambda_1$. Cette dernière inégalité contredit l'inégalité (2.13). On obtient le résultat avec $r = i+1 \in [2, q]$.

$$ \text{Ainsi } |b - \tau_{i_0+r}^*| \le C_8 \gamma_n. $$

**Pour le deuxième point**

Si $b \mapsto \|\tilde{\mu}_{s,e}^b\|_{\mathcal{H}}$ n'admet pas de maximum local en $b = \tau_{i_0+r}^*$. D'après la propriété 2.5.3 et les variations de $x \mapsto \|g(x)\|_{\mathcal{H}}^2$ sur $[a_i, a_{i+1}]$ pour $i \in [0, q]$, $\|\tilde{\mu}_{s,e}^{b_2}\|_{\mathcal{H}} = \max(\|\tilde{\mu}_{s,e}^{\tau_{i_0+r-1}^*}\|_{\mathcal{H}}, \|\tilde{\mu}_{s,e}^{\tau_{i_0+r+1}^*}\|_{\mathcal{H}}) > \|\tilde{\mu}_{s,e}^{\tau_{i_0+r}^*}\|_{\mathcal{H}}$. Sans perte de généralité, $\tau_{b_2}^* = \tau_{i_0+r-1}^*$. Comme $b \mapsto \|\tilde{\mu}_{s,e}^b\|_{\mathcal{H}}$ admet un maximum en $t = \tau_{b_2}^*$ sur $[\tau_{i_0+r-1}^*, \tau_{i_0+r+1}^*]$, donc $\|\tilde{\mu}_{s,e}^{\tau_{b_2}^*}\|_{\mathcal{H}} > \|\tilde{\mu}_{s,e}^{b'}\|_{\mathcal{H}} > \|\tilde{\mu}_{s,e}^{b_0}\|_{\mathcal{H}}$ où $b' = \tau_{b_2}^* + C_8\gamma_n$. Comme pour le premier point, on aboutit à une contradiction avec l'inégalité (2.13).

**Pour le troisième point**

En utilisant la même argumentation si $\|\tilde{\mu}_{s,e}^{\tau_{i_0+r}^*}\|_{\mathcal{H}}/\max_{b:s \le b<e} \|\tilde{\mu}_{s,e}^b\|_{\mathcal{H}}$ n'est pas minoré alors $b_0$ sera situé dans un voisinage du point de maximum de $b \mapsto \|\tilde{\mu}_{s,e}^b\|_{\mathcal{H}}$. Ce qui aboutit à une contradiction avec le fait que $b_0$ est situé dans un voisinage de $\tau_{i_0+r}^*$.

**Lemme 2.5.4.** On suppose les hypothèses du lemme 2.5.3 vraies. Alors, avec les notations du lemme 2.5.3, sur l'événement $B_n \cap A_n$, nous obtenons pour n appartenant à un voisinage de $+\infty$, $|b_0 - \tau_{i_0+r}^*| \le C_4\epsilon_n$, avec $\epsilon_n = \lambda_2^2 n^2 \delta_n^{-2} \mu_n^{-2}$.

Démonstration.

D'après la propriété 2.5.1,

$$ \begin{aligned} \arg\max_{b:s \le b<e} \|\tilde{v}_{s,e}^b\|_{\mathcal{H}} &= \arg\min_{b:s \le b<e} \min_{v_{s,e}^b \in \mathcal{F}_{s,e}^b} \|v_s^e - v_{s,e}^b\|_{\mathcal{H}^n}^2 \\ &= \arg\min_{b:s \le b<e} \|v_s^e - \bar{v}_{s,e}^b\|_{\mathcal{H}^n}^2, \end{aligned} $$
où $\overline{v}_{s,e}^b$ est la projection orthogonal de $v_s^e = (v_s, \dots, v_e)$ sur $\mathcal{F}_{s,e}^b$.
Alors,

$$ \sum_{i=s}^{e} \| Y_i - \overline{Y}_{s,e,i}^{b_0} \|_{\mathcal{H}}^2 \le \sum_{i=s}^{e} \| Y_i - \bar{\mu}_{s,e,i}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}^2. $$

Le reste de la preuve a pour but de prouver l'inégalité

$$ \sum_{i=s}^{e} \| Y_i - \overline{Y}_{s,e,i}^{d} \|_{\mathcal{H}}^2 > \sum_{i=s}^{e} \| Y_i - \bar{\mu}_{s,e,i}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}^2, \quad (2.14) $$

sous la condition $\epsilon_n < |d - \tau_{i_0+r}^*| < C_8\gamma_n$. On en déduira nécessairement que $|b_0 - \tau_{i_0+r}^*| \le \epsilon_n$.
L'inégalité (2.14) est équivalente à l'inégalité (2.15) :

$$ \begin{aligned} & \sum_{i=s}^{e} \| Y_i - \overline{Y}_{s,e,i}^{d} \|_{\mathcal{H}}^2 > \sum_{i=s}^{e} \| Y_i - \bar{\mu}_{s,e,i}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}^2 \\ \Leftrightarrow & \sum_{i=s}^{e} \| Y_i - \mu_i + \mu_i - \overline{Y}_{s,e,i}^{d} \|_{\mathcal{H}}^2 > \sum_{i=s}^{e} \| Y_i - \mu_i + \mu_i - \bar{\mu}_{s,e,i}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}^2 \\ \Leftrightarrow & \sum_{i=s}^{e} \| \mu_i - \overline{Y}_{s,e,i}^{d} \|_{\mathcal{H}}^2 - \sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}^2 > 2 \sum_{i=s}^{e} \langle \epsilon_i, (\overline{Y}_{s,e,i}^{d} - \bar{\mu}_{s,e,i}^{\tau_{i_0+r}^*}) \rangle_{\mathcal{H}} \end{aligned} \quad (2.15) $$

L'inégalité (2.15) est une conséquence de l'inégalité (2.16) :

$$ \sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^{d} \|_{\mathcal{H}}^2 - \sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}^2 > 2 \sum_{i=s}^{e} \langle \epsilon_i, (\overline{Y}_{s,e,i}^{d} - \bar{\mu}_{s,e,i}^{\tau_{i_0+r}^*}) \rangle_{\mathcal{H}}, \quad (2.16) $$

$$ \text{car } \sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^{d} \|_{\mathcal{H}}^2 \le \sum_{i=s}^{e} \| \mu_i - \overline{Y}_{s,e,i}^{d} \|_{\mathcal{H}}^2. $$

Nous avons à déterminer pour quelles valeurs de $\epsilon_n$ l'équation (2.16) est valide pour prouver l'inégalité (2.14). Un calcul donne

$$ \begin{aligned} \sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^{d} \|_{\mathcal{H}}^2 &= \| \mu - \bar{\mu}_{s,e}^{d} \|_{\mathcal{H},T}^2 \\ &= \| \mu_s^e \|_{\mathcal{H},T}^2 - \| \bar{\mu}_{s,e}^{d} \|_{\mathcal{H},T}^2 \\ &= \| \mu_s^e \|_{\mathcal{H},T}^2 - \left[ \| \tilde{\mu}_{s,e}^{d} \|_{\mathcal{H}}^2 + \frac{1}{T} \left\| \sum_{i=s}^{e} \mu_i \right\|_{\mathcal{H}}^2 \right], \end{aligned} $$
où $\mu_s^e = (\mu_s, \dots, \mu_e) \in \mathcal{H}^T$. De plus,

$$
\begin{align*}
& \sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^d \|_{\mathcal{H}}^2 - \sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^*} \|_{\mathcal{H}}^2 \\
&= \| \tilde{\mu}_{s,e}^{\tau_{i0+r}^*} \|_{\mathcal{H}}^2 - \| \tilde{\mu}_{s,e}^d \|_{\mathcal{H}}^2 \\
&= \left( \| \tilde{\mu}_{s,e}^{\tau_{i0+r}^*} \|_{\mathcal{H}} - \| \tilde{\mu}_{s,e}^d \|_{\mathcal{H}} \right) \left( \| \tilde{\mu}_{s,e}^{\tau_{i0+r}^*} \|_{\mathcal{H}} + \| \tilde{\mu}_{s,e}^d \|_{\mathcal{H}} \right) \\
&\geq \left( \| \tilde{\mu}_{s,e}^{\tau_{i0+r}^*} \|_{\mathcal{H}} - \| \tilde{\mu}_{s,e}^d \|_{\mathcal{H}} \right) \| \tilde{\mu}_{s,e}^{\tau_{i0+r}^*} \|_{\mathcal{H}}. \tag{2.17}
\end{align*}
$$

Comme $|d - \tau_{i_0+r}^*| \le C_8 \gamma_n$ et $\|\tilde{\mu}_{s,e}^{\tau_{i_0+r}^*}\|_H$ est un maximum local de $b \mapsto \|\tilde{\mu}_{s,e}^b\|_H$ d'après le lemme 2.5.3, nous pouvons utiliser le lemme 2.5.7 et nous obtenons

$$
\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} - \| \tilde{\mu}_{s,e}^d \|_{\mathcal{H}} \geq \frac{|d - \tau_{i_0+r}^*|}{\sqrt{2}\delta_n} \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}
$$

De plus, d'après le lemme 2.5.8 et la dernière assertion du lemme 2.5.3, nous obtenons

$$
\begin{align*}
\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}
& \ge C_9 \max_{b:s \le b < e} \| \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} \\
& \ge \frac{C_9}{2} \delta_n n^{-1/2} \mu_{i_0+r}^{\prime}.
\end{align*}
$$

Par conséquent,

$$
\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} - \| \tilde{\mu}_{s,e}^d \|_{\mathcal{H}} \geq \frac{C_9}{2\sqrt{2}} |d - \tau_{i_0+r}^*| n^{-1/2} \mu_{i_0+r}^{\prime}.
$$

Ainsi, d'après l'inégalité (2.17), nous obtenons

$$
\sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^d \|_{\mathcal{H}}^2 - \sum_{i=s}^{e} \| \mu_i - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^*} \|_{\mathcal{H}}^2 \geq \frac{C_9^2}{4\sqrt{2}} |d - \tau_{i0+r}^*| \delta_n \frac{(\mu_{i0+r}^{\prime})^2}{n}.
$$

Nous décomposons le terme de droite de l'inégalité (2.16).

$$
\begin{align}
& 2 \sum_{i=s}^{e} \langle \epsilon_i, (\bar{Y}_{s,e,i}^d - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^*}) \rangle_{\mathcal{H}} \nonumber \\
&= 2 \sum_{i=s}^{e} \langle \epsilon_i, (\bar{Y}_{s,e,i}^d - \bar{\mu}_{s,e,i}^d) \rangle_{\mathcal{H}} + 2 \sum_{i=s}^{e} \langle \epsilon_i, (\bar{\mu}_{s,e,i}^d - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^*}) \rangle_{\mathcal{H}}. \tag{2.18}
\end{align}
$$

Sans perte de généralité, nous supposons $d \ge \tau_{i_0+r}^*$. Le second terme de l'équation (2.18) peut se
décomposer de la manière suivante

$$
\begin{align}
& \sum_{i=s}^{e} \langle \epsilon_i, (\bar{\mu}_{s,e,i}^d - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^*}) \rangle_{\mathcal{H}} \nonumber \\
&= \sum_{i=s}^{\tau_{i0+r}^*} \langle \epsilon_i, (\bar{\mu}_{s,e,i}^d - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^*}) \rangle_{\mathcal{H}} \tag{2.19}
\end{align}
$$

$$
+ \sum_{i=\tau_{i0+r}^*+1}^{d} \langle \epsilon_i, (\bar{\mu}_{s,e,i}^d - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^*}) \rangle_{\mathcal{H}} \quad (2.20)
$$

$$
+ \sum_{i=d+1}^{e} \langle \epsilon_i, (\bar{\mu}_{s,e,i}^{d} - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^{*}}) \rangle_{\mathcal{H}} \quad (2.21)
$$

Le terme (2.19) peut être majoré de la manière suivante. D'après l'inégalité de Cauchy-Schwarz,

$$
\begin{align*}
& \left| \sum_{i=s}^{\tau_{i0+r}^*} \langle \epsilon_i, (\bar{\mu}_{s,e,i}^d - \bar{\mu}_{s,e,i}^{\tau_{i0+r}^*}) \rangle_{\mathcal{H}} \right| \\
&\le \sqrt{\tau_{i0+r}^* - s + 1} \left\| \frac{1}{\sqrt{\tau_{i0+r}^* - s + 1}} \sum_{i=s}^{\tau_{i0+r}^*} \epsilon_i \right\|_{\mathcal{H}} \left\| \frac{1}{d-s+1} \sum_{i=s}^{d} \mu_i - \frac{1}{\tau_{i0+r}^* - s + 1} \sum_{i=s}^{\tau_{i0+r}^*} \mu_i \right\|_{\mathcal{H}} \\
&\le \sqrt{\tau_{i0+r}^* - s + 1} \lambda_2 \frac{|d - \tau_{i0+r}^*|}{\tau_{i0+r}^* - s + 1} \\
&\le C_{10} \lambda_2 |d - \tau_{i0+r}^*| \mu_{i0+r}^{\prime} (\delta_n)^{-1/2}
\end{align*}
$$

Les termes (2.20) et (2.21) peuvent être majorés de la même manière par $C_{11} \lambda_2 |d - \tau_{i0+r}^*|^{1/2} \mu_{i0+r}^{\prime}$ et $C_{12} \lambda_2 |d - \tau_{i0+r}^*| \mu_{i0+r}^{\prime} (\delta_n)^{-1/2}$ respectivement.

Le premier terme de l'équation (2.18) peut se décomposer de la manière suivante

$$
\begin{align}
& \sum_{i=s}^{e} \langle \epsilon_i, (\bar{Y}_{s,e,i}^d - \bar{\mu}_{s,e,i}^d) \rangle_{\mathcal{H}} \nonumber \\
&= \sum_{i=s}^{d} \langle \epsilon_i, (\bar{Y}_{s,e,i}^d - \bar{\mu}_{s,e,i}^d) \rangle_{\mathcal{H}} \tag{2.22}
\end{align}
$$

$$
+ \sum_{i=d+1}^{e} \langle \epsilon_i, (\bar{Y}_{s,e,i}^d - \bar{\mu}_{s,e,i}^d) \rangle_{\mathcal{H}} \quad (2.23)
$$
Le terme (2.22) est égal à

$$
\begin{align*}
\sum_{i=s}^{d} \langle \epsilon_i, (\bar{Y}_{s,e,i}^d - \bar{\mu}_{s,e,i}^d) \rangle_{\mathcal{H}} &= \sum_{i=s}^{d} \langle \epsilon_i, \bar{\epsilon}_{s,e,i}^d \rangle_{\mathcal{H}} \\
&= \frac{1}{d-s+1} \left\| \sum_{i=s}^{d} \epsilon_i \right\|_{\mathcal{H}}^2 \\
&\le \lambda_2^2.
\end{align*}
$$

Le terme (2.23) est majoré par $\lambda_2^2$ de la même manière. Ainsi, l'inégalité (2.16) est valide si l'inégalité (2.24) est vraie

$$
\begin{align}
\frac{C_9^2}{4\sqrt{2}} |d - \tau_{i_0+r}^*| \delta_n n^{-1} (\mu_{i_0+r}')^2 &\ge C_{13} \max \left( \lambda_2 |d - \tau_{i_0+r}^*| \delta_n^{-1/2} \mu_{i_0+r}', \lambda_2 |d - \tau_{i_0+r}^*|^{1/2} \mu_{i_0+r}', \lambda_2^2 \right) \nonumber \\
\Rightarrow \quad |d - \tau_{i_0+r}^*| \delta_n n^{-1} (\mu_{i_0+r}')^2 &\ge C_{14} \max \left( \lambda_2 |d - \tau_{i_0+r}^*| \delta_n^{-1/2} \mu_{i_0+r}', \lambda_2 |d - \tau_{i_0+r}^*|^{1/2} \mu_{i_0+r}', \lambda_2^2 \right), \tag{2.24}
\end{align}
$$

où $C_{13}$ est défini par $C_{13} = \max\{C_{10}, C_{11}, C_{12}, 1\}; C_{14} = \frac{4\sqrt{2}C_{13}}{C_9^2}$. L'équation (2.24) entraîne

$$
\delta_n \geq (C_{14} \lambda_2 n / \mu_{i_0+r}')^{2/3} \quad (2.25)
$$

$$
|d - \tau_{i_0+r}^*| \ge C_{14} \lambda_2^2 n^2 (\delta_n \mu_{i_0+r}')^{-2} \quad (2.26)
$$

$$
|d - \tau_{i_0+r}^*| \ge C_{14} \lambda_2^2 n \delta_n^{-1} (\mu_{i_0+r}')^{-2} \quad (2.27)
$$

L'inégalité (2.27) est une conséquence de l'inégalité (2.26) car :

$$
\begin{align*}
C_{14}^2 \lambda_2^2 n^2 (\delta_n \mu_{i_0+r}')^{-2} &\ge C_{14} \lambda_2^2 n \delta_n^{-1} (\mu_{i_0+r}')^{-2} \\
&\Leftrightarrow C_{14}^2 n \delta_n^{-1} \ge C_{14} \\
&\Leftrightarrow C_{14}^2 n \ge C_{14} \delta_n.
\end{align*}
$$

$C_{14}^2 n \geq C_{14} \delta_n \text{ est vraie si } C_{14} \geq 1.$

L'inégalité (2.25) est une conséquence de l'inégalité (2.26) et de l'hypothèse $|d - \tau_{i_0+r}^*| \le C_8 \gamma_n$
car :

$$
\begin{align*}
& C_{14}^{1/2} C_8^{-1/2} \lambda_2 \lambda_1^{-1/2} n^{3/4} (\mu_{i_0+r}')^{-1/2} \ge (C_{14} \lambda_2 n / \mu_{i_0+r}')^{2/3} \\
& \Leftrightarrow \lambda_2^{1/3} \lambda_1^{-1/2} (\mu_{i_0+r}')^{2/3-1/2} \ge C_{14}^{1/6} C_8^{1/2} n^{2/3-3/4} \\
& \Leftrightarrow \lambda_2^{1/3} \lambda_1^{-1/2} (\mu_{i_0+r}')^{1/6} \ge C_{14}^{1/6} C_8^{1/2} n^{-1/12} \\
& \Leftrightarrow C_2^{1/6} \lambda_2^{1/3} \lambda_1^{-1/2} (n)^{-w/6} \ge C_{14}^{1/6} C_8^{1/2} n^{-1/12} \quad \text{car } \mu_{i_0+r}' \ge C_2 n^{-w} \\
& \Leftrightarrow \lambda_2^{1/3} \lambda_1^{-1/2} \ge C_2^{-1/6} C_{14}^{1/6} C_8^{1/2} n^{w/6-1/12} \\
& \Leftrightarrow (\log(n))^{-1/12} \ge C_{14}^{1/6} C_8^{1/2} n^{w/6-1/12}, \tag{2.28}
\end{align*}
$$

car, si $\lambda_1$ et $\lambda_2$ sont égaux à $\sqrt{\log(n)}$. Pour $n$ au voisinage de $+\infty$, l'inégalité (2.28) est vraie car
$0 < w < \frac{1}{2}$.

Par conséquent, le second terme de l'inégalité donne $\epsilon_n = \lambda_2^2 n^2 \delta_n^{-2} \mu_n^{-2}$.

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

**Lemme 2.5.5.** {Yᵢ}ᵢ∈[1,n] vérifie le modèle (1.3) . On suppose que les hypothèses du théorème 2.2.1 sont vérifiées. Sous les hypothèses (2.9), (2.10), (2.11), sur l'événement Bₙ, nous avons :

$$
\| \tilde{Y}_{s,e}^{b_0} \|_{\mathcal{H}} \geq \frac{C_{15}}{2} n^{\Theta - 1/2 - w},
$$

$$
où b_0 = \arg \max_{s \le b < e} \| \tilde{Y}_{s,e}^b \|_{\mathcal{H}}.
$$

Démonstration. D'après le lemme 2.5.8,

$$
\begin{align*}
\| \tilde{Y}_{s,e}^{b_0} \|_{\mathcal{H}} &\ge \| \tilde{Y}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} \\
&\ge \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} - \lambda_1 \\
&\ge \frac{C_9}{2} \delta_n n^{-1/2} \mu_n - \lambda_1 \\
&\ge \frac{C_9}{2} n^{\Theta - 1/2 - w} - \lambda_1 \\
&\ge \frac{C_{15}}{2} n^{\Theta - 1/2 - w}.
\end{align*}
$$

comme, pour $\lambda_1 = \sqrt{8 \log(n)}$, $\lambda_1 = o(n^{\Theta - 1/2 - w})$ car $\Theta - 1/2 - w > 0$.

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

**Lemme 2.5.6.** {$Y_i$}$_{i \in [1,n]}$ vérifie le modèle (1.3). On suppose les hypothèses du théorème 2.2.1 vraies.
Pour des constantes strictement positives C, C', si s et e vérifient l'une des conditions :

(i) ∃!1 ≤ i ≤ D* − 1 tel que s ≤ τ*ᵢ ≤ e et min{τ*ᵢ − s + 1, e − τ*ᵢ} ≤ Cεᵣ.

(ii) ∃1 ≤ i ≤ D* − 1 tel que s ≤ τ*ᵢ ≤ τ*ᵢ₊₁ ≤ e et max{τ*ᵢ − s + 1, e − τ*ᵢ₊₁} ≤ C'εᵣ.

(iii) ∃1 ≤ i ≤ D* − 1 tel que τ*ᵢ < s < e ≤ τ*ᵢ₊₁.

Alors, sur l'événement $B_n \cap A_n$, $\| \tilde{Y}_{s,e}^{b_0} \|_{\mathcal{H}} < C_{16} \lambda_2 n^{1-\Theta} + \lambda_1$, où $b_0 = \arg \max_{s \le b < e} \| \tilde{Y}_{s,e}^b \|_{\mathcal{H}}$.

Démonstration. Cas (i)
On remarque que

$$
\begin{aligned}
\| \tilde{Y}_{s,e}^{b_0} \|_{\mathcal{H}} &\le \| \tilde{\mu}_{s,e}^{b_0} \|_{\mathcal{H}} + \lambda_1 \\
&\le \max_{s \le b < e} \{ \| \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} \} + \lambda_1,
\end{aligned}
$$

d'après le lemme 2.5.3, on obtient :

$$
\begin{aligned}
\| \tilde{Y}_{s,e}^{b_0} \|_{\mathcal{H}} &\le \max_{s \le b < e} \{ \| \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} \} + \lambda_1 \\
&\le \frac{1}{C_9} \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} + \lambda_1 \\
&\le \frac{1}{C_9} \sqrt{ \frac{(\tau_{i_0+r}^* - s + 1)(e - \tau_{i_0+r}^*)}{T} } \left\| \frac{1}{\tau_{i_0+r}^* - s + 1} \sum_{i=s}^{\tau_{i_0+r}^*} \mu_i - \frac{1}{e - \tau_{i_0+r}^*} \sum_{i=\tau_{i_0+r}^*+1}^{e} \mu_i \right\|_{\mathcal{H}} + \lambda_1 \\
&\le \frac{1}{C_9} \sqrt{C \epsilon_n} \mu_{i_0+r}^{\prime} + \lambda_1 \\
&\le \frac{\sqrt{C}}{C_9} \lambda_2 n \delta_n^{-1} (\mu_{i_0+r}^{\prime})^{-1} \mu_{i_0+r}^{\prime} + \lambda_1 \text{ d'après le lemme 2.5.4} \\
&\le \frac{\sqrt{C}}{C_1 C_9} \lambda_2 n^{1-\Theta} + \lambda_1,
\end{aligned}
$$

où, pour le passage de la troisième ligne à la quatrième ligne, on a utilisé le fait qu’il y a unique
vrai instant de ruptures entre s et e.

Cas (ii)

D'après le lemme 2.5.3, on obtient :

$$
\begin{aligned}
\| \tilde{Y}_{s,e}^{b_0} \|_{\mathcal{H}} &\le \| \tilde{\mu}_{s,e}^{b_0} \|_{\mathcal{H}} + \lambda_1 \\
&\le \max \left\{ \| \tilde{\mu}_{s,e}^{\tau_{s,e}^p} \|_{\mathcal{H}}, \| \tilde{\mu}_{s,e}^{\tau_{s,e}^{p+1}} \|_{\mathcal{H}} \right\} + \lambda_1 \\
&\le \frac{1}{C_9} \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} + \lambda_1
\end{aligned}
$$

$$
\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} \quad \text{a pour expression :}
$$

$$
\begin{aligned}
& \left\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \right\|_{\mathcal{H}} \\
&= \sqrt{ \frac{(\tau_{i_0+r}^* - s + 1)(e - \tau_{i_0+r}^*)}{T} } \left\| \frac{1}{\tau_{i_0+r}^* - s + 1} \sum_{i=s}^{\tau_{i_0+r}^*} \mu_i - \frac{1}{e - \tau_{i_0+r}^*} \sum_{i=\tau_{i_0+r}^*+1}^{e} \mu_i \right\|_{\mathcal{H}} \\
&\le \sqrt{ \frac{(\tau_{i_0+r}^* - s + 1)(e - \tau_{i_0+r}^*)}{T} } \mu_{i_0+r}^{\prime},
\end{aligned}
$$

en utilisant des arguments similaires que dans la preuve du lemme A.5 (FRYZLEWICZ 2014).
Finalement, nous obtenons :

$$
\begin{align*}
\| \tilde{Y}_{s,e}^b \|_{\mathcal{H}} &\le \frac{1}{C_9} \sqrt{\frac{(\tau_{i_0+r}^* - s+1)(e-\tau_{i_0+r}^*)}{T}} \mu_{i_0+r} + \lambda_1 \\
&\le \frac{1}{C_9} \sqrt{\frac{(T C \epsilon_n)}{T}} \mu_{i_0+r} + \lambda_1 \\
&\le \frac{\sqrt{C}}{C_1 C_9} \lambda_2 n^{1-\Theta} + \lambda_1.
\end{align*}
$$

Cas (iii)

Dans ce cas, il n'y a plus de vrais instants de ruptures entre s et e donc on obtient, $\forall b \in [s, e - 1]$,

$$
\begin{align*}
\tilde{\mu}_{s,e}^b &= \sqrt{\frac{(b-s+1)(e-b)}{T}} \left[ \frac{1}{b-s+1} \sum_{i=s}^{b} \mu_i - \frac{1}{e-b} \sum_{i=b+1}^{e} \mu_i \right] \\
&= 0.
\end{align*}
$$

Ainsi,

$$
\begin{align*}
\| \tilde{Y}_{s,e}^b \|_{\mathcal{H}} &\le \lambda_1 \\
&\le \lambda_1 + \lambda_2 n^{1-\Theta}.
\end{align*}
$$

□

2.5.3 Résultats secondaires

**Lemme 2.5.7.** Si $\tau_{i_0+r}^*$ vérifie l'hypothèse (2.10). Alors, si $\|\tilde{\mu}_{s,e}^b\|_{\mathcal{H}} < \|\tilde{\mu}_{s,e}^{\tau_{i_0+r}^*}\|_{\mathcal{H}}$ et $|b - \tau_{i_0+r}^*| < C_7\gamma_n$
$(\gamma_n = \frac{n^{1/2}\lambda_1}{\mu_{p_0+r}^*})$, nous obtenons pour $n$ suffisamment grand :

$$
\left\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \right\|_{\mathcal{H}} - \left\| \tilde{\mu}_{s,e}^b \right\|_{\mathcal{H}} \ge \frac{\left| b - \tau_{i_0+r}^* \right|}{\sqrt{2}\delta_n} \left\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \right\|_{\mathcal{H}}.
$$

Démonstration. **Cas** $b > \tau_{i_0+r}^*$

Nous allons prouver que pour $n$ au voisinage de $+\infty$,

$$
\| \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} \le \sqrt{\frac{(\tau_{i_0+r}^* - s+1)(e-b)}{(e-\tau_{i_0+r}^*)(b-s+1)}} \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}
$$
On remarque que $\frac{b-\tau_{i_0+r}^*}{\tau_{i_0+r}^*-s+1} = o(1)$ et $\frac{b-\tau_{i_0+r}^*}{e-\tau_{i_0+r}^*} = o(1)$ pour $n$ au voisinage de $+\infty$. En effet,

$$ \frac{|b - \tau_{i_0+r}^*|}{\tau_{i_0+r}^* - s + 1} \le C_7 \frac{n^{1/2} \lambda_1}{\mu_{i_0+r} \delta_n} \\ \le \frac{C_7 \sqrt{8}}{C_1 C_2 C_3} n^{1/2+w-\Theta} \sqrt{\log(n)}, $$

pour $\lambda_1 = \sqrt{8 \log(n)}$.

Or, pour $n$ appartenant au voisinage de $+\infty$, $n^{1/2+w-\Theta} \sqrt{\log(n)} \underset{n \to +\infty}{\longrightarrow} 0$ car $\Theta - \frac{w}{2} > \frac{3}{4} \Rightarrow \frac{1}{2} + w - \Theta < 0$.

De même,

$$ \frac{|b - \tau_{i_0+r}^*|}{e - \tau_{i_0+r}^*} \le C_7 \frac{n^{1/2} \lambda_1}{\mu_{i_0+r} \delta_n} \\ \le \frac{C_7 \sqrt{8}}{C_1 C_2 C_3} n^{1/2+w-\Theta} \sqrt{\log(n)} $$

Or, pour $n$ appartenant au voisinage de $+\infty$, $n^{1/2+w-\Theta} \sqrt{\log(n)} \underset{n \to +\infty}{\longrightarrow} 0$ car $\Theta - \frac{w}{2} > \frac{3}{4} \Rightarrow \frac{1}{2} + w - \Theta < 0$.

Ainsi, on obtient, pour $n$ appartenant à un voisinage de $+\infty$ :

$$ \begin{align*} \sqrt{\frac{(\tau_{i_0+r}^* - s + 1)(e - b)}{(b - s + 1)(e - \tau_{i_0+r}^*)}} &= \frac{\sqrt{\tau_{i_0+r}^* - s + 1}}{\sqrt{e - \tau_{i_0+r}^*}} \frac{\sqrt{(e - \tau_{i_0+r}^*) - (b - \tau_{i_0+r}^*)}}{\sqrt{(\tau_{i_0+r}^* - s + 1) + (b - \tau_{i_0+r}^*)}} \\ &= \frac{\sqrt{1 - \frac{b - \tau_{i_0+r}^*}{e - \tau_{i_0+r}^*}}}{\sqrt{1 + \frac{b - \tau_{i_0+r}^*}{\tau_{i_0+r}^* - s + 1}}} \\ &= \frac{1 - \frac{1}{2} \frac{b - \tau_{i_0+r}^*}{e - \tau_{i_0+r}^*} + o\left(\frac{b - \tau_{i_0+r}^*}{e - \tau_{i_0+r}^*}\right)}{1 + \frac{1}{2} \frac{b - \tau_{i_0+r}^*}{\tau_{i_0+r}^* - s + 1} + o\left(\frac{b - \tau_{i_0+r}^*}{\tau_{i_0+r}^* - s + 1}\right)} \\ &\ge \frac{1 - \frac{b - \tau_{i_0+r}^*}{e - \tau_{i_0+r}^*}}{1 + \frac{b - \tau_{i_0+r}^*}{\tau_{i_0+r}^* - s + 1}} =: u_n \end{align*} $$

Ainsi, comme $u_n$ tend vers 1 lorsque $n$ tend vers $+\infty$ alors, pour $n$ appartenant à un voisinage de
+∞,

$$
\begin{align*}
\| \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} &< \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} \\
\Rightarrow \| \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} &\le \sqrt{\frac{(\tau_{i_0+r}^* - s+1)(e-b)}{(e-\tau_{i_0+r}^*)(b-s+1)}} \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}
\end{align*}
$$

Nous minorons ensuite $\left\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \right\|_{\mathcal{H}} - \left\| \tilde{\mu}_{s,e}^b \right\|_{\mathcal{H}}$ pour $n$ appartenant à un voisinage de $+\infty$ :

$$
\begin{align*}
\| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} - \| \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} &\ge \left( 1 - \sqrt{\frac{(\tau_{i_0+r}^* - s+1)(e-b)}{(e-\tau_{i_0+r}^*)(b-s+1)}} \right) \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} \\
&\ge \left[ \frac{\sqrt{1 + \frac{b-\tau_{i_0+r}^*}{\tau_{i_0+r}^* - s+1}} - \sqrt{1 - \frac{b-\tau_{i_0+r}^*}{e-\tau_{i_0+r}^*}}}{\sqrt{1 + \frac{b-\tau_{i_0+r}^*}{\tau_{i_0+r}^* - s+1}}} \right] \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} \\
&\ge \frac{\left(1 + \frac{1}{2} \frac{b-\tau_{i_0+r}^*}{\tau_{i_0+r}^* - s+1}\right) - \left(1 - \frac{1}{2} \frac{b-\tau_{i_0+r}^*}{e-\tau_{i_0+r}^*}\right)}{\sqrt{2}} \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}} \\
&\ge \frac{b - \tau_{i_0+r}^*}{\sqrt{2} \delta_n} \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}.
\end{align*}
$$

Cas $b < \tau_{i_0+r}^*$

Nous allons prouver que pour $n$ appartenant à un voisinage de $+\infty$,

$$
\| \tilde{\mu}_{s,e}^b \|_{\mathcal{H}} \le \sqrt{\frac{(b-s+1)(e-\tau_{i_0+r}^*)}{(e-b)(\tau_{i_0+r}^* - s+1)}} \| \tilde{\mu}_{s,e}^{\tau_{i_0+r}^*} \|_{\mathcal{H}}
$$
On remarque que, pour $n$ appartenant à un voisinage de $+\infty$ :

$$
\begin{align*}
\sqrt{\frac{(b-s+1)(e-\tau_{i_0+r}^*)}{(\tau_{i_0+r}^* - s+1)(e-b)}} &= \frac{\sqrt{e-\tau_{i_0+r}^*}}{\sqrt{\tau_{i_0+r}^* - s+1}} \frac{\sqrt{(\tau_{i_0+r}^* - s+1) + (b-\tau_{i_0+r}^*)}}{\sqrt{(e-\tau_{i_0+r}^*) + (\tau_{i_0+r}^* - b)}} \\
&= \frac{\sqrt{1 - \frac{\tau_{i_0+r}^*-b}{\tau_{i_0+r}^*-s+1}}}{\sqrt{1 + \frac{\tau_{i_0+r}^*-b}{e-\tau_{i_0+r}^*}}} \\
&= \frac{1 - \frac{1}{2} \frac{\tau_{i_0+r}^*-b}{\tau_{i_0+r}^*-s+1} + o\left(\frac{\tau_{i_0+r}^*-b}{\tau_{i_0+r}^*-s+1}\right)}{1 + \frac{1}{2} \frac{\tau_{i_0+r}^*-b}{e-\tau_{i_0+r}^*} + o\left(\frac{\tau_{i_0+r}^*-b}{e-\tau_{i_0+r}^*}\right)} \\
&\ge \frac{1 - \frac{\tau_{i_0+r}^*-b}{\tau_{i_0+r}^*-s+1}}{1 + \frac{\tau_{i_0+r}^*-b}{e-\tau_{i_0+r}^*}},
\end{align*}
$$

Nous procédons ensuite de la même manière que pour le cas $b > \tau_{i_0+r}^*$ pour obtenir le résultat. $\square$

**Lemme 2.5.8.** *Sous l'hypothèse (2.10), nous avons*

$$
\max_{s \le b < e} \| \tilde{\mu}_{s,e}^b \|_H \ge \frac{\delta_n}{2\sqrt{n}} \mu_{i_0+r}^{'},
$$

Démonstration. Dans un premier temps, nous cherchons à montrer que $\forall b \in [\llbracket s, e-1 \rrbracket]$, $\tilde{\mu}_{s,e}^b = \frac{1}{\sqrt{T}} g(\frac{b-s+1}{T})$ où la fonction $g$ est définie dans la propriété 2.5.2 et $\{a_i\}_{i \in \llbracket 0, q+1 \rrbracket}$, $\{\lambda_i\}_{i \in \llbracket 0, q \rrbracket}$ sont définis par :

$$
\begin{align*}
a_i &= \frac{\tau_{i_0+i}^* - l_1}{l_2 - l_1} = \frac{\tau_{i_0+i}^* - s + 1}{T} \quad \text{pour } i \in \llbracket 1, q \rrbracket \\
\lambda_i &= \mu_{\tau_{i_0+i}^*+1} \quad \text{pour } i \in \llbracket 0, q \rrbracket \\
x &= \frac{l - l_1}{l_2 - l_1} = \frac{b - s + 1}{T},
\end{align*}
$$

où $M_l = \sum_{i=1}^l \mu_i ; l_1 = s-1 ; l_2 = e ; l_1 < l < l_2 ; l = b$.
Pour cela, nous montrons tout d'abord que $\forall b \in [\llbracket s, e-1 \rrbracket]$,

$$
\begin{align*}
\tilde{\mu}_{s,e}^b &= -\Theta_{l_1,l_2}^l \\
&= \frac{-1}{\sqrt{(l-l_1)(1-\frac{l-l_1}{l_2-l_1})}} \left[ \frac{l-l_1}{l_2-l_1} (M_{l_2}-M_{l_1}) - (M_l-M_{l_1}) \right].
\end{align*}
$$
En effet,

$$
\begin{align*}
\Theta_{l_1, l_2}^l &= \frac{1}{\sqrt{(l-l_1)(1-\left(\frac{l-l_1}{l_2-l_1}\right))}} \left[ \frac{l-l_1}{l_2-l_1} (M_{l_2}-M_{l_1}) - (M_l-M_{l_1}) \right] \\
&= \sqrt{\frac{(l-l_1)}{(l_2-l_1)(l_2-l)}} (M_{l_2}-M_{l_1}) - \sqrt{\frac{(l_2-l_1)}{(l-l_1)(l_2-l)}} (M_l-M_{l_1}) \\
&= \sqrt{\frac{(b-s+1)}{(e-s+1)(e-b)}} \sum_{i=s}^{e} \mu_i - \sqrt{\frac{(e-s+1)}{(b-s+1)(e-b)}} \sum_{i=s}^{b} \mu_i \\
&= \sqrt{\frac{(b-s+1)}{(e-s+1)(e-b)}} \sum_{i=b+1}^{e} \mu_i + \left[ \sqrt{\frac{(b-s+1)}{(e-s+1)(e-b)}} - \sqrt{\frac{(e-s+1)}{(b-s+1)(e-b)}} \right] \sum_{i=s}^{b} \mu_i \\
&= \sqrt{\frac{(b-s+1)}{(e-s+1)(e-b)}} \sum_{i=b+1}^{e} \mu_i + \frac{1}{\sqrt{e-b}} \left[ \sqrt{\frac{b-s+1}{e-s+1}} - \sqrt{\frac{e-s+1}{b-s+1}} \right] \sum_{i=s}^{b} \mu_i \\
&= \sqrt{\frac{(b-s+1)}{(e-s+1)(e-b)}} \sum_{i=b+1}^{e} \mu_i + \sqrt{\frac{e-s+1}{(b-s+1)(e-b)}} \left[ \frac{(b-s+1)-(e-s+1)}{e-s+1} \right] \sum_{i=s}^{b} \mu_i \\
&= \sqrt{\frac{(b-s+1)}{(e-s+1)(e-b)}} \sum_{i=b+1}^{e} \mu_i - \sqrt{\frac{(e-b)}{(e-s+1)(b-s+1)}} \sum_{i=s}^{b} \mu_i \\
&= -\tilde{\mu}_{s,e}^b.
\end{align*}
$$

Sous l'hypothèse $M_{l_2} - M_{l_1} = \sum_{i=s}^{e} \mu_i = 0$, nous pouvons écrire $\Theta_{l_1, l_2}^l = \frac{-1}{\sqrt{l_2-l_1}} g(\frac{l-l_1}{l_2-l_1})$. Ainsi,
$\forall b \in [s, e-1]$, $\tilde{\mu}_{s,e}^b = \frac{1}{\sqrt{I}} g(\frac{b-s+1}{T})$.

En effet, on remarque que :

$$
\begin{align*}
\sum_{j=1}^{i} (a_j - a_{j-1}) \lambda_{j-1} + (x - a_i) \lambda_i &= \frac{\tau_{i_0+1}^* - l_1}{l_2 - l_1} \mu_{\tau_{i_0+1}^*} \\
&\quad + \sum_{j=2}^{i} \left( \frac{\tau_{i_0+j}^* - \tau_{i_0+j-1}^*}{l_2 - l_1} \right) \mu_{\tau_{i_0+j-1}^* + 1} \\
&\quad + \frac{l - \tau_{i_0+i}^*}{l_2 - l_1} \mu_{\tau_{i_0+i}^* + 1} \\
&= \frac{1}{l_2 - l_1} (M_l - M_{l_1}).
\end{align*}
$$
Ainsi,

$$
\begin{align*}
g(x) &= \frac{\sum_{j=1}^{i} (a_j - a_{j-1}) \lambda_{j-1} + (x - a_i) \lambda_i}{\sqrt{x(1-x)}} \\
&= \frac{1}{(l_2 - l_1) \cdot \sqrt{\frac{l_2-l_1}{l_2-l_1} \left(1 - \frac{l_2-l_1}{l_2-l_1}\right)}} \\
&= -\Theta_{l_1, l_2}^{l} \cdot \sqrt{l_2 - l_1}.
\end{align*}
$$

On remarque

$$
\begin{align*}
\| M \tau_{i_0+r}^* - M \tau_{i_0+r}^* - \delta_n - 1 \|_{\mathcal{H}} &= \left\| \sum_{i=\tau_{i_0+r}^* - \delta_n}^{\tau_{i_0+r}^*} \mu_i \right\|_{\mathcal{H}} \\
&= \delta_n \| \mu_{\tau_{i_0+r}^*} \|_{\mathcal{H}},
\end{align*}
$$

car il n'y a pas de vrais instants de ruptures dans le segment $[\tau_{i_0+r}^* - \delta_n, \tau_{i_0+r}^*]$.

$$
\text{De même, } \left\| M \tau_{i_0+r}^* + \delta_n - M \tau_{i_0+r}^* \right\|_{\mathcal{H}} = \delta_n \left\| \mu \tau_{i_0+r}^* + 1 \right\|_{\mathcal{H}}.
$$

Par conséquent,

$$
\begin{align*}
\Theta_{l_1, l_2} &= \max_{l_1 < l < l_2} \left\| \Theta_{l_1, l_2}^l \right\|_{\mathcal{H}} \\
&= \max_{l_1 < l < l_2} \left[ \sqrt{\frac{l_2 - l_1}{(l - l_1)(l_2 - l)}} \left\| M_l - M_{l_1} \right\|_{\mathcal{H}} \right]
\end{align*}
$$

On remarque

$$
\begin{align*}
\| M \tau_{i_0+r}^* - M \tau_{i_0+r}^* - \delta_n - 1 \|_{\mathcal{H}} &\le \| M \tau_{i_0+r}^* - M_{l_1} \|_{\mathcal{H}} + \| M_{l_1} - M \tau_{i_0+r}^* - \delta_n - 1 \|_{\mathcal{H}} \\
&\le 2 \max_{l_1 < l < l_2} \| M_l - M_{l_1} \|_{\mathcal{H}}.
\end{align*}
$$

$$
\text{De même, } \left\| M \tau_{i_0+r}^* + \delta_n - M \tau_{i_0+r}^* \right\|_{\mathcal{H}} \le 2 \max_{l_1<l<l_2} \left\| M_l - M_{l_1} \right\|_{\mathcal{H}}.
$$

Ainsi,

$$
\begin{align*}
& \delta_n \max \left\{ \| \mu \tau_{i_0+r}^* \|_{\mathcal{H}}, \| \mu \tau_{i_0+r}^* + 1 \|_{\mathcal{H}} \right\} \\
&= \max \left\{ \| M \tau_{i_0+r}^* - M \tau_{i_0+r}^* - \delta_n - 1 \|_{\mathcal{H}}, \| M \tau_{i_0+r}^* + \delta_n - M \tau_{i_0+r}^* \|_{\mathcal{H}} \right\} \\
&\le 2 \max_{l_1 < l < l_2} \| M_l - M_{l_1} \|_{\mathcal{H}} \\
&\Rightarrow \max_{l_1 < l < l_2} \| M_l - M_{l_1} \|_{\mathcal{H}} \ge \frac{\delta_n \max \left\{ \| \mu \tau_{i_0+r}^* \|_{\mathcal{H}}, \| \mu \tau_{i_0+r}^* + 1 \|_{\mathcal{H}} \right\}}{2}.
\end{align*}
$$
Comme, pour $l_1 < l < l_2$, $(l-l_1)(l_2-l) \le \frac{(l_2-l_1)^2}{4} \Rightarrow \frac{l_2-l_1}{(l-l_1)(l_2-l)} \ge \frac{4}{l_2-l_1}$, on en déduit que

$$ \Theta_{l_1, l_2} \ge \frac{\delta_n}{\sqrt{T}} \max \left\{ \| \mu_{\tau_{i_0+r}^*} \|_{\mathcal{H}}, \| \mu_{\tau_{i_0+r}^*+1} \|_{\mathcal{H}} \right\} \\ \ge \frac{\delta_n}{2\sqrt{n}} \mu_{i_0+r}' $$

car $2 \max\{\|\mu_{\tau_{i_0+r}^*}\|_{\mathcal{H}}, \|\mu_{\tau_{i_0+r}^*+1}\|_{\mathcal{H}}\} \ge \|\mu_{\tau_{i_0+r}^*}\|_{\mathcal{H}} + \|\mu_{\tau_{i_0+r}^*+1}\|_{\mathcal{H}} \ge \mu_{i_0+r}'$ d'après l'inégalité triangulaire. $\square$

**Propriété 2.5.2.** Nous définissons pour $i \in [0, q]$, pour $x \in [a_i, a_{i+1}]$

$$ g(x) = \frac{\sum_{j=1}^{i} (a_j - a_{j-1}) \lambda_{j-1} + (x - a_i) \lambda_i}{\sqrt{x(1-x)}} \\ = \frac{ax + b}{\sqrt{x(1-x)}}. \\ h(x) = \|g(x)\|_{\mathcal{H}}^2. $$

avec les notations

— $\{a_i\}_{i \in [0, q+1]}$ sont définis tels que $a_0 := 0 < a_1 < \dots < a_q < a_{q+1} := 1$.

— $\lambda_0, \dots, \lambda_q \in \mathcal{H}$ sont définis tels que $\forall i \in [0, q-1]$, $\lambda_i \ne \lambda_{i+1}$.

— Pour $i \in [0, q]$, $a = \lambda_i$.

— si $i \in [1, q]$, $b = \sum_{j=1}^{i} (a_j - a_{j-1}) \lambda_{j-1} - a_i \lambda_i$. Si $i = 0, b = 0$.

Alors, pour $i \in [1, q-1]$, $h$ est strictement convexe sur $[a_i, a_{i+1}]$. De plus, $h$ est strictement convexe sur $]0, a_1]$ et $[a_q, 1[$.

**Démonstration.** Pour prouver que $h$ est strictement convexe sur $[a_i, a_{i+1}]$, il suffit de montrer que $\forall x \in [a_i, a_{i+1}]$, $h''(x) > 0$. Dans un premier temps, nous calculons $h''$. Nous définissons $\forall y \in \mathcal{H}$, $r(y) = \|y\|_{\mathcal{H}}^2$, alors $\forall x \in [a_i, a_{i+1}]$, $h(x) = r(g(x))$. Nous calculons la différentielle de $r$, $\forall x, k \in \mathcal{H}$,

$$ r(x+k) = \|x+k\|_{\mathcal{H}}^2 \\ = \|x\|_{\mathcal{H}}^2 + \|k\|_{\mathcal{H}}^2 + 2\langle x, k \rangle_{\mathcal{H}} \\ \Rightarrow dr_x(k) = 2\langle x, k \rangle_{\mathcal{H}}. $$

Nous calculons ensuite la dérivée de $h$, $\forall x \in [a_i, a_{i+1}]$, $\forall k \in \mathbb{R}$

$$ dh_x(k) = dr_{g(x)}(dg_x(k)) \\ = 2\langle g(x), dg_x(k) \rangle_{\mathcal{H}} \\ = 2\langle g(x), kg'(x) \rangle_{\mathcal{H}} \\ \Rightarrow h'(x) = 2\langle g(x), g'(x) \rangle_{\mathcal{H}}. $$
Nous calculons la dérivée de $g, \forall x \in [a_i, a_{i+1}]$,

$$
\begin{align*}
g'(x) &= \frac{a\sqrt{x(1-x)} - \frac{ax+b}{2\sqrt{x(1-x)}}(1-2x)}{x(1-x)} \\
&= \frac{a[x(1-x)] - \frac{ax+b}{2}(1-2x)}{[x(1-x)]^{3/2}} \\
&= \frac{a[x-x^2] - \left[\frac{ax+b}{2} - ax^2 - bx\right]}{[x(1-x)]^{3/2}} \\
&= \frac{\frac{ax}{2} + bx - \frac{b}{2}}{[x(1-x)]^{3/2}}
\end{align*}
$$

Nous en déduisons l'expression de $h', \forall x \in [a_i, a_{i+1}]$,

$$
\begin{align*}
h'(x) &= 2\langle g(x), g'(x) \rangle_{\mathcal{H}} \\
&= \frac{1}{[x(1-x)]^2} \langle ax + b, ax + 2bx - b \rangle_{\mathcal{H}} \\
&= \frac{1}{[x(1-x)]^2} \left[ \|ax\|_{\mathcal{H}}^2 + 2\langle bx, ax \rangle_{\mathcal{H}} - \langle b, ax \rangle_{\mathcal{H}} \right. \\
&\qquad \left. + \langle b, ax \rangle_{\mathcal{H}} + \langle b, 2bx \rangle_{\mathcal{H}} - \|b\|_{\mathcal{H}}^2 \right] \\
&= \frac{1}{[x(1-x)]^2} \left[ \|a\|_{\mathcal{H}}^2 x^2 - \|b\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}} x^2 + 2x \|b\|_{\mathcal{H}}^2 \right] \\
&= \frac{1}{[x(1-x)]^2} \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}})x^2 + 2\|b\|_{\mathcal{H}}^2 x - \|b\|_{\mathcal{H}}^2 \right]
\end{align*}
$$

On en déduit l'expression de $h'', \forall x \in [a_i, a_{i+1}]$,

$$
\begin{align*}
h''(x) &= \frac{1}{[x(1-x)]^4} \left\{ \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 2x + 2\|b\|_{\mathcal{H}}^2 \right] [x(1-x)]^2 \right. \\
&\quad \left. - 2x(1-x)(1-2x) \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) x^2 + 2\|b\|_{\mathcal{H}}^2 x - \|b\|_{\mathcal{H}}^2 \right] \right\} \\
&= \frac{1}{[x(1-x)]^3} \left\{ \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 2x + 2\|b\|_{\mathcal{H}}^2 \right] [x(1-x)] \right. \\
&\quad \left. - 2(1-2x) \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) x^2 + 2\|b\|_{\mathcal{H}}^2 x - \|b\|_{\mathcal{H}}^2 \right] \right\} \\
&= \frac{R(x)}{[x(1-x)]^3}, \tag{2.29}
\end{align*}
$$
où $\forall x \in [a_i, a_{i+1}]$,

$$
\begin{align*}
R(x) &= \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 2x + 2\|b\|_{\mathcal{H}}^2 \right] [x(1-x)] \\
&\quad - 2(1-2x) \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) x^2 + 2\|b\|_{\mathcal{H}}^2 x - \|b\|_{\mathcal{H}}^2 \right] \\
&= \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 2x + 2\|b\|_{\mathcal{H}}^2 \right] (x-x^2) \\
&\quad - (2-4x) \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) x^2 + 2\|b\|_{\mathcal{H}}^2 x - \|b\|_{\mathcal{H}}^2 \right] \\
&= \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 2x^2 + 2\|b\|_{\mathcal{H}}^2 x - (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 2x^3 - 2\|b\|_{\mathcal{H}}^2 x^2 \right] \\
&\quad - \left\{ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 2x^2 + 4\|b\|_{\mathcal{H}}^2 x - 2\|b\|_{\mathcal{H}}^2 - (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 4x^3 \right. \\
&\qquad \left. - 8\|b\|_{\mathcal{H}}^2 x^2 + 4\|b\|_{\mathcal{H}}^2 x \right\} \\
&= (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) 2x^3 + 6\|b\|_{\mathcal{H}}^2 x^2 - 6\|b\|_{\mathcal{H}}^2 x + 2\|b\|_{\mathcal{H}}^2 \\
&\geq (\|a\|_{\mathcal{H}}^2 - 2\|a\|_{\mathcal{H}} \|b\|_{\mathcal{H}}) 2x^3 + 6\|b\|_{\mathcal{H}}^2 x^2 - 6\|b\|_{\mathcal{H}}^2 x + 2\|b\|_{\mathcal{H}}^2 \\
&\geq ((\|a\|_{\mathcal{H}} - \|b\|_{\mathcal{H}})^2 - \|b\|_{\mathcal{H}}^2) 2x^3 + 6\|b\|_{\mathcal{H}}^2 x^2 - 6\|b\|_{\mathcal{H}}^2 x + 2\|b\|_{\mathcal{H}}^2 \\
&\geq (\|a\|_{\mathcal{H}} - \|b\|_{\mathcal{H}})^2 2x^3 - 2x^3 \|b\|_{\mathcal{H}}^2 + 6\|b\|_{\mathcal{H}}^2 x^2 - 6\|b\|_{\mathcal{H}}^2 x + 2\|b\|_{\mathcal{H}}^2 \\
&\geq (\|a\|_{\mathcal{H}} - \|b\|_{\mathcal{H}})^2 2x^3 + 2\|b\|_{\mathcal{H}}^2 (-x^3 + 3x^2 - 3x + 1) \\
&\geq (\|a\|_{\mathcal{H}} - \|b\|_{\mathcal{H}})^2 2x^3 + 2\|b\|_{\mathcal{H}}^2 (1-x)^3 \\
&\geq 0.
\end{align*}
$$

Si $i \in [1, q-1]$, $h'' > 0$ sur $[a_i, a_{i+1}]$. Sinon, soit $j(x) = (\|a\|_{\mathcal{H}} - \|b\|_{\mathcal{H}})^2 2x^3 + 2\|b\|_{\mathcal{H}}^2 (1-x)^3$ : pour $i \in [1, q-1]$, si $\exists x \in [a_i, a_{i+1}]$, $j(x) = 0 \Rightarrow a = b = 0 \Rightarrow g = 0$ sur $[a_i, a_{i+1}]$. De même, $h'' > 0$ sur $]0, a_1]$ et $[a_q, 1[$. Sinon, si $\exists x \in ]0, a_1]$, $j(x) = 0 \Rightarrow g = 0$ sur $]0, a_1]$. On obtient le même résultat sur $[a_q, 1[$. $\square$

**Propriété 2.5.3.** Nous reprenons les notations définies dans la propriété 2.5.2 et nous montrons que si $\sum_{j=0}^q (a_{j+1} - a_j) \lambda_j = 0$, alors $g^* = \max_{0 \le x \le 1} \|g(x)\|_{\mathcal{H}}$ est atteint en l'un des $\{a_i\}_{i \in [1,q]}$ seulement.

**Démonstration.** D'après la propriété 2.5.2, pour $i \in [1, q-1]$, $h$ est strictement convexe sur $[a_i, a_{i+1}]$. Il suffit donc de montrer que $h: x \mapsto \|g(x)\|_{\mathcal{H}}^2$ est croissante sur $]0, a_1]$ et décroissante sur $[a_q, 1[$ pour obtenir le résultat.

Si $x \in ]0, a_1]$, $a = \lambda_0$ and $b = 0$. Dans ce cas, nous obtenons, $\forall x \in ]0, a_1]$,

$$
\begin{align*}
h'(x) &= \frac{1}{[x(1-x)]^2} \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}}) x^2 + 2\|b\|_{\mathcal{H}}^2 x - \|b\|_{\mathcal{H}}^2 \right] \\
&= \frac{\|a\|_{\mathcal{H}}^2}{(1-x)^2} \\
&\geq 0.
\end{align*}
$$
De plus, nous avons $\forall x \in ]0, a_1]$,

$$ 
\begin{aligned}
g(x) &= \frac{ax + b}{\sqrt{x(1-x)}} \\
&= a\sqrt{\frac{x}{1-x}} \quad \text{car } b = 0.
\end{aligned}
$$

Ainsi, si $a \neq 0$, comme $\lim_{x \to 0} g(x) = 0$, alors $h$ est strictement croissante sur $[0, a_1]$. Si $a = 0$, alors $h$ est identiquement nulle sur $[0, a_1]$ car $\lim_{x \to 0} g(x) = 0$.

Si $x \in [a_q, 1[, a = \lambda_q$ and $b = \sum_{j=1}^q (a_j - a_{j-1})\lambda_{j-1} - a_q\lambda_q = \sum_{j=0}^{q-1}(a_{j+1} - a_j)\lambda_j - a_q\lambda_q = -\lambda_q$. Dans ce cas, nous obtenons, $\forall x \in [a_q, 1[$,

$$ 
\begin{aligned}
h'(x) &= \frac{1}{[x(1-x)]^2} \left[ (\|a\|_{\mathcal{H}}^2 + 2\langle a, b \rangle_{\mathcal{H}})x^2 + 2\|b\|_{\mathcal{H}}^2 x - \|b\|_{\mathcal{H}}^2 \right] \\
&= \frac{1}{[x(1-x)]^2} \left[ (\|\lambda_q\|_{\mathcal{H}}^2 - 2\|\lambda_q\|_{\mathcal{H}}^2)x^2 + 2\|\lambda_q\|_{\mathcal{H}}^2 x - \|\lambda_q\|_{\mathcal{H}}^2 \right] \\
&= \frac{\|\lambda_q\|_{\mathcal{H}}^2}{[x(1-x)]^2} [-x^2 + 2x - 1] \\
&= \frac{-\|\lambda_q\|_{\mathcal{H}}^2}{[x(1-x)]^2} (x-1)^2 \\
&= \frac{-\|\lambda_q\|_{\mathcal{H}}^2}{x^2}.
\end{aligned}
$$

De plus, nous obtenons $\forall x \in [a_q, 1[$,

$$ 
\begin{aligned}
g(x) &= \frac{ax + b}{\sqrt{x(1-x)}} \\
&= \lambda_q \frac{x-1}{\sqrt{x(1-x)}} \\
&= -\lambda_q \sqrt{\frac{1-x}{x}}.
\end{aligned}
$$

Ainsi, si $a = \lambda_q \neq 0$, comme comme $\lim_{x \to 1} g(x) = 0$, alors $h$ est strictement décroissante $[a_q, 1]$. Si $a = \lambda_q = 0$, $h$ est identiquement nulle sur $[a_q, 1]$ car $\lim_{x \to 1} g(x) = 0$.

Ainsi le maximum de $h$ sur l'intervalle $[0, 1]$ est atteint sur l'intervalle $[a_1, a_q]$. De plus, comme pour $i \in \llbracket 1, q-1 \rrbracket$, $h$ est strictement convexe sur $[a_i, a_{i+1}]$ alors le maximum de $h$ est atteint en l'un des points $\{a_i\}_{i \in \llbracket 1, q \rrbracket}$. $\square$
Chapitre 3

Règle d'arrêt et descente de gradient
dans le modèle linéaire

Dans ce chapitre, notre objectif est de comprendre le fonctionnement d'une règle d'arrêt dans le cas simple du problème de régression linéaire. Puis, il s'agit de proposer un estimateur, construit à partir d'une règle d'arrêt, qui a de bonnes performances statistiques et peu coûteux en temps de calcul.

Dans le cadre de la régression linéaire, lorsque la matrice d'incidence X est de rang plein, on utilise souvent l'estimateur des moindres carrés (EMC) pour estimer θ* (nous travaillons dans le modèle linéaire (3.1)) (SEBER et LEE 2012). Dans ce cas, l'EMC est aussi l'estimateur du risque empirique. Pour imiter un cas fréquemment rencontré en pratique où il n'y a pas de formules explicites de l'estimateur du risque empirique, on approche l'estimateur du risque empirique à l'aide d'un algorithme de descente de gradient à pas fixe α appliqué aux moindres carrés. On note ˆθ$_{κ}$ (θ$_{κ}$ est défini dans la partie 3.1.1) cette approximation de l'EMC qui dépend d'un paramètre κ. Cette approximation de l'EMC ˆθ$_{κ}$ correspond à l'estimateur usuel qui nécessite de faire un grand nombre d'itérations de l'algorithme. Cet algorithme fournit une famille ordonnée d'estimateurs {ℓ(ˆt)}$_{t∈N}$. On utilise la connaissance de l'EMC pour étudier statistiquement cette famille d'estimateurs et proposer une règle d'arrêt ˆt.

La figure 3.1 représente l'erreur de prédiction $\frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$ en fonction de l'itération $t$ ($\hat{Y}^{(t)} = X\hat{\theta}^{(t)}; Y^* = X\theta^*$). Cette figure motive d'utiliser une règle d'arrêt car nous y observons un phénomène de surapprentissage lorsque le nombre d'itérations de l'algorithme de descente de gradient augmente (RASKUTTI, WAINWRIGHT et YU 2014; BLANCHARD, HOFFMANN et REISS 2016). Une règle d'arrêt permet de limiter ce phénomène de surapprentissage car l'on stoppe plus tôt l'algorithme, i.e. avant que le phénomène de surapprentissage se produise. De plus, la règle d'arrêt ˆt réalise un comprom biais-variance et donc permet que le biais de l'estimateur proposé ne soit pas trop grand. Des simulations montrent que lorsque $n$ est proche de $d$, l'erreur moyenne quadratique de $\hat{Y}^{(t)} = X\hat{\theta}^{(t)}$ est plus petite que celle de $\hat{Y}_κ = X\hat{\theta}_κ$.

Dans la partie 3.1, nous donnons des arguments justifiant d'utiliser une règle d'arrêt pour obtenir un estimateur $\hat{\theta}^{(t)}$ ayant de bonnes performances statistiques et moins coûteux en temps de calcul que l'estimateur usuel $\hat{\theta}_κ$. Dans la partie 3.2.3, nous comparons la précision statistique et le temps de calcul de l'estimateur proposé $\hat{\theta}^{(t)}$ à ceux de $\hat{\theta}_κ$ et de l'EMC $\hat{\theta}_n$ sur des simulations.
<figure><img src="image_20.png" /><figcaption>FIGURE 3.1 – Erreur de prédiction $\frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$ en fonction de l'itération $t$ pour $n = 30$, $d = 20$ et un pas $\alpha$ égal à 0.01 ; $\hat{Y}^{(t)} = X\hat{\theta}^{(t)}$ et $Y^* = X\theta^*$.</figcaption></figure>

La partie 3.4 contient les preuves des propriétés et des lemmes.

## 3.1 Règle d'arrêt comme compromis biais-variance

Dans cette partie, nous définissons la famille d'estimateurs $\{\hat{\theta}^{(t)}\}_{t \in \mathbb{N}}$ construite grâce à un algorithme de descente de gradient. En particulier, nous justifions l'utilisation d'une règle d'arrêt afin d'obtenir un estimateur plus précis et moins coûteux en temps de calcul que $\hat{\theta}_{\kappa}$. Puis, nous définissons la règle d'arrêt $\hat{t}$ qui traduit un compromis biais-variance.

### 3.1.1 Estimateurs obtenus par l'algorithme de descente de gradient

**Famille d'estimateurs** Nous nous inspirons d'une approche due à RASKUTTI, WAINWRIGHT et YU 2014 qui utilise une règle d'arrêt pour améliorer la précision statistique et le temps de calcul de l'estimateur construit grâce à un algorithme de descente de gradient dans le cadre des noyaux (ARONSZAJN 1950). Nous étudions cette approche dans le cas simple du problème de régression linéaire pour comprendre le fonctionnement d'une règle d'arrêt. BLANCHARD, HOFFMANN et REISS 2016 ont proposé une autre règle d'arrêt pour un algorithme de descente de gradient appliqué aux moindres carrés. Néanmoins, cette règle d'arrêt a pour but de stopper l'algorithme de descente de gradient lorsque le biais au carré de $\hat{Y}^{(t)}$ est égal à la variance de $\hat{Y}^{(t)}$ : nous avons vu au chapitre 1 que ce n'est pas toujours la situation désirée. Nous rappelons le modèle linéaire

$$Y = X\theta^* + \epsilon, \quad (3.1)$$

où $\theta^*$ est le paramètre à estimer ; $X \in \mathcal{M}_{n,d}(\mathbb{R})$ dont la $i$-ligne est $X_i^T \in \mathbb{R}^d$, la $i$-coordonnée du vecteur $Y \in \mathbb{R}^n$ est $Y_i$, où $(X_1, Y_1), \dots, (X_n, Y_n)$ sont des variables aléatoires i.i.d. . Nous faisons les