Large scale stochastic optimization

In this thesis we study iterative algorithms in order to solve constrained and unconstrained convex optimization problems, variational inequalities with monotone operators and saddle point problems. We study these problems when the dimension of the search space is high and when the values of the functions of interest are unknown and we just can deal with a stochastic oracle. The algorithms we study are stochastic adaptation of two algorithms : the first one is a variant of the mirror descent algorithm proposed by Nemirovski and Yudin and the second one a variant of the dual extrapolation algorithm by Nesterov. For both of them, we provide bounds for the expected value and bounds for moderate deviations of the approximation error with different regularity hypothesis for all the unconstrained problems we study and we propose adaptative versions of the algorithms in order to get rid of the knowledge of some parameters depending on the problem studied and unavailable in practice. At last we show how to solve constrained stochastic optimization problems thanks to an auxiliary algorithm inspired by the Newton descent one and thanks to the results we obtained for the saddle point problems.L'objet de cette thèse est l'étude d'algorithmes itératifs permettant de résoudre des problèmes d'optimisation convexe avec ou sans contraintes fonctionnelles, des problèmes de résolutions d'inégalités variationnelles à opérateur monotone et des problèmes de recherche de point selle. Ces problèmes sont envisagés lorsque la dimension de l'espace de recherche est grande et lorsque les valeurs des différentes fonctions étudiées et leur sous/sur-gradients ne sont pas connues exactement et ne sont accessibles qu'au travers d'un oracle stochastique. Les algorithmes que nous étudions sont des adaptations au cas stochastique de deux algorithmes : le premier inspiré de la méthode de descente en miroir de Nemirovski et Yudin et le second, de l'algorithme d'extrapolation duale de Nesterov. Pour chacun de ces deux algorithmes, nous donnons des bornes pour l'espérance et pour les déviations modérées de l'erreur d'approximation sous différentes hypothèses de régularité pour tous les problèmes sans contraintes fonctionnelles envisagées et nous donnons des versions adaptatives de ces algorithmes qui permettent de s'affranchir de connaître certains paramètres de ces problèmes non accessibles en pratique. Enfin nous montrons comment, à l'aide d'un algorithme auxiliaire inspiré de la méthode de Newton et des résultats obtenus lors de la résolution des problèmes de recherche de point selle, il est possible de résoudre des problèmes d'optimisation sous contraintes fonctionnelles