Poster
Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates
Francois Bachoc · Tom Cesari · Sébastien Gerchinovitz
Keywords: [ Optimization ] [ Theory ]
Abstract:
We study the problem of zeroth-order (black-box) optimization of a Lipschitz function f defined on a compact subset X of Rd, with the additional constraint that algorithms must certify the accuracy of their recommendations. We characterize the optimal number of evaluations of any Lipschitz function f to find and certify an approximate maximizer of f at accuracy ε. Under a weak assumption on X, this optimal sample complexity is shown to be nearly proportional to the integral ∫Xdx/(max(f)−f(x)+ε)d. This result, which was only (and partially) known in dimension d=1, solves an open problem dating back to 1991. In terms of techniques, our upper bound relies on a packing bound by Bouttier et al. (2020) for the Piyavskii-Shubert algorithm that we link to the above integral. We also show that a certified version of the computationally tractable DOO algorithm matches these packing and integral bounds. Our instance-dependent lower bound differs from traditional worst-case lower bounds in the Lipschitz setting and relies on a local worst-case analysis that could likely prove useful for other learning tasks.
Chat is not available.