Cadre mathématique pour l'optimisation de boîtes noires avec variables catégorielles et méta

L'optimisation de boîtes noires est une branche de l'optimisation caractérisée par une fonction objectif et des contraintes sans expression analytique. Concrètement, cela implique que les outils traditionnels de l'optimisation, dont les dérivées, ne peuvent être utilisées. La communauté de recherche a tout de même développé des méthodes algorithmiques ingénieuses pour s'attaquer à ce type de problème. À ce jour, la plupart des méthodologies développées traitent des problèmes contenant uniquement des variables continues ou entières. Les méthodologies pour traiter des problèmes ayant des variables catégorielles ou des structures mathématiques dynamiques (variables méta) sont peu nombreuses. Il ne s'agit pas d'un hasard, puisque ces problèmes délaissés contiennent des difficultés qui sont fondamentalement difficiles à sur-monter. Dans ce travail, un cadre mathématique, composé d'un système de notation et de stratégies de résolution, est présenté. Le cadre traite des problèmes d'optimisation mixte dans un contexte de boîtes noires. Le système de notation permet de modéliser explicitement les variables catégorielles et méta dans un problème mixte. Cette modélisation facilite grandement la résolution de tels problèmes. Le terme méta, introduit dans ce travail, décrit les variables spéciales qui influencent le nombre de variables (dimension) ou le nombre de contraintes. Les variables méta ont un impact important sur les définitions mathématiques de base, telles que le domaine et l'en-semble réalisable. Ceux-ci sont rigoureusement définis, ce qui permet d'exprimer plusieurs difficultés liées aux variables catégorielles et méta. Les différentes méthodologies et approches de la littérature sont catégorisées en deux type de stratégies : la résolution de sous-problèmes et la résolution d'un problème auxiliaire. Les deux stratégies incorporent les différentes méthodologies et approches de la littérature, dont la recherche directe et l'optimisation bayésienne. Le cadre mathématique est donc compatible avec la littérature. Le cadre mathématique est illustré sur un problème d'optimisation des hyperparamètres, qui est un problème d'optimisation de boîtes noires avec des méta-variables et variables catégorielles. Ce problème est une motivation importante de ce travail. En pratique, il peut être difficile de déterminer efficacement de bons hyperparamètres, puisque l'espace de recherche est mixte et potentiellement très vaste. Ainsi, déterminer de bons hyperparamètres peut être très coûteux temporellement et énergétiquement. Dans ce travail, les fondements mathématiques et des stratégies de résolution sont développés de sorte qu'ils puissent être appliqués à ce type de problème.

Abstract

In blackbox optimization, the objective function and the constraints have no analytical expression, which prevents the deployment of any method based on derivatives. This limitation did not avert any progress by researchers and practitioners. Indeed, the literature in blackbox optimization has been flourishing in the recent years. However, mixed problems with categorical variables and an unfixed mathematical structure (meta variables) have been dismissed by the community, primarily because of the intrinsically difficulties of such problems. In this work, a mathematical framework for modelling constrained mixed-variable optimization problems is presented in a blackbox optimization context. The mathematical framework is composed of a new notation system and solution strategies. The notation system allows meta and categorical variables to be explicitly and efficiently modelled, which facilitates the optimization of such problems. The new term meta variables is used to describe special variables that affect the number of variables (dimension) or the number of constraints. Moreover, the domain of the objective function and the feasible set are rigorously defined, which highlight many subtleties associated to meta variables. The flexibility of the solution strategies supports the main blackbox mixed-variable optimization approaches: direct search methods and surrogate-based methods (Bayesian optimization). The notation system and solution strategies are illustrated through an example of a hyper-parameter optimization problem from the machine learning community. This optimization problem is an important motivation behind this work. The interest in deep learning has been growing exponentially in various fields and applications. However, the performance of deep models may be sensible to the choice of hyperparameters, which may limit the performance of such models or drastically increase the time and energy costs of finding good hyperparameters. This work takes this hyperparameter optimization seriously by providing the mathematical foundation to model the underlying difficulties related to categorical and meta variables, as well as furnished state-of-the-art strategies to tackle the problem.