Résumé Technique : BAXUS – Optimisation Bayésienne Adaptative dans des Sous-Espaces Emboîtés

Énoncé du Problème

L'optimisation bayésienne de haute dimension (HDBO) vise à optimiser des fonctions boîte noire coûteuses à évaluer, comportant de quelques dizaines à plusieurs centaines de dimensions d'entrée. Bien que des avancées récentes aient étendu la portée de l'optimisation bayésienne (BO) à des domaines tels que les sciences de la vie, la recherche d'architectures neuronales et la robotique, les méthodes de l'état de l'art rencontrent des limitations significatives à mesure que la dimensionnalité augmente.

Les approches existantes se divisent généralement en deux catégories, toutes deux présentant des inconvénients critiques :

1. Méthodes de Région de Confiance (ex. TURBO) : Elles optimisent sur des régions bornées locales (régions de confiance) au sein de l'espace d'entrée complet. Bien qu'efficaces pour des dimensions modérées, leurs performances se dégradent dans des dimensions très élevées car les régions de confiance conservent la dimensionnalité complète du problème, souffrant ainsi du fléau de la dimensionnalité.
2. Méthodes d'Embedding Linéaire (ex. REMBO, HESBO, ALEBO) : Elles supposent l'existence d'un « sous-espace actif » de faible dimensionnalité et projettent l'espace d'entrée de haute dimension vers un espace cible de dimensionnalité inférieure. Cependant, ces méthodes exigent que l'utilisateur « devine » la dimensionnalité effective ($d_e$) du sous-espace actif. Si la dimensionnalité cible choisie ($d$) est trop faible, le sous-espace ne peut pas représenter l'optimum global ; si $d$ est trop élevée, l'optimisation ralentit en raison du fléau de la dimensionnalité. De plus, des méthodes comme HESBO reposent sur un hachage aléatoire offrant des garanties de pire cas inférieures pour contenir un optimum par rapport à d'autres embeddings.

Le défi central consiste à développer une méthode HDBO capable de trouver de manière fiable des optima globaux sans nécessiter de connaissances préalables sur la dimensionnalité du sous-espace actif, tout en évitant la dégradation des performances associée aux espaces de recherche de haute dimension.

Méthodologie : BAXUS

Les auteurs proposent BAXUS (Optimisation bayésienne avec des sous-espaces en expansion adaptative), une approche théoriquement fondée qui ajuste dynamiquement la dimensionnalité de l'espace d'optimisation.

1. Sous-Espaces Emboîtés Adaptatifs

Au lieu de fixer la dimensionnalité cible, BAXUS opère sur une famille de sous-espaces aléatoires emboîtés. L'algorithme commence avec un espace cible de faible dimensionnalité ($d_{init}$) et augmente progressivement la dimensionnalité à mesure qu'il collecte davantage de données.

• Initialisation : BAXUS démarre avec une petite dimension cible $d_0$.
• Expansion : Au fur et à mesure que l'optimisation progresse, la dimensionnalité cible est augmentée en « divisant » les dimensions cibles existantes. Ce processus se poursuit jusqu'à ce que la dimensionnalité cible atteigne approximativement la dimensionnalité d'entrée $D$ ou que le budget d'évaluation soit épuisé.
• Conservation des Observations : Une caractéristique cruciale de BAXUS est sa capacité à conserver les observations provenant des espaces de faible dimensionnalité lors de l'expansion vers des dimensions supérieures. Lorsqu'une dimension cible est divisée, les dimensions d'entrée contributives sont réaffectées à la dimension originale et à de nouveaux intervalles. Les valeurs de fonction (observations) sont copiées vers les nouvelles dimensions, garantissant que les données collectées lors de la phase de faible dimensionnalité restent valides dans la phase de dimensionnalité supérieure.

2. L'Embedding Sparse BAXUS

BAXUS utilise un embedding linéaire sparse novateur pour mapper l'espace cible $Y \in \mathbb{R}^d$ vers l'espace d'entrée $X \in \mathbb{R}^D$.

• Structure : La matrice d'embedding $S^\top \in \{0, \pm 1\}^{d \times D}$ est sparse, ce qui signifie que chaque colonne (dimension d'entrée) possède exactement une entrée non nulle.
• Équilibrage des Intervalles : Contrairement à HESBO, qui attribue les dimensions d'entrée aux dimensions cibles de manière uniformément aléatoire (entraînant des tailles d'intervalles variables), BAXUS impose que le nombre de dimensions d'entrée contributives par dimension cible (taille de l'intervalle) diffère d'au plus un. Cette attribution « équilibrée » est obtenue en permutant les dimensions d'entrée et en les divisant en $d$ intervalles.
• Avantage Théorique : Les auteurs démontrent que cet embedding sparse équilibré fournit une probabilité de succès de pire cas strictement supérieure (la probabilité que l'espace cible contienne un optimum global) à celle de l'embedding HESBO pour des dimensions d'entrée finies. Lorsque $D \to \infty$, la probabilité de succès de BAXUS converge vers celle de HESBO.

3. Stratégie de Région de Confiance et de Division

BAXUS intègre l'expansion de l'embedding avec une approche de Région de Confiance (TR) similaire à TURBO :

• Régions de Confiance : L'optimisation se déroule au sein de régions de confiance hyperrectangulaires dans l'espace cible, mises à l'échelle par les échelles de longueur du GP.
• Déclencheur d'Expansion : La dimensionnalité cible est augmentée lorsque la longueur du côté de base de la région de confiance tombe en dessous d'un seuil minimum (indiquant que la région actuelle est trop petite ou que l'algorithme est bloqué).
• Contrôle des Échecs : Le nombre d'« échecs » autorisés (itérations consécutives sans amélioration) avant qu'une division ne se produise est réduit en fonction de la dimensionnalité cible actuelle. Cela garantit que l'algorithme peut atteindre des dimensions élevées dans le cadre d'un budget d'évaluation fixe.
• Convergence : Il est démontré que l'algorithme atteint une convergence globale. Une fois que la dimensionnalité cible atteint la dimensionnalité d'entrée $D$, BAXUS se comporte comme TURBO, qui est connu pour converger globalement.

Contributions Clés

1. Développement d'Algorithme : Les auteurs introduisent BAXUS, qui atteint de manière fiable d'excellentes solutions sur un large éventail de tâches de haute dimension, surpassant les méthodes actuelles de l'état de l'art.
2. Nouvelle Théorie d'Embedding : Ils présentent une nouvelle famille d'embeddings aléatoires emboîtés avec trois propriétés clés :
   • Elle offre une garantie de pire cas plus large pour contenir un optimum global par rapport à l'embedding HESBO.
   • C'est un embedding sparse optimal, ce qui signifie qu'aucun autre embedding sparse n'a une probabilité de succès de pire cas plus élevée pour les mêmes dimensions d'entrée, cible et effective.
   • Sa probabilité de contenir un optimum converge vers la probabilité HESBO lorsque la dimensionnalité d'entrée $D \to \infty$.
3. Évaluation Complète : L'article fournit des preuves empiriques extensives démontrant la supériorité de BAXUS par rapport à TURBO, SAASBO, ALEBO, HESBO, CMA-ES et la recherche aléatoire sur divers benchmarks.

Résultats Expérimentaux

Les auteurs ont évalué BAXUS sur une collection de tâches d'optimisation d'hyperparamètres de 388 dimensions, de problèmes de conception de 124 dimensions, et de benchmarks avec des sous-espaces actifs connus (LASSO, MOPTA08, BRANIN, HARTMANN).

• Performance : BAXUS a constamment surpassé les méthodes de l'état de l'art. Sur le benchmark SVM 388D, BAXUS s'est adapté à la dimensionnalité cible appropriée et a trouvé de meilleures solutions plus rapidement que TURBO et CMA-ES. Sur le benchmark LASSO-HARD 1000D, BAXUS a obtenu des solutions considérablement meilleures que tous les concurrents, y compris les méthodes reposant sur des hypothèses de sous-espace actif (SAASBO, ALEBO, HESBO), qui n'ont pas pu bénéficier de la structure du sous-espace actif.
• Robustesse : BAXUS a démontré une robustesse face au bruit d'observation, maintenant des performances solides sur des variantes bruitées des benchmarks où des concurrents comme SAASBO et CMA-ES se sont dégradés de manière significative.
• Études d'Ablation : Le remplacement de l'embedding BAXUS par un embedding HESBO emboîté a entraîné une performance nettement inférieure, confirmant que la stratégie d'équilibrage des intervalles est un moteur clé du succès.
• Comparaison avec des Embeddings Fixes : BAXUS a surpassé l'exécution de TURBO avec une dimensionnalité cible fixe, montrant que la stratégie d'expansion adaptative est supérieure aux choix statiques de $d$.

Importance et Revendications

L'article revendique que BAXUS répond aux limitations critiques des méthodes HDBO actuelles en éliminant le besoin pour les praticiens de « deviner » la dimensionnalité effective du problème. En expandant adaptativement l'espace de recherche, BAXUS exploite l'efficacité de l'optimisation de faible dimensionnalité tout en garantissant que l'espace de recherche finit par couvrir l'espace d'entrée complet, assurant ainsi que l'optimum global est atteignable.

Les auteurs affirment que BAXUS est un optimiseur « prêt à l'emploi » (out-of-the-box) qui atteint des performances robustes sur une large variété de tâches de haute dimension sans nécessiter d'hypothèses spécifiques sur la structure du problème (telles que des sous-espaces actifs alignés sur les axes). Ce travail vise à rendre l'optimisation bayésienne de haute dimension plus accessible et fiable pour des applications en science et dans l'industrie où le nombre de paramètres ajustables est élevé et où leur dimensionnalité effective est inconnue.