ABSTRACT:

I will survey our recent work in understanding some computational aspects of high-dimensional statistical and causal inference. We model distributions and causal environments as sparse Bayes nets on n observable variables and potentially other hidden variables. The questions we address can be categorized into two themes.

Estimation: Can you PAC-learn the distribution given by a Bayes net with known structure? How about if it includes hidden variables? Can you approximate the distance between two distributions? Can you PAC-learn the causal effect distribution when an intervention is made on a subset of the variables? Can you test the validity of a causal Bayes net model?

Discovery: Can you learn the Bayes net structure from observations, if it’s a tree? What is the hardness of learning general bounded in-degree graphs? Can you test a proposed structure from observations? If in addition to observations, you can also perform interventional experiments on a causal environment, can you learn the direction of causation?

I will survey the landscape of problems, and then will focus on our work in structure discovery. I will pose several open problems and directions throughout the talk. The talk describes joint work with Jayadev Acharya, Sourbh Bhadane, Clement Canonne, Davin Choo, Sutanu Gayen, Saravanan Kandasamy, Ashwin Maran, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, Eric Price, Vedant Raval, Ziteng Sun, N.V. Vinodchandran, Yuhao Wang, and Joy Yang.

BIO:

Arnab Bhattacharyya is an assistant professor at the School of Computing, National University of Singapore. He obtained his bachelor’s, master’s and doctoral degrees in computer science from the Massachusetts Institute of Technology. Subsequently, he was a postdoctoral associate at Princeton University and Rutgers University, and an assistant professor and a Ramanujan Fellow at the Indian Institute of Science, Bangalore. He is the recipient of an Amazon Faculty Research Award and a National Research Foundation (Singapore) Fellowship in AI.

His research area is theoretical computer science and foundations of data science, in a broad sense. Specifically, he is interested in algorithms for problems involving high-dimensional data, causal inference, sublinear time algorithms, complexity theory, and algorithmic models for physical systems.

Hosted by Professor Raghu Meka