Sample Constrained Treatment Effect Estimation
Authors: Raghavendra Addanki
David Arbour
Tung Mai
Cameron N Musco
Anup Rao
Venue: NeurIPS 2022 Accept (2022)
Keywords: average treatment effect estimation
individual treatment effect estimation
experimental design
randomized numerical linear algebra
discrepancy minimization
causal inference

Abstract: Treatment effect estimation is a fundamental problem in causal inference. We focus on designing efficient randomized controlled trials, to accurately estimate the effect of some treatment on a population of $n$ individuals. In particular, we study \textit{sample-constrained treatment effect estimation}, where we must select a subset of $s \ll n$ individuals from the population to experiment on. This subset must be further partitioned into treatment and control groups. Algorithms for partitioning the entire population into treatment and control groups, or for choosing a single representative subset, have been well-studied. The key challenge in our setting is jointly choosing a representative subset and a partition for that set.

  We focus on both individual and average treatment effect estimation, under a linear effects model. We give provably efficient experimental designs and corresponding estimators, by identifying connections to discrepancy minimization and leverage-score-based sampling used in randomized numerical linear algebra. Our theoretical results obtain a smooth transition to known guarantees when $s$ equals the population size. We also empirically demonstrate the performance of our algorithms.


Sample Constrained Treatment Effect Estimation
Raghavendra Addanki Adobe Research com com
David Arbour Adobe Research 2rrrbour26@gmaaae com
Tung Mai Adobe Research tuma i @adobe. com
Cameron Musco
Anup Rao Adobe Research
University of Massachusetts Amherst cmusco umass. .ddu
anupraoladobe com
Abstract
Treatment effect estimation is fundamental problem in causal inference. We focus on designing efficient randomized controlled trials, to accurately estimate the effect of some treatment on population of n individuals. In particular, we study sample-constraiined treatment effect estimation, where we must select subset of 8 & n individuals from the population to experiment on. This subset must be further partitioned into treatment and control groups. Algorithms for partitioning the entire population into treatment and control groups, or for choosing single representative subset, have been well-studied. The key challenge in our setting is jointly choosing representative subset and partition for that set.
We focus both individual and average treatment effect estimation, under linear effects model. We give provably efficient experimental designs and corresponding estimators, by identifying connections discrepancy minimization and leverage- score-based sampling used in randomized numerical linear algebra. Our theoretical results obtain smooth transition known guarantees when equals the population size. We also empirically demonstrate the performance of our algorithms.
Introduction
Experimentation has long been held as a gold standard for inferring causal effects since one can explicitly enforce independence between treatment assignment and other variables which influence the outcome of interest. We consider the potential outcomes framework 37 where each individual associated with control and treatment value (also called the polential outcomes) and based on the treatment assignment, we can observe only one of these values. Efficient designs of experimentation for estimating individual treatment effects which measure the difference between treatment and control values for each individual, and the average treatment effect which measures the average individual treatment effect has been well-studied B5 In the absence of assumptions on the functional form of the potential outcomes, the minimax optimal approach for conducting an experiment is to assign individuals treatment or control completely at random, without consideration of baseline covariates (features) 25 However, by considering covariates for each individual, and using additional assumptions of smoothness, substantial gains can be made in terms of the variance of the treatment effect estimate via alternative assignment procedures. The most common approach attempts to minimize imbalance, i.e., the difference between the baseline covariates
treatment
and control groups 6 25 K5
While experimental designs that minimize imbalance increase the power of experiment for a given pool of subjects, there are many practical applications where the experimenter wishes to minimize
Author ordering alphabetical.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the total number of subjects who are placed into the experiment. For example. in medicine, clinical trials may carry nontrivial risk to patients. Within industrial applications, experiments may carry substantial costs in terms of testing changes, which decrease the quality of the user experience, or have direct monetary costs.
In this paper, we examine the problem of selecting subset of s individuals from a larger population and assigning treatments such that the estimated treatment effect has a small error. We consider two different estimands: individual treatment effect (ITE) and average treatment effect (ATE).
A bit more formally, we represent the d-covariates of population of individuals using X E Ra We assume that the treatment and control values, denoted by y', y'yy E R", are functions of the covariates, i.e., y' f'X and y g 5 where 5" < E R" are noise vectors. The ITE for the 7thh individual is y y and ATE is the average of all the ITE values. We further assume a linear model, i.c., the functions f. g are linear in X and 5" The goal is to pick a subset of s individuals and partition this subset into control and treatment groups. For an individual in the treatment group, we measure y and for an individual j in the control, we measure yy. From this small set of measurements, we seek to estimate the ITE or ATE over the full population.
Without parametric assumptions. ITE estimation not feasible A We focus on linear models in particular, since they are important in developing theory. E.g., in the literature optimal designs in active learning, much of the foundational theory built around linear models. Identifying estimators based on linearity assumptions is an active area of study in the causal inference literature [20 50
Our setup is similar to active learning 42], where the goal is to minimize the number of individual labels that we access for solving linear regression or other downstream tasks. The key difference is that we must select both a subset of individuals, and for each can measure only one of two labels: y; or y.. In particular, ITE estimation can be thought of as solving two simultaneous active linear regression problems- one for the treatment outcomes and one for the control outcomes. Thus, standard active learning- based approaches. such as [ 12 SA! fall short. Even when s equals the population size n, i.e., when active learning becomes trivial, our problem does not. We must still pick partition of the full population into treatment and control groups. Overall, sample constrained treatment effect estimation by designing efficient randomized controlled trials has received little attention, compared to various approaches that use observational data, such as 24 39 46
Our Contributions. For ITE estimation, we propose an algorithm using leverage score sampling [51] which is popular approach to subset selection for fast linear algebraic computation. For ATE estimation, we employ a recursive application of a covariate balancing design 20 We provide a theoretical analysis in terms of root mean squared error (ITE) and deviation error (ATE).
Recall that we assume the treatment and control values are linear functions of the covariates plus Gaussian noise, i.e.,''' y' XB8' + +C' and yd X-8 +00 where 5¹ E R" have i.idd mean zero, variance o² Gaussian entries, and B 8 E Rd are coefficient vectors.
For ITE estimation, we give randomized algorithm that selects Odd d) individuals in expectation, using leverage scores, which measure the importance of an individual based on their covariates. Our algorithm obtains, with high probability, root mean squared error O (Vlog d//n (||81|| ||80 [|00 +a)
(see Corollary 3.7 We argue that this is optimal up to constants and vlog d factor, even for approaches that experiment on the full population.
The key challenge in achieving this bound is to extend leverage scores to our simultaneous linear regression setting, ensuring that we do not share samples across the treatment and control effect estimation problems. To do this, we introduce smoothed covariate matrix, whose leverage scores are bounded. This ensures that, when applying independent leverage score sampling, with high probability few individuals are randomly assigned to both control and treatment, and thus removing such individuals from one of the groups does not introduce too much error.
For ATE estimation we give a randomized algorithm that selects at most individuals for treat- ment/control assignment and obtains error of Ô (a/v8- [||S'| || +
[[)ss)))s) where Ö(-) hides
logarithmic factors (see Theorem (.3). The error decreases with increasing values of s and when
n, it matches state-of-the-art guarantees due to Harshaw al. (20)
Our algorithm for ATE estimation is based on covariate balancing. This is popular approach where one attempts to assign similar individuals to the treatment and control groups, to ensure that the

---

observed effect is attributed to the administered treatment alone. Harshaw et al. [20 designed an algorithm by minimizing the discrepancy of an augmented covariate matrix, which achieves low ATE estimation error. To extend their approach to our setting, first, we need to select a subset of individuals that are representative of the entire population, and then balance the covariates. Uniform sampling or importance sampling techniques give high error here. Instead, we employ a recursive strategy, which repeatedly partitions the individuals into two subsets by balancing covariates, and selects the smaller subset to recurse on, until we have selected at most individuals.
We observe that our techniques for ITE and ATE estimation should extend to the setting when the outcomes are non-linear functions of the covariates, which are linear in some dimees-di kernel space. This is immediate for our discrepancy minimization design for ATE, which only requires knowing the pairwise inner products of the covariate vectors. For ITE estimation, leverage score sampling for kernel ridge regression (3 is most likely applicable. Extensions to broader classes of non-linear models are beyond the scope of this work, but they are an interesting future direction.
Finally, in Section []] we provide an empirical evaluation of the performance of our ITE and ATE estimation methods, comparing against uniform sampling and other baselines on several datasets. Our results suggest that our techniques can help reduce the costs associated with running randomized controlled trials substantially using only small fraction of the population.
Other Related Work. For ATE estimation, the most well-studied approaches to experiment design covariate balancing and randomization. A variety of design techniques have been studied based on these approaches, such as blocking [88, matching 23 45,, rerandomization BC (55,, and op- timization 25
Using observational data, treatment effect estimation using covariate regression adjustment and various active learning-bast based sampling techniques have gained recent atten- tion 22
38 46 Compared to ATE, estimating ITE is significantly harder and has received attention There has been a lot of recent work on efficient experimental designs to minimize experimental costs, in various domains, such as causal 28 multi-arm bandits
only recently using machine learning methods 7
13
discovery
4 2
36 and group testing 9
Preliminaries
Notation. We use bold capital letters, e.g., X to denote matrices and bold lowercase letters, e.g., y to denote vectors. We use :] and X[:j] to denote the 7t row and jth column of X respectively, which we always view as column vectors. The jth largest singular value of is denoted by a; (X). For any vector x, the Euclidean norm or the f--norm is denoted by ||x[]
For population of n individuals, we represent each with an integer in [n]] where we denote [n] def (1,2.... ... ,n]. Each individual j E [n] is associated with a treatment and control value, denoted yJ E RR,, respectively. The vectors associated with all n treatment and control values are denoted y" and yo. Additionally, each individual is associated with d-dimensional covariate vector. Combined, they comprise the rows of the covariate matrix X E Raax
In this paper, we consider the finite population framework, where the potential outcomes of in- dividuals are fixed and the randomness is only due to treatment assignment [3). We make the SUTVA assumption, i.e., the treatment outcome value of any individual is independent of treatment assignments of others in the population 48].
Assumption 2.1 (Linearity Assumption). Under the linearity assumption, the treatment and control values linear function of the covariates. Formally, for some B BB' Rdd
y X.8 5 and y = X.8 + 5
where 50 E T are noise vectors, with each coordinate drawn independently from the Gaussian distribution with zero mean and variance o2, iee. (0, We further assume that X. is row- normalized, i.e., [X[i, < 1iii [n].
Definition 2.2 (Individual Treatment Effect). Given population of n. individuals, the individual treatment effect (ITE) of j E [n] is the difference between the treatment and control values:
ITE()) yj y.
3

---

Definition 2.3 (Average Treatment Effect), Given population of n individuals, the averaage treatment effect (ATE), denoted by is the average individual treatment effect:
def Σ (TE())
1 Σ yj y3
TI jEIm]
JEMN
Definition 2.4 (Root Mean Squared Error). For a set of estimated individual treatment effects, ITE(j) for j [ni,, the root mean squared error (RMSE) is defined as:
RMSE def
(TEO) ITEO)
Vn
Definition 2.5 (Leverage Score). Given matrix X E Raxd xd the leverage score of jth now X :l.
denoted by 2 (X)), is defined as:
(x)) def
Xli.:I xli.;).
where + denotes the Moore- Penrose pseudo-inverse.
3 Individual Treatment Effect Estimation
We now describe our algorithm for ITE estimation. The algorithm identifies a subset of the population experiment on, using importance based sampling techniques, that are well-studied in randomized numerical linear algebra [5]]. Missing proof details in this section are presented in Appendix A.
Overview of approach. Under the linearity assumption (Assumption 2. can reformulate the problem of estimating the ITE for every individual as simultaneously solving two linear regression instances: one for control and one for treatment, i.e., we regress y", y on X. However, there are two challenges: I) we would like to solve these regression problems using measurements from just a small subset of individuals and we only have access either the control or treatment measurement y) or y) for any individual in this set.
To tackle the first challenge, we use sampling technique based on the importance of each row in X, captured via leverage score (Defn. 2.5 Intuitively, we want to select individuals (or equivalently rows) that capture the entire row space of X and use them to estimate the ITE of all other individuals. Leverage scores capture the importance of a row in making up the row space. E.g.. if row is orthogonal to all the other rows, it's leverage score will be the maximum value of 1.
Unfortunately, if we apply leverage score sampling independently to the regression problems for y and y rows with high leverage leverage scores may be sampled for both instances. This presents a problem, since we can only read most one of yJ or y To mitigate this issue, we construct smoothed matrix X*, which consists of X projected onto its singular vectors with high singular values. Intuitively, this dampens the effects of high leverage score 'outlier' rows that don't 't contribute significantly to the spectrum of X. Formally, we prove that the maximum leverage score of X* is bounded, which let's us solve our two regression problems via independent sampling. There will be few repeated samples across our subsets, which introduce minimal error.
3.1 Leverage Score Sampling
For some 7 2 O, to be fixed later, we define a smoothed matrix for X, the projection onto singular vectors with high singular values, follows:
Definition 3.1 (Smoothed matrix). Given X gaxd with singular value decomposition X UEVT, let 1 be the set of indices corresponding to singular values greater than v7. i.e., 1 def = {i)
(X) > VT}; we denote d' del [T] Let E = "(T",T") denote the principal sub-matrix of E associated with these large singular values. Similarly, let U Ra V Bdddd be the associated column ma-miciisss of U and V. Then, we define:
X V.

---

Sampling Matrix. Our algorithm will sample individuals, corresponding to rows of the smoothed matrix of X, i.e., X", independently the 2t row included in the sample with some probability a, Let the set of rows sampled be denoted by S. We can associate a sampling matrix W with S. The jth row W is associated with the jth element in the set S (under some fixed order). If the jth element in S is the row for individual for some i E [n), then, :[ is equal to e V Here, O₂ E IR" denotes the 7th standard basis vector. In this way, WX* consists of the subset of rows sampled in S, reweighted by the inverse squareroot of their sampling probabilities, which necessary to keep expectations correct in solving the linear regression.
Algorithm 1 SAMPLING-
Input: Smoothed covariates X E Raxd, sampling probabilities क E [0, 1|".
Output: Estimates for ITE( for each individual E [n]].
1: Add each j E [n]] to set 8 independently, with prob. xy.
2: Add each j E [n] to set 8 independently. with prob. x,,
3: Construct sampling matrix W from 5 using probabilities и.
4: Construct sampling matrix W from S* SS using probabilities x(1 - T)
5: Let B arg miggineex
| 8 "''''''''''l' for = 0,
6: For each j E [n]. let iTT(()) be the jth entry of the vector x -X'
7: return IJT(()) Vj e [n].
Algorithm SAMPLING- We perform row sampling twice, with probabilities proportional the leverage scores of X", to construct two sets , See the discussion below for the exact definition of the sampling probabilities ii which are proportional to the leverage scores of X". These sets are used to estimate the vectors y" and y", respectively. It is possible that a row gets included in both 8 and S1, In that case, we simply remove the row from St. As result, jth row is included in S with probability т (1 n,) for every j E [nx]. We construct sampling matrices W and W using probabilities π and æ (1 л) respectively. Finally, in Algorithm we solve the following linear regressions, for i = 0, 1 separately:
B = arg min
WW'' W'y'l|
BER
Our estimate for each ITE()), denoted by ITE(j) is set to jth entry of the vector X' X Observe that by construction, 5 n S1 is empty. This ensures that we have access to only one of y or y for any individual j in solving the above two subsampled regression problems.
We note that in Algorithm we could remove j from one of So, S", or with equal probability from either of the two sets, and obtain the exact same guarantees.
3.2 Theoretical Guarantees
First, we bound the error due to sampling. Critically, we show that the leverage scores of X*, and in turn the probabilities æ, are bounded by 1/yy. Thus, the sampling probabilities for S Λ T) are not too far from itself.
As we assume the row norms of X are bounded by 1, the row norms of X" are also bounded. Thus, there can be rows in X" that nearly orthogonal all other rows i.e., there can be rows with very high leverage scores. Such rows would lead to small singular values. However, we know that the smallest singular value of X is least 7 In particular, we prove:
Claim 3.2. (x*X) < for all j E [n].
Setting æ. It is well known that if we sample rows of X with probabilities æ proportional to the leverage scores, will obtain (1 = e) relative error approximation for linear regression [4I] The result of Sarlos [4] applies to sampling s rows with replacement, each equal to j with probability / ||||| It is not hard observe that it extends the variant where each row is included in the sample independently with similar probability. Therefore, we have:
Lemma 3.3 (Follows from MЛ). For X xx y R let S S [m] include each j E [n]] independently with probability n, satisfying n 2 min {,, [log(rank(X)) + 111 for
5

---

some large enough constant Let W E Blsixnn be a sampling matrix that includes now ej/ VTz if E S. where Cj E IR" is the jth standard basis vector. Let B = arg mingezd |WX3 Wyl Then, [[|S|| = Σド=1 j and with probability 2 6:
X3- - s ((+e)| min XB - yll
If the n are within constants of the required bound,
B|||]] = O (d d + .
Note that the bound on B||S]] follows from the well known fact that the of leverage scores, is equal to the rank, i.e., 2 = rrrnkk v [T]
The sampling probabilities are set to x, = min {1, 5 (X
Co [log(ran((**)) + 30/c]} for some 3.3 Thus, by the lemma, we will have, with
constant cn 2c, where is the constant in Lemma
probability 29/30, X y (1 +) X go 101
It remains to show that we will have similar guarantee for the control group. The rows in S are included independently with probability π (1 T,). ) we can prove that ; - T;) 2 41 then
2-
Lemma 3.3 will still apply, since we have set = 2c. To do so, it suffices to argue that π 1/2 by setting the parameters appropriately.
Claim 3.4. y 4cp max (ra and min(1.&,(X)) [lo((ran((X) (X (X*)) 30/e]} we have x S 1/2 for every j E [n].
Proof.
jj S 11(x") co. [lo((ran(X*")) 30/e] 1/7 - co [lo[(rak(X")) [ 30/e|] (Claim
collog(rank(X )) 30/e]
1
4Gg max (log(rank(X*)),
we argue that using the smoothed matrix X* introduces an error of V7. Combining all of them, we have the following corollary:
In Appendix A.1
Corollary 3.5. Suppose "y and π set in Claim 3.4 for some sufficiently large constant co-
Then, Algorithm SAMPLING-ITE satisfies, for = 0, 1, with probability at least 14/ 15:
x x (1++) (Vr | [|<' for i 1.
RMSE Guarantees. The root squared error (Defn. 2.4 for the ITE estimates is given by: RMSE - [ -
=0 (y -
we get the following theorem for Algorithm Theorem 3.6. Suppose s 2 120cnd d. There is randomized algorithm that selects subset S [n]] of the population with E||S[] s, and, with probability least 9/10, returns ITE estimates ITE(j) for all j E [ni] with error:
By setting e 120cgd d/s s in Corollary 3.5
(0( max { log d} (|B81| + (1881) + +o).
RMSE
For the sake of simplicity of analysis, used a constant success probability in Theorem 3.6 All our claims can easily be updated with a general failure probability of 8, with a dependence of v 1/5, using Lemma 3.3 The corollary below follows immediately from Theorem 3.6
Corollary 3.7 (Main ITE Error Bound). The root mean squared error obtained by Algorithm 7 minimized when Oid log d) and is given by:
RMSE = o(V Tog
||18'1|
[[001) + +o).

---

Our upper bound on RMSE for Algorithm| increases with s, if grows strictly faster than d'log d asympiotically, i.e., log d). Therefore, to obtain low error, we set c. log d for some constant c, even if the sample constraint allows for larger values. We believe this is an artifact of our analysis. In Section
we observe empirically that the error decreases with increasing 8.
Remark. We observe that the RMSE bound in Corollary 3.7 is nearly optimal, even for algorithms that experiment on the full population. The O(a) term cannot improved by more than constants, consequence of our noise model (see Assumption 2.1. Even if we knew the true B and 8 our RMSE would be (ar).
The term (1|80) || + 1)/ V also necessary. Suppose the matrix X is such that all rows, except row j. are zero vectors. Row is a standard basis vector, i.e., its ith entry is for some Suppose also that B and ( are both independently set to the same standard basis vector with probability 1/2, and set to zero otherwise. Then, with probability 1/2, ITE()) = and with probability 1/2. ITE(j) = =1. No algorithm which observes just one of y yj can obtain expected enror o(1) in estimating ITE(j). That is, no algorithm can obtain RMSE of (n/v/)) o (1) + | (T)
4 Average Treatment Effect Estimation
In this section, we describe our approach for estimating the average treatment effect, under the sample constraint, by building upon recent work on efficient experimental design by Harshaw et al. (20) Missing details from this section are collected in Appendix A.2
Morvitz-Thompson Estimator. Suppose S [ni] is the population assigned to the treatment group and S = [r]] S is the remaining population, i.c., the control group. well-studied estimator for estimating the average treatment effect is the every individual is assigned to S (or S with probability 0.5, then, 7 is defined as follows:
estimator (22), denoted by F. If
7
2
Σ y EES
Σ
y
Algorithm RECURSSVE--OOVRRATT--AAAAA
Input: Covariate matrix X E 2xdd number of experiments to be run s. Output: Estimate for ATE.
1: Sct Z. = X, Tu n.
2: while True do
3:
Zi Z, + GRAM-SCHMIDT- WALK where 8' =
4: if ne S. &thhen
5:
break
6:
size(Z,)) 2 size then
7:
Set Z,+1 Z, and Net1 <- size Z, )
8:
else
9:
Z.41 Z and B441 < size
10:
end
11: t t- +++
12:
end while
13: Use Z Z, to construct the ATE estimator as: F, = 2 (ESez) 8 E)-Ezez, v9
14:
return P..
Harshaw et al. present an experimental design based on the discrepancy minimization [ Their Cram-Schhidt--aal design produces random partition of the population with good balance in every dimension, i.e., control and treatment groups have similar covariates. For the Horvitz-Thompese estimator, they give tradeoff between covariate balancing and robustness (estimation error). Formally, they obtain:
Walk algorithm for
Lemma 4.1 (Proposition in 201). For all A O, with probability at least A the Gram-Schmidle Walk design satisfies: F-T S A. where
exxp
8L
2 mingeR
()
x'4x2" X,3 + -18113)
2

---

Overview of RECTURSVE-CCMMAAATEEB.. the population using the Gram-Schmidt- Walk design (GSW) recursively until the total size of population that we can experiment reduces to 8. In each recursive call, we start by partitioning the available individuals Z, into treatment and control groups, denoted by Z Z, using GSW. Next, we identify the smaller of these two subsets, say Z and recurse on Z We stop after k recursive calls when there are only s individuals to experiment on, i.e., IZ U Z S s. Finally, we construct our estimator F., similar to the Servitz-Thompse estimator, by scaling the treatment and control contributions due to Z and Z using factor 2
Our main idea in Algorithm 2 is to partition
We note that our experimental design ensures that every individual is assigned to treatment or control with equal probability. This implies that expectation, the sizes of the treatment and control groups are equal (for every partitioning). However, when we consider a particular assignment, it is possible that the size of the smaller partition is not exactly half of the population. As result, the total number of samples used might be smaller by a factor of at most 2.
Theoretical Guarantees, Our analysis approach, inspired by the coresct construction for discrepancy minimization [26]. based on the observation that we can obtain good estimates for the contribu- tions Eie mn] y; and Li y.. we obtain a good estimate for ATE (T). Using the next lemma, we argue that after call to GSW algorithm that partitions [rx] into the sets S and S we can obtain additive approximations of Σig(n) y; and Eie(n) y.. Our approximations are the contributions of treatment and control values in S and S scaled appropriately, i.e., Eies+ 2 yt and Eies 2 2-y..
Lemma 4.2. Suppose the Pram--Schmidt- Walk design 1200 partitions the population [n]] into two disjoint groups St and S Under the linearity assumption, with probability 1 - 1/3 log(n/s) s/).. for both the control and treatment groups, the following holds:
2y E2y
Σ JE[N)
y)
s (l/log(16logn//))) (20 + (
for 0,
JESI
Building upon the previous lemma, we argue in Theorem 4.3 that the additive approximation errors obtained from repeated use of GSW in our algorithm in low estimation eπror.
result
Theorem 4.3 (Main ATE Error Bound). The estimator Fa in Algorithm RECURSIVE-COVARIITE BALANCING obtains the following guarantee, with probability at least 2/3:
(Vioglog(a//
B
+ |00
|r. -1=-
Vs
8
Remark. When s n. the above theorem matches the guarantees obtained by GSW design described in Lemma 4.1 Moreover, we obtain better dependence compared sampling s rows uniformly at random and using the y²,y0 values of the sampled rows to estimate the population mean of treatment and control groups in ATE. An application of standard concentration inequalities or the central limit theorem, will yield a multiplicative factor increase in one of the error terms, with a dependence of
Ô (1/s- |||| <||a1 + [8)))). instead of the Ô (1/s (|| + [[ obtained by our algorithm, where X|| denotes the spectral norm of X and Ō()) hides the logarithmic factors.
Experimental Evaluation
In this section, we provide evaluation of our algorithms various semi-synthetic datasets. Missing details about data generation and additional results are collected in Appendix A.3
Data Generation. We evaluate our approaches on five datasets: (i) IHDP. This contains data regarding the cognitive development of children, and consists of 747 samples with 25 covariates describing properties of the children and their mothers, and whose outcome values are simulated 22l [4] (ii) Twins. This contains data regarding the mortality rate in twin births in the USA between 1989- we select twins belonging to same-sex, with weight less
1991 5. Following the work of 32]
8

---

than 2kg, resulting in about 11984 twin pairs, each with 48 covariates. We use the post- testttrettment mortality outcomes of the twins as potential outcomes, (iii) LaLonde. This contains data regarding the effectiveness of a job training program on the real earnings of an individual after completion of the program 29 which is also the outcome value. The corresponding covariate matrix contains 445 rows and 10 covariates per row. (iv) Boston. This is constructed based on the housing prices in the Boston area [19]. The outcome value for each sample represents the median house price. The corresponding covariate matrix contains 506 rows and 12 covariates per row. (v) Synthetic. We construct a covariate matrix X E 20000025 using an approach due to [33.. There a high disparity in leverage score values in X, similar what observe in other datasets. Using random linear function on X and adding Gaussian noise, we generate the potential outcomes.
For IHDP and Twins datasets, we use the simulated values for potential outcomes, similar to Shalit et For the Synthetic dataset, we simulate values for the outcomes using
al. 4 and Louizos et linear functions of the covariate matrix. For Boston, Lalonde datasets, as we have access to only one of the outcome values, we chose to compare our algorithms for fixed shift in treatment effect (i.e.,
the true treatment effect is equal to a constant), similar to Arbour et al. 6
Recussvee
Uniti tesengr-rotreeh Uivregression
Mean Recom Sqpaaren come (0weo)
04
02-
300
Sampe size scqulaten)
perserfage
(a) IHDP
(a) IHDP
0.08
BecLette-CON
Unfaam
Unftmmm
1007
Leverage
0.57
Complete Randonicstion
Unn regressiss
0.0
Ockidb 2010
892
0.09
402
0.20
202
0.01
20
80 Somple stzes cas percentape papu at on!
90
Sampe sizes percentage populadon)
(b) Twins
(b) Synthetic
We compare the performance of various methods for estimating ATE, measured using devia- methods for estimating ITE, measured using RMSE tion error on y-axis, against different sample sizes (as on y-axis, against different sample sizes (as proportion of dataset size) on axaxis.
Figure 1:
We compare the performance of various Figure 2:
proportion dataset size) on z-axis.
Baselines. (i) ATE. We compare the performance of our Algorithm RECURSIVE-
BALANCING (referred to as 'Recursive-GSW") to three baselines: (i) Uniform. We sample rows uniformly at random and assign them to treatment and control groups with equal probability. By scaling the total sum of treatment values from the sampled set by the inverse sampling probability, we estimate the contribution of treatment values in ATE and follow similar procedure for the control

---

group. (ti) Gop. We use the GSW algorithm to partition the full population and return the estimate obtained using the Sorvitz-Thompson estimator for ATE. (iii) Complete Randomization. We partition the population into treatment and control using complete randomization, i.e., with equal probability, and return the estimate obtained using the Horvitz- Torvitz-Thommson estimator for ATE, The last two baselines are overall n. individuals rather than a subset of size 8.
(ii) ITE. We compare the performance of our Algorithm SAMPLING-ITE (referred to 'Leverage') with respect to three baselines: (i) Uniform. We run Algorithm D on X and uniform sampling distribution given by J s/n Vj-(ii) Leverage-nothrent We run Algorithm ] on X, instead of X with the probability distribution y x (j(X)vjj-tii Lin-regression. This captures the best linear fit regression error, i.e., assuming we have access to both y y we regress these vectors on X to obtain B1 f0, and use the resultant ITE estimates XB XBO
Evaluation. To evaluate the performance of average treatment effect estimation (7) on the datasets, we compare the deviation error of the estimator f.. given by [. I for different sample sizes. To evaluate the performance of individual treatment effect estimates, we compare the root mean squared error RMSE (see Defn. 2.4) for different sample sizes.
Results. For every dataset, we run each experiment for 1000 trials and plot the mean using colored line. Also, we shade the region between 30 and 70 percentile around the mean to signify the confidence interval as shown in Figures] [
representing ATE and ITE results respectively.
(i) ATE. For all datasets, we observe that the deviation error obtained by our algorithm labeled as Recursive-GSW in Figure 0 is significantly smaller than that of Uniform baseline. Surprisingly, for the IHDP dataset, our approach is significantly better than Complete-randooizzuie randomization, for all sample sizes, including using just 10% of data. For all the remaining datasets using a sample of size 30%, we achieve the same error (up to the confidence interval) as that of Complete-ranee randomization. Complete randomization is one of the most commonly used methods for experimental design and our results indicate a substantial reduction in experimental costs. For IHDP dataset, a sample size of about 10% of the population is sufficient to achieve similar error that of GSW WSWpppp. For the remaining datasets, we observe that for sample sizes of about 30% of the population, the deviation error obtained by our algorithm is within the shaded confidence interval of the error obtained by GSW-pop. Therefore, for specified error tolerance level for ATE, we can reduce the associated experimental costs using just a small subset of the dataset using our algorithm.
(ii) ITE. For all sample sizes, we observe that the RMSE obtained by our algorithm labeled as Leverage in Figure 2 is significantly smaller than that of all the other basclines, including Uniform and Leverage-nothresh. E.g., we observe that when the sample size is 20% of the population in IHDP dataset, the error obtained by Leverage is at least 50% times smaller than that of Uniform and Leverage-nothee
For the Synthetic dataset, the error obtained by Leverage is extremely close to that of the error due to the best linear fit, Lin-regression (see the zoomed in part of the figure). Similar to ATE results, our algorithms result in a reduction of experimental costs for ITE estimation using only fraction of the dataset.
Conclusion
We study the sample constrained treatment effect estimation problem and give efficient algorithms for both ITH and ATE estimation. Our empirical evaluation shows that our algorithms, using only a fraction of the data, perform well compared to popular baselines that are widely used and require running experiments on the entire population. There are several interesting directions for future work. It would be interesting study sample constrained treatment effect estimation under interference 47] For ITE estimation, we leave it as an open question to extend our approach to give an algorithm with an error growing smaller with s for all values of s I n. Moreover, the vlog d factor in Corollary 3.7 likely can be improved, using recent work which improves standard leverage score sampling bounds by log d factor [T]] yielding a bound that is optimal up to constants. For ATE estimation, the Horvitz- Horvitz-Thomper Thompson estimator can include sampling probabilities different from 0.5. It is an interesting open question to extend our recursive balancing approach when the estimator contains arbitrary probabilities.
10

---

Acknowledgements
Most of this work was done while R. Addanki was student at the University of Massachusetts Amherst and an intern at Adobe. Part of this work was done while R. Addanki was a visiting student at the Simons Institute for the Theory of Computing. This work was supported by a Dissertation Writing Fellowship awarded by the Manning College of Information and Computer Sciences, University of Massachusetts Amherst R. Addanki. R. Addanki and C. Musco were additionally supported in part by NSF grants CCF-2046233 IIS-1763618 CCF-1934846, CCF-1908849, and CCF-1637536, along with Adobe and Google Research Grants.
References
[1] Raghavendra Addanki, Shiva Kasiviswanathan, Andrew McGregor, and Cameron Musco. Efficient intervention design for causal discovery with latents. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 63-73. PMLR, 2020.
[2] Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Intervention efficient algo- rithms for approximate learning of causal graphs. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), pages 151-184, PMLR, 2021.
[3] Ahmed Alaoui and Michael W Mahoney. Fast randomized kernel ridge regression with statistical guarantees. Advances in Neural Information Processing Systems 28 (NeurIPS), 28, 2015.
[4] Ayya Alieva, Ashok Cutkosky, and Abhimanyu Das. Robust pure exploration in linear bandits with limited budget. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 187-195. PMLR, 2021.
[5] Douglas Almond, Kenneth Y Chay, and David S Lee. The costs of low birth weight. The Quarterly Journal of Economics, 12313)110,--188,, 2005.
[6] David Arbour, Drew Dimmery, and Anup Rao. Efficient balanced treatment assignments for experimentation. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 of Proceedings of Machine Learning Research, pages 3070-307 3078. PMLR, 2021.
[7] Susan Athey and Guido Imbens. Recursive partitioning for heterogeneous causal effects. Proceedings of the National Academy of Sciences, 1 113((7):7353-277 7360, 2016.
[8] Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. The gram-schmidt walk: a cure for the banaszezyk blues. In Proceedings of the 50th Annual ACM Symposium Theory of Computing (STOC), pages 587-597, 2018.
[9] Steffen Bondorf, Binbin Chen, Jonathan Scarlett, Haifeng Yu, and Yuda Zhao. Sublinear-time non-adaptive group testing with (k log tests via bit-mixing coding. IEEE Transactions on Information Theory, 133):1559-1570, 2020.
[10) Chun Lam Chan, Pak Hou Che, Sidharth Jaggi, and Venkatesh Saligrama. Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algo- rithms. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1832-1839. IEEE, 2011.
[11] Xue Chen and Eric Price. Active regression via samar-sample sparsification. In Proceedings of the 32nd Annual Conference on Computational Learning Theory (COLT), pages 663-695. PMLR, 2019.
[12] Albert Cohen, Mark A Davenport, and Dany Leviatan. On the stability and accuracy of least squares approximations. Foundations of computational mathematics, 13(5):819-8344 2013.
[13] Peng Ding, Xinran Li, and Luke W Miratrix. Bridging finite and super population causal inference. Journal of Causal Inference, 5(2), 2017.
[14] Vincent Dorie. Npei: Non-parametrics for causal inference.
URL: http://githhu.
com/vdorie/npci,220 2016.

---

[15] Dingzhu Du, Frank K Hwang. and Frank Hwang. Combinatorial group testing and its applica- tions, volume 12. World Scientific, 2000.
[16] Frederick Eberhardt. Causation and intervention. PhD Thesis, Carnegie Mellon University, 2007.
[17] AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 1724-1733. PMLR, 2018.
[18] Robert Greevy, Bo Lu, Jeffrey Silber, and Paul Rosenbaum. Optimal multivariate matching before randomization. Biostatistics, 5(2):263-275, 2004.
[19] David Harrison Jr and Daniel I. Rubinfeld. Hedonic housing prices and the demand for clean air. Journal of environmental economics and management, 5(1):81-102, 1978.
[20] Christopher Harshaw, Fredrik Sävje, Daniel Spielman, and Peng Zhang, Balancing covariates in randomized experiments using the gram-schmide walk. arXiv preprint arXiv:1911.03077 2019.
[21] Jennifer Hill. Bayesian nonparametric modeling for causal inference. Journal of Computa- tional and Graphical Staristics, 20(1):217-240, 2011.
[22] Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47(260))663-6855, 1952.
[23] Kosuke Imai. Variance identification and efficiency analysis in randomized experiments under the matched-pair design. Statistics in medicine, 27(24):4857 4873, 2008.
[24] Andrew Jesson, Panagiotis Tigas, Joost van Amersfoort, Andreas Kirsch, Uri Shalit, and Yarin Gal. Causal-bald: Deep bayesian active learning of outcomes to infer treatment-effects from observational data. Advances in Neural Information Processing Systems 34 (NeurIPS), 34, 2021.
[25] Nathan Kallus. Optimal priori balance in the design of controlled experiments. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80, 07 2017.
[26] Zohar Karnin and Edo Liberty. Discrepancy. coresets, and sketches in machine learning. In Proceedings of the 32nd Anmual Conference on Computational Learning Theory (COLT), pages 1975-1993, PMLR, 2019.
[27] Abbas Kazerouni and Lawrence M Wein. Best arm identification in generalized linear bandits. Operations Research Letters, 35533336 2021.
[28] Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-optimal learning of causal graphs. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1875-1884. JMLR. org, 2017.
[29] Robert J LaLonde. Evaluating the econometric evaluations of training programs with experi- mental data. The American economic review, pages 604-620, 1986.
[30] Xinran Li, Peng Ding, and Donald B Rubin. Asymptotic theory of rerandomization in treatment- control experiments. Proceedings of the National Academy of Sciences, 1 115(37)99157-116) 2018.
[31] Winston Lin. Agnostic notes regression adjustments to experimental data: Reexamining freedman's 's critique. The Annals of Applied Statistics, 7(1):295-318, 2013.
[32] Christos Louizos, Uri Shalit, Joris M Mooij, David Sontag, Richard Zemel, and Max Welling. Causal effect inference with deep latent-variable models. Advances in Neural Information Processing Systems 30 (NeurIPS), 30, 2017.
[33] Ping Ma, Michael Mahoney, and Bin Yu. A statistical perspective on algorithmic leveraging. In Proceedings of the 31 International Conference on Machine Learning (ICML., pages 91-99. PMLR, 2014.
12

---

[34] Michael W Mahoney et al. Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning. 3(2):123-224, 2011.
[35] Kari Lock Morgan and Donald Rubin. Rerandomization to improve covariate balance in experiments. The Annals of Statistics, 40(2):1263-1288) 2012.
[36] Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and non-budgeted causal bandits. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2017-2025. PMLR, 2021.
[37] Jerzy Neyman. On the application of probability theory to agricultural experiments. essay on principles. section 9. Statistical Science, 5(4):465-472, 1923.
[38] Alexander G Nikolaev. Sheldon H Jacobson, Wendy K Tam Cho, Jason J Sauppe, and Edward C Sewell. Balance optimization subset selection (boss): An alternative approach for causal inference with observational data. Operations Research, 61(2):398-477 2013.
[39] Tian Qin, Tian-Zuo Wang, and Zhi-Hua Zhou. Budgeted heterogencous treatment effect estimation. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 8693-8702 PMLR, 2021.
[40] Donald B Rubin. Comment: Randomization analysis of experimental data. Journal of the American Statistical Association, 75(371):591, 1980.
[41] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 153-152. IEEE, 2006.
[42] Burr Settles. Active learning literature survey. 2009.
[43] Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 3076-3085. PMLR, 2017.
[44] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. In Advances in Neural Information Processing Systems 28 (NeurIPS), pages 3195-3203, 2015.
[45] Elizabeth A Stuart. Matching methods for causal inference: review and a look forward. Statistical science: review journal of the Institute of Mathematical Statistics, 25 2010.
[46] liris Sundin, Peter Schulam, Eero Siivola, Aki Vehtari, Suchi Saria, and Samuel Kaski. Active learning for decision-makin from imbalanced observational data. Proceedings of the 36th International Conference Machine Learning (ICML), pages 6046-6055. PMLR, 2019.
[47] Johan Ugander, Brian Karrer, Lars Backstrom, and Jon Kleinberg. Graph cluster randomization: Network exposure to multiple universes. In Proceedings of the 19th ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), pages 329-337, 2013.
[48] Stefan Wager. Stats 361: Causal inference. 2020.
[49] Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113(523):122-11 1242, 2018.
[50] Stefan Wager, Wenfei Du, Jonathan Taylor, and Robert Tibshirani. High-dimensional regres- sion adjustments in randomized experiments. Proceedings of the National Academy of Sciences, 113445):12633-12778 2016.
[51] David P Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description.
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
We do not foresee any direct negative outcomes of our work. As with all theoretical work, our results are based on simplified models of the real world, and this is important keep mind. In designing randomized controlled trials using our algorithms, e.g., medical study, attempting to select individuals or samples based on an error threshold, while ignoring other complex factors would be irresponsible
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
Our code is publicly accessible using the following github repository All the datasets are already public, and we have provided instructions all the parameters along with the experimental setup in Sections 5 and Appendix A.3
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
All our datasets are already public.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "Vh4uYHOW7GB", "reviewer": "Reviewer_8nKe", "summary": "The paper propose novel algorithm to estimate ITE and ATE, in the setup where the budget of targeted persons is constraints. Namely we can only touch s<<n persons, and would like to select these s people to estimate the ITE and ATE the best as possible.", "questions": "- All bounds in probability are or fixed delta, like delta=1/30. why not letting delta unfixed, so that we can check some limit cases, and then expliciting the same result for delta=1/30?\n- the choice of removing j from S^1 if j \\ in S^0 and S^1 sound odd. why so?\n- the case where n=2^k -1 and s=2^(k-1) wil only use s'=2^(k-2) samples, and \"waste\" s-s' samples if I am right?\n- I am not convinced by the explainations on line 234-235. The empirical analysis could be more various to assess this\n- the Horvitz-Thomp!son estimator could be more general, with sampling probablility explicited: A/pi-B/(1-pi). The factor 2 looks very unexplained, and the work could be easily generalized to other pi\n- Remark line 284 is nonsense, if n=s, then previous bound is -infinity\n- code is not working, and would deserve a more precise readme file: \"Requires installing python3, julia and interfacing it with other open source code mentioned in the paper.\"\n-  proof Th A9, does not hold of n is not 2^k\n-  30-70% percentile looks not standard at all why so?\n-  all plots are not vectorised: difficult to read them\n\ntypos:\nline 54 They->The \nline 55 both select-> select both\nline 118 each-> each of them\nline 184 simple-> simply\nline 242 that: bad formulation", "limitations": "ITE and ATE are deeply linked with privacy of data and could lead to privacy leak, especially for ITE.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "originality:\nthis is one of the first approach using other tools such as leverage score sampling, in a potential outcome setup, willing to estimate ITE and ATE.\n\nquality:\nthe mathematical sections are roughly interesting, and the theorem+corrolary are easy to follow. All definitions are clear.\n\nclarity:\nthe paper is roughly smooth to read, although there could be incremental improvement\n\nsignificance:\nthe significance of such sampling constraints could be better motivated, with various concrete example.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SUTTIlQZqP", "reviewer": "Reviewer_ubt5", "summary": "This paper proposed methods to estimate individual treatment effects (ITEs) and average treatment effects (ATEs) under a budget constraint and a linear model assumption on the potential outcomes. The method for estimating ITEs is based on the idea of leverage score  sampling [51] in numerical algebra. The authors apply the idea to sample a limited set of observed vectors to span the column space of the design matrix in the linear regression models for the treated and control outcomes. The authors then extend their method to estimate ATE, building upon the recent Gram-Schmidt work [20] on covariate balancing in experimental design. The authors provide theoretical guarantees and experimental results for their methods in both settings.\n\n", "questions": "In line 184, if one row gets included in both $S^0$ and $S^1$, the authors remove the row from $S^1$. Why not further randomize this with 1/2 and 1/2 probabilities for removing the row in  $S^0$ and $S^1$, respectively.  In your proposal, we are expected to end up with less treated samples.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. I believe the problem studied in this paper is important for treatment effect estimation. \n2. The method based on leverage score is an interesting and good contribution to the field.\n3. The theoretical results under a linear model give good guarantees for the method's performance. \n\nWeaknesses:\n1. The definition 2.2 of ITE is correct, but the return of Algorithm 1 is $\\mathbf X^* \\beta_1 - \\mathbf X^* \\beta_0$, which is the conditional average treatment effect, i.e. the expectation of the ITE conditional on X. In other words, the noise in the outcome goes to 0 after taking the expectation. In fact, the ITE for a given individual is a random variable rather than a parameter, so does take a fixed value. So we can not estimate it exactly, instead, methods should provide a prediction interval to quantify the randomness in ITE.\n2. I don't fully understand the transition from Lemma 3.3 (Follows from [41]) to Theorem 3.6. First Is $S = S^0\\cup S^1$ in Theorem 3.6? I thought this is the case after reading the proof in Appendix. I thought the main idea is still the same about controlling the expectation of $|S|$. Could you explain what has been designed differently for causal inference in which we only observe one outcome for every individual? I feel like the difference is just adding the step with pi(1-pi) probability in Algorithm 1\n3. It is interesting to see a theoretical guarantee on estimation errors. It is unclear to me whether this method still allows users to do \nfinite population inference for the treatment effects, i.e.,  construct valid confidence intervals for the treatment effects.\n4. Section 4 is not very easy to understand if readers (like me) don't know the Gram-Schmidt-Walk design very well. Assuming a linear model seems like a limitation when working with the Horvitz-Thompson Estimator. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "5hVkKZBhWP9", "reviewer": "Reviewer_Jafg", "summary": "This paper proposes two novel algorithms for designing efficient randomized controlled trials (RCT), so that they can be then used to estimate average and individual treatment effects. The algorithms provide ways to sample s << n points and assign them to treatment and control groups. The paper assumes linearity in the outcome functions, and shows both theoretically and empirically, that the proposed algorithms can design RCTs from which the treatment effects can be estimated accurately.\n", "questions": "- In assumption 2.1, it is stated that X is row-normalized. I can understand why we might want the design matrix to be standardized, but do not understand why it should be row-normalized.\n- For the ITE estimation task, the samples are selected based on their leverage score (a sample with a higher leverage score has a higher chance of being selected). It is however not explained why these samples are more important than the other samples with lower leverage scores.\n- In lines 158-160, it is stated that using a smoothed X would help mitigate sampling the same data point for both treatment arms. I don’t see how though. \n- It is stated that \\pi is calculated based on the leverage scores; could you please provide the exact formula for calculating \\pi?\n- Why is S^0 sampled according to \\pi and S^1 according to \\pi(1-\\pi)? Is it because we want to reduce the number of treated subjects as much as possible? Can the reverse yield a viable RCT?\n- Why are there two separate algorithms for designing RCTs, one for ATE and another for ITE? We can calculate accurate ATE from a dataset with which we can estimate accurate ITEs (I understand the reverse may not be true).\n", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is addressing a very interesting and important problem. The findings in this paper can help design RCTs that are more efficient than the conventional method of randomization.\nI however had a very hard time understanding a lot of the concepts discussed in the paper. I wished the paper had been written with more clarity.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept