Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions
Authors: Abhineet Agarwal
Anish Agarwal
Suhas Vijaykumar
Venue: NeurIPS 2023 poster (2023)
Keywords: Causal Inference
Matrix Completion
Combinatorial Learning
Ranking
TL;DR: A causal inference framework for learning unit-specific counterfactuals for combinations of interventions.

Abstract: We 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 and recommendation engines (e.g., showing a set of movies that maximizes engagement for a given user). 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. We study this problem under a novel model that imposes latent structure across both units and combinations of interventions. Specifically, we assume latent similarity in potential outcomes across units (i.e., the matrix of potential outcomes is approximately rank $r$) and regularity in how combinations of interventions interact (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 finite-sample consistency under precise conditions on the observation pattern. We show that Synthetic Combinations is able to consistently estimate unit-specific potential outcomes given a total of $\text{poly}(r) \times \left( N + s^2p\right)$ observations. In comparison, previous methods that do not exploit structure across both units and combinations have poorer sample complexity scaling as $\min(N \times s^2p, \ \ r \times (N + 2^p))$.

Synthetic Combinations:
A Causal Framework for Combinatorial Interventions
Abhineet Agarwal
Anish Agarwal" Department of IEOR Columbia University aa51 aa5194@columbe emuii..euuuuuu.uu..aa.mmmuuuu
Suhas Vijaykumar' Amazon, Core AI suhasvemit. edu
Department of Statistics University of California, Berkeley aa3797bberkeley eed edu
Abstract
We consider setting where there are N heterogeneous units and p interventions. Our goal to learn unit-specific potential outcomes for any combination these interventions, i... N x 2" causal parameters. Choosing combination of interventions a problem that naturally arises a variety of applications such as factorial design experiments and recommendation engines (c.g., showing set of movies that maximizes engagement). Running 2" experiments to estimate the various parameters is likely expensive and/or infeasible as N and grow. Further, with observational data there is likely confounding, i.e., whether or not a unit is seen under combination is correlated with its potential outcome. We study this problem under a novel model that imposes latent structure across both units and combinations of interventions. Specifically, outcomes across units (i.e., the matrix of potential outcomes is rank r) and regularity in how combinations of interventions interact (i.e., the coefficients in the Fourier expansion of the potential outcomes is sparse). We establish identification for all N 2" parameters despite unobserved confounding. We propose an estimation procedure, Synthetic Combinations, and establish finite kiite--sample consistency under precise conditions on the observation pattern. We show that Synthetic Combinations is able to consistently estimate unit-specific potential outcomes given a total of poly(r) previous methods that do not exploit structure across both units and combinations have poorer sample complexity that scales as min(N x x²p, poly(r) (N++)))
assume latent similarity in potential
(N+s²p) observations. In comparison,
Introduction
Modern-day decision makers-ine settings from e-commerce public policy to medicine-often must select a combination of actions, and would like to do so in highly personalized manner. Examples include recommending a curated basket of items customers on a commerce platform, deciding on combination of therapies for medical patient, enacting collection of socio-economic policies for specific geographic location, conjoint analysis in surveys, selecting important feature sets for machine learning models, etc. Despite the ubiquity of this setting, it comes with significant empirical challenges: with p interventions and N units, decision maker must evaluate N 2 potential combinations in order to confirm the optimal personalized policy. With large N and even with relatively small p (due to exponential dependence), becomes infeasible to run that many experiments; in observational data there is the additional challenge of potential unobserved confounding. Current methods tackle this problem by following one of two approaches: (i) they impose structure on how combinations of interventions interact, or (ii) they assume latent similarity
Work done while post-doc Amazon, Core Work done while at MIT.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

in potential outcomes across units, However, as we discuss in detail below, these approaches require a large number of observations to estimate all N x 2" potential outcomes because they do not exploit structure across both units and combinations. This motivates the question: how can one effectively share information across both units and combinations of interventions?
Contributions. Our contributions may be summarized as follows. (1) For unit 72 E [NV] we represent its potential outcomes over the 2 combinations as Boolean function from {-1,1}² to I. expressed in the Fourier basis. To impose structure across combinations, we assume that for a unit n, the linear coefficients On, E R induced by this Fourier basis representation is s-sparse, i.c., has at most s non- zero entries. To impose structure across units, we assume that this matrix of Fourier coefficients across units A= [o,,]ne Eg has rank This simultancous sparsity and low-rank assumption allows the researcher to share information across both units and combinations. (2) We establish identification for the N x 2" potential outcomes of interest, which requires that any confounding is mediated by the (unobserved) matrix of Fourier coefficients A. (3) We design a two-step algorithm "Synthetic Com- binations" and prove it consistently estimates the various causal parameters, despite potential unob- served confounding. The first step of Synthetic Combinations, termed "horizontal regression", learns the structure across combinations of petrventtonsaasssunnnn sparsity in the Fourier coefficients-vin the Lasso. The second step, termed "vertical regression". learns the structure across units assuming the matrix of Fourier coefficients are low-rank via principal component regression (PCR). (4) We show that Synthetic Combinations is able to consistently estimate unit-specific potential outcomes given a total of poly(r) (N+ + s²)) observations (ignoring logarithmic factors). This improves over previous methods that do not exploit structure across both units and combinations, which have sample complexity scaling as min(N x s"p, poly(r) x (N + 2)).. ). A summary of the sample complexities required for different methods can be found in Table I A key technical challenge in our proofs is analyzing how the error induced in the first step of Synthetic Combinations percolates through to the second step. To tackle it, we reduce the problem to that of nigh-dimenssonal error-in prvor-in-variee variables regression with linear model misspecification, and do a novel analysis of this statistical setting.
2 Related Work
Learning over Combinations. To place structure on the space of combinations, we use tools from the theory of learning (sparse) Boolean functions, in particular the Fourier transform. Sparsity of the Fourier transform was proposed as a complexity measure to characterize and design learning algorithms for low-depth trees, low-degree polynomials, and small circuits [22 26 Learning Boolean functions is now central topic in learning theory, and is closely related to many important questions in ML more broadly; see e.g. [3] for discussion of the k-Junta problem and its relation to relevant feature selection. We refer to O' Donnell [34] Chapter 3] for further background on this area. In this paper, we focus on (32] which showed that Lasso can be used to efficiently learn sparse Boolean functions, an essential property in our setting since the dimension of the function class grows exponentially,
Matrix Completion. We build on the observation that imputing counterfactual outcomes in the presence of a latent factor structure can be equivalently expressed as low-rank matrix completion [ The observation that low-rank matrices may typically be recovered from a small fraction of the entries by nuclear-norm norm minimization has had a major impact on modern statistics [15) 355 [3]. In the noisy setting, proposed estimators have generally proceeded by minimizing risk subject to a nuclear-none -orm penalty, such as in the SoftImpute algorithm of 300, or minimizing risk subject to a rank constraint as in the hard singular-value thresholding (HSVT) algorithms analyzed by
27 28 23 6).
We refer the reader to 19 33 for a comprehensive overview of this vast literature.
Learning algorithm
Exploits structure across
Exploits structure across units (rank( (A) =
Sample complexity
combinations (I 1lo = 8)
Lasso
X
((Nxs"p) O (r) x (2+)") O (poly(()) (N (N+s*p))
Matrix Completion
X
Synthetic Combina-
tions
Table I: Comparison of sample complexity of Synthetic Combinations to other methods.
2

---

Econometrics/causaal inference. There is a rich literature on how to learn personalized treatment effects for heterogeneous units. This problem is of particular importance in the social sciences and in medicine, where experimental data is limited, and has led to several promising approaches including instrumental variables, Sefference-in-diffeeemn an overview. Of particular interest to here is the "synthetic control" method [1 which exploits an underlying factor structure to effectively "share" counterfactual information between treatment and control units. Building on [I recent work has shown that the same underlying structure can be used to estimate treatment effects with multiple treatments and heterogeneous units despite unmeasured confounding. The resulting framework, called "synthetic interventions" (SI), uses the factor repre- sentation to efficiently share information across similar (yet distinct) units and treatments [5]. We generalize the SI framework to settings where treatments treatments have no units that receive it, but there is structure across combinations of interventions. In doing so, enable its in highly practical cases where multiple interventions delivered simulta- neously, such as recommender systems, medical treatment regimens, and factorial design experiments.
regression discontinuity, and others; see 7 25] for
combinations of interventions and most
Sctup and Model
In this section, we first describe requisite notation, background on the Fourier expansion of real-valued functions over booleans, and how it relates potential outcomes over combinations.
3.1 Notation
Representation of Combinations as Binary Vectors. Let [p] = (1,...pp denote the set of p interventions. Denote by II the power set of [p]. i.e., the set of all possible combinations of interventions, where we note [II] 2". Then, any given combination x E induces the following = (
binary representation v [-1,1} defined follows:
Fourier Expansion of Boolean Funetions. Let Fet bool = [f: (- 13 be the set of all real- valued functions defined on the hypercube {-1,1} Then bool forms Hilbert space defined by the following inner product: for any f.g E F Foool (f-g) = 2 E. ExE(-11ju induces the norm
This inner product 2F Exe(- (x)). We construct orthonormal basis for Fooo as follows: for each subset S [p),, define basis function xs(x)= -I, where H, is the 7th coefficient of x e [-1,1}" One can verify that for any SC that |ixs|l==1, and that (xs.xs)) O for any S' #S. Since (xs:SC (pl)/22 the functions Xs are an orthonormal basis of F
be expressed via the following "Fourier" decomposition: f(x) Escol axxs(x), where the Fourier coefficient as is given by computing as = (f.xs) We will refer to Xs as the Fourier character. Define ay = [aslsepi E R and (())=[x(())sset) {--1,1]2" as the vector of Fourier coefficients and characters respectively. Hence any function {- +B R can be re-expressed as follows: f(x) = (a)+)(x))) For ा e1, abbreviate (T()(T) and ((v())) as X3 and x" respectively.
Hence, any
Fooo
Observed and potential outcomes. Let y,(") E R. denote the potential outcome for unit n under combination and Yu E (RU*) as the observed outcome, where * indicates a missing value, i.e., the outcome associated with the unil-combination pair (π,,)) was not observed. Let = [Yn=] [TRU*) Nx2", Let D C [N] [N]x[ x [2?), refer to the subset of unit-combination pairs we observe, i.e.,
(T) if (n,
Y nx
(1)
*,
otherwise.
Note that (1) implies stable unit treatment value assignment (SUTVA) holds. Let II II denote
subset of combinations. For given unit let Yıs.,= [Y E [Ig] E (RR Ux] [1s] represent
|
the vector of observed outcomes for all я E Ig.. Similarly, let (llss) = -v,("))) : E Mg] E !sl
represent the vector of potential outcomes. Denote x(Ils) = " 11s] (-1,1) x2
3

---

3.2 Model & Target Causal Parameter
Define yı(, R real-valued function over the hypercube {-1,1}² associated with unit n. It takes as input a combination т, converts it to a p-dimensional binary vector v(T), and outputs a real number y² Given the discussion in Section 3.1 it follows that y!(*) always has the representation (x), for some an ER² Thus, without any loss of generality, the an, are unit-specific latent variables (Fourier coefficients) encoding the treatment response function. Below, we state our key assumption these induced Fourier coefficients.
Assumption 3.1 (Potential Outcome Model), For any unit-combination pair (n,T), assume it has the following representation,
(2) where on ERT and x" (-1,1)2² are the Fourier coefficients and characters, respectively. We assume the following properties: (a) low-rank: the matrix A= [On]nE[N] has rank r E (min(N,27))
Y ((²)= (ax:x"" +E
n
(b) sparsity: On, is 8-sparse (i.e. ||ax,, Ilo S., where & [2) every unit n E [N]]; (c) e is a residual term specific (n,5) which satisfies Elc,] A =0
The assumption is then that each On, 8-Sparse and A is rank-r; e, is the residual from this sparse and low-rank approximation, and it serves the source of uncertainty in our model. Given Ele, A =
the matrix E|Y [ [E[Y E [M]] E ER also is rank r, where the expectation is defined N
with respect to c This is because ( can be written as N = and since X(II) is an invertible matrix, ( rank(A). The low-rank property places structure across units; that is, we assume there is sufficient similarity across units so that E E|Y for any unit n be written linear combination of r other rows of B| This is standard assumption used to encode latent similarity across units in matrix completion and its related applications (e.g.. recommendation engines).
Sparsity establishes unit-specific structure; that is, we assume that the potential outcomes for a given user only depend on small subset of the functions (xs: S [Cpp [p]]. We emphasize that this subset of functions can be different across units. As discussed in Section 2 sparsity is commonly employed when studying the learnability of Boolean functions. In the context of recommendation engines, sparsity is implied if the ratings for a set of goods only depend on a small number of combinations of items within that set. Sparsity is also often assumed implicitly in factorial design experiments, where analysts typically only include pairwise interaction effects between interventions and ignore higher-order interactions [24]. We discuss further applications of combinatorial inference in greater detail in Appendix [A]
Next, we present assumption that formalizes the dependence (i.e., confounding) between the missingness pattern induced by the treatment assignments D and the potential outcomes y-(*) and provide an interpretation of the induced data generating process (DGP) for potential outcomes.
Assumption 3.2 (Sclection on Fourier coefficients). For all n E [N] and π II. Y((*) IDIA
DGP. Given Assumptions 3.1 and Assumption 3.2] the DGP can be summarized follows: (i) unit- specific latent Fourier coefficients A are either deterministic or sampled from an unknown distribution; we will condition on this quantity throughout. (ii) Given A, we sample mean-zero random variables
f <; and generate potential outcomes according to our model (T) ((nnxx)) ) (iii) D is allowed to depend unit-specific latent Fourier coefficients A (i.e. D=f(A)). We define all expectations
w.r.t. noise, <. This DGP introduces unobserved confounding since y,(") L.D. However, this DGP does imply that Assumption 3.2 holds, i.e., conditional the Fourier coefficients A, the potential outcomes are independent of the treatment assignments D. This conditional independence condition can be thought of "selection on latent Fourier coefficients". which generalizes the widely made assumption of "selection on observables." The latter requires that potential outcomes are independent of treatment assignments conditional on observed covariates-we reemphasize that AA is unobserved.
Target parameter. For any unit-combination pair (,,r), we aim to estimate F[Y;(*)) [A4,, where the expectation is w.r.t. eg, and we condition the set of Fourier coefficients A.

---

Identification of Potential Outcomes
We show that E[y;(") |A] can be written as a function of observed outcomes, i... we establish identification of our target causal parameter. As discussed earlier, our model allows for unobserved confounding: whether or not unit is seen under combination may be correlated with its potential outcome under that combination due to unobserved factors, as long as certain conditions are met. We introduce necessary notation and assumption required for our result. For a unit E [N], denote the subset of combinations we observe them under as II, C II. For E II, let X E II?" denote the vector where we zero out all coordinates of x" ER? that correspond to the coefficients of a, which are zero. For example, a. (1,1,0,0....0) and x" (1,1,...1))) then X (1,),0,...0). We the make the following assumption.
Assumption 4.1 (Donor Units), We assume there exists set of "donor units" I C [N]. such that the following two conditions hold:
(a) Horizontal span inclusion: For any donor unit I and combination
II, suppose
X E Espan (xu :m; ET.). That is, there exists exists Bi,, E ERIla such that X -E P7, X
(b) Linear span inclusion: For any unit n [N] I, suppose an E span(a. : I). That is, there exists w" such that at,, -.err
Horizontal span inclusion requires that the set of observed combinations for any donor unit "diverse" enough that the projection of the Fourier characteristic for target intervention is in the span of charac- teristics of observed interventions. Linear span inclusion requires that the donor set diverse enough such that the Fourier coefficient of any unit is in the span of the Fourier coefficients of the donor set.
4.1 Identification Result
Given these assumptions, we now present our identification theorem.
Theorem 4.2. Let Assumptions 3./
3.2 4./
hold. Given Pit and w", defined in Assumption 4.7
have
|A]= -A==E,, Em, 8T, E[ N, AA (a) Donor units: For u E.I, and π II, E
| - - W WH E[Y IA, D). (b) Non-donor units: no I and π HI, E|Y
Theorem 4.2 gives conditions under which the donor set I and the observation pattern D sufficient to recover the full set unit specific potential outcomes E[y,(") [A] the noise-free limit. Part (a) establishes that for every donor unit uII, the causal estimand can be written as a function of own observed outcomes E. I. given knowledge of Bi... Part (b) states that the target causal
estimand E[ for non-donor unit and combination πT can be written as a linear combination of the outcomes of the donor set I, given knowledge of w Previous works that establish identification under a latent factor model requires growing number of donor units to be observed under all treatments 6 This is infeasible in our setting because the vast majority of combinations have no units that receive it. As a result, we have to first to identify the outcomes of donor units under all combinations (part (a)), before transferring them to non-donor units (part (b)). In order to do so,
Theorem 4.2 suggests that the key quantities estimating BY(;(") for any unit-combination pair (n.T)) are 3.. and w.. In the following section, we provide an algorithm to estimate both f and w as well concrete ways of determining the donor set
The Synthetic Combinations Estimator
We now describe the Synthetic Combinations estimator, a simple and flexible two-step procedure for estimating target causal parameter. See Figure for pictorial representation.
Step 1: Horizontal Regression. We denote the vector of observed responses Y Y,,I,, =VY : 11.] E R [l,, for any unit n YI..- Then, for every unit in the donor set I, estimate E|
5

---

via the Lasso, i.e., by solving the following convex program with penalty parameter Xu:
O₂ aagginn
Yn,
(3)
x : E Ic] E R [lll"""" Then, for any donor unit-combination pair (u,x), let [[Y]'' (a denote the estimate of the potential outcome E[Y
where recall that ((I.,,,
Step Vertical Regression. Next, we estimate potential outcomes for all units n [M]] IZ. To do
we define some required notation. For 11g C1l, define the vector of estimated potential outcomes
Y [[[Y!"]]: E E Iss Additionally, [
| Rl
Step 2(a): Principal Component Regression. Perform a singular value decomposition (SVD) of E| I [ to get B =m (lll1zz) &1ppo"" Using hyper-parameter min
compute T |2 follows:
w" Σ St
inpa
Yu..
(4)
Step 2(b): Estimation, Using w [10 I], have the following estimate for any II
E|y Σ
(5)
WEI
17g 10
π
7
Y II,
W
W
I
E7 Y (1.h)
B Y
Y II,
IL
(a) Observation pattern
(b) Horizontal regression
(c) Vertical regression
Figure 1: (a) depicts example of particular observation pattern with outcome for unit-combination pair (n,m) missing. (b) demonstrates horizontal regression for donor unit where estimate potential outcome E. F.)((()) (c) visualizes vertical regression where transfer estimated outcomes from the donor to (n,r)
Suitability of Lasso and PCR. Lasso is appropriate for the horizontal regression because Qu sparse. However, Synthetic Combinations allows for any ML algorithm (e.g.. neural networks, random forests) be used in the first step. This flexibility allows an analyst to tailor the horizontal learning procedure. and include prior information. However, we leave this model-agnostic analysis as future work, and focus on the Lasso for simplicity. PCR is appropriate for the vertical regression because As 3 show, PCR implicitly regularizes the regression by adapting to the rank of the covariates (Y I. J, i.e., the out-of-sample error of PCR scales with rather than the ambient covariate dimension.
low rank.
Determining Donor Set T. Synthetic Combinations requires the existence of a subset of units able to (i) accurately estimate their potential outcomes under all possible combinations, and (ii) transfer these estimated outcomes to a unit E [N] \ Z. Theoretically. we detail sufficient conditions on the observation pattern such that we are able perform and (ii) accurately via the Lasso and PCR respectively. In practice, we recommend the following to determine I. For every unit n E [N], learn a separate Lasso model a,, and assess its performance through cross- validation (CV). Assign units with low CV error (with pre-detemmined threshold) as the donor set I,
[C[ such that
Both À and be chosen in data-drive driven manner (e.g.. via CV) discussed in and respectively.

---

and estimate outcomes [ for every unit w I and ET. For non-donor units, PCR performance can also be assessed via k-fold CV. For units with low PCR error, linear span inclusion (Assumption [b) and the assumptions required for the generalization for PCR likely hold, and hence estimate their potential outcomes as in (5). For units with large PCR error, it is either unlikely that these set of assumptions holds that IT is not large enough (i.e., additional experiments need to be run for this unit), and hence we do not recommend estimating their counterfactuals.
Synthetic Combinations Theoretical Analysis
In this section, we establish inite-sample consistency of Synthetic Combinations, starting with a discussion of the additional assumptions required for results.
6.1 Additional Assumptions
Assumption 6.1 (Bounded Potential Outcomes). We assume that E(y, E [-1, 1] for any unit-combination pair (n,
Noise). Conditioned on for any unit-combination pair (n, eñ are independent zero-mean sub-Gaussian random variahles with VarlcT | and [|] Ally, S Co
Assumption 6.2
for some constant C>0.. O.
Assumption 6.3 (Incoherence of Donor Fourier characteristics). For every unit u EI, assume x(I.,)
satisfies incoherence: x(II..) x(II.)
12p
C. .for universal constant C' >> 0.
[T_]]
To define our next set of assumptions, we introduce necessary notation. For any subset of combinations g II, let
Assumption 6.4 (Donor Unit Balanced Spectrum). For given unit n. [N] \ let rn and (II.)) $1...5r. denote the rank and non-zero singular values of I A]. We assume that the singular values are well-balanced, iee,, for universal constants c, c O, have that Sea /81 c, and
I A]I 2 cd I
Assumption 6.5 (Subspace Inclusion). For given unit n E [N] I and intervention т E EII 11 I. lies within the row-span of Y (Ia))
assume that Y (m)
Assumption 6.3 is necessary for finite-sample consistency when estimating Ot, via the Lasso estimator
(3). and is commonly made when studying the Lasso [36]. Incoherence can also seen as a inclusion
criteria for a unit n to be included in the donor set Z. Assumption 6.3 for example holds (with high
probability) if II, is chosen uniformly at random and grows (ss p) as shown in Lemma 2 of [32]
Assumption 6.4 requires that the non-zero singular values of E z
(II.) | are well-balanced. This K 5 and within the econometrics literature 10)
assumption standard when studying PCR
can also be empirically validated by plotting the spectrum of (
;; if the singular spectrum
of 18 (lm) displays natural elbow point, then Assumption 6.4 likely. Assumption 6.5 is also
(2) It can be thought of as "cauual transportabilityy" commonly made when analyzing PCR 5
condition from the model learnt using IL, the interventions π e 1111 111, That is, subspace inclusion
allows us to generalize well, and accurately estimate E[Y;(")
|A] using (É) ( (TI.) w.")..
6.2 Finite Sample Consistency
The following result establishes finite-sample consistency of Synthetic Combinations. Without loss of generality, we will focus on estimating the pair of quantities (E(y J.E..EEE.. [E{{((())) for given donor unit II and non-donor unit n E [N]{Z under treatment assignment и II. To simplify notation, we will use O,, notation: for any sequence of random vectors X,, X,, O,(%,) if, for any <> O, there exists constants 6, and n, such that IP[[ X,, la 2 7x7%) Se for every n 2 n. Similarly, we define (7())) which suppresses logarithmic terms. We will further absorb dependencies on a into Öp(.). Theorem 6.6 (Finite Sample Consistency of Synthetic Combinations). Conditioned on A, let Assumptions 3.1 4.1 and m.d6.166 h.5lld. Then, the following statements hold.
7

---

(a) For the given donor unit-combination pair (u,T), let the Lasso regularization parameter
satisfy X = - n Then, we have that: [ 1 11 (v .pp
[II.]
(b) For the given unil-combination pair (n,,)) where n II, let K. rank Then, provided that min [T.,] := M
(r |Ta
we have that:
a s²p
-
= =Op
n PV
I'
V min (II
M
[IL 1/4
Establishing Theorem 6.6 requires a novel analysis of error-i--variables (EIV) linear regression. Specifically, the general EIV linear model is as follows: = = + Z = X where Y and Z are observed. In our case, Y Yı,,, X [ 3 w Z E. Y [(]))) and H is the
error arising in estimating E| [[) via the Lasso. Typically one assumes that H is is matrix of independent sub- sub-gaussian noise. Our analysis requires a novel worst-case analysis of H (due the
2-step regression of Lasso and then PCR), in which each entry of is H simply bounded.
Next, describe the conditions placed on IT M, I to achieve consistent estimation of (E|Y:""),E[Y"
To simplify the discussion, we assume that min =|]]. This condition can be enforced in practice by simply picking subset of donor units such that [I] S [[,,] when performing PCR (i.e., step 2 of Synthetic Combinations). Given this assumption. can be verified that [TT, and M need to scale w(rA) and wr))spp) respectively to achieve - (1). Next, we present corollary that discusses
max (18( how quickly the parameters Tn. s, and p can grow with the number of observations [II,] and M.
Corollary 6.7. With the set-up of Theorem 6.6 if (a) Tn (2/2) and (b) - op(1) as
(M/(paxx((aaalTTT)) then max (I M. 000.
Corollary 6.7 quantifies how 8,r, can scale with the number of observations to achieve consistency. That is, Corollary reflects the maximum "complexity" allowed for given sample size.
6.3 Sample Complexity
We discuss the sample complexity of Synthetic Combinations to estimate all N x 2 causal param- eters, and compare it to that of other methods. To ease discussion, we will ignore dependence on logarithmic factors and a. Even potential outcomes yz(=) were observed for all unit-combination
pairs, consistently estimating E (1I)
N is not trivial. This is because, only get to observe single and noisy version Yns = (at X ) +e Hypothetically. if we observe K independent samples of Y n for given (,, denoted by Y1 ".....,. n..
Y the maximum likelihood estimator would be the empirical average X Y The empirical average would concentrate around E[( at a rate ((1/V K) and hence would require = =2
((8-)))))))))))))))))) 2) samples to estimate E[(; within error O(6). Therefore, this naive (unimplementable) solution would require N x 2 x 8 observations to estimate {
On the other hand, Synthetic Combinations produces consistent estimates of the potential outcome de- spite being given at most only a single noisy sample of each potential outcome. As the discussion after Theorem 6.6 shows. if [ [[,)). Synthetic Combinations requires [[] x x r=2"pp/ 522 observations for the donor set, and (N [T) xxr// / observations for the non-donor units to achieve an estimation er- of ((5) for all N x 2" causal parameters. Hence, we have that the number of observations required to achieve an estimation error of O()) for all pairs (n,TT) scales as (ppoy((r/8) (N +s))))
Sample Complexity Comparison to Other Methods. Horizontal regression: An alternative algorithm would be to lear an individual model for each unit n E [N]. That is, run a separate horizontal regression via the Lasso for every unit. This alternative algorithm has sample complexity that scales at least as O(N x s² (22) rather than O (p x (N (N+))p) required by Synthetic Combinations. suffers because does not utilize any structure across units (i.e., the low-rank property of A), whereas Synthetic Combinations captures the similarity between units via PCR.
8

---

Matrix completion: Synthetic Combinations can be thought of as a matrix completion method; esti- mating [=[,,'' is equívalent imputing (2,,r)-th entry of the observation matrix Y E [IU*+]XXX Nx2"" where recall * denotes an unobserved unit-combination outcome. Under the low-rank property (Assumption b)) and various models of missingness (i.e., observation patterns), recent works (see Section 2 for an overview) have established that estimating E| to accuracy (()) requires least O (poly(r/0)) x (N+2)) samples. This is because matrix completion techniques do not leverage the sparsity of On- Moreover, matrix completion results typically report error in the Frobenius norm, whereas we give entry-wise guarantees. This leads to an extra factor of 8 in our analysis as it requires proving convergence for || ax, || rather than ||a;, 1,,-a,,, a,112- Hence, Synthetic Combinations combines the best of both approaches by leveraging both the structure of the potential outcomes and the similarity across units.
on matrix completion [14] 22 6
Natural Lower Bound on Sample Complexity. We provide an informal discussion the lower bound sample-complexity to estimate all x 2" potential outcomes. As established in Lemma F. A has at most non-zero columns. Counting the parameters in the singular value decomposition of A, only r x (N+rs) free parameters are required to be estimated. Hence, a natural lower bound on the sample complexity scales +(Nr+r*s). Hence, Synthetic Combinations only sub-optimal by a factor (ignoring logarithmic factors) of sp and prly(r). As discussed earlier, an additional factor of can be removed if we focus on deriving Frobenius norm error bounds. remains interesting future work to derive estimation procedures that are able to achieve this lower bound.
7 Conclusion
In this work, we formulate a causal inference framework for combinatorial interventions, a setting that is ubiquitous in practice. We propose model that imposes both unit-specific structure, and latent similarity across units. Under this model, we propose an estimation procedure, Synthetic Combinations, that exploits the sparsity and low-rankness of the Fourier coefficients to efficiently estimate all N 2" causal parameters. We formally establish finite-sample consistency of Synthetic Combinations in an observational setting. Our work also naturally suggests future directions for research such as extending Synthetic Combinations to permutations over items (i.e., rankings), providing analysis of Synthetic Combinations that is agnostic to the horizontal regression algorithm used. A related line of work to the question above is also deriving estimation algorithms that can achieve the sample complexity lower bound discussed in Section 6.3
8 Acknowledgements
We thank Alberto Abadie, Peng Ding, Giles Hooker, Devavrat Shah, Vasilis Syrgkanis, and Bin Yu for useful discussions and feedback.
References
[1] A. Abadie, A. Diamond, and Hainmueller. Synthetic control methods for comparative case studies: Estimating the effect of california's 's tobacco control program. Journal of the American statistical Association, 105(490):493-500 2010.
[2] A. Agarwal and R. Singh. Causal inference with corrupted data: Measurement error, missing values, discretization, and differential privacy. arXiv preprint arXiv:2107.02788) 2021.
[3] A. Agarwal, D. Shah, D. Shen, and Song. On robustness of principal component regression. Advances in Neural Information Processing Systems, 32, 2019.
[4] A. Agarwal, D. Shah, and D. Shen. On principal component regression in high-dimensional error-in- errrr-in-v setting. arXiv preprint arXiv:2010. /4449, 2020.
[5] A. Agarwal, D. Shah, and D. Shen. Synthetic interventions. arXiv preprint arXiv:2006.07669 2020.
[6] A. Agarwal, M. Dahleh, Shah, and D. Shen. Causal matrix completion. arXiv preprint arXiv:2109.15154 2021.

---

[7] D. Angrist, G. W. Imbens, and D. B. Rubin. Identification of causal effects using instrumental variables. Journal of the American statistical Association, 91(434):444 455, 1996.
[8] S. Athey, M. Bayati, N. Doudchenko, G. Imbens, and K. Khosravi. Matrix completion methods for causal panel data models. Journal of the American Statistical Association, pages 1-41, 2021.
[9] Bai and S. Ng. Matrix completion, counterfactuals, and factor analysis of missing data. arXiv preprint
2019.
[10] J. Bai and S. Ng. Matrix completion, counterfactuals, and factor analysis of missing data. Journal of the American Statistical Association, 166536))1746-1765 2021.
[11] M. Bertrand and S. Mullainathan. Are emily and greg more employable than lakisha and jamal? a field experiment on labor market discrimination. American economic review, 94(4):991-1033, 2004.
[12] Y. Brandman, A. Orlitsky, and J. Hennessy. A spectral lower bound technique for the size of deci- sion trees and two-level and/or circuits. IEEE Transactions on Computers, 39(2):282-287, 1990.
[13] E. Candes and B. Recht. Exact matrix completion via convex optimization. Communications the theehACh ACM, 55(6): 11-1199, 2012.
[14] E. J. Candes and Y. Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6): 925-936, 2010.
[15] E. J. Candès and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5):2053-2880, 2010.
[16] S. Chatterjee. Matrix estimation by universal singular value thresholding. 2015.
[17] D. Chetverikov, Z.. Liao, and V. Chernozhukov. On cross-validated lasso in high dimensions. The Annals of Statistics, 49(3):1300-1311 1022.
[18] T. Dasgupta, N. S. Pillai, and D. B. Rubin. Causal inference from 2 factorial designs by using potential outcomes. Journal of the Royal Statistical Society: Series B: Statistical Methodology, pages 727-753, 2015.
[19] M. A. Davenport and Romberg. overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing, 10(4):608-63) 2016. doi: 10.1109/SSSSP2211625391000
[20] E. Duflo, R. Glennerster, and M. Kremer. Using randomization in development economics research: A toolkit. Handbook of development economics, 4:3895-3962, 2007.
[21] S. Eriksson and D.-O. Rooth. Do employers use unemployment as a sorting criterion when hiring? evidence from a field experiment. American economic review, 104(3):1014-003) 2014.
[22] Fan, W. Wang, and Y. Zhong, An loo eigenvector perturbation bound and its application to robust covariance estimation. Journal of Machine Learning Research, 18(207): 12,, 2018.
[23] M. Gavish and D. L. Donoho. The optimal hard threshold for singular values is 4/V3. IEEE Trunsuctions on Information Theory, 50(4))5040)5053, 2014.
[24] E. George, W. G. Hunter, and J. S. Hunter. Statistics for experimenters: design, innovation, and discovery. Wiley, 2005.
[25] G. W. Imbens and D. B. Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
[26] M. Karpovsky. Finite Orthogonal Series in Design of Digital Devices. John Wiley & Sons, Inc., Hoboken, NJ, USA, 1976. ISBN 0481931889.
[27] R. Keshavan, Montanari, and S. Oh. Matrix completion from noisy entries. Advances in neural information processing systems, 22, 2009.
10

---

[28] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from few entries. IEEE transactions on information theory, 56(6))2980- 29988, 2010.
[29] W. Ma and H. Chen. Missing not at random in matrix completion: The effectiveness of estimating missingness probabilities under a low nuclear norm assumption. Advances in neural information processing systems, 32, 2019.
[30] R. Mazumder, Hastie, and R. Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. The Journal of Machine Learning Research, 11:2287-2322,, 2010.
[31] E. Mossel, R. O'Donnell, and P. Servedio. Learning juntas. In Proceedings of the shirty-fifth anmual ACM symposium on Theory of computing, pages 206-212, 2003.
[32] S. Negahban and D. Shah. Learning sparse boolean polynomials. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 2032-2036. IEEE, 2012.
[33] L. T. Nguyen, J. Kim, and B. Shim. Low-rank matrix completion: A contemporary survey. IEEE Access, 7,94215-94233 20,-9922,,,999 2019.
[34] R. O'Donnell. Some topics in analysis boolean functions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 569-578, 2008.
[35] B. Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
[36] P. Rigollet and J.-C. Hütter. High dimensional statistics. Lecture notes for course 188997, 813 (814):46, 2015.
[37] P.-A. Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics, 12(1):99-111, 1972.
[38] C. J. Wu and M. S. Hamada. Experiments: planning, analysis, and optimizationn. John Wiley & Sons, 2011.
[39] A. Zhao and P. Ding. Regression-based causal inference with factorial experiments: estimands, model specifications and design-based properties. Biometrika, 109(3):799-815, 2022.

---

A Combinatorial Inference Applications
In this section, we discuss how classical models and applications could relate to our proposed potential outcome model. In particular, we discuss two well-studied models for functions over combinations: low-degree Boolean polynomials and k-Juntas. We also discuss applications such as factorial design experiments and recommendation systems.
Low-degree Boolean Polynomials. A special instance of sparse Boolean functions is low-degree polynomial which we define as follows. For positive integer d dSp, f +R is d-degree polynomial if its Fourier transform satisfies the following for any input E {-1,1}
f(x)= = Σ asXs(x).
Scipl.SIsa
In this setting, we see that S Σ (*) =p". That is, degree d- d-polynomials impose sparsity on the potential outcome by limiting the degree of interaction between interventions.
Applications of low-degree Boolean polynomials. We discuss two applications when the potential outcomes can be modeled as a low-degree Boolean polynomial.
Factorial Design Experiments. Factorial design experiments consist of p treatments where each treatment can take discrete set of values, and units assigned different combinations of these treatments. In the special case that each treatment arm only takes on two possible values, this experimental design mechanism is referred to 2 factorial experiment. Factorial design experiments are widely employed in the social sciences, agricultural and industrial applications (20) A common strategy determine treatment effects this setting assume that the potential outcome only depends on main effects and pairwise interactions with higher-order interactions being negligible
18 38
24] That is, analysts implicitly enforce sparsity of on by setting 2 We refer the reader to 39 for a detailed discussion of various estimation strategies and their validity in different settings. The model we propose (see Assumption (311] captures these various modeling choices commonly used in factorial design experiments by imposing sparsity on a,, Further, as we show later, Synthetic Combinations can adapt to low-degree polynomials without pre-specifying the degree, d, i.e., it automatically adapts to the inherent level of interactions in the data. The additional assumption we make however that there is structure across units, i.e., the matrix A= [amn)xE[N]] is low-rank.
Optimal Team Selection. Another use for combinatorial inference is to find the optimal configuration for team. For example, a soccer team be interested in finding the configuration of positions (i.e., defensive, midfield, offensive players) that leads to the highest winning percentage. Here, units n different teams, and combinations represent possible configurations of the team. The potential
outcomes E { represent the winning percentage for a given team n under a particular configuration π, with the coefficients of a,, representing the effect of different configurations on the win rate. In this setting, enforcing sparsity of ax, via low-degree polynomials may be appropriate because the number of wins may depend on all the players, however only interactions between players of the same type matter while higher-order interactions between players of different types can be negligible. Returning the example of soccer team, the win rate can depend strongly on the synergy of the offensive players, whereas interactions between offensive and defensive players have a smaller effect. Further, since different teams might play in similar ways and have the same optimal configuration, one potential way to capture this structure across teams is by placing a low-rank structure on A.
k-Juntas. Another special case of sparse Boolean functions are k-Juntas which only depend on & < input variables. More formally, a function f "f-1111"-- -R with | = le such that the fourier expansion of f can be represented as follows
IR is a k--junta if there exists a set K [p]
f(x) Σ (xxx((x) SCK
Therefore, in the setting of the k-Junta, the sparsity index 8 S 2 In contrast to low-degree polynomials where the function depends on all p variables but limits the degree of interaction between variables, k-Juntas only depend on & variables but allow for arbitrary interactions amongst them.
12

---

Applications of k-Juntas. We discuss two applications when the potential outcomes can be modeled as k-Junta.
Recommendation Systems. Recommendation platforms such as Netflix are often interested in recom- mending combination of movies that maximizes user's s engagement with a platform. Here, units n can be individual users, and π represents combinations of different movies. The potential outcomes "[Y are the engagement levels for a unit when presented with combination of movies with On representing the preferences for that user. In this setting, user's engagement with the platform may only depend on small subset of movies. For example, user who is only interested in fantasy will only remain on the platform if they are recommended movies such as Harry Potter. Under this be- havioral model, the potential outcomes (i.e., engagement levels) can be modeled non-zero coefficients of an representing the combinations of the movies that affect engagement level for user Our potential outcome observational model (Assumption 3.1 captures this form of spar- sity while also reflecting the low-rank structure commonly assumed when studying recommendation systems. Once again, our results show Synthetic Combinations adapt to JuJuas without pre- specifying the subset of features K, i.e., automatically learns the important features for a given user.
k-Junta with the
Knock-down Experiments in Genomics. A key task in genomics is to identify which set of genes are responsible for a phenotype (i.e., physical trait of interest such as blood pressure) in given individual. To do so, geneticists use knock-down experiments which measure the difference in the phenotype after eliminating the effect of a set of genes in an individual. To encode this process in the language of combinatorial causal inference, we can think of units n as different individuals, an action as knocking a particular gene out, and i as combination of genes that are knocked out. The potential outcomes [E[""""] is the expression of the phenotype for a unit n when the combination of genes π are eliminated via knock-down experiments, and the coefficients of On, represent the effect of different combination of genes on the phenotype. A typical assumption in genomics is that phenotypes only depend on a small set of genes and their interactions. In this setting, we can model this form of sparsity by thinking of the potential outcome function as k-junta, as well as capturing the similarity between the effect of genes on different individuals via our low-rank assumption.
B Proof of Theorem 4.2
AX Proof. Below, the symbol = and DX Definition X, respectively. We begin with the proof of Theorem 4.2 (a). Proof of Theorem 4.2 (a): For a donor unit Z and π e II' HI, we have
imply that the equality follows from Assumption X and
( |
(a + A)
(a x") IA
IA, D
Qa x3) AA,
(au. Σ
B A
Ell,
8 (a )
A D
3 E El + | DJ
EI.
3 E|
A, D)
Tu Ell.
13

---

Proof of Theorem 4.2 (b): For donor unit n [N] 1 and IEII II, we have
, A
(((an X + A
(an:x") 1AA
(an X x") A
auxx"")) |A,
BEZ
W (kxxs")) x")
A,
3.
3.2
1 (ax
te A
UEI
uEZ
B E| u,N. A, D)
NETT EIT,
where the last equality follows from Theorem (a).
C Proof of Theorem 6.6
C.1 Proof of Theorem 6.6 (a)
We have that
= -
(axx))) xx' =a""x")
(d Quixx")
< á -a 1x" 11.00
= -llll_-cck aaull
To finish the proof, we quote the following Theorem which we adapt to our notation.
Theorem C.1 (Theorem 2.18 (6)). Fix the number of samples n 2 2. Assume that the linear model = X where X E Raxd and is sub- sabb-aassian random variable with noise variance 2.. Moreover, assume that 110" I k. and that X satisfies the incoherence condition (Assumption
6.3 with parameter k. Then, the lasso estimator 0L with regularization parameter defined by
2r S0
satisfies
|10 -00- 1 <k log (2g()
(9)
with probability at least 1-5.
Further, as in established in the proof of Theorem 2.18 in 36). 100-0011 5 0
Note
that the set-up of Theorem C.I holds in our setting with the following notational changes: y= Yn.. x x11,,, 0* au.. jL á.. k ==s well our assumptions the regularization parameter A, and that e is sub-gaussian (Assumption 6.2h. Applying Theorem C.I gives us
s2p
||á - -ull1=0p
Substituting this bound into 8 yields the claimed result.
14

---

C.2 Proof of Theorem 6.6 (b)
For any matrix with orthonormal columns, let P1 AA denote the projection matrix on subspace spanned by the columns of A. Define w =P vg w", where V vllI.,) are the right singular
vectors of ? Let A w w" Fl, and D = _ E
- E R Denote
Ag Ag=
1-
In order to proceed, we first state the following result,
Lemma C.2. Let the set-up of T'heorem hold Then, we have
= ww)
Using Lemma C.2 and the notation established above, we have
(i) " ( .wn)
(T)
<I
W (1]
+1
(10)
From Assumption 6.5 follows that 1-) =P | (m
where v (Ta))
are the right singular
vectors of Y (II.. J. Using this in 1T
gives
- $1<A w
( J.P V. mi
A
+I
(11)
Below, we bound the three terms on the right-hand-side of (IT) separately. Before we bound each term, we state a Lemma that will be useful help us establish the results.
Lemma C.3. Let Assumptions 3.1 4.1 6.1 and 6.4.64 Then, |w" 12 125
Bounding Term 1. By Holder's inequality Lemma we have that
KAz w S || ol S w |1 S / |I VTTDE
(12)
This concludes analysis for the first term.
Bounding Term 2. By Cauchy-Schward and Assumption 6.1 we have,
S
||2 vel A
p.m.. A
(13)
We lemma that will help us conclude our bound of Term The proof is given in Appendix D.3
Lemma C.4. Let the set-up of Theorem hold. Then.
[P (Pyan mm) 1bll2
ÖØp
r
A
E
2
I'
3/2
A
In
(14)
I
min
I1
I
II,
1/4
Incorporating the result of the lemma above into
13
gives
Y P
Fa +1(++AEr 1/4
A +
= =
2
2
+r3/2 Ag
(15)
min / II,
11,,11// 1/4
15

---

Bounding Term 3. By Holder's inequality, we have that
( w A2) S
A
S <V A 2
S <
(16)
(17)
We now state proposition that will help us conclude our proof of Term 3. The proof is given in Appendix D.4] Proposition C.5. Let the set-up of Theorem 6. holdd Then, conditioned on A, we have
| II, I
Op
I'
+Ag
(18)
min
As result of Proposition C.S and Lemma
C.3
we have the following bound for Term 3,
K Öp
3/2
E
(19)
min
II V
Collecting Terms. Combining equations
12
15
gives us
-E((
Tn 1+ 1+Ve
1/4)
(20)
= =Op
r min
A
+r AE
II,
[
11 1/4
By Theorem 6.6 (a), we have that
s2p
spp M
A -0-max Op aEZ
-Op
(21)
where we remind the reader that M min M ( into 20
[T.] Substituting and our assumption that
we get
E -
? /spp
p s
pV
In
(22)
M min
M
II,
1/4
D Proofs of Helper Lemmas for Theorem 6.6
In this section we provide proofs of Lemmas C.2 for the Proof of Theorem 6.6
and Proposition C.5 which were required
D.1 Proof of Lemma
By Assumption
3.1 and (b), have
B El((on +
El((an x1
Σ W ((K
NEI
Σ W (x)
WET
= =E Y (T) w
From Assumption 6.5 we have that EY v above completes the proof.
E ( Substituting this into the equation
16

---

D.2
Proof of Lemma
For simplicity, denote E|Y, ( optimization program
= == ( By definition, w" is the solution the following
min WERIZI
1wl22
s.t.
/" ww
(TT..)
(23)
Let Ul
2
(1a))
V (la
denote the SVD of E Y (
Further, let
U (T.)),
E MTa
Mh Jin
denote the rank In truncation of the SVD. Then, define
I
Wr, = V (ll))
( where i is pseudo-inverse. We first show that
T
Wr, is solution
m1
U
(v
V
(lllabra ra (2t (ylla)r (UU (oll [[
Wr,
Σ sunss
Σ
uuug uy B (1ln)))
8j
Yn
T (
U u
= EE| Y (T..))
Next, we bound ||w..] ll using Assumptions 6. and 6.4 as follows
|| 22
(II.
[ (T...)
1 l|2
8r, (B Y r
(
Crn
[
Therefore, have
[w 111 - v [ wr,. 1125 Von.
D.3 Proof of Lemma C.4
First, we introduce some necessary notation required for the proof. Let É [m.]
Then, to establish Lemma C.4 denote the rank Tn SVD of E Y ((l)))
consider the following decomposition:
P Pymun) 4 -P
A +P P.p.... A
We bound each of these terms separately again.
Bounding Term 1. We have
(Pygnw--P -Pp.n A ) Prggn - -Popn Pepmm
|
(24)
lp
Theorem D.1 (Wedin's 's Theorem 337) Given A, E T let (U,V), (Ū, V) denote their respective left and right singular vectors. Further, let (U&, Vx) Efrespectiive, (Ü,, Vv)) correspond to the truncation of (U, V) (respectively, (Ū, (), respectively, that retains the columns correspondng to the top k singular values of A (respectively, B), Let s; represent the i-th singular values of A. Then, BB -
max maxx, -Po, I Pv. (lap)
8k-8
17

---

Applying Theorem D.I gives us
max (P - -P Pozmn) op
P Prg
- -Pegnn 11o)
2| Y
1
[I...)
op
Sy Sr
2 [ 11
E 7
7
8rn 81
2/ [ | A
8.r -ra+1
2 2 II, A
(25)
8re
where the last equality follows from the fact that x rns hence Sr,+1 0. Now, plugging Assumption 6.4| (25) into (24) gives us
max (|
P pggu
P Pymn -P P (qqua)
SCVrnAE
(26)
bp
Substituting the result of Proposition
C.5 and 26 into 24 gives
|| 1| A E
(Pyatn ( - -Ppana) )
=0p
logg((I,,)))) (II, |/)
3/2
min 11, [ +
(27)
To further simplify (27 substitute the result of Lemma C.3
Substituting the Lemma into 27 gives us
(Pryan Poaaam - -P Prrmm)) A = Ō P
A
+ A
(28)
I mint
[
Bounding Term 2. We introduce some necessary notation required to bound the second
Let E Y (n.))
-t Štju0 denote the Tn decomposition of ( Let,
term.
B I
(Tn)) - (T (IT,,)
( Further, define e!l = E eT,, [R!
I
Then to begin, note that since (II.) isometry, we have that
| P
To upper bound [I(V (I.) ) A as follows, consider
b 1A ((V (stth)) ((V/)))
((
>8 ((V=)))
Using the two equations above gives
Y (m))
| pm 21
T
(29)
To bound the numerator observation, we have
note that by definition E Y = EY (T.))
w".
Using this
Mm A
W""E "1"" 11 - ( 1
2 2 -iw:WWE''" ( + 2| 21 ).) E ww (30)
To proceed, we then use the following inequality: for any E Babb WER* we have
|Al|2=
u
mmx|| A sil2 5áb
Σn3 D3
= =|AA| ||
(31)
1=1
18

---

Substituting 30 into (29) and then applying inequality
31 gives
[P P
A
(I (1
-
|| 3 -
1
(TT,.
112 w
(32)
Next, we bound
| ii """" E
To this end, note that Assumption 3.1 implies that
[ | ( -Y-
12
- =I Jo - (1.)) - 1
= =I[E|Y? 1. Iw" Y [mm) 11 +||==*1 1 """""""" -EY (ee) ellh)
(33)
Next, proceed by calling upon Property 4.1 of 4 which states that w given by is the unique solution to the following convex program:
min WER 71
||w||2
S.L. w Eargmin]] (
( - (1..) /
(34)
weR [
Using this property, have that
B Y I
W - (1I.) 1
Jw" (1.))
w" - Y (
-I
- E (1I,,)
w"" Th 112
= =I(B[Y (1.... J.r.
(1I..)
112 + Th. 112 22
(1 (.)..a
- E (1l.)
1) "ew",,lll Th)
(35)
Substituting 33
and
35
into 32
and using 31
Y (TI..)
11 )m) E
2 (In)) mh)
W" 11 2 (1n)) 1)
Then substituting this equation into
32 gives us
PP p S
(1L)
-
Maara E
mm J A ell))))))
(36)
82
We state three lemmas that help us bound the equation above with their proofs given in Appendices D.3. D.3.2 and respecttlll..
Lemma D.2. Let the set-up of Theorem 6.6 hold. Then,
Sr,- Sr, (0p())
Lemma D.3. Let the set-up of Theoueermmm.6 hold. Then for a universal constant C we have
-
)
(Tm) 1T SCVTr
(37)
Lemma D.4. Let the set-up Theoree Then,
(38)
Using the results of three lemmas above, applying Assumption 6.4 in gives us
36
and then simplifying
rr T.AF W
In
1+
E a
PP P A =Op
(39)
[ [1
1/4
19

---

This concludes the proof for term 2. Using the result of Lemma C33 Substituting this into 39 gives us
we have that || S vTn.
3/2
1+
(14AArd"))
A
IP P m 2 20
(40)
VIZI
Collecting Terms. Combining the results of
28 and (40
gives us
|P
m.)
Wole
A E
3/2 A
(L+VETT))) [+
=Op
+
I m
I
[
Z
II 1/4
D.3.1 Proof Lemmal D.2 D.2
We first state Weyl's inequality which will be useful for us establish the results. Theorem D.5 (Weyl's Inequality). Given two matrices A.B E mg let and 8; denote the i-th singular values of A and B respectively. Then, for all, is min mm, we have (s, |s,-;; S || A-
Using Weyl's inequality gives us
15,,
Sya
E
I
E
(T I
AE
Using the inequality above and Assumption
6.4
we have
8r, 2 8r
I A
II AE
8r
8r.
Sra
Then, substituting 21 into the equation above gives that
Sr 2 1 C-CV
s2p2p
Syn
M
holds with high probability for some universal constant C'2 0. Finally, using the assumption that M (F.ssspp yields the claimed result.
D.3.2 Proof I Lemma D.3
For notational simplicity, let Ú, Sr.. V., denote (TTT)) ((T..) (II.)
respectively. For matrix
A, let A., denote its j-th column. Additionally, denote A E y (m.) 1.. -L-EE ( 1.j- Then,
(TI.. ).r -... (T...) I..3
7
YE
IT 1n) 1..g
U
0 ([Y
Ü U -
1.5 Ü.. 0 E Y (f.)) belongs to the subspace spanned by the
We have that column vectors of Ü,., while (Ü,,. oe F (1l)) )., E ( belongs to its orthogonal complement. Therefore,
[ Y (Il)).n 1 - (1l.)) 1,
B m1 ). 11. Ú,, 0. E 1.
Ú 0T 1.g
+
20

---

Bounding
| E|
11 [In))r 7
INا - Ü,, U E[ (1I.))
I 1-3
2
Observe that, we have
Ú 0 E
= 1,,
ÜŪ U E E [ U,
0f
V
(I.)
Ü, Sr V Am
= =R (.)
ej
Therefore, we have
B Y [1 m 1.. Ü. U B
(1.) 7
1..
2
Ü U E. 'n
Y 11, Ü,. Ú E
E
1.j
2
Fr
Ü U
B B
(T... I
E (TT
2
2
71, A
Bounding
| t 1., (T...)
Note
that
E E
(1)) 1.3
U (T.)
( T
(T..) I..g. Using Assumption 6.1 and 26). we have
T 2
Ü., Ú ( 1.s -EY (...) 1,3
Ü, UT
U
(II,))
[E
Y
(II..
Ü, UJ
U
U (II,.)
II,
S Lrr,
for a universal constant C>00. Combining the two bounds gives us,
max A SC A
for a universal constant C' O.
D.3.3 Proof Lemma
The proof of Lemma D.4 follows from adapting the notation of Lemma H.5 [5] to that used in this paper. Specifically, we have the notational changes established in Table well the following changes: pre = Tao "pre pre pre,I = E Y π (Il,... "
pre,zien] = -T = II, where the Lhh. of each equality is the notation used in [5] and the r.h.s is the notation used in this work. Using the notation established, we can use the result of Lemma H.5 in (5) to give us
M1.)a A io
=
+r, + + (VIT,,,
[L)).n ( 11 || |=*ll1)
I
which completes the proof.
D.4 Proof of Proposition C.5
We prove Proposition C.5 which also serves the finite-sample analysis of the vertical regression procedure (step 2 of Synthetic Combinations) done via principal component regression. The proof follows from adapting the notation of Proposition E.3 in [2] to that used in this paper. Specifically, we present table that matches their notation to ours.
Using the table above, we have that the following holds with probability 1 o ((Z)111)))
I 10 ((Z]((()
+AF
min V.I.VI
This completes the proof.
21

---

Notation of [2]
Our Notation
Y n,
X
E|
E| Y
I
3
W
W
A F
Ko,k,ō
Co
Pmvin
Table 2: A summary of the main notational differences between our setting and that of [2]
E Sparsity of Matrix of Fourier Coefficients
In this section, prove that the matrix of Fourier coefficients A has at most columns. This result helps establish that the lower bound on the sample complexity for estimating all N x 2" parameters is O(Nr+r?s) discussed in 6.3
Lemma F.1. The number of nonzero columns of A, which we have denoted p', satisfies p' <rs.
Proof. Let Ar denote the sub-matrix of A formed by taking the first t rows. Further, let p denote the number of nonzero columns of A, We proceed by induction, that is we show for all I,
s-ank 5
In the case of t= either the first row the zero vector, which case pi rrank(A)))) = or else rank(A,) 11 and pi < since the first row is at most s-sparse. Then, for general f, note that
rank 1) I rank S rank
rank(A.)) = rank(A...)) then we must also have pi-1 = p4 and the inductive hypothesis holds. Otherwise, rank(AA;) = (A) 1.
Note that the tth row A has only s nonzero entries, so pl P In this case, we have that
(a)-rak(A))p(--aaa (rank(((A)))))
< < +8) -
where the last inequality holds due to the inductive hypothesis. Since rank(AA) =r, we have that p' Srs. This completes the proof.
22


Reviews:
[{"review_id": "Xbja64kfxb", "reviewer": "Reviewer_Wabz", "summary": "__Disclaimer__: This is my first time reading & reviewing a paper from the field of Combinatorial Interventions. My expertise is in NLP.\n\nThis work studies latent structure across units and combinations of interventions, assuming similar outcomes across units and regular interaction. An estimation procedure, Synthetic Combinations, is proposed, establishing finite-sample consistency under precise conditions. This work also uses methods to reduce errors in variables and provides a possibility of model-agnostic analysis.\n", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* All the proofs and other mathematical explanations are clear, but I'm not able to understand them properly because of no expertise in that field.", "weaknesses": "*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback! We note that we perform additional experiments in the global response on a real-world dataset on recommendation systems for combinations of movies that highlight the benefit of our approach as compared to other methods (e.g., Lasso and matrix completion techniques). Further, we show that the key assumptions required for Synthetic Combinations to work are satisfied in our real-data experiments. We hope that these experiments motivate the empirical utility of Synthetic Combinations, and we will revise the paper to include these results. \n"}, {"review_id": "0qG0c8R0vo", "reviewer": "Reviewer_qb2F", "summary": "The goal paper studies the problem of recovering $N\\times 2^p$ unit-specific outcomes for N heterogeneous units and any combination of p possible interventions from small number of experiments and observations. \nPrior to this work, the problem has been studied under assumptions of latent similarity or regularity in how combinations of interventions interact, as well as some other setups. In the setup when one assumes latent similarity, namely that the matrix of Fourier coefficients across units has rank <= r, the problem is reduced to matrix completion, and hence all causal outcomes can be recovered from $O(poly(r)\\times (N+2^p))$ observations. In the case, when regularity in intervention interactions is assumed it is known that $O(Ns^2p)$ measurement are sufficient, where s is the sparcity parameter of coefficients in the Fourier expansion of the potential outcomes.\nThis paper studies the problem in the case when both latent similarity and intervention regularity is assumed. Under both assumptions the paper proposes an algorithm that recovers all $N\\times 2^p$ causal outcomes from $O(N\\times (s^2 + p))$ measurements. ", "questions": "Can you provide some intuition why you believe that the assumptions needed for Synthetic Cobminatorics to work are expect to hold for real-world datasets?", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The problem of estimating causal outcomes under a combination of interventions is a notoriously hard problem with various applications. One complication is that it is usually expensive\\impossible to run many experiments to measure the effects caused by interventions. Hence, understanding how to set up experiment that will require the minimum amount of measurements is of great importance.\nThis paper proposes an algorithm, called Synthetic Combinatorics, that provably recovers all  $N\\times 2^p$ unit-specific outcomes under $2^p$ interventions under a combination of two widely accepted assumptions from  $O(N\\times (s^2 + p))$, which is a significant improvement over the prior work.\n\nThe paper also provides statistical estimates for the number of samples needed for every experiment to achieve desired accuracy of the recovery.\n\nThe paper is well-written and as far as I can judge is correct, though I did not read the proofs carefully.", "weaknesses": "It is not completely clear how realistic is the scenario when latent similarity and intervention regularity holds simultaneously. I can imagine that in some datasets one or the other may hold, while both assumptions at the same time may not hold. The paper will benefit significantly from experiments on real-world datasets, that can confirm that theoretical assumptions are realistic and we indeed see improvement in the number of measurements needed. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback, and address their concerns as follows. \n\n>It is not completely clear how realistic is the scenario when latent similarity and intervention regularity holds simultaneously. I can imagine that in some datasets one or the other may hold, while both assumptions at the same time may not hold. The paper will benefit significantly from experiments on real-world datasets, that can confirm that theoretical assumptions are realistic and we indeed see improvement in the number of measurements needed.\n\n> Can you provide some intuition why you believe that the assumptions needed for Synthetic Cobminatorics to work are expect to hold for real-world datasets?\n\nWe thank the reviewer for pointing out the role of assumptions in our work. We perform additional experiments in the global response on a real-world dataset on recommendation systems for combinations of movies that highlight the benefit of our approach as compared to other methods (e.g., Lasso and matrix completion techniques). We also show that the key modeling assumptions (e.g., low-rank structure and sparsity) hold in this real-world dataset. Further, the improved performance of our method as compared to other approaches, and in particular, the Lasso, imply the existence of a valid donor set. We hope that these experiments motivate the empirical utility of our methods, and that our theoretical assumptions are grounded. We will revise the paper to include these results.\n\nWe also note that latent similarity is equivalent to placing a low-rank assumption on the matrix of potential outcomes $\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}]$.  That is, the $2^p \\times N$ matrix of potential outcomes $\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}]$ can be written as $\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}] = \\mathbf{\\chi}(\\Pi) \\mathcal{A}^T$, where $\\mathbf{\\chi}(\\Pi)$ is the matrix of Fourier characteristics. Since $\\mathbf{\\chi}(\\Pi)$ is an invertible matrix, $\\text{rank}(\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}] ) = \\text{rank}(\\mathcal{A})$. Hence, placing a low-rank assumption on the Fourier coefficients $\\mathcal{A}$ is equivalent to placing a low rank-assumption on the matrix of outcomes $\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}]$, which is a widely made assumption when studying matrix completion. With regards to intervention regularity and sparsity, we provide a discussion of why these assumptions hold in models used to study relevant applications such as factorial design experiments and recommendation systems in Appendix B.\n\n\n"}, {"review_id": "WocuLlMdSi", "reviewer": "Reviewer_rsAG", "summary": "The paper studies the problem of estimating potential outcomes in the presence of a combinatorial number of intervention choices. Under some assumptions, they propose a two-phased algorithm \"Synthetic Combinations\": first exploit structure across combinations of interventions (via \"horizontal regression\") and then exploit structure across units (via \"vertical regression\"). Experiments are given in the appendix.", "questions": "Line 83:\nBy \"equivalent\", do you mean that they proved equivalence between the two problems via reductions, or do you mean \"equivalent\" in a colloquial sense of the word?\n\nAssumption 3.1:\nAs discussed in the weaknesses, it is unclear to me why this model is interesting or justified. Of course, this work can be appreciated under the restriction of this assumption, but it will greatly weaken the contributions. I am more than happy to increase my \"contribution\" score if the authors provide sufficient justification for the low-rank assumption.\n\nType on Line 183:\ndouble \"exists\"\n\nMotivating example on Line 190:\nI don't understand why this motivates the existence of donor units when the paper has thus far repeatedly claim to allow unobserved confounding. If we allow interventions to be arbitrarily assigned to units, it is unclear why we should believe that donor units exist. The \"correct\" way to justify should be to say that there is an experimental design that ensures the existence of donor units, and then refer to Section 7.\n\nDetermining donor set on Line 246:\nThis feels very ad-hoc. As it is unlikely that donor units will exist if we allow arbitrary experiments, I feel that this paragraph could be removed once the authors reorder their paper to place more emphasis on the experimental design proposed in Section 7.\n\nSubsection on Additional Assumptions:\nI feel that \"so-and-so also has such an assumption\" is not sufficient discussion of assumptions. Firstly, \"so-and-so\" may have the assumptions under different contexts (e.g. see my complaint about low-rank assumption in the Weaknesses section) so it is unclear why such assumption is justified in the setting studied in this paper. Secondly, the discussion should explain \"what goes wrong\" if one particular assumption is violated, or why we should expect any particular assumption to hold in practice. As mentioned several times by now, one \"partial fix\" is to emphasize that experimental design of Section 7 guarantees some assumptions with high probability. That is, \"Synthetic Control\" should be used in conjunction with the experimental design proposed in Section 7.", "limitations": "Nil.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The proposed algorithm is clean and intuitive. It also seems to scale nicely with the number of intervention combinations in experiments.\n\nWhile the theoretical guarantees rely heavily on a bunch of assumptions, Section 7 proposes an experimental design framework which ensures that an important set of assumptions (existence of donor units) will be met with high probability. In fact, I strongly propose that the authors rephrase their paper to highlight this; otherwise it is hard to believe that their work will useable as it is highly unlikely that all the required assumptions are met in practice without having control in assigning interventions to the units.", "weaknesses": "I did not check all the proofs in detail, but I do not see any glaring weaknesses.\n\nThere are a lot of assumptions and it is highly unlikely that all the required assumptions are met in practice (Section 7 helps to mitigate some of these concerns).\n\nI am skeptical about the low-rank assumption on the matrix of Fourier coefficients $A$. While it is true low-rank assumptions are common in prior matrix completion settings, they usually directly consider the matrix at hand and not transform it into the Fourier space first. For example, Lines 655-657 in the appendix writes \"This missingness pattern where outcomes with larger absolute values are observed is common in applications such as recommendation engines, where we are only likely to observe ratings for combinations that users either strongly like or dislike\". The corresponding missingness pattern in the problem studied here is on the $N$-by-$2^p$ matrix. It is unclear to me why it should be believable that the transformed space is low-rank. The authors ought to justify this, ideally with practical examples/settings, or risk diminishing the impact of their contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback, and address their concerns as follows. \n> I am skeptical about the low-rank assumption on the matrix of Fourier coefficients $\\mathcal{A}$. While it is true low-rank assumptions are common in prior matrix completion settings, they usually directly consider the matrix at hand and not transform it into the Fourier space first. \n\n> `Assumption 3.1: As discussed in the weaknesses, it is unclear to me why this model is interesting or justified... __I am more than happy to increase my \"contribution\" score if the authors provide sufficient justification for the low-rank assumption__.\n\nThe $2^p \\times N$ matrix of potential outcomes $\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}]$ can be written as $\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}] = \\mathbf{\\chi}(\\Pi) \\mathcal{A}^T$, where $\\mathbf{\\chi}(\\Pi) $ is the matrix of Fourier characteristics. Since $\\mathbf{\\chi}(\\Pi) $ is an invertible matrix, $\\text{rank}(\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}]) = \\text{rank}(\\mathcal{A})$. Hence, placing a low-rank assumption on the Fourier coefficients $\\mathcal{A}$ is equivalent to placing a low rank-assumption on the matrix of outcomes $\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}]$.  As the reviewer points out themselves, placing low-rank structure on the outcomes $\\mathbb{E}[\\mathbf{Y}_N^{(\\Pi)}]$ is common when studying matrix completion. We discuss this equivalence in line 140, but will make this point clearer in our revision.\n> Determining donor set on Line 246: This feels very ad-hoc. As it is unlikely that donor units will exist if we allow arbitrary experiments...\n\nThis paragraph provides a data-driven method using cross-validation (CV) to identify donor units in observational settings. Our additional experiments in the global response on real-world data demonstrates that we outperform other baselines (e.g., Lasso and matrix completion methods), motivating the existence of a donor set in an observational setting. Moreover, we use the method laid out in this paragraph of CV to select the donor set in our real-world experiments, indicating that this approach can be used in practice. However, the reviewer correctly points out that a donor set is not guaranteed to exist under arbitrary/adversarial observation patterns. We will clarify this in our revision.\n> Motivating example on Line 190: I don't understand why this motivates the existence of donor units when the paper has thus far repeatedly claim to allow unobserved confounding...\n\nWe provide examples that guarantee the existence of donor units in both an experimental (i.e., our motivating example) and an observational setting. In the motivating example, the reviewer correctly points out that our treatment assignment mechanism does not induce unobserved confounding. We will revise the language to reflect this. In the observational setting, we provide an example (deferred to Appendix C for space constraints) where these assumptions hold under a natural model of unobserved confounding. Specifically, our observational example consists of a treatment assignment where only outcomes with large absolute values are seen. This observation pattern is common in recommendation systems where we only observe ratings from users who strongly like or dislike a product. We will  provide a brief description of this example in our revision.\n>Subsection on Additional Assumptions: I feel that \"so-and-so also has such an assumption\" is not sufficient discussion of assumptions. Firstly, \"so-and-so\" may have the assumptions under different contexts (e.g. see my complaint about low-rank assumption in the Weaknesses section) so it is unclear why such assumption is justified in the setting studied in this paper. Secondly, the discussion should explain \"what goes wrong\" if one particular assumption is violated...\n\nThank you for pointing out the role of assumptions in our work. We discuss assumptions from these previous works in order to build upon them, and provide context for our work. However, we agree with the reviewer that we can revise our language to reflect how we discuss our assumptions better. We will revise the text to say that in our analysis, if the assumptions that place unit-specific structure (e.g., sparsity or incoherence of Fourier characteristics) are not satisfied (which can be tested via CV), then the outcomes of the donor units cannot be accurately estimated via the Lasso.  In this case, alternative horizontal regression algorithms to estimate donor unit potential outcomes may be required instead. Similarly, if the assumptions that place structure across units (e.g., low-rank condition) do not hold (which again can be tested by examining the spectra of the matrix), then it is difficult to accurately transfer the outcomes of the donor set to the non-donor units. In the global response we verify that these assumptions do seem to hold in our real-world experiments. Further, we discuss why important applications such as factorial design experiments and recommendation systems naturally induce low-rank and sparse representations in Appendix B.  However, we will discuss the limitations of our approach and \"what goes wrong\" if these assumptions do not hold in our revision.\n> Line 83: By \"equivalent\", do you mean that they proved equivalence between the two problems via reductions, or do you mean \"equivalent\" in a colloquial sense of the word\n\nWe mean colloquially in the sense that both problems can be cast as missing data problems. That is, the central task of both causal inference and matrix completion is to impute unobserved (i.e., missing) outcomes. Specifically, given a ``causal inference estimator'' for imputing missing potential outcomes, one can use such an estimator to directly impute missing entries in the appropriately defined matrix.\nSimilarly, given a matrix completion estimator to impute missing entries in a matrix, one can then use it to impute missing potential outcomes. \n> Type on Line 183: double \"exists\" \n\nThanks! We will fix this. "}, {"review_id": "ctQ87A7Ofw", "reviewer": "Reviewer_z6nm", "summary": "The manuscript introduces a synthetic combinations estimator, which computes causal effects for unseen treatment combinations under some reasonable assumptions on the data generating process. Building on theory from potential outcomes and synthetic interventions, the authors show how to exploit information sharing across units and treatments to identify causal effects in this challenging setting. The proposed two-step algorithm is more efficient and flexible than existing alternatives. ", "questions": "See above.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The topic is timely and interesting. The manuscript is exceptionally clear and well-written, which is greatly appreciated when dealing with dense formalisms. The theoretical results are strong and convincing, rooted in established results while simultaneously going beyond the current state of the art. The analysis is sound and well-motivated. ", "weaknesses": "My main critique of this manuscript is one I am sure the authors will have anticipated – there are no empirical results in the main text! I am aware that 9 pages is tight but the authors could have been more judicious in their selection of what to send to the appendix. I also found the material on CART to be super interesting; a shame to banish this material to the wilderness of Appendices J and K. Fortunately, the final manuscript affords one extra page. I strongly encourage the authors to move Fig. 2 to the main text and expand on this empirical evaluation. Would also be great to shoehorn in some of the CART results, but that may prove difficult. If it is impossible to squeeze everything within the limit, then the authors may want to consider repurposing this manuscript for a journal submission. There is more than enough material here for a very solid journal contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback, and address their concerns as follows. \n\n>My main critique of this manuscript is one I am sure the authors will have anticipated – there are no empirical results in the main text! I strongly encourage the authors to move Fig. 2 to the main text and expand on this empirical evaluation\n\nWe thank the reviewer for highlighting this point about our presentation and empirical evaluation. We perform additional experiments in the global response on a real-world dataset on recommendation systems for combinations of movies that highlight the benefit of our approach as compared to other methods (e.g., Lasso and matrix completion techniques). Further, we show that the key assumptions required for Synthetic Combinations to work are satisfied in our real-data experiments. We will revise the paper to include these real-world experiments, as well as those in the appendix. \n\n> I also found the material on CART to be super interesting; a shame to banish this material to the wilderness of Appendices J and K. Fortunately, the final manuscript affords one extra page. Would also be great to shoehorn in some of the CART results, but that may prove difficult.\n\nWe are glad the reviewer found the material on CART to be interesting! We highlight some results regarding CART in Corollary 6.8 which shows that CART can exploit additional regularity conditions placed on the potential outcomes to allow the sparsity $s$ to scale more quickly (i.e., by a factor of the number of interventions $p$) while achieving consistency. As a result, CART is able to achieve an improved sample complexity of $O(\\text{poly}(r/\\delta) \\times (N + s^2))$ as compared to $O(\\text{poly}(r/\\delta) \\times (N + s^2p))$ samples required when the horizontal regression is done via the Lasso. We will revise the paper to make the benefits of sample complexity of using CART clearer, and also attempt to include more formal results related to CART in the main text. "}]

Author rebuttal:
We thank the reviewers for their positive feedback! A primary concern amongst reviewers was a lack of empirical evaluation
of Synthetic Combinations. Here, we present a real-world data experiment on recommendation systems for sets of movie
ratings to address these concerns, and highlight the empirical effectiveness of our approach. Further, we empirically validate
that the key assumptions (i.e., low-rank condition and sparsity of donor unit Fourier coefficients) required for Synthetic
Combinations to work also hold. We address specific reviewer concerns in rebuttals to each of them separately. 

__Data and Experimental Set-up.__ We use data collected in [2] which consists of user ratings of sets of movies. Specifically, users were asked to provide a rating of 1-5 on a set of 5 movies chosen at random. This resulted in a total of ratings from 854 users over 29, 516 sets containing 12, 549 movies. More details about the data collection process can be found in [2]. Due to computational constraints, we only perform experiments on N = 100 users and 4000 sets of ratings chosen at random. We use 80% of each user’s ratings as the training set, and the other 20% as the test set to evaluate performance.

__Comparison Methods__. As in the numerical simulations in the appendix, we compare Synthetic Combinations to matrix
completion algorithms: SoftImpute [ 1], and IterativeSVD [ 3]. These methods require that the rank of the underlying
matrix be provided as a hyper-parameter. This was chosen via 5-fold cross-validation (CV). We also compare Synthetic
Combinations to the Lasso, where we tune the regularization parameter λ via 5-fold CV. For Synthetic Combinations, we
tune all hyper-parameters via 5-fold CV. Additionally, we choose the donor set via the approached outlined in the manuscript
(see lines 246-257).

__Results.__ We measure the root mean squared error (RMSE) for all methods, and average their results over 3 repetitions. The
RMSE is displayed in the table below. We observe that Synthetic Combinations outperforms all other methods. Further, the
gap between Synthetic Combinations and the Lasso shows the benefit of first estimating the outcomes of the donor set, and
then transferring these estimated outcomes to non-donor units. We hope that this experiment enforces the empirical utility
of our approach, and showcases that our theoretical and modeling assumptions are grounded. We will revise the manuscript
to include these experiments, and expand on this empirical evaluation as well (e.g., investigating performance as a function
of the number of users and sets).

| Method | __Synthetic Combinations__ | SoftImpute | IterativeSVD | Lasso           |
|--------|--------------------------|---------------------|-----------------------|-----------------|
| RMSE   | __0.55__ $\pm$ 0.06 | 0.67 $\pm$ 0.03 | 0.68 $\pm$ 0.02 | 0.80 $\pm$ 0.12 |

__Key Assumptions of Synthetic Combinations hold__. We also verify that two of the key assumptions, the low-rank
condition on the matrix of outcomes and sparsity of donor unit Fourier coefficients, hold in this real-world dataset. For the
low-rank condition, we choose the set of movies that were rated by all users, and and plot its singular value spectrum (using a log-scale for the magnitude of the spectrum) in Figure 1 of the attached PDF. As seen in the plot, it is clear that the matrix of outcomes displays low-rank structure. For the sparsity condition, we investigate the Lasso model that was learnt for the donor units. The RMSE averaged across all the donor units on the test set was 0.51, indicating that the estimated Fourier coefficient is an accurate representation of the true underlying Fourier coefficient. Further, we note that the estimated Fourier coefficients are indeed sparse, and on average only 8.7\% of all possible coefficients are non-zero. 


__References__

[1] R. Mazumder, T. Hastie, and R. Tibshirani. Spectral regularization algorithms for learning large incomplete matrices.
The Journal of Machine Learning Research, 11:2287–2322, 2010.

[2] M. Sharma, F. M. Harper, and G. Karypis. Learning from sets of items in recommender systems. ACM Trans. Interact.
Intell. Syst., 9(4), jul 2019. ISSN 2160-6455. doi: 10.1145/3326128. URL https://doi.org/10.1145/3326128.

[3] O. Troyanskaya, M. Cantor, G. Sherlock, P. Brown, T. Hastie, R. Tibshirani, D. Botstein, and R. B. Altman. Missing
value estimation methods for dna microarrays. Bioinformatics, 17(6):520–525, 2001.



Meta-review: This paper proposes a provably intervention-efficient method for learning potential outcomes for any combination of p interventions. This is a challenging problem, and the reviewers have unanimously recommended acceptance. Please incorporate the changes requested by the authors in the camera ready revision.
Decision: Accept (poster)