Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
In this paper, we consider the problem of sequentially optimizing a black-box function based on noisy samples and bandit feedback. We assume that is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yielding a commonly-considered non-Bayesian form of Gaussian process bandit optimization. We provide algorithm-independent lower bounds on the simple regret, measuring the suboptimality of a single point reported after rounds, and on the cumulative regret, measuring the sum of regrets over the chosen points. For the isotropic squared-exponential kernel in dimensions, we find that an average simple regret of requires , and the average cumulative regret is at least , thus matching existing upper bounds up to the replacement of by in both cases. For the Mat'ern- kernel, we give analogous bounds of the form and , and discuss the resulting gaps to the existing upper bounds.
Florent Gérard Krzakala, Lenka Zdeborová, Hugo Chao Cui
Yves-Marie François Ducimetière