hypothèses suivantes : la matrice X est supposée de rang plein (rg(X) = d) et le terme d'erreur $\epsilon \in \mathbb{R}^n$ vérifie $\epsilon \sim \mathcal{N}(0, \sigma^2 I_n)$.

Nous définissons $\{\hat{\theta}^{(t)}\}_{t \in \mathbb{N}}$ la famille d'estimateurs de $\theta^*$ obtenue grâce à l'algorithme de descente de gradient (GD) à pas fixe $\alpha$ appliqué aux moindres carrés $C_n$. Nous rappelons la relation entre $\hat{\theta}^{(t+1)}$ et $\hat{\theta}^{(t)}$ :

$$ \hat{\theta}^{(t+1)} = \hat{\theta}^{(t)} - \alpha \nabla C_n(\hat{\theta}^{(t)}), \quad (3.2) $$

où $\nabla C_n(\hat{\theta}^{(t)})$ est le gradient de $C_n$ au point $\hat{\theta}^{(t)}$; $\hat{\theta}^{(0)} = \theta^{(0)}$ est l'initialisation de l'algorithme GD; $\forall \theta \in \mathbb{R}^d$, $C_n(\theta) = \frac{1}{2n} \|Y - X\theta\|_{2,n}^2$.

À l'aide de l'équation (3.2), nous obtenons une formule close de $\hat{\theta}^{(t)}$ :

$$ \hat{\theta}^{(t)} = \left( I_d - \left(I_d - \frac{\alpha}{n} X^T X\right)^t \right) \hat{\theta}_n + \left( I_d - \frac{\alpha}{n} X^T X \right)^t \theta^{(0)}, \quad (3.3) $$

où $\hat{\theta}_n$ est l'estimateur des moindres carrés.

**Approximation standard de l'EMC** Comme pour $\alpha \in ]0, \frac{1}{\lambda_1}]$, $[\hat{\theta}^{(t)} \underset{t \to +\infty}{\longrightarrow} \hat{\theta}_n = (X^T X)^{-1} X^T Y$, une approximation de l'EMC $\hat{\theta}_\kappa$ est égale à $\hat{\theta}^{(\hat{t}_\kappa)}$ où $\hat{t}_\kappa$ est défini par

$$ \hat{t}_\kappa = \min \left\{ t \in \mathbb{N} : \frac{\| \hat{\theta}^{(t+1)} - \hat{\theta}^{(t)} \|_{2,d}}{\| \hat{\theta}^{(t)} \|_{2,d}} \le \kappa \right\}, $$

où $\kappa$ est un seuil que l'utilisateur doit choisir; $\lambda_1 \ge \dots \lambda_n \ge 0$ sont les valeurs propres de $\frac{1}{n}XX^T$.

$\hat{t}_\kappa$ correspond à l'itération $t$ où $\hat{\theta}^{(t)}$ devient "proche" de l'EMC $\hat{\theta}_n$. En effet, lorsque l'on cherche à approcher un estimateur asymptotique (e.g. $\hat{\theta}_n$ pour l'algorithme de descente de gradient), il est d'usage de stopper l'algorithme lorsque l'écart relatif entre $\hat{\theta}^{(t+1)}$ et $\hat{\theta}^{(t)}$ est plus petit qu'un seuil $\kappa$.

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

Le point délicat est de déterminer quand stopper l'algorithme GD. Cette partie a pour but de justifier l'utilisation de la règle d'arrêt $\hat{t}$ afin d'obtenir un estimateur $\hat{\theta}^{(\hat{t})}$ plus précis et moins coûteux en temps de calcul que $\hat{\theta}_\kappa$.

Nous évaluons la précision de $\hat{\theta}^{(t)}$ par
$$ \begin{cases} \Delta(\hat{Y}^{(t)}) = \frac{1}{n} \|\hat{Y}^{(t)} - Y^*\|_{2,n}^2 \\ \text{ou} \\ \text{EQM}(\hat{Y}^{(t)}) = E_\epsilon[\Delta(\hat{Y}^{(t)})] \end{cases} $$
, où $\hat{Y}^{(t)} = X\hat{\theta}^{(t)}$. On calcule $E_\epsilon$ en intégrant par rapport à la loi de probabilité de $\epsilon$.

Comme $\Delta(\hat{Y}^{(t^*)}) \le \Delta(\hat{Y}_\kappa)$ pour $t^* = \underset{t \in \mathbb{N}}{\operatorname{argmin}}\{\Delta(\hat{Y}^{(t)})\}$ et $\hat{Y}_\kappa = X\hat{\theta}_\kappa$ alors $E_\epsilon[\Delta(\hat{Y}^{(t^*)})] \le E_\epsilon[\Delta(\hat{Y}_\kappa)]$. Ainsi l'estimateur $\hat{Y}_\kappa = X\hat{\theta}_\kappa$ est sous optimale en matière d'erreur moyenne quadratique. Cette sous optimalité est expliquée par la propriété 3.1.1 qui traduit un phénomène de surapprentissage lorsque le nombre d'itérations $t$ augmente (e.g. $\hat{t}_\kappa$ augmente pour $\kappa$ suffisamment petit). En effet, $E_\epsilon[\Delta(\hat{Y}^{(t)})]$ est minorée par une fonction $f$ avec $f(t)$ qui tend vers $\sigma^2d/(4n)$ lorsque $t$ tend
vers $+\infty$. Par conséquent, si nous réalisons trop d'itérations, la précision statistique de $\hat{\theta}^{(t)}$ se dé-
tériore. Ce phénomène de surapprentissage se produit lorsque le nombre d'itérations $t$ augmente
car $\hat{Y}^{(t)} = X\hat{\theta}^{(t)} \xrightarrow{t \to +\infty} \hat{Y} = X\hat{\theta}_n$ et $\hat{Y}$ est la projection orthogonale de $Y$ sur l'image de $X$. Ainsi,
une règle d'arrêt est utile pour stopper l'algorithme avant le phénomène de surapprentissage.

**Propriété 3.1.1.** $\forall t \in \mathbb{N}$,

$$
E_{\epsilon} [\Delta(\hat{Y}^{(t)})] \geq \frac{\sigma^2}{4n} \underbrace{\sum_{j=1}^{d} \min\{1, (t\alpha\hat{\lambda}_j)^2\}}_{f(t)}.
$$

La preuve de la propriété 3.1.1 est disponible dans la partie 3.4.2.

Idéalement, la règle d'arrêt $\hat{t}$ a pour objectif d'estimer $t^* = \underset{t \in \mathbb{N}}{\operatorname{argmin}} \{\Delta(\hat{Y}^{(t)})\}$ car c'est plus précis de minimiser la distance Euclidienne entre $\hat{Y}^{(t)}$ et $Y^*$. Ainsi, $\hat{t}$ est choisie telle que $\Delta(\hat{Y}^{(\hat{t})})$ est minimale et l'on peut attendre que $\Delta(\hat{Y}^{(\hat{t})}) \le \Delta(\hat{Y}_K)$.

**3.1.3 Interprétation**

Dans cette partie, nous montrons que $\bar{t} = \underset{t \in \mathbb{N}}{\operatorname{argmin}} \{\operatorname{EQM}(\hat{Y}^{(t)})\}$ peut être interprété comme un compromis biais-variance. La propriété 3.1.2 montre que lorsque $n$ tend vers $+\infty$, $\Delta(\hat{Y}^{(t)})$ converge en probabilité vers $E_{\epsilon}[\Delta(\hat{Y}^{(t)})]$. Ainsi, la règle d'arrêt $\hat{t}$, qui estime $t^* = \underset{t \in \mathbb{N}}{\operatorname{argmin}} \{\Delta(\hat{Y}^{(t)})\}$, traduit un compromis biais-variance car $\Delta(\hat{Y}^{(t)})$ est “proche” de $E_{\epsilon}[\Delta(\hat{Y}^{(t)})]$ lorsque $n$ est suffisamment grand.

La figure 3.2 peut être interprétée comme un compromis biais-variance. En effet, d'après l'équation (3.4), EQM($\hat{Y}^{(t)}$) peut être décomposée en la somme du biais au carré de $\hat{Y}^{(t)}$ et de la variance de $\hat{Y}^{(t)}$, notés $b(\hat{Y}^{(t)})^2$ et var($\hat{Y}^{(t)}$) respectivement.

$$
\operatorname{EQM}(\hat{Y}^{(t)}) = \underbrace{\frac{1}{n} \left\| E_{\epsilon}[\hat{Y}^{(t)}] - Y^{*} \right\|_{2,n}^{2}}_{b(\hat{Y}^{(t)})^2} + \underbrace{E_{\epsilon} \left[ \frac{1}{n} \left\| \hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}] \right\|_{2,n}^{2} \right]}_{\operatorname{var}(\hat{Y}^{(t)})} . \quad (3.4)
$$

La figure 3.2 montre que $t \mapsto b(\hat{Y}^{(t)})^2$ décroît alors que $t \mapsto \operatorname{var}(\hat{Y}^{(t)})$ croît. En effet, à l'itération $t=0$, $b(\hat{Y}^{(t)})^2$ est grand ($b(\hat{Y}^{(0)})^2 = \frac{1}{n}\|Y^* - Y^{(0)}\|_{2,n}^2$) alors que $\operatorname{var}(\hat{Y}^{(t)})$ est égale à 0. Inversement, lorsque $t$ tend vers $+\infty$, $b(\hat{Y}^{(t)})^2$ tend vers 0 tandis que $\operatorname{var}(\hat{Y}^{(t)})$ tend vers $\operatorname{var}(\hat{Y}) = \frac{\sigma^2 d}{n}$ où $\hat{Y} = X\hat{\theta}_n$. Ainsi $\bar{t}$ minimise la somme de $t \mapsto b(\hat{Y}^{(t)})^2$ et $t \mapsto \operatorname{var}(\hat{Y}^{(t)})$ et ces deux fonctions sont de sens de variation contraire. Par conséquent, $\bar{t}$ traduit un compromis biais-variance.

La propriété suivante justifie que $\Delta(\hat{Y}^{(t)})$ est “proche” de $E_{\epsilon}[\Delta(\hat{Y}^{(t)})]$ lorsque $n$ est suffisamment grand. De plus, comme $\hat{t}$ estime $t^*$ alors $\hat{t}$ traduit un compromis biais-variance.

**Propriété 3.1.2.** D'après l'inégalité de Markov, lorsque $t$ est fixé, $\Delta(\hat{Y}^{(t)})$ converge en probabilité vers $E_{\epsilon}[\Delta(\hat{Y}^{(t)})]$ lorsque $n$ tend vers $+\infty$, i.e. $\forall \delta > 0$, $P(|\Delta(\hat{Y}^{(t)}) - E_{\epsilon}[\Delta(\hat{Y}^{(t)})]| \ge \delta)$ tend vers 0 lorsque $n$ tend vers $+\infty$.

La preuve de la propriété 3.1.2 est disponible dans la partie 3.4.3.
<figure><img src="image_21.png" /><figcaption>FIGURE 3.2 – 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$.</figcaption></figure>

La figure 3.3 illustre la propriété 3.1.2 où nous observons 3 trajectoires de $t \mapsto \Delta(\hat{Y}^{(t)})$ concentrées autour de son espérance $t \mapsto E[\Delta(\hat{Y}^{(t)})]$ lorsque $n$ est suffisamment grand.

Dans la suite, nous proposons une majoration de $t \mapsto \Delta(\hat{Y}^{(t)})$ par un terme de biais et un terme de variance. Puis, $\hat{t}$ est définie afin de minimiser cette majoration et donc de minimiser $t \mapsto \Delta(\hat{Y}^{(t)})$.

### 3.1.4 Contrôle du biais et de la variance

La règle d'arrêt $\hat{t}$ a pour but de minimiser $t \mapsto \Delta(\hat{Y}^{(t)})$. Comme il est difficile de minimiser directement $t \mapsto \Delta(\hat{Y}^{(t)})$, nous minimisons une majoration de cette fonction. D'après l'équation (3.5), nous pouvons majorer $\Delta(\hat{Y}^{(t)})$ par un terme de biais $B_t^2$ et un terme de variance $V_t$

$$ \Delta(\hat{Y}^{(t)}) \le \underbrace{\frac{2}{n} \|E[\hat{Y}^{(t)}] - Y^*\|_{2,n}^2}_{B_t^2} + \underbrace{\frac{2}{n} \|\hat{Y}^{(t)} - E[\hat{Y}^{(t)}]\|_{2,n}^2}_{V_t} \quad (3.5) $$

car d'après l'inégalité triangulaire, $\forall a, b \in \mathbb{R}^n$, $\|a + b\|_{2,n}^2 \le 2\|a\|_{2,n}^2 + 2\|b\|_{2,n}^2$.

Comme il est difficile de minimiser $t \mapsto B_t^2 + V_t$, nous majorons $B_t^2$ et $V_t$ grâce aux lemmes 3.1.1 et 3.1.2.

**Lemme 3.1.1.** Si $\|\theta^*\|_{2,d} \le 1$ et $\theta^{(0)} = 0, \forall t \in \mathbb{N}$,

$$ B_t^2 \le 2 \sum_{j=1}^{d} \hat{\lambda}_j \rho_j^{2t} := B_t^{2, \mathrm{sup}}, \quad (3.6) $$

où $\forall j \in [1, d]$, $\rho_j = 1 - \alpha \hat{\lambda}_j$.
<figure><img src="image_22.png" /></figure>

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

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

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

FIGURE 3.3 – Figures 3.3a, 3.3b, 3.3c et 3.3d : Tracé de 3 trajectoires de $\Delta(\hat{Y}^{(t)})$ et $E_{\epsilon}[\Delta(\hat{Y}^{(t)})]$ en fonction de $t$ pour $d=20$ et pour $n=25, 200, 500, 1000$ respectivement. Les paramètres sont $\alpha = 0.01$ et $\text{SNR} = 2 \approx \frac{\|X\theta^*\|_{2,d}}{\|\epsilon\|_{2,n}}$.

Dans les travaux existants sur les règles d'arrêt (RASKUTTI, WAINWRIGHT et YU 2014; YAO, ROSASCO et CAPONNETTO 2007), il est classique de faire une hypothèse sur la fonction de régression pour majorer le terme de biais. Nous supposons donc $\|\theta^*\|_{2,d} \le 1$ pour majorer le terme de biais $B_t^2$ car $B_t^2$ dépend de $\theta^*$.

Nous établissons maintenant une majoration de $V_t$ qui est valable avec grande probabilité jusqu'à l'itération $t_{max}$. $t_{max}$ correspond au nombre maximum d'itérations que l'utilisateur peut réaliser en un temps prescrit donné.
**Lemme 3.1.2.** $\exists C_1 > 0 \text{ telle que, } \forall z > 0, \text{ avec une probabilité d'au moins } 1 - e^{-z}, \forall t \in [0, t_{\max}]$,

$$V_t \le 2E_\epsilon [V_t] + C_1 \frac{(z + \log (t_{\max} + 1))}{n} \quad (3.7)$$

$$\text{et } 2E_{\epsilon}[V_t] \le \frac{4\sigma^2}{n} \sum_{j=1}^{d} \min \left\{ 1, (t\alpha\hat{\lambda}_j)^2 \right\} =: V_t^{sup}.$$

Les preuves des lemmes 3.1.1 et 3.1.2 sont disponibles dans les parties 3.4.4 et 3.4.5 respectivement.

D'après les lemmes 3.1.1 et 3.1.2, le majorant du terme de biais $B_t^{2,\text{sup}}$ et du terme de variance $V_t^{\text{sup}}$ expliquent la dynamique de $t \mapsto B_t^2$ et $t \mapsto V_t$. En effet, nous observons sur la figure 3.2 la décroissance exponentielle de $t \mapsto B_t^2$ et le fait que $\{B_t^2\}_{t \in \mathbb{N}}$ converge vers 0 lorsque $t$ tend vers $+\infty$ comme la fonction $t \mapsto B_t^{2,\text{sup}}$. De plus, nous observons sur la figure 3.2 que $E_\epsilon[V_t] = 2\text{var}(\hat{Y}^{(t)})$ est quadratique en $t$ lorsque $t$ est petit et converge vers une limite finie lorsque $t$ tend vers $+\infty$ comme la fonction $t \mapsto V_t^{\text{sup}}$.

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

Nous définissons dans cette partie la règle d'arrêt $\hat{t}$ comme un point de minimum d'un majorant de $\Delta(\hat{Y}^{(t)})$ afin de minimiser $t \mapsto \Delta(\hat{Y}^{(t)})$.

D'après les équations (3.6) et (3.7), nous obtenons une majoration de $\Delta(\hat{Y}^{(t)})$, avec une probabilité d'au moins $1 - e^{-z}, \forall t \in [0, t_{\max}]$,

$$\Delta(\hat{Y}^{(t)}) \le B_t^{2,\text{sup}} + 2E_\epsilon[V_t] + C_1 \frac{(z + \log (t_{\max} + 1))}{n}. \quad (3.8)$$

La règle d'arrêt $\hat{t}$ a pour objectif de minimiser la majoration proposée dans l'équation (3.8) afin de minimiser $t \mapsto \Delta(\hat{Y}^{(t)})$. Comme le troisième terme de la majoration de $\Delta(\hat{Y}^{(t)})$ ne dépend pas de $t$, $\hat{t}$ doit minimiser $B_t^{2,\text{sup}} + 2E_\epsilon[V_t]$. Comme $E_\epsilon[V_t]$ dépend de la variance du terme d'erreur, nous remplaçons $\sigma^2$ par l'un de ses estimateurs $\hat{\sigma}^2$. Ainsi, la règle d'arrêt $\hat{t}$ est la première itération telle que $t \mapsto B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t]$ cesse de décroître où $\hat{E}_\epsilon[V_t] = \frac{2\hat{\sigma}^2}{n} \sum_{j=1}^d (1 - (1 - \alpha\hat{\lambda}_j)^t)^2$; $E_\epsilon[V_t] = \frac{2\sigma^2}{n} \sum_{j=1}^d (1 - (1 - \alpha\hat{\lambda}_j)^t)^2$. Formellement, $\hat{t}$ est définie par :

$$\hat{t} = \min \left\{ t \in \mathbb{N} : B_{t+1}^{2,\text{sup}} + 2\hat{E}_\epsilon[V_{t+1}] > B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t] \right\}.$$

Nous supposons que $t \mapsto B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t]$ n'admet que des points de minimum globaux. Nous avons fait des simulations pour justifier cette hypothèse. Pour $d = 20$, les figures 3.4a, 3.4b, 3.4c et 3.4d représentent $t \mapsto B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t]$ en fonction du nombre d'itérations $t$ pour $n = 25, 50, 100, 500$ respectivement. Nous observons sur ces figures que $t \mapsto B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t]$ admet un unique point de minimum global. Au vu de ces simulations, nous supposons donc que $t \mapsto B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t]$ n'admet que des points de minimum globaux.

$\hat{t}$ traduit un compromis biais-variance car $t \mapsto B_t^{2,\text{sup}}$ et $t \mapsto \hat{E}_\epsilon[V_t]$ sont monotones de sens de variation contraire. De plus, $\hat{t}$ est définie telle que $\Delta(\hat{Y}^{(\hat{t})})$ est minimale. Par conséquent, on peut attendre à observer sur les simulations que $\hat{Y}^{(\hat{t})}$ est plus précis que $\hat{Y}_\kappa$ en matière d'erreur moyenne quadratique.
<figure><img src="image_26.png" /><figcaption>FIGURE 3.4 – Figures 3.4a, 3.4b, 3.4c et 3.4d : Graphiques de $t \mapsto B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t]$ en fonction de l'itération $t$ pour $d = 20$ et pour $n = 25, 50, 100, 500$ respectivement. Les paramètres sont $\alpha = 0.01$ et $\text{SNR} = 1 \approx \frac{\|X\theta^*\|_{2,d}}{\|\epsilon\|_{2,n}}$.</figcaption></figure>

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

Dans cette partie, nous donnons des éléments suggérant que la règle d'arrêt $\hat{t}$ croît en $\log(n)$.

**Propriété 3.1.3.** $\exists M_1, M_2, M_3, M_4 \in \mathbb{R}_+^*$ tel que, sur un événement de grande probabilité, pour $n$ suffisamment grand,

$$M_1 + M_2 \log(n) \le t^* \le M_3 + M_4 \log(n).$$

La preuve de la propriété 3.1.3 est disponible dans la partie 3.4.6.
La figure 3.5 illustre la propriété 3.1.3 où l'on observe que $\frac{t^*}{\log(n)}$ reste bornée lorsque $n$ est suffisamment grand. La propriété 3.1.3 suggère que $\hat{t}$ est de l'ordre de $\log(n)$ pour $n$ suffisamment grand. Donc, cela suggère que la règle d'arrêt $\hat{t}$ croît lentement avec $n$ et donc $\hat{\theta}^{(\hat{t})}$ est peu coûteux en temps de calcul.

<figure><img src="image_27.png" /><figcaption>FIGURE 3.5 – Graphique de $\frac{t^*}{\log(n)}$ en fonction de $n$ pour $d = 20$, SNR=2 $\approx \frac{\|X\theta^*\|_{2,d}}{\|\epsilon\|_{2,n}}$ et $\alpha = 0.01$.</figcaption></figure>

# 3.2 Résultats numériques

Nous présentons dans cette partie les objectifs des simulations et le cadre de simulations. Puis, nous interprétons les résultats des simulations obtenues.

## 3.2.1 Objectifs

L'objectif de ces simulations est de comparer la performance statistique de $\hat{\theta}^{(\hat{t})}$ et $\hat{\theta}_\kappa$ pour $\kappa = 10^{-7}$ afin de déterminer si l'estimateur $\hat{\theta}^{(\hat{t})}$ est plus précis qu'une approximation de l'estimateur des moindres carrés $\hat{\theta}_\kappa$. On compare également la performance statistique de l'estimateur $\hat{\theta}^{(\hat{t})}$ à celle de l'estimateur des moindres carrés $\hat{\theta}_n$, ce dernier étant très utilisé dans le cadre étudié. Cette performance statistique est mesurée par le gain relatif $\text{GainRel}(\tilde{Y})$ défini par

$$ \text{GainRel}(\tilde{Y}) = \frac{\text{EQM}(\tilde{Y}) - \text{EQM}(\hat{Y})}{\text{EQM}(\hat{Y})}, $$

où $\tilde{Y}$ est l'estimateur auquel on compare l'estimateur proposé. Ici, $\tilde{Y}$ est égal à $\hat{Y}_\kappa$ ou $\hat{Y}$. Nous comparons aussi le temps de calcul de $\hat{\theta}^{(\hat{t})}$ et $\hat{\theta}_\kappa$ en faisant varier la valeur de $\kappa \in \{10^{-3}, 10^{-7}, 10^{-11}\}$. Il est à noter que $\hat{\theta}^{(\hat{t})}$ et $\hat{\theta}_\kappa = \hat{\theta}^{(\hat{t}_\kappa)}$ sont calculés à l'aide de l'équation (3.2) car on souhaite se placer dans le cas où l'on ne dispose pas de formules explicites de $\hat{\theta}^{(\hat{t})}$, cas fréquemment rencontré en pratique. Nous comparons également le temps de calcul de $\hat{\theta}^{(\hat{t})}$ à celui de l'estimateur des moindres carrés $\hat{\theta}_n$.
### 3.2.2 Cadre de simulations

Pour $d \in \{20,100\}$, nous générons $\forall i \in [1,n] : x_i^T \sim N(0,\Sigma)$ où $\Sigma \in M_d(\mathbb{R})$ est une matrice diagonale avec sa plus grande valeur propre égale à 5 et sa plus petite valeur propre égale à 1. $\epsilon \sim N(0,\sigma^2 I_n)$ où $\sigma^2$ est choisie telle que $\text{SNR}^2 = \frac{(\theta^*)^T \Sigma \theta^*}{\sigma^2} \approx \frac{\|X\theta^*\|_{2,n}^2}{\|\epsilon\|_{2,n}^2}$. Pour $d=20$, $n$ varie de 25 jusqu'à 1000. Pour $d=100$, $n$ varie de 110 à 1000. $\alpha = 0.01$ est indépendant de $n$ et $\alpha \in ]0, \frac{1}{\lambda_1}$ [pour toutes les valeurs de $n$ testées. Le nombre $B$ de répétitions du terme d'erreur est égal à 100.

### 3.2.3 Interprétation

Dans un premier temps, nous comparons les estimateurs $\hat{Y}^{(t)}$ et $\hat{Y}_\kappa$ en matière d'erreur moyenne quadratique. Pour $d \in \{20,100\}$, pour $\kappa = 10^{-7}$, nous observons sur les figures 3.7a, 3.7c et 3.10a, 3.10c que le gain relatif de $\hat{Y}^{(t)}$ est strictement positif pour une taille d'échantillons $n$ proche de $d$ lorsque la référence est $\check{Y} = \hat{Y}_\kappa$. Ce gain relatif est plus élevé lorsque le rapport signal à bruit SNR est égal à 1, i.e. lorsque la variance du terme d'erreur est grande. Pour SNR = 1, ce gain relatif est de 0.2 et 0.1 pour $n$ proche de $d$ pour $d = 20$ et $d = 100$ respectivement. Pour SNR = 4, ce gain relatif est de l'ordre de 0.02 pour $d = 20$ et $d = 100$. On observe aussi que la courbe du gain relatif de $\hat{Y}^{(t)}$ a la même allure de courbe que celle du gain relatif de $\hat{Y}^{(t*)}$. Ainsi, on observe que l'erreur moyenne quadratique de $\hat{Y}^{(t)}$ est inférieure à celle de $\hat{Y}_\kappa$ lorsque $n$ est proche de $d$. La situation où $n$ est proche de $d$ et la variance du terme d'erreur est grande correspond au cas où l'EMC n'est pas un bon estimateur de $\theta^*$. Il est donc intéressant de disposer de l'estimateur $\hat{\theta}^{(t)}$ ayant une meilleure précision statistique que $\hat{\theta}_\kappa$.

Nous avons aussi comparé $\hat{\theta}^{(t)}$ et l'estimateur des moindres carrés $\hat{\theta}_n$ en matière de performance statistique. Les figures 3.8a, 3.8c, 3.9a et 3.9c représentent le gain relatif de $\hat{Y}^{(t)}$ en fonction de $n$ lorsque la référence est $\check{Y} = \hat{Y}$ pour $d \in \{20,100\}$. Pour SNR = 1, ce gain relatif est de 0.2 et 0.1 lorsque $n$ est proche de $d$ pour $d = 20$ et $d = 100$ respectivement. De même que lorsque la référence est $\check{Y} = \hat{Y}_\kappa$, on observe que le gain relatif de $\hat{Y}^{(t)}$ est positif lorsque $n$ est proche de $d$ et que le gain relatif est d'autant plus élevé, lorsque $n$ est proche de $d$, que le rapport signal à bruit (SNR) est proche de 1. On observe aussi sur les figures 3.8a et 3.8c que la courbe du gain relatif de $\hat{Y}^{(t)}$ a la même allure de courbe que celle du gain relatif de $\hat{Y}^{(t*)}$. On observe également sur les figures 3.8a, 3.8c, 3.9a et 3.9c que, lorsque $\check{Y} = \hat{Y}$, l'estimateur $\hat{Y}^{(t)}$ est meilleur que l'estimateur des moindres carrés pour certaines valeurs élevées de $n$.

Dans un deuxième temps, nous comparons les estimateurs $\hat{\theta}^{(t)}$ et $\hat{\theta}_\kappa$ en matière de performance en temps de calcul. À $n$ fixé, lorsque $\kappa$ diminue, $\hat{f}_\kappa$ augmente et donc le temps de calcul de $\hat{\theta}_\kappa$ augmente. Ce phénomène est illustré pour $d \in \{20,100\}$ par les figures 3.7b, 3.7d et 3.10b où l'on observe que, pour $\kappa \in \{10^{-7}, 10^{-11}\}$, le temps de calcul de $\hat{\theta}_\kappa$ est supérieur au temps de calcul de $\hat{\theta}^{(t)}$. On observe aussi sur la figure 3.10d que les temps de calcul $\hat{\theta}_\kappa$ et de $\hat{\theta}^{(t)}$ sont du même ordre de grandeur.

Nous comparons également l'estimateur $\hat{\theta}^{(t)}$ et l'estimateur des moindres carrés $\hat{\theta}_n$ en matière de performance en temps de calcul. Les figures 3.8b, 3.8d, 3.9b et 3.9d représentent l'évolution du temps de calcul de $\hat{\theta}^{(t)}$ et $\hat{\theta}_n$ en fonction de $n$ pour $d \in \{20,100\}$ et SNR $\in \{1,4\}$. Comme l'estimateur des moindres carrés a une formule explicite et le calcul de $\hat{\theta}^{(t)}$ nécessite d'itérer l'algorithme GD jusqu'à la règle d'arrêt $\hat{f}$, le temps de calcul de $\hat{\theta}^{(t)}$ est supérieur à celui de l'estimateur des moindres carrés $\hat{\theta}_n$.
Nous illustrons à l'aide de la figure 3.6 le comportement de $t^*$, $\hat{t}$ et $\hat{t}_\kappa$ en fonction de $n$. Cette figure représente, pour différentes valeurs de $n$, $\Delta(\hat{Y}^{(t)})$, $B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t]$ en fonction du nombre d'itérations $t$. On a positionné également sur cette figure $t^*$, $\hat{t}$ et $\hat{t}_\kappa$. On observe que $\hat{t}_\kappa$ est plus éloigné de $t^*$ que $\hat{t}$. De plus, on observe, pour $n \in \{100, 500\}$, que $t^*$ et $\hat{t}$ augmentent lentement. La figure 3.6 illustre la propriété 3.1.3 suggérant que $\hat{t}$ croît en $\log(n)$ pour $n$ suffisamment grand. Ainsi, lorsque $n$ augmente, le temps de calcul de $\hat{\theta}^{(t)}$ aura tendance à être inférieur à $\hat{\theta}_\kappa$. De plus, on observe que $\hat{t}_\kappa$ se situe lorsque le phénomène de surapprentissage se produit et donc lorsque la précision statistique de $\hat{\theta}_\kappa$ se détériore. On aura tendance donc à avoir un estimateur $\hat{\theta}^{(t)}$ ayant une meilleure précision statistique et moins coûteux en temps de calcul que $\hat{\theta}_\kappa$.

<figure><img src="image_28.png" /><figcaption>FIGURE 3.6 – Figures 3.6a, 3.6b, 3.6c et 3.6d : Graphiques de $\Delta(\hat{Y}^{(t)})$ (en bleu foncé), $B_t^{2,\text{sup}} + 2\hat{E}_\epsilon[V_t]$ (en bleu clair) en fonction de l'itération $t$ pour $d = 20$, pour $\kappa = 10^{-7}$, pour $n = 25, 50, 100, 500$ respectivement.</figcaption></figure>
## 3.3 Conclusion

Dans le cadre du problème de régression linéaire, nous avons proposé un estimateur, construit à partir de la règle d'arrêt $\hat{t}$, qui a une meilleure performance statistique et est moins coûteux en temps de calcul que l'estimateur usuel $\hat{\theta}_{\kappa} = \hat{\theta}^{(\hat{t}_{\kappa})}$ pour $\kappa = 10^{-7}$ lorsque $n$ est proche de $d$. Nous observons également que l'estimateur $\hat{\theta}^{(t)}$ a une meilleure performance statistique que l'estimateur des moindres carrés $\hat{\theta}_n$ lorsque $n$ est proche de $d$ et pour certaines valeurs élevées de $n$. La situation où $n$ est proche de $d$ correspond au cas où l'EMC (et donc aussi une approximation de l'EMC $\hat{\theta}_{\kappa}$) n'est pas un bon estimateur de $\theta^*$. Nous avons donc observé dans un cas simple, où l'estimateur du risque empirique est moins performant, qu'une règle d'arrêt permet d'améliorer la précision statistique de la famille $\{\hat{\theta}^{(t)}\}_{t \in \mathbb{N}}$. De plus, les simulations montrent que, pour $\kappa = 10^{-7}$, $\hat{t}_{\kappa}$ est grand comparativement à $\hat{t}$. Ainsi, le temps de calcul de $\hat{\theta}^{(t)}$ aura tendance à être inférieur à $\hat{\theta}_{\kappa}$.

En perspective, nous pouvons chercher à étendre les résultats obtenus au cadre de la régression non-paramétrique car nous nous sommes inspirés d'une règle d'arrêt dans ce contexte (RASKUTTI, WAINWRIGHT et Yu 2014).

## 3.4 Preuves

Dans cette partie, nous donnons les preuves des propriétés et lemmes énoncés dans ce chapitre. Ces résultats sont valables lorsque $\forall i \in [1, n]$, $\epsilon_i \sim \mathcal{G}(\sigma^2)$, i.e. $\epsilon_i$ suit une loi sous-Gaussienne de paramètre $\sigma^2$. Ils sont donc en particulier valables si $\forall i \in [1, n]$, $\epsilon_i \sim \mathcal{N}(0, \sigma^2)$.

### 3.4.1 Formules closes de $\hat{\theta}^{(t)}$ et $\hat{Y}^{(t)}$

Dans un premier temps, nous calculons le gradient de $C_n : \forall \theta, H \in \mathbb{R}^d$,

$$ 
\begin{align*}
C_n(\theta + H) &= \frac{1}{2n} \|Y - X(\theta + H)\|_{2,n}^2 \\
&= \frac{1}{2n} \|Y - X\theta\|_{2,n}^2 + \frac{1}{2n} \|XH\|_{2,n}^2 - \frac{1}{n} \langle XH, Y - X\theta \rangle_{\mathbb{R}^n} \\
&= C_n(\theta) + \frac{1}{n} \langle X^T X\theta - X^T Y, H \rangle_{\mathbb{R}^n} + o(\|H\|_{2,d}),
\end{align*}
$$

$$ \text{car } \|XH\|_{2,n}^2 = o(\|H\|_{2,d}). $$

$$ \text{Ainsi, } \forall H \in \mathbb{R}^d, d(C_n)\theta(H) = \frac{1}{n}\langle X^T X\theta - X^T Y, H \rangle_{\mathbb{R}^n} = \langle \nabla C_n(\theta), H \rangle_{\mathbb{R}^n} \Rightarrow \nabla C_n(\theta) = \frac{1}{n}X^T X\theta - \frac{1}{n}X^T Y. $$

$$ \text{Puis, nous utilisons la relation entre } \hat{\theta}^{(t)} \text{ et } \hat{\theta}^{(t-1)}, \forall t \ge 1, $$

$$ 
\begin{align*}
\hat{\theta}^{(t)} &= \hat{\theta}^{(t-1)} - \alpha \nabla C_n(\hat{\theta}^{(t-1)}) \\
&= \hat{\theta}^{(t-1)} - \frac{\alpha}{n} [X^T X \hat{\theta}^{(t-1)} - X^T Y] \\
&= [I_d - \frac{\alpha}{n} X^T X] \hat{\theta}^{(t-1)} + \frac{\alpha}{n} X^T Y.
\end{align*}
$$
<figure><img src="image_29.png" /></figure>

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

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

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

FIGURE 3.7 – Figures 3.7a et 3.7c : Graphiques du gain relatif de $\hat{Y}^{(t)}$ et $\hat{Y}^{(t^*)}$ en fonction de $n$ pour $d = 20$ et $\text{SNR} \in \{1, 4\}$ lorsque $\hat{Y} = \hat{Y}_\kappa$. Figures 3.7b et 3.7d : Graphiques du temps de calcul de $\hat{\theta}^{(t)}$ et $\hat{\theta}_\kappa$ en fonction de $n$ pour $d = 20$, $\text{SNR} \in \{1, 4\}$ et $\kappa \in \{10^{-3}, 10^{-7}, 10^{-11}\}$.

Nous remarquons que $\forall t \ge 2$,

$$ \hat{\theta}^{(t)} = \left[ I_d - \frac{\alpha}{n} X^T X \right] \hat{\theta}^{(t-1)} + \frac{\alpha}{n} X^T Y $$

$$ \hat{\theta}^{(t-1)} = \left[ I_d - \frac{\alpha}{n} X^T X \right] \hat{\theta}^{(t-2)} + \frac{\alpha}{n} X^T Y $$

$$ \Rightarrow \hat{\theta}^{(t)} - \hat{\theta}^{(t-1)} = \left[ I_d - \frac{\alpha}{n} X^T X \right] \left( \hat{\theta}^{(t-1)} - \hat{\theta}_n^{(t-2)} \right) $$

$$ = \left[ I_d - \frac{\alpha}{n} X^T X \right]^{t-1} \left( \hat{\theta}^{(1)} - \theta^{(0)} \right). $$
<figure><img src="image_33.png" /><figcaption>FIGURE 3.8 – Figures 3.8a et 3.8c : Graphiques du gain relatif de $\hat{Y}^{(\hat{t})}$ et $\hat{Y}^{(t^*)}$ en fonction de $n$ pour $d = 20$, SNR$\in\{1,4\}$ et $\hat{Y} = \hat{Y}^*$. Figures 3.8b et 3.8d : Graphiques du temps de calcul de $\hat{\theta}^{(\hat{t})}$ et $\hat{\theta}$ en fonction de $n$ pour $d = 20$, SNR$\in\{1,4\}$.</figcaption></figure>

Par conséquent, nous obtenons $\forall t \ge 1$,

$$ 
\begin{aligned}
\hat{\theta}^{(t)} - \theta^{(0)} &= \sum_{i=0}^{t-1} (\hat{\theta}^{(i+1)} - \hat{\theta}^{(i)}) \\
&= \sum_{i=0}^{t-1} \left( I_d - \frac{\alpha}{n} X^T X \right)^i (\hat{\theta}^{(1)} - \theta^{(0)}).
\end{aligned} 
\quad (3.9) 
$$

$$ \text{Ainsi, } \{\hat{\theta}^{(t)}\}_{t \in \mathbb{N}} \text{ converge} \iff \|I_d - \frac{\alpha}{n} X^T X\|_2 < 1 \Leftrightarrow \alpha \in ]0, \frac{1}{\lambda_1}]. $$
<figure><img src="image_34.png" /></figure>

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

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

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

FIGURE 3.9 – Figures 3.9a et 3.9c : Graphiques du gain relatif de $\hat{Y}^{(t)}$ et $\hat{Y}^{(t^*)}$ en fonction de $n$ pour $d = 100$, $SNR \in \{1, 4\}$ et $\hat{Y} = \hat{Y}^*$. Figures 3.9b et 3.9d : Graphiques du temps de calcul de $\hat{\theta}^{(t)}$ et $\hat{\theta}$ en fonction de $n$ pour $d = 100$, $SNR \in \{1, 4\}$.

Donc, d'après l'équation (3.9)

$$
\begin{align*}
\hat{\theta}^{(t)} - \theta^{(0)} &= \sum_{i=0}^{t-1} \left( I_d - \frac{\alpha}{n} X^T X \right)^i (\hat{\theta}^{(1)} - \theta^{(0)}) \\
&= \left( \frac{\alpha}{n} X^T X \right)^{-1} \left[ I_d - \left( I_d - \frac{\alpha}{n} X^T X \right)^t \right] (\hat{\theta}^{(1)} - \theta^{(0)}) \\
&= \left( \frac{\alpha}{n} X^T X \right)^{-1} \left[ I_d - \left( I_d - \frac{\alpha}{n} X^T X \right)^t \right] \left( -\frac{\alpha}{n} X^T X \theta^{(0)} + \frac{\alpha}{n} X^T Y \right) \\
&= \left[ I_d - \left( I_d - \frac{\alpha}{n} X^T X \right)^t \right] \left( (X^T X)^{-1} X^T Y - \theta^{(0)} \right) \\
\Rightarrow \hat{\theta}^{(t)} &= \left[ I_d - \left( I_d - \frac{\alpha}{n} X^T X \right)^t \right] \left( (X^T X)^{-1} X^T Y - \theta^{(0)} \right) + \theta^{(0)} \\
&= \left[ I_d - \left( I_d - \frac{\alpha}{n} X^T X \right)^t \right] (\hat{\theta}_n - \theta^{(0)}) + \theta^{(0)} \\
&= \left[ I_d - \left( I_d - \frac{\alpha}{n} X^T X \right)^t \right] \hat{\theta}_n + \left( I_d - \frac{\alpha}{n} X^T X \right)^t \theta^{(0)},
\end{align*}
$$
<figure><img src="image_38.png" /><figcaption>FIGURE 3.10 – Figures 3.10a et 3.10c : Graphiques du gain relatif de $\hat{Y}^{(i)}$ et $\hat{Y}^{(t)}$ en fonction de $n$ pour $d = 100$ et $\text{SNR} \in \{1,4\}$ lorsque $\hat{Y} = \hat{Y}_\kappa$. Figures 3.10b et 3.10d : Graphiques du temps de calcul de $\hat{\theta}^{(i)}$ et $\hat{\theta}_\kappa$ en fonction de $n$ pour $d = 100$, $\text{SNR} \in \{1,4\}$ et $\kappa \in \{10^{-3}, 10^{-7}, 10^{-11}\}$.</figcaption></figure>

où $\hat{\theta}_n = (X^T X)^{-1} X^T Y$.

Comme $I_d$ et $X^T X$ commutent, d'après la formule du binôme de Newton, nous obtenons l'expression de $\hat{Y}^{(t)} = X\hat{\theta}^{(t)}$ :

$$ \hat{Y}^{(t)} = \left( I_n - \left( I_n - \frac{\alpha}{n} XX^T \right)^t \right) Y + \left( I_n - \frac{\alpha}{n} XX^T \right)^t Y^{(0)}. \quad (3.10) $$
### 3.4.2 Preuve de la propriété 3.1.1

D'après la propriété 3.4.1 et le lemme 8 (RASKUTTI, WAINWRIGHT et YU 2014), nous avons
$\forall t \ge 0$,

$$
\begin{align*}
E_{\epsilon}[\Delta(\hat{Y}^{(t)})] &= \frac{1}{n} \|S^t Z\|_2^2 + \frac{\sigma^2}{n} \mathrm{Tr}((I_n - S^t)^2) \\
&\geq \frac{\sigma^2}{n} \mathrm{Tr}((I_n - S^t)^2) \\
&\geq \frac{\sigma^2}{n} \sum_{j=1}^{n} (1 - S_{jj}^t)^2 \\
&\geq \frac{\sigma^2}{n} \sum_{j=1}^{d} (1 - S_{jj}^t)^2 \quad \mathrm{car} \ \forall j \in \llbracket d+1, n \rrbracket, \hat{\lambda}_j = 0 \\
&\geq \frac{\sigma^2}{4n} \sum_{j=1}^{d} (\min(1, t\alpha\hat{\lambda}_j))^2.
\end{align*}
$$

**Propriété 3.4.1.** $\forall t \in \mathbb{N}$,

$$
\begin{align*}
\mathrm{EQM}(\hat{Y}^{(t)}) &= E_{\epsilon}[\Delta(\hat{Y}^{(t)})] \\
&= \frac{1}{n} \|S^t Z\|_{2,n}^2 + \frac{\sigma^2}{n} \mathrm{Tr}((I_n - S^t)^2)
\end{align*}
$$

$$où K = \frac{1}{n}XX^T = P\Lambda P^T; Z = P^T X(\theta^{(0)} - \theta^*); S = (I_n - \alpha\Lambda).$$

**Démonstration.** Nous calculons $\mathrm{EQM}(\hat{Y}^{(t)})$

$$
\begin{align*}
\mathrm{EQM}(\hat{Y}^{(t)}) &= E_{\epsilon}[\Delta(\hat{Y}^{(t)})] \\
&= \frac{1}{n} \|E_{\epsilon}[\hat{Y}^{(t)}] - Y^*\|_{2,n}^2 + E_{\epsilon}\left[\frac{1}{n} \|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\|_{2,n}^2\right]
\end{align*}
$$

Pour le terme de biais, nous obtenons d'après l'équation (3.10),

$$
\begin{align*}
E_{\epsilon}[\hat{Y}^{(t)}] &= (I_n - R^t)Y^* + R^t Y^{(0)} \\
\Rightarrow \quad &E_{\epsilon}[\hat{Y}^{(t)}] - Y^* = R^t(Y^{(0)} - Y^*) \\
\Rightarrow \quad &b(\hat{Y}^{(t)})^2 = \frac{1}{n} \|R^t(Y^{(0)} - Y^*)\|_{2,n}^2 \\
&= \frac{1}{n} \|S^t P^T (Y^{(0)} - Y^*)\|_{2,n}^2 \\
&= \frac{1}{n} \|S^t Z\|_{2,n}^2,
\end{align*}
$$

$$où R = I_n - \frac{\alpha}{n}XX^T = PSP^T; S = I_n - \alpha\Lambda; Y^* = X\theta^*; Z = P^T(Y^{(0)} - Y^*).$$
Pour le terme de variance, d'après l'équation (3.10),

$$
\begin{align*}
\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}] &= (I_n - R^t)\epsilon \\
\Rightarrow E_{\epsilon}\left[\frac{1}{n}\left\|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\right\|_{2,n}^2\right] &= \frac{1}{n}\operatorname{Tr}(E_{\epsilon}\left[(I_n - R^t)\epsilon\epsilon^T(I_n - R^t)\right]) \\
&= \frac{\sigma^2}{n}\operatorname{Tr}((I_n - R^t)^2) \\
&= \frac{\sigma^2}{n}\operatorname{Tr}((I_n - S^t)^2),
\end{align*}
$$

□

3.4.3 Preuve de la propriété 3.1.2

Nous montrons dans cette partie que $\Delta(\hat{Y}^{(t)}) = \frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2$ converge en probabilité vers $E_\epsilon[\Delta(\hat{Y}^{(t)})]$ lorsque $n$ tend vers $+\infty$.

On remarque, $\forall t \in \mathbb{N}$,

$$
\begin{align*}
\Delta(\hat{Y}^{(t)}) &= \frac{1}{n} \| E_{\epsilon}[\hat{Y}^{(t)}] - Y^* \|_{2,n}^2 + \frac{1}{n} \| \hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}] \|_{2,n}^2 \\
&\quad + \frac{2}{n} \langle E_{\epsilon}[\hat{Y}^{(t)}] - Y^*, \hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}] \rangle_{\mathbb{R}^n} \\
\Rightarrow \Delta(\hat{Y}^{(t)}) - E_{\epsilon}[\Delta(\hat{Y}^{(t)})] &= \frac{1}{n} \| \hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}] \|_{2,n}^2 + \frac{2}{n} \langle E_{\epsilon}[\hat{Y}^{(t)}] - Y^*, \hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}] \rangle_{\mathbb{R}^n} \\
&\quad - E_{\epsilon} \left[ \frac{1}{n} \| \hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}] \|_{2,n}^2 \right].
\end{align*}
$$

D'après l'inégalité de Markov, $\forall \delta > 0$,

$$
\begin{align*}
P\left(\frac{1}{n}\left\|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\right\|_{2,n}^2 > \delta\right) &\le \frac{E_{\epsilon}\left[\frac{1}{n}\left\|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\right\|_{2,n}^2\right]}{\delta} \\
&\le \frac{\sigma^2 \sum_{j=1}^d (1 - \rho_j^t)^2}{n\delta} \\
\Rightarrow P\left(\frac{1}{n}\left\|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\right\|_{2,n}^2 > \frac{1}{\sqrt{n}}\right) &\le \frac{\sigma^2 d}{\sqrt{n}},
\end{align*}
$$

où $\forall j \in [1, d]$, $\rho_j = 1 - \alpha \hat{\lambda}_j$ et la deuxième ligne provient du calcul de la variance de $\hat{Y}^{(t)}$ (cf. propriété ??).

Sur l'événement $\{\frac{1}{n}\|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\|_{2,n}^2 \le \frac{1}{\sqrt{n}}\}$, on obtient

$$
\begin{align*}
|\Delta(\hat{Y}^{(t)}) - E_{\epsilon}[\Delta(\hat{Y}^{(t)})]| &\le \frac{1}{n} \|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\|_{2,n}^2 + \frac{2}{n} \|E_{\epsilon}[\hat{Y}^{(t)}] - Y^*\|_{2,n} \|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\|_{2,n} \\
&\quad + E_{\epsilon} \left[ \frac{1}{n} \|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\|_{2,n}^2 \right].
\end{align*}
$$
Nous remarquons que, d'après les propriétés 3.4.1 et 3.4.2,

$$
\begin{align*}
\frac{1}{n} \| E_{\epsilon} [\hat{Y}^{(t)}] - Y^{*} \|_{2,n}^{2} &= \frac{1}{n} \sum_{j=1}^{d} Z_{j}^{2} \rho_{j}^{2t} \\
&= \frac{1}{n} \sum_{j=1}^{d} n \hat{\lambda}_{j} \rho_{j}^{2t} (u_{j}^{T} (\theta^{(0)} - \theta^{*}))^{2} \\
&\leq d \hat{\lambda}_{1} \| \theta^{(0)} - \theta^{*} \|_{2,d}^{2},
\end{align*}
$$

car $\forall j \in [1, d]$, $\rho_j \in ]0, 1[$. On remarque que $d\hat{\lambda}_1 \|\theta^{(0)} - \theta^*\|_{2,d}^2$ peut être majorée presque sûrement par une constante G indépendante de $n$. En effet, $\hat{\lambda}_1 = \|\frac{1}{n}X^T X\|_2$ converge presque sûrement vers $\|E_x[xx^T]\|_2$ lorsque $n$ tend vers $+\infty$, où $x \in \mathbb{R}^d$ est un vecteur contenant les variables explicatives. On calcule $E_x[\cdot]$ en intégrant par rapport à la loi de probabilité de $x \in \mathbb{R}^d$.

Ainsi, sur l'événement $\{\frac{1}{n}\|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\|_{2,n}^{2} \le \frac{1}{\sqrt{n}}\}$,

$$
\begin{align*}
|\Delta(\hat{Y}^{(t)}) - E_{\epsilon}[\Delta(\hat{Y}^{(t)})]| &\le \frac{1}{\sqrt{n}} + \frac{2\sqrt{G}}{\sqrt{n}} \|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\|_{2,n} + \frac{\sigma^2 d}{n} \\
&\le \frac{1}{\sqrt{n}} + \frac{2\sqrt{G}}{n^{1/4}} + \frac{\sigma^2 d}{n}
\end{align*}
$$

Comme $P(\frac{1}{n}\|\hat{Y}^{(t)} - E_{\epsilon}[\hat{Y}^{(t)}]\|_{2,n}^2 \le \frac{1}{\sqrt{n}})$ tend vers 1 lorsque $n$ tend vers $+\infty$ et $\frac{1}{\sqrt{n}} + \frac{2\sqrt{G}}{n^{1/4}} + \frac{\sigma^2 d}{n}$ tend vers 0 lorsque $n$ tend vers $+\infty$ alors $\Delta(\hat{Y}^{(t)})$ converge en probabilité vers $E_{\epsilon}[\Delta(\hat{Y}^{(t)})]$ lorsque $n$ tend vers $+\infty$.

3.4.4 Preuve du lemme 3.1.1

**Lemme 3.4.1.** $\forall t \in \mathbb{N}$, ($rg(X) = rg(XX^T) = rg(X^T X) = d$),

$$
\begin{align*}
\Delta(\hat{Y}^{(t)}) &\le \frac{2}{n} \|S^t P^T (Y^* - Y^{(0)})\|_{2,n}^2 + \frac{2}{n} \|(I_n - S^t) P^T \epsilon\|_{2,n}^2 \\
&\le \underbrace{\frac{2}{n} \sum_{j=1}^d (S^t)_{jj}^2 Z_j^2}_{B_t^2} + \underbrace{\frac{2}{n} \sum_{j=1}^d (1 - S_{jj}^t)^2 [P^T \epsilon]_j^2}_{V_t},
\end{align*}
$$

où $Z = P^T(Y^{(0)} - Y^*)$.

Démonstration. D'après l'équation (3.10), $\forall t \in \mathbb{N}$,

$$
\begin{align*}
\hat{Y}^{(t)} - Y^{*} &= P\left[(I_n - S^t) P^T \epsilon + S^t P^T (Y^{(0)} - Y^{*})\right] \\
\Rightarrow \Delta(\hat{Y}^{(t)}) &= \frac{1}{n} \|Y^{(t)} - Y^{*}\|_{2,n}^2 \\
&\le \frac{2}{n} \left\| (I_n - S^t) P^T \epsilon \right\|_{2,n}^2 + \frac{2}{n} \left\| S^t P^T (Y^{(0)} - Y^{*}) \right\|_{2,n}^2,
\end{align*}
$$
car $\forall a, b \in \mathbb{R}^n$, $\|a+b\|_{2,n}^2 \le 2\|a\|_{2,n}^2 + 2\|b\|_{2,n}^2$.
Ainsi, nous obtenons le résultat car

$$
\begin{align*}
B_t^2 &= \frac{2}{n} \left\| S^t P^T (Y^{(0)} - Y^*) \right\|_{2,n}^2 \\
&= \frac{2}{n} \left\| S^t Z \right\|_{2,n}^2 \\
&= \frac{2}{n} \sum_{j=1}^d (S^t)_{jj}^2 Z_j^2 + \frac{2}{n} \sum_{j=d+1}^n Z_j^2 \\
&= \frac{2}{n} \sum_{j=1}^d (S^t)_{jj}^2 Z_j^2 \quad \text{car } \forall j \in [d+1, n], Z_j = 0 \\
V_t &= \frac{2}{n} \left\| (I_n - S^t) P^T \epsilon \right\|_{2,n}^2 \\
&= \frac{2}{n} \sum_{j=1}^d (1 - S_{jj}^t)^2 [P^T \epsilon]_j^2.
\end{align*}
$$

□

**Propriété 3.4.2.** Si $rg(X) = d$, les coordonnées de $Z = P^T(Y^{(0)} - Y^*)$ vérifient

$$
Z_i = \begin{cases} \sqrt{n\lambda_i^{n,d}} u_i^T (\theta^{(0)} - \theta^*), & \text{pour } i \in [1, d] \\ 0, & \text{pour } i \in [d+1, n] \end{cases},
$$

où $u_i$ est le $i^{\text{ème}}$ vecteur propre de $X^T X$ et $\{\lambda_i^{n,d}\}_{i \in [1,d]}$ sont les valeurs propres de $\frac{1}{n} X^T X$.

Démonstration. Soit $p_i$ le $i^{\text{ème}}$ vecteur propre de $K$. Ainsi, les vecteurs propres $(p_1, \dots, p_d)$ de $K = \frac{1}{n}XX^T$ associés avec ses valeurs propres non nulles (i.e. $\{\hat{\lambda}_i\}_{i \in [1,d]}$) forment une famille orthonormée définie par $\forall i \in [1,d]$, $p_i = \frac{Xu_i}{\sqrt{n\lambda_i^{n,d}}}$ où $u_i$ est le $i^{\text{ème}}$ vecteur propre de $X^T X$. Nous remarquons que $\forall i \in [1,d]$, $\hat{\lambda}_i = \lambda_i^{n,d}$.

En effet,

Soit $u$ un vecteur propre de $\frac{1}{n}X^T X$ associé à la valeur propre $\lambda \neq 0$,

$$
\begin{align*}
\frac{1}{n} X^T X u &= \lambda u \\
\Rightarrow \frac{1}{n} X X^T (X u) &= \lambda X u
\end{align*}
$$

Comme $u$ est un vecteur propre de $\frac{1}{n}X^T X$ associé à la valeur propre $\lambda \neq 0 \Rightarrow u \notin \ker(X^T X) = \ker(X) \Rightarrow Xu \neq 0$. Alors, $Xu$ est un vecteur propre de $K$ associé à la valeur propre $\lambda$.
De même, si $u$ est un vecteur propre de $K$ associé à la valeur propre $\lambda \neq 0$,

$$
\begin{align*}
\frac{1}{n} XX^T u &= \lambda u \\
\Rightarrow \frac{1}{n} X^T XX^T u &= \lambda X^T u
\end{align*}
$$
Comme $u$ est un vecteur propre de $K = \frac{1}{n}XX^T$ associé à la valeur propre $\lambda \neq 0 \Rightarrow u \notin \ker(XX^T) = \ker(X^T)$
$\Rightarrow X^T u \neq 0$. Alors, $X^T u$ est un vecteur propre de $\frac{1}{n}X^T X$ associé à la valeur propre $\lambda$.

Si $u_1, u_2$ sont des vecteurs propres de $X^T X$ associés aux valeurs propres $\lambda_1, \lambda_2$ tels que $\langle u_1, u_2 \rangle_{\mathbb{R}^d} = 0$, alors

$$
\begin{align*}
\langle X u_1, X u_2 \rangle_{\mathbb{R}^n} &= \langle X^T X u_1, u_2 \rangle_{\mathbb{R}^d} \\
&= \lambda_1 \langle u_1, u_2 \rangle_{\mathbb{R}^d} \\
&= 0.
\end{align*}
$$

De plus, ||Xu₁||₂,ₙ = ⟨X^T Xu₁, u₁⟩_ℝ^d = λ₁. Le remarques précédentes assurent que (p₁, ..., pₙ) forme une famille orthonormée de vecteurs propres de K.

Nous calculons les coordonnées de Z. Nous remarquons que ∀i ∈ [[d + 1, n]], pᵢ ∈ ker(K).

Par conséquent, nous obtenons ∀i ∈ [[1, d]],

$$
\begin{align*}
(P^T X)_i &= p_i^T X \\
&= (X^T p_i)^T \\
&= \frac{1}{\sqrt{n \lambda_i^{n,d}}} (X^T X u_i)^T \\
&= \sqrt{n \lambda_i^{n,d}} u_i^T.
\end{align*}
$$

De plus, ∀i ∈ [[d + 1, n]],

$$
\begin{align*}
(P^T X)_i &= p_i^T X \\
&= (X^T p_i)^T \\
&= 0,
\end{align*}
$$

$$
\text{car } \forall i \in \llbracket d+1,n \rrbracket, p_i \in \ker(K) = \ker(XX^T) = \ker(X^T). \quad \square
$$

**Lemme 3.4.2.** Si $||\theta^*||_{2,d} \le 1$ et $\theta^{(0)} = 0$, alors $\forall t \in \mathbb{N}$,

$$
B_t^2 \le 2 \sum_{j=1}^{d} \hat{\lambda}_j \rho_j^{2t} :=: B_t^{2,sup}. \qquad (3.11)
$$

Démonstration. D'après le lemme 3.4.1 et la propriété 3.4.2, nous obtenons

$$
\begin{align*}
B_t^2 &= \frac{2}{n} \sum_{j=1}^{d} Z_j^2 \rho_j^{2t} \\
&= \frac{2}{n} \sum_{j=1}^{d} n \hat{\lambda}_j \rho_j^{2t} (u_j^T (\theta^{(0)} - \theta^*)^2) \\
&\le 2 \sum_{j=1}^{d} \hat{\lambda}_j \rho_j^{2t} \|\theta^{(0)} - \theta^*\|_{2,d}^2,
\end{align*}
$$
d'après l'inégalité de Cauchy-Schwarz.

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

### 3.4.5 Preuve du lemme 3.1.2

**Propriété 3.4.3.** Nous définissons $\mathcal{B}$

$$ \mathcal{B} = \left\{ \forall t \le t_{\max}, V_t < 2E_{\epsilon} [V_t] + \frac{4\sigma^2 (z + \log(t_{\max} + 1))}{c_3 n} \right\}, \quad (3.12) $$

où $c_3$ est une constante strictement positive. Alors, la probabilité de $\mathcal{B}$ est d'au moins $1 - e^{-z}$.

**Démonstration.** Nous remarquons que,

$$ P(\mathcal{B}^c) = P\left(\exists t \le t_{\max}, V_t \ge 2E_{\epsilon} [V_t] + \frac{4\sigma^2 (z + \log(t_{\max} + 1))}{c_3 n}\right) $$

Par conséquent,

$$ \begin{align*} P(\mathcal{B}^c) &= P\left(\exists t \le t_{\max}, V_t \ge 2E_{\epsilon} [V_k] + \frac{4\sigma^2 (z + \log(t_{\max} + 1))}{c_3 n}\right) \\ &= P\left(\bigcup_{t=0}^{t_{\max}} \left\{V_t \ge 2E_{\epsilon} [V_t] + \frac{4\sigma^2 (z + \log(t_{\max} + 1))}{c_3 n}\right\}\right) \\ &\le \sum_{t=0}^{t_{\max}} P\left(V_t \ge 2E_{\epsilon} [V_t] + \frac{4\sigma^2 (z + \log(t_{\max} + 1))}{c_3 n}\right) \\ &\le \sum_{t=0}^{t_{\max}} e^{-z - \log(t_{\max} + 1)} \\ &\le \sum_{t=0}^{t_{\max}} \frac{1}{t_{\max} + 1} e^{-z} \\ &\le e^{-z}, \end{align*} $$

où la quatrième ligne est justifiée par la propriété 3.4.4.

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

**Lemme 3.4.3.** Si $Q_n = \sum_{i=1}^n \sum_{j=1}^n a_{ij} (T_i T_j - E_{\epsilon} [T_i T_j])$ où $\{T_i\}_{i \in \llbracket 1, n \rrbracket}$ sont des variables aléatoires i.i.d sous Gaussiennes de paramètre 1 et $A = \{a_{ij}\}_{(i,j) \in \llbracket 1, n \rrbracket}^2$ est une matrice symétrique. Alors, nous obtenons, d'après l'inégalité de concentration (WRIGHT 1973), $\forall z > 0$,

$$ P\left(Q_n \ge \frac{1}{c_3} \left[ \|A\|_2 z + \sqrt{c_3} \|A\|_F \sqrt{z} \right] \le \exp(-z)\right) \le \exp(-z), $$

où $\|A\|_2$ et $\|A\|_F$ sont respectivement la norme d'opérateur et la norme de Frobenius de $A = \{a_{ij}\}_{(i,j) \in \llbracket 1, n \rrbracket}^2$.

**Démonstration.** Les hypothèses de l'inégalité de concentration de (WRIGHT 1973) sont vérifiées car :

— $A = \{a_{ij}\}_{(i,j) \in \llbracket 1, n \rrbracket}^2$ est une matrice symétrique.
— Comme $\{T_i\}_{i \in [1, n]}$ sont des variables aléatoires i.i.d. sous Gaussiennes de paramètre 1 alors la distribution de $T$ est symétrique et $T$ vérifie $\forall x \ge 0$, $P(|T| \ge x) \le M \int_x^\infty e^{-\gamma t^2} dt$ où $M = \sqrt{\frac{8}{\pi}}$ et $\gamma = \frac{1}{4}$.

Alors, d'après l'inégalité de concentration (WRIGHT 1973), $\exists c_3 > 0, \forall \delta > 0$,

$$P[Q_n \ge \delta] \le \exp\left(-c_3 \min\left\{\frac{\delta}{\|A\|_2}, \frac{\delta^2}{\|A\|_F^2}\right\}\right),$$

Dans un premier temps, nous prouvons que, $\forall \delta > 0$, $P[Q_n \ge \delta] \le \exp(-\frac{\delta^2}{\|A\|_F^2 + \delta \|A\|_2})$. Nous remarquons que

$$\begin{align*}
\frac{\delta}{\|A\|_2} &< \frac{\delta^2}{\|A\|_F^2} \\
\Leftrightarrow \delta &> \frac{\|A\|_F^2}{\|A\|_2} =: \delta_0 \\
\Rightarrow \exp\left(-c_3 \min\left\{\frac{\delta}{\|A\|_2}, \frac{\delta^2}{\|A\|_F^2}\right\}\right) &= 1_{\{\delta > \delta_0\}} \exp\left(-c_3 \frac{\delta}{\|A\|_2}\right) + 1_{\{\delta \le \delta_0\}} \exp\left(-c_3 \frac{\delta^2}{\|A\|_F^2}\right).
\end{align*}$$

De plus, $\forall \delta > 0$,

$$\frac{\delta}{\|A\|_2} = \frac{\delta^2}{\delta \|A\|_2} \\
\ge \frac{\delta^2}{\|A\|_F^2 + \delta \|A\|_2}.$$

Nous obtenons aussi, $\forall \delta > 0$,

$$\frac{\delta^2}{\|A\|_F^2} \ge \frac{\delta^2}{\|A\|_F^2 + \delta \|A\|_2}.$$

Ainsi, $\forall \delta > 0$,

$$\begin{align*}
& \exp\left(-c_3 \min\left\{\frac{\delta}{\|A\|_2}, \frac{\delta^2}{\|A\|_F^2}\right\}\right) \\
&= 1_{\{\delta > \delta_0\}} \exp\left(-c_3 \frac{\delta}{\|A\|_2}\right) + 1_{\{\delta \le \delta_0\}} \exp\left(-c_3 \frac{\delta^2}{\|A\|_F^2}\right) \\
&\le 1_{\{\delta > \delta_0\}} \exp\left(-c_3 \frac{\delta^2}{\|A\|_F^2 + \delta \|A\|_2}\right) + 1_{\{\delta \le \delta_0\}} \exp\left(-c_3 \frac{\delta^2}{\|A\|_F^2 + \delta \|A\|_2}\right) \\
&\le \exp\left(-c_3 \frac{\delta^2}{\|A\|_F^2 + \delta \|A\|_2}\right).
\end{align*}$$
Nous définissons $z = \frac{c_3 \delta^2}{\|A\|_F^2 + \delta \|A\|_2}$. Alors, nous obtenons

$$ 
\begin{gathered}
\frac{c_3 \delta^2}{\|A\|_F^2 + \delta \|A\|_2} = z \\
\Rightarrow c_3 \delta^2 - \|A\|_2 z \delta - \|A\|_F^2 z = 0
\end{gathered}
\qquad (3.13) $$

Nous remarquons que $\delta > 0$ qui vérifie l'équation. (3.13) est

$$ \delta = \frac{\|A\|_2 z + \sqrt{\|A\|_2^2 z^2 + 4c_3 \|A\|_F^2 z}}{2c_3}. $$

Par conséquent, $\forall z > 0$,

$$ P \left[ Q_n \ge \frac{\|A\|_2 z + \sqrt{\|A\|_2^2 z^2 + 4c_3 \|A\|_F^2 z}}{2c_3} \right] \le \exp(-z). $$

Nous remarquons

$$ 
\begin{align*}
\frac{\|A\|_2 z + \sqrt{\|A\|_2^2 z^2 + 4c_3 \|A\|_F^2 z}}{2c_3} &\le \frac{1}{2c_3} \left[ 2 \|A\|_2 z + 2 \sqrt{c_3} \|A\|_F \sqrt{z} \right] \\
&\le \frac{1}{c_3} \left[ \|A\|_2 z + \sqrt{c_3} \|A\|_F \sqrt{z} \right].
\end{align*} $$

Comme $\{Q_n \ge \frac{1}{c_3} [\|A\|_2 z + \sqrt{c_3} \|A\|_F \sqrt{z}]\} \subset \{Q_n \ge \frac{\|A\|_2 z + \sqrt{\|A\|_2^2 z^2 + 4c_3 \|A\|_F^2 z}}{2c_3}\}$, nous concluons, $\forall z > 0$,

$$ P \left( Q_n \ge \frac{1}{c_3} \left[ \|A\|_2 z + \sqrt{c_3} \|A\|_F \sqrt{z} \right] \right) \le \exp(-z). $$

□

**Propriété 3.4.4.** Il existe une constante $c_3 > 0$ telle que $\forall z > 0, \forall t \in \mathbb{N}$,

$$ P \left( V_t \ge 2E_{\epsilon} [V_t] + \sigma^2 \frac{z}{n} \frac{4}{c_3} \right) \le \exp(-z). \qquad (3.14) $$

Nous obtenons aussi, $\forall z > 0, \forall t \in \mathbb{N}$, sur un événement de probabilité au moins $1 - \exp(-z)$,

$$ V_t < V_t^{sup} + \frac{4\sigma^2 z}{c_3 n}, \qquad (3.15) $$

où $V_t^{sup} := \frac{4\sigma^2}{n} \sum_{j=1}^{d} \min\{1, (t\alpha\hat{\lambda}_j)^2\}$.

**Démonstration.** D'après le lemme 3.4.1, nous avons une autre expression de $V_t, \forall t \in \mathbb{N}$,

$$ V_t = \frac{2}{n} \sum_{j=1}^{d} (1 - S_{jj}^t)^2 [P^T \epsilon]_j^2 = \frac{2}{n} \text{Tr}(P Q_t P^T \epsilon \epsilon^T), $$
où $Q_t = \text{Diag}((1 - S_{jj}^t)^2, j \in \llbracket 1, n \rrbracket)$.

Ainsi, d'après le lemme 8 (RASKUTTI, WAINWRIGHT et Yu 2014), nous pouvons majorer $E_\epsilon[V_t]$, $\forall t \in \mathbb{N}$,

$$
\begin{align*}
E_{\epsilon}[V_t] &= \frac{2\sigma^2}{n} \operatorname{Tr}(Q_t) \\
&= \frac{2\sigma^2}{n} \sum_{j=1}^{d} (1 - S_{jj}^t)^2 \\
&\le \frac{2\sigma^2}{n} \sum_{j=1}^{d} \left( \min\{1, t\alpha\hat{\lambda}_j\} \right)^2 \\
&\le \frac{2\sigma^2}{n} (t\alpha)^2 \sum_{j=1}^{d} \left( \min\left\{\frac{1}{(t\alpha)^2}, \hat{\lambda}_j^2\right\} \right). \tag{3.16}
\end{align*}
$$

Nous utilisons une inégalité de concentration (WRIGHT 1973) qui affirme, $\forall \delta > 0$,

$$
P[Q_n \ge \delta] \le \exp\left(-c_3 \min\left\{\frac{\delta}{\|A\|_2}, \frac{\delta^2}{\|A\|_F^2}\right\}\right),
$$

où $Q_n = \sum_{i=1}^n \sum_{j=1}^n a_{ij} (T_i T_j - E_\epsilon[T_i T_j])$ avec $\{T_i\}_{i \in \llbracket 1, n \rrbracket}$ sont des variables aléatoires i.i.d. sous Gaus-
siennes de paramètre 1 ; $\|A\|_2$ et $\|A\|_F$ sont respectivement la norme d'opérateur et la norme de
Frobenius de la matrice symétrique $A = \{a_{ij}\}_{(i,j) \in \llbracket 1, n \rrbracket}^2$. D'après le lemme 3.4.3, nous obtenons,
$\forall z > 0$,

$$
P \left( Q_n \ge \frac{1}{c_3} \left[ \|A\|_2 z + \sqrt{c_3} \|A\|_F \sqrt{z} \right] \le \exp(-z) \right) \le \exp(-z), \quad (3.17)
$$

Nous définissons $A_t = \frac{2}{n} P Q_t P^T = \{a_{ij}\}_{(i,j)\in\llbracket 1,n\rrbracket}^2$ et $T_i = \frac{\epsilon_i}{\sigma}$ (comme $\forall i \in \llbracket 1,n \rrbracket$, $\epsilon_i \sim \mathcal{G}(\sigma^2) \Rightarrow T_i \sim \mathcal{G}(1)$). Alors, nous avons $\sigma^2 Q_n = V_t - E_\epsilon[V_t]$.

Nous majorons $\|A_t\|_2$ et $\|A_t\|_F^2$

$$
\begin{align*}
\|A_t\|_2 &= \frac{2}{n} (1 - S_{11}^t)^2 \quad \text{car } A_t \text{ est symétrique.} \\
&\le \frac{2}{n} \operatorname{car} S_{11}^t \in ]0, 1[.
\end{align*}
$$

$$
\begin{align*}
\|A_t\|_F^2 &= \operatorname{Tr}(A_t^T A_t) \\
&= \frac{4}{n^2} \operatorname{Tr}(P Q_t^2 P^T) \\
&\le \frac{4}{n^2} \operatorname{Tr}(Q_t) \operatorname{car} \forall j \in \llbracket 1, n \rrbracket, (Q_t)_{jj} \le 1 \\
&\le \frac{2}{\sigma^2 n} E_\epsilon[V_t].
\end{align*}
$$
Ainsi, d'après l'équation (3.17), nous obtenons

$$
\begin{align*}
& P\left(Q_n \ge \frac{1}{c_3} \left[ \|A_t\|_2 z + \sqrt{c_3} \|A_t\|_F \sqrt{z} \right) \right) \\
&= P\left(V_t - E_\epsilon[V_t] \ge \frac{\sigma^2}{c_3} \left[ \|A_t\|_2 z + \sqrt{c_3} \|A_t\|_F \sqrt{z} \right] \right) \\
&\ge P\left(V_t - E_\epsilon[V_t] \ge \frac{\sigma^2}{c_3} \left[ \frac{2z}{n} + \sqrt{c_3} \sqrt{\frac{2E_\epsilon[V_t]z}{\sigma^2n}} \right] \right) \\
&\ge P\left(V_t - E_\epsilon[V_t] \ge \frac{\sigma^2}{c_3} \left[ \frac{2z}{n} + \sqrt{c_3} \left( \theta^{1/2} \frac{2E_\epsilon[V_t]}{\sigma^2} + \theta^{-1/2} \frac{z}{n} \right) \right] \right),
\end{align*}
$$

car $\forall \theta > 0$, $ab \le \theta a^2 + \theta^{-1}b^2 \Rightarrow \sqrt{ab} \le \theta^{1/2}a + \theta^{-1/2}b$ où $a = \frac{2E_\epsilon[V_t]}{\sigma^2}$ et $b = \frac{z}{n}$.
Par conséquent, nous obtenons, $\forall z > 0$,

$$
\begin{align*}
P\left(V_t - E_\epsilon[V_t] \ge \frac{\sigma^2}{c_3} \left[ \frac{2z}{n} + \sqrt{c_3} \left( \theta^{1/2} \frac{2E_\epsilon[V_t]}{\sigma^2} + \theta^{-1/2} \frac{z}{n} \right) \right] \right) &\le \exp(-z) \\
\Rightarrow P\left(V_t \ge \left( \frac{2\theta^{1/2}}{\sqrt{c_3}} + 1 \right) E_\epsilon[V_t] + \sigma^2 \frac{z}{n} \left( \frac{2}{c_3} + \frac{\theta^{-1/2}}{\sqrt{c_3}} \right) \right) &\le \exp(-z).
\end{align*}
$$

Nous choisissons $\theta$ tel que $\frac{2\theta^{1/2}}{\sqrt{c_3}} + 1 = 2 \Rightarrow \frac{\theta^{1/2}}{\sqrt{c_3}} = \frac{1}{2} \Rightarrow \theta^{1/2} = \frac{1}{2}\sqrt{c_3}$. Alors, nous obtenons, $\forall z > 0$, $\forall t \in \mathbb{N}$,

$$
P\left(V_t \ge 2E_\epsilon[V_t] + \frac{4\sigma^2 z}{c_3 n}\right) \le \exp(-z).
$$

□

3.4.6 Preuve de la propriété 3.1.3

Pour montrer, avec grande probabilité, que $t^*$ est encadré par deux fonctions équivalentes à $\log(n)$ à une constante près lorsque $n$ tend vers $+\infty$, on étudie les variations de la fonction $x \mapsto \frac{1}{n}\|\hat{Y}^{(x)} - Y^*\|_{2,n}^2$, fonction définie sur $\mathbb{R}_+$.

**Propriété 3.4.5.** Sur l'événement $D_n$ (définie dans la preuve ci-dessous) de grande probabilité ($P(D_n) \xrightarrow{n \to +\infty} 1$), nous pouvons majorer $t^* = \arg \min_{t \in \mathbb{N}} \{\Delta(\hat{Y}^{(t)})\}$

$$
t^* \le v_2(n) \\
v_2(n) := \frac{1}{-\log(\rho_d)} \log \left( 1 + n \sqrt{\hat{\lambda}_1} \|\theta^* - \theta^{(0)}\|_{2,d} \right).
$$

Démonstration. Nous souhaitons majorer $t^* = \arg \min_{t \in \mathbb{N}} \{\Delta(\hat{Y}^{(t)})\}$ avec grande probabilité. La stra-
tégie de la preuve repose sur l'étude de la fonction $\Phi$ définie par $\forall x \ge 0$, $\Phi(x) = \frac{1}{n} \|\hat{Y}^{(x)} - Y^*\|_{2,n}^2$.
Nous cherchons une condition suffisante pour que $\Phi'(x) > 0$ afin d'obtenir une majoration de $k^*$.
Nous obtenons, $\forall x \in \mathbb{N}$,

$$ \frac{1}{n} \| \hat{Y}^{(x)} - Y^{*} \|_{2,n}^{2} = \frac{1}{n} \| E_{\epsilon} [ \hat{Y}^{(x)} ] - Y^{*} \|_{2,n}^{2} + \frac{1}{n} \| \hat{Y}^{(x)} - E_{\epsilon} [ \hat{Y}^{(x)} ] \|_{2,n}^{2} \\ + \frac{2}{n} \langle E_{\epsilon} [ \hat{Y}^{(x)} ] - Y^{*}, \hat{Y}^{(x)} - E_{\epsilon} [ \hat{Y}^{(x)} ] \rangle_{\mathbb{R}^{n}} $$

Nous calculons chacun des trois termes de la décomposition de $\frac{1}{n} \| \hat{Y}^{(x)} - Y^{*} \|_{2,n}^{2}$. Nous obtenons, $\forall x \in \mathbb{N}$,

$$ \hat{Y}^{(x)} = \left( I_n - \left(I_n - \frac{\alpha}{n} XX^T\right)^x \right) Y + \left(I_n - \frac{\alpha}{n} XX^T\right)^x Y^{(0)} \\ \Rightarrow E_{\epsilon}[\hat{Y}^{(x)}] = \left(I_n - \left(I_n - \frac{\alpha}{n} XX^T\right)^x\right) Y^* + \left(I_n - \frac{\alpha}{n} XX^T\right)^x Y^{(0)} \\ \Rightarrow E_{\epsilon}[\hat{Y}^{(x)}] - Y^* = \left(I_n - \frac{\alpha}{n} XX^T\right)^x (Y^{(0)} - Y^*) \\ = P S^x P^T (Y^{(0)} - Y^*) \\ \Rightarrow \hat{Y}^{(x)} - E_{\epsilon}[\hat{Y}^{(x)}] = \left(I_n - \left(I_n - \frac{\alpha}{n} XX^T\right)^x\right) \epsilon \\ = P(I_n - S^x) P^T \epsilon \\ \Rightarrow \langle E_{\epsilon}[\hat{Y}^{(x)}] - Y^*, \hat{Y}^{(x)} - E_{\epsilon}[\hat{Y}^{(x)}] \rangle_{\mathbb{R}^n} = \langle P S^x P^T (Y^{(0)} - Y^*), P(I_n - S^x) P^T \epsilon \rangle_{\mathbb{R}^n} \\ = \langle S^x P^T (Y^{(0)} - Y^*), (I_n - S^x) P^T \epsilon \rangle_{\mathbb{R}^n} \\ = \sum_{j=1}^{d} Z_j [P^T \epsilon]_j \rho_j^x (1 - \rho_j^x) \\ \frac{1}{n} \| E_{\epsilon}[\hat{Y}^{(x)}] - Y^* \|_{2,n}^2 = \frac{1}{n} \sum_{j=1}^{d} Z_j^2 \rho_j^{2x} \\ \frac{1}{n} \| \hat{Y}^{(x)} - E_{\epsilon}[\hat{Y}^{(x)}] \|_{2,n}^2 = \frac{1}{n} \sum_{j=1}^{d} (1 - \rho_j^x)^2 [P^T \epsilon]_j^2, $$

où $K = \frac{1}{n}XX^T = P\Lambda P^T$ ; $rg(K) = d$ ; $S = I_n - \alpha\Lambda$ ; $Z = P^T(Y^{(0)} - Y^*)$ ; $\forall i \in [1, n]$ , $\rho_i = S_{ii} = 1 - \alpha\hat{\lambda}_i$.
Ainsi, d'après l'expression de $\Phi$ et $\Phi', \forall x \ge 0$, nous déduisons

$$
\begin{align*}
\Phi(x) &= \frac{1}{n} \left[ \sum_{j=1}^{d} Z_j^2 \rho_j^{2x} + \sum_{j=1}^{d} (1 - \rho_j^x)^2 [P^T \epsilon]_j^2 + 2 \sum_{j=1}^{d} Z_j [P^T \epsilon]_j \rho_j^x (1 - \rho_j^x) \right] \\
\Rightarrow \Phi'(x) &= \frac{1}{n} \left[ 2 \sum_{j=1}^{d} Z_j^2 \rho_j^{2x} \log(\rho_j) - 2 \sum_{j=1}^{d} [P^T \epsilon]_j^2 \rho_j^x (1 - \rho_j^x) \log(\rho_j) \right. \\
&\qquad \left. + 2 \sum_{j=1}^{d} Z_j [P^T \epsilon]_j (\rho_j^x - 2\rho_j^{2x}) \log(\rho_j) \right] \\
&= \frac{2}{n} \left[ \sum_{j=1}^{d} (Z_j^2 + [P^T \epsilon]_j^2 - 2Z_j [P^T \epsilon]_j) \rho_j^{2x} \log(\rho_j) \right. \\
&\qquad \left. + \sum_{j=1}^{d} (Z_j [P^T \epsilon]_j - [P^T \epsilon]_j^2) \rho_j^x \log(\rho_j) \right] \\
&= \frac{2}{n} \left[ \sum_{j=1}^{d} N_j^2 \rho_j^{2x} \log(\rho_j) + \sum_{j=1}^{d} [P^T \epsilon]_j N_j \rho_j^x \log(\rho_j) \right],
\end{align*}
$$

$$
\text{où } \forall j \in [1, d], N_j = Z_j - [P^T \epsilon]_j = [P^T (Y^{(0)} - Y)]_j.
$$

Nous cherchons une condition suffisante pour obtenir $\Phi'(x) > 0$.

$$
\begin{align*}
\Phi'(x) &= \frac{2}{n} \left[ \sum_{j=1}^{d} N_j^2 \rho_j^{2x} \log(\rho_j) + \sum_{j=1}^{d} [P^T \epsilon]_j N_j \rho_j^x \log(\rho_j) \right] \\
&= \frac{2}{n} \sum_{j=1}^{d} w_j(x),
\end{align*}
$$

$$
\text{où } w_j(x) = N_j^2 \rho_j^{2x} \log(\rho_j) + [P^T \epsilon]_j N_j \rho_j^x \log(\rho_j).
$$

Nous cherchons une condition suffisante sur $x$ pour que $\forall j \in [1, d]$, $w_j(x) > 0$ afin d'obtenir
$\Phi'(x) > 0$. Ainsi, $\forall j \in [1, d] =$

$$
\begin{align*}
w_j(x) &> 0 \\
&\Leftrightarrow N_j^2 \rho_j^{2x} \log(\rho_j) + [P^T \epsilon]_j N_j \rho_j^x \log(\rho_j) > 0 \\
&\Leftrightarrow N_j^2 \rho_j^{2x} + [P^T \epsilon]_j N_j \rho_j^x < 0 \quad \text{car } \rho_j \in [0, 1] \\
&\Leftrightarrow \rho_j^x + \frac{[P^T \epsilon]_j}{N_j} < 0 \\
&\Leftrightarrow \rho_j^x < \frac{[P^T \epsilon]_j}{[P^T \epsilon]_j - Z_j} \\
&\Leftrightarrow \rho_j^{-x} > 1 - \frac{Z_j}{[P^T \epsilon]_j} \\
&\Leftrightarrow \rho_j^{-x} > 1 - \frac{\sqrt{n \hat{\lambda}_j u_j^T (\theta^{(0)} - \theta^*)}}{[P^T \epsilon]_j} \\
&\Leftrightarrow \rho_j^{-x} > 1 + \frac{\sqrt{n \hat{\lambda}_j \|\theta^* - \theta^{(0)}\|_{2,d}}}{|[P^T \epsilon]_j|}.
\end{align*}
$$

Nous définissons $\mathcal{D}_n = \bigcap_{j=1}^d \{|(P^T \epsilon)_j| > \frac{1}{\sqrt{n}}\}$. Nous remarquons que $P(D_n) \ge 1 - \sum_{j=1}^d P(|(P^T \epsilon)_j| < \frac{1}{\sqrt{n}})$. De plus, $(P^T \epsilon)_1, \dots, (P^T \epsilon)_d$ ont la même distribution que $L \sim \mathcal{G}(\sigma^2)$. Comme $A_n = \{|L| < \frac{1}{\sqrt{n}}\}$ est une suite décroissante d'événements (au sens de l'inclusion) alors $P(|L| < \frac{1}{\sqrt{n}}) \xrightarrow{n \to +\infty} P(|L| = 0) = 0$. Par conséquent, $P(D_n) \xrightarrow{n \to +\infty} 1$. Nous obtenons, sur l'événement $\mathcal{D}_n$,

$$
\begin{align*}
w_j(x) &> 0 \\
&\Leftrightarrow \rho_j^{-x} > 1 + \frac{\sqrt{n \hat{\lambda}_j} \|\theta^* - \theta^{(0)}\|_{2,d}}{|[P^T \epsilon]_j|} \\
&\Leftrightarrow \rho_j^{-x} > 1 + n \sqrt{\hat{\lambda}_j} \|\theta^* - \theta^{(0)}\|_{2,d} \\
&\Leftrightarrow x > \frac{1}{-\log(\rho_j)} \log \left( 1 + n \sqrt{\hat{\lambda}_j} \|\theta^* - \theta^{(0)}\|_{2,d} \right) \\
&\Leftrightarrow x > \frac{1}{-\log(\rho_d)} \log \left( 1 + n \sqrt{\hat{\lambda}_1} \|\theta^* - \theta^{(0)}\|_{2,d} \right).
\end{align*}
$$

□
**Propriété 3.4.6.** Sur l'événement $\mathcal{E}_n \left( P\left(\mathcal{E}_n\right) \xrightarrow[n \to +\infty]{} 1 \right)$, nous pouvons minorer $t^* = \arg \min_{t \in \mathbb{N}} \{\Delta(\hat{Y}^{(t)})\}$:

$$t^* \ge v_1(n)$$
$$v_1(n) := \frac{1}{\log\left(\frac{\rho_d}{\rho_1^2}\right)} \left[ \log\left(\frac{\log(\rho_d)}{\log(\rho_1)}\right) + \frac{1}{2}\log(2) + \frac{1}{2}\log\left(1 + \frac{\sqrt{n}\hat{\lambda}_d \|\theta^* - \theta^{(0)}\|_{2,d}^2}{d}\right) \right].$$

*Démonstration.* Nous voulons majorer $t^* = \arg \min_{t \in \mathbb{N}} \{\Delta(\hat{Y}^{(t)})\}$ avec grande probabilité. On utilise pour cela une stratégie similaire à celle utilisée pour démontrer la propriété 3.4.5. Nous savons que $\forall x \in \mathbb{R}$, $\Phi'(x)$ a pour expression

$$\begin{align*}
\Rightarrow \Phi'(x) &= \frac{1}{n} \left[ 2 \sum_{j=1}^{d} Z_j^2 \rho_j^{2x} \log(\rho_j) - 2 \sum_{j=1}^{d} [P^T \epsilon]_j^2 \rho_j^x (1 - \rho_j^x) \log(\rho_j) \right. \\
&\qquad \left. + 2 \sum_{j=1}^{d} Z_j [P^T \epsilon]_j (\rho_j^x - 2\rho_j^{2x}) \log(\rho_j) \right] \\
&= \frac{2}{n} \left[ \underbrace{\sum_{j=1}^{d} N_j^2 \rho_j^{2x} \log(\rho_j)}_{\Phi_1'(x)} + \underbrace{\sum_{j=1}^{d} [P^T \epsilon]_j N_j \rho_j^x \log(\rho_j)}_{\Phi_2'(x)} \right],
\end{align*}$$

$$\text{où } \forall j \in [1, d], N_j = Z_j - [P^T \epsilon]_j = [P^T (Y^{(0)} - Y)]_j.$$

Nous majorons $\Phi'_1, \forall x \ge 0$,

$$\begin{align*}
\Phi'_1(x) &\le \sum_{j=1}^{d} N_j^2 \rho_j^{2x} \log(\rho_j) \\
&\le \log(\rho_d) \rho_1^{2x} \sum_{j=1}^{d} N_j^2 \\
&\le \log(\rho_d) \rho_1^{2x} \|P^T (Y - Y^{(0)})\|_{2,d}^2 \\
&\le \log(\rho_d) \rho_1^{2x} \times 2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2),
\end{align*}$$

$$\text{où } \rho_1 \le \dots \le \rho_d.$$
Nous majorons $\Phi'_2, \forall x \ge 0$,

$$
\begin{align*}
\Phi'_2(x) &= \sum_{j=1}^{d} [P^T \epsilon]_j N_j \rho_j^x \log(\rho_j) \\
&= -\langle S^{x/2} \sqrt{-\log(S)} N, S^{x/2} \sqrt{-\log(S)} P^T \epsilon \rangle_{\mathbb{R}^d} \\
&\le \|S^{x/2} \sqrt{-\log(S)} N\|_{2,d} \|S^{x/2} \sqrt{-\log(S)} P^T \epsilon\|_{2,d}.
\end{align*}
$$

Nous remarquons que, $\forall x \ge 0$,

$$
\begin{align*}
\| S^{x/2} \sqrt{-\log(S)} N \|_{2,d} &= \sqrt{\sum_{j=1}^{d} \rho_j^x (-\log(\rho_j)) N_j^2} \\
&\le \sqrt{-\log(\rho_1)} \rho_d^{x/2} \sqrt{\sum_{j=1}^{d} N_j^2} \\
&\le \sqrt{-\log(\rho_1)} \rho_d^{x/2} \| P^T (Y - Y^{(0)}) \|_{2,d} \\
&\le \sqrt{-\log(\rho_1)} \rho_d^{x/2} \sqrt{2 (\| P^T (Y^* - Y^{(0)}) \|_{2,d}^2 + \| P^T \epsilon \|_{2,d}^2)} \\
&\le \sqrt{-\log(\rho_1)} \rho_d^{x/2} \sqrt{2 (\| Z \|_{2,n}^2 + \| P^T \epsilon \|_{2,d}^2)}
\end{align*}
$$

De même, nous obtenons $\forall x \ge 0$,

$$
\begin{align*}
\| S^{x/2} \sqrt{-\log(S)} P^T \epsilon \|_2 &= \sqrt{\sum_{j=1}^{d} \rho_j^x (-\log(\rho_j)) [P^T \epsilon]_j^2} \\
&\le \sqrt{-\log(\rho_1)} \rho_d^{x/2} \|P^T \epsilon\|_{2,d}.
\end{align*}
$$

Par conséquent, nous obtenons une majoration de $\Phi'_2, \forall x \ge 0$,

$$
\begin{align*}
\Phi'_2(x) &\le \| S^{x/2} \sqrt{-\log(S)} N \|_{2,d} \| S^{x/2} \sqrt{-\log(S)} P^T \epsilon \|_{2,d} \\
&\le (-\log(\rho_1)) \rho_d^x \| P^T \epsilon \|_{2,d} \sqrt{2 (\| Z \|_{2,n}^2 + \| P^T \epsilon \|_{2,d}^2)}
\end{align*}
$$
Ainsi, une condition suffisante pour avoir $\Phi'(x) < 0$ est

$$
\begin{align*}
& \log(\rho_d) \rho_1^{2x} 2 (\|Z\|_{2,n}^2 + \|\epsilon\|_{2,d}^2) + (-\log(\rho_1)) \rho_d^x \|P^T \epsilon\|_{2,d} \sqrt{2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2)} < 0 \\
\Leftrightarrow & (-\log(\rho_1)) \rho_d^x \|P^T \epsilon\|_{2,d} \sqrt{2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2)} < (-\log(\rho_d)) \rho_1^{2x} 2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2) \\
\Leftrightarrow & \frac{\log(\rho_1)}{\log(\rho_d)} \|P^T \epsilon\|_{2,d} < \left(\frac{\rho_1^2}{\rho_d}\right)^x \sqrt{2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2)} \\
\Leftrightarrow & \frac{\log(\rho_1)}{\log(\rho_d)} \frac{\|P^T \epsilon\|_{2,d}}{\sqrt{2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2)}} < \left(\frac{\rho_1^2}{\rho_d}\right)^x \\
\Leftrightarrow & \log\left(\frac{\log(\rho_1)}{\log(\rho_d)}\right) + \log\left(\frac{\|P^T \epsilon\|_{2,d}}{\sqrt{2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2)}}\right) < x \log\left(\frac{\rho_1^2}{\rho_d}\right) \\
\Leftrightarrow & x < \frac{1}{\log\left(\frac{\rho_1^2}{\rho_d}\right)} \left[ \log\left(\frac{\log(\rho_1)}{\log(\rho_d)}\right) + \log\left(\frac{\|P^T \epsilon\|_{2,d}}{\sqrt{2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2)}}\right) \right] \\
\Leftrightarrow & x < \frac{1}{\log\left(\frac{\rho_d}{\rho_1^2}\right)} \left[ \log\left(\frac{\log(\rho_d)}{\log(\rho_1)}\right) + \log\left(\frac{\sqrt{2 (\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2)}}{\sqrt{\|P^T \epsilon\|_{2,d}^2}}\right) \right] \\
\Leftrightarrow & x < \frac{1}{\log\left(\frac{\rho_d}{\rho_1^2}\right)} \left[ \log\left(\frac{\log(\rho_d)}{\log(\rho_1)}\right) + \frac{1}{2}\log(2) + \frac{1}{2}\log\left(\frac{\|Z\|_{2,n}^2 + \|P^T \epsilon\|_{2,d}^2}{\|P^T \epsilon\|_{2,d}^2}\right) \right] \\
\Leftrightarrow & x < \frac{1}{\log\left(\frac{\rho_d}{\rho_1^2}\right)} \left[ \log\left(\frac{\log(\rho_d)}{\log(\rho_1)}\right) + \frac{1}{2}\log(2) + \frac{1}{2}\log\left(1 + \frac{\|Z\|_{2,n}^2}{\|P^T \epsilon\|_{2,d}^2}\right) \right],
\end{align*}
$$

$$ \text{car } \rho_1 \le \dots \le \rho_d \Rightarrow \frac{\rho_1^2}{\rho_d} \le \rho_d < 1. $$

Comme $\|P^T \epsilon\|_{2,d}^2 = \sum_{j=1}^d (p_j^T \epsilon)^2$ (où $p_j$ est la $j$-e colonne de $P$) et $\epsilon_1, \dots, \epsilon_d$ sont i.i.d. de loi de probabilité $\mathcal{G}(\sigma^2) \Rightarrow p_j^T \epsilon \sim \mathcal{G}(\sigma^2)$ (car $\|p_j\|_{2,n} = 1) \Rightarrow \forall t > 0, P((p_j^T \epsilon)^2 > t^2) = P(|p_j^T \epsilon| > t) = 2 \exp(-\frac{t^2}{2\sigma^2})$.
Ainsi $\mathcal{E}_n = \bigcap_{j=1}^d \{(p_j^T \epsilon)^2 \le \sqrt{n}\}$ vérifie $P(\mathcal{E}_n) \ge 1 - 2d \exp(-\frac{\sqrt{n}}{2\sigma^2})$. Sur l'événement $\mathcal{E}_n$, nous obtenons
$$ \Phi'(x) < 0 $$

$$ \Leftrightarrow x < \frac{1}{\log\left(\frac{\rho_d}{\rho_1^2}\right)} \left[ \log\left(\frac{\log(\rho_d)}{\log(\rho_1)}\right) + \frac{1}{2}\log(2) + \frac{1}{2}\log\left(1 + \frac{(\|Z\|_{2,n}^2)}{d\sqrt{n}}\right) \right] $$

$$ \Leftrightarrow x < \frac{1}{\log\left(\frac{\rho_d}{\rho_1^2}\right)} \left[ \log\left(\frac{\log(\rho_d)}{\log(\rho_1)}\right) + \frac{1}{2}\log(2) + \frac{1}{2}\log\left(1 + \frac{n\hat{\lambda}_d \|\theta^* - \theta^{(0)}\|_{2,d}^2}{d\sqrt{n}}\right) \right] $$

$$ \Leftrightarrow x < \frac{1}{\log\left(\frac{\rho_d}{\rho_1^2}\right)} \left[ \log\left(\frac{\log(\rho_d)}{\log(\rho_1)}\right) + \frac{1}{2}\log(2) + \frac{1}{2}\log\left(1 + \frac{\sqrt{n}\hat{\lambda}_d \|\theta^* - \theta^{(0)}\|_{2,d}^2}{d}\right) \right]. $$

□
Chapitre 4

Estimateur à budget de temps limité

Notre objectif est de déterminer le couple (t, n) garantissant que $\hat{\theta}_n^{(t)}$ est le meilleur estimateur de $\theta^*$ (selon le critère $Q(\hat{\theta}_n^{(t)})$ défini ci-dessous) lorsque nous disposons d'un budget de temps T limité. Au chapitre 3, nous avons cherché le temps de calcul nécessaire pour obtenir un estimateur $\hat{\theta}^{(t)}$ le plus "proche" possible de $\theta^*$. Tandis que dans ce chapitre, une contrainte de temps de calcul est imposée et il s'agit de trouver le meilleur estimateur de $\theta^*$ à budget de temps T limité. Le problème du choix du couple (t, n) d'un estimateur $\hat{\theta}_n^{(t)}$ est un problème fréquemment rencontré en pratique lorsque l'utilisateur a une contrainte de temps de calcul et souhaite obtenir un estimateur ayant de bonnes performances statistiques.

4.1 Compromis entre temps et taille de l'échantillon

Dans cette partie, nous faisons un état de l'art sur les estimateurs à budget de temps limité. Puis, nous présentons dans un deuxième temps le critère $Q(\hat{\theta}_n^{(t)})$ dans le cadre du problème de régression linéaire. Puis, nous définissons le choix optimal $(t, n')$ du nombre d'itérations et de la taille d'échantillon garantissant une précision optimale à budget de temps limité.

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

Dans le cadre de la régression, BOTTOU et BOUSQUET 2008 cherche à déterminer les paramètres permettant d'obtenir une précision statistique optimale d'un estimateur lorsque le budget de temps est limité. Appliquée au cadre de la régression linéaire, il cherche à choisir le couple $(n, \eta)$ minimisant un critère mesurant la précision statistique (BOTTOU et BOUSQUET 2008; BOTTOU 2010). $\eta$ est définie par $\frac{1}{n}\|Y - \tilde{Y}\|_{2,n}^2 \le \frac{1}{n}\|Y - \hat{Y}\|_{2,n}^2 + \eta$ et $\tilde{Y} = X\tilde{\theta}_n$ est une approximation de $Y^* = X\theta^*$ calculée par un algorithme itératif. Formellement, ce problème de minimisation est défini par

$$
\begin{equation}
\begin{aligned}
& \min_{n, \eta} \mathbb{E} \left[ E_x \left[ (x^T \tilde{\theta}_n - x^T \theta^*)^2 \right] \right] \\
& \quad \left\{
  \begin{array}{l}
    n \le n_{\max} \\
    T(n, \eta) \le T_{\max}
  \end{array}
\right.
\end{aligned}
\tag{4.1}
\end{equation}
$$
où $T(n, \eta)$ est le temps de calcul de $\tilde{Y}$. $\mathbb{E}$ et $E_x$ désignent respectivement l'espérance selon le choix aléatoire de l'échantillon et l'espérance selon la loi de probabilité des covariables $x \in \mathbb{R}^d$.

On remarque que le critère du problème de minimisation 4.1 ressemble au critère $E_\epsilon[\frac{1}{n}\|\hat{Y}^{(t)} - Y^*\|_{2,n}^2]$ étudié au chapitre précédent. Lorsque il n'y a pas de limite de budget de temps, cela suggère que le problème de minimisation 4.1 traduit un compromis biais - variance.

Lorsque le budget de temps est limité, BORTOU et BOUSQUET 2008 étudie le choix du couple $(n, \eta)$ afin que la précision statistique de $\tilde{Y}$ soit optimale. Comme le temps de calcul de $\tilde{Y}$ dépend de $n$ et $\eta$ alors choisir le couple $(n, \eta)$ revient à choisir le temps de calcul de $\tilde{Y}$ et la taille d'échantillon. Il s'agit donc d'une étude similaire à celle faite dans ce chapitre. BORTOU et BOUSQUET 2008 ont déterminé pour différents algorithmes (e.g. pour l' algorithme de descente de gradient et l'algorithme de descente de gradient stochastique présentés au chapitre 1) une majoration de la précision statistique optimale ainsi que des valeurs approximatives de $n$ et $\eta$ assurant cette précision statistique optimale.

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

Le critère $Q(\hat{\theta}_n^{(t)})$ mesure une distance entre $\hat{\theta}_n^{(t)}$ et l'estimateur $\hat{\theta}_n^A$ qui correspond à $\hat{\theta}_n^{(t)}$ lorsque $t$ tend vers $+\infty$. Dans ce chapitre, nous étudions le choix du couple $(t, n)$ dans le cadre du modèle linéaire (3.1). Nous utilisons l'algorithme de descente de gradient à pas fixe $\alpha$ (GD) appliqué aux moindres carrés étudié dans le chapitre 3. Nous savons que, si $\alpha \in ]0, \frac{1}{\lambda_1^{n,d}}[$ ($\lambda_1^{n,d}$ est la plus grande valeur propre de $\frac{1}{n}XX^T$), alors $\hat{\theta}_n^{(t)}$ tend vers l'estimateur des moindres carrés $\hat{\theta}_n^A = \hat{\theta}_n$ lorsque $t$ tend vers $+\infty$. Nous définissons le critère $Q(\hat{\theta}_n^{(t)})$ par :

$$Q(\hat{\theta}_n^{(t)}) = E_\epsilon \left[ \|\hat{\theta}_n^{(t)} - \hat{\theta}_n\|_{2,d}^2 \right],$$

où on calcule $E_\epsilon[\dots]$ en intégrant par rapport la loi de probabilité du terme d'erreur $\epsilon$.

Nous disposons d'une formule close de $Q(\hat{\theta}_n^{(t)})$

$$ 
\begin{aligned}
Q(\hat{\theta}_n^{(t)}) &= \|V^t(\theta^* - \theta^{(0)})\|_{2,d}^2 + \sigma^2 \mathrm{Tr} (V^t(X^T X)^{-1} V^t) \\
&= \sum_{i=1}^d \rho_i^{2t} \left( W_i^2 + \frac{\sigma^2}{n \lambda_i^{n,d}} \right),
\end{aligned} 
\quad (4.2) $$

où $W = U^T(\theta^{(0)} - \theta^*); V = I_d - \frac{\alpha}{n}X^T X; X^T X = UDU^T$ est obtenu par décomposition en valeurs singulières; $\lambda_1^{n,d} \ge \dots \ge \lambda_d^{n,d} > 0$ sont les valeurs propres de $\frac{1}{n}X^T X; \forall i \in [1, d]$, $\rho_i = 1 - \alpha \lambda_i^{n,d}$.

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

Dans cette partie, nous définissons le couple $(t', n')$ optimisant le critère $Q(\hat{\theta}_n^{(t)})$ afin de fournir le meilleur estimateur de $\theta^*$ lorsque le budget de temps $T$ est limité.

Pour un budget de temps limité $T$, le couple $(t', n')$ est défini par

$$(t', n') = \arg \min_{(t,n) \in \mathbb{N}^2} \{Q(\hat{\theta}_n^{(t)})\},$$
sous la contrainte $t\bar{T}_n \le T$ où $\bar{T}_n$ est le temps moyen d'exécution d'une itération de l'algorithme de descente de gradient à pas fixe pour une taille d'échantillon $n$. L'estimateur proposé est donc $\hat{\theta}_{n'}^{(t')}.$

Pour déterminer le couple $(t', n')$, nous cherchons à calculer le critère $Q(\hat{\theta}_n^{(t)})$ pour de grandes valeurs de $t$ et $n$ à partir de l'estimation de $Q(\hat{\theta}_n^{(t)})$ pour de faibles valeurs de $t$ et $n$. Une piste est, grâce à l'estimation de $Q(\hat{\theta}_n^{(t)})$ pour de faibles valeurs de $t$ et $n$, d'estimer $\theta^*$ et $\sigma^2$ pour capter la dynamique de $Q(\hat{\theta}_n^{(t)})$ en $n$ et $t$. Une autre piste est d'utiliser des résultats asymptotiques. Par exemple, nous avons obtenu un équivalent de $\log_{10}(Q(\hat{\theta}_n^{(t)}))$ lorsque $t$ tend vers $+\infty$ (cf propriété 4.1.1) qui nécessite uniquement d'estimer $Q(\theta^{(0)})$ lorsque la taille d'échantillon $n$ est fixée

**Propriété 4.1.1.**

$$ \log_{10} \left( Q\left(\hat{\theta}_n^{(t)}\right) \right) \underset{t \to +\infty}{\sim} 2t \log_{10}(\rho_d) + \log_{10} \left( Q\left(\theta^{(0)}\right) \right), $$

où $\rho_d = 1 - \alpha \lambda_d^{n,d}$ est la plus grande valeur propre de $I_d - \frac{\alpha}{n} X^T X$.

La preuve de la propriété 4.1.1 est disponible dans la partie 4.4.2.

La partie suivante a pour but de comprendre, à l'aide de simulations, l'évolution du couple $(t', n')$ en fonction du budget de temps $T$.

## 4.2 Simulations

Nous présentons dans cette partie les objectifs des simulations et le cadre de simulations. Puis, nous interprétons les résultats des simulations obtenues.

### 4.2.1 Objectifs

L'objectif de ces simulations est de comprendre la dynamique de $t'$ et $n'$ en fonction du budget de temps $T$. Il s'agit aussi d'illustrer, sur des simulations, le résultat asymptotique de $\log_{10}(Q(\hat{\theta}_n^{(t)}))$ lorsque $t$ tend vers $+\infty$ (cf. propriété 4.1.1).

Il est à noter que $Q(\hat{\theta}_n^{(t)}) = E[\|\hat{\theta}_n^{(t)} - \hat{\theta}_n\|_{2,d}^2]$ est estimé sur $B = 100$ répétitions du terme d'erreur $\epsilon$ (cf. modèle linéaire (1.9)). $\{\hat{\theta}_n^{(t)}\}_{t \in [0, t^0]}$ ($t^0 = 2000$) est calculé à l'aide de l'équation (3.2) pour chaque valeur de $n$.

### 4.2.2 Cadre de simulations

Nous reprenons le cadre de simulations défini dans la partie 3.2.2. Nous fixons SNR = 4.

### 4.2.3 Interprétation

Dans un premier temps, les figures 4.1a et 4.1b sont des illustrations de la propriété 4.1.1 car nous observons que $\log_{10}(Q(\hat{\theta}_n^{(t)}))$ est une fonction affine en $t$ lorsque $t$ est suffisamment grand.
<figure><img src="image_41.png" /><figcaption>FIGURE 4.1 – Figures 4.1a et 4.1b : Graphiques de $\log_{10} Q(\hat{\theta}_n^{(t)})$ en fonction de l'itération $t$ pour différentes valeurs de $n$ et, pour $d=20$ et $d=100$ respectivement.</figcaption></figure>

<figure><img src="image_42.png" /><figcaption>FIGURE 4.2 – Figures 4.2a et 4.2b : Graphiques de $\log_{10}(Q(\hat{\theta}_n^{(t)}))$ en fonction du temps de calcul de $\hat{\theta}_n^{(t)}$, pour différentes valeurs de $n$ et, pour $d=20$ et $d=100$ respectivement.</figcaption></figure>

Dans un second temps, nous étudions l'évolution du couple $(t', n')$ en fonction du budget de temps $T$. L'équation (4.2) montre que $Q(\hat{\theta}_n^{(t)})$ décroît exponentiellement vite avec $t$ et en $n^{-1}$ en $n$. Ainsi, pour un budget de temps $T$, pour deux tailles d'échantillon $n_1$ et $n_2$ telles que $n_2 > n_1$, et $t^1$ et $t^2$ tels que $T = t^1 \bar{T}_{n_1} = t^2 \bar{T}_{n_2}$ ($t^1 > t^2$ car $n \mapsto \bar{T}_n$ est croissante), $Q(\hat{\theta}_{n_1}^{(t^1)})$ aura "tendance" à être inférieur $Q(\hat{\theta}_{n_2}^{(t^2)})$.
<figure><img src="image_43.png" /><figcaption>FIGURE 4.3 – Figures 4.3a et 4.3b : Graphiques du couple $(t', n')$ en fonction du budget de temps $T$ pour $d = 20$.</figcaption></figure>

Cette remarque explique l'évolution du couple $(t', n')$ en fonction du budget de temps $T$. Lorsque $T = 0$, on sélectionne tout d'abord la plus petite taille d'échantillon $n = n_{min}$ et $t' = 0$ et, lorsque $T$ augmente, on a "tendance" à sélectionner $n' = n_{min}$ et $t' = t \in [1, t^0]$ tant que $t^0 \bar{T}_{n_{min}} \ge T = t \bar{T}_{n_{min}}$ ($t^0$ est le nombre maximum d'itérations de GD pour chaque valeur de $n$). Puis, lorsque $T > t^0 \bar{T}_{n_{min}}$, tant que $Q(\hat{\theta}_{n_{min}}^{(t^0)}) < Q(\hat{\theta}_{n_2}^{(t)})$ ($n_2 > n_{min}$), on sélectionne $n' = n_{min}$ et $t' = t^0$. Puis lorsque $T$ augmente et l'itération $t$ est suffisamment grande, comme $Q(\hat{\theta}_{n_{min}}^{(t^0)}) > Q(\hat{\theta}_{n_2}^{(t^0)})$ alors $\exists t \in [1, t^0]$, $Q(\hat{\theta}_{n_2}^{(t^0)}) < Q(\hat{\theta}_{n_{min}}^{(t^0)})$ : on sélectionne $n' = n_2$ et $t' = t$.

En dimension $d \in \{20, 100\}$, les figures 4.3a, 4.3b, 4.4a et 4.4b, et les remarques ci-dessus mettent en évidence le rôle du couple $(t, n)$ dans le compromis précision statistique - temps de calcul. La précision est mesurée par le critère $Q(\hat{\theta}_n^{(t)})$ et le temps de calcul est celui de $\hat{\theta}_n^{(t)}$. La
<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /><figcaption>FIGURE 4.4 – Figures 4.4a et 4.4b : Graphiques du couple $(t', n')$ en fonction du budget de temps $T$ pour $d = 100$.</figcaption></figure>

décroissance exponentielle de $Q(\hat{\theta}_n^{(t)})$ en $t$ et la décroissance de $Q(\hat{\theta}_n^{(t)})$ en $n^{-1}$ entraînent que $n'$ est constante par morceaux et $t'$ est affine par morceaux en fonction du budget de temps $T$. On remarque que lorsque $n'$ augmente de $n_1$ à $n_2$, $t'$ diminue car il faut moins d'itérations pour atteindre la précision $Q(\hat{\theta}_{n_1}^{(t_0)})$.

## 4.3 Conclusion

Dans le cadre du problème de régression linéaire, nous avons mis en évidence, grâce à des simulations, le compromis entre $t$ et $n$ à budget de temps fixé pour atteindre une précision optimale. En effet, les simulations montrent que le choix optimal $n'$ est constant par morceaux en fonction de $T$ et $t'$ est affine par morceaux en fonction de $T$. On remarque que, pour chaque
augmentation de $n'$, $t'$ diminue car il faut moins d'itérations pour atteindre une précision optimale.

Nous avons aussi obtenu un équivalent du critère $Q(\hat{\theta}_n^{(t)})$ lorsque $t$ tend vers $+\infty$ montrant que $Q(\hat{\theta}_n^{(t)})$ décroît exponentiellement vite avec $t$. Nous avons aussi illustré sur des simulations la décroissance exponentielle de $Q(\hat{\theta}_n^{(t)})$ en $t$.

## 4.4 Preuves

Dans cette partie, nous détaillons les preuves des propriétés énoncées dans ce chapitre.

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

**Propriété 4.4.1.** Nous avons une formule close du critère $Q(\hat{\theta}_n^{(t)})$, $\forall t \in \mathbb{N}$,

$$ 
\begin{aligned}
Q(\hat{\theta}_n^{(t)}) &= E_\epsilon \left[ \left\| \hat{\theta}_n^{(t)} - \hat{\theta}_n \right\|_{2,d}^2 \right] \\
&= \left\| V^k (\theta^* - \theta^{(0)}) \right\|_2^2 + \sigma^2 \text{Tr} \left( V^k (X^T X)^{-1} V^k \right),
\end{aligned}
$$

$$ \text{où } V = I_d - \frac{\alpha}{n} X^T X \text{ et } \hat{\theta}_n = (X^T X)^{-1} X^T Y. $$

**Démonstration.** D'après l'équation (3.3),

$$ 
\begin{aligned}
\hat{\theta}_n^{(t)} - \hat{\theta}_n &= V^t (\theta^{(0)} - \hat{\theta}_n) \\
\Rightarrow \quad & \left\| \hat{\theta}_n^{(t)} - \hat{\theta}_n \right\|_{2,d}^2 = \left\| V^t (\hat{\theta}_n - \theta^{(0)}) \right\|_{2,d}^2 \\
&= \left\| V^t \hat{\theta}_n \right\|_{2,d}^2 + \left\| V^t \theta^{(0)} \right\|_2^2 - 2 \langle V^t \hat{\theta}_n, V^t \theta^{(0)} \rangle_{\mathbb{R}^d}.
\end{aligned}
$$

Ainsi,

$$ 
\begin{aligned}
E_\epsilon \left[ \left\| V^t \hat{\theta}_n \right\|_{2,d}^2 \right] &= E_\epsilon \left[ \left\| V^t (X^T X)^{-1} X^T Y \right\|_2^2 \right] \\
&= E_\epsilon \left[ \left\| V^t (X^T X)^{-1} X^T (X \theta^* + \epsilon) \right\|_{2,d}^2 \right] \\
&= E_\epsilon \left[ \left\| V^t (X^T X)^{-1} X^T X \theta^* \right\|_{2,d}^2 + \left\| V^t (X^T X)^{-1} X^T \epsilon \right\|_{2,d}^2 \right. \\
& \qquad \left. + 2 \langle V^t (X^T X)^{-1} X^T X \theta^*, V^t (X^T X)^{-1} X^T \epsilon \rangle_{\mathbb{R}^d} \right] \\
&= \left\| V^t \theta^* \right\|_{2,d}^2 + E_\epsilon \left[ \left\| V^t (X^T X)^{-1} X^T \epsilon \right\|_{2,d}^2 \right] \\
&= \left\| V^t \theta^* \right\|_2^2 + \sigma^2 \text{Tr} \left( V^t (X^T X)^{-1} V^t \right).
\end{aligned}
$$
Finalement, on obtient l'expression du critère $Q(\hat{\theta}_n^{(t)})$, $\forall t \in \mathbb{N}$,

$$
\begin{align*}
Q(\hat{\theta}_n^{(t)}) &= E_\epsilon \left[ \| \hat{\theta}_n^{(t)} - \hat{\theta}_n \|_{2,d}^2 \right] \\
&= E_\epsilon \left[ \| V^t \hat{\theta}_n \|_{2,d}^2 \right] + \| V^t \theta^{(0)} \|_{2,d}^2 - 2 \langle V^t \theta^*, V^t \theta_0 \rangle_{\mathbb{R}^d} \\
&= \| V^t \theta^* \|_{2,d}^2 + \sigma^2 \mathrm{Tr} \left( V^t (X^T X)^{-1} V^t \right) + \| V^t \theta^{(0)} \|_{2,d}^2 - 2 \langle V^t \theta^*, V^t \theta^{(0)} \rangle_{\mathbb{R}^d} \\
&= \| V^t (\theta^* - \theta^{(0)}) \|_{2,d}^2 + \sigma^2 \mathrm{Tr} \left( V^t (X^T X)^{-1} V^t \right). \tag{4.3}
\end{align*}
$$

Expression simplifiée de $Q(\hat{\theta}_n^{(t)}) = E_\epsilon[\|\hat{\theta}_n^{(t)} - \hat{\theta}_n\|_{2,d}^2]$

Nous avons une autre expression du critère $Q(\hat{\theta}_n^{(t)}) = E_\epsilon[\|\hat{\theta}_n^{(t)} - \hat{\theta}_n\|_{2,d}^2]$.

D'après l'équation 4.3,

$$
\begin{align*}
E_{\epsilon} \left[ \| \hat{\theta}_{n}^{(t)} - \hat{\theta}_{n} \|_{2,d}^{2} \right] &= \| V^{t} (\theta^{*} - \theta^{(0)}) \|_{2,d}^{2} + \sigma^{2} \mathrm{Tr} \left( V^{t} (X^{T} X)^{-1} V^{t} \right) \\
&= \| V^{t} (\theta^{*} - \theta^{(0)}) \|_{2,d}^{2} + \frac{\sigma^{2}}{n} \mathrm{Tr} \left( V^{t} \left( \frac{X^{T} X}{n} \right)^{-1} V^{t} \right) \\
&= \sum_{i=1}^{d} \rho_{i}^{2t} \left( W_{i}^{2} + \frac{\sigma^{2}}{n \lambda_{i}^{n,d}} \right), \tag{4.4}
\end{align*}
$$

où $W = U^T(\theta^{(0)} - \theta^*); X^T X = UDU^T$ est obtenu par décomposition en valeurs singulières;
$\lambda_1^{n,d} \ge \dots \ge \lambda_d^{n,d} > 0$ sont les valeurs propres de $\frac{1}{n}X^T X; \forall i \in [1,d], \rho_i = 1 - \alpha \lambda_i^{n,d}$. $\square$

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

**Propriété 4.4.2.** D'après le théorème des accroissements finis, nous obtenons un équivalent de
$\log_{10}(Q(\hat{\theta}_n^{(t)}))$ lorsque $t$ tend vers $+\infty$

$$
\log_{10} \left( Q \left( \hat{\theta}_n^{(t)} \right) \right) \underset{t \to +\infty}{\sim} 2t \log_{10} (\rho_d) + \log_{10} (Q(\theta^{(0)})),
$$

où $\forall i \in [1, d]$, $\rho_i = 1 - \alpha \lambda_i^{n,d}$; $\lambda_1^{n,d} \ge \dots \ge \lambda_d^{n,d} > 0$ sont les valeurs propres de $\frac{1}{n}X^T X$.

Démonstration. Nous définissons g par $g: \mathbb{R}^d \to \mathbb{R}$
$(x_1, \dots, x_d) \mapsto \log_{10}(f(x_1, \dots, x_d))$. La fonction
$f$ est définie par $\forall (x_1, \dots, x_d) \in \mathbb{R}^d$, $f(x_1, \dots, x_d) = \sum_{i=1}^d (x_i(W_i^2 + \frac{\sigma^2}{n\lambda_i^{n,d}})) = \sum_{i=1}^d \alpha_i x_i$ où $\forall i \in$
$[1, d]$, $\alpha_i = W_i^2 + \frac{\sigma^2}{n\lambda_i^{n,d}}$.

Soit $\forall x > 0$, $j(x) = \log_{10}(x)$. D'après le théorème des accroissements finis appliqué à la fonction g avec $b = (\rho_1^{2t}, \dots, \rho_d^{2t}) \in \mathbb{R}^d$ et $a = (\rho_d^{2t}, \dots, \rho_d^{2t}) \in \mathbb{R}^d$,

$$
\begin{align*}
g(b) &= g(a) + d g_u(b-a) \\
&= g(a) + \langle \nabla(g)(u), b-a \rangle_{\mathbb{R}^d},
\end{align*}
$$
où $u \in ]a, b[ = \{v \in \mathbb{R}^d : v = \theta b + (1 - \theta)a, \theta \in ]0, 1[\}$.

Nous calculons $dg_u (g = j \circ f), \forall h \in \mathbb{R}^d,$

$$ 
\begin{aligned}
dg_u(h) &= dj_{f(u)}(df_u(h)) \\
&= \frac{df_u(h)}{f(u)},
\end{aligned}
$$

car, $\forall h \in \mathbb{R}, dj_{f(u)}(h) = \frac{h}{f(u)}$.

Nous remarquons que $\forall i \in [1, d]$,

$$ 
\begin{aligned}
\frac{\partial f}{\partial x_i}(u) &= \alpha_i \\
\Rightarrow \forall h \in \mathbb{R}^d, dg_u(h) &= \frac{\langle \nabla(f)(u), h \rangle_{\mathbb{R}^d}}{f(u)} \\
&= \frac{\sum_{i=1}^d \alpha_i h_i}{\sum_{j=1}^d \alpha_j u_j}.
\end{aligned}
$$

Ainsi,

$$ 
\begin{aligned}
g(b) &= g(a) + dg_u(b-a) \\
&= g(a) + \frac{\sum_{i=1}^{d} \alpha_i (\rho_i^{2t} - \rho_d^{2t})}{\sum_{j=1}^{d} \alpha_j u_j}. \qquad (4.5)
\end{aligned}
$$

Nous remarquons que $dg_u(b-a) = \sum_{t \to +\infty} o(g(a))$.

En effet,

$$ 
\begin{aligned}
\frac{dg_u(b-a)}{g(a)} &= \frac{\frac{\sum_{i=1}^{d} \alpha_i (\rho_i^{2t} - \rho_d^{2t})}{\sum_{j=1}^{d} \alpha_j u_j}}{2t \log(\rho_d) + \log_{10}(\sum_{i=1}^{d} \alpha_i)} \\
&= \frac{\frac{\sum_{i=1}^{d} \alpha_i (\left(\frac{\rho_i}{\rho_d}\right)^{2t} - 1)}{\sum_{j=1}^{d} \alpha_j \left(\frac{u_j}{\rho_d^{2t}}\right)}}{2t \log_{10}(\rho_d) + \log(\sum_{i=1}^{d} \alpha_i)}.
\end{aligned}
$$

Comme $\forall i \in [1, d-1], \rho_i < \rho_d \Rightarrow (\frac{\rho_i}{\rho_d})^{2t} \underset{t \to +\infty}{\longrightarrow} 0$. De plus, $\forall j \in [1, d], \frac{u_j}{\rho_d^{2t}} \in ](\frac{\rho_j}{\rho_d})^{2t}, 1[$ alors $\sum_{j=1}^d \alpha_j (\frac{u_j}{\rho_d^{2t}}) \ge \sum_{j=1}^d \alpha_j (\frac{\rho_j}{\rho_d})^{2t}$. Ainsi $\frac{dg_u(b-a)}{g(a)} \underset{t \to +\infty}{\longrightarrow} 0 \Rightarrow dg_u(b-a) = o(g(a)) \Rightarrow g(b) \underset{t \to +\infty}{\sim} g(a)$.

Ainsi,

$$ \log(E_c \left[ \left\| \hat{\theta}_n^{(t)} - \hat{\theta}_n \right\|_{2,d}^2 \right]) \underset{t \to +\infty}{\sim} 2t \log(\rho_d) + \log_{10} \left( \sum_{i=1}^d \left( W_i^2 + \frac{\sigma^2}{n \lambda_i^{n,d}} \right) \right). $$

□
# Conclusion

## Conclusion

Dans ce manuscrit de thèse, nous avons proposé une réponse aux deux premières questions énoncées en introduction. Pour répondre à la première question, nous avons proposé d'utiliser, dans le chapitre 2 et 3, des règles d'arrêts, associées à des algorithmes itératifs, qui optimisent un critère en fonction du nombre d'itérations à distance finie. Un avantage des estimateurs associés à ces règles d'arrêts est leur faible complexité en temps par rapport aux méthodes concurrentes. Néanmoins, nous pouvons calculer ces règles d'arrêts si nous disposons d'un budget de temps suffisant. Lorsque nous disposons d'un budget de temps T limité, nous avons proposé un estimateur, dans le chapitre 4, qui tient compte, en plus du choix de l'itération *t*, du choix de la taille d'échantillon *n* en optimisant un critère en *t* et *n*.

Les règles d'arrêt associées à des algorithmes itératifs, proposées au chapitre 2 et 3, permettent de récupérer un estimateur précis parmi $\{\hat{\theta}^{(t)}\}_{t \in \mathbb{N}}$ et $\{\hat{\tau}_D\}_{D \in [1, n-1]}$ en stoppant un algorithme avant que le phénomène de surapprentissage se produise. Ce phénomène de surapprentissage a été illustré aux chapitres 2 et 3, et justifie d'utiliser de telles règles d'arrêt. En effet, pour le chapitre 2, le théorème 2.2.1) est un résultat de consistance de l'estimateur $\hat{\tau}_D$. De plus, ce théorème montre que l'événement $\{\hat{D} = D^*\}$ est de grande probabilité et donc la règle d'arrêt stoppe l'algorithme KSRBS avant que le phénomène de surapprentissage se produise. De plus, pour le chapitre 3, la règle d'arrêt $\hat{t}$ réalise en plus un compromis biais - variance et donc l'estimateur $\hat{\theta}^{(t)}$ aura tendance à avoir un biais et une variance contrôlés. Nous avons observé sur des simulations que, lorsque *n* est proche de *d*, l'estimateur $\hat{\theta}^{(t)}$ est meilleur qu'une approximation de l'estimateur des moindres carrés (EMC) en matière d'erreur moyenne quadratique. Cette approximation de l'EMC nécessite de stopper l'algorithme à une itération élevée, itération à laquelle le phénomène de surapprentissage se produit.

Les estimateurs $\hat{\tau}_D$ et $\hat{\theta}^{(t)}$ ont aussi l'avantage d'avoir une faible complexité en temps en comparaison respectivement à l'estimateur de KCP et l'approximation de l'EMC $\hat{\theta}_\kappa$. En effet, la complexité de KSRBS est de $O(\hat{D}n^2)$ alors que celle de KCP est de $O(D_{max}n^2)$ sans compter le calcul de $\hat{D}$ par heuristique de pente (où $D_{max}$ est potentiellement grand). L'approximation de l'EMC $\hat{\theta}_\kappa$ a l'inconvénient de dépendre du seuil $\kappa$ qu'il faut choisir arbitrairement. Nous avons observé, sur des simulations, que lorsque $\kappa$ est assez petit, $\hat{\theta}^{(t)}$ est moins coûteux en temps de calcul que $\hat{\theta}_\kappa$.

Nous rencontrons aussi en pratique une situation où nous disposons d'un budget de temps *T* limité. Cette situation est différente de celle utilisant des règles d'arrêts qui suppose que l'on assez de temps pour calculer les règles d'arrêts $\hat{t}$ et $\hat{D}$. Le chapitre 4 montre que le choix du couple $(t', n')$ optimisant le critère $Q(\hat{\theta}_n^{(t)})$ varie en fonction du budget de temps *T* : *n'* est une fonction croissante constante par morceaux en fonction de *T* et $\hat{t}$ est affine par morceaux en
fonction de T. Lorsque $n'$ augmente de $n_1$ à $n_2$, $t'$ diminue car il faut moins d'itérations pour atteindre la précision statistique optimale.
Perspective

Nous avons étudié, dans le chapitre 2, la règle d'arrêt $\hat{D}$ de KSRBS qui dépend du seuil $\zeta_n$. Dans le cadre de la détection de ruptures dans la moyenne d'un signal réel, $\zeta_n$ est choisi égal à $C\hat{\sigma}\sqrt{2\log(n)}$ où C est une constante calibrée telle que $|\hat{D} - D^*|$ soit minimale pour un grand nombre de répétitions et différentes tailles d'échantillon $n$ (FRYZLEWICZ 2014). Nous avons choisi pour KSRBS la même expression de $\zeta_n$ adaptée au cadre des noyaux. Néanmoins, en plus de déterminer $\hat{D}$, $\zeta_n$ détermine si un instant de ruptures candidat est un instant de ruptures estimé ou non. C'est pourquoi, il serait intéressant d'étudier le choix du seuil $\zeta_n$ garantissant de bonnes performances statistiques de l'estimateur $\hat{\tau}_{\hat{D}}$.

Nous nous sommes aussi intéressés dans le chapitre 3 à la règle d'arrêt $\hat{t}$ dans le cadre du problème de régression linéaire. Une autre perspective serait de vérifier que nous pouvons transposer les résultats obtenus dans le cadre de la régression linéaire au cadre de la régression non-paramétrique en utilisant des noyaux. En effet, le théorème du représentant (SCHÖLKOPF, HERBRICH et Alex J. SMOLA 2001) permet de transformer un problème de minimisation du risque empirique sur un RKHS $\mathcal{H}$ en un problème de minimisation sur $\mathbb{R}^n$ (RASKUTTI, WAINWRIGHT et YU 2014) et donc d'utiliser l'algorithme de descente de gradient.

Une perspective serait de construire des règles d'arrêt pour un algorithme de descente de gradient stochastique (SGD). L'étude des règles d'arrêt pour les algorithmes de descente de gradient (GD) est plus simple que pour celle de SGD. En effet, SGD choisit à chaque itération une observation aléatoirement alors que ce n'est pas le cas de GD. Comme la complexité en temps de SGD est inférieure à celle de GD, on peut attendre encore économiser du temps de calcul grâce une règle d'arrêt associée à SGD.

Nous avons abordé au chapitre 4 le choix du couple $(t, n)$ lorsque le budget de temps $T$ est limité. Nous avons obtenu un équivalent de $\log_{10}(Q(\hat{\theta}_n^{(t)}))$ lorsque $t$ tend vers $+\infty$. Cependant, dans la pratique, pour déterminer le couple $(t, n')$, il est nécessaire de pouvoir calculer les valeurs de $Q(\hat{\theta}_n^{(t)})$ lorsque $t$ et $n$ sont grands à partir de l'estimation de $Q(\hat{\theta}_n^{(t)})$ lorsque $t$ et $n$ sont petits dans le but d'économiser du temps de calcul. Une piste à explorer pour résoudre ce problème est de déterminer des équivalents de $Q(\hat{\theta}_n^{(t)})$ pour les deux cas : $t$ est quelconque et $n$ tend vers $+\infty$ ; $t$ et $n$ tendent vers $+\infty$. Une autre piste est de déterminer des estimateurs de paramètres inconnus $(\sigma^2, \theta^*)$ à partir de l'estimation de $Q(\hat{\theta}_n^{(t)})$ lorsque $t$ et $n$ sont petits afin de capter la dynamique de $Q(\hat{\theta}_n^{(t)})$.
Bibliographie

ARLOT, Sylvain, Alain CELISSE et Zaid HARCHAOUI (2012). *Kernel Change-Point Detection*. URL : https://hal.archives-ouvertes.fr/hal-00671174/document.

— (2016). « A Kernel Multiple Change-Point Algorithm via Model Selection ». In : arXiv : 1202.3878.

ARONSZAJN, N. (1950). « Theory of Reproducing Kernels ». In : *Transactions of the American Mathematical Society* 68.3, p. 337–404. ISSN : 0002-9947, 1088-6850. DOI : 10.1090/S0002-9947-1950-0051437-7.

ASPREMONT (2016). *Convex optimization*. Rapp. tech. ENS Ulm.

AUGER, Ivan E. et Charles E. LAWRENCE (1989). « Algorithms for the Optimal Identification of Segment Neighborhoods ». In : *Bulletin of Mathematical Biology* 51.1, p. 39–54. ISSN : 0092-8240, 1522-9602. DOI : 10.1007/BF02458835.

BAUER, Frank, Sergei PEREVERZEV et Lorenzo ROSASCO (2007). « On Regularization Algorithms in Learning Theory ». In : *Journal of Complexity* 23.1, p. 52–72. ISSN : 0885-064X. DOI : 10.1016/j.jco.2006.07.001.

BELLMAN, Richard (1954). « The Theory of Dynamic Programming ». In : *Bulletin of the American Mathematical Society* 60.6, p. 503–515. ISSN : 0002-9904, 1936-881X.

BERLINET, Alain et Christine THOMAS-AGNAN (2004). *Reproducing Kernel Hilbert Spaces in Probability and Statistics*. Boston, MA : Springer US. ISBN : 978-1-4613-4792-7 978-1-4419-9096-9. DOI : 10.1007/978-1-4419-9096-9.

BIAU, Gérard, Kevin BLEAKLEY et David MASON (2015). « Long Signal Change-Point Detection ». In : arXiv : 1504.01702 [math, stat]. URL : http://arxiv.org/abs/1504.01702.

BIRGÉ, Lucien et Pascal MASSART (2007). « Minimal Penalties for Gaussian Model Selection ». In : *Probability Theory and Related Fields* 138 (1-2), p. 33–73. ISSN : 0178-8051, 1432-2064. DOI : 10.1007/s00440-006-0011-8.

BLANCHARD, Gilles, Marc HOFFMANN et Markus REISS (2016). « Optimal Adaptation for Early Stopping in Statistical Inverse Problems ». In : arXiv : 1606.07702 [math, stat].

BLEAKLEY, Kevin et Jean-Philippe VERT (2011). *The Group Fused Lasso for Multiple Change-Point Detection*. URL : https://hal.archives-ouvertes.fr/hal-00602121/document.

BOTTOU, Léon (2010). « Large-Scale Machine Learning with Stochastic Gradient Descent ». In : *Proceedings of COMPSTAT’2010*. Sous la dir. d’Yves LECHEVALLIER et Gilbert SAPORTA. Physica-Verlag HD, p. 177–186. ISBN : 978-3-7908-2603-6 978-3-7908-2604-3.

BOTTOU, Léon et Olivier BOUSQUET (2008). « The Tradeoffs of Large Scale Learning ». In : IN : ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 20, p. 161–168.

BUBECK, Sébastien (2014). « Theory of Convex Optimization for Machine Learning ». In : arXiv : 1405.4980 [cs, math, stat].

CARPENTIER (2014). *Vue d'ensemble de la méthode du gradientstochastique*. Rapp. tech. ENSTA ParisTech.
CELISSE, Alain et al. (2016). *New Efficient Algorithms for Multiple Change-Point Detection with Kernels*. URL: https://hal.inria.fr/hal-01413230/document.

CHO, Haeran et Piotr FRYZLEWICZ (2012). « Multiscale and Multilevel Technique for Consistent Segmentation of Nonstationary Time Series ». In: *Statistica Sinica* 22.1. ISSN: 10170405. DOI: 10.5705/ss.2009.280.

FRYZLEWICZ, Piotr (2014). « Wild Binary Segmentation for Multiple Change-Point Detection ». In: *The Annals of Statistics* 42.6, p. 2243-2281.

FUKUMIZU, Kenji et al. (2007). « Kernel Measures of Conditional Dependence ». In: *Proceedings of the 20th International Conference on Neural Information Processing Systems*. NIPS’07. USA: Curran Associates Inc., p. 489-496. ISBN: 978-1-60560-352-0.

GARREAU, Damien et Sylvain ARLOT (2016). « Consistent Change-Point Detection with Kernels ». In: arXiv: 1612.04740 [math, stat]. URL: http://arxiv.org/abs/1612.04740.

GEY, Servane et Emilie LEBARBIER (2008). *Using CART to Detect Multiple Change Points in the Mean for Large Sample*. URL: https://hal.archives-ouvertes.fr/hal-00327146.

GORDON, Geoff et Ryan TIBSHIRANI (2012). *Subgradient method*. Rapp. tech. Carnegie Mellon University.

GRETTON, Arthur et al. (2012). « A Kernel Two-Sample Test ». In: *J. Mach. Learn. Res.* 13, p. 723-773. ISSN: 1532-4435.

KILLICK, R., P. FEARNHEAD et I. A. ECKLEY (2012). « Optimal Detection of Changepoints With a Linear Computational Cost ». In: *Journal of the American Statistical Association* 107.500, p. 1590-1598.

LAJUGIE, Rémi, Sylvain ARLOT et Francis BACH (2014). « Large-Margin Metric Learning for Constrained Partitioning Problems ». In: *Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32*. T. 32. ICML’14. Beijing, China: JMLR.org, p. I-297-I-305.

LEBARBIER, Emilie (2002). « Quelques Approches Pour La Détection de Ruptures à Horizon Fini ». Thèse de doct. Paris 11.

— (2003). *Detecting Multiple Change-Points in the Mean of Gaussian Process by Model Selection*. Report.

MATTESON, David S. et Nicholas A. JAMES (2014). « A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data ». In: *Journal of the American Statistical Association* 109.505, p. 334-345. ISSN: 0162-1459. DOI: 10.1080/01621459.2013.849605.

NESTEROV, Yurii (2004). *Introductory Lectures on Convex Optimization*. Réd. par Panos M. PARDALOS et Donald W. HEARN. T. 87. Applied Optimization. Boston, MA: Springer US. ISBN: 978-1-4613-4691-3 978-1-4419-8853-9. DOI: 10.1007/978-1-4419-8853-9.

RASKUTTI, Garvesh, Martin J. WAINWRIGHT et Bin Yu (2014). « Early Stopping and Non-Parametric Regression : An Optimal Data-Dependent Stopping Rule ». In: *J. Mach. Learn. Res.* 15.1, p. 335-366.

RIGAILL, Guillem (2010). « A Pruned Dynamic Programming Algorithm to Recover the Best Segmentations with $1$ to $K_{[max]}$ Change-Points ». In: arXiv: 1004.0887 [stat].

SCHÖLKOPF, Bernhard, Ralf HERBRICH et Alex J. SMOLA (2001). « A Generalized Representer Theorem ». In: *Computational Learning Theory*. International Conference on Computational Learning Theory. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, p. 416-426. ISBN: 978-3-540-42343-0 978-3-540-44581-4. DOI: 10.1007/3-540-44581-1_27.

SCHOLKOPF, Bernhard et Alexander J. SMOLA (2001). *Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond*. Cambridge, MA, USA: MIT Press. ISBN: 978-0-262-19475-4.

SCOTT, A. J. et M. KNOTT (1974). « A Cluster Analysis Method for Grouping Means in the Analysis of Variance ». In: *Biometrics* 30.3, p. 507-512. ISSN: 0006-341X. DOI: 10.2307/2529204.
SEBER, George A. F. et Alan J. LEE (2012). *Linear Regression Analysis*. John Wiley & Sons. 585 p.
ISBN: 978-1-118-27442-2.

SNYMAN, Jan (2009). *Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms*. New York: Springer. 258 p.

SRIPERUMBUDUR, Bharath K. et al. (2010). « Hilbert Space Embeddings and Metrics on Probability Measures ». In : *J. Mach. Learn. Res.* 11, p. 1517–1561. ISSN : 1532-4435.

TSUDA, Koji et Bernhard SCHÖLKOPF (2004). « A primer on kernel methods ». In : *in Kernel Methods in Computational*. MIT Press, p. 35–70.

VENKATRAMAN, E.S. (1992). *Consistency results in multiple change-point problems*. Rapp. tech. 24. Department of Statistics, Stanford University.

WRIGHT, F. T. (1973). « A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables Whose Distributions Are Not Necessarily Symmetric ». In : *The Annals of Probability* 1.6, p. 1068–1070. ISSN : 0091-1798. DOI : 10.1214/aop/1176996815.

YAO, Yuan, Lorenzo ROSASCO et Andrea CAPONNETTO (2007). « On Early Stopping in Gradient Descent Learning ». In : *Constructive Approximation* 26.2, p. 289–315.

YUAN, Ya-xiang (1999). « Step-sizes for the gradient method ». In : *American Mathematical Society* 42.2.

ZOU, Changliang et al. (2014). « Nonparametric Maximum Likelihood Approach to Multiple Change-Point Problems ». In : *The Annals of Statistics* 42.3, p. 970–1002. ISSN : 0090-5364. DOI : 10.1214/14-A0S1210. arXiv : 1405.7173. URL : http://arxiv.org/abs/1405.7173.
# Table des matières

<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>
<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>3 Règle d'arrêt et descente de gradient dans le modèle linéaire</td><td>69</td></tr><tr><td>3.1 Règle d'arrêt comme compromis biais-variance</td><td>70</td></tr><tr><td>3.1.1 Estimateurs obtenus par l'algorithme de descente de gradient</td><td>70</td></tr><tr><td>3.1.2 Intérêt de la règle d'arrêt</td><td>71</td></tr><tr><td>3.1.3 Interprétation</td><td>72</td></tr><tr><td>3.1.4 Contrôle du biais et de la variance</td><td>73</td></tr><tr><td>3.1.5 Règle d'arrêt proposée</td><td>75</td></tr><tr><td>3.1.6 Évolution de la règle d'arrêt</td><td>76</td></tr><tr><td>3.2 Résultats numériques</td><td>77</td></tr><tr><td>3.2.1 Objectifs</td><td>77</td></tr><tr><td>3.2.2 Cadre de simulations</td><td>78</td></tr><tr><td>3.2.3 Interprétation</td><td>78</td></tr><tr><td>3.3 Conclusion</td><td>80</td></tr><tr><td>3.4 Preuves</td><td>80</td></tr><tr><td>3.4.1 Formules closes de θ̂(t) et Ŷ̂(t)</td><td>80</td></tr><tr><td>3.4.2 Preuve de la propriété 3.1.1</td><td>85</td></tr><tr><td>3.4.3 Preuve de la propriété 3.1.2</td><td>86</td></tr><tr><td>3.4.4 Preuve du lemme 3.1.1</td><td>87</td></tr><tr><td>3.4.5 Preuve du lemme 3.1.2</td><td>90</td></tr><tr><td>3.4.6 Preuve de la propriété 3.1.3</td><td>94</td></tr><tr><td>4 Estimateur à budget de temps limité</td><td>103</td></tr><tr><td>4.1 Compromis entre temps et taille de l'échantillon</td><td>103</td></tr><tr><td>4.1.1 État de l'art pour les estimateurs à budget de temps limité</td><td>103</td></tr><tr><td>4.1.2 Critère de qualité de l'estimateur</td><td>104</td></tr><tr><td>4.1.3 Optimisation du critère en temps et taille de l'échantillon</td><td>104</td></tr><tr><td>4.2 Simulations</td><td>105</td></tr><tr><td>4.2.1 Objectifs</td><td>105</td></tr><tr><td>4.2.2 Cadre de simulations</td><td>105</td></tr><tr><td>4.2.3 Interprétation</td><td>105</td></tr><tr><td>4.3 Conclusion</td><td>108</td></tr><tr><td>4.4 Preuves</td><td>109</td></tr><tr><td>4.4.1 Formule close du critère Q(θ̂(t))</td><td>109</td></tr><tr><td>4.4.2 Asymptotique de log<sub>10</sub>(Q(θ̂(t))) en t</td><td>110</td></tr><tr><td>Conclusion</td><td>113</td></tr><tr><td>Bibliographie</td><td>117</td></tr><tr><td>Table des matières</td><td>121</td></tr></tbody></table>
# É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