Adaptive Candidate Point Thompson Sampling for High-Dimensional Bayesian Optimization

Ce papier présente l'Adaptive Candidate Thompson Sampling (ACTS), une méthode qui améliore l'optimisation bayésienne en haute dimension en générant dynamiquement des points candidats dans des sous-espaces guidés par le gradient d'un modèle de substitution, surmontant ainsi la rareté des points dans les discrétisations fixes traditionnelles.

L'essentiel

Imagine que vous êtes un explorateur perdu dans une forêt immense et très complexe (c'est votre problème d'optimisation). Votre objectif est de trouver le point le plus haut de cette forêt (le sommet de la montagne) pour avoir la meilleure vue. Mais il y a un problème : la forêt est si grande qu'elle a des milliers de dimensions, et vous ne pouvez faire que quelques pas à la fois avant de vous fatiguer (c'est l'évaluation coûteuse d'une fonction).

C'est là qu'intervient l'Optimisation Bayésienne. C'est comme avoir un guide très intelligent qui dessine une carte mentale de la forêt en se basant sur les quelques endroits où vous avez déjà marché. Ce guide essaie de deviner où se trouve le sommet.

Le Problème : La "Malédiction de la Dimension"

Dans les méthodes classiques, le guide essaie de deviner le sommet en regardant des milliers de points dispersés au hasard dans la forêt.

• L'analogie : Imaginez que vous cherchez une aiguille dans une botte de foin. Si la botte de foin est petite, vous pouvez la fouiller rapidement. Mais si la botte de foin est aussi grande qu'un continent (des centaines de dimensions), et que vous ne pouvez regarder que 10 000 points au total, votre recherche sera comme chercher une aiguille dans l'océan. Les points sont si espacés que vous avez de fortes chances de rater le sommet, même s'il est juste à côté de l'un de vos points de contrôle.

C'est ce que les auteurs appellent la "malédiction de la dimension". Plus la forêt est grande, plus il faut de points pour la couvrir, et plus il est difficile de trouver le chemin.

La Solution : ACTS (L'Explorateur Intuitif)

Les auteurs proposent une nouvelle méthode appelée ACTS (Adaptive Candidate Thompson Sampling). Au lieu de regarder des points au hasard dans toute la forêt, ACTS change de stratégie.

Voici comment cela fonctionne, avec une analogie simple :

1. Le Guide a un "Pressentiment" (L'échantillonnage) :
   Le guide ne se contente pas de regarder la carte. Il tire au sort une version possible de la forêt (une "réalisation" de la carte). Sur cette version imaginaire, il cherche le point le plus haut.

2. Sentir la Pente (Le Gradient) :
   Au lieu de regarder partout, le guide se place à l'endroit où vous êtes actuellement (le "meilleur point connu") et il demande : "Si je devais grimper sur cette version imaginaire de la forêt, dans quelle direction la pente monte-t-elle ?". Il sent la direction de la montée (le gradient).

3. Réduire la Zone de Recherche (Le Cône) :
   C'est l'astuce géniale. Au lieu de chercher dans toute la forêt, le guide dit : "Oublions les autres directions. Concentrons-nous uniquement sur un petit couloir, un cône étroit qui pointe exactement dans la direction de la montée que je viens de sentir.".

   • L'analogie : Imaginez que vous cherchez un trésor. Au lieu de fouiller tout le désert, vous avez une boussole qui vous dit "Le trésor est quelque part vers le Nord". Au lieu de chercher partout, vous ne cherchez que dans un petit chemin qui part vers le Nord. Cela rend votre recherche beaucoup plus dense et efficace.

4. Remplir le Couloir :
   Puisque cette zone est maintenant beaucoup plus petite, vous pouvez y placer beaucoup plus de points de contrôle (des "candidats") sans dépasser votre budget d'énergie. Vous avez maintenant une carte très détaillée de ce couloir prometteur, ce qui augmente vos chances de trouver le vrai sommet.

Pourquoi c'est génial ?

• C'est comme un zoom intelligent : Au lieu de regarder la forêt entière avec des jumelles floues, vous zoomez sur la zone où la probabilité de trouver le sommet est la plus élevée.
• Pas de piège local : Même si le guide tire au sort une direction qui semble bonne mais qui mène à une petite colline (un optimum local), le fait que ce soit un "tirage au sort" signifie qu'au fil du temps, il essaiera aussi d'autres directions. Il ne restera pas coincé.
• Simple et efficace : Cette méthode peut remplacer n'importe quelle méthode existante sans changer tout le système. C'est comme changer les pneus de votre voiture pour des pneus de course : la voiture fonctionne déjà, mais elle va beaucoup plus vite.

En Résumé

Le papier explique comment trouver le meilleur point dans un monde très complexe (comme régler les paramètres d'une intelligence artificielle ou concevoir une nouvelle molécule de médicament).

Au lieu de chercher au hasard dans un espace gigantesque (ce qui est inefficace), ACTS utilise l'intuition du guide pour se concentrer uniquement sur les zones où la "pente" monte. C'est comme passer d'une recherche au hasard dans une ville entière à une recherche ciblée dans une seule rue où l'on a vu quelqu'un courir vers la sortie. Le résultat ? On trouve le meilleur endroit beaucoup plus vite et avec moins d'efforts.

Résumé technique

1. Le Problème : Le Fléau de la Dimensionnalité dans l'Optimisation Bayésienne

L'optimisation bayésienne (BO) est un cadre puissant pour l'optimisation de fonctions coûteuses et sans forme analytique (boîte noire), largement utilisé en apprentissage automatique et en découverte scientifique. L'approche standard utilise souvent l'Échantillonnage de Thompson (Thompson Sampling - TS) pour sélectionner les points d'évaluation suivants.

Cependant, l'application du TS avec des processus gaussiens (GP) dans des espaces de haute dimension (des centaines ou milliers de dimensions) se heurte à un problème majeur :

• Intracabilité du tirage continu : Échantillonner une fonction continue $f$ à partir d'un GP est impossible. On doit donc discrétiser l'espace en un ensemble fini de points candidats $\tilde{X}$.
• Densité exponentielle : Pour couvrir efficacement un espace de dimension $d$, le nombre de points nécessaires croît exponentiellement avec $d$. Avec une limite de calcul typique d'environ $10^4$ points candidats, la densité devient extrêmement faible en haute dimension, rendant la probabilité de trouver le maximum d'un échantillon de fonction (le "maximizer") négligeable.
• Limites des méthodes existantes : Les approches actuelles tentent de contourner ce problème soit par des approximations de GP évolutives, soit en restreignant la recherche à des sous-espaces locaux (comme dans TuRBO) ou en utilisant des perturbations aléatoires sur un petit nombre de dimensions (RAASP). Ces méthodes souffrent souvent d'une densité de points insuffisante ou d'une exploration trop locale.

2. Méthodologie : Échantillonnage de Thompson à Candidats Adaptatifs (ACTS)

Les auteurs proposent ACTS, une méthode qui augmente la densité des points candidats non pas en élargissant l'ensemble, mais en réduisant adaptivement l'espace de recherche avant le tirage.

Principe Fondamental

L'idée clé est que l'ensemble des points candidats ne doit pas être indépendant de l'échantillon de la fonction postérieure. ACTS exploite le fait que les GPs sont fermés sous les opérations linéaires, permettant d'échantillonner conjointement la fonction $f$ et son gradient $\nabla f$ au point actuel (l'incumbent $x_0$).

Algorithme ACTS

Le processus se déroule en plusieurs étapes à chaque itération :

1. Échantillonnage du Gradient : On échantillonne le gradient du processus gaussien au point incumbent $x_0$, noté $\nabla f(x_0) \sim p(\nabla f(x_0) | D_t)$. Ce gradient indique une direction de montée probable pour l'échantillon de fonction courant.
2. Construction de l'Espace de Recherche Adaptatif : Au lieu de chercher dans tout l'espace $X$, ACTS définit un sous-espace $T_{\nabla f(x_0)}$ aligné avec ce gradient.
   • L'espace est défini comme un cône aligné sur les axes (axis-aligned cone) partant de $x_0$ et s'étendant dans la direction des composantes positives du gradient.
   • Mathématiquement : $T_{\nabla f(x_0)} = \{x_0 + v \odot \nabla f(x_0) \mid 0 \preceq v \in \mathbb{R}^d\} \cap X$.
   • Cela réduit drastiquement le volume de recherche (d'un facteur de $2^d$ dans le pire des cas), augmentant ainsi la densité des points candidats dans la région prometteuse.
3. Génération des Candidats : Un ensemble de points candidats $\tilde{X}$ est généré à l'intérieur de ce cône restreint, en utilisant une politique de base (comme Sobol ou RAASP) mais appliquée uniquement dans ce sous-espace.
4. Échantillonnage et Maximisation : On échantillonne les valeurs de la fonction $f$ sur $\tilde{X}$ conditionnellement au gradient échantillonné, puis on sélectionne le point maximisant cet échantillon.

Intégration avec RAASP

Les auteurs montrent comment ACTS peut améliorer la politique RAASP (Random Axis-Aligned Subspace Perturbations) en modifiant la probabilité de sélection des dimensions à perturber. Au lieu de choisir les dimensions au hasard, la probabilité de perturber une dimension $j$ est proportionnelle au carré de la composante du gradient $|\nabla f(x_0)_j|^2$, favorisant ainsi les directions de forte pente.

3. Contributions Clés

1. Nouvelle Stratégie de Discrétisation : ACTS introduit une approche orthogonale aux méthodes existantes : au lieu d'approximer le GP pour gérer la dimensionnalité, elle adapte la géométrie de l'ensemble de candidats en fonction de l'échantillon de fonction lui-même.
2. Garantie de Consistance Globale : Bien que la méthode utilise une information locale (le gradient), les auteurs prouvent théoriquement (Théorème 1) que l'algorithme conserve la consistance globale. L'espace de recherche reste bien défini même si le gradient est proche de zéro (grâce à la nature stochastique de l'échantillonnage), garantissant que l'algorithme finira par explorer l'ensemble de l'espace et converger vers le maximum global.
3. Compatibilité et Modularité : ACTS est un "remplacement plug-and-play" (drop-in replacement) pour les méthodes TS existantes. Elle fonctionne aussi bien en mode séquentiel que par lots (batch), et s'intègre naturellement avec des méthodes de régions de confiance (Trust Regions) comme TuRBO, offrant des bénéfices complémentaires.
4. Efficacité Computationnelle : La complexité supplémentaire est négligeable ($O(n_t^2 d)$ pour l'échantillonnage du gradient et $O(M d^2)$ pour la conditionnalité), restant dominée par la décomposition de Cholesky standard $O(M^3)$ nécessaire à l'échantillonnage du GP.

4. Résultats Expérimentaux

Les auteurs ont évalué ACTS sur une large gamme de benchmarks synthétiques et réels, allant de 12 à 1000 dimensions (ex: Lunar Lander, Rover, MOPTA08, réglage d'hyperparamètres SVM, conception de molécules GuacaMol).

• Performance Supérieure : ACTS surpasse systématiquement les méthodes de référence (RAASP, Cylindrical TS, Pathwise TS) sur la majorité des benchmarks, en particulier en haute dimension.
• Qualité des Échantillons : L'analyse montre que les points candidats générés par ACTS atteignent des valeurs de fonction postérieure ($f_{max}$) significativement plus élevées que les autres méthodes, ce qui se traduit directement par de meilleures performances d'optimisation.
• Densité et Volume : ACTS réduit le volume de l'espace de recherche de plusieurs ordres de grandeur (ex: $10^{-18}$ pour 60 dimensions) par rapport à l'espace complet, augmentant la densité effective des points candidats sans augmenter le budget de calcul.
• Exploration vs Exploitation : Contrairement à une intuition initiale, l'analyse de la "localité" (via la distance de voyage du voyageur de commerce) montre qu'ACTS n'est pas plus local que les autres méthodes TS et maintient une bonne capacité d'exploration.
• Comparaison avec l'État de l'Art : ACTS égale ou dépasse des méthodes avancées comme SAASBO, BAxUS et LogEI sur de nombreux problèmes, démontrant une robustesse supérieure.

5. Signification et Impact

Ce travail est significatif car il résout un goulot d'étranglement fondamental de l'optimisation bayésienne en haute dimension : la sparsité des points candidats.

• Changement de paradigme : Au lieu de simplement approximer le modèle pour le rendre calculable, ACTS utilise l'information structurelle du modèle (le gradient échantillonné) pour guider la discrétisation de l'espace.
• Efficacité pratique : En permettant une discrétisation beaucoup plus dense dans les régions prometteuses, ACTS permet aux méthodes TS de réaliser leur potentiel théorique de convergence même dans des espaces à milliers de dimensions.
• Applicabilité : La méthode est simple à implémenter, compatible avec les infrastructures existantes (comme BoTorch) et applicable à des domaines variés allant de la robotique à la découverte de matériaux et de médicaments.

En résumé, ACTS offre une solution élégante et théoriquement fondée pour rendre l'échantillonnage de Thompson efficace en haute dimension, en adaptant dynamiquement la granularité de la recherche à la géométrie locale de la fonction objectif estimée.