Abstract Submission

6639. On the optimality of the Piyavskii-Shubert algorithm for global Lipschitz optimization: a bandit perspective

Contributed abstract in session FA-5: Optimization and Artificial Intelligence II, stream Optimization and Artificial Intelligence.

Friday, 9:00 - 10:40
Room: Pontryagin

Authors (first author is the speaker)

1. Clément Bouttier
2. Sébastien Gerchinovitz
Université Toulouse 3 - Paul Sabatier
3. Tommaso Cesari


We consider the problem of maximizing a non-concave Lipschitz multivariate function over a compact domain by sequentially querying its (possibly perturbed) values. We study a natural algorithm originally designed by Piyavskii and Shubert in 1972, for which we prove new bounds on the number of evaluations of the function needed to reach or certify a given optimization accuracy. Our analysis uses a bandit-optimization viewpoint and solves an open problem from Hansen et al. (1991), by bounding the number of evaluations to certify a given accuracy with a simple and optimal integral.


Status: accepted

Back to the list of papers