La preuve est issue du cours
[1.19]. On commence par réécrire
(3.23)
\begin{equation*}
\theta_{k+1}-\theta^*=\theta_k-\theta^*-\eta^k \nabla_{\theta} j_{i^r}(\theta_k)
\end{equation*}
dont on calcule la norme au carré
\begin{equation}
\parallel \theta_{k+1}-\theta^*\parallel^2=\parallel \theta_{k}-\theta^*\parallel^2-2 \eta^k\langle \theta_k-\theta_*,
\nabla_{\theta} j_{i^r}(\theta_k)\rangle+\left(\eta_k\right)^2
\parallel \nabla_{\theta} j_{i^r}^2(\theta_k)\parallel^2 .\tag{3.25}
\end{equation}
On définit une loi uniforme discrète \(p_u\) qui tire au sort aléatoirement l’indice \(i_k\) parmi \(\left\{1,...,N\right\}\text{.}\) On remarque que l’espérance selon \(p_u\) est donnée
\begin{equation*}
\mathbb{E}_{p_u}\left[\nabla_{\theta} j_{i^r}(\theta) \right]=\sum_{i=1}^N \nabla_{\theta} j_{i^r=i}(\theta_k)\mathbb{P}(i_r=i)=
\frac{1}{N} \sum_{i=1}^N \nabla_{\theta} j_{i}(\theta_k)=\nabla_{\theta} \mathcal{J}(\theta)
\end{equation*}
On peut calculer l’espérence du carré de la même façon
\begin{equation*}
\mathbb{E}_{p_u}\left[\nabla_{\theta} j_{i^r}(\theta)^2 \right]=\sum_{i=1}^n \nabla_{\theta} j_{i^r=i}(\theta_k)^2\mathbb{P}(i_r=i)=
\frac{1}{N} \sum_{i=1}^N \nabla_{\theta} j_{i}(\theta_k)^2
\end{equation*}
On va maintenant prendre l’espérance de l’égalité
(3.25) et en utilisant les deux identités introduites juste au dessus. On obtient:
\begin{equation*}
\mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]=\parallel \theta_{k}-\theta^*\parallel^2-2 \eta^k\langle \theta_k-\theta_*,
\nabla_{\theta} \mathcal{J}(\theta_k)\rangle+\left(\eta_k\right)^2
\mathbb{E}\left[\parallel \nabla_{\theta} j_{i^r}^2(\theta_k)\parallel^2\right] .
\end{equation*}
\begin{equation*}
\mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]=\parallel \theta_{k}-\theta^*\parallel^2-2 \eta^k\langle \theta_k-\theta_*,
\mathbb{E}_{p_u}\left[\nabla_{\theta} j_{i^r}(\theta) \right]\rangle+\frac{\left(\eta_k\right)^2}{N} \sum_{i=1}^N \nabla_{\theta} j_{i}(\theta_k)^2
\end{equation*}
Maintenant on utilise la \(\alpha\) convexité de la fonction \(\mathcal{J}\text{,}\) on obtient:
\begin{equation}
\mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]\le \left(1-2\eta_k\alpha \right)\parallel \theta_{k}-\theta^*\parallel^2
+ \frac{\left(\eta_k\right)^2}{N} \sum_{i=1}^N \nabla_{\theta} j_{i}(\theta_k)^2\tag{3.26}
\end{equation}
Pour finir on utilise l’hypothèse
(3.24) on obtient:
\begin{equation}
\mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]\le \left(1-2\eta_k\alpha+C\left(\eta_k\right)^2 \right)\parallel \theta_{k}-\theta^*\parallel^2
+ C\left(\eta_k\right)^2\tag{3.27}
\end{equation}
On pose le coefficient d’amplification
\begin{equation*}
\beta_k = 1-2\eta_k\alpha+C\left(\eta_k\right)^2
\end{equation*}
qui est plus petit que strictement inférieur à un sous la condition sur \(\eta_k\) introduite dans la proposition. Par récurrence on a:
\begin{equation}
\mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]\le c_k\parallel \theta_{k}-\theta^*\parallel^2 + C c_k \sum_{i=1}^k \frac{(\eta_i)^2}{c_i}
+ C\left(\eta_k\right)^2\tag{3.28}
\end{equation}
avec \(c_k=\Pi_{i=1}^N \beta_i\text{.}\) On va maintenant conclure à la convergence si \(0 \lt \alpha \lt \frac12\text{,}\) le choix \(\eta_k=\frac{1}{k+1}\) conduit à
\begin{equation*}
\beta_k=1-\frac{2 \alpha}{k+1}+\mathcal{O}\left(k^{-2}\right), \quad c_k=O\left(k^{-2 \alpha}\right), \quad
c_k \sum_{i=0}^k \frac{\left(\eta_i\right)^2}{c_i}=\mathcal{O}\left(k^{-2 \alpha}\right),
\end{equation*}
Cela permet de conclure la preuve.