Exploring High-dimensional Search Space via Voronoi Graph Traversing

Aidong Zhao, Xuyang Zhao, Tianchen Gu, Zhaori Bi, Xinwei Sun, Changhao Yan, Fan Yang, Dian Zhou, Xuan Zeng
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:4219-4236, 2024.

Abstract

Bayesian optimization (BO) is a well-established methodology for optimizing costly black-box functions. However, the sparse observations in the high-dimensional search space pose challenges in constructing reliable Gaussian Process (GP) models, which leads to blind exploration of the search space. We propose a novel Voronoi Graph Traversing (VGT) algorithm to extend BO to ultra high-dimensional problems. VGT employs a Voronoi diagram to mesh the design space and transform it into an undirected Voronoi graph. VGT explores the search space by iteratively performing path selection, promising cell sampling, and graph expansion operations. We introduce a UCB-based global traversal strategy to select the path towards promising Voronoi cells. Then we perform local BO within the promising cell and train local GP with a neighboring subset. The intrinsic geometric boundaries and adjacency of the Voronoi graph assist in fine-tuning the trajectory of local BO sampling. We also present a subspace enhancement approach for the intrinsic low-dimensional problems. Experimental results, including both synthetic benchmarks and real-world applications, demonstrate the proposed approach’s state-of-the-art performance for tackling ultra high-dimensional problems ranging from hundreds to one thousand dimensions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-zhao24a, title = {Exploring High-dimensional Search Space via Voronoi Graph Traversing}, author = {Zhao, Aidong and Zhao, Xuyang and Gu, Tianchen and Bi, Zhaori and Sun, Xinwei and Yan, Changhao and Yang, Fan and Zhou, Dian and Zeng, Xuan}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {4219--4236}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/zhao24a/zhao24a.pdf}, url = {https://proceedings.mlr.press/v244/zhao24a.html}, abstract = {Bayesian optimization (BO) is a well-established methodology for optimizing costly black-box functions. However, the sparse observations in the high-dimensional search space pose challenges in constructing reliable Gaussian Process (GP) models, which leads to blind exploration of the search space. We propose a novel Voronoi Graph Traversing (VGT) algorithm to extend BO to ultra high-dimensional problems. VGT employs a Voronoi diagram to mesh the design space and transform it into an undirected Voronoi graph. VGT explores the search space by iteratively performing path selection, promising cell sampling, and graph expansion operations. We introduce a UCB-based global traversal strategy to select the path towards promising Voronoi cells. Then we perform local BO within the promising cell and train local GP with a neighboring subset. The intrinsic geometric boundaries and adjacency of the Voronoi graph assist in fine-tuning the trajectory of local BO sampling. We also present a subspace enhancement approach for the intrinsic low-dimensional problems. Experimental results, including both synthetic benchmarks and real-world applications, demonstrate the proposed approach’s state-of-the-art performance for tackling ultra high-dimensional problems ranging from hundreds to one thousand dimensions.} }
Endnote
%0 Conference Paper %T Exploring High-dimensional Search Space via Voronoi Graph Traversing %A Aidong Zhao %A Xuyang Zhao %A Tianchen Gu %A Zhaori Bi %A Xinwei Sun %A Changhao Yan %A Fan Yang %A Dian Zhou %A Xuan Zeng %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-zhao24a %I PMLR %P 4219--4236 %U https://proceedings.mlr.press/v244/zhao24a.html %V 244 %X Bayesian optimization (BO) is a well-established methodology for optimizing costly black-box functions. However, the sparse observations in the high-dimensional search space pose challenges in constructing reliable Gaussian Process (GP) models, which leads to blind exploration of the search space. We propose a novel Voronoi Graph Traversing (VGT) algorithm to extend BO to ultra high-dimensional problems. VGT employs a Voronoi diagram to mesh the design space and transform it into an undirected Voronoi graph. VGT explores the search space by iteratively performing path selection, promising cell sampling, and graph expansion operations. We introduce a UCB-based global traversal strategy to select the path towards promising Voronoi cells. Then we perform local BO within the promising cell and train local GP with a neighboring subset. The intrinsic geometric boundaries and adjacency of the Voronoi graph assist in fine-tuning the trajectory of local BO sampling. We also present a subspace enhancement approach for the intrinsic low-dimensional problems. Experimental results, including both synthetic benchmarks and real-world applications, demonstrate the proposed approach’s state-of-the-art performance for tackling ultra high-dimensional problems ranging from hundreds to one thousand dimensions.
APA
Zhao, A., Zhao, X., Gu, T., Bi, Z., Sun, X., Yan, C., Yang, F., Zhou, D. & Zeng, X.. (2024). Exploring High-dimensional Search Space via Voronoi Graph Traversing. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:4219-4236 Available from https://proceedings.mlr.press/v244/zhao24a.html.

Related Material