AISTATS 2021poster8 citations
The Sample Complexity of Level Set Approximation
François Bachoc, Tommaso Cesari, Sébastien Gerchinovitz
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.
BibTeX
@InProceedings{pmlr-v130-bachoc21a,
title = { The Sample Complexity of Level Set Approximation },
author = {Bachoc, Fran{\c{c}}ois and Cesari, Tommaso and Gerchinovitz, S{\'e}bastien},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {424--432},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/bachoc21a/bachoc21a.pdf},
url = {https://proceedings.mlr.press/v130/bachoc21a.html},
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. }
}