3.4. Gradient stochastique

Il s’agit ici de présenter l’algorithme du gradient stochastique et de prouver uniquement la convergence en norme \(\mathbf{L}^2\) dans un cadre fortement convexe.

3.4.1. Préliminaires déterministes

Soit \(g:\mathbf{R}^d \to \mathbf{R}\) une fonction réelle de classe \(\mathcal{C}^1\) \(\alpha\)–fortement convexe sur \(\mathbf{R}^d\) c’est à dire telle qu’il existe \(\alpha > 0\)

\[\begin{equation*} \forall \theta, \theta' \in \mathbf{R}^d, \quad g(\theta) - g(\theta') \ge \langle \nabla g(\theta'), \theta - \theta' \rangle + \frac{\alpha}{2} |\theta - \theta'|^2, \end{equation*}\]

où \(\nabla g: \mathbf{R}^d \to \mathbf{R}^d\) est le gradient de \(g\). Sous cette hypothèse (plus forte que la stricte convexité car \(\alpha > 0\)), il existe un unique minimum \(\theta^*\) de \(g\), i.e. \(\operatorname{argmin}(g) = \{\theta^*\}\), et le gradient s’annule en \(\theta^*\), \(\nabla g(\theta^*) = 0\). Cette hypothèse \(g\) \(\alpha\)–fortement convexe peut s’exprimer directement sur le gradient en remarquant

\[\begin{equation*} \begin{aligned} g(\theta^*) - g(\theta) &\ge \langle \nabla g(\theta), \theta^* - \theta \rangle + \frac{\alpha}{2} |\theta^* - \theta|^2, \\ g(\theta) - g(\theta^*) &\ge \langle \nabla g(\theta^*), \theta - \theta^* \rangle + \frac{\alpha}{2} |\theta - \theta^*|^2, \end{aligned} \end{equation*}\]

donc en sommant ces 2 inégalités et en utilisant \(\nabla g(\theta^*) = 0\) on obtient

\[\begin{equation*} 0 \ge \langle \nabla g(\theta), \theta^* - \theta \rangle + \alpha |\theta - \theta^*|^2 \end{equation*}\]

Le problème initiale d’optimisation de la fonction \(\alpha\)–fortement convexe \(g\) se ramène à la recherche du zéro d’une fonction \(f:\mathbf{R}^d \to \mathbf{R}^d\) (qui est un gradient) vérifiant \(\{f = 0\} = \{\theta^*\}\) et

\[\begin{equation*} \forall \theta \in \mathbf{R}^d, \quad \langle f(\theta), \theta - \theta^* \rangle \ge \alpha |\theta - \theta^*|^2. \end{equation*}\]

Un algorithme déterministe, appelé algorithme de Newton-Raphson, converge vers le zéro \(\theta^* \in \mathbf{R}^d\) et est défini par la suite

\[\begin{equation*} \begin{cases} \theta_0 \in \mathbf{R}^d \\ \theta_{k+1} = \theta_k - [J_f(\theta_k)]^{-1} f(\theta_k) \end{cases} \end{equation*}\]

où \(J_f(\theta)\) est la matrice jacobienne de \(f\) (la Hessienne de la fonction \(g\) si \(f = \nabla g\)). Cette matrice jacobienne indique la pente optimale (se convaincre avec \(d = 1\) ou voir le cours d’optimisation) à suivre pour converger vers le zéro \(\theta^*\). Si la matrice jacobienne de \(f\) n’est pas connue on peut considérer une variante non-optimale

(3.13)\[ \theta_{k+1} = \theta_k - \gamma_{k+1} f(\theta_k)\]

avec \((\gamma_n)_{n \ge 1}\) une suite de réels positifs qui tend vers 0 telle que \(\sum_n \gamma_n = +\infty\). Pour cet algorithme non-optimal à pas décroissant, on peut aussi prouver que \(\lim_n \theta_n = \theta^*\).

3.4.2. Cadre probabiliste

Supposons maintenant que la fonction \(f\) a la représentation probabiliste suivante

\[\begin{equation*} \forall \theta \in \mathbf{R}^d, \quad f(\theta) = \mathbf{E} \big[ F(\theta, X) \big], \end{equation*}\]

où \(X\) est une variable aléatoire à valeurs dans \(\mathbf{R}^q\) et \(F:\mathbf{R}^d \times \mathbf{R}^q \to \mathbf{R}^d\) est une application mesurable. L’algorithme \eqref{eq:algo_newton} s’écrit alors

(3.14)\[\begin{equation} \theta_{k+1} = \theta_k - \gamma_{k+1} \mathbf{E}\big[F(\theta_k, X) \big], \end{equation}\]

et pour le calcul de \(\mathbf{E} \big[ F(\theta_k, X) \big]\) on peut considérer un estimateur de Monte Carlo de la forme \(\frac{1}{n} \sum_{j=1}^n F(\theta_k, X_k^{(j)})\) où la suite doublement indicée \((X_k^{(j)})_{k \ge 1,j \ge 1}\) est i.i.d. de même loi que \(X\). L’algorithme du gradient stochastique s’écrit avec le choix particulier (et remarquable) \(n = 1\), c’est à dire qu’il s’écrit

(3.15)\[ \theta_{k+1} = \theta_k - \gamma_{k+1} F(\theta_k, X_{k+1}),\]

où \((X_k)_{k \ge 1}\) est une suite i.i.d. de copies de \(X\). Voici un résultat de convergence.

Proposition 3.9

Soit \(\theta_0 \in \mathbf{R}^d\) fixé et \((\theta_k)_{k \ge 1}\) définie par la récurrence (3.15) où \(f(\theta) = \mathbf{E}\big[F(\theta, X) \big]\) vérifie

\[\begin{equation*} \exists \alpha > 0, \quad \forall \theta \in \mathbf{R}^d, \quad \langle f(\theta), \theta - \theta^* \rangle \ge \alpha |\theta - \theta^*|^2, \end{equation*}\]

et \(\theta \mapsto F(\theta, X)\) est à croissance sous-linéaire en norme \(\mathbf{L}^2\) i.e.

\[\begin{equation*} \exists B > 0, L \ge 0, \quad \mathbf{E} \big[|F(\theta, X)|^2 \big] \le B + L |\theta - \theta^*|^2. \end{equation*}\]

Alors \(\lim_{n \to \infty} \|\theta_n - \theta^*\|_{_2} = 0\).

Proof. Par définition de l’algorithme (3.15) on a

\[\begin{equation*} |\theta_{k+1} - \theta^*|^2 = |\theta_k - \theta^*|^2 - 2 \gamma_{k+1} \langle \theta_k - \theta^*, F(\theta_k, X_{k+1}) \rangle + \gamma_{k+1}^2 |F(\theta_k, X_{k+1})|^2, \end{equation*}\]

et en posant \(D_{k+1} = \langle \theta_k - \theta^*, F(\theta_k, X_{k+1}) - f(\theta_k) \rangle\) on a

\[\begin{equation*} |\theta_{k+1} - \theta^*|^2 = |\theta_k - \theta^*|^2 - 2 \gamma_{k+1} \langle \theta_k - \theta^*, f(\theta_k) \rangle + 2 \gamma_{k+1} D_{k+1} + \gamma_{k+1}^2 |F(\theta_k, X_{k+1})|^2. \end{equation*}\]

Par l’hypothèse sur \(f\) on obtient

(3.16)\[ |\theta_{k+1} - \theta^*|^2 \le (1 - 2 \alpha \gamma_{k+1}) |\theta_k - \theta^*|^2 + 2 \gamma_{k+1} D_{k+1} + \gamma_{k+1}^2 |F(\theta_k, X_{k+1})|^2.\]

La variable \(D_{k+1}\) est d’espérance nulle car \(X_{k+1}\) est indépendante de \(\theta_k\) et en préconditionnant par rapport à \(\theta_k\) on obtient

\[\begin{equation*} \mathbf{E}[D_{k+1}] = \mathbf{E}\big[ \mathbf{E}[D_{k+1} | \theta_k] \big] = \mathbf{E}\big[ \langle \theta_k - \theta^*, \mathbf{E}[F(\theta_k, X_{k+1})|\theta_k] - f(\theta_k) \rangle \big] = 0 \end{equation*}\]

car \(\mathbf{E}\big[F(\theta_k, X_{k+1})|\theta_k\big] = f(\theta_k)\). Ainsi en prenant l’espérance de (3.16) on obtient

\[\begin{equation*} \mathbf{E} \big[|\theta_{k+1} - \theta^*|^2 \big] \le (1 - 2 \alpha \gamma_{k+1}) \mathbf{E} \big[|\theta_k - \theta^*|^2 \big] + \gamma_{k+1}^2 \mathbf{E}\big[| F(\theta_k, X_{k+1})|^2 \big]. \end{equation*}\]

Par l’hypothèse (essentielle) de croissance sous-linéaire de \(\theta \mapsto F(\theta, X)\) en norme \(\mathbf{L}^2\) on a

\[\begin{equation*} \mathbf{E} \big[|\theta_{k+1} - \theta^*|^2\big] \le (1 - 2 \alpha \gamma_{k+1} + L \gamma_{k+1}^2) \mathbf{E}\big[|\theta_k - \theta^*|^2 \big] + \gamma_{k+1}^2 B. \end{equation*}\]

On conclut par le lemme de Gronwall discret.