acceptodds
Under review as a conference paper at ICLR 2027

Improved Guarantees for Heterogeneous Treatment-Effect Estimation via Matrix Completion

Abstract

A central goal of modern causal inference is estimating heterogeneous treatment effects to answer questions like “how does an intervention affect each unit,” rather than only on average. We study this problem with panel-data where we observe units across times under unknown, non-uniform treatment assignments. The data in this setting is naturally represented as a matrix of all unit–time treatment effects. Estimating heterogeneous treatment effects can then be expressed as obtaining a good estimation of each row's average in this matrix. This allows us to formulate the problem as matrix completion, which can be solved under natural low-rankness assumptions. However, existing matrix-completion guarantees are not powerful enough to get meaningful bounds for the per-row guarantee required for estimating the heterogeneous treatment effect; roughly speaking, they are only useful for estimating average treatment effect bounds, as also illustrated in a recent line of work. We give a simple, computationally efficient estimator that, without knowledge of the propensities and under standard low-rankness and regularity assumptions, achieves a row-wise error of . Technically, our analysis establishes the first sharp row-wise -perturbation bound for low-rank approximation, complementing existing spectral-, Frobenius-, and entrywise perturbation theory. We evaluate our estimator on both synthetic and semi-synthetic data, and find lower estimation error than direct Horvitz–Thompson and Hájek estimators for several unit-specific treatment effects. Further, in synthetic experiments, the error decay matches the dependence on panel size predicted by our theoretical bounds.

Primary area:
learning theory
Keywords:
heterogeneous treatment effects, matrix completion, causal inference, matrix perturbation theory

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_RJqkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper wants each person’s treatment effect from panel data (n people × m time points) with random, unknown treatment probabilities. It frames this as matrix completion and claims a simple, fast estimator with per-person error of about √(1/n + n/m²), plus a new row-wise perturbation bound. In experiments the estimator beats Horvitz–Thompson and Hájek estimators.

Critical strengths

Theoretically solid.

Critical weaknesses
  1. Most components of the analysis are standard: inverse-propensity rescaling, matrix Bernstein, Weyl, symmetric dilation, gap-based rank selection, and the contour expansion of Tran & Vu. The genuinely new ingredient appears to be Theorem 4.2. However, the paper does not explain precisely what it improves over (i) existing ‖·‖_{2→∞} subspace bounds (Cape et al. 2019; Abbe et al. 2020) converted to low-rank-approximation bounds, and (ii) √m times the entrywise bound of Tran & Vu (2025a). Please state explicitly which factor is gained (e.g., condition number, gap at the true rank, logarithmic factors) and give an example where Theorem 4.2 is strictly better. Without this comparison, the technical contribution is hard to assess.

  2. The main comparison is to Athey et al. (2021) and Agarwal et al. (2023), which study harder assignment designs (block adoption and missing-not-at-random). Under the independent Bernoulli design considered here, existing entrywise guarantees for spectral matrix completion (e.g., Abbe et al. 2020; Chen et al. 2019) appear to already imply row-wise bounds in the row-homogeneous case. The authors should clarify what their results add beyond this literature. The contribution then appears to rest on the new ‖·‖_{2,∞} perturbation bound and the treatment of nonuniform propensities, and the latter yields vanishing error only for noise-like nonuniformity.

  3. The paper gives an error bound with unknown constants, not uncertainty estimates. A practitioner can’t say “Ana’s effect is 0.5 ± 0.2.” For individual effects, inference matters as much as the point estimate.

Questions for authors

See above

5 comments
AuthorsOpenReview ↗

Response to Reviewer RJqk (1/3)

Thank you for identifying the comparisons that would make the contribution clearer. We agree that Theorem 4.2 is the main new technical result.

Weakness 1: “Most components of the analysis are standard: inverse-propensity rescaling, matrix Bernstein, Weyl, symmetric dilation, gap-based rank selection, and the contour expansion of Tran & Vu. The genuinely new ingredient appears to be Theorem 4.2. However, the paper does not explain precisely what it improves over (i) existing ∣⋅∣2→∞\\|\cdot\\|_{2\to\infty} subspace bounds (Cape et al. 2019; Abbe et al. 2020) converted to low-rank-approximation bounds, and (ii) m\sqrt m times the entrywise bound of Tran & Vu (2025a). Please state explicitly which factor is gained (e.g., condition number, gap at the true rank, logarithmic factors) and give an example where Theorem 4.2 is strictly better. Without this comparison, the technical contribution is hard to assess.”

We answer the three parts of this question in turn. The technical follow-up below gives the calculations.

(i) Subspace bounds. Converting a bound on singular subspaces into a bound on the low-rank approximation multiplies the subspace error by σ1(A)\sigma_1(A), so the converted bound depends on the condition number κ=σ1/σs\kappa=\sigma_1/\sigma_s. For example, the reconstruction bound of Abbe et al. (2020, Theorem 3.4) has a factor κ4\kappa^4 and a signal condition at the true rank. Theorem 4.2 bounds the low-rank approximation directly. It has no condition-number factor and needs a gap only at the retained rank.

(ii) Tran and Vu (2025a). Our proof adapts their contour expansion. For random noise, their Theorem 2.1 requires the gap δs≥40rK(m+n)/p\delta_s\geq40rK\sqrt{(m+n)/p}, which grows linearly with the rank, while Theorem 4.2 requires δs≥6∣E∣op\delta_s\geq6\\|E\\|_{\mathrm{op}}. When the rank, the incoherence, and σs/δs\sigma_s/\delta_s are bounded, m\sqrt m times their entrywise bound is of order log⁡3(m+n)\log^3(m+n), while our row-wise bound is of order log⁡2(m+n)\log^2(m+n). Theorem 4.2 also allows a deterministic perturbation in addition to the random one, which our analysis of nonuniform designs needs. The factors gained are therefore the factor rr in the gap condition and one logarithmic factor. For a perturbation with both parts, ER+E0E_R+E_0, their Theorem 2.1 does not apply, and bounding the row-wise error by the operator norm, using the spectral bound of Tran, Vishnoi, and Vu (2025), loses a factor of order m+n\sqrt{m+n} on the random part, up to logarithmic factors, whereas Theorem 4.2 keeps the random-noise rate.

(iii) An example. Consider an incoherent rank-two d×dd\times d matrix with entries bounded by 1/21/2 and singular values d/4d/4 and d4/5/4d^{4/5}/4, so that κ=d1/5\kappa=d^{1/5}, observed independently with probability 1/21/2 and without added noise. Theorem 4.2 bounds the normalized row error by O(log⁡2d/d)O(\log^2d/\sqrt d), which vanishes. The reconstruction bound of Abbe et al. (2020, Theorem 3.4) is of order d3/10log⁡dd^{3/10}\sqrt{\log d}, which grows with dd, even though its signal condition holds.

We will add these comparisons and the example to the paper.

AuthorsOpenReview ↗

Response to Reviewer RJqk (2/3)

Weakness 2: “The main comparison is to Athey et al. (2021) and Agarwal et al. (2023), which study harder assignment designs (block adoption and missing-not-at-random). Under the independent Bernoulli design considered here, existing entrywise guarantees for spectral matrix completion (e.g., Abbe et al. 2020; Chen et al. 2019) appear to already imply row-wise bounds in the row-homogeneous case. The authors should clarify what their results add beyond this literature. The contribution then appears to rest on the new ∣⋅∣2,∞\\|\cdot\\|_{2,\infty} perturbation bound and the treatment of nonuniform propensities, and the latter yields vanishing error only for noise-like nonuniformity.”

We agree that when all entries share a common observation probability and the condition number is bounded, existing entrywise guarantees imply row-wise bounds, and we will discuss them explicitly. Our results go beyond this setting in three ways.

  • Unit-specific rates. Abbe et al. (2020) and Chen et al. (2019) assume a common observation probability. Our row-homogeneous designs allow each unit its own unknown treatment rate, as in stratified randomization.

  • Condition number. These results assume a bounded condition number or depend on it polynomially, while our bound does not depend on it. This matters, for example, when a strong common trend dominates weaker unit-specific patterns. In the example in our answer to Weakness 1, our bound vanishes while that of Abbe et al. grows with the dimension.

  • Nonuniform designs. With the factor identified by Reviewer rWGs corrected, our guarantee covers designs whose propensities vary within rows with bounded ∣P∣op\\|P\\|_{\mathrm{op}}, such as schedules in which each unit's treatment probability is raised at a bounded number of times, with a bounded number of units raised at each time. Designs whose propensities vary over time in the same way for all units, such as ramp-ups, are covered by a column-scaled variant of our estimator (see our response to Reviewer fC3x).

We will also clarify that Athey et al. (2021) and Agarwal et al. (2023) study different assignment models.

Weakness 3: “The paper gives an error bound with unknown constants, not uncertainty estimates. A practitioner can't say `Ana's effect is 0.5±0.20.5\pm0.2.' For individual effects, inference matters as much as the point estimate.”

We agree that uncertainty quantification for individual effects is important. Our results concern point estimation. Explicit constants, together with estimates of the parameters in our bound, would give error bars, but these would be conservative, since the bound holds simultaneously for all units. Calibrated intervals require a distributional approximation for each estimated effect that accounts for the bias from truncation and the data-driven choice of rank, as developed for matrix completion under uniform sampling by Chen, Fan, Ma, and Yan (2019). Tightening our constants and developing such inference for our estimator are important directions but beyond the scope of this work. We will discuss them in the paper.

AuthorsOpenReview ↗

Response to Reviewer RJqk (3/3): Technical follow-up

Technical follow-up to Reviewer RJqk

This follow-up gives the calculations behind our answer to Weakness 1.

(i) Converting subspace bounds. Let Π\Pi and Π~\widetilde\Pi be the projections onto the top-ss left singular spaces of AA and A~=A+E\widetilde A=A+E. Since As=ΠAA_s=\Pi A and A~s=Π~A~\widetilde A_s=\widetilde\Pi\widetilde A, A~s−As=(Π~−Π)A+Π~E,.\widetilde A_s-A_s=(\widetilde\Pi-\Pi)A+\widetilde\Pi E\\,. A two-to-infinity bound on singular subspaces, such as Cape, Tang, and Priebe (2019), Theorem 3.7, controls Π~−Π\widetilde\Pi-\Pi, and the identity multiplies this error by ∣A∣op=σ1(A)\\|A\\|_{\mathrm{op}}=\sigma_1(A). Combined with the Davis–Kahan bound for the operator-norm part, this conversion yields a bound with factors σ1/σs\sigma_1/\sigma_s and σ1/δs\sigma_1/\delta_s, where Theorem 4.2 has σs/δs\sigma_s/\delta_s. The example in (iii) shows that this dependence appears in the published reconstruction bound of Abbe et al. (2020).

(ii) Comparison with Tran and Vu (2025a). Let N=m+nN=m+n, and let μ0\mu_0 be the standard coherence. Their Theorem 2.1 (arXiv v2) assumes δs≥40rKN/p\delta_s\geq40rK\sqrt{N/p} and gives

\leq C\\,\frac{(\log N+\mu_0)\log^2N}{\sqrt{mn}}\\,r\sigma_s \left(\frac K{\sigma_s}\sqrt{\frac Np}+\frac{rK\sqrt{\log N}}{\delta_s\sqrt p}+\frac{r^2\mu_0K\log N}{p\\,\delta_s\sqrt{mn}}\right).$$ For $m=n=d$ and bounded $r$, $\mu_0$, $K$, $p$, and $\sigma_s/\delta_s$, the first term dominates, and $\sqrt d$ times the bound is of order $\log^3d$. For the same noise, Theorem 4.2 gives $\\|\widetilde A_s-A_s\\|_{2,\infty}=O(\sqrt r\mu\log^2d\\,\sigma_s/\delta_s)$. Our incoherence parameter satisfies $\mu=\sqrt{r\mu_0}$, so $\sqrt r\mu=r\sqrt{\mu_0}$, and the two bounds have the same dependence on the rank. Their Theorem 2.1 does not apply to mixed noise $E=E_R+E_0$. Their general deterministic result (Theorem 3.2) has different hypotheses, so we compare only with Theorem 2.1. *(iii) The rank-two example.* Let $d$ be even, let $u=d^{-1/2}\mathbf 1$, let $v$ have $d/2$ entries equal to $d^{-1/2}$ and $d/2$ entries equal to $-d^{-1/2}$, and set $$A=\frac d4uu^\top+\frac{d^{4/5}}4vv^\top\\,.$$ Then $A$ has rank two, entries bounded by $1/2$, incoherence parameter $\mu=\sqrt2$, and condition number $\kappa=d^{1/5}$. Observe each entry independently with probability $p=1/2$, without added noise, and let $\widetilde A=2D\odot A$. Then $E=\widetilde A-A$ has independent, centered entries bounded by $1/2$, so $\\|E\\|_{\mathrm{op}}=O(\sqrt d)$ with high probability. The gap $\delta_2=\sigma_2=d^{4/5}/4$ exceeds $6\\|E\\|_{\mathrm{op}}$ for large $d$, and $\sigma_2/\delta_2=1$, so Theorem 4.2 gives $$\frac{\\|\widetilde A_2-A\\|_{2,\infty}}{\sqrt d}=O\left(\frac{\log^2d}{\sqrt d}\right).$$ [Abbe, Fan, Wang, and Zhong (2020), Theorem 3.4](https://pmc.ncbi.nlm.nih.gov/articles/PMC8046180/), bounds the entrywise reconstruction error by $C\eta^2\kappa^4(\\|A\\|_{\max}+\sigma)\sqrt{N\log N/p}$, where $\eta$ is the largest row norm of the singular vector matrices and $\sigma$ is the noise level. Here $\eta^2=2/d$, $N=2d$, and $\sigma=0$, and the signal condition of the theorem holds because its left-hand side is $O(d^{-1/10}\sqrt{\log d})$. The bound is of order $d^{3/10}\sqrt{\log d}$. Since $\\|F\\|_{2,\infty}/\sqrt d\leq\\|F\\|_{\max}$ for every $d\times d$ matrix $F$, it gives a normalized row error bound of the same order, which grows with $d$.
Reviewer_rWGsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the setting of micro-randomized trials where the goal is to estimate "heterogeneous" treatment effects for each of the n individuals (e.g. patients) that is treated m times, over different windows of time  - which then reduces to simply matrix recovery under some low-rank assumptions on the (outcome) matrices, measured  in terms of the 1/\sqrt{m} || . ||_2,\infty difference of M\hat - M (i.e. estimate - ground truth effects). Technically speaking it combines ideas from matrix completion with assumptions from the line of work by Tran&Vu (not requiring bounded condition number of gap at sigma_r)

Critical strengths

Paper was nicely structured and quite readable for a technical paper.

Critical weaknesses

Motivation vs. settings "mismatch":

  • Micro-randomized trials like in HeartSteps have a carry-over "problem". This is not at all discussed in the assumptions of the paper (i.e. that potential outcomes may depend on the treatment history, as in Bojinov, Rambachan and Shephard or Bojinov, Simchi-Levi & Zhao)

  • It seems to me more reasonable that M is low-rank rather than A(1)  or A(0) themselves which may be closer to full-rank instead? Probably does not change the paper much, 

Technically speaking there are some critical, some fixable oversights and gaps:

  • From Theorem 4.2. to eq. (4.2.) (to prove Thm 3.2) there seems to be a (significant) typo from the first result to the second - the term \sqrt{m+n} seems to have vanished, but if it's actually carried over, would result in a bound of order ||P||_op  (if m~n) and Corollary 3.3. would read ||P||_op / \sqrt{m} which would not be decaying in realistic settings when ||P||_op is of order \sqrt{m} at least (unless its row-homogeneous)? 

  • It seems that in Section 4, the authors actually analyze the case where p_i is known, as they assume (E Y^\tilde ub)_ij = (p_ij a_ij/p_i) (which is not true when plugging in phat_i as defined). This seems fixable, but the authors would need to do the legwork ... 

Further, it did not seem to me that the key challenge steps required that much more novel tools given the line of work of Tran&Vu, as significant as the paper keeps claiming. It would be good to make clear what the real challenge is. They write in the main text "separating their  contributions [of E_R and E_0] is highly nontrivial" and refer to Section D - where they simply use a triangle inequality and by the inequality D.7. can separately analyze the terms? These two steps don't seem to me in any way "highly nontrivial". For the term with E_R, they then just use a result from Tran&Vu 2025a; for the term with ||E_0||_op they just use a crude bound \leq K_A ||P||_op (which is also not proven)

Questions for authors

Could you fix the technical gaps above, address the novelty point and answer to the first motivation/setting mismatch? If the technical issues are all fixed, I can imagine a raise in score to weak accept.

5 comments
AuthorsOpenReview ↗

Response to Reviewer rWGs (1/5)

Thank you for the careful technical reading and for identifying specific ways to improve the paper. We answer each point below.

“Micro-randomized trials like in HeartSteps have a carry-over `problem'. This is not at all discussed in the assumptions of the paper (i.e. that potential outcomes may depend on the treatment history, as in Bojinov, Rambachan and Shephard or Bojinov, Simchi-Levi & Zhao)”

We agree that carryover can matter in micro-randomized trials and that our model, in which each outcome depends only on the current treatment, does not capture it. The works you cite handle carryover by defining potential outcomes on treatment paths, and they estimate average effects of these paths: Bojinov, Rambachan, and Shephard (2021) in panel experiments, and Bojinov, Simchi-Levi, and Zhao (2023) in switchback experiments with carryover of bounded order. Our goal is complementary: assuming no carryover, we estimate the effect for each unit, using low-rank structure across units. We will state the no-carryover assumption explicitly, discuss these works, and note that extending unit-level estimation to carryover of bounded order is a natural next step.

“It seems to me more reasonable that MM is low-rank rather than A(1)A(1) or A(0)A(0) themselves which may be closer to full-rank instead? Probably does not change the paper much,”

Low rank of MM alone is indeed a weaker and often more natural assumption. For example, A(0)=BA(0)=B and A(1)=B+uv⊤A(1)=B+uv^\top give a rank-one MM for any BB. Our estimator completes A(0)A(0) and A(1)A(1) separately and therefore uses low rank of each. When the propensities are known, as in randomized experiments, Theorem 4.2 also gives a guarantee that needs only low rank of MM. The inverse-propensity-weighted difference Zij=Dij(1)Yijobs/pij(1)−Dij(0)Yijobs/pij(0)Z_{ij}=D_{ij}(1)Y^{\mathrm{obs}}_{ij}/p_{ij}(1)-D_{ij}(0)Y^{\mathrm{obs}}_{ij}/p_{ij}(0) has mean MijM_{ij} and independent, bounded entries, so Theorem 4.2 applies to its truncated SVD with the rank and incoherence of MM. We will add this as a remark.

“From Theorem 4.2. to eq. (4.2.) (to prove Thm 3.2) there seems to be a (significant) typo from the first result to the second - the term m+n\sqrt{m+n} seems to have vanished, but if it's actually carried over, would result in a bound of order ∣P∣op\\|P\\|_{\mathrm{op}} (if m∼nm\sim n) and Corollary 3.3. would read ∣P∣op/m\\|P\\|_{\mathrm{op}}/\sqrt m which would not be decaying in realistic settings when ∣P∣op\\|P\\|_{\mathrm{op}} is of order m\sqrt m at least (unless its row-homogeneous)?”

Yes, the factor m+n\sqrt{m+n} should remain in (4.2). With it, when m≍nm\asymp n, the design term in Corollary 3.3 is of order ∣P∣op/m\\|P\\|_{\mathrm{op}}/\sqrt m up to logarithmic factors, as you say. Our guarantee therefore still gives vanishing error when ∣P∣op\\|P\\|_{\mathrm{op}} is bounded. This includes row-homogeneous designs, where P=0P=0, and designs in which each unit's treatment probability is raised above a baseline at a bounded number of times, with a bounded number of units raised at each time (part 1 of the technical follow-up below). It does not include designs with ∣P∣op\\|P\\|_{\mathrm{op}} of order m\sqrt m. We will correct (4.2), Theorem 3.2, Corollaries 3.3 and 3.5, and the corresponding statements in the introduction. In Corollary 3.5, condition (3.3) becomes max⁡a∣P(a)∣op≤O~(ν)\max_a\\|P(a)\\|_{\mathrm{op}}\leq\widetilde O(\nu). For designs whose propensities vary over time in the same way for all units, such as ramp-ups, a variant of our estimator that scales columns instead of rows attains the rate of Corollary 3.3 (see our response to Reviewer fC3x, Question 1).

AuthorsOpenReview ↗

Response to Reviewer rWGs (2/5)

“It seems that in Section 4, the authors actually analyze the case where pip_i is known, as they assume (EY~ub)ij=(pijaij/pi)(\mathbb E\widetilde Y^{ub})_{ij}=(p_{ij}a_{ij}/p_i) (which is not true when plugging in p^i\hat p_i as defined). This seems fixable, but the authors would need to do the legwork ...”

Section 4 indeed computes the expectation with the population frequencies pip_i, and the gap can be closed with a short additional argument, which we will add to the paper. The algorithm's input equals the input with population frequencies multiplied on the left by Q=diag⁡(pi/p^i)Q=\operatorname{diag}(p_i/\hat p_i), and with high probability ∣Q−I∣op=O~(1/qm)\\|Q-I\\|_{\mathrm{op}}=\widetilde O(1/\sqrt{qm}). Multiplying by a diagonal matrix this close to the identity changes every singular value by a relative amount of at most ∣Q−I∣op\\|Q-I\\|_{\mathrm{op}}, so the rank-selection argument still applies with a larger constant. At the selected rank, it also moves the top right singular space only slightly, and the estimate changes by O~(1/m)\widetilde O(1/\sqrt m) in normalized row error, which is within the rate of Corollary 3.3. Part 2 of the technical follow-up below gives the details.

“Further, it did not seem to me that the key challenge steps required that much more novel tools given the line of work of Tran&Vu, as significant as the paper keeps claiming. It would be good to make clear what the real challenge is. They write in the main text ‘separating their contributions [of ERE_R and E0E_0] is highly nontrivial' and refer to Section D - where they simply use a triangle inequality and by the inequality D.7. can separately analyze the terms? These two steps don't seem to me in any way ‘highly nontrivial'. For the term with ERE_R, they then just use a result from Tran&Vu 2025a; for the term with ∣E0∣op\\|E_0\\|_{\mathrm{op}} they just use a crude bound ≤KA∣P∣op\leq K_A\\|P\\|_{\mathrm{op}} (which is also not proven)”

The challenge is to bound the row-wise error of the low-rank approximation itself when the perturbation is the sum of a random part ERE_R and a deterministic part E0E_0, using only the incoherence of AA and a gap at the retained rank. A natural approach compares A~s\widetilde A_s with the low-rank approximation of an intermediate matrix such as A+ERA+E_R or A+E0A+E_0, but this needs incoherence of the intermediate matrix, which does not follow from that of AA. We instead expand around AA itself, adapting the contour expansion of Tran and Vu (2025a) from entrywise to row-wise bounds. The main technical difficulty lies in separating the contributions of ERE_R and E0E_0 while preserving their different row-wise behavior. The analysis of Tran and Vu (2025a) uses the randomness of EE to show that its powers spread their mass across rows, which gives a factor of order ∣E∣μ/m+n\\|E\\|\mu/\sqrt{m+n}. This fails for E=ER+E0E=E_R+E_0, since E0E_0 may concentrate its mass on a few rows, and treating all of EE as deterministic gives a factor of order ∣ER∣+∣E0∣\\|E_R\\|+\\|E_0\\|. Our analysis gives a factor of order μ(∣ER∣/m+n+∣E0∣)\mu(\\|E_R\\|/\sqrt{m+n}+\\|E_0\\|) in balanced panels, up to rank and logarithmic factors: the random part keeps its gain from incoherence, and the deterministic part costs only its operator norm.

We agree that the triangle inequalities themselves are elementary, although applying them at the right point of the expansion is what keeps both kinds of terms under control. We will replace “highly nontrivial” with this explanation (part 4 of the technical follow-up below).

The bound ∣A⊙P∣op≤KA∣P∣op\\|A\odot P\\|_{\mathrm{op}}\leq K_A\\|P\\|_{\mathrm{op}} was indeed not proven, and it holds only with an additional factor. Part 3 of the technical follow-up below proves ∣A⊙P∣op≤r,KA∣P∣op\\|A\odot P\\|_{\mathrm{op}}\leq\sqrt r\\,K_A\\|P\\|_{\mathrm{op}}, where rr is the rank of AA, and shows that this factor cannot be dropped in general. This changes our results only by replacing ∣P(a)∣op\\|P(a)\\|_{\mathrm{op}} with r,∣P(a)∣op\sqrt r\\,\\|P(a)\\|_{\mathrm{op}} in the threshold, Theorem 3.2, and Corollary 3.3. It does not affect Corollaries 3.4 and 3.5, which assume bounded rank.

AuthorsOpenReview ↗

Response to Reviewer rWGs (3/5): Technical follow-up

Technical follow-up to Reviewer rWGs

This follow-up gives the calculations that our answers above refer to: the design term with the factor m+n\sqrt{m+n} and a class of nonuniform designs that it covers (part 1), the argument for empirical row frequencies (part 2), the corrected bound on the design-bias term (part 3), and how the proof separates the random and deterministic perturbations (part 4).

The design term with the factor m+n\sqrt{m+n}

Let N=m+nN=m+n and Ba=∣A(a)⊙P(a)∣opB_a=\\|A(a)\odot P(a)\\|_{\mathrm{op}}, let K⋆K_\star and σ⋆\sigma_\star be the parameters of the random perturbation under population scaling, and let LN=log⁡2N+K⋆log⁡4N/NL_N=\log^2N+K_\star\log^4N/\sqrt N. Dividing the bound of Theorem 4.2 by m\sqrt m gives

\leq C\sqrt r\\,L_N\frac{\sigma_s}{\delta_s} \frac{\sqrt N}{\sqrt m} \left(\frac{\mu}{\sqrt m}+\frac{\mu}{\sqrt n}\right) (\sigma_\star+B_a)\\,.$$ When $m\asymp n$ and the rank, the incoherence, and $\sigma_s/\delta_s$ are bounded, the term with $B_a$ is of order $\widetilde O(B_a/\sqrt n)$. By part 3, $B_a\leq\sqrt r\\,K_A\\|P(a)\\|_{\mathrm{op}}$, so this term vanishes when $\\|P(a)\\|_{\mathrm{op}}$ is bounded. For example, let $p_{ij}=q_i+\Delta_iS_{ij}$, where $0\leq\Delta_i\leq\Delta$, the matrix $S\in\\{0,1\\}^{n\times m}$ has at most $d$ ones in each row and each column, and the row averages $p_i$ and $1-p_i$ are at least $c$. With $H=I-\mathbf 1\mathbf 1^\top/m$, we have $P(1)=\operatorname{diag}(\Delta_i/p_i)\\,SH$ and $P(0)=-\operatorname{diag}(\Delta_i/(1-p_i))\\,SH$. Since $S$ has at most $d$ ones in each row and each column, $\\|S\\|_{\mathrm{op}}\leq d$. As $\\|H\\|_{\mathrm{op}}=1$, both matrices have operator norm at most $\Delta d/c$.
Reviewer_miF3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies heterogeneous treatment effect estimation using panel data with unknown and non-uniform treatment assignment probabilities. The authors formulate the problem as matrix completion, where unit-specific treatment effects are represented by row averages of a treatment effect matrix. To address the limitations of existing matrix completion methods in providing row-wise estimation guarantees, the authors propose a computationally efficient row-scaled truncated SVD estimator that relies only on observed outcomes and treatment assignments without requiring knowledge of treatment propensities. The proposed method is evaluated through synthetic and semi-synthetic experiments.

Critical strengths
  1. The authors establish a novel row-wise l2 perturbation bound for low-rank matrix approximation, extending existing matrix perturbation theory beyond spectral, Frobenius, and entrywise error guarantees. This theoretical contribution is particularly relevant for heterogeneous treatment effect estimation, where accurate estimation at the individual-unit level is required rather than only aggregate estimation accuracy.
  2. The proposed row-scaled truncated SVD estimator offers a relatively simple and computationally efficient approach to estimating unit-specific treatment effects. The estimator does not require knowledge or explicit estimation of treatment propensity scores, which may be difficult to obtain accurately in observational studies.
Critical weaknesses
  1. The proposed estimator relies on low-rankness, incoherence, and signal-to-noise assumptions to establish theoretical guarantees. However, these assumptions may not hold in many real-world observational datasets, where treatment effects can exhibit complex and heterogeneous patterns across individuals and time. It would be helpful for the authors to further discuss the practical validity of these assumptions and evaluate the robustness of the proposed estimator when they are violated.
Questions for authors
  1. How sensitive is the proposed estimator to violations of the low-rank and incoherence assumptions?
1 comment
AuthorsOpenReview ↗

Response to Reviewer miF3

Thank you for your positive assessment and for highlighting the row-wise guarantee and the estimator's simplicity. We answer your comment and question below.

Question 1: “How sensitive is the proposed estimator to violations of the low-rank and incoherence assumptions?”

Theoretically, the guarantee degrades gradually as the rank and incoherence grow. For row-homogeneous designs, both enter Theorem 3.2 only through the factor r3/2μr^{3/2}\mu. Hence, for m≥nm\geq n and fixed design parameters, the normalized error is O~(r3/2μ/n)\widetilde O(r^{3/2}\mu/\sqrt n) as long as the signal condition of Assumption 3.1 holds, and it vanishes whenever r3/2μ=o(n)r^{3/2}\mu=o(\sqrt n) up to logarithmic factors.

To test robustness to approximate low rank, we ran additional experiments and found that our estimator is robust to such violations, in the sense that its error grows gradually with the size of the violation. Starting from the synthetic setup of Appendix A.2 (n=44n=44, m=210m=210, rank-3 means, treatment probability 1/2), we add to each mean matrix an independent random sign matrix scaled by δ\delta. This adds a full-rank component to the signal. We keep the estimator unchanged, including its cross-validated rank selection. For each δ\delta, the table gives the median normalized worst-row error over 200 panels and the size of the full-rank component of the treatment effect relative to its low-rank part, measured in Frobenius norm.

δ\delta00.050.100.15
Worst-row error (∥M^−M∥2,∞/m\Vert \widehat M-M\Vert _{2,\infty}/\sqrt{m})0.2450.2580.2930.339
Relative size of full-rank component0%14%27%41%

In particular, even under a large violation, the increase in error is modest: when the full-rank component is about 41% as large as the low-rank part, the error rises only from 0.245 to 0.339. We will add these experiments to the paper.

Reviewer_fC3xOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies heterogeneous treatment-effect estimation in panel data with independent Bernoulli assignments whose propensities are unknown and possibly non-uniform. The target is row-wise (∥⋅∥2,∞\|\cdot\|_{2,\infty}) recovery of the unit–time effect matrix M=A(1)−A(0)M=A(1)-A(0), which controls unit-level averages Avgi(S)\text{Avg}_i(S) for ∣S∣=Ω(m)|S|=\Omega(m). The estimator rescales each row by its empirical observation frequency and applies gap-thresholded truncated SVD. The main technical result (Theorem 4.2) is a 2→∞2\to\infty perturbation bound for low-rank approximations under random plus deterministic perturbations, proved via contour expansion. Under row-homogeneous designs the row-normalized error is O~(n−1/2)\tilde O(n^{-1/2}). Experiments on synthetic and HeartSteps-calibrated panels compare against Horvitz–Thompson and Hájek estimators.

Critical strengths

Theorem 4.2 gives a ∥⋅∥2,∞\|\cdot\|_{2,\infty}-norm perturbation bound for the low-rank approximation itself, rather than for singular subspaces, and it allows both random and deterministic perturbations. This is consequential to my assessment because it is the paper’s only substantive new technical tool: all of the main results rest on it. It may also be useful beyond causal inference.

Critical weaknesses

1: The claim of handling non-uniform propensities is not supported. For example, under a ramp-up design where pij=0.9p_{ij}=0.9 in the first half of the periods and 0.10.1 in the second half, ∥P∥op≍mn\|P\|_{op}\asymp\sqrt{mn} and the bound becomes O(1)O(1). This is consequential because the abstract and introduction present unknown, non-uniform propensities as a key feature, yet the guarantee essentially covers only row-homogeneous designs.

2: There is a significant gap between theory and experiments. The theoretical threshold depends on unknown quantities, while the experiments use cross-validation instead. The theory covers only long windows, but the empirical advantage appears on short windows. The baselines are only HT and Hájek, with no low-rank methods. This is consequential because the experiments neither validate the algorithm and setting the theory addresses nor show whether the gains come from the proposed method itself or from low-rank smoothing in general.

Questions for authors

1.Under a ramp-up design (e.g., pij=0.9p_{ij}=0.9 then 0.10.1), the bound becomes O(1)O(1). Is this a limitation of row scaling, or is there a lower bound showing that no method can do better?

2.Can the threshold be chosen from data (e.g., using estimated p^i\hat p_i) while keeping the guarantee of Theorem 3.2?

3.How does the method compare with low-rank baselines (e.g., MC-NNM, USVT) on the window-query tasks?

3 comments
AuthorsOpenReview ↗

Response to Reviewer fC3x (1/3)

Thank you for your detailed review and for recognizing the potential value of the row-wise perturbation result beyond causal inference.

We answer your comments and questions below and hope you will strengthen your support for the paper.

Question 1: “Under a ramp-up design (e.g., pij=0.9p_{ij}=0.9 then 0.1), the bound becomes O(1)O(1). Is this a limitation of row scaling, or is there a lower bound showing that no method can do better?”

It is a limitation of row scaling, and other estimators can do better.

Indeed, a natural variant of our estimator does better by using the fact that propensities are shared across units (that is, pij=pjp_{ij}=p_j), so each pjp_j can be estimated from the nn assignments at time jj.

Concretely, for each action aa, it computes a truncated SVD of the zero-filled matrix Z(a)Z(a), with entries Zij(a)=Dij(a)YijobsZ_{ij}(a)=D_{ij}(a)Y^{\mathrm{obs}}_{ij}, and then divides column jj by its empirical frequency p^j(a)=n−1∑iDij(a)\hat p_j(a)=n^{-1}\sum_iD_{ij}(a). Thus it scales columns instead of rows, and only after the SVD.

Since EZ(a)=A(a)diag⁡(pj(a))\mathbb EZ(a)=A(a)\operatorname{diag}(p_j(a)) has the same rank as A(a)A(a), and Z(a)Z(a) has independent entries, Theorem 4.2 applies to Z(a)Z(a) with no design-bias term.

A short argument then transfers its row-wise bound to A(a)A(a). When every pj(a)p_j(a) is at least a constant cc, the variant attains the same O~(1/n+n/m2)\widetilde O(\sqrt{1/n+n/m^2}) rate as Corollary 3.3, with constants depending on cc.

We give the details in the technical follow-up in this thread and will add this variant to the paper. This variant covers designs in which all units follow a common time-varying schedule, such as ramp-ups.

Question 2: “Can the threshold be chosen from data (e.g., using estimated p^i\hat p_i) while keeping the guarantee of Theorem 3.2?”

For row-homogeneous designs, yes. There, rp=1r_p=1 and P(a)=0P(a)=0, so the threshold depends on the design only through qq. With high probability, min⁡a,ip^i(a)\min_{a,i}\hat p_i(a) is within a constant factor of qq. Using this estimate in place of qq therefore changes the threshold by at most a constant factor, and Theorem 3.2 continues to hold with adjusted constants (Remark B.1).

More generally, beyond row-homogeneous designs, the threshold also depends on how the propensities vary within rows, and the constants in our analysis are conservative. As with most theoretical results, there is thus a gap between the threshold that our guarantee prescribes and the one that works best in practice. Tightening these constants is an important direction, but it is beyond the scope of this work.

That said, from a practical perspective, the threshold is a hyperparameter, and hyperparameters of this kind are routinely chosen from data by cross-validation. In our experiments, we use Algorithm 1 with the truncation level selected by five-fold cross-validation on held-out observed outcomes (Appendix A.1), just as MC-NNM (Athey et al., 2021) selects its regularization parameter.

Weakness 2: “The theory covers only long windows, but the empirical advantage appears on short windows.” Our guarantee covers windows much shorter than mm. By (1.1), the error for a window SS is at most m/∣S∣\sqrt{m/|S|} times the normalized row error. Hence, when m≥nm\geq n, the bound vanishes for every window with ∣S∣≫m/n|S|\gg m/n, up to logarithmic factors. In balanced panels, this includes windows of polylogarithmic length. Our experiments (m/n≈4.8m/n\approx4.8) show a clear advantage at such intermediate lengths as well. For example, at length 10 our median RMSE is 0.070, compared with 0.190 for HT and 0.115 for Hájek (Table 2).

AuthorsOpenReview ↗

Response to Reviewer fC3x (2/3)

Question 3: “How does the method compare with low-rank baselines (e.g., MC-NNM, USVT) on the window-query tasks?”
We ran both baselines on the panels, assignments, cross-validation folds, and window queries of Appendix A: 200 synthetic panels and 500 panels calibrated to the HeartSteps study. On the synthetic panels, our estimator is more accurate than MC-NNM on windows of intermediate length, and MC-NNM is more accurate on short windows and on the full window. On the HeartSteps-calibrated panels, MC-NNM is more accurate at every length.

However, MC-NNM is far more expensive: in a single-thread benchmark, it took about 3,000 times as long as our estimator (34 versus 0.011 seconds per synthetic panel, as in the last column of the table). USVT is as cheap as our estimator but less accurate at 15 of the 16 window lengths on the synthetic panels. We will add these comparisons, at all window lengths, to the paper.

Baselines.

We implement the published methods and tune their hyperparameters by the same five-fold cross-validation as for our estimator: the penalty of MC-NNM (Athey et al., 2021), which includes unpenalized unit and time effects, and the rank of USVT (Chatterjee, 2015). (We tune the rank of USVT because its published threshold is a worst-case bound computed from the range of the outcomes and the panel size, and no singular value of the data reaches it in any of our panels, so the published version estimates a zero effect for every unit.)

Results. The table gives median RMSEs over the synthetic panels at five of the 16 window lengths, and the median time per panel for cross-validation and fitting on a single thread (five panels).

Window length1730105210Time (s)
Ours0.17770.07880.05570.05240.03140.011
MC-NNM (unit and time effects)0.10660.06570.05730.06000.021534
USVT (rank chosen by CV)0.17720.08440.06290.06030.04200.018

Observations.

On the synthetic panels, our estimator has lower RMSE than MC-NNM for windows of length 35 to 105 and comparable RMSE at lengths 21 and 30, while MC-NNM has lower RMSE for windows of length at most 15 and for the full window. Our estimator has lower RMSE than USVT at 15 of the 16 lengths.

On the HeartSteps-calibrated panels, MC-NNM has lower RMSE than our estimator at every length.

MC-NNM is slow because it traces a path of 100 penalties for cross-validation, which took tens of thousands of proximal-gradient iterations per action and panel, each with an SVD. Our estimator and USVT need one truncated SVD per fold. On the HeartSteps-calibrated panels, the median times were 34 seconds for MC-NNM and 0.006 seconds for our estimator. At 176 units and 840 periods, MC-NNM took about 9 minutes per panel, compared with 0.2 seconds for our estimator.

AuthorsOpenReview ↗

Response to Reviewer fC3x (3/3)

Technical follow-up to Reviewer fC3x

A variant for propensities shared across units

In our answer to Question 1, we described a variant of our estimator for designs in which all units share the same time-varying propensities, such as your ramp-up design. Here we give the details omitted there and show that this variant attains the rate of Corollary 3.3.

Fix an action aa, and write A=A(a)A=A(a), Z=Z(a)Z=Z(a), πj=pj(a)\pi_j=p_j(a), and Π=diag⁡(πj)\Pi=\operatorname{diag}(\pi_j). Assume that ∣Yij(a)∣≤K|Y_{ij}(a)|\leq K and c≤πj≤1−cc\leq\pi_j\leq1-c for all jj. When the propensities are shared across units, B≔EZ=AΠandZ=B+N,,B\coloneqq\mathbb EZ=A\Pi\qquad\text{and}\qquad Z=B+N\\,, where NN has independent, centered entries bounded by 2K2K. Column scaling preserves the structure that our analysis uses. The column space of BB equals that of AA, so it has the same incoherence parameter, and the incoherence parameter of its row space is at most (1−c)/c(1-c)/c times that of AA. Moreover, rank⁡(B)=rank⁡(A)=r\operatorname{rank}(B)=\operatorname{rank}(A)=r and σr(B)≥c,σr(A)\sigma_r(B)\geq c\\,\sigma_r(A). Hence, if c,σr(A)≥6∣N∣opc\\,\sigma_r(A)\geq6\\|N\\|_{\mathrm{op}}, Theorem 4.2 with E0=0E_0=0 and s=rs=r bounds ∣[Z]r−B∣2,∞/m\\|[Z]_r-B\\|_{2,\infty}/\sqrt m by O~(1/n+n/m2)\widetilde O(\sqrt{1/n+n/m^2}).

The variant returns A^=[Z]rΠ^−1\widehat A=[Z]_r\widehat\Pi^{-1}, where Π^=diag⁡(p^j(a))\widehat\Pi=\operatorname{diag}(\hat p_j(a)). The exact identity A^−A=([Z]r−B),Π^−1+A,(ΠΠ^−1−I)\widehat A-A=([Z]_r-B)\\,\widehat\Pi^{-1}+A\\,(\Pi\widehat\Pi^{-1}-I) gives, whenever max⁡j∣p^j(a)−πj∣≤e≤c/2\max_j|\hat p_j(a)-\pi_j|\leq e\leq c/2, ∣A^−A∣2,∞m≤2c⋅∣[Z]r−B∣2,∞m+2Kc,e,.\frac{\\|\widehat A-A\\|_{2,\infty}}{\sqrt m}\leq\frac2c\cdot\frac{\\|[Z]_r-B\\|_{2,\infty}}{\sqrt m}+\frac{2K}{c}\\,e\\,. This step is deterministic, so Π^\widehat\Pi may depend on the same assignments as ZZ. By Hoeffding's inequality and a union bound over jj, we may take e=log⁡(2m/δ)/(2n)e=\sqrt{\log(2m/\delta)/(2n)} with probability at least 1−δ1-\delta. Combining the two actions gives the rate of Corollary 3.3. The rank can also be selected by the gap rule of Algorithm 1 applied to ZZ. Since ZZ is not rescaled, the threshold then depends only on KK and the dimensions. Denoising before dividing by estimated propensities also appears in Bhattacharya and Chatterjee (2022), who prove consistency in mean squared error. Theorem 4.2 supplies the row-wise guarantee needed here.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.