Vanessa Piccolo

L'une des questions les plus fondamentales en apprentissage statistique est de comprendre pourquoi les algorithmes optimisent si efficacement des fonctions non convexes et en grande dimension. Ces fonctions peuvent être vues comme des paysages complexes avec un nombre exponentiel de minima locaux, susceptibles d’attirer et de piéger la dynamique d’optimisation. Une approche pour mieux comprendre cela est d'analyser la complexité du paysage d’optimisation, c’est-à-dire étudier le nombre asymptotique de ses points critiques. Dans ce contexte, nous étudions la complexité des polynômes aléatoires gaussiens perturbés par un signal de rang fini, qui est caractérisé par des polynômes déterministes qui dépendent de certains vecteurs unitaires fixes et de paramètres externes. Nous dérivons des formules variationnelles pour les taux de croissance exponentielle du nombre moyen de points critiques et de maxima locaux. Ces résultats s’appuient sur la formule de Kac-Rice, qui relie le nombre attendu de points critiques à des moyennes conditionnelles de déterminants de grandes matrices aléatoires. De plus, nos résultats révèlent une transition de phase dans la complexité du paysage, identifiant un seuil critique des paramètres externes au-delà duquel de nouvelles régions du paysage avec un nombre sous-exponentiel de points critiques émergent.