L'optimisation adaptative de la boîte noire est devenue plus facile : HCT n'a besoin que d'une régularité locale.

Résumé Les bandits hiérarchiques sont une approche pour l'optimisation globale de fonctions extrêmement irrégulières. Cet article fournit de nouveaux éléments concernant POO, un méta-algorithme adaptatif qui ne nécessite pas la connaissance de la régularité locale de la fonction cible. Nous mettons d'abord en évidence le fait que l'algorithme de sous-routine utilisé dans POO doit avoir un petit regret sous l'hypothèse de lissage local par rapport au partitionnement choisi, qui est inconnu s'il est satisfait par le sous-routine standard HOO. Dans ce travail, nous établissons une telle garantie de regret pour HCT, qui est un autre algorithme d'optimisation optimiste hiérarchique qui a besoin de connaître le lissage. Cela confirme la validité de POO. Nous montrons que POO peut être utilisé avec HCT comme une sous-routine avec une borne supérieure de regret qui correspond à celle des algorithmes les plus connus utilisant la connaissance de la régularité jusqu'à un facteur √ log n.