Pièges du non convexe et redémarrages

Quand il y a plus d'une vallée

La plupart des modèles intéressants ne sont pas convexes. Leurs objectifs ont plusieurs minima locaux, points selle et plateaux, et la descente de gradient roule simplement dans la vallée où elle commence. Prenons $f(x)=x^4-3x^2+x$. Sa dérivée $4x^3-6x+1$ s'annule en $x=-1.301$, $x=0.170$ et $x=1.131$. Le premier et le dernier sont des minima, avec $f=-3.514$ et $f=-1.070$, et celui du milieu est une bosse entre eux. La descente à petit pas depuis $x_0=2$ finit en $1.131$, simple minimum local, et depuis $x_0=-2$ elle finit en $-1.301$, le global. Deux départs aussi proches que $x_0=0.1$ et $x_0=0.2$, de part et d'autre de la bosse en $0.170$, finissent dans des vallées différentes.

Les points selle sont l'autre piège. Le gradient y est nul mais la hessienne a des valeurs propres des deux signes : la fonction descend dans certaines directions et monte dans d'autres. En grande dimension la plupart des points stationnaires sont des cols, et la descente de gradient simple y ralentit fortement. Le momentum, le bruit des mini-lots et l'information d'ordre deux aident à s'en échapper. Les plateaux, où le gradient est minuscule sur une vaste région, ressemblent à une convergence sans en être une.

Le remède classique est de redémarrer. Lancez l'optimiseur depuis $K$ points de départ différents et gardez le résultat de plus basse valeur d'objectif. Si chaque départ tombe indépendamment dans la vallée globale avec la probabilité $p$, alors au moins l'un des $K$ départs y tombe avec la probabilité $1-(1-p)^K$. Pour $p=0.2$ et $K=10$ cela donne $0.893$, et atteindre $99\%$ demande $K\ge\ln0.01/\ln0.8=20.6$, donc 21 départs. De meilleurs points de départ aident aussi : une solution d'une relaxation convexe, la calibration de la veille ou une recherche sur grille des quelques paramètres qui comptent le plus.

• Minima locaux : la descente finit dans la vallée de départ, donc le départ décide de la réponse.
• Cols et plateaux : gradient nul ou minuscule sans minimum ; momentum et bruit aident.
• Redémarrages : $K$ départs réussissent avec la probabilité $1-(1-p)^K$ ; gardez la meilleure valeur d'objectif.

Lab : ce qui est noté

• La valeur du minimum global15 pts
• Partir de x = 215 pts
• Deux départs proches15 pts
• Succès de redémarrages aléatoires15 pts
• Combien de redémarrages15 pts
• Près d'un point selle10 pts
• Comparer les résultats des redémarrages15 pts