StoBO: Scaling Batch Bayesian Optimization to High Dimensions through Causal Discovery

In this work, we develop a unified framework for high-dimensional Bayesian optimization in settings where the optimization variables are causally related but with unknown causal structure. We exploit the synergy between stochastic (hard) interventions in causal discovery and batch Bayesian optimization to design a stochastic Bayesian optimization algorithm that simultaneously targets two goals: efficient black-box optimization and causal structure learning. To guide intervention selection, we develop a gradient-based acquisition function that exploits regions with large expected gradient magnitude while exploring regions with high gradient uncertainty. After each intervention batch, we perform independence tests to update the estimated causal structure. Unlike traditional causal discovery methods, our approach relies only on marginal, rather than conditional, independence tests, and is therefore more sample-efficient. We derive both the asymptotic behavior and non-asymptotic error bounds of the test statistic. Experiments on a broad collection of synthetic benchmark functions and real-world optimization problems demonstrate that StoBO achieves competitive optimization performance while accurately recovering causal parent variables in high-dimensional settings.