Optimal Multi-Fidelity Best-Arm Identification

Poiani, Riccardo; Degenne, Rémy; Kaufmann, Emilie; Metelli, Alberto Maria; Restelli, Marcello

Type de document :

Communication dans un congrès avec actes

Titre :

Optimal Multi-Fidelity Best-Arm Identification

Auteur(s) :

Poiani, Riccardo [Auteur]
Politecnico di Milano [Milan] [POLIMI]
Degenne, Rémy [Auteur]
Scool [Scool]
Kaufmann, Emilie [Auteur]

Centre National de la Recherche Scientifique [CNRS]
Scool [Scool]
Metelli, Alberto Maria [Auteur]
Politecnico di Milano [Milan] [POLIMI]
Restelli, Marcello [Auteur]
Politecnico di Milano [Milan] [POLIMI]

Titre de la manifestation scientifique :

Advances in Neural Information Processing Systems (NeurIPS)

Ville :

Vancouver (BC)

Pays :

Canada

Date de début de la manifestation scientifique :

2024-12-10

Date de publication :

2024-12-10

Discipline(s) HAL :

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

Résumé en anglais : [en]

In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible. We study multi-fidelity best-arm identification, in which the algorithm ...
Lire la suite >In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible. We study multi-fidelity best-arm identification, in which the algorithm can choose to sample an arm at a lower fidelity (less accurate mean estimate) for a lower cost. Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm. Our first contribution is a tight, instance-dependent lower bound on the cost complexity. The study of the optimization problem featured in the lower bound provides new insights to devise computationally efficient algorithms, and leads us to propose a gradient-based approach with asymptotically optimal cost complexity. We demonstrate the benefits of the new algorithm compared to existing methods in experiments. Our theoretical and empirical findings also shed light on an intriguing concept of optimal fidelity for each arm.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Foundations of robustness and reliability in artificial intelligence
Tests Adaptatifs et Frugaux

Collections :