Nearly Optimal Algorithms for Level Set Estimation

Blake Mason, Lalit Jain, Subhojyoti Mukherjee, Romain Camilleri, Kevin Jamieson, Robert Nowak
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:7625-7658, 2022.

Abstract

The level set estimation problem seeks to find all points in a domain $\mathcal{X}$ where the value of an unknown function $f:\mathcal{X}\rightarrow \mathbb{R}$ exceeds a threshold $\alpha$. The estimation is based on noisy function evaluations that may be acquired at sequentially and adaptively chosen locations in $\mathcal{X}$. The threshold value $\alpha$ can either be explicit and provided a priori, or implicit and defined relative to the optimal function value, i.e. $\alpha = (1-\epsilon)f(\mathbf{x}_\ast)$ for a given $\epsilon > 0$ where $f(\mathbf{x}_\ast)$ is the maximal function value and is unknown. In this work we provide a new approach to the level set estimation problem by relating it to recent adaptive experimental design methods for linear bandits in the Reproducing Kernel Hilbert Space (RKHS) setting. We assume that $f$ can be approximated by a function in the RKHS up to an unknown misspecification and provide novel algorithms for both the implicit and explicit cases in this setting with strong theoretical guarantees. Moreover, in the linear (kernel) setting, we show that our bounds are nearly optimal, namely, our upper bounds match existing lower bounds for threshold linear bandits. To our knowledge this work provides the first instance-dependent, non-asymptotic upper bounds on sample complexity of level-set estimation that match information theoretic lower bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-mason22a, title = { Nearly Optimal Algorithms for Level Set Estimation }, author = {Mason, Blake and Jain, Lalit and Mukherjee, Subhojyoti and Camilleri, Romain and Jamieson, Kevin and Nowak, Robert}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {7625--7658}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/mason22a/mason22a.pdf}, url = {https://proceedings.mlr.press/v151/mason22a.html}, abstract = { The level set estimation problem seeks to find all points in a domain $\mathcal{X}$ where the value of an unknown function $f:\mathcal{X}\rightarrow \mathbb{R}$ exceeds a threshold $\alpha$. The estimation is based on noisy function evaluations that may be acquired at sequentially and adaptively chosen locations in $\mathcal{X}$. The threshold value $\alpha$ can either be explicit and provided a priori, or implicit and defined relative to the optimal function value, i.e. $\alpha = (1-\epsilon)f(\mathbf{x}_\ast)$ for a given $\epsilon > 0$ where $f(\mathbf{x}_\ast)$ is the maximal function value and is unknown. In this work we provide a new approach to the level set estimation problem by relating it to recent adaptive experimental design methods for linear bandits in the Reproducing Kernel Hilbert Space (RKHS) setting. We assume that $f$ can be approximated by a function in the RKHS up to an unknown misspecification and provide novel algorithms for both the implicit and explicit cases in this setting with strong theoretical guarantees. Moreover, in the linear (kernel) setting, we show that our bounds are nearly optimal, namely, our upper bounds match existing lower bounds for threshold linear bandits. To our knowledge this work provides the first instance-dependent, non-asymptotic upper bounds on sample complexity of level-set estimation that match information theoretic lower bounds. } }
Endnote
%0 Conference Paper %T Nearly Optimal Algorithms for Level Set Estimation %A Blake Mason %A Lalit Jain %A Subhojyoti Mukherjee %A Romain Camilleri %A Kevin Jamieson %A Robert Nowak %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-mason22a %I PMLR %P 7625--7658 %U https://proceedings.mlr.press/v151/mason22a.html %V 151 %X The level set estimation problem seeks to find all points in a domain $\mathcal{X}$ where the value of an unknown function $f:\mathcal{X}\rightarrow \mathbb{R}$ exceeds a threshold $\alpha$. The estimation is based on noisy function evaluations that may be acquired at sequentially and adaptively chosen locations in $\mathcal{X}$. The threshold value $\alpha$ can either be explicit and provided a priori, or implicit and defined relative to the optimal function value, i.e. $\alpha = (1-\epsilon)f(\mathbf{x}_\ast)$ for a given $\epsilon > 0$ where $f(\mathbf{x}_\ast)$ is the maximal function value and is unknown. In this work we provide a new approach to the level set estimation problem by relating it to recent adaptive experimental design methods for linear bandits in the Reproducing Kernel Hilbert Space (RKHS) setting. We assume that $f$ can be approximated by a function in the RKHS up to an unknown misspecification and provide novel algorithms for both the implicit and explicit cases in this setting with strong theoretical guarantees. Moreover, in the linear (kernel) setting, we show that our bounds are nearly optimal, namely, our upper bounds match existing lower bounds for threshold linear bandits. To our knowledge this work provides the first instance-dependent, non-asymptotic upper bounds on sample complexity of level-set estimation that match information theoretic lower bounds.
APA
Mason, B., Jain, L., Mukherjee, S., Camilleri, R., Jamieson, K. & Nowak, R.. (2022). Nearly Optimal Algorithms for Level Set Estimation . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:7625-7658 Available from https://proceedings.mlr.press/v151/mason22a.html.

Related Material