acceptodds
Under review as a conference paper at ICLR 2027

FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions

Abstract

We study fully online fixed-confidence causal discovery without any historical observational data. Starting from zero samples, the learner sequentially selects interventions to recover both the causal DAG and its edge weights under a linear-Gaussian structural equation model. We establish an instance-dependent lower bound for any -correct algorithm and propose FOCUS, which adaptively allocates interventions through an online max–min game. A key contribution is a computable concentration inequality for the accumulated KL divergence involving causal parameters shared across interventions. We prove that FOCUS is -correct and that its expected stopping time matches the lower bound in its dependence up to an instance-dependent constant. Experiments demonstrate improved structure and edge-weight recovery and confirm the predicted stopping-time trend. Our codes are available on https://anonymous.4open.science/r/FOCUS_code-76E5

Primary area:
causal reasoning
Keywords:
causal discovery, online learning, adaptive intervention

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_TPh2OpenReview ↗
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 1−δ1 − \delta, 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 (ϵ,δ)(\epsilon, \delta)-correct, and show that its expected stopping time grows as log⁡(1/δ)\log(1/\delta), 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
  1. 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.

  2. The paper is clear and self-contained. I checked the main proofs at a high level and did not find errors.

Critical weaknesses
  1. My main concern is that the theoretical guarantees are vacuous in practice, and the experiments do not test them. The constant κB\kappa_B in Lemma 4.2 comes from worst-case bounds that grow exponentially with pp. With the paper's own experimental settings, it is about 10−1310^{-13} for p=6p = 6, 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 101210^{12}. The claim of order-optimality in log⁡(1/δ)\log(1/\delta) 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 (ϵ,δ)(\epsilon, \delta)-correctness is about.

  1. 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 u2u^2, so the endpoint with the largest ∣u∣|u| is always best.

The method is also limited to very small graphs. Each round requires enumerating all p!p! 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
  1. What is the empirical error rate at stopping for each δ\delta, under the threshold actually used in the experiments? Is it below δ\delta?

  2. Can a GLR-type stopping rule with a guarantee be used for this model, and if not, what prevents it?

  3. How does the stopping time of FOCUS compare with RANDOM under the same stopping rule and the same δ\delta?

2 comments

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.

Reviewer_TPh2OpenReview ↗

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 p=7p = 7, its error rate is already above δ\delta. Since the guarantee is the main contribution of the paper, I will keep my score.

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

This paper studies causal discovery under a linear-Gaussian model. It considers the the case where the learner can iteratively pick either passive observation or a single-node intervention, receives the sample, and must decide when to stop. The goal is to return the true DAG and edge weights within error and with high probability while minimizing the sample complexity. The paper proposes a Fixed-confidence Online Causal learning method Using Sequential adaptive interventions (FOCUS) as an online algorithm for this setting. The paper describes the algorithm along with theoretical guarantees that the algorithm satisfies. The paper wraps up with synthetic experiments where FOCUS is compared against three other baseline algorithms.

Critical strengths

The papers studies a pretty canonical problem of adaptive causal discovery. To my knowledge, it's unique in the sense that it considers starting with no data (whereas a lot of prior work assumes access to the observational distribution), along with joint recovery of the DAG and edge weights in a continuous setting. Taking an online learning approach to discovery (via Adahedge) is also a pretty interesting application of no-regret approaches in the context of causal discovery.

Critical weaknesses

The algorithm is not efficient in the sense that the actual implementation of the oracle is exponential in p (e.g. Algorithm 2 Line 4 loops over all p! permutations). Rather than saying these are deferred to Appendix F, it may be better if the authors could make this more transparent in the main, and/or propose alternative implementations of the oracles used for the algorithm.

The experiments are limited to small Erdős–Rényi graphs with small p, and compare against only two literature baselines (AIT-DCDI, CBED). There is a long line of literature on adaptive causal discovery algorithms, and the experimental section would be more complete if there is a more comprehensive comparison of FOCUS against other applicable algorithms.

Questions for authors
  1. Can the authors give some idea of whether the oracles needed for the algorithm can be efficiently implemented in practice? Or if this is intractable, what other theoretical justification is there to suggest that the proposed FOCUS algorithm is optimal?

  2. Can the authors give some intuition for when the proposed algorithm is better than naively collecting sufficient observational data and then running any one of the existing adaptive discovery algorithms? On this note, this is also a basic but natural exploration baseline algorithm that should ideally be considered in the experiments as well.

4 comments

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.

Reviewer_pAtzOpenReview ↗

Response

Thanks to the authors for writing up a detailed rebuttal.

For W1, I understand that oracle efficient algorithms are common in theory literature. However, it does leave the question about the overall algorithm's guarantee if we cannot implement the said oracle efficiently, which to my understanding is the case? If so, this should be made clear.

And thanks for the running the experiments in table 1. Maybe I'm missing something, but one thing is that the rows are indexed at seemingly very specific number of samples like e.g. 2087 or 2957. I might have expected something like 1000, 2000...etc. What is the reason for this? Relatedly, it does not seem like the performance of FOCUS is better throughout?

Anyhow, I'm also not up to date on the variety of different new causal discovery algorithms, which the algorithm should be compared against. I'm a bit on the fence about this work and the overall general impression is that the paper may benefit from more clear, stronger theoretical and/or empirical reasons that justify FOCUS's advantages.

Thank you for your comments; we provide further details below and hope they address your concerns and clarify our contributions, simulation assumptions, and how our setting relates to those commonly adopted in the literature.

Response regarding the oracle implementation.

We would first like to emphasize that assuming access to optimization oracles is common in theoretical studies of online discovery and online decision-making, including Degenne et al. (2019) and Elahi et al. (2024), as discussed in Remark 4.3. In addition to the oracle-based analysis, our work provides concrete procedures for implementing these oracles in Appendix F. As reported in our previous response, the implementation also has reasonable running times for networks of moderate size. We therefore consider the algorithm practically implementable.

Identifying large causal networks remains a challenging problem and often requires additional constraints or assumptions. Our work primarily studies the optimality of online identification with confidence guarantees, rather than high-dimensional network identification. We believe that a classical method such as NOTEARS can serve as a suitable approximate solver for larger networks. However, our main focus and contribution concern the theoretical properties of online identification. Developing the NOTEARS-based implementation and investigating its performance on large networks are therefore beyond the scope of the present work.

Response regarding the experimental design.

We acknowledge that FOCUS does not perform particularly well during the early stage, when relatively few samples have been collected. This is due to the forced exploration specified in Eq. (18): FOCUS initially needs to accumulate exploratory samples to support accurate subsequent estimation. Consequently, the proportion of actions selected adaptively is relatively low at the beginning. After collecting more samples, FOCUS overtakes the baselines and achieves the best performance. This behavior is also reflected in Figures 1–5 of the paper.

To capture this transition accurately, we use a denser evaluation grid in the early stage. Specifically, for the experiments with a budget of 6,000 samples, we construct 24 uniformly spaced evaluation points between 40 and 1,000 samples and another 24 between 1,000 and 6,000 samples, round them to integer sample counts, and merge the two grids while removing duplicates. This allows us to capture when FOCUS begins to outperform the other methods, as illustrated by the curves in the paper.

This grid construction produces evaluation points such as 2,087 and 2,957, rather than restricting evaluation to multiples of 1,000. Because space in the rebuttal is limited, we report a more widely spaced subset of these points to illustrate the overall trends. If the paper is accepted, we will incorporate the additional results into the figures in the final version using all evaluation points. The grid construction can also be verified in our submitted code.

The non-round sample counts are therefore an incidental consequence of the evaluation grid, rather than deliberately selected values. They do not affect how performance is measured, and their origin can be verified from the code.

We would also like to emphasize that, although FOCUS may lag behind during the early stage, this occurs well before the stopping condition is triggered, as shown in Figure 1(c) and the stopping-time table in our response to Reviewer TPh2, Q3. This early-stage disadvantage therefore does not undermine the effectiveness of FOCUS: it still stops in the shortest time while meeting the required confidence guarantee. We therefore do not consider the early-stage performance gap to be a problem for the fixed-confidence objective studied in this work.

Further discussion of baselines and oracle assumptions.

Finally, many related studies adopt settings similar to ours. For example, Elahi et al. (2024) use a comparable number of baselines, consider networks of similar sizes, and make analogous oracle assumptions. We would therefore like to emphasize that these choices are common in the related literature.

References

  1. 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.

  2. 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, volume 235 of Proceedings of Machine Learning Research, pages 12385–12408, 2024.

  3. Xun Zheng, Bryon Aragam, Pradeep K. Ravikumar, and Eric P. Xing. DAGs with NO TEARS: Continuous optimization for structure learning. In Advances in Neural Information Processing Systems, volume 31, 2018.

Thank you for your previous responses and for the time you have devoted to reviewing our work. As the discussion deadline approaches, we would sincerely appreciate your careful consideration of our previous responses, particularly our comparisons with existing studies in this field regarding simulation settings, oracle assumptions, and the number of baselines evaluated. We hope that you will consider raising your score in light of these clarifications.

If you have any further questions or concerns, please feel free to raise them, and we will respond as promptly as possible.

Thank you again for your time and effort in reviewing our paper. We greatly appreciate your contribution to the review process.

Reviewer_71BEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to learn both the graph and the edge weights of a linear Gaussian causal model without observational data, when the learner can draw an observational sample or perform a hard intervention on one variable at each round. The learner must stop as soon as it can return the correct graph and weights within a given tolerance, with a user-set probability of error. The authors prove a lower bound on the number of samples any such method needs, show that it is enough to intervene at the two ends of each allowed range, and propose FOCUS. FOCUS chooses interventions through an online game against the hardest alternative model and stops using a new concentration bound. The authors prove that FOCUS meets the target error probability and that its expected sample count grows with the log of the inverse error probability, up to a problem-dependent constant.

Critical strengths
  1. The problem is well posed and the core theory is sound. The lower bound (Thm 3.3), the reduction to interval endpoints (Prop. 4.1) and the correctness proof (Thm 5.1) are clear, and I found no errors in them.

  2. The stopping rule has an explicit error guarantee (Lemma 4.2). This guarantee holds despite the adaptive choice of interventions and requires no historical observational data. Each step of the algorithm can also be computed exactly (App. F).

Critical weaknesses
  1. The constants in Lemma 4.2 come from worst-case bounds and are very small. With the settings of Sec. 6 (6 nodes, maximum weight 1.5), the key rate constant is about 4e-13. This makes the stopping rule in Eq. (22) very conservative and the upper bound in Thm 5.2 very large. The gap between the upper and lower bounds (Rem. 5.3) contains the same constant, so the optimality claim holds only for how the sample count grows with the confidence level, not for the sample count itself. The sampling rule and the upper-bound proof also closely follow Degenne et al. (2019) and Elahi et al. (2024), so the new parts are mainly the Gaussian setting, the endpoint reduction and Lemma 4.2. In addition, two steps in the proof of Thm 5.2 need clarification (see the questions).

  2. With the constants above, Eq. (22) needs a statistic of about 5e16 at 4000 samples, while the statistic can reach only a few thousand. Yet Fig. 1c reports stopping at about 4000 to 4500 samples, and Sec. 6 does not say which threshold was used. As a result, the experiments may not test the stated guarantee. All methods are also compared at a fixed sample budget, not under the stopping rule, so it is not clear how much adaptive selection shortens the stopping time. The gain over RANDOM, which uses the same estimator but picks interventions uniformly at random, is clear for edge weights (Fig. 1b) but small for graph recovery (Fig. 1a). Finally, the setting is narrow: perfect interventions on every node, known ranges and parameter bounds, and only 5 to 7 nodes.

Questions for authors
  1. Which stopping threshold produced the stopping times in Fig. 1c? If it differs from Eq. (22), please show that the observed error rate still stays below the target.

  2. Eq. (15) does not match the standard AdaHedge update (de Rooij et al., 2014). As written, with an infinite first learning rate, it never moves away from the first-round choice. Which update is analyzed, and does Lemma E.2 apply to it?

  3. In Eq. (93), why does the best-response gap tend to zero? The best responses are taken over different sets and can jump at ties.

3 comments

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.

Reviewer_71BEOpenReview ↗

Reviewer Rebuttal Response

Thank you for the detailed response. The authors have addressed several of my concerns, particularly by clarifying the experimental setup, correcting the AdaHedge update, and providing additional empirical results. While some theoretical and practical limitations remain, I appreciate the clarifications and additional evidence. Overall, I would like to maintain my original rating of weak acceptance.

Thank you for your response. We are deeply grateful for the time and effort you have devoted to reviewing our work. Your suggestions have been very helpful in further improving the quality of our manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.