The Sample Complexity of Level Set Approximation

François Bachoc, Tommaso Cesari, Sébastien Gerchinovitz
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:424-432, 2021.

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.

Cite this Paper

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. } }
Endnote
%0 Conference Paper %T The Sample Complexity of Level Set Approximation %A François Bachoc %A Tommaso Cesari %A Sébastien Gerchinovitz %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-bachoc21a %I PMLR %P 424--432 %U https://proceedings.mlr.press/v130/bachoc21a.html %V 130 %X 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.
APA
Bachoc, F., Cesari, T. & Gerchinovitz, S.. (2021). The Sample Complexity of Level Set Approximation . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:424-432 Available from https://proceedings.mlr.press/v130/bachoc21a.html.

Related Material