The sample complexity of level set approximation

Abstract

We study the problem of approximating the level set of an unknown function by sequentially querying its values. We introduce a family of algorithms called Bisect and Approximate through which we reduce the level set approximation problem to a local function approximation problem. We then show how this approach leads to rate-optimal sample complexity guarantees for H{ö}lder functions, and we investigate how such rates improve when additional smoothness or other structural assumptions hold true.

References in corpus (6)

• Sequential design of computer experiments for the estimation of a probability of failure
• Optimal rates for plug-in estimators of density level sets
• Black-box optimization of noisy functions with unknown smoothness
• Gaussian process surrogates for failure detection: a Bayesian experimental design approach
• Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization
• Adaptive Hausdorff estimation of density level sets