Optimisation parallèle générale sans métrique.

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 la régularité. Cela confirme la validité de POO. Nous montrons que POO peut être utilisé avec HCT comme sous-programme 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. En plus de cela, nous proposons une enveloppe générale, appelée GPO, qui peut faire face aux algorithmes qui n'ont que des garanties de regret simples. Enfin, nous complétons nos résultats par des expériences sur des fonctions difficiles.