Regret analysis of the Piyavskii-Shubert algorithm ---- Sébastien Gerchinovitz

  • When Oct 08, 2019 from 11:00 AM to 12:00 PM (Europe/Amsterdam / UTC200)
  • Where L016
  • Add event to calendar iCal

We consider the problem of maximizing a non-convex Lipschitz function f over a bounded domain in dimension d. In this talk we provide regret guarantees for a decade-old algorithm due to Piyavskii and Shubert (1972). These bounds are derived in the general setting when f is only evaluated approximately. In particular they yield optimal regret bounds when f is observed under independent subgaussian noise. This is joint work with Clément Bouttier and Tommaso Cesari.