Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates
Authors: Francois Bachoc, Tom Cesari, Sébastien Gerchinovitz
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 R X dx/(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. |
| Researcher Affiliation | Collaboration | François Bachoc Institut de Mathématiques de Toulouse & University Paul Sabatier francois.bachoc@math.univ-toulouse.fr Tommaso Cesari Toulouse School of Economics tommaso-renato.cesari@univ-toulouse.fr Sébastien Gerchinovitz IRT Saint Exupéry & Institut de Mathématiques de Toulouse sebastien.gerchinovitz@irt-saintexupery.com |
| Pseudocode | Yes | Algorithm 1: Certified DOO (c.DOO) |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or a link to a code repository for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not present experiments involving datasets, training, or validation data. |
| Dataset Splits | No | The paper is theoretical and does not present experiments involving dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or the specific hardware used to run experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup, therefore no software dependencies with version numbers are listed. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and algorithm design, not on experimental results or their setup. Therefore, no experimental setup details like hyperparameters or training configurations are provided. |