- A&C Seminar: Approximation ...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in March 2021

## 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

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