ImpatientCapsAndRuns : Configuration approximativement optimale des algorithmes à partir d'une réserve infinie

Résumé

Les procédures de configuration d'algorithmes optimisent les paramètres d'un algorithme donné pour qu'il soit performant sur une distribution d'entrées. Les travaux théoriques récents se sont concentrés sur le cas de la sélection entre un petit nombre d'alternatives. En pratique, les espaces de paramètres sont souvent très grands ou infinis, et donc les procédures heuristiques réussies rejettent les paramètres avec impatience'', sur la base de très peu d'observations. Inspiré par cette idée, nous introduisons ImpatientCapsAndRuns, qui écarte rapidement les configurations les moins prometteuses, accélérant de manière significative la procédure de recherche par rapport aux algorithmes précédents avec des garanties théoriques, tout en obtenant un temps d'exécution optimal jusqu'à des facteurs logarithmiques sous des hypothèses douces. Les résultats expérimentaux démontrent une amélioration pratique.