Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization

The goalof online optimization is to find an approximatemaximizer of a given function f: D R d R with as little evaluations off as possible. In this paper we assumethat the only accessto the function f is through an oracle returning the (possibly) perturbed values of the function at the queried points. Perturbations can be deterministic or stochastic. No analytical expression of f or any of its derivatives is available. At each round k the learner picks a new point x k D and the value f(x k) is revealed by the oracle, up to an additive perturbation ξ k . After each evaluation, the learner can return a point x k D, which may differ from the last queried point x k .