acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
batch Bayesian optimization, causal discovery, high-dimension optimization, independence test

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_CcfFOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper presents StoBO, a method to jointly learn the parental set of a target random variable and the best interventional values for those parents in a Markov causal model. The method introduces a new objective whose optimization intended to increase the statistical power of the independence test utilized in identifying the parents.

Critical strengths

The idea of optimizing an acquisition function such that it assists the independence test subroutine in parent discovery is interesting.

Critical weaknesses

I would like to start from the paper's motivation. Indeed, when the functions are causally dependent the standard BO can be suboptimal, the authors are missing a citation to the nominal paper [1], but in the Markovian causal model considered in the paper, i.e. in the absence of unobserved cofounders, this is false [1]. The experiments of the paper, in Table 2, show that standard BO achieves better performance than other methods. Secondly, the initial discussion that some variables may not be controlled is not relevant to this paper as it assumes, in Algorithm 1, that all can be controlled. If some variables were to be considered as purely observational, then after marginalisation of these variables the model does not have to stay Markovian [2]. If these variables were to be considered as contextual then one must consider the regime in [3].

However, this is comparably minor remark than the critical errors present in the paper. The authors list three contributions in Introduction:

  1. "A synergistic intervention principle" provided by Property 1. With current formulation property 1 is wrong. For a fixed-value intervention, every intervened input is constant and hence independent of the target. Whenever the target has a parent, this contradicts faithfulness to the stated mutilated graph. Thus, the faithfulness premise cannot hold in the nontrivial atomic case, and the claim that Property 1 applies to atomic interventions is untenable. For stochastic interventions it also remains incorrect, as dependence between WW-s may spill over to other variables that are not parents of X0X_0. The authors later take WW to be mutually independent. But a valid stochastic formulation should explicitly assume mutually independent, non-degenerate intervention assignments, independent of the outcome noise, and faithfulness of the resulting randomized interventional law. The authors also conflict the definition of mutual independence with that of pairwise independence on page 5. The optimality of intervening on the parent set is already established in [1]. The additional marginal-independence characterization follows immediately from graph surgery and post-interventional faithfulness, so its independent theoretical contribution appears limited.

  2. "A dual-purpose intervention principle" claims that the gradient-guided acquisition function empowers the independence test which is justified by Theorem 1. The proof of Theorem 1 is wrong. The local derivative and probability-mass conditions do not apply the uniform lower bound on the marginal dependence claim in the paper. For example, please consider X1=a∗ZX_1=a*Z and X0=X1+U0X_0=X_1+U_0 where Z and U_0 are independent, the first one is uniform the other one is Gaussian and a>0a>0. The fixed derivative and region-bound bounds are satisfied but its covariance distance tends to 0, invalidation the positive infimum argument. The finite-sample proof switches from the original biased estimator from Section 4 to an unbiased estimator and incorrectly treats sample-centered distance products as a two-observation U-statistic kernel. Moreover, the theorem considers the derivative of f0f_0 but the acquisition function is defined based on the derivatives of its noise-averaged mean gg, and there is no relationship established between them. This invalidates the claimed theoretical justification for the acquisition function; the criterion remains a heuristic whose benefit requires separate validation.

  3. "An independence test for heterogeneous batches". The test developed in the paper is a direct aggregation of Szekely et. al. 2014 and by itself is not novel (see also Zhu et. al. 2020), as the Property 2 given in the paper which is a direct consequence of Theorem 5 of Székely et. al. 2007. However, the proof assume that the batch statistics are mutually independent because they are computed from independent batches but StoBO chooses the next intervention distribution adaptively, based on the fitted acquisition functions. The proof of Property 3 is incorrect. On page 17, it confuses an all-pairs aggregate of sample distance covariances with the diagonal-only aggregate by setting cross-coordinate terms to zero under independence. Independence makes the population distance covariance zero, but not the sample estimate. Therefore, the transfer of the cited power results to the proposed statistic is invalid. Moreover, Property 3 does not specify the asymptotic regime or alternative class for a power comparison, and it does not establish the separate claim that power increases with the number of batches.

The core theoretical guarantees are not established, the applicability of Property 1 to atomic interventions is untenable, the proof of Theorem 1 fails to justify the proposed connection between gradients and test power, and the heterogeneous-batch analysis contains an unjustified independence assumption and an incorrect sample-level equality. The novelty of the elementary intervention and aggregation arguments is insufficiently distinguished from prior work. These issues affect the paper’s central justification and I therefore recommend rejection.

[1] Structural Causal Bandits: Where to Intervene?; Sanghack Lee et. al.; NeurIPS 2018 [2] Causal Bayesian Optimization; Virginia Aglietti et. al.; AISTATS 2020 [3] Contextual causal Bayesian optimisation; Arsenyan et. al.; ICLR 2026

Questions for authors

In Table 1, we see that the method does not always identify all the true parents of the target variable. This can be catastrophic as the method may not be able to attain the optimum even under the usual smoothness assumptions employed in the BO literature, resulting in the linear regret [3]. Q: How long does it take for the proposed method to identify all the parents, does it identify it in all runs? If not what percent of the runs does not completely identify the parental set.

In Table 2, the method lags behind the standard BO for all the experiments, which is not entirely expected as the standard BO performs optimizatin on a higher dimensional space and may suffer from the curse of dimensionality, yet it outperforms on the same horizon. Q: How much of the runtime advantage comes from batching and less frequent surrogate updates, rather than from parent discovery or the proposed acquisition function? Does the advantage remain against Standard BO with the same batch size and update frequency, and how do the methods compare in objective value versus wall-clock time?

Overall, I fail to see the benefits of this method on the given experiments. I would suggest the authors to state the empirical benefit of the method more clearly.

6 comments
AuthorsOpenReview ↗

Response to critical weaknesses

We thank the reviewer for the careful and detailed reading. Several comments identified gaps in the original proofs, and we have revised the theoretical analysis in response. We have uploaded a revised manuscript containing only these theoretical revisions, with all changes highlighted in red. We address each point in turn below (all line numbers refer to the original version).

Response to motivation

We agree with the reviewer and thanks for pointing us to Lee & Bareinboim (2018), which we will cite. By “suboptimal”, we did not mean that standard BO converges to a worse optimum. We meant that it searches a d-dimensional space when the objective depends only on ∣π∣|\pi| coordinates, which reduces sample efficiency and increases per-iteration cost. This is consistent with Table 2, where standard BO attains the best objective values, but at a substantially higher computational cost (Table 7).

StoBO is a batch method and is not intended to outperform sequential methods that update the surrogate after every evaluation. Like other batch BO methods, it targets settings where: (i) evaluations can be run in parallel batches, so the relevant cost is the number of rounds rather than the number of evaluations; (ii) surrogate-update cost matters; and (iii) identifying the influential variables is itself a goal. Standard BO needs 1000 sequential rounds for 1000 evaluations, while StoBO needs 20.

Response to non-controllable variables

We discussed the non-intervenable case in the Limitations section (Appendix G). There we showed that Property 1 continues to hold when the non-intervenable variables are root variables, or more generally when the post-intervention graph remains star-shaped into X0X_0. We agree that the examples of non-controllable variables in the introduction do not match the setting of Algorithm 1. We will revise the introduction. We will also include our response to Reviewer JSjS (Question 5) into the revised version.

Response to Contribution 1 (Property 1)

We would like to clarify that we did not claim Property 1 itself as a novel theoretical result. As the reviewer notes, it follows directly from graph surgery and post-interventional faithfulness. The contribution listed in our introduction is the synergistic intervention principle that Property 1 makes explicit: the queries of BO can be recast as stochastic interventions, so that the same evaluations serve both objectives. This observation is what motivates the design of StoBO: the dual-purpose batch acquisition strategy and the independence test for heterogeneous batches.

Atomic intervention. The reviewer is correct about the atomic interventions. We will delete that sentence in lines 214-215. We would like to note that Property 1 is only used by StoBO in the stochastic setting, so this correction does not affect the algorithm or any results.

Stochastic intervention. For stochastic interventions, the result holds under conditions that are satisfied by our design:

  • mutual independence of the WjW_j is required on page 5 (line 218), and the Remark in Appendix B (lines 833-839) discusses exactly the spillover issue raised by the reviewer;
  • non-degeneracy follows from the Gaussian intervention distribution with σ>0\sigma > 0;
  • independence from U0U_0 holds because interventions are sampled before the function is evaluated. In addition, our definition of faithfulness in Section 2 requires a one-to-one correspondence between independences and d-separations. Since the intervened inputs have no edges among them in the post-intervention graph, this already rules out dependence among them. Nevertheless, we agree that these conditions should be part of the statement itself, and we will restate Property 1.

Pairwise independence. We thank the reviewer for pointing out this error and apologize for the oversight. On pages 3 and 5, the intended condition is mutual independence, as stated in words, but the accompanying formulas express only pairwise independence. We will correct both formulas. None of our proofs rely on the pairwise formulation, and the algorithm and experimental results remain unaffected.

AuthorsOpenReview ↗

Response to critical weaknesses (cont.)

Response to Contribution 2 (Theorem 1)

Theorem 1. We thank the reviewer for carefully examining Theorem 1 and apologize for the lack of clarity in the original presentation. The original proof section (Appendix C) combined two distinct parts. The first part (lines 884-926) motivated the gradient-guided acquisition by explaining why we need to select points with large gradients. It concluded with the statement (lines 924-926): "In line with Zhang & Spirtes (2002), we here interpret the inequality dCov(X1b∗,X0b∗)≥λ>0\text{dCov}(X_1^{b^{\ast}}, X_0^{b^{\ast}})\ge \lambda>0 as λ\lambda-strong marginal faithfulness. …" The second part (lines 927-991) proved Theorem 1 using this λ\lambda-strong marginal faithfulness assumption; it did not rely on the regularity conditions presented in the text box. In the uploaded revised manuscript, we have separated the acquisition motivation from the theorem's proof into two sections.

We have also refined the statement of Theorem 1 (replacing the regularity conditions with the λ\lambda-strong marginal faithfulness assumption) and corrected the description of the U-statistic kernel to specify that it is of order four. The sample-size lower bound has been updated from cK2λj2log⁡(1α)c \frac{K^2}{\lambda_j^2}\log(\frac{1}{\alpha}) to cK2λj2log⁡(2α)c \frac{K^2}{\lambda_j^2}\log(\frac{2}{\alpha}).

Biased vs. unbiased estimator. We noted in our proof that we analyze the unbiased estimator of Székely & Rizzo (2014), and that Section 4 uses the original estimator. We also noted in Section 4 that the two yield very similar type-I error and power in our simulations. This is expected in our setting: each per-batch test involves scalar variables, whereas the bias of the original estimator that motivated the unbiased version (Székely & Rizzo, 2013) is a high-dimensional phenomenon.

Gradient-guided acquisition. We respectfully note that the paper presents the gradient-guided acquisition as motivated by Theorem 1 (lines 269-274), rather than derived from it, in the same sense that standard acquisition functions are theoretically motivated heuristics. This motivation remains valid under the corrected theory.

Response to Contribution 3

Novelty. We agree that the test builds on prior work, and the manuscript says so in several places (Section 4; Conclusion; Appendix B, where Property 2 is attributed to Theorem 5 of Székely et al., 2007). Our contribution is not the statistic itself. It is the analysis under adaptive, heterogeneous batches (lines 94-96, third contribution), where the per-batch statistics are neither identically distributed nor independent. Regarding Zhu et al. (2020), their aggregate sums distance covariances over all coordinate pairs (i,k)(i, k). Ours sums only the tt batch-matched pairs (Xjb,X0b)(X_j^b, X_0^b).

Property 2. The reviewer is right that the original proof assumed mutually independent batch statistics, which StoBO’s adaptive design violates. The revised proof treats the adaptive case separately, with tt fixed and m→∞m \to \infty. Under the assumption that each batch’s design parameter θb\theta_b converges in probability to θb∗\theta_b^{\ast} we couple each batch with a batch generated from the same innovations under the deterministic design θb∗\theta_b^*, which falls under the non-adaptive case. We then show that the difference between the two statistics vanishes in probability.

Property 3. We agree that the original proof incorrectly transferred power results for the all-pairs aggregate to our batch-matched statistic. The revised proof makes no such transfer. It establishes the result directly for the coordinate-wise statistic, which under H0H_0 is a sum of martingale differences. The proof applies the martingale central limit theorem with studentization by within-batch permutation variances. The regime and alternative class are now explicit: mm fixed, t→∞t \to \infty, and an average conditional dependence signal bounded away from zero. Under these conditions, the test has asymptotic size α\alpha and asymptotic power one. Ramdas et al. (2015) and Zhu et al. (2020) are now cited only as motivation.

We thank the reviewer for these comments, which substantially improved the rigour of our analysis. These revisions concern only the theoretical analysis: the algorithm, the permutation test used in practice, and all experimental results remain unchanged.

AuthorsOpenReview ↗

Response to Question 1: parent recovery across runs

In Table 1, StoBO stops when the estimated parent sets π^\hat{\pi} from two consecutive batches are identical. The second column of Table 1 reports the average number of batches tt needed to meet this stopping criterion, and the last column reports the number of true parents detected after 10 further batches (t+10t+10). Each experiment is repeated 100 times.

Does StoBO identify all parents in every run? For five of the ten functions (Ackley, Rastrigin, Griewank, Powell and Styblinski-Tang), yes. The last column of Table 1 shows that all true parents are detected by t+10t+10 in every run, with zero standard deviation. For the other five functions, complete recovery is not achieved in every run within this budget.

How long does it take? The table below reports the first batch b∗b^{\ast} at which the estimated parent set contains all true parents (mean ± standard deviation over the 100 runs). Complete recovery at b∗b^{\ast} does not mean that StoBO stops there. A true parent may drop out of π^\hat{\pi} in a later batch, so that π^b∗+1≠π^b∗\hat{\pi}_{b^{\ast}+1} \neq \hat{\pi}_{b^{\ast}} and the run continues. For this reason, some runs on Hartmann6, Rosenbrock and Dixon-Price recover all parents early yet stop with an incomplete set.

FunctionBatches to complete recovery (b∗b^*)
Michalewicz25.69 ± 7.19
Hartmann65.40 ± 4.29
Ackley5.71 ± 1.58
Rastrigin6.71 ± 1.69
Levy12.88 ± 7.07
Griewank3.17 ± 0.74
Rosenbrock5.61 ± 4.53
Dixon-Price8.76 ± 6.72
Powell3.86 ± 1.39
Styblinski-Tang6.29 ± 1.47

We believe that recovery depends mainly on how each parent enters the objective:

  • Consistent contributions. Ackley, Rastrigin, Griewank, Powell and Styblinski-Tang have broad or regularly structured landscapes in which every coordinate contributes consistently to the output. Stochastic perturbations of each parent therefore produce distinct, repeatable effects that are easy to detect.
  • Localised informative regions. Michalewicz and Hartmann6 have narrow informative regions, which local batches may miss.
  • Masked effects. In Levy, Rosenbrock and Dixon-Price, some coordinates appear in fewer terms or enter at a lower polynomial order, so their marginal effects can be masked by the other inputs.

The missed parents are also highly consistent across runs and tend to have weak marginal effects on the response. For example, Hartmann6 reaches a 2.2% optimality gap even though, on average, 0.79 true parents are missed at stopping (Table 1).

Linear regret. We agree that permanently omitting a true parent can lead to linear regret. During parent discovery, however, StoBO does not permanently exclude unselected variables:

  • Their sampling locations maximise the posterior expected absolute derivative. This criterion accounts for derivative uncertainty, so these variables continue to be explored.
  • Each new batch updates the full-dimensional GP and repeats the independence tests, so a parent missed early can still enter π^t\hat{\pi}_t later (Figure 4).

A temporary omission therefore does not by itself imply linear regret. The risk remains once parent discovery stops and the optimization is restricted to π^\hat{\pi}. Since true parents can be detected early but may later drop out, a natural remedy is a stopping rule based on the union of π^\hat{\pi} over recent batches. We will discuss this limitation and the proposed remedy in the appendix.

Reviewer_jgpnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes StoBO, which combines high-dimensional batch Bayesian optimization with the identification of direct causal parents of the objective variable. The method applies mutually independent random interventions to all inputs and updates the parent-variable estimates by accumulating distance covariance statistics across batches. For the identified parent variables, standard BO acquisition functions are used, while for the remaining variables, exploration is guided by the expected absolute gradient under the GP posterior. The paper provides asymptotic and non-asymptotic analyses of the associated independence test, and evaluates optimization performance, variable identification, and computational efficiency on ten synthetic benchmarks and five real-world application problems.

Critical strengths

1.The method explicitly balances improving the objective with collecting information about potentially overlooked parent variables. The synthetic experiments show substantial dimensionality reduction while retaining many true parents on several benchmarks, and report cases where parent recovery remains difficult. This makes the approach potentially useful when identifying influential variables matters alongside finding a good objective value.

Critical weaknesses

1.Algorithm 1 chooses each new intervention center using previous observations, whereas Section 4 and the proof of Property 2 use cross-batch independence to justify the aggregated statistic. Independent random draws within each batch do not by themselves imply independence across adaptively chosen batches. The paper does not explain how this history dependence is handled in the theoretical analysis or the cumulative permutation test. This leaves an important gap between the proposed algorithm and its claimed statistical guarantees, although it does not by itself establish that the empirical procedure fails.

2.Appendix F.3 runs all comparison methods sequentially, whereas StoBO uses batches. Consequently, the runtime comparison does not distinguish benefits of the proposed discovery and acquisition mechanisms from those of less frequent model updates. Moreover, Table 5 removes the conventional optimization block B2, rather than directly testing the new gradient-guided block B3 against a simpler exploration strategy. Batch-matched comparisons and a targeted B3 ablation would help establish what the method adds beyond batching and variable screening.

Questions for authors

1.How is the dependence induced by adaptive intervention centers handled in Property 2 and the cumulative permutation test? Can the claimed guarantees be justified conditional on the sampling history?

2.Can you provide comparisons with batch BO baselines using the same batch size and function-evaluation budget, reporting both optimization performance and runtime?

3.What happens to parent recovery and optimization performance when B3 is replaced by random exploration of the currently unselected variables, with the remaining components unchanged?

3 comments
AuthorsOpenReview ↗

Response to W1 and Q1: cross-batch dependence

We thank the reviewer for this important question. Reviewer CcfF also identified gaps in the original proofs, and we have revised the theoretical analysis in response. We have uploaded a revised manuscript containing only these theoretical revisions, with all changes highlighted in red. These revisions concern only the theoretical analysis; the algorithm, the permutation test used in practice and all experimental results remain unchanged.

Conditional null hypothesis. Conditional on B1:b−1\mathcal B_{1:b-1}, the batch-bb design θb=(ub,σ)\theta_b=(u_b, \sigma) is fixed. The interventions are then drawn i.i.d. from N(ub,diag(σ2))\mathcal N (u_b, \text{diag}(\sigma^2)), with mutually independent components that are independent of the outcome noise. Property 1 therefore applies within every batch, conditionally on the history. The null hypothesis is accordingly stated conditionally: Xjb⊥⊥X0b∣B1:b−1X_j^b \mathrel{\perp\mkern-10mu\perp} X_0^b \mid \mathcal B_{1:b-1} for all bb, which holds if and only if Xj∉pa(X0)X_j \notin pa(X_0).

Property 2 (fixed tt, m→∞m \to \infty). The revised proof treats the adaptive case explicitly, conditionally on the initial design. Assuming each design parameter converges, θb→pθb∗\theta_b \xrightarrow{p} \theta_b^{\ast} with m→∞m \to \infty, we couple each batch with a batch generated from the same innovations under the deterministic design θb∗\theta_b^{\ast}; the coupled statistics fall under the non-adaptive case. Conditionally on the history, we bound E[(Db,m−Db,m∗)2∣B1:b−1]≤4Δb(θb)→p0\text{E}[(\sqrt{D_{b,m}} - \sqrt{D^*_{b,m}})^2 \mid \mathcal B_{1:b-1}] \le 4\Delta_b(\theta_b) \xrightarrow{p} 0. The limiting distribution of the aggregated statistic then follows from Slutsky's lemma, under two stated regularity conditions (R1-R2).

Property 3 (fixed mm, t→∞t \to \infty). Under the conditional null, the unbiased per-batch statistics DbD_b satisfy E[Db∣B1:b−1]=0\text{E}[D_b \mid \mathcal{B}_{1:b-1}] = 0, so ∑bDb\sum_b D_b is a martingale with respect to the filtration generated by the batches. No cross-batch independence is needed. The martingale central limit theorem, combined with studentization by the within-batch permutation variances, gives asymptotic size α\alpha. Asymptotic power one holds when the average conditional dependence signal is bounded away from zero.

Cumulative permutation test. Permutations are performed within each batch, so each batch's permutation distribution is valid conditionally on its history. We do not claim exact finite-sample validity for the cumulative permutation test under adaptive sampling. Permuting responses in an earlier batch would, in principle, have changed the later designs. Its theoretical justification is asymptotic, through the studentized test of Property 3, whose variance estimate is computed from the same within-batch permutations. We will state this distinction explicitly in Section 4.

AuthorsOpenReview ↗

Response to W2, Q2 and Q3: ablation of Block 3 and batch-matched comparison

We thank the reviewer for this suggestion. We here provide the B3 ablation study. The batch-matched comparison study is provided in our response to Reviewer CcfF (Question 2).

We compare full StoBO with two variants that replace B3 only:

  • Random mean: the intervention mean for the non-parents is randomly drawn from the domain.
  • Full-domain UCB: the intervention mean is chosen by maximizing UCB over all coordinates.

Each run uses 50 initial evaluations followed by 14 batches of m=50m = 50, for a total of 750 evaluations, and results are averaged over 20 seeds. "Final FN" is the number of missed parents after the last batch. "Average FN" is the number of missed parents averaged over all batches, so it reflects how quickly parents are discovered.

Table R5: Missed true parents (FN) under StoBO, random, and full-domain UCB. Mean ± std over 20 seeds, 750 evaluations; bold marks the lowest average FN.

Test functionFinal FN: StoBOFinal FN: RandomFinal FN: UCBAvg. FN: StoBOAvg. FN: RandomAvg. FN: UCB
Ackley0.00 ± 0.000.00 ± 0.000.00 ± 0.001.11 ± 0.511.27 ± 0.761.27 ± 0.56
Dixon-Price1.00 ± 0.000.95 ± 0.391.10 ± 0.451.30 ± 0.201.37 ± 0.251.62 ± 0.38
Griewank0.00 ± 0.000.00 ± 0.000.00 ± 0.000.39 ± 0.160.47 ± 0.210.61 ± 0.28
Hartmann60.85 ± 0.880.65 ± 0.880.80 ± 0.831.22 ± 0.711.21 ± 0.671.17 ± 0.61
Levy0.80 ± 0.410.85 ± 0.370.70 ± 0.471.29 ± 0.301.40 ± 0.361.44 ± 0.26
Michalewicz2.05 ± 0.762.55 ± 0.602.65 ± 0.933.10 ± 0.723.22 ± 0.563.40 ± 0.54
Powell0.00 ± 0.000.05 ± 0.220.00 ± 0.000.45 ± 0.230.51 ± 0.290.77 ± 0.44
Rastrigin0.00 ± 0.000.00 ± 0.000.35 ± 0.671.13 ± 0.491.29 ± 0.511.94 ± 0.66
Rosenbrock0.65 ± 0.490.75 ± 0.440.85 ± 0.370.82 ± 0.330.90 ± 0.240.99 ± 0.21
Styblinski-Tang0.00 ± 0.000.00 ± 0.000.00 ± 0.000.96 ± 0.290.98 ± 0.371.26 ± 0.33

Table R6: Number of variables selected as parents (TP+FP) after the final batch under the same three placements. Mean ± std over 20 seeds, 750 evaluations.

Test functionTP+FP: StoBOTP+FP: RandomTP+FP: UCB
Ackley9.05 ± 1.549.55 ± 2.289.95 ± 2.24
Dixon-Price8.50 ± 1.578.85 ± 1.738.70 ± 2.08
Griewank9.50 ± 1.509.75 ± 1.779.80 ± 1.74
Hartmann69.90 ± 1.6510.30 ± 2.649.70 ± 2.49
Levy8.85 ± 2.508.85 ± 1.7310.05 ± 2.09
Michalewicz9.10 ± 1.659.20 ± 2.678.60 ± 3.66
Powell9.65 ± 1.669.00 ± 2.329.50 ± 1.79
Rastrigin10.95 ± 2.8610.70 ± 2.8310.80 ± 1.96
Rosenbrock9.60 ± 2.419.20 ± 2.339.30 ± 2.36
Styblinski-Tang9.85 ± 2.609.15 ± 2.069.65 ± 2.96

Tables R5 and R6 show that:

  • Average FN. Full StoBO attains the lowest average FN on 9 of the 10 functions against both alternatives. Hartmann6 is the exception, where the three variants are essentially tied. Under a one-sided sign test across functions, a 9-of-10 outcome has p≈0.011p \approx 0.011 for each comparison.
  • Final FN. Differences are smaller, because all variants eventually recover the easy parents. Full StoBO is better than or equal to random means on 8 of 10 functions and than UCB on 8 of 10 functions. The clearest gains are on Michalewicz, the hardest function for discovery.
  • Selected-set size. TP+FP is comparable across variants, so the gains in FN do not come from selecting more variables.

Trajectory. We also visualized how the FN changes from batch to batch for the three variants (cannot insert in the rebuttal here, will inlcude in the revised version). Full StoBO's curve drops fastest during the early-to-middle batches (roughly batches 2-7), with the clearest separation on Ackley, Griewank, Dixon-Price and Rastrigin. The variants then converge towards the same final level on most functions. Full-domain UCB is consistently the slowest: on Rastrigin, Powell, Griewank and Styblinski-Tang it trails by several batches. This is because maximizing UCB pulls the non-parent samples towards the optimum and reduces their spread, which weakens the independence tests. Random means are a stronger baseline and stay close to StoBO on Powell and Styblinski-Tang, which shows that spreading the samples alone already helps, and the gradient guidance adds a further, consistent gain. Michalewicz is the exception: there StoBO's advantage only appears after about batch 6, then keeps growing, and its curve is still falling at batch 14. On Dixon-Price, Hartmann6, Levy and Rosenbrock, all three variants level off at the same non-zero FN. This suggests that the parents missed there have weak marginal signals that no choice of sampling location can recover, which is a limitation of marginal testing rather than of Block 3.

Thank you for your response and clarifications. My concerns have been addressed.

Reviewer_JSjSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The manuscript proposes StoBO, a unified framework for high-dimensional Bayesian optimization (BO) where input variables are causally related but the causal structure is unknown. The authors exploit stochastic interventions to simultaneously optimize a black-box function and learn the causal graph. The core mechanism involves performing marginal independence tests on interventional data batches to identify direct parents of the target variable and reduce the optimization problem to a lower-dimensional subspace. To guide intervention selection, the authors develop a gradient-based acquisition function that targets regions with large expected gradient magnitude or high uncertainty for non-parent variables.

Critical strengths
  1. The manuscript effectively bridges Bayesian optimization and causal discovery, addressing a setting where both the data-generating mechanism and the DAG are unknown, which is more challenging than existing causal BO methods that assume known structures.

  2. Unlike traditional constraint-based causal discovery that relies on conditional independence tests, StoBO leverages Property 1 to reduce parent identification to marginal independence testing after intervening on all variables. This approach is theoretically justified and can offer improved sample efficiency.

  3. The design of the acquisition function specifically targets regions with high expected gradient magnitude or uncertainty for non-parent variables, providing a principled way to explore causal structure without relying solely on standard BO heuristics.

  4. By updating models only after every batch of observations rather than after each individual query, StoBO seems to achieve significant speedups over some selected state-of-the-art sequential methods. Table 7 shows StoBO is approximately 1.6 times faster than HeSBO and TuRBO-1, and over 20 times faster than Standard BO on the Ackley function.

Critical weaknesses
  1. The main text relies on qualitative descriptions such as trajectories converging to low objective values or "approaching the known global optimum." I did not see any explicit quantitative metrics reported for the causal discovery component, such as the percentage of correctly identified parents, F1 scores, or exact graph recovery rates in the main body.

  2. The results sections present mean trajectories and runtime averages over 20 random seeds but omit statistical significance tests (e.g., paired t-tests or Wilcoxon signed-rank tests) to determine if performance differences between StoBO and baselines are statistically significant. Visual overlap of trajectories in Figures 10 and 11 could be misleading without formal testing

  3. The manuscript claims efficiency gains stem from restricting optimization to direct parents, yet there is no ablation study where the causal discovery step (Block 1) is disabled or replaced with a random parent selection strategy. It is unclear how much of the performance gain is attributable specifically to accurate causal structure learning versus the batch mode itself.

  4. Section 4 introduces an independence test based on distance covariance but does not specify the thresholding mechanism used to decide between independence and dependence in the main text. The choice of significance level and the specific estimator details are deferred to Appendix D or implied by simulation results, making reproducibility difficult.

  5. The Limitations section admits that Property 1 may not hold generally if non-intervenable variables exist or induce backdoor paths, restricting validity to cases where non-intervenable variables are root nodes or the post-intervention graph is star-shaped. The manuscript would benefit from a more detailed discussion on how these constraints limit applicability in real-world scenarios where some variables cannot be intervened upon.

Questions for authors
  1. Can you provide specific quantitative metrics (e.g., F1 score, percentage of correctly identified parents) for the causal discovery component in both synthetic and real-world experiments? How does the accuracy of parent identification correlate with the final optimization performance across different benchmarks?
  2. Please include statistical significance tests (e.g., p-values or confidence intervals derived from paired t-tests or Wilcoxon signed-rank tests) for the comparisons shown in Figures 10 and 11 to validate the observed performance gaps against baselines.
  3. Could you add an ablation study comparing StoBO against a variant that uses a fixed, randomly selected subset of variables (or a standard variable selection method without causal discovery) to isolate the specific contribution of the independence testing and parent identification modules?
  4. In Section 4, please explicitly define the critical value threshold or p-value cutoff used to determine independence in the distance covariance test. Is this threshold fixed across all batches or adaptive?
  5. The Limitations section notes that non-intervenable variables can invalidate Property 1 unless they are root variables. Given that many real-world problems involve unobservable or uncontrollable confounders, how robust is StoBO in such settings, and what practical heuristics might be used to handle them?
6 comments
AuthorsOpenReview ↗

Response to W1 and Q1: quantitative metrics

We would like to clarify that Table 1 (columns 2-4, and column 6) and Table 2 (last row) both reported metrics related to parent discovery. Table 6 in Appendix F.3 further compares variable selection with LassoBO. We would also like to clarify that StoBO targets the parent set pa(X0)pa(X_0) of the response, not the full DAG. Exact recovery of the whole graph is therefore outside its scope.

Synthetic experiments. Using the results in Table 1 (at stopping, averaged over 100 runs), we computed recall (the percentage of true parents identified), precision, and F1. Here $ F1 = 2 TP /(k + TP + FP)$, where kk is the number of true parents.

Function (kk)RecallPrecisionF1FPGap (Table 1)
Michalewicz (5)50.4%29.7%0.375.9623.96%
Hartmann6 (6)86.8%55.2%0.684.222.20%
Ackley (5)96.2%49.7%0.664.871.15
Rastrigin (5)93.2%44.7%0.605.7616.39
Levy (5)83.2%46.5%0.604.791.23
Griewank (5)99.4%52.1%0.684.570.59
Rosenbrock (5)81.4%45.5%0.584.87817.40
Dixon-Price (5)78.4%46.3%0.584.54196.95
Powell (4)97.5%42.8%0.605.2121.35
Styblinski-Tang (5)95.4%49.2%0.654.934.90%

Recall exceeds 93% on five functions and 78% on all except Michalewicz. Precision is lower, around 45-55%. This is expected from the testing procedure: each of the d−k≈95d - k \approx 95 non-parents is tested at level α=0.05\alpha = 0.05, so about 0.05×95≈4.750.05 \times 95 \approx 4.75 false positives arise by chance alone. The observed FP counts (4.2-6.0) closely match this nominal type-I error rate. This is also consistent with Figure 5, where the number of selected variables grows linearly with dd. The false positives therefore reflect the per-variable significance level rather than a failure of the test. We favour recall because a missed parent is more harmful for optimization than a superfluous variable. Overall, StoBO reduces 100 candidate variables to about 9 while retaining most true parents.

Real-world experiments. The true parents are unknown for the real-world problems, so recall and precision cannot be computed. Table 2 instead reports the size of the selected set, which StoBO reduces to 12-23% of the input dimension:

  • DNA: 34.8 of 180;
  • Mazda: 44.3 of 222;
  • SVM: 46.9 of 388;
  • MOPTA08: 28.4 of 124;
  • CEC2020-38: 23.3 of 126.

These sizes are consistent with prior knowledge of these problems. For DNA, Šehić et al. (2022) estimated an effective dimensionality of about 43. CEC2020-38 has about 10 independent control degrees of freedom (Appendix F.3).

Correlation with optimization performance. Across functions, parent-recovery accuracy and the optimality gap are related but not perfectly aligned, because the gap also depends on how hard the reduced low-dimensional problem is.

  • Michalewicz has both the lowest recall (50.4%) and the largest relative gap (23.96%).
  • The high-recall functions Ackley, Griewank and Styblinski-Tang all reach small gaps.
  • Rastrigin and Powell have high recall but larger gaps, because their landscapes remain highly multimodal even in five dimensions.
  • Hartmann6 reaches a 2.2% gap despite a recall of 86.8%, which suggests that the missed parents have limited influence on the response.
AuthorsOpenReview ↗

Response to W2 and Q2: statistical significance tests

We thank the reviewer for this suggestion.

In Tables R2 and R3, we performed two-sided Wilcoxon signed-rank tests comparing StoBO with each baseline on the final best objective value (1000 evaluations; 500 for ALEBO and SAASBO, matching Figure 10). Runs are paired by random seed: the same seed gives the same problem instance and the same initial design for every method. A sign is shown when p < 0.05: (+) means StoBO is significantly better, (-) means the baseline is significantly better, and no sign means no significant difference. With 20 paired seeds, the smallest possible exact p-value is 2/220≈1.9×10−62/2^{20}\approx 1.9\times 10^{-6}. So p=0.000002 means one method was better on all 20 seeds.

Because we ran 110 tests, we also applied a Holm-Bonferroni correction (family-wise α\alpha = 0.05). Of the 83 comparisons significant at 0.05, 74 remain significant after correction. The 9 that drop out are those with 0.002 ≤\leq p ≤\leq 0.048: 4 favoured StoBO and 5 favoured the baseline. None of the conclusions below change.

Table R1 (summary of Tables R2 and R3): StoBO wins / no significant difference / losses against each baseline (uncorrected p < 0.05).

BaselineSyntheticReal-world
HeSBO9 / 1 / 05 / 0 / 0
GIT-BO7 / 2 / 14 / 0 / 1
ALEBO3 / 3 / 4-
Standard BO3 / 4 / 30 / 0 / 5
BAxUS1 / 4 / 51 / 1 / 3
SAASBO1 / 3 / 6-
TuRBO-11 / 3 / 61 / 2 / 2
LassoBO0 / 4 / 61 / 0 / 4
Total25 / 24 / 3112 / 3 / 15

Table R1 shows that:

  1. StoBO significantly outperforms the embedding-based methods HeSBO and GIT-BO on almost every problem, with only 2 losses.
  2. The strongest sequential methods (LassoBO, TuRBO-1, BAxUS, SAASBO, Standard BO) reach better final objective values on most problems.
  3. On Hartmann6, Levy and Rastrigin, StoBO is statistically indistinguishable from most strong baselines.

We think this is the expected trade-off of StoBO's design, not a weakness hidden by the trajectories. The sequential baselines refit their surrogate after every evaluation, about 1000 times. StoBO refits once per batch of m = 50, about 20 times, and it spends early batches on causal parent discovery as well as optimisation. In return, StoBO is 1.6x faster than TuRBO-1 and HeSBO, about 25x faster than Standard BO, and two to three orders of magnitude faster than BAxUS, SAASBO and ALEBO (Table 7). It also outputs an explicit set of causal parent variables, which none of the sequential baselines except LassoBO provide. StoBO is therefore best suited to settings where evaluations can run in parallel, wall-clock or surrogate-fitting cost matters, or identifying influential variables is a goal in itself.

Table R2. Wilcoxon signed-rank p-values on the synthetic test functions (StoBO vs. each baseline, final best objective value, 20 paired seeds).

FunctionALEBOBAxUSGIT-BOHeSBOLassoBOSAASBOStandard BOTuRBO-1
Ackley0.012079 (+)0.000002 (-)0.000010 (+)0.000002 (+)0.000002 (-)0.6215130.000002 (-)0.000002 (-)
Dixon-Price0.000002 (-)0.000002 (-)0.000002 (-)0.2610990.000002 (-)0.000063 (-)0.000002 (-)0.000002 (-)
Griewank0.000010 (+)0.000002 (-)0.000002 (+)0.000002 (+)0.0825500.000002 (-)0.7841260.000013 (-)
Hartmann60.0582580.3299830.000002 (+)0.000004 (+)0.8983170.7011810.2942520.956329
Levy0.0582580.3117940.1327270.000002 (+)0.1429060.000483 (+)0.1768530.784126
Michalewicz0.023951 (-)0.4090980.000019 (+)0.000036 (+)0.002325 (-)0.000322 (-)0.1649570.013617 (-)
Powell0.000168 (-)0.000134 (-)0.4304330.000006 (+)0.000134 (-)0.002712 (-)0.001209 (+)0.000134 (-)
Rastrigin0.0825500.4523750.003654 (+)0.000586 (+)0.1230930.4304330.001209 (-)0.430433
Rosenbrock0.000322 (-)0.000322 (-)0.007296 (+)0.000851 (+)0.000322 (-)0.000322 (-)0.048441 (+)0.001986 (-)
Styblinski-Tang0.000006 (+)0.000010 (+)0.000002 (+)0.000002 (+)0.000002 (-)0.000002 (-)0.000010 (+)0.000851 (+)

Table R3. p-values, real-world problems (StoBO vs. baselines).

ProblemBAxUSGIT-BOHeSBOLassoBOStandard BOTuRBO-1
CEC2020-380.000002 (-)0.000002 (-)0.000010 (+)0.000002 (-)0.000002 (-)0.000002 (-)
DNA0.000002 (-)0.000002 (+)0.000002 (+)0.000002 (-)0.000002 (-)0.000002 (-)
MOPTA080.000851 (-)0.000002 (+)0.000002 (+)0.000002 (-)0.000002 (-)0.075851
Mazda0.000002 (+)0.000002 (+)0.000002 (+)0.000002 (+)0.000002 (-)0.000002 (+)
SVM0.1768530.000002 (+)0.000002 (+)0.000002 (-)0.000002 (-)0.311794
AuthorsOpenReview ↗

Response to W3 and Q3: ablation of Block 1 (parent identification)

We thank the reviewer for this suggestion.

We added an ablation study in which Block 1 (the independence tests) is replaced by one of four alternative rules for choosing the "parent" set. Blocks 2-4 stay exactly as in StoBO. In particular, every variant uses the same batch mode (m = 50), so any difference between variants comes from which variables are chosen, not from batching.

  • Fixed random: 10 variables are chosen uniformly at random before the first batch and kept fixed throughout.
  • Dynamic random: 10 variables are re-sampled uniformly at random after every batch.
  • GP-ARD (a standard variable-selection method without causal discovery): after each batch, the 10 variables with the smallest learned ARD lengthscales in the Block 3 GP are treated as parents.
  • Oracle: the true parent set is used in every batch. This is an upper reference that cannot be achieved in practice.

Table R4: Final best objective value, mean (std) over 20 seeds after 750 evaluations (lower is better). Bold marks the best non-oracle method.

FunctionFull StoBOFixed randomDynamic randomGP-ARDOracle
Ackley0.514 (0.197)4.052 (2.346)2.492 (0.795)0.523 (0.251)0.324 (0.159)
Dixon-Price110.57 (92.73)852.57 (505.31)730.05 (533.27)146.47 (101.86)151.55 (74.62)
Griewank0.541 (0.270)1.707 (1.178)0.794 (0.200)0.688 (0.176)0.082 (0.047)
Hartmann6-3.255 (0.062)-3.232 (0.083)-3.245 (0.062)-3.262 (0.061)-3.275 (0.060)
Levy0.785 (0.437)3.129 (1.239)2.728 (1.392)1.325 (0.454)0.802 (0.320)
Michalewicz-3.599 (0.406)-3.282 (0.396)-3.447 (0.398)-3.840 (0.335)-4.163 (0.244)
Powell15.89 (10.46)33.30 (16.55)36.00 (19.28)12.31 (7.42)7.71 (6.18)
Rastrigin13.94 (3.69)19.88 (7.68)21.27 (6.33)13.53 (3.17)8.74 (2.77)
Rosenbrock506.63 (234.87)2793.79 (1154.99)2806.99 (1468.14)592.50 (466.69)399.20 (196.50)
Styblinski-Tang-190.03 (7.91)-184.04 (10.49)-184.07 (10.56)-189.98 (9.32)-192.17 (6.96)

Table R4 shows that

  1. Identifying the right variables, not batch mode, drives performance. All five variants share the same batch mode, yet random selection is much worse than StoBO. On the seven functions with a global minimum of zero, StoBO's final value is 1.4-8x lower than fixed random selection (e.g. Ackley 0.51 vs 4.05; Rosenbrock 507 vs 2794). Re-sampling the random set after each batch does not close this gap.
  2. StoBO's parent identification is close to the oracle. StoBO is within one standard deviation of the oracle on most functions and matches or beats it on Dixon-Price and Levy. The largest remaining gaps (Griewank, Michalewicz, Powell, Rastrigin) are on functions where Table 1 shows that StoBO occasionally misses a parent or keeps extra false positives.
  3. GP-ARD is competitive, and this is consistent with our theory. StoBO and GP-ARD each win on some functions (StoBO on 6, GP-ARD on 4), with most differences within one standard deviation. This is expected. Because StoBO intervenes on all inputs, only the direct parents of X0X_0 can affect the output, so any reasonable relevance score computed on these interventional data, including ARD lengthscales, targets the direct parents. The main contribution is therefore the intervention design. Given that design, the independence test offers three advantages over ARD ranking: (i) it does not need the number of parents in advance (GP-ARD was given k = 10, roughly double the true count, whereas StoBO chooses the set size from the data); (ii) each inclusion decision has a controlled type-I error rate, so the reported parent set has a statistical meaning that a lengthscale ranking does not; and (iii) it is non-parametric and does not depend on the GP being well specified, which matters because ARD lengthscales are known to be unreliable when data are scarce.

We will add this ablation to the appendix.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.