Vitesse convergence algorithme stochastique

GumbellB

Bonsoir amis mathématiciens !!!

Je vous propose en ce samedi soir un petit problème sur la vitesse de convergence $L^2$ d'un algorithme stochastique. Je mets l'énoncé puis mes réponses (pour faciliter la lecture ).Soit $H : \mathbb{R}^d \times \mathbb{R}^q \rightarrow \mathbb{R}^d$ une fonction borélienne et $Z : (\Omega, \mathcal{A}, \mathbb{P}) \rightarrow \mathbb{R}^q$ un vecteur aléatoire vérifiant $$\forall y \in \mathbb{R}^d, \| H(y,Z)\| \leq C_{H,Z} (1 + |y|)$$
0. Montrer que l'égalité $h(y) = \mathbb{E}H(y,Z)$ définit bien une fonction (borélienne) $h : \mathbb{R}^d \rightarrow \mathbb{R}^d$ vérifiant $$\forall y \in \mathbb{R}^d,\ |h(y)| \leq C_{H,Z} (1 + |y|)
$$ On définit par récurrence l'algorithme stochastique
$$Y_{n+1} = Y_n - \gamma_{n+1} H(Y_n, Z_{n+1}), Y_0 \in L^2(\Omega, \mathcal{A}, \mathbb{P})$$ où $(Z_n)$ désigne une suite de copies indépendantes de $Z$ définies sur ce même espace de probabilités $(\Omega, \mathcal{A}, \mathbb{P})$ et $(\gamma_n)_{n \geq 1}$ une suite de pas strictement positifs vérifiant $\lim\limits_{n}{\gamma_n} = 0$
1. On suppose dans toute la suite du problème qu'il existe $y^* \in \mathbb{R}^d$ et une constante réelle $c > 0$ telle que $$\forall y \in \mathbb{R}^d, (y - y^* | h(y)) \geq c|y - y^*|^2
$$ 1.a. Montrer que $\{ h = 0 \} = \{ y^* \}$.
1.b. Montrer que, sous des hypothèses additionnelles que l'on précisera avec soin, la suite $(Y_n)_{n \geq 0}$ converge p.s. vers $y^*$ (des arguments précis sur $h$ et $(\gamma_n)_{n \geq 1}$ sont demandés).
2. Pour tout $n \geq 0$, on pose $\varepsilon_n = \mathbb{E}|Y_n - y^*|^2$.
2.a. Montrer que, pour tout $n \geq 0$, $$\varepsilon_{n+1} \leq \varepsilon_n - 2 c \gamma_{n+1} \varepsilon_n + \gamma_{n+1}^2 \mathbb{E}|H(Y_n,Z_{n+1})|^2
$$ 2.b. Montrer que pour tout $n \geq 0$, $\mathbb{E}|H(Y_n,Z_{n+1})|^2 \leq C'(1 + \varepsilon_n)$ et en déduire que $$\varepsilon_{n+1} \leq \varepsilon_n ( 1 - 2 c \gamma_{n+1} + C'\gamma_{n+1}^2) + C'\gamma_{n+1}^2$$

GumbellB

Toutes vos remarques sont les bien venues.

0. Soit $y \in \mathbb{R}^d$. On a : $\|H(y,Z)\|_2 \leq C_{H,Z} (1 + |y|)$
d'où a fortiori, $H(y,Z) \in L^2(\Omega)$, puis $H(y,Z) \in L^1(\Omega)$.
On a également en utilisant l'inégalité de Cauchy-Schwarz :
\begin{eqnarray*}
|\mathbb{E}H(y,Z)| &\leq& \left( \mathbb{E}|H(y,Z)|^2 \right)^{\frac{1}{2}} \\
&=& \| H(y,Z)\|_2 \\
&\leq& C_{H,Z}(1 + |y|)
\end{eqnarray*}
Pour tout pavé $A \subset \mathbb{R}^d$, on a donc : \quad $\displaystyle \int_{A} \mathbb{E}H(y,Z) dy \leq \int_{A} C_{H,Z} (1 + |y|) dy < +\infty$
Par Fubini, on en déduit que $h(y) = \mathbb{E}H(y,Z)$ est mesurable de $A$ dans $\mathbb{R}$.
$h : \mathbb{R}^d \rightarrow \mathbb{R}^d$ est donc bien une fonction borélienne vérifiant : $\forall y \in \mathbb{R}^d,\ |h(y)| \leq C_{H,Z} (1 + |y|)$
1.a. Soit $y \in \{ h = 0 \}$. On a alors : \quad $(y - y^* | h(y)) = 0$
Soit comme $(y - y^* | h(y)) \geq c|y - y^*|$, $|y - y^*|$. Soit finalement, $y = y^*$.
On a donc : $\{ h = 0 \} = \{ y^* \}$
1.b. No idea.

2.a. Soit $n \in \mathbb{N}$.
\begin{eqnarray*}
\varepsilon_{n+1} &=& \mathbb{E}|Y_{n+1} - y^*|^2 \\
&=& \mathbb{E}|Y_n - \gamma_{n+1}H(Y_n,Z_{n+1}) - y^*|^2 \\
&=& \mathbb{E}|Y_n - y^*|^2 + \gamma_{n+1}^2 \mathbb{E}|H(Y_n,Z_{n+1})|^2 - 2\gamma_{n+1}\mathbb{E}[(Y_n - y^*|H(Y_n,Z_{n+1})] \\
&=& \varepsilon_n + \gamma_{n+1}^2 \mathbb{E}|H(Y_n,Z_{n+1})|^2 - 2\gamma_{n+1}(\mathbb{E}(Y_n - y^*)|\mathbb{E}(H(Y_n,Z_{n+1})) \\
&=& \varepsilon_n + \gamma_{n+1}^2 \mathbb{E}|H(Y_n,Z_{n+1})|^2 - 2\gamma_{n+1}(\mathbb{E}(Y_n - y^*)|h(Y_n)) \\
&\leq& \varepsilon_n + \gamma_{n+1}^2 \mathbb{E}|H(Y_n,Z_{n+1})|^2 - 2\gamma_{n+1}c\mathbb{E}|Y_n - y^*|^2
\end{eqnarray*}
Soit finalement : \quad $\varepsilon_{n+1} \leq \varepsilon_n - 2 c \gamma_{n+1} \varepsilon_n + \gamma_{n+1}^2 \mathbb{E}|H(Y_n,Z_{n+1})|^2$
2.b. Soit $n \in \mathbb{N}$.
\begin{eqnarray*}
\mathbb{E}|H(Y_n,Z_{n+1})|^2 &=& \mathbb{E}[\mathbb{E}[|H(Y_n,Z_{n+1})|^2|Y_n]]
\end{eqnarray*}