Sequential learning and stochastic optimization of convex functions

Apprentissage séquentiel et optimisation stochastique de fonctions convexes

Xavier Fontaine (1)

1 CB - CB - Centre Borelli - UMR 9010

In this thesis we study several machine learning problems that are all linked with the minimization of a noisy function, which will often be convex.Inspired by real-life applications we focus on sequential learning problems which consist in treating the data ``on the fly'', or in an online manner.The first part of this thesis is thus devoted to the study of three different sequential learning problems which all face the classical ``exploration vs. exploitation'' trade-off.Each of these problems consists in a situation where a decision maker has to take actions in order to maximize a reward or to evaluate a parameter under uncertainty, meaning that the rewards or the feedback of the possible actions are unknown and noisy.We demonstrate that all of these problems can be studied under the scope of stochastic convex optimization, and we propose and analyze algorithms to solve them.In the second part of this thesis we focus on the analysis of the Stochastic Gradient Descent algorithm, which is likely one of the most used stochastic optimization algorithms in machine learning.We provide an exhaustive analysis in the convex setting and in some non-convex situations by studying the associated continuous-time model, and obtain new optimal convergence results.

Dans cette thèse nous étudions plusieurs problèmes d'apprentissage automatique qui sont tous liés à la minimisation d'une fonction bruitée, qui sera souvent convexe.Du fait de leurs nombreuses applications nous nous concentrons sur des problèmes d'apprentissage séquentiel, qui consistent à traiter des données ``à la volée'', ou en ligne.La première partie de cette thèse est ainsi consacrée à l'étude de trois différents problèmes d'apprentissage séquentiel dans lesquels nous rencontrons le compromis classique ``exploration vs. exploitation''.Dans chacun de ces problèmes un agent doit prendre des décisions pour maximiser une récompense ou pour évaluer un paramètre dans un environnement incertain, dans le sens où les récompenses ou les résultats des différentes actions sont inconnus et bruités.Nous étudions tous ces problèmes à l'aide de techniques d'optimisation stochastique convexe, et nous proposons et analysons des algorithmes pour les résoudre.Dans la deuxième partie de cette thèse nous nous concentrons sur l'analyse de l'algorithme de descente de gradient stochastique qui est vraisemblablement l'un des algorithmes d'optimisation stochastique les plus utilisés en apprentissage automatique.Nous en présentons une analyse complète dans le cas convexe ainsi que dans certaines situations non convexes en étudiant le modèle continu qui lui est associé, et obtenons de nouveaux résultats de convergence optimaux.

Mots clés: Sequential learning; Stochastic optimization; Convex optimization

Mots clés: Apprentissage séquentiel; Optimisation stochastique; Optimisation convexe

Domaines: Mathématiques générales [math.GM]

Xavier Fontaine. Sequential learning and stochastic optimization of convex functions. General Mathematics [math.GM]. Université Paris-Saclay, 2020. English. ⟨NNT : 2020UPASM024⟩. ⟨tel-03153285⟩