Bayesian Optimistic Optimisation with Exponentially Decaying Regret

1. Énoncé du problème

L'article aborde le problème de l'optimisation globale de fonctions boîte noire, coûteuses et sans bruit $f(x)$ où $x \in \mathcal{X} \subset \mathbb{R}^D$. L'objectif est de trouver le maximum global $x^*$ avec un budget limité d'évaluations de fonction $N$.

La performance est mesurée par le regret simple :
$$r_N = \sup_{x \in \mathcal{X}} f(x) - \max_{1 \le i \le N} f(x_i)$$

Limites existantes :

• Optimisation Bayésienne (BO) : Les algorithmes BO standards (par exemple, GP-UCB, GP-EI) atteignent généralement des bornes de regret sous-linéaires (par exemple, $O(\sqrt{\frac{\log N}{N}})$ ou $O(1/\sqrt{N})$). Un goulot d'étranglement majeur est que le BO nécessite de résoudre un problème d'optimisation auxiliaire non convexe (maximisation de la fonction d'acquisition) à chaque itération, ce qui est coûteux en calcul et difficile en haute dimension.
• Optimisation Optimiste (basée sur les arbres) : Des algorithmes comme SOO et BaMSOO partitionnent l'espace de recherche de manière hiérarchique. Bien qu'ils évitent l'optimisation auxiliaire, ils souffrent d'une corrélation négative stricte entre le facteur de branchement $m$ (granularité du partitionnement) et le nombre d'expansions de l'arbre. Pour obtenir des partitions fines (grand $m$), ils doivent évaluer de nombreux nœuds enfants, consommant rapidement le budget d'évaluation $N$. Par conséquent, leurs bornes de regret dans le pire des cas sont souvent limitées à $O(e^{-\sqrt{N}})$ ou à des taux sous-linéaires.

Les auteurs se demandent : Pouvons-nous concevoir un algorithme pratique qui combine l'efficacité du modèle du BO avec les avantages structurels de l'optimisation optimiste basée sur les arbres pour atteindre une borne de regret plus serrée (spécifiquement $O(N^{-\sqrt{N}})$) sans le coût computationnel de l'optimisation auxiliaire ?

2. Méthodologie : L'algorithme BOO

Les auteurs proposent l'Optimisation Optimiste Bayésienne (BOO), un nouvel algorithme qui intègre les Processus Gaussiens (GP) avec une recherche hiérarchique sur arbre modifiée.

Innovations clés

1. Découplage du facteur de branchement et des évaluations :

   • Approche traditionnelle : Dans SOO/BaMSOO, l'expansion d'un nœud nécessite d'évaluer $m$ enfants. Ainsi, le nombre d'expansions est plafonné à $N/m$.
   • Approche BOO : L'algorithme sélectionne un nœud à étendre basé sur la borne supérieure de confiance GP (GP-UCB). Crucialement, il n'évalue la fonction objectif qu'au niveau du nœud parent sélectionné, et non au niveau de ses $m$ enfants. Les enfants sont ajoutés à l'arbre structurellement mais restent non évalués jusqu'à ce qu'ils soient sélectionnés ultérieurement.
   • Résultat : Cela "détache" le facteur de branchement $m$ du budget d'évaluation. L'algorithme peut utiliser un $m$ très grand pour créer des partitions extrêmement fines sans payer le coût de $m$ évaluations par étape.

2. Procédure de partitionnement novatrice $P(m; a, b)$ :

   • Au lieu de diviser uniquement le côté le plus long d'une cellule (standard dans SOO), le BOO décompose le facteur de branchement $m = a^b$.
   • Il divise la cellule le long de ses $b$ dimensions les plus longues en $a$ parties égales chacune.
   • En fixant $b = D$ (la dimensionalité), l'algorithme partitionne toutes les dimensions simultanément. Cela permet d'affiner l'espace de recherche beaucoup plus rapidement dans toutes les directions par rapport au fractionnement séquentiel des dimensions.

3. Stratégie d'échantillonnage :

   • L'algorithme maintient un modèle GP.
   • À chaque étape, il sélectionne le nœud feuille ayant la valeur GP-UCB la plus élevée.
   • Il évalue $f$ uniquement au centre de ce nœud sélectionné.
   • Il met à jour le GP et la structure de l'arbre, en ajoutant $m$ enfants au nœud sélectionné.

Flux de l'algorithme (simplifié)

1. Initialiser un arbre avec un nœud racine.
2. Sélectionner le nœud feuille $(h, i)$ avec la valeur GP-UCB maximale $U_p(c_{h,i})$.
3. Si $U_p(c_{h,i}) \ge v_{max}$ (valeur observée actuelle la plus élevée) :
   • Évaluer $f$ au centre du nœud.
   • Mettre à jour l'ensemble de données et réajuster le GP.
   • Étendre le nœud en ajoutant $m$ enfants en utilisant la règle de partitionnement $P(m; a, b)$.
4. Répéter jusqu'à épuisement du budget $N$.

3. Contributions théoriques et analyse du regret

L'article fournit une analyse théorique rigoureuse sous l'hypothèse que $f$ est échantillonné à partir d'un Processus Gaussien avec un noyau Matérn ayant un paramètre de régularité $\nu > 4 + \frac{D}{2}$.

• Borne de regret : Les auteurs prouvent que le BOO atteint une borne de regret simple de :
  $$r_N = O(N^{-\sqrt{N}})$$
  Il s'agit d'un regret à décroissance exponentielle qui est strictement plus serré que la borne $O(e^{-\sqrt{N}})$ des algorithmes optimistes précédents de l'état de l'art (comme IMGPO) et nettement meilleur que les bornes BO standards.

• Mécanisme théorique clé :

  • La preuve repose sur la borne de la taille de l'"ensemble d'expansion" (nœuds qui pourraient potentiellement contenir l'optimum).
  • En utilisant le partitionnement novateur ($b=D$) et le grand facteur de branchement $m$, la "dimension de quasi-optimalité" est montrée comme étant effectivement nulle.
  • Le découplage de $m$ par rapport aux évaluations permet à l'algorithme d'explorer l'espace avec une granularité élevée ($m$ grand) tout en maintenant un faible coût d'évaluation, conduisant à un taux de convergence amélioré.

4. Résultats expérimentaux

Les auteurs ont validé le BOO sur des benchmarks synthétiques et des tâches réelles de réglage d'hyperparamètres en apprentissage automatique.

• Lignes de base : Comparé à GP-EI, GP-UCB, SOO, BaMSOO et IMGPO.
• Fonctions synthétiques : Testé sur les fonctions Hartmann3, Schwefel et Shekel.
  • Résultat : Le BOO a systématiquement surpassé toutes les lignes de base en termes de vitesse de convergence (distance logarithmique à l'optimum). Il a obtenu les meilleures performances sur Hartmann et Schwefel, et des performances compétitives sur Shekel.
• Réglage d'hyperparamètres :
  • Tâches : Réglage d'ElasticNet, MLP et XGBoost sur les ensembles de données MNIST et Skin Segmentation.
  • Résultat : Le BOO a obtenu des erreurs de prédiction inférieures à toutes les lignes de base. Pour XGBoost, il a surpassé les autres de loin.
• Efficacité computationnelle :
  • Le BOO est nettement plus rapide que GP-EI et GP-UCB car il évite la maximisation coûteuse des fonctions d'acquisition sur des espaces continus.
  • Il est légèrement plus lent que IMGPO en raison de la surcharge de gestion d'un arbre plus grand (grand $m$), mais ce compromis offre des performances d'optimisation supérieures.

5. Importance et conclusion

• Briser la barrière du regret : Il s'agit du premier algorithme pratique à atteindre une borne de regret de $O(N^{-\sqrt{N}})$ pour l'optimisation bayésienne, surpassant les limites théoriques des méthodes optimistes et bayésiennes précédentes.
• Praticité : Contrairement aux approches théoriques précédentes qui nécessitaient un échantillonnage impraticable (comme l'échantillonnage $\delta$-cover), le BOO est implémentable et efficace.
• Synergie : Ce travail comble avec succès le fossé entre l'Optimisation basée sur un modèle (BO) et l'Optimisation Optimiste sans modèle, démontrant que l'intégration d'un modèle GP dans une structure basée sur des arbres avec une stratégie d'échantillonnage spécifique peut produire des améliorations exponentielles de la convergence.
• Travaux futurs : Les auteurs prévoient d'étendre la méthode à des environnements bruyants et à des espaces de plus haute dimension.

En résumé, l'article présente une avancée significative dans la théorie et la pratique de l'optimisation globale en introduisant un mécanisme pour découpler la granularité de la recherche du coût d'évaluation, aboutissant à une borne de regret de l'état de l'art et à des performances empiriques supérieures.