Paysage et complexité pour des classes de problèmes d’optimisation non convexe

L’optimisation non convexe joue un rôle fondamental en mathématiques appliquées modernes, intervenant dans l’apprentissage automatique, le traitement du signal, la théorie du contrôle et l’algèbre linéaire numérique. Bien que les problèmes non convexes soient souvent complexes en raison de paysages comportant de multiples minima locaux et points-selles, des travaux récents ont montré que certains d'entre eux bénéficiant d'une structure spécifique—en particulier ceux possédant certaines caractéristiques algébriques ou géométriques—admettent des solutions efficaces.Cette thèse aborde l'optimisation non convexe sous deux angles complémentaires. Premièrement, nous analysons des problèmes d’optimisation matricielle, motivés par leurs liens avec la théorie de l’apprentissage profond—notamment l’entraînement des réseaux linéaires—et avec l’algèbre linéaire numérique—notamment l’approximation de fonctions matricielles. Plus précisément, nous nous concentrons sur l’approximation de la racine carrée et, par une analyse du paysage d’optimisation, nous caractérisons des classes de points critiques, identifions certaines conditions garantissant que tous les minima locaux sont globaux, et étudions des phénomènes tels que l'apparition de points-selles d’ordre supérieur. Dans un second temps, nous abordons des problèmes non convexes plus généraux, en nous concentrant sur les problèmes de type moindres carrés non linéaires. Nous y analysons différents algorithmes, incluant des méthodes de type Newton, pour lesquels nous établissons des garanties de complexité en termes de nombre d'itérations et d'opérations pour obtenir des points critiques au premier et second ordre.