- 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:
-
"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 -s may spill over to other variables that are not parents of . The authors later take 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.
-
"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 and where Z and U_0 are independent, the first one is uniform the other one is Gaussian and . 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 but the acquisition function is defined based on the derivatives of its noise-averaged mean , 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.
-
"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
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 as -strong marginal faithfulness. …" The second part (lines 927-991) proved Theorem 1 using this -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 -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 to .
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 . Ours sums only the batch-matched pairs .
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 fixed and . Under the assumption that each batch’s design parameter converges in probability to we couple each batch with a batch generated from the same innovations under the deterministic design , 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 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: fixed, , and an average conditional dependence signal bounded away from zero. Under these conditions, the test has asymptotic size 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.
Response to Question 1: parent recovery across runs
In Table 1, StoBO stops when the estimated parent sets from two consecutive batches are identical. The second column of Table 1 reports the average number of batches needed to meet this stopping criterion, and the last column reports the number of true parents detected after 10 further batches (). 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 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 at which the estimated parent set contains all true parents (mean ± standard deviation over the 100 runs). Complete recovery at does not mean that StoBO stops there. A true parent may drop out of in a later batch, so that 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.
| Function | Batches to complete recovery () |
|---|---|
| Michalewicz | 25.69 ± 7.19 |
| Hartmann6 | 5.40 ± 4.29 |
| Ackley | 5.71 ± 1.58 |
| Rastrigin | 6.71 ± 1.69 |
| Levy | 12.88 ± 7.07 |
| Griewank | 3.17 ± 0.74 |
| Rosenbrock | 5.61 ± 4.53 |
| Dixon-Price | 8.76 ± 6.72 |
| Powell | 3.86 ± 1.39 |
| Styblinski-Tang | 6.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 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 . Since true parents can be detected early but may later drop out, a natural remedy is a stopping rule based on the union of over recent batches. We will discuss this limitation and the proposed remedy in the appendix.
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 ∣π∣ 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 X0. 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:
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.