Seminars
View all Seminars | Download ICal for this eventInterventional Complexity of Learning Causal Graphs
Series: Theory Seminar
Speaker: Vibhor Porwal, Research Associate II, Adobe Research, Bangalore
Date/Time: May 20 11:00:00
Location: Microsoft Teams - ON-LINE
Faculty Advisor:
Abstract:
A well-studied challenge that arises in the structure learning problem of causal directed acyclic graphs (DAG) is that using observational data, one can only learn the graph up to a "Markov equivalence class" (MEC). The remaining undirected edges have to be oriented using interventions, which can be very expensive to perform in applications. Thus, the problem of minimizing the number of interventions needed to fully orient the MEC has received a lot of recent attention. In this talk, I will describe a new universal lower bound on the number of single-node interventions that any algorithm (whether active or passive) would need to perform in order to orient a given MEC. I will then discuss the tightness of this lower bound and compare it with previously known lower bounds. I will also describe the notion of CBSP orderings, which are topological orderings of DAGs without v-structures, and underly the main technical idea for proving our lower bound.
This is based on joint work with Piyush Srivastava (TIFR) and Gaurav Sinha (Adobe Research). Paper link - https://arxiv.org/abs/2111.05070
-----------
Microsoft Teams Link:
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
Speaker Bio:
Host Faculty: Sruthi Gorantla and Rahul Madhavan