Descente de gradients et variantes

Pour ce TP noté, vous devrez charger votre fichier sur Moodle, avant 22h, jeudi 09/03/2023.

Important

Pour ce travail vous devez déposer un unique fichier au format .py, structuré avec des cellules, dont le nom est tp_note_HAX606X_Prenom_Nom.py. Vous remplirez votre nom, prénom de manière adéquate. Si le nom de fichier ne suit pas cette forme, vous perdez 1 pt.

De plus, les personnes qui n’auront pas soumis leur devoir sur Moodle avant la limite obtiendront comme note zéro. Ainsi, pensez à soumettre une version provisoire par sécurité…

La note totale est sur 20 points répartis comme suit :

qualité des réponses aux questions : 15 pts,
qualité de rédaction et d’orthographe : 1 pts,
qualité des graphiques (légendes, couleurs) : 1 pt
qualité du code (noms de variables clairs, commentaires, code synthétique, etc.) : 2 pt
reproductibilité (exécution correcte sur la machine du correcteur) et absence de bug : 1 pt

Notation

Pour un vecteur x\in\mathbb{R}^d, on rappelle que la norme euclidienne est ||x||_2=\sqrt{\sum_{i=1}^d x_i^2} et la norme infinie est donnée par ||x||_\infty = \max(|x_i|, i=1,\dots,d).

Algorithme de la descente de gradient

On donne ici l’algorithme de descente de gradient pour une fonction différentiable f:\mathbb{R}^d \to \mathbb{R},

    \begin{algorithm}
    \caption{Descente de gradient}
    \begin{algorithmic}
    \INPUT $\nabla f~(\texttt{function}), x_{\rm init}~(\texttt{numpy.ndarray}), \gamma~(\texttt{float}), \epsilon~(\texttt{float}), n_{\rm iter}~(\texttt{int})$
    \STATE $x \gets x_{\rm init}$
    \COMMENT{Initialization}
    \FOR{$i=1,\dots,n_{\rm iter}$}
        \STATE $g \gets \displaystyle \nabla f (x)$
        \IF{$\|g\|_{\infty} \leq \epsilon$}
            \STATE Break
        \ENDIF
        \STATE $x \gets x - \gamma g$
    \ENDFOR
    \OUTPUT $x$
    \end{algorithmic}
    \end{algorithm}

Question 1a : Coder la descente de gradient

Adapter et coder en Python l’Algorithme ci-dessus pour avoir en sortie la liste de tous les itérés de la descente de gradient. Pour ce faire, on veillera à ce que le code puisse traiter le cas d’un vecteur x\in\mathbb{R}^d avec d quelconque, et pas uniquement le cas bi-dimensionnel (cf. question suivante). Pour vous aider, les éléments entre parenthèses indiquent le type des entrées/sorties, type que l’on obtient par exemple avec la commande type:

<class 'numpy.ndarray'>

Question 1b : Test multi-dimensionnel

Proposez un test de l’algorithme sur une fonction simple (par exemple quadratique) avec un espace de départ de dimension d=23.

Question 1c : Test unidimensionnel

Prenons f:x\mapsto (x-1)^2. Utiliser la fonction subplots de matplotlib pour créer deux graphiques l’un au dessus de l’autre, en affichant les 15 premiers itérés avec un pas de 0.1 et une tolérance de 10^{-15}, et une initialisation x_{\rm init} = x_0= -1/2:

afficher sur le graphique du haut la fonction f (en bleu et en trait continu) ainsi que la suite des valeurs prise par la fonction f sur les itérés de la descente de gradient, c’est-à-dire \big(f(x_k)\big)_{k=0,\dots, 14} (en rouge, avec des marqueurs de votre choix).
afficher sur le graphique du bas la trajectoire de l’amplitude de la dérivée, évaluée en chaque itéré, c’est-à-dire \big(|\nabla f(x_k)|\big)_{k=0,\dots, 14}.

L’axe des abscisses sera partagé entre les deux figures en utilisant l’argument sharex de la fonction subplots. Le résultat attendu pourra s’inspirer de la Figure 1 ci-dessous.

Figure 1: Descente de gradient sur la fonction test

Question 2 : Test et visualisation sur le fonction de Rosenbrock

Afficher sur un même graphique les lignes de niveaux de la fonction de Rosenbrock f_{\mathit{ros}} en dimension d=2: \begin{align*} f_{\mathit{ros}}: \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \mapsto (x_1 - 1) ^ 2 + 100 \cdot (x_2-x_1^2) ^ 2 \enspace, \end{align*} ainsi que tous les itérés de l’algorithme de descente de gradient pour n_{\rm iter}=30, \epsilon=10^{-10} en partant du point x_{\rm init}=(-1, -0.5) et pour deux choix de pas \gamma=10^{-5} ou \gamma=10^{-3}. On pourra par exemple utiliser scipy.optimize.rosen_der pour cela. Pour l’affichage graphique, on pourra s’inspirer de l’exemple donné ci-dessous:

Figure 2: Variantes de descente de gradient

Adapter le pas dans la descente de gradient

Question 3 : Algorithme de descente de gradient avec recherche linéaire

La méthode de recherche linéaire (🇬🇧: line search) permet de multiplier ou de diviser \gamma_k, la taille du pas courant à l’itération k, d’un facteur \tau, si la fonction n’a pas assez décru (ce qui est quantifié par un nouveau paramètre \alpha).

    \begin{algorithm}
    \caption{Descente de gradient avec recherche linéaire }
    \begin{algorithmic}
    \INPUT $f~(\texttt{function})$,$\nabla f~(\texttt{function})$,$ x_{\rm init}~(\texttt{numpy.ndarray})$,$ \gamma~(\texttt{float})$,$ \epsilon~(\texttt{float})$,$ n_{\rm iter}~(\texttt{int})$,$ \alpha~(\texttt{float})$,$ \tau~(\texttt{float})$ \\

    \STATE $x \gets x_{\rm init}$
    \COMMENT{Initialization}
    \FOR{$i=1,\dots,n_{\rm iter}$}
        \STATE $g \gets \displaystyle \nabla f (x)$
        \IF{$\|g\|_{\infty} \leq \epsilon$}
            \STATE Break
        \ENDIF
        \STATE $z \gets x - \gamma g$
        \IF{$f(z) \leq f(x) - \alpha \gamma \|g\|_2^2$}
            \STATE $x \gets z $
            \STATE $\gamma \gets \gamma /\tau $
        \ELSE
            \STATE $\gamma \gets \tau \gamma $
        \ENDIF
    \ENDFOR
    \OUTPUT $x~(\texttt{numpy.ndarray})$
    \end{algorithmic}
    \end{algorithm}

Adapter et coder en Python l’algorithme ci-dessus pour avoir en sortie la liste de tous les itérés obtenus par la descente de gradient avec recherche linéaire, mais aussi la liste de tous les pas \gamma_k utilisés. Dans la suite on utilisera \alpha =0.5, \tau=0.5.

Question 4 : Algorithme de descente de gradient avec recherche linéaire

La méthode du pas adaptatif permet d’adapter la taille du pas courant \gamma_k de manière plus souple que la méthode précédente. Représenter sur un même graphique l’évolution de la taille des pas au cours des itérations pour les trois algorithmes introduits.

    \begin{algorithm}
    \caption{Descente de gradient avec recherche linéaire }
    \begin{algorithmic}
    \INPUT $\nabla f~(\texttt{function})$,$ x_{\rm init}~(\texttt{numpy.ndarray})$,$ \gamma~(\texttt{float})$,$ \epsilon~(\texttt{float})$,$ n_{\rm iter}~(\texttt{int})$ \\
    \COMMENT{Initialization}
    \STATE $\gamma_0 \gets \gamma$
    \STATE $x_0 \gets x_{\rm init}$
    \STATE $x_1 \gets x_{0} - \gamma_0 \nabla f(x_0)$
    \STATE $\theta_0 \gets +\infty$
    \FOR{$i=1,\dots,n_{\rm iter}$}
        \STATE $\gamma_k \gets  \min \left(\sqrt{1+\theta_{k-1}} \gamma_{k-1},\frac{1}{2} \frac{\|x_k - x_{k-1}\|}{\|
        \nabla f (x_k) - \nabla f (x_{k-1})\|} \right)$
        \STATE $g \gets \displaystyle \nabla f (x_k)$
        \IF{$\|g\|_{\infty} \leq \epsilon$}
            \STATE Break
        \ENDIF
        \STATE $x_{k+1} \gets x_k - \gamma_k g$
        \STATE $\theta_k \gets \frac{\gamma_k}{\gamma_{k-1}} $
    \ENDFOR
    \OUTPUT $x_k ~(\texttt{numpy.ndarray})$
    \end{algorithmic}
    \end{algorithm}

La méthode du pas adaptatif permet d’adapter la taille du pas courant \gamma_k de manière plus souple. Représenter sur un même graphique l’évolution de la taille des pas au cours des itérations, et ce pour les trois algorithmes introduits.

Question 5 : comparaison des convergences en fonction des itérés

Le minimum global de la fonction de Rosenbrock f_{ros} est atteint en x^\star = (1,1), c’est-à-dire:

x^\star \in \displaystyle\operatorname*{argmin}_{x\in\mathbb{R}^2}f_{ros}(x) \enspace.

Note

Pour une fonction g, la notation x^* \in \displaystyle\operatorname*{argmin}_{x}g(x) signifie que x^* est un point qui atteint la valeur \displaystyle\min_{x}g(x), ainsi: g(x^*)=\displaystyle\min_{x}g(x).

Comparer la convergence de ces trois méthodes de la manière suivante :

Représenter sur les lignes de niveau de la fonction de Rosenbrock l’image des itérés courants. On pourra tenter de reproduire la Figure 2 pour les choix de pas (initiaux) et de vecteur x_{\rm init} similaires.
Représenter sur un premier graphique la norme du gradient en l’itéré courant en fonction de l’indice de l’itération pour chacune des trois méthodes.
Tracer sur un second graphique la distance (euclidienne) de l’itéré courant x_k à x^\star.
Quelle méthode vous semble être la plus/moins avantageuse (justifier très brièvement à partir de vos graphiques)? La réponse sera écrite dans un bref commentaire de quelques lignes dans votre fichier py.

Pour améliorer la lisibilité du graphique, nous rappelons que l’usage d’une échelle logarithmique sur la mesure observée peut être utile.

--- title: "Descente de gradients et variantes" toc: true lang: fr jupyter: python3 format: html: toc-location: left toc-depth: 6 code-tools: true self-contained: true page-layout: article fig-format: retina echo: false code-fold: true html-math-method: katex header-includes: | <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/pseudocode@latest/build/pseudocode.min.css"> <script src="https://cdn.jsdelivr.net/npm/pseudocode@latest/build/pseudocode.min.js"> </script> include-after: | <script> pseudocode.renderClass("pseudocode"); </script> <script>qu pseudocode.renderElement(document.getElementById("gd"),{ noEnd: true }); </script> <script> pseudocode.renderElement(document.getElementById("gd_adapt"),{ noEnd: true }); </script> <script> pseudocode.renderElement(document.getElementById("gd_rech_lin"),{ noEnd: true }); </script> --- Pour ce TP noté, vous devrez charger votre fichier sur Moodle, avant 22h, jeudi 09/03/2023. ::: {.callout-important} Pour ce travail vous devez déposer un **unique** fichier au format `.py`, structuré avec des cellules, dont le nom est `tp_note_HAX606X_Prenom_Nom.py`. Vous remplirez votre nom, prénom de manière adéquate. Si le nom de fichier ne suit pas cette forme, <span style="color:red">vous perdez 1 pt</span>. De plus, les personnes qui n'auront pas soumis leur devoir sur Moodle avant la limite obtiendront comme note <span style="color:red"> **zéro**</span>. Ainsi, pensez à soumettre une version provisoire par sécurité... ::: La note totale est sur **20** points répartis comme suit : - qualité des réponses aux questions : **15** pts, - qualité de rédaction et d’orthographe : **1** pts, - qualité des graphiques (légendes, couleurs) : **1** pt - qualité du code (noms de variables clairs, commentaires, code synthétique, etc.) : **2** pt - reproductibilité (exécution correcte sur la machine du correcteur) et absence de bug : **1** pt ::: {.hidden} $$ \DeclareMathOperator*{\argmin}{argmin} $$ ::: ## Notation Pour un vecteur $x\in\mathbb{R}^d$, on rappelle que la norme euclidienne est $||x||_2=\sqrt{\sum_{i=1}^d x_i^2}$ et la norme infinie est donnée par $||x||_\infty = \max(|x_i|, i=1,\dots,d)$. ## Algorithme de la descente de gradient On donne ici l'algorithme de descente de gradient pour une fonction différentiable $f:\mathbb{R}^d \to \mathbb{R}$, <pre id="gd" class="pseudocode" style="display:hidden;"> \begin{algorithm} \caption{Descente de gradient} \begin{algorithmic} \INPUT $\nabla f~(\texttt{function}), x_{\rm init}~(\texttt{numpy.ndarray}), \gamma~(\texttt{float}), \epsilon~(\texttt{float}), n_{\rm iter}~(\texttt{int})$ \STATE $x \gets x_{\rm init}$ \COMMENT{Initialization} \FOR{$i=1,\dots,n_{\rm iter}$} \STATE $g \gets \displaystyle \nabla f (x)$ \IF{$\|g\|_{\infty} \leq \epsilon$} \STATE Break \ENDIF \STATE $x \gets x - \gamma g$ \ENDFOR \OUTPUT $x$ \end{algorithmic} \end{algorithm} </pre> #### Question 1a : Coder la descente de gradient Adapter et coder en `Python` l'Algorithme ci-dessus pour avoir en sortie la liste de tous les itérés de la descente de gradient. Pour ce faire, on veillera à ce que le code puisse traiter le cas d'un vecteur $x\in\mathbb{R}^d$ avec $d$ quelconque, et pas uniquement le cas bi-dimensionnel (cf. question suivante). Pour vous aider, les éléments entre parenthèses indiquent le type des entrées/sorties, type que l'on obtient par exemple avec la commande `type`: ```{python} #| eval: true import numpy as np vecteur = np.array([1,2,3,4]) print(type(vecteur)) ``` #### Question 1b : Test multi-dimensionnel Proposez un test de l'algorithme sur une fonction simple (par exemple quadratique) avec un espace de départ de dimension $d=23$. #### Question 1c : Test unidimensionnel Prenons $f:x\mapsto (x-1)^2$. Utiliser la fonction `subplots` de `matplotlib` pour créer deux graphiques l'un au dessus de l'autre, en affichant les $15$ premiers itérés avec un pas de $0.1$ et une tolérance de $10^{-15}$, et une initialisation $x_{\rm init} = x_0= -1/2$: - afficher sur le graphique du haut la fonction $f$ (en bleu et en trait continu) ainsi que la suite des valeurs prise par la fonction $f$ sur les itérés de la descente de gradient, c'est-à-dire $\big(f(x_k)\big)_{k=0,\dots, 14}$ (en rouge, avec des marqueurs de votre choix). - afficher sur le graphique du bas la trajectoire de l'amplitude de la dérivée, évaluée en chaque itéré, c'est-à-dire $\big(|\nabla f(x_k)|\big)_{k=0,\dots, 14}$. L'axe des abscisses sera partagé entre les deux figures en utilisant l'argument `sharex` de la fonction `subplots`. Le résultat attendu pourra s'inspirer de la @fig-gd-test ci-dessous. ::: {layout-ncol=1} ![Descente de gradient sur la fonction test](./grad_descent_test.svg){#fig-gd-test} ::: #### Question 2 : Test et visualisation sur le fonction de Rosenbrock Afficher sur un même graphique les lignes de niveaux de la fonction de Rosenbrock $f_{\mathit{ros}}$ en dimension $d=2$: $$ \begin{align*} f_{\mathit{ros}}: \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \mapsto (x_1 - 1) ^ 2 + 100 \cdot (x_2-x_1^2) ^ 2 \enspace, \end{align*} $$ ainsi que tous les itérés de l'algorithme de descente de gradient pour $n_{\rm iter}=30$, $\epsilon=10^{-10}$ en partant du point $x_{\rm init}=(-1, -0.5)$ et pour deux choix de pas $\gamma=10^{-5}$ ou $\gamma=10^{-3}$. On pourra par exemple utiliser `scipy.optimize.rosen_der` pour cela. Pour l'affichage graphique, on pourra s'inspirer de l'exemple donné ci-dessous: ::: {layout-ncol=1} ![Variantes de descente de gradient](./small_steps.svg){#fig-gd} ::: ## Adapter le pas dans la descente de gradient #### Question 3 : Algorithme de descente de gradient avec recherche linéaire La méthode de recherche linéaire (🇬🇧: *line search*) permet de multiplier ou de diviser $\gamma_k$, la taille du pas courant à l'itération $k$, d'un facteur $\tau$, si la fonction n'a pas assez décru (ce qui est quantifié par un nouveau paramètre $\alpha$). <pre id="gd_rech_lin" class="pseudocode" style="display:hidden;"> \begin{algorithm} \caption{Descente de gradient avec recherche linéaire } \begin{algorithmic} \INPUT $f~(\texttt{function})$,$\nabla f~(\texttt{function})$,$ x_{\rm init}~(\texttt{numpy.ndarray})$,$ \gamma~(\texttt{float})$,$ \epsilon~(\texttt{float})$,$ n_{\rm iter}~(\texttt{int})$,$ \alpha~(\texttt{float})$,$ \tau~(\texttt{float})$ \\ \STATE $x \gets x_{\rm init}$ \COMMENT{Initialization} \FOR{$i=1,\dots,n_{\rm iter}$} \STATE $g \gets \displaystyle \nabla f (x)$ \IF{$\|g\|_{\infty} \leq \epsilon$} \STATE Break \ENDIF \STATE $z \gets x - \gamma g$ \IF{$f(z) \leq f(x) - \alpha \gamma \|g\|_2^2$} \STATE $x \gets z $ \STATE $\gamma \gets \gamma /\tau $ \ELSE \STATE $\gamma \gets \tau \gamma $ \ENDIF \ENDFOR \OUTPUT $x~(\texttt{numpy.ndarray})$ \end{algorithmic} \end{algorithm} </pre> Adapter et coder en `Python` l'algorithme ci-dessus pour avoir en sortie la liste de tous les itérés obtenus par la descente de gradient avec recherche linéaire, mais aussi la liste de tous les pas $\gamma_k$ utilisés. Dans la suite on utilisera $\alpha =0.5, \tau=0.5$. #### Question 4 : Algorithme de descente de gradient avec recherche linéaire La méthode du pas adaptatif permet d'adapter la taille du pas courant $\gamma_k$ de manière plus souple que la méthode précédente. Représenter sur un même graphique l'évolution de la taille des pas au cours des itérations pour les trois algorithmes introduits. <pre id="gd_adapt" class="pseudocode" style="display:hidden;"> \begin{algorithm} \caption{Descente de gradient avec recherche linéaire } \begin{algorithmic} \INPUT $\nabla f~(\texttt{function})$,$ x_{\rm init}~(\texttt{numpy.ndarray})$,$ \gamma~(\texttt{float})$,$ \epsilon~(\texttt{float})$,$ n_{\rm iter}~(\texttt{int})$ \\ \COMMENT{Initialization} \STATE $\gamma_0 \gets \gamma$ \STATE $x_0 \gets x_{\rm init}$ \STATE $x_1 \gets x_{0} - \gamma_0 \nabla f(x_0)$ \STATE $\theta_0 \gets +\infty$ \FOR{$i=1,\dots,n_{\rm iter}$} \STATE $\gamma_k \gets \min \left(\sqrt{1+\theta_{k-1}} \gamma_{k-1},\frac{1}{2} \frac{\|x_k - x_{k-1}\|}{\| \nabla f (x_k) - \nabla f (x_{k-1})\|} \right)$ \STATE $g \gets \displaystyle \nabla f (x_k)$ \IF{$\|g\|_{\infty} \leq \epsilon$} \STATE Break \ENDIF \STATE $x_{k+1} \gets x_k - \gamma_k g$ \STATE $\theta_k \gets \frac{\gamma_k}{\gamma_{k-1}} $ \ENDFOR \OUTPUT $x_k ~(\texttt{numpy.ndarray})$ \end{algorithmic} \end{algorithm} </pre> La méthode du pas adaptatif permet d'adapter la taille du pas courant $\gamma_k$ de manière plus souple. Représenter sur un même graphique l'évolution de la taille des pas au cours des itérations, et ce pour les trois algorithmes introduits. #### Question 5 : comparaison des convergences en fonction des itérés Le minimum global de la fonction de Rosenbrock $f_{ros}$ est atteint en $x^\star = (1,1)$, c'est-à-dire: $$ x^\star \in \displaystyle\operatorname*{argmin}_{x\in\mathbb{R}^2}f_{ros}(x) \enspace. $$ ::: {.callout-note} Pour une fonction $g$, la notation $x^* \in \displaystyle\operatorname*{argmin}_{x}g(x)$ signifie que $x^*$ est un point qui atteint la valeur $\displaystyle\min_{x}g(x)$, ainsi: $g(x^*)=\displaystyle\min_{x}g(x)$. ::: Comparer la convergence de ces trois méthodes de la manière suivante : - Représenter sur les lignes de niveau de la fonction de Rosenbrock l'image des itérés courants. On pourra tenter de reproduire la @fig-gd pour les choix de pas (initiaux) et de vecteur $x_{\rm init}$ similaires. - Représenter sur un premier graphique la norme du gradient en l'itéré courant en fonction de l'indice de l'itération pour chacune des trois méthodes. - Tracer sur un second graphique la distance (euclidienne) de l'itéré courant $x_k$ à $x^\star$. - Quelle méthode vous semble être la plus/moins avantageuse (justifier très brièvement à partir de vos graphiques)? La réponse sera écrite dans un bref commentaire de quelques lignes dans votre fichier `py`. Pour améliorer la lisibilité du graphique, nous rappelons que l'usage d'une échelle logarithmique sur la mesure observée peut être utile.