Contrôle terminal TP HAX606X

\DeclareMathOperator*{\argmin}{argmin} \DeclareMathOperator*{\argmax}{argmax}

Important

Pour ce travail vous devez déposer un unique fichier au format .py ou .ipynb, structuré avec des cellules, dont le nom est tp_final_HAX606X_Prenom_Nom.py (ou tp_final_HAX606X_Prenom_Nom.ipynb). 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.

Soumettez une version préapytorlable par sécurité sur Moodle (que vous modifierez par la suite).

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

• qualité des réponses aux questions : 18 pts,
• qualité du code (noms de variables clairs, commentaires, code synthétique, etc.) : 1 pt
• reproducibilité (exécution correcte) et absence de bug : 1 pt

Objectifs

Dans le premier exercice, nous allons étudier l’impact des hyperparamètres dans la descente de gradient, notamment sur les stratégies pour choisir les tailles de pas. Dans le second, le but est d’étudier les problèmes minimax avec la montée et descente de gradients et une application au jeu pierre-feuille-ciseaux.

Exercice 1

Nous allons étudier la fonction de Rastrigin f_{Ras} définie par:

f_{Ras}(x,y)= 2A + x^2 - A \cos(2\pi x) + y^2 - A \cos(2\pi y) \enspace.

Où A\in\mathbb{R} est un scalaire qui impactera la difficulté de trouver le minimum global.

• 1. Tracer les lignes de niveaux de cette function et sa réprésention en 3D l’un à côté de l’autre en prenant avec (x,y)\in [-5.12,5.12]^2. On choisira A=1 pour le moment.
• 2. Cette fonction est-elle convexe ?
• 3. Calculer le gradient de la fonction f_{Ras} et l’implémenter avec A en paramètre libre.

Avec scipy

• 4. Minimiser la fonction de Rastrigin en utilisant le module scipy avec 2 points initiaux différents choisis dans [-5.12, 5.12]^2, l’un devra être (-1, 1) et pour deux méthodes d’optimisation différentes (4 résultats au total).
• 5. Commenter les sorties obtenues en expliquant comment interpréter chaque élément renvoyé par scipy.

Avec pytorch

• 6. Minimiser en utilisant les optimiseurs SGD et RMSprop la fonction de Rastrigin avec un pas \gamma=0.1 et 100 itérations maximum, on initialisera au point (-1, 1). Commenter.

Descente de gradient

Voici le pseudocode pour la descente de gradient classique.

    \begin{algorithm}
    \caption{Descente de gradient à pas fixe}
    \begin{algorithmic}
    \INPUT $\nabla f, x_{init}, \gamma,$ maxiter, $\epsilon$
    \STATE $x = x_{init}$
    \COMMENT{Initialization}
    \FOR{$i=1,\dots,$maxiter}
        \STATE $g\leftarrow \nabla f(x)$
        \COMMENT{Evaluation du gradient en l'itéré courant}
    \IF{$\|g\|^2 \leq \epsilon^2$ }
        \COMMENT{Caractérisation d'un extremum}
        \STATE Break
    \ELSE
    \STATE $x \leftarrow x - \gamma g$
    \COMMENT{Pas dans la direction opposée au gradient}
    \ENDIF
    \ENDFOR
    \OUTPUT $x$
    \end{algorithmic}
    \end{algorithm}

• 7. Coder la descente de gradient en laissant la possibilité de modifier \gamma à chaque itération à partir d’une liste appelée lr_scheduler_values en entrée. Cette liste prédéfinie par la suite permettra de modifier la valeur de \gamma au cours des itérations. Retourner en sortie la suite des itérés (x_i)_i et la suite des valeurs de l’objectif (f(x_i))_i
• 8. Comment retrouver la descente de gradient à pas fixe à partir de la descente de gradient à pas variable définie avec lr_scheduler_values ?
• 9. Lancer la descente de gradient classique à pas fixe sur la fonction f_{Ras} en utilisant le code avec lr_scheduler_values.

Programmer la valeur du pas

Plusieurs stratégies (scheduler) existent pour calibrer la taille du pas (appelé learning rate par la suite). Nous proposons d’en étudier plusieurs:

• Descente de gradient avec scheduler constant: le pas reste fixe au cours du temps
• Descente de gradient avec scheduler multistep: le pas est réduit d’un facteur \alpha\in\mathbb{R}_+ constant à des étapes définies 0<t_1<t_2<\dots\in\mathbb{N} à l’avance:

\gamma_0 \in\mathbb{R},\quad\gamma_i = \begin{cases}\frac{\gamma_0}{\alpha}& \text{if}\ t_1 \leq i < t_2 \\ \frac{\gamma_0}{\alpha^2} &\text{if}\ t_2\leq i < t_3 \\ \dots \end{cases} \enspace.

• Descente de gradient avec scheduler cosine: le pas est défini à partir d’un cosinus ce qui lui permet d’explorer plus l’espace. Il nécessite de définir un \gamma_{\max}, \gamma_{\min}, et le nombre total d’itérations N.

\gamma_i = \gamma_{\min} + \frac{1}{2}(\gamma_{\max} - \gamma_{\min}) ( 1 + \cos\left[ \frac{i\pi}{N} \right]) \enspace.

• Descente de gradient avec scheduler cosine avec redémarrage: le pas est défini à partir d’un cosinus ce qui lui permet de sortir des minima locaux. En réutilisant les notations précédentes, et en notant i_{courant} l’index courant (c’est à dire depuis le dernier rédémarrage en t_1,t_2,\dots) et N_{intervalsize} le nombre d’itérations entre deux redémarrages:

\begin{cases} \gamma_i = \gamma_{\min} + \frac{1}{2}(\gamma_{\max} - \gamma_{\min}) ( 1 + \cos\left[ \frac{i_{courant}\pi}{N_{intervalsize}} \right])& \text{if}\ i_{courant} \notin \{t_1,t_2,\dots\} \\ \gamma_i = \gamma_{i-1} + \frac{1}{2}(\gamma_{\max} - \gamma_{\min}) ( 1 - cos\left[ \frac{1\pi}{N_{intervalsize}} \right]) & \text{if}\ i \in \{t_1,t_2,\dots\} \end{cases} \enspace.

• 10-11-12) Tracer les tailles de pas (pas besoin de lancer la descente de gradient) au cours des itérations pour chaque stratégie sur 500 itérations:
  • scheduler constant avec \gamma=\gamma_{\min}=0.001 puis avec \gamma=\gamma_{\max}=0.1 (à tracer en pointillés)
  • scheduler multistep en partant de \gamma_{\max} avec un facteur de décroissance \alpha=10 appliqué toutes les 100 itérations
  • scheduler cosine avec N=500 (et les valeurs données précédemment)
  • Bonus: scheduler cosine avec redémarrage toutes les 100 itérations.

• 13. Fixer l’aléatoire de numpy avec une graîne qui sera la longueur de la chaîne de caractères contenant votre prénom et votre nom attachés (sans espace)
• 14. Choisir un point initial aléatoire dans [-5.12, 5.12]^2
• 15. Lancer la descente de gradient avec chaque stratégie sur f_{Ras}. Commenter la covergence de l’objectif

• 16. Tracer les itérés sur 4 graphiques séparés (on utilisera les titres pour repérer la méthode). Commenter les résultats obtenus. Bonus: rajouter un cinquième graphique pour le cosine avec redémarrage.

• 17. Reprendre brièvement avec A=5, commenter et expliquer.

En pratique, ces stratégies sont appélées des scheduler et sont très utiles pour l’optimisation de réseaux de neurones. Vous pourrez en trouver d’autres dans la documention du module optim de pytorch.

Exercice 2

Dans cet exercice, notre but est le problème minimax d’optimisation sans contrainte présenté ci-dessous:

{\min}_{x\in\mathbb{R}^m} {\max}_{y\in\mathbb{R}^n} f(x,y).

Ces problèmes se rencontrent souvent dans la théorie des jeux, et le but est souvent de trouver un équilibre de Nash (un point d’équilibre qui maximise les gains de chaque joueur).

On suppose que f est une fonction convexe-concave et lisse (Lipschitz, continuellement différentiable, convexe en x et concave en y).

Algorithme de descente-montée alternée

L’algorithme standard pour résoudre ce type de problèmes est l’algorithme Sim-GDA (Simultaneous Gradient Descent Ascent) défini par sa mise à jour:

\begin{cases} x_{k+1} &= x_k - \gamma \nabla_x f(x_k, y_k) \\ y_{k+1} &= y_k + \gamma \nabla_y f(x_k, y_k) \end{cases}

avec \gamma>0 un pas fixé. Un deuxième algorithme Alt-GDA (Alternating gradient descent ascent) profite que les itérés soient calculés séquentiellement et utilise la règle de mise à jour suivante:

\begin{cases} x_{k+1} &= x_k - \gamma \nabla_x f(x_k, y_k) \\ y_{k+1} &= y_k + \gamma \nabla_y f(x_{k+1}, y_k) \end{cases}.

• 18. Coder ces deux méthodes, on utilisera un critère d’arrêt basé sur un nombre de pas maximal et une convergence en norme 2 pour les itérés en x et les itérés en y avec une précision \varepsilon>0. Les fonctions \nabla_x f et \nabla_y f seront placées en arguments pour tester plusieurs cadres d’application.

Etudions maintenant ces algorithmes ¹

¹ papier de 2022 sur ces méthodes

Etude sur 2 cas classiques.

Soient f_1(x,y)=xy et f_2(x,y)=0.5x^2 + 10xy - 0.5y^2 avec x,y\in\mathbb{R}.

• 19. En utilisant une grille de 4 sous-figures, tracer la trajectoire des itérés (x_k,y_k)_k avec un pas \gamma=0.01 pour Sim-GDA (première ligne des subplots) et Alt-GDA (deuxième ligne des subplots). Mettre en valeur le point initial (0.5, -0.5) sur les graphiques. Qu’observez-vous ?

Pierre, feuille, ciseaux

Appliquons ces algorithmes au jeu du pierre, feuille, ciseaux. Supposons qu’une joueuse A et une joueuse B se lancent dans une partie. On rappelle que la pierre gagne contre les ciseaux, qui gagnent contre la feuille, qui gagne elle-même contre la pierre. Aucun autre type de coup n’est accepté ! Elles comptent les points comme suit:

• En cas d’égalité, le gain est de 0,
• Si une joueuse gagne, elle a +1 point,
• Si une joueuse perd, elle a -1 point.

On peut représenter cela dans une matrice de récompense R: R = \begin{pmatrix} 0& -1& 1 \\ 1 & 0& -1 \\ -1 & 1 & 0 \end{pmatrix} qui se lit comme suit. Si les choix pierre, papier, ciseaux sont représentés par les indices 1,2,3. Si la joueuse A joue i et la joueuse B joue j, alors R_{i,j} est le gain de la joueuse A et la joueuse B obtient -R_{i,j}.

La stratégie de la joueuse A est représentée par un vecteur de probabilités p\in\Delta_3 (\Delta_3 est le simplex de dimension 3: p_1+p_2+p_3=1 et p_i\geq 0 pour i=1,2,3) et la stratégie de la joueuse B est représentée par un vecteur de probabilités q. Le gain moyen de la joueuse A est: p^\top R q = \sum_{i,j=1}^3 p_i R_{i,j} q_j.

Pour la joueuse A, le but est de maximiser ses gains et minimiser ceux de la joueuse B: {\min}_{q\in\Delta_3} {\max}_{p\in\Delta_3} p^\top R q =f(p,q)\enspace.

• 20. Calculer et coder \nabla_p f et \nabla_q f
• 21. Reprendre Sim-GDA et Alt-GDA en projetant (à la manière de la descente de gradient projeté) les itérés x_{k+1} et y_{k+1} dans \Delta_3 pour rester dans l’espace des solutions valides. Utiliser pour cela la projection \Pi: \mathbb{R}^d \rightarrow \Delta_d définie par (\Pi(p))_k = \frac{e^{p_k}}{\sum_{i=1}^d e^{p_i}} pour k=1,\dots,d.
• 22. Faire tourner les algorithmes de Sim-GDA et Alt-GDA avec des stratégies initiales où joueuse A ne fait que “Pierre” et joueuse “B” alterne entre “Feuille” et “Ciseaux” un coup sur deux.
• 23. Quelle est la meilleure stratégie obtenue ? Quel est le gain moyen pour la joueuse A ? En déduire celui de la joueuse B. Commenter.
• 24. Que ce passe-t-il si la matrice des récompenses R n’est pas antisymétrique ou si les gains et pertes ne sont plus de \pm 1 ?