Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions

• URL: http://arxiv.org/abs/2303.14226v2
• Date: Mon, 15 Jan 2024 09:14:09 GMT
• Title: Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions
• Authors: Abhineet Agarwal, Anish Agarwal, Suhas Vijaykumar
• Abstract summary: We learn unit-specific potential outcomes for any combination of interventions, i.e., $N times 2p$ causal parameters. Running $N times 2p$ experiments to estimate the various parameters is likely expensive and/or infeasible as $N$ and $p$ grow.
• Score: 8.491098180590447
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consider a setting where there are $N$ heterogeneous units and $p$ interventions. Our goal is to learn unit-specific potential outcomes for any combination of these $p$ interventions, i.e., $N \times 2^p$ causal parameters. Choosing a combination of interventions is a problem that naturally arises in a variety of applications such as factorial design experiments, recommendation engines, combination therapies in medicine, conjoint analysis, etc. Running $N \times 2^p$ experiments to estimate the various parameters is likely expensive and/or infeasible as $N$ and $p$ grow. Further, with observational data there is likely confounding, i.e., whether or not a unit is seen under a combination is correlated with its potential outcome under that combination. To address these challenges, we propose a novel latent factor model that imposes structure across units (i.e., the matrix of potential outcomes is approximately rank $r$), and combinations of interventions (i.e., the coefficients in the Fourier expansion of the potential outcomes is approximately $s$ sparse). We establish identification for all $N \times 2^p$ parameters despite unobserved confounding. We propose an estimation procedure, Synthetic Combinations, and establish it is finite-sample consistent and asymptotically normal under precise conditions on the observation pattern. Our results imply consistent estimation given $\text{poly}(r) \times \left( N + s^2p\right)$ observations, while previous methods have sample complexity scaling as $\min(N \times s^2p, \ \ \text{poly(r)} \times (N + 2^p))$. We use Synthetic Combinations to propose a data-efficient experimental design. Empirically, Synthetic Combinations outperforms competing approaches on a real-world dataset on movie recommendations. Lastly, we extend our analysis to do causal inference where the intervention is a permutation over $p$ items (e.g., rankings).

Related papers

• Robustly estimating heterogeneity in factorial data using Rashomon Partitions [4.76518127830168]
  We develop an alternative perspective, called Rashomon Partition Sets (RPSs) RPSs incorporate all partitions that have posterior values near the maximum a posteriori partition, even if they offer substantively different explanations. We apply our method to three empirical settings: price effects on charitable giving, chromosomal structure (telomere length) and the introduction of microfinance.
  arXiv  Detail & Related papers  (2024-04-02T17:53:28Z)
• EM for Mixture of Linear Regression with Clustered Data [6.948976192408852]
  We discuss how the underlying clustered structures in distributed data can be exploited to improve learning schemes. We employ the well-known Expectation-Maximization (EM) method to estimate the maximum likelihood parameters from $m$ batches of dependent samples. We show that if properly, EM on the structured data requires only $O(1)$ to reach the same statistical accuracy, as long as $m$ grows up as $eo(n)$.
  arXiv  Detail & Related papers  (2023-08-22T15:47:58Z)
• A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Models [49.038420266408586]
  We show that sorting variables by increasing variance often yields an ordering close to a causal order. We propose an efficient baseline algorithm termed $R2$-SortnRegress that exploits high $R2$-sortability. Our findings reveal high $R2$-sortability as an assumption about the data generating process relevant to causal discovery.
  arXiv  Detail & Related papers  (2023-03-31T17:05:46Z)
• Replicable Clustering [57.19013971737493]
  We propose algorithms for the statistical $k$-medians, statistical $k$-means, and statistical $k$-centers problems by utilizing approximation routines for their counterparts in a black-box manner. We also provide experiments on synthetic distributions in 2D using the $k$-means++ implementation from sklearn as a black-box that validate our theoretical results.
  arXiv  Detail & Related papers  (2023-02-20T23:29:43Z)
• On counterfactual inference with unobserved confounding [36.18241676876348]
  Given an observational study with $n$ independent but heterogeneous units, our goal is to learn the counterfactual distribution for each unit. We introduce a convex objective that pools all $n$ samples to jointly learn all $n$ parameter vectors. We derive sufficient conditions for compactly supported distributions to satisfy the logarithmic Sobolev inequality.
  arXiv  Detail & Related papers  (2022-11-14T04:14:37Z)
• Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability [7.727052811126007]
  In outcome indistinguishability, the goal is to output a predictor that cannot be distinguished from the target predictor. We show that the sample complexity of outcome indistinguishability is characterized by the metric entropy of $P$ w.r.t. This equivalence makes an intriguing connection to the long-standing metric entropy duality conjecture in convex geometry.
  arXiv  Detail & Related papers  (2022-03-09T06:02:31Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  We propose an ensemble learning algorithm called textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) for imbalanced classification problems.
  arXiv  Detail & Related papers  (2021-09-01T14:10:38Z)
• An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
  We present an efficient algorithm (RSG+) for canonical correlation analysis (CCA) using a reparametrization of the projection matrices. While the paper primarily focuses on the formulation and technical analysis of its properties, our experiments show that the empirical behavior on common datasets is quite promising.
  arXiv  Detail & Related papers  (2021-06-08T23:38:29Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)

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.