Quelques problèmes en optimisation non convexe et stochastique

Le sujet de cette thèse est l'analyse de divers algorithmes stochastiques visant à résoudre un problème d'optimisation non convexe. Nous commençons par un problème d'optimisation lisse en analysant une famille d'algorithmes adaptatifs avec moments qui comprend entre autres ADAM et la descente de gradient accélérée de Nesterov. La convergence et la fluctuation des itérés sont établies. Un résultat général d'évitement des pièges pour les algorithmes stochastiques sous-tendus par une équation différentielle non autonome est présenté. Il est appliqué pour établir la non-convergence des itérés aux points-selles. La suite du manuscrit est consacrée au cas où la fonction que l'on cherche à minimiser est non lisse. La plupart de nos résultats dans cette partie s'appliquent aux fonctions définissables dans une structure o-minimale. Tout d'abord, nous analysons la version à pas constants de la descente de sous-gradient stochastique (SGD) et montrons que ses itérés convergent en grande probabilité vers l'ensemble des points critiques. Deuxièmement, nous montrons que chaque point critique d'une fonction Lipschitz, définissable, générique se trouve sur une variété active, satisfaisant une condition de Verdier et d'angle et est soit un minimum local, un point selle actif ou un point critique fortement répulsif. Nous montrons, sous des conditions légères sur les perturbations, que le SGD évite les deux derniers types de points. Une amélioration de la formule de projection pour les fonctions définissables, donnant une condition de type Lipschitz sur ses sous-gradients de Clarke, est présentée. Enfin, nous établissons un phénomène d'oscillation des itérés du SGD et de ses extensions proximalesThe subject of this thesis is the analysis of several stochastic algorithms in a nonconvex setting. The aim is to prove and characterize their convergence. First, we study a smooth optimization problem, analyzing a family of adaptive algorithms with momentum which includes the widely used ADAM and Nesterov's accelerated gradient descent. Convergence and fluctuation of the iterates are established. A general avoidance of traps result for stochastic algorithms underlined by a nonautonomous differential equation is presented and applied to establish the nonconvergence of the iterates to saddle points.The rest of the manuscript is devoted to the case where the function that we seek to minimize is nonsmooth. Most of our results in this part apply to functions definable in an o-minimal structure. Firstly, we analyze the constant step version of the stochastic subgradient descent (SGD) and show that the iterates converge with high probability to the set of critical points. Secondly, we show that every critical point of a generic, definable, locally Lipschitz continuous function is lying on an active manifold, satisfying a Verdier and an angle condition and is either a local minimum, an active strict saddle or a sharply repulsive critical point. We show that, under mild conditions on the perturbation sequence, the SGD escapes active strict saddles and sharply repulsive critical points. An improvement of the projection formula for definable functions, giving a Lipschitz-like condition on its Clarke subgradients is presented and is of independent interest. Finally, we establish an oscillation phenomena of the iterates of the SGD and its proximal extension