Active Level Set Estimation for Continuous Search Space with Theoretical Guarantee

Giang Ngo, Dang Nguyen, Dat Phan-Trong, Sunil Gupta
Proceedings of the 15th Asian Conference on Machine Learning, PMLR 222:943-958, 2024.

Abstract

A common problem encountered in many real-world applications is level set estimation where the goal is to determine the region in the function domain where the function is above or below a given threshold. When the function is black-box and expensive to evaluate, the level sets need to be found in a minimum set of function evaluations. Existing methods often assume a discrete search space with a finite set of data points for function evaluations and estimating the level sets. When applied to a continuous search space, these methods often need to first discretize the space which leads to poor results while needing high computational time. While some methods cater for the continuous setting, they still lack a proper guarantee for theoretical convergence. To address this problem, we propose a novel algorithm that does not need any discretization and can directly work in continuous search spaces. Our method suggests points by constructing an acquisition function that is defined as a measure of confidence of the function being higher or lower than the given threshold. A theoretical analysis for the convergence of the algorithm to an accurate solution is provided. On multiple synthetic and real-world datasets, our algorithm successfully outperforms state-of-the-art methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v222-ngo24a, title = {Active Level Set Estimation for Continuous Search Space with Theoretical Guarantee}, author = {Ngo, Giang and Nguyen, Dang and Phan-Trong, Dat and Gupta, Sunil}, booktitle = {Proceedings of the 15th Asian Conference on Machine Learning}, pages = {943--958}, year = {2024}, editor = {Yanıkoğlu, Berrin and Buntine, Wray}, volume = {222}, series = {Proceedings of Machine Learning Research}, month = {11--14 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v222/ngo24a/ngo24a.pdf}, url = {https://proceedings.mlr.press/v222/ngo24a.html}, abstract = {A common problem encountered in many real-world applications is level set estimation where the goal is to determine the region in the function domain where the function is above or below a given threshold. When the function is black-box and expensive to evaluate, the level sets need to be found in a minimum set of function evaluations. Existing methods often assume a discrete search space with a finite set of data points for function evaluations and estimating the level sets. When applied to a continuous search space, these methods often need to first discretize the space which leads to poor results while needing high computational time. While some methods cater for the continuous setting, they still lack a proper guarantee for theoretical convergence. To address this problem, we propose a novel algorithm that does not need any discretization and can directly work in continuous search spaces. Our method suggests points by constructing an acquisition function that is defined as a measure of confidence of the function being higher or lower than the given threshold. A theoretical analysis for the convergence of the algorithm to an accurate solution is provided. On multiple synthetic and real-world datasets, our algorithm successfully outperforms state-of-the-art methods.} }
Endnote
%0 Conference Paper %T Active Level Set Estimation for Continuous Search Space with Theoretical Guarantee %A Giang Ngo %A Dang Nguyen %A Dat Phan-Trong %A Sunil Gupta %B Proceedings of the 15th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Berrin Yanıkoğlu %E Wray Buntine %F pmlr-v222-ngo24a %I PMLR %P 943--958 %U https://proceedings.mlr.press/v222/ngo24a.html %V 222 %X A common problem encountered in many real-world applications is level set estimation where the goal is to determine the region in the function domain where the function is above or below a given threshold. When the function is black-box and expensive to evaluate, the level sets need to be found in a minimum set of function evaluations. Existing methods often assume a discrete search space with a finite set of data points for function evaluations and estimating the level sets. When applied to a continuous search space, these methods often need to first discretize the space which leads to poor results while needing high computational time. While some methods cater for the continuous setting, they still lack a proper guarantee for theoretical convergence. To address this problem, we propose a novel algorithm that does not need any discretization and can directly work in continuous search spaces. Our method suggests points by constructing an acquisition function that is defined as a measure of confidence of the function being higher or lower than the given threshold. A theoretical analysis for the convergence of the algorithm to an accurate solution is provided. On multiple synthetic and real-world datasets, our algorithm successfully outperforms state-of-the-art methods.
APA
Ngo, G., Nguyen, D., Phan-Trong, D. & Gupta, S.. (2024). Active Level Set Estimation for Continuous Search Space with Theoretical Guarantee. Proceedings of the 15th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 222:943-958 Available from https://proceedings.mlr.press/v222/ngo24a.html.

Related Material