Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings

Aryan Deshwal, Sebastian Ament, Maximilian Balandat, Eytan Bakshy, Janardhan Rao Doppa, David Eriksson
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:7021-7039, 2023.

Abstract

We consider the problem of optimizing expensive black-box functions over high-dimensional combinatorial spaces which arises in many science, engineering, and ML applications. We use Bayesian Optimization (BO) and propose a novel surrogate modeling approach for efficiently handling a large number of binary and categorical parameters. The key idea is to select a number of discrete structures from the input space (the dictionary) and use them to define an ordinal embedding for high-dimensional combinatorial structures. This allows us to use existing Gaussian process models for continuous spaces. We develop a principled approach based on binary wavelets to construct dictionaries for binary spaces, and propose a randomized construction method that generalizes to categorical spaces. We provide theoretical justification to support the effectiveness of the dictionary-based embeddings. Our experiments on diverse real-world benchmarks demonstrate the effectiveness of our proposed surrogate modeling approach over state-of-the-art BO methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-deshwal23a, title = {Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings}, author = {Deshwal, Aryan and Ament, Sebastian and Balandat, Maximilian and Bakshy, Eytan and Doppa, Janardhan Rao and Eriksson, David}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {7021--7039}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/deshwal23a/deshwal23a.pdf}, url = {https://proceedings.mlr.press/v206/deshwal23a.html}, abstract = {We consider the problem of optimizing expensive black-box functions over high-dimensional combinatorial spaces which arises in many science, engineering, and ML applications. We use Bayesian Optimization (BO) and propose a novel surrogate modeling approach for efficiently handling a large number of binary and categorical parameters. The key idea is to select a number of discrete structures from the input space (the dictionary) and use them to define an ordinal embedding for high-dimensional combinatorial structures. This allows us to use existing Gaussian process models for continuous spaces. We develop a principled approach based on binary wavelets to construct dictionaries for binary spaces, and propose a randomized construction method that generalizes to categorical spaces. We provide theoretical justification to support the effectiveness of the dictionary-based embeddings. Our experiments on diverse real-world benchmarks demonstrate the effectiveness of our proposed surrogate modeling approach over state-of-the-art BO methods.} }
Endnote
%0 Conference Paper %T Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings %A Aryan Deshwal %A Sebastian Ament %A Maximilian Balandat %A Eytan Bakshy %A Janardhan Rao Doppa %A David Eriksson %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-deshwal23a %I PMLR %P 7021--7039 %U https://proceedings.mlr.press/v206/deshwal23a.html %V 206 %X We consider the problem of optimizing expensive black-box functions over high-dimensional combinatorial spaces which arises in many science, engineering, and ML applications. We use Bayesian Optimization (BO) and propose a novel surrogate modeling approach for efficiently handling a large number of binary and categorical parameters. The key idea is to select a number of discrete structures from the input space (the dictionary) and use them to define an ordinal embedding for high-dimensional combinatorial structures. This allows us to use existing Gaussian process models for continuous spaces. We develop a principled approach based on binary wavelets to construct dictionaries for binary spaces, and propose a randomized construction method that generalizes to categorical spaces. We provide theoretical justification to support the effectiveness of the dictionary-based embeddings. Our experiments on diverse real-world benchmarks demonstrate the effectiveness of our proposed surrogate modeling approach over state-of-the-art BO methods.
APA
Deshwal, A., Ament, S., Balandat, M., Bakshy, E., Doppa, J.R. & Eriksson, D.. (2023). Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:7021-7039 Available from https://proceedings.mlr.press/v206/deshwal23a.html.

Related Material