Learning Treatment Effects in Panels with General Intervention Patterns
Year: 2021

Abstract:
The problem of causal inference with panel data is a central econometric question. The following is a fundamental version of this problem: Let M∗ be a low rank matrix and E be a zero-mean noise matrix. For a ‘treatment’ matrix Z with entries in {0, 1} we observe the matrix O with entries Oij := M∗ ij + Eij + TijZij where Tij are unknown, heterogenous treatment effects. The problem requires we estimate the average treatment effect τ∗ := ∑ ij TijZij/ ∑ ij Zij . The synthetic control paradigm provides an approach to estimating τ∗ when Z places support on a single row. This paper extends that framework to allow rate-optimal recovery of τ∗ for general Z, thus broadly expanding its applicability. Our guarantees are the first of their type in this general setting. Computational experiments on synthetic and real-world data show a substantial advantage over competing estimators.

text: ∑ ij TijZij/ ∑ ij Zij . The synthetic control
paradigm provides an approach to estimating τ∗ when Z places support on a single row. This paper extends that framework to allow rate-optimal recovery of τ∗ for general Z, thus broadly expanding its applicability. Our guarantees are the first of their type in this general setting. Computational experiments on synthetic and real-world data show a substantial advantage over competing estimators.

heading: 1 Introduction
text: Consider that we are given a sequence of T observations on each of n distinct ‘units’. In an econometric context, a unit might correspond to a geographic region with the associated sequence of observations corresponding to some economic time series of interest. In e-commerce, a unit may correspond to a customer, with the associated sequence of observations corresponding to site-visits for that customer over time. For each unit, some subset of its observations are potentially impacted by an intervention. This may correspond to a new economic policy in the econometric example, or the application of a new type of promotion in the e-commerce context. The question at hand is to estimate the ‘average treatment effect’ of this intervention. This is a core question in econometrics.
The problem above can be formalized as follows: Let M∗ ∈ Rn×T be a fixed, unknown matrix and E be a zero-mean random matrix; we refer to M∗ + E as the ‘counterfactual’ matrix with each row corresponding to a distinct ‘unit’. A known ‘treatment’ matrix Z with entries in {0, 1} encodes observations impacted by an intervention. Specifically, we observe a matrix O with entries Oij = M ∗ ij + Eij + TijZij where the Tij are unknown, heterogenous treatment effects.1 Our goal is
to recover the average treatment effect τ∗ = ∑ ij TijZij/ ∑ ij Zij .
1Observable covariates on each unit may also be available; we suppress this aspect here for clarity.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The ‘synthetic control’ paradigm [1, 2] has been a transformative approach to addressing this problem. That setup addresses the special case of this problem where a single unit (say, the first row) is treated; i.e. Z has support on a portion of the first row. The approach is conceptually simple: find a linear combination of the untreated units (i.e. all rows other than the first) that approximate the first row on its untreated entries. One then uses the same linear combination to impute counterfactual values i.e. the entires of M∗ in the support of Z. Under the assumption that M∗ is low rank (and other assumptions), one can show that this approach recovers τ∗.
Applications like the e-commerce setup alluded to earlier require we allow for more general intervention patterns, i.e. allow for general Z as opposed to the single row (or block) support required in synthetic control. A tantalizing possibility, first raised by [3], is treating entries of M∗ in the support of Z as missing and applying matrix completion techniques to impute these counterfactual values. This viewpoint has the benefit of making no assumptions on the treatment effects and yields algorithms that do not require any special structure for Z. However, it is unclear that counterfactual recovery – which is equivalent to matrix recovery with general missingness patterns – is actually possible via such a method, so that recovery guarantees are typically unavailable.

heading: 1.1 This Paper
text: Succinctly, we develop an estimator that recovers the average treatment effect under provably minimal assumptions on Z. This is made possible by a new de-biasing identity and an extension of the entrywise uncertainty quantification analysis of [4, 5] to general non-random missingness patterns that is of independent interest.
In providing context for our contributions, it is worth asking what one can hope for in this problem. In addition to requiring that M∗ have low rank (say r), it is clear that we cannot in general expect to recover τ∗ absent assumptions on the treatment matrix Z. For instance, we must rule out the existence of a rank r matrix M ′, distinct fromM∗ for whichM ′ = M∗+γZ for some γ 6= 0, or else identifying τ∗ is impossible even if E is identically zero (we could rule this out if Z were not in the tangent space of M∗). Separately, unlike matrix completion, we actually observe M∗ij + Tij +Eij on treated entires. If the heterogeneity in treatment effects is too large, however, it is unclear that these observations are of much value. Thus, in addition to benign assumptions on M∗ and E, we make a set of assumptions on (A) the projection of Z onto the tangent space of M∗ and (B) the heterogeneity in treatment effects. Against this backdrop, we make the following contributions:
Rate Optimal Estimator: We construct an estimator that achieves rate optimal guarantees for the recovery of the average treatment effect τ∗ (Theorem 1) with general treatment patterns. We show under additional assumptions that our estimator is asymptotically normal (Theorem 2).
Minimality of Assumptions: Should the conditions we place on the projection of Z onto the tangent space of M∗ be violated by an amount that grows small with problem size, we show no algorithm can recover τ∗ even with homogeneous treatments (Proposition 2). Our assumptions on heterogeneity are also shown to be minimal, and satisfied by extant models in the synthetic control literature.
General Treatment Patterns Work: We show that our assumptions on Z are satisfied by general treatment patterns, e.g., requiring that at least a constant fraction of entries are not treated or matrices Z with rank polynomially larger than the rank of M∗.
Empirical Performance: We show both for synthetic and real data that our estimator provides a material improvement in empirical performance relative to available alternatives, including matrix completion based estimators and, where applicable, state-of-the-art synthetic control estimators.

heading: 1.2 Related Literature
text: The synthetic control literature pioneered by [1, 2] has grown to encompass sophisticated learning and inferential methods; see [6] for a review. [7, 8, 9] consider a variety of regularized regression techniques to learn the linear combination of untreated units that yields a synthetic control. [10, 11, 12] consider instead the use of principal component regression techniques. [13] propose alternative approaches to imputing counterfactuals by averaging across both untreated units (rows) and time (untreated columns). [14, 15] address inferential questions that arise in synthetic control with the latter providing a permutation test that is generally applicable.
Matrix completion methods present a means to allow for inference with general treatment patterns. [3] are among the first to study this, but provide no guarantees on recovering the average treatment effect. Alternatively methods that do provide guarantees on the recovery of treatment effects via matrix completion tend to make strong assumptions: [16] effectively assume that Z has support on a block (so that traditional synthetic control techniques could also apply), [17] make stationarity assumptions on M∗ and require it to be zero-mean and [18] assume that Z has i.i.d. entries (wherein a trivial estimator of the average treatment effect is also applicable).
A distinct (and common) setting for treatment effect estimation presents us with a single observation per unit and a rich set of observed covariates on these units. These observed covariates roughly ensure exchangeability of units across interventions within covariate strata. ML has been broadly used in this setting; eg. [19, 20, 21]. In contrast for our problem, one could view these covariates as latent.
Our estimation procedure begins with first computing a ‘rough’ estimate of the treatment effect via a natural convex estimator; [22, 23, 24] are empirical studies that have uses this estimator. Crucially, we provide a new de-biasing technique that allows for recovery guarantees and exhibits a significant performance improvement relative to this rough estimate. It is also worth noting that this convex estimator also finds application in the related problem of panel data regression; see [25, 26, 27]. State of the art methods there effectively require that Z is dense.
Whereas work on matrix completion with non-standard observation patterns [28, 29, 30, 31] exists this is by and large not obviously useful or applicable to our problem. Instead, we build on a recent program to bridge convex and non-convex formulations for matrix completion [4] and RobustPCA [5]. That work has provided a pioneering analysis of entry-wise guarantees and uncertainty quantification for convex matrix completion estimators wherein entries remain missing at random. Our work here may be viewed as extending that program to a broad class of non-random missingness patterns, a contribution of important independent interest.

heading: 2 Model and Algorithm
text: We begin by formally defining our problem; we in fact present a generalization to the problem described in the previous section, allowing for multiple treatments. Let M∗ ∈ Rn×n be a fixed rank-r matrix with singular value decomposition (SVD) denoted by M∗ = U∗Σ∗V ∗>, where U∗, V ∗ ∈ Rn×r have orthonormal columns, and Σ∗ ∈ Rr×r is diagonal with diagonal entries σ1 ≥ · · · ≥ σr > 0.2 Let σmax := σ1, σmin := σr and κ := σmax/σmin be the condition number of M∗. There are k treatments that can be applied to each entry, and for each treatment m ∈ {1, . . . , k}, we are given a treatment matrix Zm ∈ {0, 1}n×n which encodes the entries which have received the mth treatment (0 meaning no treatment, and 1 meaning being treated).3 We then observe a single matrix of outcomes:
O := M∗ + E + k∑
m=1
Tm ◦ Zm
(◦ is the Hadamard or ‘entrywise’ product), where each Tm ∈ Rn×n is an unknown matrix of treatment effects, and E ∈ Rn×n is a (possibly heterogeneous) random noise matrix. Finally, let τ∗ ∈ Rk be the vector of average treatment effects, whosemth value is defined as τ∗m := 〈Tm, Zm〉/‖Zm‖1 and let δm = Tm ◦ Zm − τ∗mZm be associated ‘residual’ matrices. Our problem is to estimate τ∗ after having observed O and Z1, . . . , Zk.
It is worth noting that the representation above is powerful: for instance, it subsumes the setting where the intervention on any entry is associated with a {0, 1}k-valued covariate vector, and the treatment effect observed on that entry is some linear function of this covariate vector plus idiosyncratic noise. Recovery of τ∗ is then equivalent to recovering covariate dependent heterogeneous treatment effects.
Our problem also subsumes the synthetic control setting where k = 1 and Z1 must place support on a single row; the focus of our later analysis will be the case where Z1 is allowed to be general.
2Note that in contrast to the previous section, we are now assuming square matrices (i.e. n = T in the notation of the previous section). This is purely to simplify the notation – for a rectangular n-by-T matrix, all of our theoretical guarantees hold if one swaps n with min{n, T}.
3We allow for multiple treatments to be applied to an entry.
The assumptions that we will need to impose in order to state meaningful results can be divided into two groups. The first are assumptions on M∗ and E that are, by this point, canonical in the matrix completion literature: Assumption 1 (Random Noise). The entries of E are independent, mean-zero, sub-Gaussian random variables with sub-Gaussian norm bounded by σ: that is, ‖Eij‖ψ2 ≤ σ for every i, j ∈ [n]. Assumption 2 (Incoherence). M∗ is µ-incoherent:
‖U∗‖2,∞ ≤ √ µr/n and ‖V ∗‖2,∞ ≤ √ µr/n,
where ‖ · ‖2,∞ denotes the maximum `2-norm of the rows of a matrix.
In addition to these standard conditions onM∗ andE which we will assume throughout this paper, we will also need to impose conditions on the relationship between M∗ and the Zm’s. Loosely speaking, these conditions preclude treatment matrices Zm that can be ‘disguised’ within M∗, in the sense that their projections onto the tangent spaces of M∗ are large. Specifically, the formal statements relate to a particular decomposition of the linear space of n× n matrices, Rn×n = T ∗ ⊕ T ∗⊥, where T ∗ is the tangent space of M∗ in the manifold consisting of matrices with rank no larger than rank(M∗):
T ∗ = {U∗A> +BV ∗>| A,B ∈ Rn×rank(M ∗)}.
Equivalently, the orthogonal space of T ∗, denoted T ∗⊥, is the subspace of Rn×n whose columns and rows are orthogonal, respectively, to the spaces U∗ and V ∗. Let PT∗⊥(·) denote the projection operator onto T ∗⊥:
PT∗⊥(A) = (I − U∗U∗>)A(I − V ∗V ∗>). We will defer the formal statements of the additional conditions to the next section, but suffice to say for now that they assume PT∗⊥(Zm) to be sufficiently large (we will show that lower bounds on the size of PT∗⊥(Zm), in the the precise form of our own conditions, are nearly necessary). In the remainder of this section, we will outline the core contribution of this paper, which is an estimator for τ∗ with a provably rate-optimal guarantee.

heading: 2.1 A De-biased Convex Estimator
text: Our estimator is constructed in two steps, stated as Eqs. (1a) and (1b) below:
(M̂, τ̂) ∈ argmin M∈Rn×n,τ∈Rk
g(M, τ) := 1
2 ∥∥∥∥∥O −M − k∑
m=1
τmZm ∥∥∥∥∥ 2
F
+ λ ‖M ‖∗ , (1a)
τd := τ̂ −D−1∆. (1b) In Eq. (1b), define by D ∈ Rk×k the Gram matrix with entires Dlm = 〈PT̂⊥(Zl), PT̂⊥(Zm)〉, and by ∆ ∈ Rk the ‘error’ vector with components ∆l = λ〈Zl, Û V̂ >〉, where we have let M̂ = Û Σ̂V̂ > be the SVD of M̂ , and let T̂ denote the tangent space of M̂ .4
The first step, Eq. (1a), is a natural convex optimization formulation that we use to compute a ‘rough’ estimate of the average treatment effects. The objective function’s first term penalizes choices of M and τ which differ from the observed O, and the second term seeks to penalize the rank of M using the nuclear norm as a (convex) proxy. The tuning parameter λ > 0, which will be specified in our theoretical guarantees, encodes the relative weight of these two objectives.
After the first step, having (M̂, τ̂) as a minimizer of Eq. (1a), we could simply use τ̂ as our estimator for τ∗. However, a brief analysis of the first-order optimality conditions for (1a) yields a simple, but powerful decomposition of τ̂ − τ∗ that suggests a first-order improvement to τ̂ via de-biasing: Lemma 1. Suppose (M̂, τ̂) is a minimizer of (1a). Let M̂ = Û Σ̂V̂ > be the SVD of M̂ , and let T̂ denote the tangent space of M̂ . Denote Ê = E + ∑ m δm ◦ Zm. Then, D(τ̂ − τ∗) = ∆1 + ∆2 + ∆3, (2) where ∆1,∆2,∆3 ∈ Rk are vectors with components
∆1m = λ〈Zm, Û V̂ >〉,∆2m = 〈PT̂⊥(Zm), Ê〉,∆ 3 m = 〈Zm, PT̂⊥(M ∗)〉. 4Our definition implicitly assumes that D is invertible. We view this as a natural assumption on (the absence
of) collinearity in treatments.
Consider this error decomposition, i.e. τ̂ − τ∗ = D−1(∆1 + ∆2 + ∆3) by Eq. (2), and note that D−1∆1 is entirely a function of observed quantities. Thus, it is known and removable. The second step of of our algorithm, Eq. (1b), does exactly this. The resulting de-biased estimator, denoted τd, is the subject of this paper. As an aside, it is worth noting that while de-biased estimators for high-dimensional inference have received considerable attention recently, our de-biasing procedure is algorithmically distinct from existing notions of de-biasing, including those for problems closely related to our own (e.g. matrix completion [32, 18] and panel data regression [27]).
Our main results characterize the error τd − τ∗. The crux of this can be gleaned from the second and third terms of Eq. (2). If T̂ is sufficiently ‘close’ to T ∗, then ∆3 becomes negligible (because PT∗⊥(M
∗) = 0). Showing closeness of T̂ and T ∗ is the main technical challenge of this work. The remaining error, contributed by ∆2, can then be characterized as a particular ‘weighted average’ of the (independent) entries of E and the residual matrices δm which we show to be min-max optimal.
To conclude this section, we prove Lemma 1 for a single treatment (k = 1); the complete proof is a straightforward generalization, completed in Appendix A (See the online full version5 for Appendix details).
Proof of Lemma 1 for k = 1. Since k = 1, we suppress redundant subscripts. Consider the first-order optimality conditions of (1a): 〈
Z,O − M̂ − τ̂Z 〉 = 0 (3a)
O − M̂ − τ̂Z = λ(Û V̂ > +W ), (3b) ‖W ‖ ≤ 1 (3c)
PT̂⊥(W ) = W (3d)
(W is called the ‘dual certificate’ in the matrix completion literature [33, 34, 35]). Combining Eq. (3b) and Eq. (3a), we have〈
Z,O − M̂ − τ̂Z 〉 = 0 =⇒ 〈 Z, λ(Û V̂ > +W ) 〉 = 0 =⇒ λ 〈 Z, Û V̂ > 〉 = −〈Z, λW 〉 . (4)
Next, applying PT̂⊥(·) to both sides of Eq. (3b) and using Eq. (3d):
PT̂⊥(O − M̂ − τ̂Z) = λW =⇒ PT̂⊥(M ∗) + PT̂⊥(E + δ ◦ Z)− (τ̂ − τ ∗)PT̂⊥(Z) = λW, (5)
where the implication is by definition: O = M∗ + E + τ∗Z + δ ◦ Z. Finally, substituting λW from Eq. (5) into Eq. (4), we obtain
λ 〈 Z, Û V̂ > 〉 = − 〈 Z,PT̂⊥(M ∗) + PT̂⊥(E + δ ◦ Z)− (τ̂ − τ ∗)PT̂⊥(Z) 〉 =⇒ (τ̂ − τ∗)
∥∥PT̂⊥(Z)∥∥2F = λ〈Z, Û V̂ >〉+ 〈Z,PT̂⊥(E + δ ◦ Z)〉+ 〈Z,PT̂⊥(M∗)〉 This is equivalent to Eq. (2), completing the proof.

heading: 3 Theoretical Guarantees
text: Summarizing so far, our estimator is constructed in two steps: solve the convex program in Eq. (1a) to obtain an initial estimate (M̂, τ̂), then de-bias according to Eq. (1b). While we have presented this estimator in a setting that allows for multiple treatments (i.e. k ≥ 1), for the sake simplicity our results here (Theorems 1 and 2) are restricted to the single treatment (i.e. k = 1) setting. Recall that the work on synthetic control, which we seek to extend, is for a single treatment and a particular form of Z1 (support on a single row); our results in this section are for a single treatment but general Z1. To ease notation, we will from here on suppress treatment-specific subscripts (Z1, τ1, etc.)
As mentioned earlier, our results require a set of conditions that relate the treatment matrix Z to the tangent space T ∗ of M∗:
5https://arxiv.org/abs/2106.02780
Assumption 3. There exist positive constants Cr1 , Cr2 such that (a) ‖ZV ∗‖2F + ∥∥Z>U∗∥∥2 F ≤ (1− Cr1/ log(n)) ‖Z‖ 2 F .
(b) ∣∣〈Z,U∗V ∗>〉∣∣ ‖PT∗⊥(Z)‖ ≤ (1− Cr2/ log(n)) ‖PT∗⊥(Z)‖2F .
Assumption 3 is nearly necessary for identifying τ∗ (in a manner made formal by Proposition 2 below). These conditions are mild enough to allow for various treatment patterns that occur in practice, and broadly expand on the set of patterns possible in the synthetic control literature (as we discuss in Section 3.1).
Let δ = T ◦Z− τ∗Z be the matrix of treatment effect ‘residuals.’ Our first result establishes a bound on the error rate of τd. Note that δ is a zero-mean matrix and is zero outside the support of Z. Thus the requirement below that ‖δ‖ ≤ Cδσ √ n/r is mild. It is trivially met in synthetic control settings. It is also easily seen as met when δ has independent, sub-Gaussian entries. Finally as it turns out, the condition can also admit random sub-gaussian matrices with complex correlation patterns; see [36]. Theorem 1 (Optimal Error Rate). Suppose σ √ n
σmin ≤ C1 1κ2r2 log5(n) and ‖δ‖ ≤ Cδσ
√ n/r. Then for
any C2 > 0, for sufficiently large n, with probability 1−O(n−C2), we have
|τd − τ∗| ≤ Ce log(n) max
( σ
‖Z‖F κ3rnσ log5(n) σmin , | 〈PT∗(δ), PT∗(Z)〉 | ‖Z‖2F
) .
Here, Ce is a constant depending (polynomially) on C1, C2, Cr1 , Cr2 , Cδ (where Cr1 and Cr2 are the constants appearing in Assumption 3).
To begin parsing this result, consider a ‘typical’ scenario in which σ, κ, r, µ = O(1), and σmin = Ω(n). Then Theorem 1 implies that
|τd − τ∗| = Õ ( σ/‖Z‖F + | 〈PT∗(δ), PT∗(Z)〉 |/‖Z‖2F ) . (6)
This is minimax optimal (up to log n factors), as shown below: Proposition 1 (Minimax Lower Bound). For any estimator τ̂ , there exists an instance with σ, κ, r, µ = Θ(1), and σmin = Θ(n), on which, with probability at least 1/3,
|τ̂ − τ∗| ≥ max ( σ/ ‖Z‖F , | 〈PT∗(δ), PT∗(Z)〉 |/ ‖Z‖ 2 F ) .
Finally, it is worth considering some special cases under which Eq. (6) reduces further to
|τd − τ∗| = Õ (σ/‖Z‖F) , (7) which is the optimal rate (up to log n) achieviable even when M∗ and δ are known. Any of the following are, alone, sufficient to imply Eq. (7):
Independent δ: Independent, sub-gaussian δij with O(1) sub-gaussian norm. Synthetic control and block Z: ‖δ‖max = O(1), Z consists of an ` × c block that is sufficiently sparse: √ `c(`+c) = O(n). For comparison, state-of-the-art synthetic control results [13, 37] require the sparser condition `c(`+ c) = O(n) (though that condition enables asymptotic normality results). Panel data regression: The conditions imposed in [27], the most notably that Z be sufficiently dense: ‖PT∗⊥(Z)‖2F = Θ(n2). This recovers their error guarantee (up to log factors); see Appendix D. Our second main result establishes asymptotic normality for our estimator. This naturally requires some additional control over the variability of δ. We consider the setting in which the δij = Tij − τ∗ are independent variables. Theorem 2 (Asymptotic Normality). Suppose each δij is a mean-zero, independent random variable with sub-Gaussian norm ‖δij‖ψ2 = O(1). Assume κ = r = µ = σ = O(1) and σmin = Ω(n). Then with probability 1−O(1/n3),
τd − τ∗ = 〈E + (δ ◦ Z), PT∗⊥(Z)〉 ‖PT∗⊥(Z)‖ 2 F +O
( log8(n)
n
) .
Consequently, (τd − τ∗)/V 1/2τ → N (0, 1), Vτ = ∑ ij PT∗⊥(Z) 2 ijVar(Eij + δijZij) /(∑ ij PT∗⊥(Z) 2 ij )2 ,
provided that V 1/2τ = Ω(log9(n)/n).
Asymptotic normality is of econometric interest, as it enables inference. Specifically, inference can be performed using a ‘plug-in’ estimator V̂τ for Vτ , gotten by substituting T̂ for T ∗ and O−Md− τdZ for E + (δ ◦ Z), where Md is a de-biased estimator for M∗ (see Appendix L). This is a common procedure in the literature (e.g., see [18]), and it is straightforward to show that V̂τ ∼ Vτ . Proof Technique: The proofs of Theorems 1 and 2 are inspired by recent developments on bridging convex and non-convex formulations for matrix completion [4] and Robust-PCA [5]. Whereas that work assume a random, independent missingness pattern, our proof extends that program to deal with deterministic treatment patterns Z. As such, this analysis is likely of interest, in its own right, as a complement to the matrix completion literature [38, 39, 4, 5]. Broadly, we must address the issue that constructing a dual certificate to analyze the quality of our convex estimator directly is hard. Instead [4] show the existence of such a certificate non-constructively by studying a non-convex estimator and showing that a (fictitious) gradient descent algorithm applied to that estimator recovers a suitable dual certificate. We effectively extend that program to deterministic patterns Z, and provide entry-wise recovery guarantees on M∗ in this setting that are of independent interest.

heading: 3.1 Applicability of Treatment Conditions
text: Having stated our results, we return to our assumptions on Z (Assumption 3) and discuss the extent to which they allow for treatment patterns that occur in practice. First however, we establish that Assumption 3 is necessary. Consider the proposition below, which establishes that should either of the condition of Assumption 3 be violated by an amount that grows negligible with n, then identification is rendered impossible so that no estimator can recover τ∗.
Proposition 2. Let n be any positive even integer. There exists a matrix Z ∈ {0, 1}n×n and a pair of rank-1 and µ = 2 (incoherent) matrices M1,M2 ∈ Rn×n with SVDs denoted by Mi = UiΣiV >i and Ti being the tangent space of Mi, such that all three of the following statements hold:
1. ‖ZVi‖2F + ‖ZTUi‖2F = ‖Z‖ 2 F , i = 1, 2 2. ∣∣〈Z,UiV >i 〉∣∣ ‖PT∗⊥i (Z)‖ = ‖PT∗⊥i (Z)‖2F, i = 1, 2 3. M1 + Z = M2
We next discuss various treatment patterns that are admissible under Assumption 3:6 1. Rank grows faster than r: Assumption 3 holds if ∑r i=1 σi(Z) 2 ≤ (1− C/ log n) ‖Z‖2F/( √ r+2).
Loosely speaking, this requires that the rank of Z be strictly higher than r, and that less than 1/ √ r of its ‘mass’ lie in its first r components. Put another way, Z must be sufficiently different from any rank-r approximation. One common setting where this occurs is when there is sufficient randomness in generating Z, such as the case where the entries of Z are drawn independently, which is the canonical scenario in the matrix completion literature (e.g., [35, 38, 39]).
2. Maximal number of ones in a row and column: Let ` and c denote the maximum number of ones in a row and column, respectively, of Z. Assumption 3 holds if ` + c ≤ (1− C/ log n)n/(r2µ). When r, µ = O(1), this allows `, c = O(n) and generalizes the sparse block patterns studied in the literature (e.g. [40, 13]), where Z is a two-by-two block matrix with exactly one block equal to one.
3. Single row or column (Synthetic Control): Consider the case when Z is supported on a single row (or column, equivalently), as in synthetic control. Assumption 3 holds if ‖z>V ∗‖2F ≤ (1− C/ log n− µr/n) ‖z‖2, where z> is the non-zero row of Z. This will easily hold, if allowing a negligible perturbation to either z1 or the row space of M∗. It is also interesting to note that the identification assumption made in the canonical paper [2] (i.e., T−10 σmin( ∑T0 i=1 V ∗ i V ∗> i ) > 0 is bounded away from zero, where T0 = maxzi=0 i), together with T0 = Ω(n/ log(n)) and µr = O(n/ log(n)) (also implicitly assumed in [2] for an optimal gaurantee), together imply Assumption 3.
We end this section by drawing a connection to the literature on panel data regression with interactive fixed effects [25, 36, 27]. That literature studies estimators similar in spirits to ours (e.g., [27] analyzed the performance of the convex estimator and a heuristic de-biasing approach). However,
6Also see a further discussion for mathematical equivalent forms of Assumption 3 based on basis transformations and the generalization to k > 1 in Appendix C.
those approaches are only known to work if ‖PT∗⊥(Z)‖F = Θ(n2)7. This is of course a substantially stronger assumption than Assumption 3 and rules out sparse treatment patterns (as in synthetic control). In summary, our approach also has the potential to broaden the scope of problems addressed via panel data regression.

heading: 4 Experiments
text: We conducted a set of experiments on semi-synthetic datasets (the treatment is introduced artificially and thus ground-truth treatment-effect values are known) and real datasets (the treatment is real and ground-truth treatment-effect values are unknown). The results show that our estimator τd is more accurate than existing algorithms and its performance is robust to various treatment patterns.
The following four benchmarks were implemented: (i) Synthetic Difference-in-Difference (SDID) [13]; (ii) Matrix-Completion with Nuclear Norm Minimization (MC-NNM) [3] (iii) Robust Synthetic Control (RSC) [10] (iv) Ordinary Least Square (OLS): Selects a, b ∈ Rn, τ ∈ R to minimize ‖O− a1T − 1bT − τZ‖2F, where 1 ∈ Rn is the vector of ones. It is worth noting that SDID and RSC one apply to traditional synthetic control patterns (block and stagger below).
Semi-Synthetic Data (Tobacco). The first dataset consists of the annual tobacco consumption per capita for 38 states during 1970-2001, collected from the prominent synthetic control study [2] (the treated unit California is removed). Similar to [3], we view the collected data as M∗ and introduce artificial treatments. We considered two families of patterns that are common in the economics literature: block and stagger [3]. Block patterns model simultaneous adoption of the treatment, while stagger patterns model adoption at different times. In both cases, treatment continues forever once adopted. Specifically, given the parameters (m1,m2), a set of m1 rows of Z are selected uniformly at random. On these rows, Zij = 1 if and only if j ≥ ti, where for block patterns, ti = m2, and for stagger patterns, ti is selected uniformly from values greater than m2.
To model heterogenous treatment effects, let Tij = τ∗ + δi where δi is i.i.d and δi ∼ N (0, σδ) characterizes the unit-specific effect. Then the observation is O = M∗ + T ◦ Z. We fix τ∗ = σδ = M̄∗/5 through all experiments, where M̄∗ is the mean value of M∗ 8. The hyperparameters for all algorithms were tuned using rank r ∼ 5 (estimated via the spectrum of M∗). Next, we compare the performances of the various algorithms on an ensemble of 1,000 instances with m1 ∼ Uni[1, n1),m2 = Uni[1, n2) for stagger patterns and m1 ∼ Uni[1, 5),m2 = 18 for block patterns (matching the year 1988, where California passed its law for tobacco control). The results are reported in the first two rows of Table 1 in terms of the average normalized error |τ − τ∗|/τ∗. Note that the treatment patterns here are ‘home court’ for the SDID and RSC synthetic control methods but our approach nonetheless outperforms these benchmarks. One potential reason is that these methods do not leverage all of the available data for learning counterfactuals: MC-NNM and SDID ignore treated observations. RSC ignores even more: it in addition does not leverage some of the untreated observations in M∗ on treated units (i.e. observations Oij for j < ti on treated units).
Semi-Synthetic Data (Sales). The second dataset consists of weekly sales of 167 products over 147 weeks, collected from a Kaggle competition [41]. In this application, treatment corresponds to
7Parenthetically, the assumption ‖PT∗⊥(Z)‖F = Θ(n2) greatly simplifies analysis in [27] since a global bound on τ − τ∗ can be easily obtained. One of the main technical innovations in our paper, building on recent advances in the matrix completion literature, is to conduct a refined ‘local’ analysis without the assumption on the density of Z.
8See Appendix E for estimating row-specific treatment effects
various ‘promotions’ of a product (e.g. price reductions, advertisements, etc.). We introduced an artificial promotion Z, used the collected data as M∗ (M̄∗ ≈ 12170), and the goal was to estimate the average treatment effect given O = M∗ + T ◦ Z and Z (T follows the same generation process as above with τ∗ = σ = M̄∗/5).
Now the challenge in these settings is that these promotions are often decided based on previous sales. Put another way, the treatment matrix Z is constructed adaptively. We considered a simple model for generating adaptive patterns for Z: Fix parameters (a, b). If the sale of a product reaches its lowest point among the past a weeks, then we added promotions for the following b weeks (this models a common preference for promoting low-sale products). Across our instances, (a, b) was generated according to a ∈ Uni[5, 25], b ∈ Uni[5, 25]. This represents a treatment pattern where it is unclear how typical synthetic control approaches (SDID, RSC) might even be applied.
The rank of M∗ is estimated via the spectrum with r ∼ 35. See Table 1 for the results averaged over 1,000 instances. The average of |τ − τ∗|/τ∗ is ∼ 5.3% for our algorithm, versus 27.6% for MC-NNM. We conjecture that the reason for this is that highly structured missing-ness patterns are challenging for matrix-completion algorithms; we overcome this limitation by leveraging the treated data as well. Of course, there is a natural trade-off here: if the heterogeneity in δ were on the order of the variation in M∗ (so that ‖δ ◦ Z‖ σr(M∗)) then it is unclear that the treated data would help (and it might, in fact, hurt). But for most practical applications, the treatment effects we seek to estimate are typically small relative to the nominal observed values.
Real Data. This dataset consists of daily sales and promotion information of 571 drug stores over 942 days, collected from Rossmann Store Sales dataset [42]. The promotion dataset Z is binary (1 indicates a promo is running on that specific day and store). The real pattern is highly complex (see Fig. 1) and hence synthetic-control type methods (SDID, RSC) again do not apply. Our goal here is to estimate the average increase of sales τ∗ brought by the promotion.
The hyperparameters for all algorithms were tuned using rank r ∼ 70 (estimated via cross validation). A test set Ω consisting of 20% of the treated entires is randomly sampled and hidden. The test error is then calculated by ‖PΩ(M + τZ − O)‖2F/‖PΩ(O − Ō)‖2F where Ō is the mean-value of O. Fig. 1 shows the results averaged over 100 instances. Our algorithm provides superior test error. This is potentially a conservative measure since it captures error in approximating both M∗ and τ∗; the variation contributed by M∗ to observations is substantially larger that that contributed by τ∗. Now whereas the ground-truth for τ∗ is not known here, the negative treatment effects estimated by MC-NNM and OLS seem less likely since store-wise promotions are typically associated with positive effects on sales.
Asymptotic Normality. The normality of our estimator is also verified, where the prediction from Theorem 2 is precise enough to enable inferential tasks such as constructing confidence intervals (CIs) for τ∗: our 95% CIs typically had “true” coverage rates in the range of 93-96% for a synthetic set of instances described in Appendix E. See Fig. 2.

heading: 5 Conclusion
text: Motivated by the extremely important econometric problem of estimating treatment effects from panel data, we studied a natural formulation of this problem as one of recovering an unknown quantity
that has been added to an unknown low-rank matrix at a subset of its entries. We proposed an estimator based on solving, and de-biasing, a natural regularized least-squares objective. We built on recent techniques for establishing entry-wise guarantees that leverage a connection between convex and non-convex formulations, and proved that our estimator is order-optimal with nearly minimal conditions on the underlying low-rank matrix and the pattern of ‘treated’ entries.
One exciting direction for further work is to consider the correlation between noises (as opposed to the independent noise assumption). In fact, our main guarantee for the error rate (Theorem 1) is not restricted to independent noise (the results incorporate a deterministic E naturally, see Appendix B and Appendix J). On the other hand, our asymptotic normality result (Theorem 2) indeed requires independent noise. Generalizing this result to correlated noise appears to be more involved and may require further technical innovations.

heading: 6 Ackowledgement
text: We thank all anonymous reviewers for their constructive comments. Farias and Peng were partially supported by NSF Grant CMMI 1727239.

Review summaries:
This paper looks at the problem of learning treatment effects from observational data. Recently, there has been a flurry of work in establishing theoretical guarantees for low-rank matrix recovery in presence of a Gaussian noise, where de-biasing-based estimators have been analyzed. This paper takes that problem to a next level, in the context of learning treatment effects. Here, the observed matrix is a low-rank matrix added with noise and also treatment matrices. The goal is to recover the effect of average treatment. The authors propose a two-step estimator. In the first step, they try to learn a low-rank matrix and the treatments using a convex optimization program, which is standard in the matrix recovery literature. Then they also use a de-biasing step to improve the performance of their estimation of the treatment matrix.

This paper considers a general problem of applying multiple treatments (heterogenous) to multiple units across multiple time-steps, where the outcome is of this treatment has a linear relationship. Given the treatment decision matrix and the outcome matrix, the goal of the algorithm is to obtain the treatment effect (or more specifically a sufficient statistic that can be used to derive the treatment effect given the model). In particular, the outcome matrix O for n units across T steps is determined by a linear system M* + E + sum_{k} treatment_effect_matrix_k * decision_matrix_k. The algorithm sees the outcome matrix O and knows the decision_matrix_k for each of the k treatments and it needs to recover the treatment_effect_matrix_k for each of the k treatments. The paper identifies assumptions under which such an estimator is possible, shows that when violating one of the assumptions no algorithm can obtain such an estimator and that they have good empirical performance on semi-synthetic datasets.

The paper considers the problem of average treatment effect estimation in panel data. The authors consider a setup where the observed outcomes form a matrix with a special structure: it is the sum of a counterfactual matrix and a treatment matrix, where the counterfactual matrix is assumed to be a “noisy observation” of a low rank matrix. The paper proposes a debiased estimator, shows that it is rate optimal, derives its asymptotic normality and demonstrate its performance through numerical experiments.