Séance Séminaire

Séminaire de Probabilités et Statistique

Optimal global Lipschitz optimization or function approximation: a bandit perspective

In this talk we explain how sequential algorithms of a "bandit" flavor can help solve problems in global optimization or function approximation in an optimal way. In particular, we consider the problem of black-box optimization of a Lipschitz function f defined on a compact subset X of R^d, and study the number of function evaluations needed to either reach or certify a given accuracy epsilon. We prove refined bounds (and a nearly-matching lower bound) for an algorithm close in spirit to the UCB algorithm. The bounds are f-dependent and can be rewritten in a simple integral form. We will present these results after a brief reminder on bandit problems and the UCB algorithm, and will finish the talk with a short overview of how similar ideas can be useful for some function approximation problems. These are joint works with François Bachoc, Peter Bartlett, Clément Bouttier, Tommaso Cesari, and Pierre Gaillard, in particular: hal-03129721, hal-02976018 and arxiv:2002.02390.

WEBINAIRE ouvert à toutes et tous : https://umontpellier-fr.zoom.us/j/85813807839