Adaptive methods for optimization in stochastic environments

Imaginons que nous ayons accès à un simulateur qui modélise le comportement d’une tâche numérique complexe. Considéré comme une boîte noire, nous ne pouvons obtenir des informations utiles qu’en exécutant le simulateur avec différentes entrées. Par exemple, le processus d’inférence de la structure 3D d’une protéine à partir de sa séquence d’acides aminés peut être considéré comme une tâche complexe, qui peut être modélisée par un simulateur. Les entrées du simulateur sont les séquences d’acides aminés et les sorties sont les structures 3D prédites. Une famille populaire de méthodes cherche à optimiser une fonction énergétique appropriée - produite par le simulateur - qui décrit la relation entre la structure d’une protéine et sa séquence d’acides aminés. Ces méthodes sont intéressantes car elles sont capables de construire des structures de protéines sans connaissance préalable des structures résolues.Dans cette thèse, nous modélisons des scénarios précédents comme un problème d’optimisation séquentielle dans des environnements stochastiques. A chaque instant, nous pouvons interroger un point de l’environnement, et recevoir une récompense bruitée. Nous nous concentrons d’abord sur le cas où l’environnement est représenté par un nombre fini de points, et ensuite sur le cas plus général où l’environnement est composé d’un nombre infini dénombrable de points, voire continu. Dans les deux cas, le coût d’une requête pouvant être élevée, nous envisageons ainsi à repérer au plus vite le point (quasi)-optimal. Cette étude est motivée par de nombreux scénarios réels comme, entre autres, les essais cliniques, les tests A/B, ou l’optimisation des placements publicitaires. Ainsi pour terminer, nous nous intéressons en particulier à l’une de ces applications plus importantes pour la communauté d’apprentissage statistique, c’est-à-dire l’optimisation des hyper-paramètres.Imagine that we have access to a simulator that models the behaviour of some complex numerical task. Being considered as a black box, we can only get useful information by running the simulator with different inputs. For example, the process of inferring the 3D structure of a protein from its amino-acid sequence can be regarded as such a complex task, that can be modelled by a simulator. The inputs of the simulator are the amino-acid sequences and the outputs are the predicted 3D structures. A popular family of methods seek to optimize a suitable energy function – produced by the simulator – that describes the relation between the structure of a protein and its amino-acid sequence. These meth- ods are of interest because they are able to build protein structures without prior knowl- edge on solved structures.In this thesis, we model the previous scenarios as a sequential optimization problem under stochastic environments. At each round, we can query a data point from the environment, and receive a noisy reward. We first focus on the case where the environment is abstracted as a finite search space, then we investigate also on a more general setting where the environment is composed of an infinite number of points or even continuous. In both cases, the cost of a single query would be high, and we thus aim at identify the (near)-optimum as efficiently as possible. The whole study is motivated by numerous real scenarios including, but not limited to, clinical trial, A/B testing, advertisement placement optimization. We therefore conclude by some particular focus on one of its most important contributions for the machine learning community, i.e. hyper-parameter optimization