Scalable Computation of Causal Bounds
- URL: http://arxiv.org/abs/2308.02709v1
- Date: Fri, 4 Aug 2023 21:00:46 GMT
- Title: Scalable Computation of Causal Bounds
- Authors: Madhumitha Shridharan and Garud Iyengar
- Abstract summary: We consider the problem of computing bounds for causal queries on causal graphs with unobserved confounders and discrete valued observed variables.
Existing non-studied approaches for computing such bounds use linear programming (LP) formulations that quickly become intractable for existing solvers.
We show that this LP can be significantly pruned, allowing us to compute bounds for significantly larger causal inference problems compared to existing techniques.
- Score: 11.193504036335503
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of computing bounds for causal queries on causal
graphs with unobserved confounders and discrete valued observed variables,
where identifiability does not hold. Existing non-parametric approaches for
computing such bounds use linear programming (LP) formulations that quickly
become intractable for existing solvers because the size of the LP grows
exponentially in the number of edges in the causal graph. We show that this LP
can be significantly pruned, allowing us to compute bounds for significantly
larger causal inference problems compared to existing techniques. This pruning
procedure allows us to compute bounds in closed form for a special class of
problems, including a well-studied family of problems where multiple confounded
treatments influence an outcome. We extend our pruning methodology to
fractional LPs which compute bounds for causal queries which incorporate
additional observations about the unit. We show that our methods provide
significant runtime improvement compared to benchmarks in experiments and
extend our results to the finite data setting. For causal inference without
additional observations, we propose an efficient greedy heuristic that produces
high quality bounds, and scales to problems that are several orders of
magnitude larger than those for which the pruned LP can be solved.
Related papers
- Redefining the Shortest Path Problem Formulation of the Linear Non-Gaussian Acyclic Model: Pairwise Likelihood Ratios, Prior Knowledge, and Path Enumeration [0.0]
The paper proposes a threefold enhancement to the LiNGAM-SPP framework.
The need for parameter tuning is eliminated by using the pairwise likelihood ratio in lieu of kNN-based mutual information.
The incorporation of prior knowledge is then enabled by a node-skipping strategy implemented on the graph representation of all causal orderings.
arXiv Detail & Related papers (2024-04-18T05:59:28Z) - AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
We show that by efficiently parallelizing existing causal discovery methods, we can scale them to thousands of dimensions.
Specifically, we focus on the causal ordering subprocedure in DirectLiNGAM and implement GPU kernels to accelerate it.
This allows us to apply DirectLiNGAM to causal inference on large-scale gene expression data with genetic interventions yielding competitive results.
arXiv Detail & Related papers (2024-03-06T15:06:11Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
arXiv Detail & Related papers (2023-12-19T13:17:43Z) - Provably Efficient Learning in Partially Observable Contextual Bandit [4.910658441596583]
We show how causal bounds can be applied to improving classical bandit algorithms.
This research has the potential to enhance the performance of contextual bandit agents in real-world applications.
arXiv Detail & Related papers (2023-08-07T13:24:50Z) - Approximate Causal Effect Identification under Weak Confounding [13.552959043816482]
We propose an efficient linear program to derive the upper and lower bounds of the causal effect.
We show that our bounds are consistent in the sense that as the entropy of unobserved confounders goes to zero, the gap between the upper and lower bound vanishes.
arXiv Detail & Related papers (2023-06-22T23:35:49Z) - Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
Gaussian processes scale prohibitively with the size of the dataset.
Many approximation methods have been developed, which inevitably introduce approximation error.
This additional source of uncertainty, due to limited computation, is entirely ignored when using the approximate posterior.
We develop a new class of methods that provides consistent estimation of the combined uncertainty arising from both the finite number of data observed and the finite amount of computation expended.
arXiv Detail & Related papers (2022-05-30T22:16:25Z) - Recursive Causal Structure Learning in the Presence of Latent Variables
and Selection Bias [27.06618125828978]
We consider the problem of learning the causal MAG of a system from observational data in the presence of latent variables and selection bias.
We propose a novel computationally efficient constraint-based method that is sound and complete.
We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world structures.
arXiv Detail & Related papers (2021-10-22T19:49:59Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data.
Our algorithms are validated extensively on synthetic and real-world datasets.
arXiv Detail & Related papers (2021-10-12T02:21:30Z) - Nonparametric estimation of continuous DPPs with kernel methods [0.0]
Parametric and nonparametric inference methods have been proposed in the finite case, i.e. when the point patterns live in a finite ground set.
We show that a restricted version of this maximum likelihood (MLE) problem falls within the scope of a recent representer theorem for nonnegative functions in an RKHS.
We propose, analyze, and demonstrate a fixed point algorithm to solve this finite-dimensional problem.
arXiv Detail & Related papers (2021-06-27T11:57:14Z) - Deconfounded Score Method: Scoring DAGs with Dense Unobserved
Confounding [101.35070661471124]
We show that unobserved confounding leaves a characteristic footprint in the observed data distribution that allows for disentangling spurious and causal effects.
We propose an adjusted score-based causal discovery algorithm that may be implemented with general-purpose solvers and scales to high-dimensional problems.
arXiv Detail & Related papers (2021-03-28T11:07:59Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of Partially Observable Decision Processes (POMDPs)
We present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works.
arXiv Detail & Related papers (2020-06-22T17:58:54Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.