On the dynamics of descent algorithms in high-dimensional planted models
Institution:
université Paris-SaclayDisciplines:
Directors:
Abstract EN:
Optimization of high-dimensional non-convex models has always been a difficult and fascinating problem. Since our minds tend to apply notions that we experienced and naturally learned in low-dimension, our intuition is often led astray.Those problems appear naturally and become more and more relevant, in particular in an era where an increasingly large amount of data is available. Most of the information that we receive is useless and identifying what is relevant is an intricate problem.Machine learning problems and inference problems often fall in these settings.In both cases we have a cost function that depends on a large number of parameters that should be optimized. A rather simple, but common, choice is the use of local algorithms based on the gradient, that descend in the cost function trying to identify good solutions.If the cost function is convex, then under mild conditions on the descent rate, we are guaranteed to find the good solution. However often we do not have convex costs. To understand what happens in the dynamics of these non-convex high-dimensional problems is the main goal of this project.In the thesis we will space from Bayesian inference to machine learning in the attempt of building a theory that describes how the algorithmic dynamics evolve and when it is doomed to fail. Prototypical models of machine learning and inference problems are intimately related. Another interesting connection that is known since long time, is the link between inference problems and disordered systems studied by statistical physicists. The techniques and the results developed in the latter form the true skeleton of this work.In this dissertation we characterize the algorithmic limits of gradient descent and Langevin dynamics. We analyze the structure of the landscape and find the counter-intuitive result that in general an exponential number of spurious solutions do not prevent vanilla gradient descent initialized randomly to find the only good solution. Finally, we build a theory that explains quantitatively and qualitatively the underlying phenomenon.
Abstract FR:
L'optimisation des modèles non convexes en haute dimension a toujours été un problème difficile et fascinant. Puisque nos avons la tendance à appliquer des notions que nous avons expérimentées et naturellement apprises en basse dimension, notre intuition est souvent égarée.Ces problèmes apparaissent naturellement et deviennent de plus en plus pertinents, en particulier dans une époque où une quantité de plus en plus importante de données est disponible. La plupart des informations que nous recevons sont inutiles et l'identification de ce qui est pertinent est un problème complexe.Souvent les problèmes d'apprentissage automatique et les problèmes d'inférence entre dans cette catégorie.Dans les deux cas, nous avons une fonction de coût qui dépend d'un grand nombre de paramètres à optimiser. Un choix assez simple, mais courant, est l'utilisation d'algorithmes locaux basés sur le gradient, qui descendent dans la fonction de coût en essayant d'identifier les bonnes solutions.Si la fonction de coût est convexe alors il suffit de vérifier des simple conditions sur la vitesse de descente pour trouver la bonne solution. Cependant, souvent, nous n'avons pas de coûts convexes. Comprendre ce qui se passe dans la dynamique de ces problèmes non convexe en haute dimension est l'objectif principal de ce projet.Dans la thèse, on considéra les problèmes d'inférence bayésienne et d'apprentissage automatique en essayant de construire une théorie qui décrit comment la dynamique algorithmique évolue et quand elle est vouée à l’échec. Les modèles des problèmes d'apprentissage automatique et d'inférence sont intimement liés. Un autre lien intéressant et connu depuis longtemps est le lien entre les problèmes d'inférence et les systèmes désordonnés étudiés par les physiciens statistiques. Les techniques et les résultats développés dans ce dernier forment le véritable base de ce travail.Dans cette thèse, nous caractérisons les limites algorithmiques de la descente de gradient et la dynamique de Langevin. Nous analysons la structure du paysage et trouvons le résultat contre-intuitif qu'en général un nombre exponentiel de solutions fausses n’empêche pas la descente de gradient vanille initialisée au hasard vers la seule bonne solution. Enfin, nous construisons une théorie qui explique quantitativement et qualitativement le phénomène.