General parallel optimization without a metric

Shang, Xuedong; Kaufmann, Emilie; Valko, Michal

Type de document :

Communication dans un congrès avec actes

Titre :

General parallel optimization without a metric

Auteur(s) :

Shang, Xuedong [Auteur]
Sequential Learning [SEQUEL]
Kaufmann, Emilie [Auteur]

Sequential Learning [SEQUEL]
Centre National de la Recherche Scientifique [CNRS]
Valko, Michal [Auteur]

Sequential Learning [SEQUEL]

Titre de la manifestation scientifique :

Algorithmic Learning Theory

Ville :

Chicago

Pays :

Etats-Unis d'Amérique

Date de début de la manifestation scientifique :

2019

Date de publication :

2019

Mot(s)-clé(s) en anglais :

continuously-armed bandits
global optimization
black-box optimization

Discipline(s) HAL :

Statistiques [stat]/Machine Learning [stat.ML]

Résumé en anglais : [en]

Hierarchical bandits are an approach for global optimization of extremely irregular functions. This paper provides new elements regarding POO, an adaptive meta-algorithm that does not require the knowledge of local smoothness ...
Lire la suite >Hierarchical bandits are an approach for global optimization of extremely irregular functions. This paper provides new elements regarding POO, an adaptive meta-algorithm that does not require the knowledge of local smoothness of the target function. We first highlight the fact that the subroutine algorithm used in POO should have a small regret under the assumption of local smoothness with respect to the chosen partitioning, which is unknown if it is satisfied by the standard subroutine HOO. In this work, we establish such regret guarantee for HCT, which is another hierarchical optimistic optimization algorithm that needs to know the smoothness. This confirms the validity of POO. We show that POO can be used with HCT as a subroutine with a regret upper bound that matches the one of best-known algorithms using the knowledge of smoothness up to a √ log n factor. On top of that, we propose a general wrapper, called GPO, that can cope with algorithms that only have simple regret guarantees. Finally, we complement our findings with experiments on difficult functions.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Inférence bayésienne à ressources limitées - données massives et modèles coûteux
Extraction et transfert de connaissances dans l'apprentissage par renforcement
BANDITS MANCHOTS POUR SIGNAUX NON-STATIONNAIRES ET STRUCTURES

Collections :