Untangling Effect and Side Effect: Consistent Causal Inference in Non-Targeted Trials
Authors: Georgios Mavroudeas
Malik Magdon-Ismail
Kristin Bennett
Jason Kuruzovich
Venue: Submitted to ICLR 2023 (2023)
Keywords: Causal Inference
Non Targeted Trials
Machine Learning
Heterogeneous Treatment Effects

Abstract: A treatment is usually appropriate for some group (the ``sick" group) on whom it has an effect, but it can also have a side-effect when given to subjects from another group (the ``healthy" group). In a non-targeted trial both sick and healthy subjects may be treated, producing
heterogeneous effects within the treated group. Inferring the correct treatment effect on the sick population is then 
difficult, because the effect and side-effect are tangled. We propose an efficient nonparametric approach to untangling the effect and side-effect, called  PCM (pre-cluster and merge). We prove its asymptotic consistency in a general setting and
show, on synthetic data, 
more than a 10x improvement in accuracy over existing state-of-the-art.


UNTANGLING EFFECT AND SIDE EFFECT: CONSIS- TENT CAUSAL INFERENCE IN NON-TARGETED TRIALS
Anonymous authors Paper under double-blind review
ABSTRACT
A treatment is usually appropriate for some group (the "sick" group) whom it has an effect, but it can also have a side-effect when given to subjects from another group (the "healthy" group). In non-targeted trial both sick and healthy subjects may be treated, producing heterogeneous effects within the treated group. Infer- ring the correct treatment effect on the sick population is then difficult, because the effect and side-effect are tangled. We propose an efficient nonparametric approach to untangling the effect and side-effect, called PCM (pre-cluster and merge). We prove its asymptotic consistency in a general setting and show, on synthetic data, more than 10x improvement in accuracy over existing state-of-the-art
INTRODUCTION
A standard approach to causal effect estimation is the targeted randomized controlled trial (RCT), see (8) [33 15 17 23). To test treatment's effect a sick population, subjects are recruited and admitted into the trial based on eligibility criteria designed to identify sick subjects. The trial subjects are then randomly split into a treated group that receives the treatment and control group that receives the best alternative treatment (or a placebo). "Targeted" means only sick individuals admitted into the trial via the eligibility criteria, with the implicit assumption that only a single treatment-effect is to be estimated. This ignores the possibility of treated subgroups among the sick population with heterogeneous effects. Further, one often does not have the luxury of targeted RCT. For example, cligibility criteria for admittance to the trial may not unambiguously identify sick subjects, or one may not be able to control who gets into the trial. When the treatment is not exclusively applied on sick subjects, we say the trial is non-targeted and new methods are needed to extract the treatment effect on the sick, (25). Non-targeted trials are the norm whenever subjects self-select into intervention, which is often the case across domains stretching from healthcare to advertising. We propose a nonparametric approach to causal inference in non-targeted trials, based on pre-cluster and merge strategy.
Assume a population is broken into l groups with different expected treatment effects in each group. Identify each group with the level of its treatment effect, so there are effect levels c 0, 0,,,,.., L 1. For example, a population's subjects can be healthy, e = 0, or sick, e = 1. We use the Rubin- Neyman potential outcome framework, (19). A subject is a tuple s (xx, c, t, v) sampled from distribution D, where x E [0, 1] is a feature-vector such as [age, weight], indicates the subject's level, & indicates the subjects treatment cohort, and y is the observed outcome. The observed out- come is one of two potential outcomes, v if treated or 7 if not treated. We consider strongly ignorable trials: given x, the propensity to treat is strictly between 0 and I and the potential outcomes {v, 7) depend only on x, independent of t. In strongly ignorable trial, one can use the features to identify counterfactual controls for estimating effect. The level e is central to the scope of our work. Math- ematically, e is a hidden effect modifier which determines the distribution of the potential outcomes (c is an unknown and possibly complex function of x). The level e dichotomizes the feature space into subpopulations with different effects. One tries to design the eligibility criteria for the trial to ensure that the propensity to treat is non-zero only for subjects in one level. What to do when the eligibility criteria allow more than one level into the trial is exactly the problem address. Though our work applies to a general number of levels, all the main ideas can be illustrated with just two levels, e E (0, 1). For the sake of concreteness, denote these two levels healthy and sick.

---

A trial samples subjects, $1: $1:..., Sn- If subject is treated, t, 1 and the observed outcome 8/: = Vr otherwise t, = O, and the observed outcome U; (consistency). The treated group is T {i t; = 1]. the control group is C = {i t, 0}, and the sick group is S = {i c; 1}. Our task is to determine the treatment works on the sick, and if there is any side-effect on the healthy. We wish estimate the effect and side-effect, defined as
EFF
ED (V - ū c=
SIDE-FFF
EDDU
0].
Most prior work estimates EFF using the average treatment effect for the treated, the ATT
ATT a a
(2)
which assumes all treated subjects are sick. There are several complications with this approach.
(i) Suppose a subject is treated with probability p(a, c), the propensity to treat. For non-uniform propensity to treat, the treated group has selection bias, and ATT is a biased estimate of EFF. Ways to address this bias include inverse propensity weighting, (18), matched controls, (I), and
23). Alternatively, one learning the outcome function yxr, 1), see for example 2 10 22 i 1/.
can simply ignore this bias and accept that ATT is estimating E
(ii) The second term the RHS in (2) can't 't be computed because don't ton't know the counterfac- tual 6 for treated subjects. Much of causal inference deals with accurate unbiased estimation of a
4 9.. Our goal is not improve counterfactual estimation. Hence, in our experiments, we use off-the-shelf counterfactual estimators.
(iii) (Focus of our work) The trial is non-targeted and some (often most) treated subjects are healthy.
To highlight the challenge in (iii) above, consider simple case with uniform propensity treat, p(z, c) Conditioning on at least one treated subject,
E[ATT] P[sick] x EFF + P[healthh] X SIDE-EFF.
The ATT is mix of effect and side effect and is therefore biased when the treatment effect is heterogeneous across levels. In many settings, for example healthcare, P[sick] < P|]halthy] and the bias is extreme, rendering ATT useless. Increasing the number of subjects won't resolve this bias. State-of-the causal inference packages provide methods to compute ATT, specifically aimed at accurate estimates of the counterfactual average, (B.)). (5) 21). These packages suffer from the mixing bias above. We propose fix which can be used as an add-on to these packages.
Our Contribution. Our main result is an asymptotically consistent distribution independent algo- rithm to extract the correct effect levels and associated subpopulations in non-targeted trials, when the number of effect-levels is unknown. Our main result is Theorem T Assume non-targeted trial has treated group with n subjects sampled from an unknown distribution D. There is algorithm which identifies i effect-levele levels with estimated expected effect f.e in level c, and assigns each subject 8t to a level é which, under mild technical conditions, satisfies:
Theorem 1. All of the following hold with probability 1 ooo()):
(1) i 8= f, i.e., the correct number of effect levels is identified.
(2) A.c =fc ō cl + o(1), i.e., the effect each level is estimated accurately.
(3) The fraction of subjects assigned the correct effect level is o(1). The effect level è is correct if pé, matches, to within d(1), the expected treatment effect for the subject.
For the formal assumptions, see Section 3 Parts (1) and (2) say the algorithm extracts the correct number of levels and their expected effects. Part (3) says the correct subpopulations for each level are extracted. Knowing the correct subpopulations is useful for post processing, for example to understand the effects terms of the features. Our algorithm satisfying Theorem [ given Sec- tion [ The algorithm uses unsupervised pre-cluster and merge strategy which reduces the task of estimating the effect-levels to a I-dimensional optimal clustering problem that provably extracts the correct levels asymptotically
xo. Our algorithm assumes unbiased estimator of counter- factuals, for example some established method (5) 21. In practice, this means one can control for confounders. If unbiased counterfactual estimation is not possible, then any form of causal effect analysis is doomed. Our primary goal is untangling the heterogeneous effect levels, hence we use an off trr-th--helf gradient boosting algorithm to get counterfactuals in experiments (5).
2

---

We demonstrate that our algorithm's performance synthetic data matches the theory. Subpopula- tion effect-analysis is special case of heterogeneous treatment effects (HTE). (12 20: 23). Hence, also compare with X-Leamer, state-of-th the art algorithm for HTE 12) and Bayes optimal pre- diction of effect-level. lations, and has accuracy that more than 10x better for estimating per-subject expected effects. Note, HTE algorithms do not extract subpopulations with effect-levels. They predict effect given the features One can, however, try infer subpopulations from predicted effects. Our algorithm also significantly outperforms Bayes optimal based on individual effects, which suggests that some form of pre-cluster and merge strategy is necessary. This need for some form of clustering has been independently observed in (II chapter 4) who studies variety of clustering approaches in non-distribution independent setting with a known number of levels.
comparison to X-Learner, our algorithm extracts visually better subpopu-
ALGORITHM: PRE-CLUSTER AND MERGE FOR SUBPOPULATION EFFECTS (PCM)
Our algorithm uses nonparametric pre-cluster and merge strategy that achieves asymptotic consis- tency without any user-specified hyperparameters. The inputs are the n subjects s1,..., 8n, where
{ = {(2 tv yes D:)
Note, both the factual y and counterfactual Tt are inputs to the algorithm. To use the algorithm in practice, of course, the counterfactual must be estimated, and for our demonstrations an out-of-the-box gradient boosting regression algorithm from 7 16) to estimate counterfactuals. Inaccuracy in counterfactual estimation will be accommodated in our analysis. The need to estimate counterfactuals does impact the algorithm in practice, due to an asymmetry in most trials: the treated population is much smaller than the controls. Hence, one might be able to estimate counterfactuals for the treated population but not for the controls due to lack of coverage by the (small) treated population. In this case, our algorithm is only run on the treated population.
convenient to define individual treatment effects ITE; (y Y: (21,- - 1), where is the observed factual and Y: the counterfactual (21, = +1 ensuring that the effect computed is for treatment versus no treatment). There are five main steps.
1: [PRE-CLUSTER] Cluster the x; into K O(yn) clusters Zz,..., ., Zx.
2: Compute ATT for each cluster Zj, ATT, = average,; ITE,
3: [MERGE] Group the {ATT;} into i effect-levels, merging the clusters at each level
to get subpopulations X1, Xi. X (X₂ is the union of all clusters at level c.)
4: Compute subpopulation effects A. = average ITE, for 0, i....,--11
5: Assign subjects to effect levels, update the populations X, and expected effects Ao-
We now elaborate on the intuition and details for each step in the algorithm.
Step 1. The clusters in the pre-clustering step play two roles. The first is to denoise individual effects using in-cluster averaging. The second is to group like with like, that clusters should be homogeneous, containing only subjects from accurately estimate a single level's effect (we do not know which). We allow for any clustering algorithm. However,
effect-level. This means each cluster-ATT will
theoretical analysis (for simplicity) uses specific algorithm, box- clustering, based on an s-net of the feature space, One could also use standard clustering algorithm such K Kmmean. We compare box-clustering with K-means in the appendix.
Step 2. Denoising of the individual effects using in-cluster averaging. Assuming clusters are ho- mogeneous, each cluster ATT will approximate some level's effect.
Step 3. Assuming the effects in different levels are well separated, this separation gets emphasized the cluster-ATTs, provided clusters are homogeneous. Hence, we can identify effect-levels from the clusters with similar effects, and merge those clusters into subpopulations. Two tasks must be solved. Finding the number of subpopulations é and then optimally grouping the clusters into i subpopulations. To find the subpopulations, we use ê-means with squared 1-dim clustering error.
3

---

Our algorithm sets i to achieve ê-means most log n/nn n/nn/2d. So,
optimal 1-dim clustering error(e 1) > log m//n 2/2d
optimal 1-dim clustering error(e)
log oogn/n"/> 1/2d
Simultaneously finding é and optimally partitioning the clusters into é groups can be solved using a standard dynamic programming algorithm in ((K*)) time using O(K) space (24). Note, our algorithm will identify the number of effect levels provided such distinct subpopula- tions exist in the data. If it is known that only two subpopulations exist, sick and healthy, then é can be hard-coded to 2.
Step 4. Assuming each cluster is homogeneous and clusters with similar effects found in step 3 are from the same effect-level. the subpopulations formed by merging the clusters with similar effects will be nearly homogeneous. Hence, the subpopulation-ATT. will be accurate estimates of the effects at each level.
Step 5. Each subject æ; is implicitly assigned level è; based on the subpopulation Xe to which it belongs. However, we can do better. By considering the v nearest neighbors to Ii, we can obtain a smoothed effect for 24. We use this smoothed effect to place x, into the subpopulation whose effect matches best, hence placing z; into a level. Unfortunately, running this algorithm for all n subjects is costly, needing sophisticated data structures to reduce the expected run time below (nn)). ). As an alternative, we center an using the average effect over points in this hypercube. This approach requires ((nvTi) run time obtain the effect-level for all subjects, significantly better than O(n²) when n is large. Once the effect-levels for all subjects are obtained, one can update the subpopulations X and the corresponding effect-estimates joc-
a; and smooth x; 's effect
The run time of the algorithm is O(n + nyn) (expected and with high probability) and the output is nearly homogeneous subpopulations which can now be post-processed. An example of useful post- post-processing is a ceature-based explanation of the do not know which subpopulation(s) are the sick ones, hence we cannot say which is the effect and which is the side effect. A post-processing oracle would make this determination. For example, a doctor in medical trial would identify the sick groups from subpoplattioo-dnngrrahhi..
Note that we still
Note. The optimal 1-d clustering can be done directly the smoothed ITES from the (1/n hypereubes centered on each Iú. using the same thresholds in step 3. One still gets asymptotic consistency, however the price an increased run time to Onzzz). This is prohibitive for large n.
3 ASYMPTOTIC CONSISTENCY: PROOF OF THEOREM
To prove consistency, must make our assumptions precise. In some cases the assumptions stronger than needed, for simplicity exposition.
A1. The feature space X is [0, 1] and the marginal feature-disrribution is uniform, D(x) 1. More generally, X is compact and D(x) is bounded, 0 < 6 < D(x) I A (can be relaxed). A2. The level is unknown function of the feature x, h(z). Potential effects depend only on c. Conditioning on c, effects are well separated. Let flc Ep ( ö|c]. Then,
[MCe - Mo 2 K
for c
A3. Define the subpopulation for level as X_ = (c). Each subpopulation has positive measure, P(r E x_ = Be 2 B>
A4. For a treated subject x; with outcome y., it is possible to produce an unbiased estimate of the counterfactual outcome y/. Effectively, we are assuming an unbiased estimate the individual treatment effect ITE; = y/ Dt is available. Any causality analysis requires some estimate of counterfactuals and, in practice, one typically gets counterfactuals from the untreated subjects after controlling for confounders (1)..)
AS. Sample averages concentrate. Essentially, the estimated ITES are independent. This is true in practice because the subjects independent and the counterfactual estimates use predictor learned from the independent control population. For m i.i.d. subjects, let the average of the estimated ITES be e and the expectation of this average be v. Then,
PI[e vl
S e -
4

---

The parameter > is related to distributional properties of the estimated ITES. Higher variance ITE estimates result in y being smaller. Concentration a mild technical assumption requiring the estimated effects to be unbiased well behaved random variables, to which central limit theorem applies. Bounded effects or normally distributed effects suffice for concentration.
A6. The boundary between the subpopulations has small measure. Essentially two subjects that have very similar features will belong to the same level with high probability (the function c = (xx) is not a "random" function). Again, this is a mild technical assumption which is taken for granted in practice. Let us make the assumption more precise. Define an e-net to be a subdivision of X into (1/e)² disjoint hypereubes of side E. A hypercube of an E-net impure if it contains points from multiple subpopulations. Let Nimpure be the number of impure hypercubes in an E-net. Then e Nimpure S age, where >> 0 and is constant. Note, d - is the
require that
of the boundary. In most problems, م p=
n n/2d !. A7. We use box-clustering for the first step in the algorithm. Given n, define E(n) 1 All points in hypercube of an enn)-net form cluster. Note that the number of clusters is approximately vn. The expected number of points in a cluster is nE(n)² 22 vn.
We prove Theorem | via sequence of lemmas. The feature space X = [0, 1] partitioned into levels Xo...., X where X. = h (c) is the set of points whose level is c. Define an e-net that partitions X into N₂ = E hypercubes of equal volume Ed, where E is the side-length of the hypercube. Set 5 1/| n ////2d] Then, N₂- vn(1 O'd/n2/2d)
vn. Each hypercube in the E-net defines cluster for the pre-clustering stage. There are about /n clusters and, since (xx) is uniform, there are about v points in each cluster. Index the clusters in the e-net by E (I...., Ne} and define n2 as the number of points in cluster j. Formally, we have,
Lemma 1. Suppose D(x) 2 ö > O. Then, P(min, n, 2 f > 1- /n
Proof. Fix a hypereube in the e-net. Its volume is ed 2 (1/n2/2djd = 1/V A point lands in this hypercube with probability at least v/. Let Y be the number of points in the hypercube. Then, is a sum of n independent Bernoullis and E[Y] 2 8yn. By a Chernoff bound (14 page 70),
P|Y 8/ S P|Y < [[1]/2] exp(- I exp(-6vn/8).
By a union bound over the N₂ clusters,
P(some cluster has fewer than 8/nn2 points] < N: cxxx((68v//8) S Vnexp(-6vn/8).
The lemma follows by taking the complement event.
For uniform D(x), = 1 and every cluster has at least //n points with high probability. We can now condition this high probability event that every cluster is large. This means that a cluster's ATT is an average of many ITES, which by A5 concentrates at the expected effect for the hypercube. Recall that the expected effect in level is defined as Me = Epiv ø|c]. We can assume, w.l.o.g., that /o0 < 141 .... < 14e-1- Define U/ as the expected average effect for points in the hypercube j and ATT, as the average ITE for points in cluster j. since every cluster is large, every cluster's ATT, will be close to its expected average effect v More formally,
Lemma 2. Pfmax, |ATT, - 21 < 2 logn//0 2 1- 3/2 vieep((88/n/8
Proof. Conditioning on min, n, > 2 / and using A5, we have
P[IATT, Uz1 > 2 log n n/75/n min n, 2 2 18 I exp( (20022ogg = 1/n².
By a union bound, Plmmax/ |ATT, my| > 2 logn/70 76 n miny n, > 1 < Ne/n². For any
events A, B3 by total probability, P[A|| < PIA B + P Therefore,
P|max ATT, Myl > 2
S Ne/n² + Plminn < 10
To conclude the proof, N. vn and Lemma
5

---

A hypercube in the e-net is homogeneous if it only contains points of one level (the hypercube does not intersect the boundary between levels). Let Ne be the number of homogeneous hypercubes for level and Vinqure be the number of hypereubes that not homogeneous, i.c., impure.
Lemma 3. Nimpure S ae N and N₂ 2 Ne(3/A as?).
Proof. A6 directly implies Nimpure I Nee.N. Only the pure level e or impure hypercubes can contain points in level c. Using A3 and gd = 1/N,. we have
S PP & X.) S (N₂ + N s (Ne+ Nc)
The result follows after rearranging the above inequality.
The main tools we need are Lemmas and Let us recap what we have. The cluster ATTS are close to the expected average effect in every hypercube. The number of impure hypercubes is an asymptotically negligible fraction of the hypercubes since E O (22/) Each level has an asymptotically constant fraction of homogeneous hypercubes. This means that almost all cluster ATTS will be close to level's 's expected effect, and every level will be well represented. Hence, if we optimally cluster the ATTS, with fewer than clusters, we won't be able to get clustering error close to zero. With at least clusters, we will be able to get clustering error approaching zero. This the content of the next lemma, which justifies step 3 in the algorithm. An optimal k-clustering of the cluster ATTS produces & centers 0 ..... O2 and assigns each cluster ATT, to center ((TTT,) so that the average clustering eтror err( = [ATT,, ((ATT,))) ( is minimized. Given kt one find an optimal k-clustering in O(N²k) time using O(Ne) space.
Lemma 4. With probability at least 1 - n 3/2
optimal clustering of the ATTS
with E - 1 and & clusters produces clustering errors which satisfy
err(e- 1) 2 (3/2 ace) kk/2 (k/2 2 1ogn/78857
2
log n < for
2²76 16
err(() S (ase(ur-1111 100²
+ - no + a/78//
Proof. With the stated probability, by Lemma all ATTS are within 2 logn//o//ni the expected effect for their respective hypercube. This, together with Lemma 3 enough to prove the bounds.
First, the upper bound on err()). Choose cluster centers Mo..... (4x-1, the expected effect for each level. This may not be optimal, so it gives upper bound the cluster error. Each homogeneous hypercube has expected effect which is of these levels, and its ATT is within 2 /og n of the corresponding μ.. Assign each ATT for a homogeneous hypercube to its corresponding p. The homogeneous hypercubes have total clustering error most log n n(N;- Nimpure) /n. For an impure hypercube, the expected average effect is a convex combination of μo. H1-11 Assign these ATTS to either No or Me-1. with an error at most (1/ / [Mr_ - mo)) Thus,
4 log n(N - -Nimpure) + Nimpure (2/10g log n n//8Vm (18-1 m0))²
Neerr())
7óvn
4 log nNe + -Nimpure Nimpure (MC-1 200
7dvn
The upper bound follows after dividing by Ne and using Nimpure I Ne.
Now, the lower bound on err(e - 1). Consider any & - 1 clustering of the ATTS with centers 0o....,0.... At least N. > (B/A - are) of the ATTS are within 2 2 n/1ō of pe. We also know that Mc+1 Me 2 K. Consider the disjoint intervals [Mc. - n2/2, He + x/2]. By the pigeonhole principle, at least one of these intervals [Mc+ - x/2, Pe+ + x/2] does not contain center. Therefore all the ATTS associated Mew will incur error at least k/2 2 logn//00 when k/2 2 n/ The total error is
N-err(e - 1) New (k/2 26/2-2//10g noogn//dv/n 2 (1
Using No. 2 Ne(A axe)) and dividing by N₂ concludes the proof.

---

Lemma 4 is crucial to estimating the number of levels. The error is 3k² / /4)(1+((1)) for fewer than clusters and (je - (1 + o(1)) for l or more clusters. Any function T(n) that asymp- totically separates these two errors can
as enror threshold. The function should be agnostic to the parameters a, B, K, A, p..... In practice, p and since
1/n'/2d, we have chosen T(n) = log logn/n//24, Since enr(E - 1) is asymptotically constant, L - 1 clusters can't achieve error T r(n) (asymptotically). Since err(E) E O(e*), & clusters can achieve error T r(n) (asymptotically))
Hence, choosing as the minimum number of clusters that achieves error (nn) will asymptotically output the correct number of clusters É, with high probability, proving part (1) of Theorem [
We now prove parts (2) and (3) of Theorem 1 which follow from the accuracy of steps 4 and 5 in the algorithm. We know the algorithm asymptotically selects the correct number of levels with high probability. We show that each level is populated by mostly the homogeneous clusters of that level.
With probability least 1-nz n 3/2 v exp(-6vn//)) asymptotically in n, all the No ATTS from the homogeneous hypercubes of level are assigned to the same cluster in the optimal clustering, and no ATTS from different level's homogeneous hypercubes assigned this cluster.
Lemma 5.
Proof. Similar to the proof of Lemma consider the disjoint intervals [nc- -K/4, Pr + k/4). One center 0g must be placed in this interval otherwise the clustering which is not optimal. All the ATTS for level с are (as n gets large) more than k/2 away from any other center, and at most K/2 away from 0g. which means all these ATTS get assigned to f..
is asymptotically constant,
Similar to Lemma I we can get a high bigh-probabiiiity upper bound of ay on the maximum number of points in a cluster. Asymptotically, the number of points in the impure clusters is Rimpure Ole" vr.N). Suppose these impure points have expected average effect μ (a convex combination of the Me)s). The number points in level e homogeneous clusters is ne E (V(T).)). Even if all impure points are added level c, the expected average effect for the points in level c
E[ITE| aassigned level c]
Tiimpur]/ Reffe
Mr. + O(5))
Timpure
+ The
Part (2) of Theorem follows from the next lemma after setting & ~ 1/n2/2d and p= p.
Lemma 6. Estimate Pe as the average ITE for all points assigned to level e. (the cth order statistic of the optimal centers .g....,0 0011).
Then f.e = pe + OsE + /logn//) with probability - o().
Proof. Apply Chernoff bound. We are taking an average of proportional to points with expec- tation in (3. This average will approximate the expectation to within Vlog n/n with probability - (1). The details are very similar to the proof of Lemma so we omit them.
Part (3) of Theorem now follows because all but the O(e") fraction of points in the impure clusters are assigned a correct expected effect. An additional fine-tuning leads to much as 2x improve- ment in experiments. For each point, consider the e-hypercube centered on that point. By Chernoff bound, each of these n hypercubes has ((vn) points, as in Lemma All but a fraction (ce)) of these are impure. Assign each point to the center 0g that best matches its supercube""smoother ITE, giving new subpopulations X. and corresponding cubpopulation-effeee fae. This EM-style update can be iterated. Our simulations show the results for one E-M update.
4 DEMONSTRATION ON SYNTHETIC DATA
We use 2-dimensional synthetic experiment with three levels to demonstrate our pre-cluster and merge algorithm (PCM). Alternatives to pre-clustering include state-of-the-art methods that directly predict the effect such as meta-learnrs, and the Bayes optimal classifier based on ITES. All methods used a base gradient boosting forest with 400 trees to estimate counterfactuals. The subpopulations in our experiment level 2. We present detailed results with n = 200K. Extensive results can be found in the appendix. Let us briefly describe the two existing benchmarks will compare against.
shown in Figure [ where black is effect-level 0, gray is level 1 and white is
7

---

1.00
The treatment t is distributed randomly between the subjects. The out- come y, conditioned on e and f, is Gaussian with std. dev. 5:
0.75
ytt, c) N (u((..))
0.50
The three sub populations have treatment effects of 0,12. The expected potential outcome for treatment and level (f, e) are:
0.25
M(0.D)
M(L.)) 0,
P(o,1)
P(1,)) 1,
0.00
((0,2) =
P(1.)) = 2.
0.0
0.5
1.0
Figure Subpopulations for synthetic data.
X-learner (12). is meta-leamer that estimates heterogeneous treatment effects directly from ITES. For the outcome and effect models of X-Learner we use a base gradient boosting learner with 400 estimators (6) implemented in scikit-learn (16). For the propensity model use logistic regression.
Bayes Optimal uses the ITES to reconstruct the subpopulations, given the number of levels and the ground-truth outcome distribution y(t, c) from Figure [ The Bayes optimal classifier is: Onayes ITE & 0.5, Cayes = 0.5 < ITE < 1.5, CByyes if 1.5 < ITE. We also use these thresholds reconstruct subpopulations for X-learner's predicted ITES. Note: Neither the thresholds nor the number of levels are available in practice. We compare the benchmark subpopulations re- constructed with these thresholds further showease the power of algorithm's subpopulations, which outperform the competition without access to the forbidden information.
Let c; be the level of subject and ITE, the estimated ITE. The error is |ic, - -ITE, and report the mean absolute error in the table below. Our algorithm predicts a level é; and uses its associated effect je; as ITF, The other methods predict ITE directly for which we compute mean absolute error. As mentioned above, we also show the error for the optimally reconstructed subpopulations, which is not possible in practice, but included for comparison (red emphasizes not available in practice).
n
PCM (this work)
X-Learner
Bayes Optimal
Subpopulations
Predicted-ITE
Subpopulations
Raw-ITE
20K
0.35-10.39
3.04 + 1.11
3.07 +: 2.41
4.57 :: 1.33
4.59 +: 3,49
200k
0.109:10.22
1.44 0.83
1.50 + 1.38
4.22 + 1.28
4.24 + 3.22
2M
0.036110.13
0.34 + 0.47
0.46 + 0.56
4.01 + 1.25
4.03 + 3.05
Our algorithm about 10x better than existing benchmarks even though we not use the forbidden information (number of levels and optimal thresholds). It is also clear that X-learner is significantly better than Bayes optimal with just the raw ITES. The next table shows subpopulation effeets, again red indicates the use of forbidden information on the number of levels and optimal thresholds. The ground truth effects are μi = 0, f1 = 1, /22 =
71
PCM (this work)
X-Learner
Bayes Optimal
nu0
f22
Ag
Ao
A
f02
20K
-0.21
0.91
2.07
-2.5
0.99
4.44
-3.94
1.00
5.99
200K
0.06
0.963
1.95
-1.16
1.01
2.87
-3.62
1.00
5.61
2M
0.04
0.996
1.993
-0.26
0.99
2.07
-3,41
1.00
5.41
Note that üi for X-learner and Bayes optimal are accurate, an artefact of knowing the optimal thresh- olds (not realizable in practice). A detailed comparison of our algorithm (PCM) with X-Learner and Bayes optimal subpopulations is shown in Figure 2 PCM clearly extracts the correct subpopula- tions. X-Learner and Bayes optimal, even given the number of levels and optimal thresholds, does not come visually close to PCM. Note, X-learnr does display some structure but Bayes optimal on just the ITES a disaster. This is further illustrated in the TTE-histogamms in the second row. PCM clearly shows three levels. where X-learner ITES and the raw ITES suggest just one high variance level. The 3rd row shows the confusion matrices for subpopulation assignment. The red indicates of information forbidden in practice, however include for comparison. The confusion
8

---

PCM (this work)
X-Learner
Bayes Optimal
1.00
1.00
1.00
0.75
0.75
0.75
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
2000
3000
1500
1000
500
500
1 ITE-PCM
5.0
-2.5
0.0
2.5
5.0
10
0
10
ITE-XLEARNER
ITE
ClI Pred
C1 Pred
C2 Pred
C0 Pred
C1 Pred
C2 Prod
CD Pred
CI Pred
C2 Pred
C0 True
0.92
0.085
0.0
C0 True
0.58
0.16
0.26
C9 True
0.54
0.07
0.39
True
C2 True
0.0
0.026
0.973
0.15
0.20
0.65
C2 True
0.39
0.074
0.54
Figure 2: Top row. PCM reconstructs superior subpopulations without access to the forbidden information used by X-learner and Bayes optimal (number of levels and optimal thresholds). Middle row. The ITE-histogram for PCM clearly shows distinct effects, while the other methods suggest single high-variance effect. Bottom Row. Subpopulation confusion matrices show that PCM extracts the correct subpopulations. The other methods fail even with the forbidden information.
matrix for PCM without forbidden information clearly dominates the other methods which use for- bidden information. The high noise in the outcomes undermines the other methods, while PCM is robust. In high noise settings, direct of the ITES without some form of pre-clustering fails.
Summary of experiments with synthetic data. Our algorithm accurately extracts subpopulations different effect-levels. Analysis of individual treatment effects fails when there is noise. Our periments show that practice follows the theory (more detailed experiments, including how cluster homogeneity converges 1, are shown in the appendix). We note that there is curse of dimen- sionality, namely the convergence is at rate O(n 1/2d).
CONCLUSION
Our work amplifies the realm of causal analysis to non-targeted trials where the treated population can consist of large subpopulations with different effects. Our algorithm uses plug-and--laay pre- synthetic our analysis, we did not
cluster and merge strategy that provably untangles the different effects. Experiments data show a 10x or more improvement over existing HTTE--benchmars. attempt to optimize the rate of convergence. Optimizing this could lead to improved algorithms. Our work allows causal effects analysis to be used in settings such as health interventions, where wide deployment over mostly healthy population would mask the effect on the sick population. Our methods can seemlessly untangle the effects without knowledge of what sick and healthy mean. This line of algorithms can also help in identifying inequities between the subpopulations. One significant contribution is to reduce the untangling of subpopulation effects to a I-dim clustering problem which we solve efficently. This approach may be of independent interest beyond causal- effect analysis. The effect is just function that takes on levels. Our approach can be used to learn any function that takes on a finite number of levels. It could also be used to learn a piecewise approximation arbitrary continuous function compact set.

---

REFERENCES
[1] Younathan Abdia, KB Kulasekera, Sommath Datta, Maxwell Boakye, and Maiying Kong. Propensity scores based methods for estimating average treatment effect and average treatment effect among treated: a comparative study. Biometrical Journal, 59(5):977-98, 2017
[2] Ahmed M Alaa, Michael Weisz, and Mihacla Van Der Schaar. Deep counterfactual networks with propensity-dropon arXiv preprint arXiv: 05966, 2017.
[3] Susan Athey, Julie Tibshirani, and Stefan Wager. Generalized random forests. The Annals of Statistics, 47(2): 148-1 178, 2019.
[4] Heejung Bang and James M Robins. Doubly robust estimation in missing data and causal inference models. Biometrics, 6144)962,-973, 2005.
[5] Keith Battocchi, Eleanor Dillon, Maggie Hei, Greg Lewis, Paul Oka, Miruna Opreseu, and Vasilis Syrgkanis. EconML: A Python Package for ML-Based Heterogeneous Treatment Ef- fects Estimation. https://github.. http:/ghihhhooo//iiiooooo//ooooo
2019, Version 0.x.
[6] Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pages 118--123,, 2001.
[7] Jerome H Friedman. Stochastic gradient boosting, Computational statistics & data analysis, 38(4):367-378, 2002.
[8] Sander Greenland. Randomization, statistics, and causal inference. Epidemiology, pages 421 1- 429, 1990.
[9] Jens Hainmueller, Entropy balancing for causal effects: A multivariate reweighting method to produce balanced samples in observational studies. Political analysis. 20(1):25-46. 2012.
[10] Jennifer Hill. Bayesian nonparametric modeling for causal inference. Journal of Computa- tional and Graphical Staristics, 20(1):217-240, 2011.
[11] Kwangho Kim. Causal Inference with Complex Data Structures and Non-Standard Effects. PhD thesis, Carnegie Mellon University, 2020.
[12] Sören R Künzel, Jasjeet S Sekhon, Peter J Bickel, and Bin Yu. Metalearners for estimating heterogeneous treatment effects using machine learning. Proceedings of the national academy of sciences, 1 116(10)44556444 4165566--66..600 2019.
[13] Alessandro Liberati, HN Himel, and TC Chalmers. A quality assessment of randomized con- trol trials of primary treatment of breast cancer. Journal of Clinical Oncology, 4(6):942-951, 1986.
[14] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. ACM Computing Surveys (CSUR), 28(1):33-37, 1996.
[15] Judea Pearl. The seven tools of causal inference, with reflections on machine learning. Com- munications of the ACM, 62(3):44-60, 2019.
[16] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning python. the Journal of machine Learning research, 12:2825-2830, 2011.
[17] Paul R Rosenbaum. Interference between units in randomized experiments. Journal of the american statistical association, 102(477):191-200 2007.
[18] Paul R Rosenbaum and Donald B Rubin. The central role of the propensity score in observa- tional studies for causal effects. Biometrika, 70(1):41 -555, 1983.
[19] Donald B Rubin. Causal inference using potential outcomes: Design, modeling, decisions. Journal the American Stafistical Association, 100(469):322-331, 2005.
10

---

[20] Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In International Conference on Machine Learning, pages 3076-3085. PMLR, 2017.
[21] Amit Sharma and Emre Kiciman. Dowhy: An end-to-end library for causal inference. arXiv preprint arXiv:201 1.04216, 2020.
[22] Stijn Vansteelandt and Rhian M Daniel. On regression adjustment for the propensity score. Statistics in medicine, 33(23):4053 4072, 2014.
[23] Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effeets using random forests. Journal of the American Statistical Association, 113(523);1288-122) 1242, 2018.
[24] Haizhou Wang and Mingzhou Song. Ckmeans. 1d. dp: optimal k-means clustering in one dimension by dynamic programming. The R journal, 3(2):29, 2011.
[25] Yuyang Zhang, Patrick Schnell, Chi Song, Bin Huang, and Bo Lu. Subgroup causal effect identification and estimation via matching tree. Computational Statistics & Data Analysis, 159:107188, 2021.

---

A APPENDIX
We provide more detailed experimental results, specifically results for different n (20K, 200K and 2M) and comparison of different clustering methods in the pre-clustering phase: box-only, PCM (box plus step of E-M improvement) and K-means. To calculate the counterfactual for treated subjects, we train gradient boosted forest on the control population.
B CONVERGENCE WITH 77
B. RECONSTRUCTED SUBPOPULATIONS
We show subpopulation reconstructions for n E (20K, 200K, 2MJ.
PCM (this work)
X-Learner
Bayes Optimal
1.00
1.00
1.00
0.75
0.75
0.75
0.50
0.50
0.50
20k
0.25
0.25
0.25
0.00
0.00
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
1.00
1.00
1.00
0.75
0.75
0.75
200k
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
1.00
1.00
1.00
0.75
0.75
0.50
0.50
0.50
2M
0.25
0.25
0.25
0.00
0.00
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Even with just 20K points in this very noisy setting, PCM is able extract some meaningful sub- population structure, while none of the other methods can.
12

---

B.2
ITE HISTOGRAMS
We show the ITE histograms for n E {20K, 200K, 2M
PCM (our work)
X-Learner
ITE
200
200
100
150
150
20k
100
100
50
0
-10
0
10
ITE-PCM
ITE-XLEARNER
ITE
2000
1000
2000
200k
500
1000
5.0
-2.5
0.0
2.5
5.0
-10
ITE-PCM
ITEXXLEARNER
20000
15000
80000
15000
60000
2M
40000
10000
5000
20000
5000
-1
D
1
2
3
-10
0
10
ITE-PCM
ITE-XLEARNER
ITE
13

---

C DIFFERENT PRE-CLUSTERING METHODS
We show the reconstructed subpopulations and effect errors for different pre-clustering methods. Box-clustering without any E-M step is also provably consistent. Our algorithm PCM uses box- clustering followed by an E-M step to improve the subpopulations using smoothed ITES. We also show K-means pre-clustering, for which we did not prove any theoretical guarantees.
Reconstruction.
PCM (this work)
BOX
KMEANS
1.00
1.00
1.00
0.75
0.75
0.50
0.50
0.50
20k
0.25
0.25
0.25
0.00
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
1.00
1.00
1.00
0.75
0.75
0.75
200k
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
1.00
1.00
1.00
0.75
0.75
0.75
0.50
0.50
0.50
2M
0.25
0.25
0.25
0.00
0.00
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Histograms.
14

---

PCM (our work)
BOX
KMEANS
15
100
10
10-
20k
50
5-
5
ITE-PCM
ATE
ATE
1000
15
15
200k
10
500
5-
5
0
0
2
1
2
ITE-PCM
ATE
10000
40
40
2M
5000
20
2
ITE-PCM
ATE
ATE
Error Table.
PCM (this work)
BOX
KMEANS
20K
0.35+
0.50 0.52
0.54 + 0.50
200k
0.109:0.22
0.17 + 0.35
0.20 + 0.37
2M
0.036=0.13
0.078 + 0.214
0.065 = 0.20
15

---

D CLUSTER HOMOGENEITY
To further show how practice reflects the theory, we plot average cluster homogeneity versus n. The cluster homogeneity the fraction of points in cluster that from its majority level. Our entire methodology relies on the pre-clustering step producing vast majority of homogeneous clusters. The rapid convergence homogeneous clusters enables and the corresponding effects via pre-cluster and merge.
identify the correct subpopulations
1.0
0.9
Mean Hmg.
0.8
0.7
0.6
102
103
104
10
106
Number of Points
16


Reviews:
[{"review_id": "qy_4_Qf9YgG", "reviewer": "Reviewer_e3GP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors study the problem of estimating treatment effect heterogeneity when the subgroup indicators are unknown (e.g. sick versus healthy). In particular, the researcher knows that treatment effect heterogeneity only depends on the latent subgroup indicators, which are functions of observed covariates, but does not know how many subgroups there are and which subgroup each individual belongs to. The goal is to recover the correct number of subgroups, the effect for each subgroup, and to assign each individual to the correct subgroup. The authors propose an algorithm based on clustering and prove that it asymptotically achieves these three goals under seven assumptions.", "summary_of_the_review": "I found the solution to be original and therefore significant. I will improve the score if the authors connect the problem statement with previous work (which will actually improve the significance).", "strength_and_weaknesses": "See below", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "luz-X8tgy_", "reviewer": "Reviewer_KbyX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper proposes an algorithm (pre-cluster and merge) to better disambiguate heterogenous treatment effects in non-targeted clinical trials (where there is a hidden confounder of the patient of whether the patient was sick/healthy/other confounder variable-- with same observable patient properties/covariates otherwise. ", "summary_of_the_review": "I am leaning to reject, given the few weaknesses I've noted which I think are significant-- but would recommend accept should these be addressed.", "strength_and_weaknesses": "Strengths\n- Simple methods that works well.\n- Proof of theorem 1 is methodical and clear.\n- Robust to different clustering algorithms\n\nWeaknesses\n- Paper lacks refinement in exposition. For instance, I think a causal graph could have illustrative; defining groups (sick, health etc.) as a hidden confounder. I think cleaning this up and making this clearer would be helpful.\n- The paper lacks a coherent related work section; would appreciate more related work for instance how this relates to estimating HTEs with hidden confounder.\n\nMinor Comments\n- Side effects doesn't seem like the appropriate nomenclature.\n- ATT instead of ATE or CATE if conditional\n\nQuestions\n- Experiments demonstrating performance in imbalanced dataset with respect to the groups would be useful\n- Are there no baselines that are able to incorporate to incorporate using the HTE to identify groups?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RyP2WUNUgb", "reviewer": "Reviewer_7AgW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The purpose of this paper is to provide statistical method to handle the so-called non-targeted trials in which one can’t control the selection of treatment units. Therefore, “some (often most) treated subjects are healthy (p.2)”, and this greatly confounds the estimation of ATT. This paper provides asymptotically consistent algorithm for accurately estimating the treatment effect, and demonstrate its value numerically with synthetic data.", "summary_of_the_review": "The problem that this paper proposes to consider could have been better motivated by using a practical example, and the algorithm looks like a generic algorithm rather than one that centers at the proposed problem. A lack of a real data analysis also undermines the quality of this paper.", "strength_and_weaknesses": "- A stronger justification of the practical significance of non-targeted trials could be greatly beneficial. In particular, although self-selection is indeed a well-known in e.g. natural experiments on digital platforms, it is a bit difficult for me to image self-selection problem would occur in clinical trials, where experimental units are recruited through a careful and rigorous process where doctors are usually involved. Therefore, perhaps a concrete clinical situation should be carefully elaborated, or relevant literature should be cited in the paper to substantiate the importance of this somewhat non-canonical situation. It is also important to show the situation of non-targeted trial is sufficiently common, so that any new method being developed for this situation is worth much attention.\n- The algorithm in Section 2 looks like a algorithm for estimating heterogeneous treatment effect, but HTE is fundamentally different from the clinical sick/healthy subjects setting because usually it is pretty clear whether a patient is sick or healthy.\n- The algorithm is a combination of cluster analysis and off-the-shelf estimation of individual ITE. Both methods are well known, so synthetic analysis could’ve taken less proportion because it is unlikely that the two methods would go wrong, especially the simulation setting is simplistic with dimension 2. On the other hand, real data analysis is necessary in order to evidence the value of the algorithm in application.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject