Cost-aware Stopping for Bayesian Optimization

Résumé Technique : Arrêt sensible au coût pour l'optimisation bayésienne

Énoncé du problème
Dans l'apprentissage automatique automatisé, la découverte scientifique et d'autres applications de l'optimisation bayésienne (BO), les praticiens sont confrontés au défi de décider quand interrompre l'évaluation de fonctions boîtes noires coûteuses. Bien que des règles d'arrêt existent, elles échouent souvent à prendre en compte les coûts d'évaluation variables de manière rigoureuse.

• Les règles heuristiques (par exemple, des nombres d'itérations fixes ou l'arrêt lorsque la meilleure valeur reste inchangée) manquent de garanties théoriques et peuvent s'arrêter trop tôt ou engendrer des évaluations inutiles.
• Les règles basées sur le regret (par exemple, UCB-LCB, Knowledge Gradient) sont fondées théoriquement pour minimiser le regret simple, mais sont typiquement conçues pour des contextes à coût uniforme. Elles ne prennent pas explicitement en compte les coûts d'évaluation, ce qui conduit souvent à des coûts cumulés excessifs et à un regret ajusté au coût élevé lorsque les coûts sont élevés.
• Les fonctions d'acquisition sensibles au coût (par exemple, l'indice de Gittins de la Boîte de Pandore (PBGI) et le Log Expected Improvement per Cost (LogEIPC)) ont été développées pour optimiser le compromis entre la qualité de la solution et le coût, mais leur intégration avec des règles d'arrêt adaptatives n'a pas été étudiée de manière systématique.

L'objectif central est de concevoir une règle d'arrêt qui optimise le regret simple ajusté au coût attendu, défini comme la somme du regret simple (la différence entre la meilleure solution trouvée et l'optimum global) et du coût cumulé de la collecte de données.

Méthodologie
Les auteurs proposent une nouvelle règle d'arrêt sensible au coût, dérivée du cadre de décision de la Boîte de Pandore. La méthodologie établit un lien théorique entre deux fonctions d'acquisition de pointe sensibles au coût :

1. L'indice de Gittins de la Boîte de Pandore (PBGI) : Dérivé de la solution de programmation dynamique du problème de la Boîte de Pandore, adapté pour l'optimisation bayésienne corrélée.
2. Le Log Expected Improvement per Cost (LogEIPC) : Une approximation à un pas de temps de la politique bayésienne optimale.

La règle d'arrêt proposée, nommée règle d'arrêt PBGI/LogEIPC, est définie par la condition selon laquelle l'optimisation doit cesser lorsqu'aucun point non observé n'offre une amélioration attendue valant son coût d'évaluation. Mathématiquement, la règle s'arrête à l'instant $\tau$ quand :
$$\min_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{PBGI}^\tau(x) \geq y^*_{1:\tau}$$
ou équivalemment :
$$\max_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{LogEIPC}^\tau(x) \leq 0$$
où $y^*_{1:\tau}$ est la meilleure valeur observée à ce jour.

Les détails clés de l'implémentation incluent :

• Moment de mise à jour du postérieur : La règle utilise les valeurs de la fonction d'acquisition calculées après la mise à jour du postérieur de l'itération actuelle (prospectif/forward-looking), ce que les auteurs soutiennent être plus proche de l'intuition de la "valeur réelle" et produit des gains empiriques par rapport aux approches rétroactives (backward-looking).
• Gestion des coûts inconnus : Lorsque les coûts sont inconnus, ils sont modélisés de manière stochastique (par exemple, comme un processus gaussien sur le log-coût), et le coût attendu $E[c(x)]$ est utilisé dans la condition d'arrêt.
• Stabilisation : Pour éviter les arrêts prématurés causés par les fluctuations du modèle ou une optimisation imparfaite de la fonction d'acquisition (particulièrement dans les hautes dimensions), les auteurs imposent une période de stabilisation et appliquent un lissage par moyenne mobile au signal d'arrêt.

Contributions clés

1. Une nouvelle règle d'arrêt sensible au coût : Le papier présente une règle d'arrêt adaptative dérivée de la théorie de la Boîte de Pandore qui s'étend naturellement au principe de conception de l'amélioration attendue. Elle fournit un cadre unifié applicable tant à la BO classique qu'à la BO sensible au coût.
2. Garanties théoriques : Les auteurs prouvent que, lorsqu'elle est couplée à des fonctions d'acquisition PBGI ou LogEIPC, la règle d'arrêt proposée satisfait une borne supérieure théorique sur le regret simple ajusté au coût attendu. Plus précisément, la politique est garantie de ne pas être moins performante que la ligne de base de l'« arrêt immédiat » (s'arrêter juste après la première évaluation). Cela constitue la première garantie théorique de ce type pour toute règle d'arrêt adaptative en optimisation bayésienne.
3. Validation empirique : L'étude fournit une évaluation systématique à travers des tâches synthétiques et des benchmarks empiriques (LCBench pour l'optimisation d'hyperparamètres et NATS-Bench pour la recherche d'architecture neuronale).

Résultats

• Tâches synthétiques : Dans des contextes de regret bayésien en 1D et 8D avec des fonctions de coût uniformes, linéaires et périodiques, la règle d'arrêt PBGI/LogEIPC couplée à sa fonction d'acquisition correspondante égale ou surpasse systématiquement les autres paires (y compris UCB-LCB, LogEIPC-med et PRB). Elle est particulièrement robuste dans les scénarios à coût élevé.
• Benchmarks empiriques :
  • Sur LCBench (35 jeux de données), la règle proposée couplée à PBGI ou LogEIPC se classe dans le top 3 pour environ 75 % des tâches.
  • Sur NATS-Bench, la règle est compétitive, approchant la performance optimale a posteriori.
  • La règle s'arrête de manière fiable avant la limite d'itérations (200 itérations), alors que les règles basées sur le regret (comme SRGap-med et UCB-LCB) échouent fréquemment à s'arrêter tôt, engendrant des coûts excessifs.
  • Les auteurs notent que la sous-performance sur certains petits jeux de données est probablement due à des décalages intrinsèques de validation/test du benchmark plutôt qu'à la règle d'arrêt elle-même.

Signification et affirmations
Le papier affirme traiter une considération pratique cruciale mais sous-explorée en optimisation bayésienne : la détermination sensible au coût de quand s'arrêter.

• Avancement théorique : Le travail comble le fossé entre les fonctions d'acquisition sensibles au coût et l'arrêt adaptatif, fournissant la première garantie formelle qu'une politique adaptative n'entraînera pas un regret ajusté au coût pire que l'arrêt immédiat.
• Utilité pratique : La règle proposée élimine le besoin de réglage heuristique des seuils d'arrêt (par exemple, des constantes fixes ou des seuils basés sur la médiane) en dérivant le seuil directement du coût d'évaluation.
• Robustesse : Le cadre démontre une robustesse à travers diverses structures de coûts et erreurs de spécification de modèle, offrant une alternative fondée sur des principes aux critères d'arrêt heuristiques dans les tâches d'optimisation coûteuses.

Les auteurs concluent que leur cadre peut être étendu à des contextes impliquant des évaluations bruitées, multi-fidélité ou par lots (batches), ainsi qu'à d'autres formulations d'objectifs, bien que cela soit noté comme une direction future plutôt qu'une contribution actuelle.