Méthodes d’apprentissage statistique pour l’optimisation globale.

Résumé Cette thèse se consacre à une analyse rigoureuse des algorithmes d'optimisation globale équentielle. On se place dans un modèle de bandits stochastiques où un agent vise à déterminer l'entrée d'un système optimisant un critère. Cette fonction cible n'est pas connue et l'agent effectue séquentiellement des requêtes pour évaluer sa valeur aux entrées qu'il choisit. Cette fonction peut ne pas être convexe et contenir un grand nombre d'optima locaux. Nous abordons le cas difficile où les évaluations sont coûteuses, ce qui exige de concevoir une sélection rigoureuse des requêtes. Nous considérons deux objectifs, d'une part l'optimisation de la somme des valeurs reçues à chaque itération, d'autre part l'optimisation de la meilleure valeur trouvée jusqu'à présent. Cette thèse s'inscrit dans le cadre de l'optimisation bayésienne lorsque la fonction est une réalisation d'un processus stochastique connu, et introduit également une nouvelle approche d'optimisation par ordonnancement où l'on effectue seulement des comparaisons des valeurs de la fonction. Nous proposons des algorithmes nouveaux et apportons des concepts théoriques pour obtenir des garanties de performance. Nous donnons une stratégie d'optimisation qui s'adapte à des observations reçues par batch et non individuellement. Une étude générique des supremums locaux de processus stochastiques nous permet d'analyser l'optimisation bayésienne sur des espaces de recherche nonparamétriques. Nous montrons également que notre approche s'étend à des processus naturels non gaussiens. Nous établissons des liens entre l'apprentissage actif et l'apprentissage statistique d'ordonnancements et déduisons un algorithme d'optimisation de fonctions potentiellement discontinue.