Arnab Bhattacharyya (Theory Seminar)

"Algorithms for learning and testing statistical and causal relations"

Arnab Bhattacharyya (NUS)
Monday, March 29th 2022, 2-3pm

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