- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
In this paper, the authors study how to learn a linear-Gaussian causal model from scratch by choosing, one sample at a time, whether to observe the system passively or to intervene on a single variable, and when to stop. The goal is to return the true causal graph and edge weights that are all within ε of the truth, with probability at least , using as few samples as possible. The authors first derive an instance-dependent lower bound on the expected number of samples. They then propose FOCUS, which estimates the model by maximum likelihood, learns which interventions to use through an online max–min game (AdaHedge against a best-response alternative model), and stops when a KL-based statistic passes a threshold built from a new concentration inequality. They show that restricting each intervention value to the two ends of its allowed interval loses nothing, prove that FOCUS is -correct, and show that its expected stopping time grows as , matching the lower bound up to an instance-dependent constant. In simulations with 5 to 7 nodes, FOCUS recovers the graph and edge weights faster than baselines.
Critical strengths
-
Learning a causal model fully online, with a stopping rule that has a frequentist guarantee and with edge weights as part of the target, is a well-motivated and important problem.
-
The paper is clear and self-contained. I checked the main proofs at a high level and did not find errors.
Critical weaknesses
- My main concern is that the theoretical guarantees are vacuous in practice, and the experiments do not test them. The constant in Lemma 4.2 comes from worst-case bounds that grow exponentially with . With the paper's own experimental settings, it is about for , so the stopping rule analyzed in the theory would need an astronomically large number of samples before it could stop, and the gap between the upper and lower bounds is at least . The claim of order-optimality in is also weak, since uniform sampling with the same stopping rule would have the same order. The paper does not explain why a GLR-type analysis [1, 2], which does not lose such a factor, cannot be used here, even though it presents Lemma 4.2 as a key contribution.
Based on my understanding, because of this, the experiments cannot use the stopping rule from the theory. In the experiments, the authors instead use a simple heuristic threshold. Using a heuristic threshold in experiments is common, but I think the authors should mention how often the algorithm returns a wrong answer when it stops, since that is what -correctness is about.
- The technical novelty is limited, and the method only works for very small graphs. Since every node can be intervened on, the graph is already known to be identifiable [4], so the only question is how many samples are needed, which is where the results are weak (Weakness 1). The algorithm follows the track-and-stop framework of [2], which Elahi et al. [3] already applied to causal discovery, and the endpoint reduction (Proposition 4.1) is straightforward: the information from an intervention grows with , so the endpoint with the largest is always best.
The method is also limited to very small graphs. Each round requires enumerating all topological orders, so the experiments stop at 7 nodes, and the authors do not report runtime. The authors note that larger graphs would require approximate solvers, but the guarantees do not cover them. In addition, all data are simulated from exactly the model the method assumes, so the experiments say nothing about robustness to misspecification, such as nonlinear effects or hidden confounders. Finally, for a fixed-confidence method, the natural comparison is the stopping time against RANDOM under the same stopping rule, rather than error curves at a fixed sample budget.
[1] Emilie Kaufmann and Wouter M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246):1–44, 2021.
[2] Rémy Degenne, Wouter M. Koolen, and Pierre Ménard. Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems, volume 32, 2019.
[3] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 13:2409–2464, 2012.
[4] Muhammad Qasim Elahi, Lai Wei, Murat Kocaoglu, and Mahsa Ghasemi. Adaptive online experimental design for causal discovery. In Proceedings of the 41st International Conference on Machine Learning, PMLR 235:12385–12408, 2024.
Questions for authors
-
What is the empirical error rate at stopping for each , under the threshold actually used in the experiments? Is it below ?
-
Can a GLR-type stopping rule with a guarantee be used for this model, and if not, what prevents it?
-
How does the stopping time of FOCUS compare with RANDOM under the same stopping rule and the same ?
2 comments
Official Comment by Reviewer TPh2
Thank you for the detailed response. The new results answer my Q1 and Q3. However, my main concern remains. The stopping rule in the theory is too loose to use, so the experiments use an empirical threshold instead. This threshold has no guarantee, and at , its error rate is already above . Since the guarantee is the main contribution of the paper, I will keep my score.
As the discussion period is approaching its deadline, we would sincerely appreciate the opportunity to hear your thoughts on our response. We hope that the additional clarifications have addressed your concerns. Please feel free to raise any further questions, and we also welcome you to review our discussions with the other reviewers, where we provide additional explanations and results. Thank you again for your time and consideration.