Sharp Rates for Discrete Confounding

The observed data are $O_i=(X_i,A_i,Y_i)$, $i=1,\ldots,n$, with $O_1,\ldots,O_n\stackrel{\mathrm{iid}}{\sim}P$, where the covariate $X$ takes values in $\{1,\ldots,d\}$, the treatment $A$ and outcome $Y$ are binary. For each category $k\in\{1,\ldots,d\}$ write $p_k=P(X=k)$ for the category mass, $\pi_k=P(A=1\mid X=k)$ for the treatment probability, and, for each treatment arm $a\in\{0,1\}$, $\mu_{ak}=E_P[Y\mid A=a,X=k]$ for the conditional mean outcome.

For the overlap level $\epsilon$, every category $k$ with category mass $p_k>0$ satisfies $$\epsilon \le \pi_k \le 1-\epsilon .$$

The observed outcome satisfies $$Y=Y(A)$$ almost surely.

The potential outcomes satisfy $$(Y(0),Y(1))\perp A\mid X .$$

$$\mathsf R_{n,d,\epsilon} := \inf_{\widehat\tau} \sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}} E_P\!\left[(\widehat\tau-\tau(P))^2\right].$$ The infimum ranges over all measurable estimators $\widehat\tau$ based on $O_1,\ldots,O_n$.

Fix an overlap level $\epsilon$ with $0<\epsilon<1/2$. Then there are constants $a_\epsilon,\rho_\epsilon,C_\epsilon>0$ and an integer $N_\epsilon<\infty$ such that, writing $$r_{n,d}:=\frac1n+\frac{d^2}{n^2(\log n)^2},$$ the following statements hold.

• (Matched minimax envelope.) For every $n,d$, every single-observation law $P$, and every sample law $\mu_n$ in the experiment class $\mathcal E_{n,d,\epsilon}$ of Definition P-1, if $$d>0,\qquad n\ge N_\epsilon,\qquad d\le \rho_\epsilon n\log n,$$ then the minimax risk $\mathsf R_{n,d,\epsilon}$ of Definition P-6 and the truncated balanced ratio-polynomial hybrid estimator $\widehat\tau_n^{\mathrm{hyb}}$ of Definition P-5 satisfy $$a_\epsilon r_{n,d} \le \mathsf R_{n,d,\epsilon} \le \sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}} E_P\!\left[\left(\widehat\tau_n^{\mathrm{hyb}}-\tau(P)\right)^2\right] \le C_\epsilon r_{n,d}.$$
• (Parametric interior.) For every $K>0$ there is a constant $C_K>0$ such that, for every $n,d$, every single-observation law $P$, and every sample law $\mu_n$ in $\mathcal E_{n,d,\epsilon}$, if $$d>0,\qquad n\ge N_\epsilon,\qquad d\le K\sqrt n\log n,\qquad d\le \rho_\epsilon n\log n,$$ then $$\frac{a_\epsilon}{n} \le \mathsf R_{n,d,\epsilon} \le \frac{C_K}{n}.$$
• (Consistency threshold.) For every pair of integer sequences $n_j,d_j$ with $n_j\to\infty$, $d_j>0$ eventually, and $$d_j\le \rho_\epsilon n_j\log n_j$$ eventually, the minimax risk converges to zero exactly along the sequences satisfying the vanishing normalized dimension condition: $$\mathsf R_{n_j,d_j,\epsilon}\to 0 \quad\Longleftrightarrow\quad \frac{d_j}{n_j\log n_j}\to 0.$$

With $\widehat\tau_n^{\mathrm{hyb}}$ as in Definition P-5 and $\mathsf R_{n,d,\epsilon}$ as in Definition P-6, the following assertions hold.

• Computability. There is a universal integer $K>0$ such that, for every $n,d\in\mathbb N$, a real-arithmetic program based on the hybrid count input has operation count at most $$K\,d\,M(n)^4$$ and, for every sample $O_1,\ldots,O_n$, evaluates exactly to $\widehat\tau_n^{\mathrm{hyb}}$.
• Fixed-overlap hybrid calibration. For every overlap level $\epsilon$ with $0<\epsilon<1/2$, there are constants $C_\epsilon,\rho_\epsilon>0$ and an integer $N_\epsilon$ such that, for all $n,d\in\mathbb N$ with $n>0$, $d>0$, $n\ge N_\epsilon$, and $$d\le \rho_\epsilon n\log n,$$ the hybrid estimator satisfies $$\sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}} E_P\!\left[\left(\widehat\tau_n^{\mathrm{hyb}}-\tau(P)\right)^2\right] \le C_\epsilon\left\{\frac1n+\frac{d^2}{n^2(\log n)^2}\right\}.$$ For the deterministic estimator $$\widehat\tau_{C_\epsilon,\epsilon} = \begin{cases} \widehat\tau_n^{\mathrm{hyb}}, & \text{if } C_\epsilon\left\{\frac1n+\frac{d^2}{n^2(\log n)^2}\right\} \le \frac1n+4(1/2-\epsilon)^2,\\ \widehat\tau_{\mathrm{ctr}}, & \text{otherwise,} \end{cases}$$ one also has $$\mathsf R_{n,d,\epsilon} \le \sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}} E_P\!\left[\left(\widehat\tau_{C_\epsilon,\epsilon}-\tau(P)\right)^2\right] \le \max\{C_\epsilon,4\} \left[ \frac1n+ \min\left\{ \frac{d^2}{n^2(\log n)^2},(1/2-\epsilon)^2 \right\} \right].$$
• Centered randomization bound. For every overlap level $\epsilon$ with $0<\epsilon\le 1/2$ and every $n,d\in\mathbb N$ with $n>0$ and $d>0$, the centered estimator $$\widehat\tau_{\mathrm{ctr}} = \frac1n\sum_{i=1}^n 2(2A_i-1)\left(Y_i-\frac12\right)$$ satisfies $$\sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}} E_P\!\left[\left(\widehat\tau_{\mathrm{ctr}}-\tau(P)\right)^2\right] \le \frac1n+4(1/2-\epsilon)^2.$$
• Endpoint randomization bracket. For every $n,d\in\mathbb N$ with $n>0$ and $d>0$, $$\frac{1}{100n}\le \mathsf R_{n,d,1/2}\le \frac1n.$$