BARK: A Fully Bayesian Tree Kernel for Black-box Optimization

Toby Boyne, Jose Pablo Folch, Robert Matthew Lee, Behrang Shafei, Ruth Misener
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:5291-5318, 2025.

Abstract

We perform Bayesian optimization using a Gaussian process perspective on Bayesian Additive Regression Trees (BART). Our BART Kernel (BARK) uses tree agreement to define a posterior over piecewise-constant functions, and we explore the space of tree kernels using a Markov chain Monte Carlo approach. Where BART only samples functions, the resulting BARK model obtains samples of Gaussian processes defining distributions over functions, which allow us to build acquisition functions for Bayesian optimization. Our tree-based approach enables global optimization over the surrogate, even for mixed-feature spaces. Moreover, where many previous tree-based kernels provide uncertainty quantification over function values, our sampling scheme captures uncertainty over the tree structure itself. Our experiments show the strong performance of BARK on both synthetic and applied benchmarks, due to the combination of our fully Bayesian surrogate and the optimization procedure.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-boyne25a, title = {{BARK}: A Fully {B}ayesian Tree Kernel for Black-box Optimization}, author = {Boyne, Toby and Folch, Jose Pablo and Lee, Robert Matthew and Shafei, Behrang and Misener, Ruth}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {5291--5318}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/boyne25a/boyne25a.pdf}, url = {https://proceedings.mlr.press/v267/boyne25a.html}, abstract = {We perform Bayesian optimization using a Gaussian process perspective on Bayesian Additive Regression Trees (BART). Our BART Kernel (BARK) uses tree agreement to define a posterior over piecewise-constant functions, and we explore the space of tree kernels using a Markov chain Monte Carlo approach. Where BART only samples functions, the resulting BARK model obtains samples of Gaussian processes defining distributions over functions, which allow us to build acquisition functions for Bayesian optimization. Our tree-based approach enables global optimization over the surrogate, even for mixed-feature spaces. Moreover, where many previous tree-based kernels provide uncertainty quantification over function values, our sampling scheme captures uncertainty over the tree structure itself. Our experiments show the strong performance of BARK on both synthetic and applied benchmarks, due to the combination of our fully Bayesian surrogate and the optimization procedure.} }
Endnote
%0 Conference Paper %T BARK: A Fully Bayesian Tree Kernel for Black-box Optimization %A Toby Boyne %A Jose Pablo Folch %A Robert Matthew Lee %A Behrang Shafei %A Ruth Misener %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-boyne25a %I PMLR %P 5291--5318 %U https://proceedings.mlr.press/v267/boyne25a.html %V 267 %X We perform Bayesian optimization using a Gaussian process perspective on Bayesian Additive Regression Trees (BART). Our BART Kernel (BARK) uses tree agreement to define a posterior over piecewise-constant functions, and we explore the space of tree kernels using a Markov chain Monte Carlo approach. Where BART only samples functions, the resulting BARK model obtains samples of Gaussian processes defining distributions over functions, which allow us to build acquisition functions for Bayesian optimization. Our tree-based approach enables global optimization over the surrogate, even for mixed-feature spaces. Moreover, where many previous tree-based kernels provide uncertainty quantification over function values, our sampling scheme captures uncertainty over the tree structure itself. Our experiments show the strong performance of BARK on both synthetic and applied benchmarks, due to the combination of our fully Bayesian surrogate and the optimization procedure.
APA
Boyne, T., Folch, J.P., Lee, R.M., Shafei, B. & Misener, R.. (2025). BARK: A Fully Bayesian Tree Kernel for Black-box Optimization. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:5291-5318 Available from https://proceedings.mlr.press/v267/boyne25a.html.

Related Material