Learning to Assess the Reliability of Number-of-Runs Estimation in Stochastic Optimization

Résumé technique : Apprentissage de l'évaluation de la fiabilité de l'estimation du nombre d'exécutions dans l'optimisation stochastique

Énoncé du problème
Le benchmarking à grande échelle des algorithmes d'optimisation stochastique fait face à une tension fondamentale entre la fiabilité expérimentale et l'efficacité computationnelle. Bien que des exécutions répétées soient nécessaires pour une évaluation valide des performances, le coût d'une répétition extensive croît rapidement avec l'échelle des portefeuilles d'algorithmes et des dimensions des problèmes. Les pratiques actuelles reposent sur des choix de conception statiques (par exemple, fixer le nombre d'exécutions à 15, 25 ou 50), qui supposent implicitement un comportement homogène des algorithmes à travers les problèmes — une hypothèse rarement étayée par des preuves empiriques.

Un travail récent a introduit une heuristique en ligne empirique qui estime de manière adaptative le nombre d'exécutions requis par instance en surveillant la stabilité des performances et la symétrie de la distribution. Bien que cette méthode améliore l'efficacité en réduisant le nombre total d'exécutions d'environ 50 %, elle souffre d'une limitation critique : dans un sous-ensemble de cas (déviation de 5 à 25 %), le nombre d'exécutions estimé est inexact. Ces inexactitudes ne peuvent être détectées rétrospectivement qu'après l'achèvement de toutes les exécutions, rendant la méthode inadaptée aux scénarios de benchmarking entièrement en ligne où une prise de décision en temps réel est requise.

Méthodologie
Cette étude propose une extension basée sur l'apprentissage de l'heuristique en ligne empirique existante, la transformant en un système d'auto-évaluation capable de détecter précocement les estimations du nombre d'exécutions peu fiables.

• Source de données et annotation : L'étude utilise un jeu de données dérivé de 132 000 exécutions de 11 algorithmes d'optimisation (du framework Nevergrad) à travers 24 classes de problèmes en 20 dimensions (suite de benchmarks COCO). Les étiquettes de vérité terrain (estimations fiables vs non fiables) ont été établies via une analyse post-hoc des expériences d'arrêt adaptatif originales, qui utilisaient trois méthodes de détection d'outliers (IQR, élagage par percentiles, score z modifié) et quatre seuils d'asymétrie (0,05 ; 0,10 ; 0,15 ; 0,20).
• Extraction de caractéristiques : Pour permettre l'apprentissage supervisé, les séquences de longueur variable des valeurs de la fonction objectif sont transformées en vecteurs de caractéristiques de dimension fixe. Un total de 23 caractéristiques est extrait, classé comme suit :
  • Statistiques : Moyenne, médiane, écart-type, variance, quartiles, écart interquartile, MAD, coefficient de variation.
  • Distributionnelles : Asymétrie, kurtosis, entropie.
  • Liées à l'énergie : Somme, somme des valeurs absolues, énergie du signal, racine carrée de la moyenne quadratique.
  • Forme et stabilité : Pente de l'amélioration des performances, écart-type glissant, énergie FFT et autocorrélation.
• Tâche d'apprentissage : Le problème est formulé comme une tâche de classification binaire visant à prédire si une estimation du nombre d'exécutions est correcte (1) ou incorrecte (0).
  • Déséquilibre des classes : Le jeu de données présente un fort déséquilibre de classes. L'étude privilégie la détection des estimations incorrectes (classe minoritaire) pour éviter un arrêt prématuré.
  • Sélection de modèle : L'optimisation des hyperparamètres est réalisée à l'aide d'Optuna sur des modèles basés sur des arbres et des modèles d'ensemble (arbres de décision, forêts aléatoires, XGBoost, LightGBM, CatBoost). La fonction objectif maximise le Rappel0 (rappel de la classe minoritaire) plutôt que la précision ou le score F1, car les faux négatifs (prédire une estimation non fiable comme fiable) sont plus préjudiciables que les faux positifs.
  • Configuration expérimentale : Une configuration d'apprentissage « au sein d'une configuration » est employée. Les modèles sont entraînés et testés sur des données partageant le même optimiseur, la même méthode de détection d'outliers et le même seuil d'asymétrie. Cela donne lieu à 132 jeux de données distincts (3 méthodes × 4 seuils × 11 algorithmes).

Contributions clés

1. Recadrage de l'arrêt adaptatif : L'article déplace l'accent de la simple estimation du nombre d'exécutions vers l'évaluation de la fiabilité de cette estimation en temps réel.
2. Ingénierie des caractéristiques pour la dynamique d'optimisation : Il introduit un ensemble spécifique de 23 caractéristiques statistiques, sans énergie, et de forme/stabilité dérivées des trajectoires d'optimisation pour caractériser le comportement de convergence.
3. Stratégie de classification déséquilibrée : Il démontre une approche spécifique pour gérer les données déséquilibrées dans les contextes de benchmarking, où le coût de manquer une estimation non fiable (faux négatif) l'emporte sur le coût des exécutions redondantes (faux positif).

Résultats
L'évaluation révèle des défis significatifs et des succès spécifiques dans l'apprentissage de la fiabilité au sein de configurations fixes :

• Généralisabilité limitée : Des classifieurs valides (répondant à $F1_1 > 0,70$ et $Recall_0 > 0,80$) n'ont été obtenus que dans 48,5 % des 132 configurations (64/132). Cela souligne la difficulté d'apprendre des modèles fiables lorsqu'ils sont restreints à un seul optimiseur et à des paramètres expérimentaux fixes.
• Variabilité algorithmique : La prévisibilité variait considérablement selon l'algorithme. La différenciation évolutionnaire (DE), CMA diagonale, NGOpt14 et NGOpt38 ont atteint les taux de réussite les plus élevés (66,7 % de configurations valides), tandis que NaiveIsoEMNA était le plus difficile à prédire (8,3 % de configurations valides).
• Arbitrage avec la ligne de base : Par rapport à une ligne de base de classe majoritaire (qui prédit toutes les instances comme fiables), les classifieurs entraînés ont souvent sous-performé en termes de $F1_1$ (seulement 6,8 % des jeux de données ont surpassé la ligne de base). Cependant, la ligne de base a obtenu un $Recall_0$ de 0,00, ce qui signifie qu'elle a complètement échoué à identifier les estimations non fiables. En revanche, les classifieurs entraînés ont systématiquement atteint des valeurs de $Recall_0$ supérieures à 0,80, identifiant avec succès les cas de convergence problématiques que la ligne de base avait manqués.

Portée et affirmations
L'article affirme que la fiabilité du nombre d'exécutions peut être apprise dans un scénario au sein d'une configuration, permettant la détection d'estimations non fiables avec un rappel élevé de la classe minoritaire. Cette capacité transforme l'heuristique adaptative en un système qui soutient les décisions expérimentales en temps réel tout en préservant les avantages d'efficacité de l'estimation adaptative du nombre d'exécutions.

Cependant, les auteurs sont modestes quant à la portée de ces résultats. Ils déclarent explicitement que les performances sont « limitées par la diversité restreinte des données au sein des configurations fixes ». Avec seulement 240 instances par configuration, les modèles peinent à apprendre au-delà de la prédiction de la classe majoritaire. L'étude conclut que, bien que la prédiction de la fiabilité soit possible, elle reste difficile dans des contextes à données limitées, suggérant que les travaux futurs devraient explorer des scénarios où les données de différents algorithmes d'optimisation sont combinées pour augmenter la diversité de l'entraînement.