Résumé Technique : Optimisation Bayésienne par Lots Évolutive via des Fonctions d'Acquisition par Sous-espaces

Énoncé du Problème

L'Optimisation Bayésienne (BO) est un cadre puissant pour résoudre des problèmes d'optimisation de boîte noire coûteux. Bien que la BO standard fonctionne de manière séquentielle, en sélectionnant un point d'échantillonnage à la fois, cette approche est inefficace lorsque des ressources de calcul parallèle sont disponibles. Pour exploiter le parallélisme, des algorithmes d'Optimisation Bayésienne par Lots (Batch Bayesian Optimization) sont nécessaires pour évaluer plusieurs échantillons simultanément.

Cependant, les approches par lots existantes font face à des problèmes d'évolutivité importants à mesure que la taille du lot ($q$) augmente :

• Amélioration Attendue Multi-points (qEI) : Bien que théoriquement solide, l'optimisation de qEI implique un espace de recherche de dimension $d \times q$ (où $d$ est la dimension du problème). À mesure que $q$ croît, le coût computationnel de l'évaluation de la fonction de répartition multivariée et la difficulté d'optimiser la fonction d'acquisition augmentent de manière exponentielle, rendant qEI et ses variantes (ex: FqEI, qLogEI) impraticables pour de grandes tailles de lots (typiquement $q > 10$).
• Approches Heuristiques (ex: Kriging Believer, Constant Liar, Local Penalization) : Ces méthodes reposent souvent sur des points "fictifs" ou des fonctions de pénalité artificielles pour simuler les effets de lot. À mesure que la taille du lot augmente, l'accumulation de ces points artificiels dégrade la précision du modèle de Processus Gaussien (GP), pouvant induire la direction de recherche en erreur et réduire l'efficacité de l'optimisation.
• Approches Multi-objectifs et Multi-modèles : Les méthodes qui entraînent plusieurs modèles de substitution ou résolvent des problèmes d'optimisation multi-objectifs engendrent souvent des coûts de calcul élevés qui ne passent pas bien à l'échelle avec de grandes tailles de lots.

Le défi central abordé dans ce travail est la conception d'une stratégie d'acquisition par lots qui reste calculablement traitable et efficace pour des évaluations par lots à grande échelle sans souffrir de la malédiction de la dimensionnalité ou de la dégradation du modèle.

Méthodologie

Les auteurs proposent une nouvelle approche appelée Fonctions d'Acquisition par Sous-espaces, qui étend les fonctions d'acquisition existantes (spécifiquement l'Amélioration Attendue, mais aussi adaptable à PI et UCB) pour opérer au sein de sous-espaces sélectionnés aléatoirement et alignés sur les axes.

Concept Central : Amélioration Attendue par Sous-espace (SSEI)

Au lieu de chercher $q$ points dans l'espace de conception complet de dimension $d$ simultanément, la méthode :

1. Sélectionne des Sous-espaces : Sélectionne aléatoirement un ensemble de sous-espaces alignés sur les axes. Un sous-espace de dimension $k$ aligné sur les axes est défini en choisissant $k$ coordonnées parmi les $d$ dimensions originales, tout en fixant les $d-k$ coordonnées restantes aux valeurs de la meilleure solution actuelle ($x_{min}$).
2. Optimise Localement : Pour chaque sous-espace sélectionné, la fonction d'acquisition standard (ex: EI) est optimisée uniquement sur les $k$ variables actives. Les variables non sélectionnées restent fixées à $x_{min}$.
3. Génère le Lot : Un point de requête est sélectionné de chaque sous-espace unique. Si la taille de lot requise $q$ dépasse le nombre de sous-espaces disponibles ($N = 2^d - 1$), la méthode emploie l'Amélioration Attendue Multi-points par Sous-espace (SSqEI), qui optimise plusieurs points au sein d'un même sous-espace.

Cadre Computationnel

L'algorithme proposé (Algorithme 1) fonctionne comme suit :

• Initialisation : Générer des échantillons initiaux et entraîner un modèle GP.
• Sélection de Sous-espaces : Tirer aléatoirement un entier $k \in [1, d]$, puis une combinaison aléatoire de $k$ coordonnées pour former un sous-espace. Cela évite le coût computationnel de l'énumération de tous les sous-espaces possibles.
• Optimisation de l'Acquisition :
  • Si $q \le N$ : Sélectionner $q$ sous-espaces distincts et optimiser la SSEI standard dans chacun pour trouver un point par sous-espace.
  • Si $q > N$ : Distribuer les $q$ points sur les $N$ sous-espaces disponibles (en optimisant plusieurs points par sous-espace via SSqEI).
• Évaluation : Évaluer le lot de $q$ points résultants en parallèle.
• Mise à jour : Mettre à jour le modèle GP avec les nouvelles observations et répéter.

La dimensionnalité du problème d'optimisation pour la fonction d'acquisition est réduite de $d \times q$ à environ $k \times 1$ (ou $k \times q_i$ pour SSqEI), où la dimension attendue $E[k] \approx d/2$. Cela réduit considérablement la complexité de l'optimisation de l'acquisition.

Contributions Clés

1. Stratégie de Lot Évolutive : Le papier introduit une méthode pour étendre l'optimisation bayésienne à de grandes tailles de lots en découplant la sélection du lot en optimisations de sous-espaces indépendantes ou de faible dimension, évitant ainsi la complexité exponentielle de qEI.
2. Simplicité et Généralité : L'approche ne nécessite aucun hyperparamètre supplémentaire et est applicable à un large éventail de fonctions d'acquisition (démontré pour EI, PI et UCB). Elle est conceptuellement simple : "tirer des sous-espaces, optimiser localement, agréger".
3. Robustesse à la Dimensionnalité : En restreignant la recherche aux sous-espaces alignés sur les axes ancrés à la meilleure solution actuelle, la méthode équilibre naturellement l'exploration (via la sélection aléatoire de sous-espaces) et l'exploitation (via la recherche locale autour de $x_{min}$), ce qui la rend particulièrement efficace dans les espaces de grande dimension.

Résultats Expérimentaux

Les auteurs ont évalué la méthode proposée (SSEI) contre dix algorithmes de pointe par lots (incluant qEI, qLogEI, FqEI, TuRBO, MSMR, MACE, PEI, EIMI, KB et Random Search) sur 60 problèmes de référence synthétiques (GPMean, SumSquares, Rosenbrock, etc.) à travers des dimensions $d \in \{2, 4, 8, 10, 20, 30\}$ et des tailles de lots $q \in \{1, 2, 4, 8, 16, 32, 64, 128\}$.

• Performance vs BO Séquentielle : Lorsque $q=1$, la SSEI performe de manière similaire à l'EI standard sur les problèmes de faible dimension, mais surpasse significativement celle-ci sur les problèmes de haute dimension ($d \ge 8$). Les auteurs attribuent cela au fait que l'EI séquentielle peine à optimiser la fonction d'acquisition en haute dimension, tandis que la recherche locale par sous-espace de la SSEI trouve de meilleurs optima locaux pour la fonction d'acquisition.
• Évolutivité avec la Taille du Lot :
  • Petits à Moyens Lots ($q \le 32$) : La SSEI atteint une accélération quasi linéaire en termes de temps de calcul (itérations) tout en maintenant une performance comparable ou supérieure aux autres méthodes par lots lorsqu'elle est mesurée en évaluations de fonctions.
  • Grands Lots ($q = 128$) : La SSEI surpasse nettement tous les algorithmes par lots comparés, y compris les variantes de qEI qui échouent ou se dégradent considérablement à cette échelle. La méthode proposée converge plus rapidement et trouve de meilleures solutions finales.
• Comparaison avec des Algorithmes Spécifiques :
  • vs qEI/qLogEI/FqEI : La SSEI est supérieure, surtout à mesure que $d$ et $q$ augmentent, car elle évite la malédiction de la dimensionnalité $d \times q$.
  • vs TuRBO : La SSEI est compétitive, surpassant souvent TuRBO sur les dimensions faibles à moyennes et l'égalisant sur les hautes dimensions.
  • vs Méthodes basées sur la Pénalité (PEI, EIMI, KB) : La SSEI surpasse systématiquement ces méthodes, qui souffrent d'une dégradation du modèle à mesure que la taille du lot croît.
• Généralisabilité : L'approche par sous-espace a été appliquée avec succès à la Probabilité d'Amélioration (SSPI) et à la Borne de Confiance Supérieure (SSUCB), montrant des gains de performance similaires par rapport à leurs homologues multi-points (qPI, qUCB).

Signification et Revendications

Le papier affirme que les Fonctions d'Acquisition par Sous-espaces proposées offrent une solution simple, efficace et évolutive pour l'optimisation bayésienne par lots. La principale importance réside dans la capacité d'utiliser des ressources de calcul parallèle à grande échelle (grand $q$) sans les goulots d'étranglement computationnels ou la dégradation de précision associés aux méthodes existantes.

Les auteurs soulignent que :

• La méthode atténue efficacement la malédiction de la dimensionnalité dans l'optimisation de la fonction d'acquisition.
• Elle offre un compromis pratique entre l'exploration globale (via la sélection aléatoire de sous-espaces) et l'exploitation locale (via la fixation des variables non sélectionnées).
• C'est une extension "plug-and-play" qui peut être appliquée à diverses fonctions d'acquisition et qui est particulièrement précieuse pour les problèmes d'optimisation coûteux où l'évaluation parallèle est réalisable.

Le travail conclut que la sélection de points de requête à partir de multiples sous-espaces différents est une stratégie prometteuse pour l'optimisation bayésienne par lots à grande échelle, offrant des améliorations significatives de la vitesse de convergence et de la qualité des solutions par rapport aux approches de pointe actuelles.