A&C Seminar: Approximation Algorithms for Learning Causal Graphs

Speaker: Raghavendra Addanki , University of Massachusetts, Amherst

Date: Wednesday, March 24, 2021

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/j/97637459251

Event Type: Seminar

Room Description:

Host: Quanquan Liu, MIT

Contact: Quanquan Liu, quanquan@csail.mit.edu

Relevant URL: https://mit.zoom.us/j/97637459251

Speaker URL: https://people.cs.umass.edu/~raddanki/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Approximation Algorithms for Learning Causal Graphs

Title : Approximation Algorithms for Learning Causal Graphs

Abstract :
Discovering causal relationships is one of the fundamental problems in causality. In our work, we study the problem of learning a causal graph where we seek to identify all the causal relations (edges) between variables in our system (nodes of the graph). It has been shown that, under certain assumptions, observational data alone lets us recover the existence of a causal relationship between, but not the direction of all relationships. To recover the direction, we use the notion of an intervention (or an experiment) described in Pearl’s Structural Causal Models (SCM) framework. We assume access to an undirected graph G on the observed variables whose edges represent all causal relationships and our goal is to recover their directions using a minimum cost set of interventions.

It is known that constructing an exact minimum cost intervention set for an arbitrary graph G is NP-hard. We further argue that, conditioned on the hardness of approximate graph coloring, no polynomial time algorithm can achieve an approximation factor better than o(log n), where n is the number of observed variables in G. To overcome this limitation, we introduce a bi-criteria approximation goal that lets us recover the directions of all but small fraction of edges in G. Under this relaxed goal, we give polynomial time algorithms that achieve an approximation factor of 2. Our algorithms combine work on efficient intervention design and the design of low-cost separating set systems, with ideas from the literature on graph property testing.

Based on joint works with Shiva Kasiviswanathan, Andrew McGregor and Cameron Musco.

Research Areas:
Algorithms & Theory, AI & Machine Learning

Impact Areas:
Big Data

See other events that are part of the Algorithms and Complexity Seminar 2021.

Created by Quanquan Liu Email at Thursday, March 18, 2021 at 12:17 AM.