More Like this

1. Condition number bounds for causal inference

   Gordon, S.L. ; Kumar, V. M. ; Schulman, L. J. ; Srivastava, P. ( January 2021 , Proceedings of Machine Learning Research)

   de Campos, C. ; Maathuis, M. H. (Ed.)

   An important achievement in the field of causal inference was a complete characterization of when a causal effect, in a system modeled by a causal graph, can be determined uniquely from purely observational data. The identification algorithms resulting from this work produce exact symbolic expressions for causal effects, in terms of the observational probabilities. More recent work has looked at the numerical properties of these expressions, in particular using the classical notion of the condition number. In its classical interpretation, the condition number quantifies the sensitivity of the output values of the expressions to small numerical perturbations in the input observational probabilities. In the context of causal identification, the condition number has also been shown to be related to the effect of certain kinds of uncertainties in the structure of the causal graphical model. In this paper, we first give an upper bound on the condition number for the interesting case of causal graphical models with small “confounded components”. We then develop a tight characterization of the condition number of any given causal identification problem. Finally, we use our tight characterization to give a specific example where the condition number can be much lower than that obtained via generic bounds on the condition number, and to show that even “equivalent” expressions for causal identification can behave very differently with respect to their numerical stability properties. 

   more » « less
2. Sample Complexity of Distinguishing Cause from Effect

   Acharya, Jayadev ; Bhadane, Sourbh ; Bhattacharyya, Arnab ; Kandasamy, Saravanan ; Sun, Ziteng ( April 2023 , Proceedings of Machine Learning Research)

   Ruiz, Francisco ; Dy, Jennifer ; van de Meent, Jan-Willem (Ed.)

   We study the sample complexity of causal structure learning on a two-variable system with observational and experimental data. Specifically, for two variables X and Y, we consider the classical scenario where either X causes Y , Y causes X, or there is an unmeasured confounder between X and Y. We show that if X and Y are over a finite domain of size k and are significantly correlated, the minimum number of interventional samples needed is sublinear in k. We give a tight characterization of the tradeoff between observational and interventional data when the number of observational samples is sufficiently large. We build upon techniques for closeness testing and for non-parametric density estimation in different regimes of observational data. Our hardness results are based on carefully constructing causal models whose marginal and interventional distributions form hard instances of canonical results on property testing. 

   more » « less
3. Learning and Sampling of Atomic Interventions from Observations

   Bhattacharyya, Arnab ; Gayen, Sutanu ; Kandasamy, Saravanan ; Maran, Ashwin ; Vinodchandran, N. V. ( July 2020 , Proceedings of the 37th International Conference on Machine Learning)

   We study the problem of efficiently estimating the effect of an intervention on a single variable using observational samples. Our goal is to give algorithms with polynomial time and sample complexity in a non-parametric setting. Tian and Pearl (AAAI ’02) have exactly characterized the class of causal graphs for which causal effects of atomic interventions can be identified from observational data. We make their result quantitative. Suppose 𝒫 is a causal model on a set V of n observable variables with respect to a given causal graph G, and let do(x) be an identifiable intervention on a variable X. We show that assuming that G has bounded in-degree and bounded c-components (k) and that the observational distribution satisfies a strong positivity condition: (i) [Evaluation] There is an algorithm that outputs with probability 2/3 an evaluator for a distribution P^ that satisfies TV(P(V | do(x)), P^(V)) < eps using m=O (n/eps^2) samples from P and O(mn) time. The evaluator can return in O(n) time the probability P^(v) for any assignment v to V. (ii) [Sampling] There is an algorithm that outputs with probability 2/3 a sampler for a distribution P^ that satisfies TV(P(V | do(x)), P^(V)) < eps using m=O (n/eps^2) samples from P and O(mn) time. The sampler returns an iid sample from P^ with probability 1 in O(n) time. We extend our techniques to estimate P(Y | do(x)) for a subset Y of variables of interest. We also show lower bounds for the sample complexity, demonstrating that our sample complexity has optimal dependence on the parameters n and eps, as well as if k=1 on the strong positivity parameter. 

   more » « less
4. Tropospheric and Stratospheric Causal Pathways Between the MJO and NAO

   https://doi.org/10.1029/2019JD031024  

   Barnes, Elizabeth A. ; Samarasinghe, Savini M. ; Ebert‐Uphoff, Imme ; Furtado, Jason C. ( August 2019 , Journal of Geophysical Research: Atmospheres)

   Previous work has shown that the Madden‐Julian Oscillation (MJO) can influence the North Atlantic Oscillation (NAO) via a Rossby wave teleconnection that propagates through the troposphere (i.e., a tropospheric pathway). In addition, recent work suggests that the MJO can influence the stratospheric polar vortex, which is also known to influence the tropospheric NAO—thus, there likely exists a stratospheric pathway for MJO influence as well. Here, we apply two methods to shed more light on the pathways linking the MJO to the NAO. First, we use a traditional approach in climate science based on analyzing conditional probabilities. Second, we use methods from causal discovery theory based on probabilistic graphical models. Together, these two analysis approaches reveal that the MJO can impact the NAO via both a tropospheric and stratospheric pathway. The stratospheric pathway is shown to come about in two ways: First, both methods show that the MJO itself influences the strength of the stratospheric polar vortex on a timescale of ∼10 days, and then 5 days later the vortex can drive changes in the NAO. Second, the state of the stratospheric polar vortex acts to condition the NAO to be conducive (or not) to MJO influence. When the vortex is in a state that opposes the expected NAO response to the MJO, we find little influence of the MJO on the NAO, however, when the vortex supports the expected NAO response, the NAO is up to 30% more likely to be in a particular state following active MJO periods.

    

   more » « less
5. HOGWILD!-Gibbs can be PanAccurate

   Daskalakis, Constantinos ; Dikkala, Nishanth ; Jayanti, Siddhartha ( January 2018 , Journal of neural information processing)

   Asynchronous Gibbs sampling has been recently shown to be fast-mixing and an accurate method for estimating probabilities of events on a small number of variables of a graphical model satisfying Dobrushin's condition~\cite{DeSaOR16}. We investigate whether it can be used to accurately estimate expectations of functions of {\em all the variables} of the model. Under the same condition, we show that the synchronous (sequential) and asynchronous Gibbs samplers can be coupled so that the expected Hamming distance between their (multivariate) samples remains bounded by O(τlogn), where n is the number of variables in the graphical model, and τ is a measure of the asynchronicity. A similar bound holds for any constant power of the Hamming distance. Hence, the expectation of any function that is Lipschitz with respect to a power of the Hamming distance, can be estimated with a bias that grows logarithmically in n. Going beyond Lipschitz functions, we consider the bias arising from asynchronicity in estimating the expectation of polynomial functions of all variables in the model. Using recent concentration of measure results, we show that the bias introduced by the asynchronicity is of smaller order than the standard deviation of the function value already present in the true model. We perform experiments on a multi-processor machine to empirically illustrate our theoretical findings. 

   more » « less