Smaller Confidence Intervals From IPW Estimators via Data-Dependent Coarsening

Smaller Confidence Intervals From IPW Estimators via Data-Dependent Coarsening

\pagenumbering{arabic}

Introduction

An observational study consists of several individuals who are described by a vector of covariates $x\in \mathbb{R}^d$. In the study, each individual $x$ receives treatment with some fixed but unknown probability $e(x)$. We observe tuples of the form $(x, y, t)$ of whether the treatment was assigned ($t = 1$) or not ($t = 0$) and the corresponding treatment-dependent outcome $y$. {Let {$X$ be the covariate random variable and} $Y(t)$ be the random variable denoting the outcome when $T=t$ (for $t\in\ensuremath{\left\{0, 1\right\}}{}$), so that $y = T Y(1) + (1-T) Y(0)$} {(note that $T, Y(1), Y(0)$ can depend on $X$).} The key quantity of interest is the average treatment effect $\tau$, which is the average effect of the treatment on the population of individuals, i.e., {$\tau \coloneqq\operatorname{\mathbb{E}}[Y(1)-Y(0)]$}. As an example the individuals can be patients with covariates that include the details of their medical history, the treatment corresponds to whether they received some medication or not, and the outcome is the the extent of the patient's symptoms. In another example the individuals are customers, the covariates include price sensitivity and interests, the treatment corresponds to whether they receive some discount, and the outcome is their satisfaction.

The difficulty in estimating the average treatment effect $\tau$ is that, for each individual, we only observe their outcome either with or without treatment but not both, i.e., the data is censored. To estimate $\tau$ from censored data, we need to account for the probabilities $e(x)$ with which each individual is assigned treatment. These probabilities are known as propensity scores.

Inverse propensity-score weighted (IPW) estimators are a family of estimators that use the propensity scores $e(x)$ for each $x$ and a censored dataset $\mathscr{C}$ as input, and output a value $\ensuremath{\tau_\mathrm{IPW}}{}(\mathscr{C};e)$. This value is an unbiased estimate of $\tau$ if $\mathscr{C}$ is drawn from an underlying distribution $\mathcal{D}$ that satisfies a standard assumption--namely unconfoundedness--which we formally define in (ref). IPW estimators are widely used in a variety of fields from Economics dehejia1998causal,dehejia2002propensity,galiani2005water,abadie2006large,abadie2016matching, to Statistics rosenbaum2002overt,rubin2006matched, to Medicine robin1997estimating,christakis2003health,austin2008critical, to Political Science brunell2004turnout,sekhon2004quality,ho2007matching, to Sociology morgan2006matching,lee2009estimation,oakes2017methods. There are several reasons for their popularity including that $\ensuremath{\tau_\mathrm{IPW}}{}$ is: (1) easy to describe, (2) efficiently computable, (3) unbiased given accurate propensity scores $e(x)$, and (4) asymptotically normal. Nevertheless, these vanilla IPW estimators suffer from some stability issues that we explore below.

\noindentIssue I: Inaccuracies. IPW estimators enjoy the aforementioned good statistical properties when provided with accurate propensity scores. Unfortunately, the IPW estimator $\ensuremath{\tau_\mathrm{IPW}}{}(\mathscr{C};\widehat{e})$ can be arbitrarily far from $\tau$, when the propensity score estimates $\widehat{e}$ slightly differ from the true propensity scores $e$ even on one covariate by an additive amount $\varepsilon>0$. This leads us to the following question.

In the special case of $\varepsilon=0$, practitioners and researchers have devoted significant effort to reducing the size of the confidence intervals arising from IPW estimators, e.g., hirano2003efficient,li2018overlapWeights. This includes several doubly-robust estimators that utilize predictions of covariate-level outcomes {(i.e., {predictions of $\mu_t(x)\coloneqq\operatorname{\mathbb{E}}[Y(t)\mid X{=}x]$} for $t=0$ and $t=1$)} to achieve smaller confidence intervals robins2005doublyRobust,chernozhukov2018doubleML,chernozhukov2022simple,foster2023orthognalSL. However, the understanding of the $\varepsilon > 0$ case is limited (see (ref) for some prior work on inaccurate propensity scores).

\noindentIssue II: Outliers. Root-mean-squared-error (RMSE) is the main quantity of interest of an estimator of the average treatment effect $\tau$; not only because it checks the consistency of the estimator but also because it controls the size of the resulting confidence interval at a fixed confidence level. It is well known that given $n$ samples, the RMSE of both IPW and doubly-robust estimators is proportional to $\sqrt{\frac{1}{n} \operatorname{\mathbb{E}}_\mathcal{D}\left[\frac{1}{e(X)(1-e(X))}\right]}$ imbens2015causal,farrell2015robust,chernozhukov2022simple,foster2023orthognalSL.

An outlier in this context is defined as a covariate $x$ whose propensity score $e(x)$ is close to $0$ or $1$. To be more concrete, let covariate $x$ be a $\beta$-outlier if $e(x)(1-e(x)) < \beta$. One important issue with the aforementioned expression of RMSE is that it goes to $\infty$ if there exists an outlier with positive mass. Therefore, even a single $\beta$-outlier, with small $\beta$, can significantly affect the size of the confidence interval of $\tau$.

A popular heuristic to increase robustness to such outliers is to remove or trim all $\beta$-{outliers} from the data for some $\beta = \Omega(1)$ crump2009dealing. While this ensures that the standard deviation is at most $O({1/\sqrt{\beta n}})$, it can increase the bias of the estimation to $\rho$, where $\rho$ is the probability mass of the $\beta$-outliers li2018overlapWeights. Hence, this would result in an RMSE and, hence, confidence interval of size proportional to $\rho+O\left({1/\sqrt{\beta n}}\right)$ which is finite, as opposed to the RMSE of IPW which is $\infty$ in this case, but still it does not converge to zero. Unfortunately, without further assumptions, it is information-theoretically impossible to find an estimator with RMSE that goes to zero as $n$ goes to infinity (for more details see (ref)). This leads us to the following question.

{In this work, we study both questions Q1 and Q2. When $\varepsilon>0$, in the regime of Q1, none of the aforementioned estimators (i.e., IPW, doubly-robust, and trimmed-IPW estimators) guarantee RMSE that decays with $n$; unless there are no $\beta$-outliers for $\beta\gg \varepsilon$. When $\rho=\omega({1/\sqrt{n}})$, in the regime of Q2\textbf{,} then none of the aforementioned \mbox{estimators guarantee RMSE smaller than $\rho+O({1/\sqrt{n\beta}})$.}}

Our Main Result: Estimation Robust to Inaccuracies and Outliers

Our goal is to efficiently find an estimator whose confidence intervals satisfy the properties desired in Q1 and Q2. We make the following natural assumption on the outcomes.

We expect Lipschitzness to hold in many settings such as when $\mu_t(x)$ belongs to a parametric family {(e.g., see wager2018estimation who require Lipschitzness).} For instance, a common assumption in the literature is that $\mu_t$ has a linear parametric form, say, $\mu_t(x)=w_t^\top x +\varepsilon$ imbens2015causal,hernan2023causal. This implies that $\mu_t$ is $\ensuremath{\left\lVert w_t \right\rVert}_1$-Lipschitz and satisfies (ref) when $w_t$ has a bounded norm. Lipschitzness of $\mu(x)$ alone, however, does not address any of the issues that we mentioned before: all aforementioned estimators are independent of the geometry of the covariates, hence, we can always rearrange the covariates to satisfy Lipschitzness. Our estimators, on the other hand, will make use of the geometry of covariates.

Apart from the Lipschitzness of outcomes, we also need assumptions to exclude certain edge cases where it seems hard (if not impossible) to achieve a small RMSE. For some small parameter $\alpha>0$, a number $k=O(1)$, we assume that $\beta$-outliers satisfy the following assumptions.

If sparsity does not hold then, under mild conditions, there is a large ball $B$ most of whose mass is $\beta$-outliers (see (ref)). Since $B$ has a large radius, covariates well inside $B$ are far from any non-outlier and, hence, we cannot use Lipschitzness to estimate the expected outcomes (with and without treatment) at these covariates. Further, estimating these expected outcomes directly may require arbitrarily large samples as their propensity scores can be arbitrarily close to 0 or 1.

If isolation does not hold, then either (i) we need a large number of (small) balls to cover the covariates {(see (ref))} or (ii) any cover with $O(1)$ balls has two close balls. In case (i), we need a huge number of samples to identify the good partition $\mathcal{S}$. Intuitively, this is because the VC-dimension of unions of $k$ balls is at least $\Omega(k)$, leading to a need for $\Omega(k)$ samples, which goes to $\infty$ as $k\to\infty$ (see (ref)). In case (ii), the cover can be identified from finite samples, but how to identify it computationally efficiently is unclear. Under the assumptions above, we can find estimators with better guarantees than existing estimators.

This algorithm gives a unified approach for handling inaccuracies in propensity scores and outliers. Concretely, the algorithm, namely, (ref), answers both questions Q1 and Q2 in the affirmative: at one extreme, where there are no $\beta$-outliers (i.e., $\rho=0$) but the provided propensity scores have $\varepsilon$-error, the algorithm achieves an RMSE $O(\varepsilon)$ for $\beta \geq {\rho/d}$ and $O(\varepsilon+{{1/\sqrt{n\beta}}})$ otherwise. At the other extreme, where accurate propensity scores are known, but $\rho$-fraction of the points are outliers, the algorithm achieves an RMSE $O(\alpha\rho+{{1/\sqrt{n\beta}}})$. This quantity is $\Omega\left({1/\alpha}\right)$-times smaller than $\rho+O({1/\sqrt{n\beta}})$ in the regime $\rho=\omega({1/\sqrt{n\beta}})$ where trimmed-IPW performs {poorly}, and matches the guarantee of trimmed-IPW otherwise (when $\rho=O({1/\sqrt{n\beta}})$).

To put our algorithmic contribution in context, we verify that existing estimators have large confidence intervals under the same assumptions (see also (ref)).

\footnotetext{(ref) does not take $L$ as input. If $L$ is provided, then $\alpha L$ in the RMSE can be improved to $\min{\{1,\alpha L\}}$: one can simply check if $\alpha L\leq 1$ and, if so, output the CIPW estimate, and, otherwise, use the $\beta$-Trimmed IPW estimate.}

Other Contributions

In this section, we highlight some other important contributions of our work. In particular, in (ref), we explore the robustness of a natural extension of IPW estimators which we call coarse IPW estimators (CIPW), and, in (ref), we justify the need for data-dependent clustering.

Properties of CIPW Estimators

We introduce a family of Coarse IPW (CIPW) estimators that captures almost all the existing IPW estimators in the literature and we explore their performance with respect to Q1 and Q2.

\noindentCIPW Estimators. Each estimator $\tau_{\mathdutchcal{S}, N}$ in this family is specified by a partitioning of the covariate space into sets $\mathdutchcal{S}=\left\{S_1, S_2, \dots\right\}$ and an additional null set $N$. Given $\left(\mathdutchcal{S}, N\right)$, the corresponding CIPW estimator $\tau_{\mathdutchcal{S}, N}$ is defined as the IPW estimator over the coarse domain--where all covariates belonging to any one set $S\in \mathdutchcal{S}$ are merged into a single covariate and all covariates in the null set $N$ are ignored (see (ref) for a formal definition). This family captures the IPW estimators as well as the aforementioned variants (see (ref) below). (The only exception is doubly-robust estimators, which are captured by using doubly-robust estimators instead of IPW on the coarse domain.)

\noindentRobust Root Mean Squared Error. Since all estimators $E$ we consider, even the ones in (ref), are asymptotically normal, their confidence intervals scale with their root-mean-squared-error (RMSE), defined as $\sqrt{\operatorname{\mathbb{E}}_{\mathscr{C}\sim \mathcal{D}}[\sabs{E(\mathscr{C}; e)-\tau}^2]},$ where $\mathscr{C}$ is the dataset of size $n$ and $e$ is the propensity scores. Our interest is in the worse-case RMSE under additive perturbations of propensity scores: for any $\varepsilon>0$, let $B(e,\varepsilon)$ be the $\ell_\infty$-ball of radius $\varepsilon$ around $e$ and define

As mentioned in (ref), for any $\varepsilon>0$, the $\varepsilon$-Robust RMSE of IPW and doubly-robust estimators can be arbitrarily larger than their respective non-robust RMSE ((ref)). When $\varepsilon=0$, we simplify the above notation and use $\operatorname{RMSE}_{\mathcal{D}}{(E)}$.

\noindentComputational Complexity. Since we care about a data-dependent way to design the CIPW estimator, a natural question that arises is to find the best CIPW estimator given a censored dataset $\mathscr{C}$ of size $n$ from $\mathcal{D}$ and $\varepsilon>0$. In particular, we have to find a partition $(\mathdutchcal{S}, N)$ such that $\tau_{\mathdutchcal{S}, N}$ has the minimum $\varepsilon$-Robust RMSE among all CIPW estimators.

In other words, we want to solve the optimization problem: $\operatornamewithlimits{arg\,min}_{\mathdutchcal{S}, N}\; \operatorname{RMSE}_{\mathcal{D},\varepsilon}{(\tau_{\mathdutchcal{S}, N})}.$ We begin with the special case of this problem with $\varepsilon=0$ and consider its decision version: given number $U$, verify whether $\min_{\mathdutchcal{S}, N}\; \operatorname{RMSE}_{\mathcal{D}}{(\tau_{\mathdutchcal{S}, N})}\leq U$. We call this problem Min-RMSE, whose inputs are $U$ and (all relevant parameters of) $\mathcal{D}$.

Since our focus is on computational complexity, we further assume that for any fixed partition $(\mathdutchcal{S}, N)$, $\operatorname{RMSE}_{\mathcal{D}}{(\tau_{\mathdutchcal{S}, N})}$ is efficiently computable. We show that even in this special case, the problem is $\mathsf{NP}$-hard. In fact, not only is it $\mathsf{NP}$-hard, but also notoriously hard to approximate.

In the proof of (ref) we construct an exponential-gap-inducing partition from Subset-Sum to Min-RMSE. We overview key ideas and present the complete proof in (ref).

\noindentA Criterion Guaranteeing Small Robust RMSE. Given the computational hardness of finding the CIPW estimator with the minimum RMSE (even approximately), we focus on finding a good CIPW estimator that is robust to inaccuracies in propensity scores and outliers. Toward this, we will analyze an upper bound on $\operatorname{RMSE}_{\mathcal{D}}(\tau_{\mathdutchcal{S}, N})$ focusing, for now, on the $\varepsilon=0$ case. The standard bias-variance decomposition implies that $ \operatorname{RMSE}_{\mathcal{D}}(\tau_{\mathdutchcal{S}, N}) = \operatorname{Bias}_{\mathcal{D}}(\tau_{\mathdutchcal{S}, N}) + {\operatorname{Var}_{\mathcal{D}}(\tau_{\mathdutchcal{S}, N})}^{{1/2}} $. After algebraic manipulation, we derive explicit expressions for both quantities ((ref)). While these expressions are complicated, the key takeaway is that with bounded outcomes and $L$-Lipschitzness, the bias and variance are upper bounded as follows

where $e(S)$ is the average propensity score over $S$, i.e., $e(S) = \frac{1}{\mathrm{vol(S))}}\int_S e(x) \text{d} x$ and $\operatorname{diam}(S) \coloneqq \max_{x,x'\in R} \ensuremath{\left\lVert x-x' \right\rVert}_p$ with the same $p$ as in (ref) (Lipschitzness). While these formulas are still not very simple, they are at least independent of the distribution of the outcomes. Moreover, observe the following from (ref):

These arguments lead to the following simple criterion for a good partition for a CIPW estimator.

The aforementioned upper bounds ((ref)) imply that any CIPW estimator constructed from an \ensuremath{(\alpha,\beta,\gamma)}-good-local partition with $\gamma\leq {1/2}$ has a RMSE of at most $O\left(\alpha L+\gamma+{1/\sqrt{n \beta}}\right)$. Crucially, the criteria in (ref) are independent of the distribution of the outcomes which may not be known. Nevertheless, Lipschitzness is crucial to obtain such a criterion: for instance, without Lipschitzness, for any $\alpha,\beta,\gamma>0$ and any \ensuremath{(\alpha,\beta,\gamma)}-good-local partition different from IPW, (ref) constructs a distribution $\mathcal{D}$ where $\operatorname{RMSE}_{\mathcal{D}}{\left(\tau_{\mathdutchcal{S}, N}(C)\right)}\geq {1/3}$. Apart from a small non-robust RMSE, importantly, we show that a good-local partition also implies a small robust RMSE.

Hence, not only does a good-local partition have a small RMSE but, if the inaccuracy in the propensity scores $\varepsilon$ is much smaller compared to the coarse propensity scores, then it also has a small $\varepsilon$-Robust RMSE. Contrast this with existing estimators: while $\varepsilon$-Robust RMSE of IPW and doubly-robust estimators can be arbitrarily larger than their RMSE, the $\varepsilon$-Robust RMSE and RMSE of a CIPW estimator based on a good-local partition are $\left({\varepsilon/\beta}\right)$-close. Intuitively, this is because in any \ensuremath{(\alpha,\beta,\gamma)}-good-local partition $(\mathdutchcal{S}, N)$, for all $S\in \mathdutchcal{S}$, the coarse propensity score $e(S)$ is bounded away from $0$ and 1. This is useful as, when propensity scores are bounded away from $0$ and 1, then $\varepsilon$-additive errors in propensity scores also imply $\left(1\pm O(\varepsilon)\right)$-multiplicative errors---which are significantly easier to handle. Finally, we note that CIPW estimators arising from any good-local partition are asymptotically normal ((ref)), allowing us to obtain corresponding confidence intervals.

\noindentLearning a Good-Local Partition. We note that (ref) requires the partition to be independent of the dataset on which the estimator is evaluated. Hence, one must first learn a good-local partition $(\mathdutchcal{S}, N)$ using the dataset $\mathscr{C}$ and then evaluate the learned $\tau_{\mathdutchcal{S}, N}$ on a fresh dataset $\mathscr{C}'$. However, finding a good-local partition seems challenging even from a statistical perspective. For instance, to even test whether a given partition $(\mathdutchcal{S}, N)$ is good, we, at least, require a uniform convergence bound over all the possible sets that we might use, e.g., this is needed to even check whether $\mathcal{D}(N) \leq \gamma$ or not. Our next result shows that, even assuming that the sets in the partition belong to a VC class, it is not possible to learn a good-local partition without further assumptions.

This lemma excludes the existence of any finite-sample algorithm that finds a good-local partition without further assumptions. Briefly, the proof uses that $\mathdutchcal{S}$ may contain a large number of subsets and reduces PAC-learning of a union of $\abs{\mathdutchcal{S}}$ intervals (of width at most $\alpha$) up to $\gamma$-error in the agnostic setting to finding an \ensuremath{(\alpha,\beta,\gamma)}-good-local partition. The result then follows by verifying that the VC dimension of this class is at least $\abs{\mathdutchcal{S}}$ and using lower bounds on the sample complexity of PAC learning in the agnostic setting shalev2014understanding.

This brings us to (ref) (Sparsity and Isolation). These assumptions guarantee the existence of an \ensuremath{(\alpha, \Omega(\beta), 0)}-good-local partition $(\mathdutchcal{S}^\star, N^\star)$ where $\abs{\mathdutchcal{S}^\star}=k=O(1)$ and all sets of the partition belong to a family with VC-dimension $O(d)$. This allows us to build the algorithm promised in (ref), although the resulting estimator is a generalized version of CIPW. We refer to (ref) for the technical details.

Need for Data Dependence

In this section we ask whether there exists some CIPW, different from IPW, that has better RMSE uniformly over all unconfounded distributions $\mathcal{D}$.

Therefore, not only is it impossible to weakly beat the RMSE of the IPW estimator, but any CIPW estimator different from IPW has at least a constant RMSE for some distribution $\mathcal{D}$ irrespective of the number of samples $n$. This negative result demonstrates that the true power of CIPW estimators can only be realized by designing the estimator in a data-dependent way (see (ref) for further discussion).

Related Work

Sensitivity Analysis in Causal Inference includes a large body of work studying the performance of estimators with inaccurate propensity scores rosenbaum2002observational. The literature on sensitivity analysis studies several error models, including pointwise multiplicative errors in propensity scores (which are implied by bounding the odds ratio, i.e., $\max_x \left(\nicefrac{e(x)}{\widehat{e}(x)}\right)\cdot\left(\nicefrac{(1-\widehat{e}(x)}{(1-e(x))}\right)$) tan2006distributional,kallus2019interval,kallus2021minimax, errors with bounded expected value of the odds-ratio huang2023variancebased, and fixed interval bounds on propensity scores aronow2012interval. However, almost all of the works operate under the assumption that there are no $\beta$-outliers for some $\beta=\Omega(1)$. In contrast, we allow the existence of outliers and design new estimators that, under mild assumptions ((ref)), have a smaller RMSE than existing estimators ((ref)).

Robust Statistics includes a growing number of works that, broadly speaking, solve estimation tasks amidst data inaccuracies (ranging from adversarial corruption huber2004robust to interval censoring cohen1991truncated)--with a growing focus on computational efficiency diakonikolas2019recent. The simplest task is perhaps estimating the mean of a Gaussian distribution when a \(\rho\)-fraction of samples is adversarially corrupted. Here, common estimators (e.g., the empirical mean) fail, but robust alternatives can estimate the true mean within an additive factor \(O(\rho)\). Moreover, without additional assumptions, it is information-theoretically impossible to achieve a better estimation of the mean. Such information-theoretic lower bounds also arise in our work. For instance, given a distribution $\mathcal{D}$ with a mass $\rho$ of outliers, any estimator must have an RMSE of at least $\Omega(\rho)$ ((ref)). Under (ref), however, one can find more robust estimators (e.g., (ref)).

Learning propensity scores from data is necessary as propensity scores are unknown in an observational study. A number of Machine Learning methods are used for estimating propensity scores: from simple methods such as logistic regression (see westreich2010estimation), to more sophisticated methods such as regression trees, random forests, and boosted variates of these methods mccaffrey2004propensity, to neural networks westreich2010estimation. These methods, however, are susceptible to errors in the estimated propensity scores. In this work, we show that they can be combined with CIPW estimators to increase the robustness of the resulting estimators to these errors.

{ Non-propensity-score-based estimators of the average treatment effect predict the expected (potential) outcomes conditional on the covariates, i.e., they predict $\mu_t(x)\coloneqq \operatorname{\mathbb{E}}[Y(t)\mid X{=}x]$ for each covariate $x$ and $t\in \ensuremath{\left\{0, 1\right\}}$ chernozhukov2024applied. While this quantity is identifiable under unconfoundedness, \footnote{To see why the quantity is identifiable, observe that, under unconfoundedness, $\operatorname{\mathbb{E}}[Y(t)\mid X{=}x] = \operatorname{\mathbb{E}}[Y(t)\mid X{=}x, T{=}t]$ and $Y(t)$ is observed when $T=t$.} the estimations error scale with inverse propensity scores (concretely, with $\frac{1}{{e(x)(1-e(x))}}$) and, hence, can be large in the presence of outliers $x$ whose propensity scores $e(x)$ are close to 0 or 1 wager2018estimation. It would be interesting to see if a similar approach as CIPW estimators can reduce the errors of estimators predicting the conditional expected outcomes $\mu_t(x)$ in the presence of outliers. }

Preliminaries

\noindentCausal Inference Setup. An observational study involves several individuals or units (e.g., patients); each described by a vector of covariates $X\in \mathbb{R}^d$ (encoding, e.g., medical history). In the study, each unit $x$ is assigned a treatment $T$ (e.g., medication) with some fixed but known probability $e(x)\in (0,1)$ independent of all other units and we observe a treatment-dependent outcome $Y(T)$ (e.g., the extent of the patient's symptoms). We focus bounded outcomes $Y(T)\in [-1,1]$ and binary treatments $T\in \ensuremath{\left\{0, 1\right\}}$.\footnote{Our results extend to categorical treatments paying the standard degradation with the number of categories and to outcomes in $[-B, B]$ (for any $B>0$) with linear degradation in the RMSE with $B$.} The tuple $(X,Y(0),Y(1),T)$ has an unknown joint distribution $\mathcal{D}$. The following parameters of $\mathcal{D}$ are of interest: for each $x$ and $t\in \ensuremath{\left\{0, 1\right\}}$: \[ \mathcal{D}(x) \coloneqq \operatorname{\operatorname*{Pr}\nolimits}_\mathcal{D}[X{=}x]\,,\qquad \mu_t(x) \coloneqq \operatorname{\mathbb{E}}_\mathcal{D}[Y(t) \mid X{=}x]\,,\qquad v_t(x) \coloneqq \operatorname{Var}_\mathcal{D}[Y(t) \mid X{=}x]\,. \] which denote the probability mass, conditional means, and conditional variances at $x$ respectively. Of specific interest will be outlier covariates: for any $\beta>0$ and (possibly inaccurate) propensity scores $e\colon \mathbb{R}^d\to (0,1)$, covariate $x\in \mathbb{R}^d$ is said to be a $\beta$-outlier with respect to $e$ if $e(x)(1-e(x)) < \beta$. We denote the set of $\beta$-outliers with respect to $e$ by \[ \textcolor{white}{.}\qquad\ensuremath{\mathscr{O}}{}(\beta; e)\coloneqq \left\{x\in \mathbb{R}^d\colon e(x)(1-e(x)) < \beta\right\}\,. \tag{$\beta$-outliers w.r.t. $e$} \]

\noindentAverage Treatment Effect. An important goal in causal inference is to estimate the effect of treatment on the average outcomes, which is known as the average treatment effect imbens2015causal,hernan2023causal. Concretely, the average treatment effect is defined as \[ \textcolor{white}{.}\hspace{30mm} \tau \coloneqq \operatorname{\mathbb{E}}_\mathcal{D}\left[Y(1) - Y(0)\right]. \tag{Average Treatment Effect} \] If one had access to independent samples from $\mathcal{D}$, then we could estimate the above expectation using empirical averages. The main difficulty is that the samples are censored: instead of observing sample $s=(X, Y(0), Y(1), T)$, only the censored sample $c=(X, Y(T), T)$ is observed. That is if the unit was assigned treatment, then $Y(0)$ is censored, and $Y(0)$ is censored otherwise. Due to this censoring, $\tau$ is unidentifiable without additional assumptions on $\mathcal{D}$.\footnote{{One simple example demonstrating this is as follows: let $Y(0)$ be deterministically $0$ and $Y(1)=T\cdot A + (1-T)B$ for some random variables $A$ and $B$ independent of $T$. Here, $\tau=\operatorname{\mathbb{E}}_\mathcal{D}[Y(1)-Y(0)]=\operatorname{\mathbb{E}}[T]\operatorname{\mathbb{E}}[A]+\operatorname{\mathbb{E}}[1-T]\operatorname{\mathbb{E}}[B]$. However, since $Y(1)$ is only observed if $T=1$, one does not gain any information about $\operatorname{\mathbb{E}}[B]$ and, hence, $\operatorname{\mathbb{E}}[B]$ is non-identifiable from the censored data implying that $\tau$ is also non-identifable.}} Unconfoundedness is a standard assumption that enables identifiability. It requires that conditional on the covariates the outcomes are independent of the treatment, i.e.,

Unconfoundedness is known by many other names: ignorability, conditional exogeneity, conditional independence, and selection on observables imbens2015causal,hernan2023causal.

\noindentEstimators. An estimator $E$ of $\tau$ is a function that takes a censored dataset $\mathscr{C} =\left\{\left(x_i, y_i, t_i\right)\colon 1\leq i\leq n\right\}$ as input and outputs a scaler value $E(\mathscr{C})$. Apart from $\mathscr{C}$, $E$ may also get some additional or nuisance parameters $\eta$, such as the propensity scores, in which case, we overload the notation to $E(\mathscr{C};\eta).$ (See (ref) for several examples.) Ideally, we want $E(\mathscr{C};\eta)$ to be equal to $\tau$. Since this is almost never possible, we settle for confidence intervals on $\tau$. To obtain confidence interval $E(\mathscr{C};\eta)$ must have a known distribution, e.g., a standard normal distribution. This is guaranteed by asymptotic normality (which requires that $E(\mathscr{C};\eta)$ approaches a normal distribution as $\abs{\mathscr{C}}\to \infty$). We show that CIPW estimators constructed from good-local partitions are asymptotically normal in (ref).

Coarse Inverse Propensity-Score Weighted Estimators

In this section, we formally define CIPW estimators, which are inspired by the success of tree-methods in estimating treatment effects mccaffrey2004propensity,wager2018estimation.

As mentioned in (ref), the above definition is quite general and captures several existing propensity score-based estimators (see (ref)). The motivation of CIPW estimators comes from the use of decision trees and random forests for learning propensity scores mccaffrey2004propensity,wager2018estimation: these methods also partition the covariate domain and learn a “common” propensity score for all covariates in the domain. We present expressions for the bias, variance, and RMSE of CIPW estimators in (ref). We show that $\tau_{\mathdutchcal{S}, N}$ is asymptotically normal whenever $\min_{S\in \mathdutchcal{S}} e(S)(1-e(S))$ is bounded away from 0 (as for good-local partitions) in (ref).

\noindentFractional CIPW Estimators. If we restrict to the CIPW estimators defined above, then RMSE guarantee in (ref) deteriorates to $\varepsilon+\alpha L+{1/\sqrt{n\beta}}$. To achieve the improved guarantee of $\varepsilon+\rho\cdot \alpha L+{1/\sqrt{n\beta}}$, we need to consider fractional CIPW estimators: each fractional CIPW estimator is defined by a fractional partition $(\mathdutchcal{S}, N, w)$, where, for each $T\in \mathdutchcal{S}\cup \left\{N\right\}$ and covariate $x$, there is a weight $w_T(x)\in [0,1]$. The weights satisfy the natural condition that they sum to 1 for any covariate $x$, i.e., $\sum_T w_T(x)=1$.

Before defining $\tau_{\mathdutchcal{S}, N, w}$, we explain the connection between a fractional partition $(\mathdutchcal{S}, N, w)$ and a usual partition; they have many similarities. Concretely, $(\mathdutchcal{S}, N, w)$ is a (usual) partition of an extension $\mathdutchcal{X}_{\mathdutchcal{S}, N, w}$ of the original covariate-domain $\mathdutchcal{X}=\mathbb{R}^d$: in the extended covariate-domain, each covariate $x\in \mathdutchcal{X}$ (with mass $\mathcal{D}(x))$, is split into multiple covariates $\left\{x_T\colon T\in \mathdutchcal{S}\cup\left\{N\right\}\right\}ht\}}$ which have probability masses $\left\{\mathcal{D}(x)\cdot w_T(x)\colon T\in \mathdutchcal{S}\cup \left\{N\right\}\right\}ht\}}$ respectively. For any $(\mathdutchcal{S}, N, w)$, $\tau_{\mathdutchcal{S}, N, w}$ is defined as the CIPW estimator on the new domain $\mathdutchcal{X}_{\mathdutchcal{S}, N, w}\times [-1,1] \times \ensuremath{\left\{0, 1\right\}}$. One issue is that the dataset $\mathscr{C}$ we receive lies in the original domain and we would like to have samples in the extended domain, where the fractional CIPW operates. To address this issue we proceed as follows: for each $(x_i,y_i,t_i)\in \mathscr{C}$, we replace it with $((x_i)_T, y_i, t_i)$ with probability $\propto w_T(x_i)$ for each $T\in \mathdutchcal{S}\cup\left\{N\right\}$. Note that such a re-sampling process is necessary, since if one naïvely added weights to (ref), then the terms will no longer be independent.

To summarize, fractional CIPW estimators are defined on a fractional partition $(\mathdutchcal{S}, N, w)$, they are CIPW estimators on an extension of the domain, and given $\mathscr{C}$, we can generate samples from the extended domain and, hence, compute $\tau_{\mathdutchcal{S}, N, w}$. Further, we can compute the RMSE of fractional CIPW estimators by using the expression of RMSE of a CIPW estimator on the extended domain. Finally, a fractional partition is said to be \ensuremath{(\alpha,\beta,\gamma)}-good-local partition if the corresponding CIPW estimator on the extended domain is \ensuremath{(\alpha,\beta,\gamma)}-good-local partition.

\noindentComputing Coarse Propensity Scores. The expression of $\tau_{\mathdutchcal{S}, N}$ involves coarse propensity scores $\left\{e(S)\colon S\in \mathdutchcal{S}\right\}$ ((ref)). These coarse propensity scores can be estimated from data, akin to the usual propensity scores. For instance, under standard assumptions on (i) propensity scores (e.g., finite fat shattering dimension alon1997scale; as implied by common smoothness assumptions hirano2003efficient) and (ii) sets in $\mathdutchcal{S}$ (e.g., finite VC dimension blumer1989learnability and lower bounds on probability mass), coarse propensity scores can be estimated from data: for instance, given $\widehat{e}\colon \mathbb{R}^d\to (0,1)$ and $\mathscr{C}$ of size $n=\Omega\left(\varepsilon^{-2}\right)$, for any $S\in \mathdutchcal{S}$, the empirical average ${\left(\sum_{i}\widehat{e}(x_i) \mathds{I}[x_i\in S]\right)/\left(\sum_{i}\mathds{I}[x_i\in S]\right)}$ is additively $\varepsilon$ close to $e(S)$ with high probability. For simplicity of exposition, we henceforth assume access to an oracle that given a set $S$ (from a class of finite VC dimension), outputs a value $v\in e(S)\pm \varepsilon$.

Algorithmic Result and Overview of Our Algorithm

In this section, we present our main algorithmic result: an efficient algorithm that, given $\varepsilon$-accurate propensity scores, outputs a prediction of $\tau$ that has a small $\varepsilon$-Robust RMSE.

In particular, the estimator's RMSE only increases by a small additive amount due to inaccuracies in propensity scores and outliers. As shown by (ref), this is significantly better than existing estimators which, under the same assumptions, can have $\Omega(1)$ RMSE. Moreover, the RMSE is close to the information-theoretic lower bound of $\Omega\left(\rho\min\left\{1, \alpha L\right\}\right)$. The algorithm does not use $L$ or $k$. If it is given $L$ as input, then we can bring the RMSE closer to the lower bound by using (ref) if $\alpha L<1$ and otherwise using $\beta$-Trimmed IPW Estimator. Finally, the estimator in (ref) is {asymptotically normal} and, hence, enables one to generate confidence intervals on $\tau$.

The pseudocode of the algorithm is in (ref) and the proof of (ref) appears in (ref).

Technical Overview of (ref)

(ref) splits $\mathscr{C}$ into two equal parts $\mathscr{C}_1$ and $\mathscr{C}_2$; $\mathscr{C}_1$ is used to learn a (fractional) good-local partition $(\mathdutchcal{S}, N, w)$ and $\mathscr{C}_2$ is used to evaluate $\tau_{\mathdutchcal{S}, N, w}$. Our algorithm contains multiple components that handle different challenges. For this reason, we divide the description of the algorithm into three stages, where each stage handles a more general setting. (ref) presents the final algorithm.

\noindentStage 1 - Accurate Propensity Scores ($\varepsilon=0$). In this case, the algorithm then constructs an \ensuremath{(2\alpha, \Omega(\beta), 0)}-good-local partition of covariates in $\mathscr{C}_1$ in $O(n^3)$ time. To do this, the algorithm covers all $\beta$-outliers in $\mathscr{C}_1$ by balls of diameter $2\alpha$; the outliers are identifiable as $\varepsilon=0$. To do this efficiently, the algorithm utilizes that the $k$-balls in the cover of $\beta$-outliers are far (due to (ref)).

Let this partition be $(\mathdutchcal{S}, N)$. We want $(\mathdutchcal{S}, N)$ to also generalize to $\mathscr{C}_2$. Toward this, one can use standard uniform convergence bounds to show that all sets in $\mathdutchcal{S}\cup\left\{N\right\}$ satisfy the conditions required by a good-local partition (this is where we use $\abs{\mathdutchcal{S}}=k=O(1)$). The difficulty is that there can be many covariates in $\mathscr{C}_2$ that are not in $\mathscr{C}_1$ and, hence, may not be covered by $(\mathdutchcal{S}, N)$. In fact, there may be a large mass of them since we consider a continuous domain and, hence, have a 0 probability of sampling the same covariate twice. We show that (ref) implies that the set of $\beta$-outliers not covered by $(\mathdutchcal{S}, N)$ (whether in $\mathscr{C}_2$ or not) have a mass of at most $O\left({1/n}\right)$ ((ref)). This enables us to extend $(\mathdutchcal{S}, N)$ to a \ensuremath{(2\alpha, \Omega(\beta), O(1/n))}-good-local partition of the whole domain $(\mathdutchcal{S}', N')$ (where we add all uncovered outliers to $N'$).

\noindentStage 2 ($0\leq \varepsilon\leq {\beta/10}$): Stage 1 used propensity scores to (i) identify $\beta$-outliers and (ii) evaluate $\tau_{\mathdutchcal{S}', N'}(\mathscr{C}_2; e)$. Implementing (ii) with inaccurate propensity scores is not an issue as the $\varepsilon$-Robust MSE of good-local partitions is well-behaved ((ref)). To implement (i), we show the following ((ref)): for any $\varepsilon\leq {\beta/10}$, \[ \forall\ {\widehat{e}\in B(e, \varepsilon)}\,,\quad \frac{\beta}{9}\text{-outliers} ~~\subseteq~~ \left\{x\in \mathbb{R}^d\colon \widehat{e}(x)(1-\widehat{e}(x))\leq \frac{\beta}{3}\right\} ~~\subseteq~~ \beta\text{-outliers}\,. \] Hence, given any $\varepsilon$-inaccurate propensity score $\widehat{e}$, one can approximately identify the outliers, which we show is sufficient to ensure guarantees of Stage 1 up to constant factors ((ref)).

\footnotetext{We shortly mention that the number of $\ell_\infty$-balls $k$ used in our cover is not given to the algorithm, but our $\mathsf{UpdateWeight}$ routine uses it. However, there is an easy adaptation of this algorithm that finds $k$ which can be run as a pre-processing step: we run $\mathsf{FindGoodPartition}$ by omitting the calls to $\mathsf{UpdateWeight}$ and then $k$ will correspond to the number of iterations of the (first) outer for loop. Then we execute our algorithm with $k$ as input.}

\noindentStage 3 (Improving Guarantee on Bias from $\alpha L$ to $\rho\alpha L$): Since $\mathcal{D}(N')=O(1/n)$ and the diameter of all sets in $\mathdutchcal{S}'$ is $2\alpha$, an upper bound on the bias is as follows (see (ref)) \[ \operatorname{Bias}_\mathcal{D}(\tau_{\mathdutchcal{S}', N'}) \leq O\left(\frac{1}{n}\right) +O(\alpha L)\cdot \sum_{S\in \mathdutchcal{S}'\colon \operatorname{diam}(S)>0}\mathcal{D}(S) \,. \] To get an upper bound of $O(\rho \alpha L+({1/{n}}))$, we need to ensure that the total mass of sets $S$ for which $\operatorname{diam}{(S)}>0$ is at most $\rho$. However, even under (ref), there may be no partition satisfying this guarantee. To see this suppose there is a single $\beta$-outlier, $x_{\rm out}$, with mass $\mathcal{D}(x_{\rm out})=\rho$. Let $x_{\rm in}$ be a non-outlier close to $x_{\rm out}$ with mass $\mathcal{D}(x_{\rm in})\gg \rho$. Since $x_{\rm in}$ is a point-mass, any $S$ covering $x_{\rm out}$ either covers $x_{\rm in}$ or does not cover $x_{\rm in}$. In the former case, then $\mathcal{D}(S)=\mathcal{D}(x_{\rm in})+\mathcal{D}(x_{\rm out})\gg \rho,$ and, hence, we do not satisfy $\mathcal{D}(S)\leq \rho$. In the latter case, $e(S)(1-e(S))\leq \beta$ and, hence it cannot be a part of a good-local partition. We side-step the issue by considering weighted partitions. Intuitively, in this case, one can construct two sets $S,S'$ and set $w_S(x_{\rm out})=1$ and $w_S(x_{\rm in})={\rho/\mathcal{D}(x_{\rm in})}$. This corresponds to the $\mathsf{UpdateWeight}$ routine in (ref).

Additional Remarks

{Next, we present some additional remarks on (ref).

Our algorithm for estimating $\tau$ requires the knowledge of parameters in (ref). Some of these parameters (those in (ref)) can be estimated from data: given $\varepsilon$ accurate propensity scores $\widehat{e}$, one can check if (ref) hold for all $x$ with $\widehat{e}(x)(1-\widehat{e}(x)) < 2\beta+\varepsilon$. This is sufficient as (ref) implies that any $\beta$-outlier must satisfy $\widehat{e}(x)(1-\widehat{e}(x)) < 2\beta+\varepsilon$. Estimating the Lipschitzness constant (i.e., testing (ref)) requires access to $\mu_t(x)$ which may be unavailable in practice. However, if $\mu_t(x)$ is a parametric function of $x$ (a common assumption in practice imbens2015causal,hernan2023causal), then (ref) holds under mild assumptions on the underlying parameter; see discussion after (ref).

(ref) is required to ensure that CIPW estimators defined by good-local partitions have a small robust RMSE. (ref) is a necessary condition to ensure the existence of a good-local partition. Given (ref) holds, (ref) ensures (i) the existence of a fractional good-local partition with (possibly) overlapping partitions and (ii) an efficient algorithm to find it. While (ref) is not necessary to ensure the existence of a (fractional) good-local partition, to be able to identify the good-local partition from finite samples, some assumption in addition to (ref) is necessary (see (ref)). That said, alternatives to (ref) may also be able to ensure (i) and (ii). For instance, if the outliers lie in known affine subspaces and non-outliers have a “sufficient” mass close to these subspaces, then any covering of these subspaces by $\ell_p$-balls of diameter $\alpha$ is a good-local partition, and the corresponding CIPW estimator satisfies (ref)'s guarantee.}

Expressions of Bias and Variance of CIPW Estimators

In this section, compute the expressions of the bias and variance of CIPW estimators. These, in turn, imply expressions for the RMSE and MSE of CIPW estimators.

Let us comment on the above expressions. The propensity scores $e(x)$ and $e(S)$ are observed quantities. While $\mu_0(x),\mu_1(x),v_0(x),$ and $v_1(x)$ are not observed due to censoring, under unconfoundedness, given a sufficiently large dataset, they can be computed to arbitrary accuracy ( e.g., by using that $\mu_1(x)=\operatorname{\mathbb{E}}\left[Y(1)\right]=\operatorname{\mathbb{E}}[Y(1)\mid T=1]$). Hence, under unconfoundedness, (ref) gives us expressions for bias, variance, and MSE in terms of quantities that can be estimated from a censored dataset. Furthermore, using the Central Limit Theorem, whenever $e(S)(1-e(S))$ is bounded away from 0, one can also obtain confidence intervals for the bias and variance and, hence, RMSE. (This analysis is analogous to that in (ref) which establishes asymptotic normality of $\tau_{\mathdutchcal{S}, N}$ when the coarse propensity scores $e(S)$ for each $S\in \mathdutchcal{S}$ are bounded away from $0$.)

In the remainder of this section, we prove (ref).

Formal Statements and Proofs of Hardness Results

Computational Hardness of Finding Minimum-RMSE CIPW Estimator

{In this section, we consider the computational complexity of solving $\operatornamewithlimits{arg\,min}_{\mathdutchcal{S}, N}\; \operatorname{RMSE}_{\mathcal{D}}{(\tau_{\mathdutchcal{S}, N})}$.} Concretely, we consider the following decision version of it which considers distributions $\mathcal{D}$ supported over $m$ covariates $x_1,x_2,\dots,x_m.$

{Since it is more convenient to work with the MSE instead of the RMSE, above we phrase the condition on the square of the RMSE.} Under unconfoundedness all of the inputs to Min-RMSE are identifiable and, hence, can be estimated to arbitrary precision given sufficiently many samples. Since we are interested in the computational complexity, we assume all inputs are known exactly for now. Our main hardness result is as follows.

\hardnessApproximation*

The proof of (ref) appears in (ref). We continue with a technical overview below.

Technical Overview

{The hardness result follows from a reduction of Subset-Sum to the special case of Min-RMSE where $\mu_0(x)=v_0(x)=0$ and $v_1(x)+\mu_1(x)^2=C>0$ for all $x$ and some large constant $C$.

Consider an instance $a_1,a_2,\dots,a_m$ and $V$ of Subset-Sum. The first idea in the hardness result is to select $n$ and $U$ such that such that any solution $(\mathdutchcal{S}, N)$ of $\textbf{\textsf{Min-RMSE}}{}$ must ensure that $\tau_{\mathdutchcal{S}, N}$ is unbiased and $N=\emptyset$. To see why this is relevant, consider the following equality, which follows from the expression of CIPW estimators bias (see (ref)) \[ \mathbb{E}_{\mathscr{C}}[\tau_{\mathdutchcal{S}, N}(\mathscr{C};e)] = \sum_x \frac{\mathcal{D}_X(x)}{1-\mathcal{D}(N)} \left( \frac{e(x)\mu_1(x)}{e(S_x)} - \frac{\left(1-e(x)\right)\mu_0(x)}{1-e(S_x)} \right ) \,, \] where $S_x$ is the unique $S\in \mathdutchcal{S}$ containing $x$. This implies that $\tau_{\mathdutchcal{S}, N}$ is unbiased if and only if \[ \tau\cdot (1-\mathcal{D}(N))=\sum_{x\not\in N} \mathcal{D}_X(x) \tau_{\mathdutchcal{S}, N}(x; (e,\mu))\,, \] where $\tau_{\mathdutchcal{S}, N}(x; (e,\mu) ) = \frac{e(x)\mu_1(x)}{e(S_x)} - \frac{\left(1-e(x)\right)\mu_0(x)}{1-e(S_x)}.$ If we can ensure $N=\emptyset$, then this simplifies to \[ \tau=\sum_{x} \mathcal{D}_X(x)\cdot \tau_{\mathdutchcal{S}, N}(x; (e,\mu))\,. \] Hence, selecting $\tau\propto V$ and $\mathcal{D}_X(x_i)\tau_{\mathdutchcal{S}, N}(x_i; (e,\mu)) \propto a_i$ for all $1\leq i\leq m$, implies that $\tau_{\mathdutchcal{S}, N}$ is unbiased if and only if $\sum_{x\in [m]\backslash N} a_i=V.$

The difficulty is that $\tau$ is dependent on the values of $\mathcal{D}_X(x)$ and $\tau_{\mathdutchcal{S}, N}(x; (e,\mu))$ and, hence, cannot take an arbitrary value. To avoid this, one idea is to introduce a dummy element $x_{m+1}$ which must be included in $N$ (the $\texttt{null}$ set) in any solution of Min-RMSE: this is useful as (1) we can set $\tau$ to be an arbitrary value by selecting an appropriate $\mathcal{D}_X(x_{m+1})\tau_{\mathdutchcal{S}, N}(x_{m+1}; (\varepsilon, \mu))$ and (2) since $x_{m+1}\in N$, it is irrelevant for the sum $\sum_{x\not\in N} \mathcal{D}_X(x) \tau_{\mathdutchcal{S}, N}(x; (\varepsilon, \mu))$ which shows up in the bias. To be more precise, since $N\neq\emptyset$, we need to account for the factor $(1-\mathcal{D}(N))$. We can side-step this by ensuring $1-\mathcal{D}(N)\approx 1 - \mathcal{D}_X(x_{m+1})\approx 1$.

One idea to ensure that in any feasible solution satisfies $x_{m+1}\in N$ is to set a very propensity score for $x_{m+1}$, say, $e(x_{m+1})=\varepsilon\ll 1$. This ensures that if $x_{m+1}\not\in N$ and if $x_{m+1}$ is also not merged with any other point, then the variance is at least $\Omega\left({1/\varepsilon}\right)$. However, it allows for $x_{m+1}\not\in N$, if $x_{m+1}$ is merged with other points. We ensure that merging $x_{m+1}$ with other points is not desirable by adding another dummy element $x_{m+2}$. We construct $x_{m+2}$ so that:

Finally, to prove the hardness of approximation, we extend the above reduction. Given any instance $\ensuremath{\mathcal{I}_{\rm SS}}{}$ of Subset-Sum with bit-complexity $b$ and a number $\eta>0$, we construct an instance \ensuremath{\mathcal{I}_{\rm MSE}} of Min-RMSE such that:

}

Proof of (ref)

In this section, we prove (ref).

Reduction

To prove (ref), we construct a gap-inducing reduction from Subset-Sum to the special case of Min-RMSE where \[ \mu_0(x)=v_0(x)=0 \quad \text{for all } x\,. \] In this special case of Min-RMSE, the expression of the MSE (see (ref)) simplifies to:

Where $e(S)$ is the average propensity score on $S$ and $\mathcal{D}(S)$ is the total probability mass on $S$: \[ e(S)\coloneqq \frac{\sum_{x\in S} e(x)\mathcal{D}(x)}{\mathcal{D}(S)} \quad\text{and}\quad \mathcal{D}(S)\coloneqq \sum_{x\in S} \mathcal{D}(x)\,. \] Thus, $\min_{\mathdutchcal{S}, N}\operatorname{MSE}_\mathcal{D}(\tau_{\mathdutchcal{S}, N})$ is equivalent to the following program \[ $\min_{1\leq k\leq m}\quad \min_{ \substack{ N\subseteq [m],\\ \mathdutchcal{S} = \left\{S_1,\dots,S_k\right\} \text{ partitions}\\ \text{$[m]\backslash N$ into $k$ non-empty sets } }\quad \left(

\right) .$} \]

\noindentReduction. Recall that Subset-Sum is defined as follows and is known to be $\mathsf{NP}$-hard gareyjohnson1990.

Given an instance $\mathcal{I}_{SS}(a,T)$ of Subset-Sum, define constants \[ A \coloneqq \sum_i a_i\,,\quad {\varepsilon \ll \frac{1}{(Am)^4}\,,} \quad \alpha = \varepsilon^3\,,\quad \beta = \varepsilon^5\,,\quad\text{and}\quad \Delta = \frac{1}{1+\varepsilon+k\varepsilon^3}\,. \] We construct an instance $\mathcal{I}_{\rm MSE}(m,n,e,\mu,v,\mathcal{D},U)$ of Min-RMSE with \[ m = k+2\,,\quad n = \varepsilon^{-7}\,,\quad\text{and}\quad U = {8A^2\varepsilon^7}\,. \] The first $k$ out of $k+2$ points are defined as follows: for each $1\leq i\leq k$ \[ \mathcal{D}(x_i) = \Delta\alpha\,,\quad e(x_i) = 1\,,\quad \mu_1(x_i) = a_i\,, \quad\text{and}\quad v_1(x_i) = 4A^2 - \mu_{1}(x_i)^2\,. \addtocounter{equation}{1}\tag{\theequation}\label{eq:reduction:construction:firstkPt} \] The last two points are defined as follows:

Recall that for all points $x$, we set $\mu_0(x)=v_0(x)=0$. This completes the construction of \ensuremath{\mathcal{I}_{\rm MSE}}. Clearly, \ensuremath{\mathcal{I}_{\rm MSE}} can be constructed in time polynomial in the bit complexity of \ensuremath{\mathcal{I}_{\rm SS}}. For \ensuremath{\mathcal{I}_{\rm MSE}} to be a valid instance of Min-RMSE, we need to ensure that $\mu_1,v_1\in\left[-1,1\right]$, which can be done by dividing $\mu_1$ by $A$ and $v_1$ and $U$ by $A^2$. (Intuitively, this does not change the proof because $\operatorname{MSE}{(\tau_{\mathdutchcal{S}, N})}/U$ is invariant to scaling of the outcomes and $\sqrt{U}$.)

Soundness

Next, we prove that the reduction is sound.

To see how this implies soundness, observe that due to the first part of the above lemma, if \ensuremath{\mathcal{I}_{\rm MSE}} is a Yes instance with certificate $\left(\mathdutchcal{S}, N\right)$, then a special element $x_m$ satisfies: $x_m\in N$ or $x_m\in S_i$ with $\abs{S_i}\geq 2$. The second and third parts imply that if $x_m$ satisfies either of these conditions, then soundness holds. Therefore \[ \ensuremath{\mathcal{I}_{\rm MSE}}{} \text{ is a \texttt{Yes} instance} \quad\implies\quad \ensuremath{\mathcal{I}_{\rm SS}}{} \text{ is a \texttt{Yes} instance}\,. \]

Completeness

Finally, we prove completeness.

Statistical Hardness of Learning Good-Local Partitions

In this section, we prove (ref). The formal version of (ref) is as follows.

As mentioned in (ref), the proof (ref) utilizes the fact that $\mathdutchcal{S}$ can contain a large number of subsets. Using this, it reduces the problem of PAC-learning a union of $\abs{\mathdutchcal{S}}$ intervals (of width at most $\alpha$) up to $\gamma$-error in the agnostic setting to finding an \ensuremath{(\alpha,\beta,\gamma)}-good-local partition. The result follows that this class has a VC-dimension of at least $\abs{\mathdutchcal{S}}$ and, hence, if $\abs{\mathdutchcal{S}}\to\infty$, then it cannot be learned with any finite number of samples.

Technical Overview

In this section, we overview the proof of (ref). The complete proof appears in (ref).

Define $k \coloneqq \abs{\mathdutchcal{S}}$; this is a parameter in our proof and we select $k>n$. It will suffice to consider one-dimensional covariates, i.e., $d=1$. Let $\mathdutchcal{H}$ be the set of all intervals of width at most $\alpha$. Let $\mathdutchcal{G}$ to be the union of $k$ sets from $\mathdutchcal{H}$, i.e., $\mathdutchcal{G} \coloneqq \left\{H_1\cup H_2\cup \dots\cup H_k\colon H_1,H_2,\dots,H_k\in \mathdutchcal{H}\right\}$ It is straightforward to see that $\mathdutchcal{G}$ can shatter of set of $k$ points $X=\left\{x_1,x_2,\dots,x_k\right\}\subseteq \mathbb{R}$ such that any pair of points in $X$ is at least $4\alpha$ apart. Hence, in particular, using well-known lower bounds, it follows that $\mathdutchcal{G}$ cannot be PAC-learned with $k$ samples.\footnote{Recall that a set of $p$ points $X=\left\{x_1,x_2,\dots,x_p\right\}\subseteq \mathbb{R}$ are shattered by a hypothesis class $\mathdutchcal{G}\subseteq \ensuremath{\left\{0, 1\right\}}^\mathbb{R}$ if for every vector $b\in \ensuremath{\left\{0, 1\right\}}^{p}$, there is a set $G\in \mathdutchcal{G}$ such that $x_i\in G$ if and only if $b_i=1$.}

\noindentPAC-Learning Instance. Fix any $X$ of size $k$ shattered by $\mathdutchcal{G}$ such that points in $X$ are pairwise $4\alpha$ apart. Consider any distribution $\mathcal{P}$ on $X\times \ensuremath{\left\{0, 1\right\}}$. Let ${\rm neg}(X)=\left\{x\in X\colon \operatorname{\operatorname*{Pr}\nolimits}_{(x,y)\sim \mathcal{P}}[y=1] <{1/2}\right\}$ and ${\rm pos}(X)=X\backslash {\rm neg}(X)$. Observe that any $G\in \mathdutchcal{G}$ with error $\varepsilon+{\rm OPT}{}$ on $\mathcal{P}$ must label all but $\varepsilon$-fraction of points in ${\rm neg}(X)$ negatively and all but $\varepsilon$-fraction of points in ${\rm pos}(X)$ positively.

\noindentReduction. Given $X$ and $\mathcal{P}$, we construct an unconfounded distribution $\mathcal{D}=\mathcal{D}_{\alpha,\beta,\gamma,\varepsilon}$ such that any \ensuremath{(\alpha,\beta,\gamma)}-good-local partition w.r.t. to $\mathcal{D}$ can be used to find a hypothesis with $\varepsilon+{\rm OPT}{}$ error on $\mathcal{P}$ as follows: given $(\mathdutchcal{S}, N)$, let $\mathdutchcal{S}_{>1}\subseteq \mathdutchcal{S}$ be the subset of $\mathdutchcal{S}$ where each set $S\in \mathdutchcal{S}_{>1}$ has more than one point, and let $G_\mathdutchcal{S}$ be the hypothesis that labels all points from $X$ in $\mathdutchcal{S}_{>1}$ negatively and all remaining points positively.

\noindentConstruction. At a high level, start with covariates $X$ and add $\abs{{\rm neg}(X)}$ additional covariates $Z$: for each $x_i\in {\rm neg}(X)$, we add a covariate $z_i$ very close to it. We select propensity scores so that each $x\in X$ has $e(x)={1/2}$ and each $z\in Z$ is a $\eta$-outlier for $\eta\ll \beta$. The remainder of the reduction is independent of the distribution of the outliers and, hence, we can choose it to satisfy unconfoundedness and (ref). Further, observe that the above construction already satisfies (ref) with constants $\alpha,\beta$.

\noindentOverview of Soundness and Completeness. For simplicity suppose $\gamma=0$. Now we show that any \ensuremath{(\alpha,\beta,0)}-good-local partition $(\mathdutchcal{S}, N)$ must cluster each $z_i\in Z$ with the only point within $\alpha$-distance of it, namely, $x_i\in {\rm neg}(X)$. If not, then $e(S) \leq \eta$ for the partition $S$ containing $z_i$. ($z_i$ cannot be clustered with another point as all other points at further than $\alpha$-away and $\operatorname{diam}{(S)}\leq\alpha$.) Hence, we can identify all samples in ${\rm neg}(X)$ given $(\mathdutchcal{S}, N)$. When $\gamma>0$, then we can identify all but $O(\gamma)$ fraction of points in ${\rm neg}(X)$, which we show is sufficient to achieve $(\gamma\varepsilon)$-accurate.

Proof of (ref)

Properties of CIPW Estimators Based on Good-Local Partitions

Asymptotic Normality of CIPW Estimators Based on Good-Local Partitions

In this section, we show that CIPW estimators arising from good-local partitions are asymptotically normal.

Thus, CIPW estimators arising from good-local partitions imply confidence intervals on $\tau$.

Robust RMSE of CIPW Estimators Based on Good-Local Partitions

In this section, we upper bound the robust RMSE of any CIPW estimator based on a good-local partition. Concretely, we prove the following result.

\RobustMSEofLGpartition*

Fix any pair of true and inaccurate propensity scores $e,\widehat{e}\colon \mathbb{R}^d\to (0,1)$ where $\widehat{e}\in B(e,\varepsilon)$. Recall \[ \operatorname{RMSE}{\left(\tau_{\mathdutchcal{S}, N}(\widehat{e})\right)} = \sqrt{\operatorname{\mathbb{E}}_\mathscr{C}\left[\left(\tau_{\mathdutchcal{S}, N}(\mathscr{C}; \widehat{e}) - \tau\right)^2\right]}\,. \] We will prove the following upper bound on $\operatorname{RMSE}{\left(\tau_{\mathdutchcal{S}, N}(\widehat{e})\right)}$: if $\mathcal{D}(N)\leq \frac{1}{2}$, it holds that \[ \operatorname{RMSE}{(\tau_{\mathdutchcal{S}, N}(\widehat{e}))}^2 \leq \left( 4L\sum_{S\in \mathdutchcal{S}}\mathcal{D}(S)\operatorname{diam}(S) + 8\mathcal{D}(N) \right)^2 +\frac{1}{n} \sum_{S\in \mathdutchcal{S}} \frac{\mathcal{D}(S)}{\widehat{e}(S)(1-\widehat{e}(S))} \cdot \frac{1}{1 - \mathcal{D}(N)}\,. \addtocounter{equation}{1}\tag{\theequation}\label{eq:robustMSE_upperbound:term1} \] (ref) follows from the definition of an \ensuremath{(\alpha,\beta,\gamma)}-good-local partition.

{For the remainder of the proof, it would be more convenient to work with the MSE and then use $\operatorname{RMSE}{(\tau_{\mathdutchcal{S}, N}(\widehat{e}))}=\sqrt{\operatorname{MSE}{(\tau_{\mathdutchcal{S}, N}(\widehat{e}))}}$.} Substituting inaccurate propensity scores $\widehat{e}$ and repeating the proof of (ref) implies that

Where $\zeta(x)\coloneqq \frac{e(x)\mu_1(x)}{\widehat{e}(X; \mathdutchcal{S}, N)} - \frac{(1-e(x))\mu_0(x)}{1-\widehat{e}(X; \mathdutchcal{S}, N)}$. To simplify this, we use the fact that since $(\mathdutchcal{S}, N)$ is an \ensuremath{(\alpha,\beta,\gamma)}-good-local partition, for all $S\in \mathdutchcal{S}$, $e(S), \widehat{e}(S)\geq \beta-\varepsilon$ and, hence, for all $S\in \mathdutchcal{S}$ \[ \frac{1}{\widehat{e}(S)} \in \frac{1}{1\pm \nicefrac{\varepsilon}{\beta}}\cdot \frac{1}{{e}(S)}\,. \] Substituting this in the above expression of the MSE implies that $\operatorname{MSE}{(\tau_{\mathdutchcal{S}, N}(\widehat{e}))}\cdot \left(1\pm \nicefrac{\varepsilon}{\beta}\right)$ is upper bounded by the following

Where $\psi(x)\coloneqq \frac{e(x)\mu_1(x)}{e(X; \mathdutchcal{S}, N)} - \frac{(1-e(x))\mu_0(x)}{1-e(X; \mathdutchcal{S}, N)}$.

We upper bound $\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1pt] (char) {3};}$ by 0. We prove upper bounds on \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1pt] (char) {1};} and \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1pt] (char) {2};} below. Before proceeding to the result, let $\mathdutchcal{S}=\left\{S_1,S_2,\dots\right\}$ and for each $S_j\in \mathdutchcal{S}$ define its bias $b(j)$ as follows \[ b(j) \coloneqq \max_{r\in \ensuremath{\left\{0, 1\right\}}}\max_{x_1,x_2\in S_j} \abs{\mu_r(x_1)-\mu_r(x_2)}. \addtocounter{equation}{1}\tag{\theequation}\label{def:clusterBias} \]

\noindentUpper bound on $(1)$. Our proof is divided into the following two steps:

Let $\overline{\mathcal{D}}(x)\coloneqq \operatorname{\operatorname*{Pr}\nolimits}[X=x\mid X\not\in N]$. Toward the first step, observe that

Therefore, using that $-1\leq Y^0,Y^1\leq 1$ \[ \abs{ \operatorname{\mathbb{E}}\left[Y^1-Y^0\mid X\not\in N\right] - \operatorname{\mathbb{E}}_X\left[\psi(X)\mid X\not\in N\right] } \leq 4\mathcal{D}(N)+4\sum_{S\in \mathdutchcal{S}} { b(i) }\mathcal{D}(S)\,. \addtocounter{equation}{1}\tag{\theequation}\label{eq:clustering:step1_1} \] Next, toward the second step, observe that

Using that $\operatorname{\mathbb{E}}\left[Y^1-Y^0\mid X\not\in N\right]\leq 2$, it follows that

Therefore, (ref) imply that \[ \sqrt{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1pt] (char) {1};}} = \abs{ \operatorname{\mathbb{E}}_X\left[\psi(X)\mid X\not\in N\right] - \operatorname{\mathbb{E}}\left[Y^1-Y^0\right] } \leq 8\mathcal{D}(N)+4\sum_{S\in \mathdutchcal{S}} b(i)\mathcal{D}(S)\,. \]

\noindentUpper bound on $(2)$. Term \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1pt] (char) {2};} can be upper bounded as follows.

Proofs of Algorithmic Results

Proof of Main Algorithmic Result

In this section, we prove (ref), our main algorithmic result:

\mainTheorem*

{As mentioned in (ref), the algorithm divides the given dataset $\mathscr{C}$ into two parts: $\mathscr{C}_1$ and $\mathscr{C}_2$. Using the $\mathscr{C}_1$, it constructs a (fractional) {\ensuremath{(\alpha,\Omega(\beta),\varepsilon)}-good-local partition} $\left(\mathdutchcal{S}, N,w\right)$. Then, it outputs $\tau_{\mathdutchcal{S}, N, w}(\mathscr{C}_2; \widehat{e})$, i.e., the value of the CIPW estimator $\tau_{\mathdutchcal{S}, N, w}$ on the second half of the dataset. See (ref) for a discussion on fractional CIPW estimators, how to compute them, and the definition of a fractional good-local partition.}

Before proceeding to this, in the next subsection, we present a few properties of propensity scores that are used to prove correctness.

Properties of Propensity Scores

The first result shows that inaccurate propensity scores are sufficient to approximately identify outliers with respect to the true propensity scores. Given $\beta>0$ and $\widehat{e}\colon \mathbb{R}^d\to (0,1)$, let $\ensuremath{\mathscr{O}}{}(\beta; \widehat{e})$ be the set of all points $\beta$-outliers with respect to $\widehat{e}$, i.e., \[ \ensuremath{\mathscr{O}}{}(\beta; \widehat{e}) \coloneqq \left\{x\in \mathbb{R}^d \colon \widehat{e}(x)(1-\widehat{e}(x)) \leq \beta\right\}\,. \]

The next fact shows that the coarse propensity scores of a good-local partition are bounded away from 0 and 1.

Our final fact enables us to infer the propensity scores of outliers and identify outliers from (inaccurate) propensity scores. It is used in the proofs of all the facts in this subsection.

Next, we present the proofs of all facts in this subsection.

Proof of (ref)

We divide the proof the following five steps.

{To see how these results imply (ref), observe that the upper bounds in (ref) applied to fractional partitions imply that:

Where for each set $T$, $\mathcal{D}_w(T)$ is the weighted mass of $T$, i.e., $\mathcal{D}_w(T)=\sum_{x\in T} w_T(x)\cdot \mathcal{D}(x)$, and $\operatorname{diam}_w{(T)}$ is the diameter of the set of all covariates $x$ with a positive mass $w_T(x)>0$. Substituting $\mathcal{D}_w(N)\leq \varepsilon$, and, for each $S\in \mathdutchcal{S}$, $\operatorname{diam}_{w}(S)\leq 2\alpha$, $\widehat{e}(S)(1-\widehat{e}(S)) \geq e(S)(1-e(S))-O(\varepsilon)\geq \beta-\varepsilon\geq {\beta/2}$, implies that

Finally, by Step 4, $\sum_{S\in \mathdutchcal{S}: \operatorname{diam}_w(S)>0} \mathcal{D}_w(S)\leq 5\rho$ and, hence the result follows. }

\noindentStep 1 (Existence of good-local partition $(\mathdutchcal{S}^\star, N^\star)$) In this step, we prove the following lemma.

\noindentStep 2 (WHP $\mathdutchcal{S}$ covers most outliers in $\mathdutchcal{S}^\star$) In this step, we prove the following lemma.

\noindentStep 3 ($\mathdutchcal{S}$ is disjoint and, all $S\in \mathdutchcal{S}$, have small diameter and non-extreme propensity scores): In this step, we prove the following lemma.

\noindentStep 4 (Non-singleton sets in $\mathdutchcal{S}$ have mass at most $2\rho+k\varepsilon$): We prove the following lemma.

\noindentStep 5 (Asymptotic normality): In this step, we show that $\tau_{\mathdutchcal{S}, N, w}$ is asymptotically normal: it follows because $\tau_{\mathdutchcal{S}, N, w}$ is a CIPW estimator on the extended domain ((ref)) and, for any set $T$, $e(T)$ is the same in the original and extended domains, and, hence by (ref), $e(S)(1-e(S))\geq {\beta/9}$ in the extended domain. (ref) (which is applicable as $\varepsilon\leq \beta/10$) implies asymptotic normality.

Plug-In Rates for Doubly Robust Estimators

Recall that doubly robust estimators use two nuisance parameters, the propensity scores and estimates of the expected outcomes $\mu_0,\mu_1\colon\mathbb{R}^d\to [-1,1]$. Since they depend on estimates of $\mu_0,\mu_1\colon\mathbb{R}^d\to [-1,1]$, they do not fit the family of CIPW estimators ((ref)). However, for a partition $(\mathdutchcal{S}, N)$, one can consider the following generalization of a doubly robust estimator: given propensity scores $e\colon \mathbb{R}^d\to (0,1)$ and conditional means $\mu_0,\mu_1\colon \mathbb{R}^d\to [-1,1]$, define \[ \tau_{{\rm DR}, \mathdutchcal{S}, N}{(\mathscr{C}; \mu_0, \mu_1, e)} \coloneqq \frac{1}{\abs{\left\{i\in [n]\colon x_i\not\in N\right\}}} \sum_{\substack{S\in \mathdutchcal{S}\\i\colon x_i\in S}} \left( \frac{ \left(t_i-e(S)\right)\left(y-\mu_1(x_i)\right) }{e(S)} - \frac{ \left(e(S)-t_i\right)\left(y-\mu_0(x_i)\right) }{1-e(S)} \right) } \,. \] This is the doubly robust estimator defined on the domain $\mathdutchcal{S}$ (where, for each $S\in \mathdutchcal{S}$, all elements of $S$ are assumed to have the same covariate).

We show that when $(\mathdutchcal{S}, N)$ is a good-local partition then it has a small robust MSE.

Thus, combining this result with the efficient algorithm for finding a good-local partition in (ref), we get an efficient method for constructing a coarse doubly robust estimator with a small robust MSE. This estimator has a small robust MSE because of the same reason why CIPW estimators defined by a good-local partition have a small robust MSE: the MSE of a (standard) doubly robust estimator is $\propto \operatorname{\mathbb{E}}\left[\frac{1}{e(x)(1-e(x))}\right]$ while the MSE of the above coarse doubly robust estimator is $\propto \operatorname{\mathbb{E}}\left[\frac{1}{e(S)(1-e(S))}\right]$. The latter is small as $e(S)(1-e(S))\geq \beta$ for all $S\in \mathdutchcal{S}$ in a good-local partition. Moreover, the bias introduced is also small because of Lipschitzness and the fact that each $S\in \mathdutchcal{S}$ has a small diameter. The same approach can also be used to construct coarse variants of other estimators: given an estimator $E$ that depends on the propensity scores, evaluate $E$ on the coarse domain $\mathdutchcal{S}$ with the coarse propensity scores $\left\{e(S)\colon S\in \mathdutchcal{S}\right\}$. This should significantly improve the robust MSE of $E$ whenever $\operatorname{Var}{(E)}\propto \operatorname{\mathbb{E}}\left[\frac{1}{e(x)(1-e(x))}\right]$ or $\propto \max_x \frac{1}{e(x)(1-e(x))}$.

Proofs of Results Comparing CIPW to Baselines

Formal Statement and Proof of (ref)

In this section, we prove (ref). Its formal statement is as follows.

Formal Statement and Proof of (ref)

In this section, we show that small errors in propensity scores can increase the RMSE of IPW and doubly robust estimators (even those that are given accurate conditional means $\mu_0$ and $\mu_1$) by an arbitrary amount. Concretely, we prove the following result.

Thus, inaccuracies in propensity scores can arbitrarily increase the RMSE of IPW and, even, doubly robust estimators that are given accurate conditional means $\mu_0$ and $\mu_1$.

{As mentioned in (ref), we focus on the doubly-robust estimator in (ref). The above result demonstrates that this estimator is fragile to errors in propensity scores. Since most guarantees of other doubly robust estimators also crucially rely on the absence of $O(1)$-outliers, we expect other doubly robust estimators to be fragile to errors as well.}

Acknowledgements

We would like to thank the anonymous COLT reviewers for their comments and suggestions. AM thanks Colleen Chan, Chris Harshaw, and Shinpei Nakamura-Sakai for helpful discussions and references.

\printbibliography