mlsanityData to 14 Oct 2026

Active causal structure learning with advice

arXiv 2305.19588 ↗First posted 31 May 2023cs.LG cs.AI cs.DScited by 10

Not on the map. Why?

Abstract (arXiv)

We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) G^* while minimizing the number of interventions made. In our setting, we are additionally given side information about G^* as advice, e.g. a DAG G purported to be G^*. We ask whether the learning algorithm can benefit from the advice when it is close to being correct, while still having worst-case guarantees even when the advice is arbitrarily bad. Our work is in the same space as the growing body of research on algorithms with predictions. When the advice is a DAG G, we design an adaptive search algorithm to recover G^* whose intervention cost is at most O(max1, log psi) times the cost for verifying G^*; here, psi is a distance measure between G and G^* that is upper bounded by the number of variables n, and is exactly 0 when G=G^*. Our approximation factor matches the state-of-the-art for the advice-less setting.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 32 of its 119 references that are in the map. First posted on arXiv 31 May 2023.

Builds on

32 of 119 references.

References · 32

  1. 2018Competitive caching with machine learned advicecited by 195
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2013Learning Bayesian Networks: The Combination of Knowledge and Statistical Datacited by 187
  4. 2013Causal Inference and Causal Explanation with Background Knowledgecited by 170
  5. 2020Algorithms with Predictionscited by 153
  6. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 80
  7. 2017Permutation-based Causal Inference Algorithms with Interventionscited by 78
  8. 2020Online metric algorithms with untrusted predictionscited by 75
  9. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  10. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  11. 2019A Model for Learned Bloom Filters, and Optimizing by Sandwichingcited by 64
  12. 2015Learning Causal Graphs with Small Interventionscited by 63
20 more
  1. 2019ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discoverycited by 52
  2. 2013Strong Completeness and Faithfulness in Bayesian Networkscited by 45
  3. 2017Cost-Optimal Learning of Causal Graphscited by 44
  4. 2019Online Computation with Untrusted Advicecited by 42
  5. 2013A Transformational Characterization of Equivalent Bayesian Network Structurescited by 41
  6. 2020Secretaries with Advicecited by 41
  7. 2020Better and Simpler Learning-Augmented Online Cachingcited by 38
  8. 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
  9. 2020Active Structure Learning of Causal DAGs via Directed Clique Treecited by 38
  10. 2018Experimental Design for Cost-Aware Learning of Causal Graphscited by 25
  11. 2013A Bayesian Approach to Learning Causal Networkscited by 20
  12. 2022Verification and search algorithms for causal DAGscited by 18
  13. 2013Being Bayesian about Network Structurecited by 17
  14. 2021A Novel Prediction Setup for Online Speed-Scalingcited by 17
  15. 2019ML-based Fault Injection for Autonomous Vehicles: A Case for Bayesian Fault Injectioncited by 16
  16. 2020Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGscited by 14
  17. 2022A Universal Error Measure for Input Predictions Applied to Online Graph Problemscited by 14
  18. 2020Minimal enumeration of all possible total effects in a Markov equivalence classcited by 12
  19. 2023Subset verification and search algorithms for causal DAGscited by 12
  20. 2022Learning-Augmented Algorithms for Online TSP on the Linecited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 4; 2026: 2.

10 papers.

  1. 2024Online bipartite matching with imperfect advicecited by 13
  2. 2024Learning multivariate Gaussians with imperfect advicecited by 4
  3. 2025Approximate Proportionality in Online Fair Divisioncited by 4
  4. 2024Probably approximately correct high-dimensional causal effect estimation given a valid adjustment setcited by 2
  5. 2025Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budgetcited by 1
  6. 2025Product distribution learning with imperfect advicecited by 1
  7. 2024Membership Testing in Markov Equivalence Classes via Independence Query Oraclescited by 0
  8. 2025Linear Causal Discovery with Interventional Constraintscited by 0
  9. 2026Causal Preference Elicitationcited by 0
  10. 2026Online Allocation with Unknown Shared Supplycited by 0