Minimax ATE Estimation with Many Discrete Cells

For a real-outcome finite-cell law $P$ indexed by $k=1,\ldots,d$ and an overlap parameter $\epsilon$ with $0<\epsilon<1/2$, assume consistency, conditional exchangeability of $(Y(0),Y(1))$ and $A$ given $X$ for measurable potential-outcome events, overlap $\epsilon\le \pi_k\le 1-\epsilon$ whenever $p_k>0$, and first-moment integrability of each arm-cell outcome law for every $a\in\{0,1\}$ and positive-mass cell. With $p_k$ the cell mass and $\mu_{ak}$ the arm-cell conditional outcome mean, define $$\tau(P) := \sum_{k=1}^{d}p_k(\mu_{1k}-\mu_{0k}).$$

For each cell $k$, let $$p_k:=P(X=k),$$ and, when $p_k>0$, let $$\pi_k:=P(A=1\mid X=k).$$ For every $k$ with $p_k>0$, $$\epsilon\le \pi_k\le 1-\epsilon .$$

For every cell $k$, let $$\tau_k:=\mu_{1k}-\mu_{0k}$$ and $$\delta_k:=\tau_k-\sum_j p_j\tau_j ,$$ both well defined on zero-mass cells as well. The cell-effect deviations satisfy $$\max_{k:p_k>0}|\delta_k|\le \sigma M .$$

$$\mathcal P_{d,\epsilon,M,\sigma} := \left\{ P: \begin{array}{l} X\in\{1,\ldots,d\},\ A\in\{0,1\},\ Y,Y(0),Y(1)\in\mathbb R,\\ 0<\epsilon<1/2,\quad M\ge 1,\quad 0\le \sigma\le 2,\\ P\text{ satisfies }\text{ass:consistency, ass:conditional-exchangeability, ass:overlap, ass:mean-normalization, ass:second-central-moment, ass:approximate-homogeneity} \end{array} \right\}.$$

Let $$\mathcal T_{n,M} := \bigl\{ T:\mathcal O^n\to[-M,M]\;:\;T\ \text{is measurable} \bigr\}.$$ The minimax mean-squared risk over $\mathcal P_{d,\epsilon,M,\sigma}$ is $$\mathsf R_{n,d,\epsilon,M,\sigma} := \inf_{T\in\mathcal T_{n,M}} \sup_{P\in\mathcal P_{d,\epsilon,M,\sigma}} E_{Q_P^{(n)}}\!\left[(T-\tau(P))^2\right].$$

Given candidate estimators $T_n^{\mathrm{poly}}$ and $T_n^{\mathrm{col}}$, each a total measurable map $\mathcal O^n\to[-M,M]$, define $\widehat\tau_n^{\star}$ by the following steps.

1. Define the rare-cell polynomial remainder $$u_{n,d}:=\frac{d^2}{n^2\log^2(en)}.$$
2. Define the collision remainder $$h_{n,d,\sigma}:=\sigma^2+\frac{d}{n^2}.$$
3. Output the measurable selector $$\widehat\tau_n^{\star}:= \begin{cases} T_n^{\mathrm{col}},&h_{n,d,\sigma}\le\min\{1,u_{n,d}\},\\ T_n^{\mathrm{poly}},&u_{n,d}<\min\{1,h_{n,d,\sigma}\},\\ 0,&\text{otherwise}. \end{cases}$$

For every overlap parameter $\epsilon$ with $0<\epsilon<1/2$, there exist a constant $C_{\epsilon}>0$ and a polynomial calibration handle $(N_{\epsilon},\rho_{\epsilon})$ such that:

• (Handle calibration.) $\rho_{\epsilon}>0$, and for every pair of integers $n,d\ge1$, $$N_{\epsilon}\le n,\qquad d\le \rho_{\epsilon} n\log(en) \quad\Longrightarrow\quad 2\le K_n ,$$ where $K_n$ is the polynomial degree used by the polynomial estimator.
• (Index range.) The guarantee applies to every pair of integers $n,d\ge1$, every $M\ge1$, and every $0\le\sigma\le2$.
• (Model class.) The law $P$ ranges over $\mathcal P_{d,\epsilon,M,\sigma}$ from Definition P-1.

For these indices, let $T_n^{\mathrm{poly}}$ be the admissible polynomial estimator calibrated by $(N_{\epsilon},\rho_{\epsilon})$, let $T_n^{\mathrm{col}}$ be the collision estimator, and let $\widehat\tau_n^{\star}$ be the known-radius selector in Definition P-7 applied with radius $\sigma$ to these two estimators, and write $$r_{n,d,\sigma} = \frac{1}{n} + \min\left\{ 1,\, \min\left[ \frac{d^2}{n^2\log^2(en)},\, \sigma^2+\frac{d}{n^2} \right] \right\}$$ for the selector benchmark. Then $\widehat\tau_n^{\star}$ is measurable, satisfies $\widehat\tau_n^{\star}(s)\in[-M,M]$ for every sample $s$, and $$\sup_{P\in\mathcal P_{d,\epsilon,M,\sigma}} E_{Q_P^{(n)}}\!\left[\left(\widehat\tau_n^{\star}-\tau(P)\right)^2\right] \le C_{\epsilon}M^2 r_{n,d,\sigma}.$$

For every $0<\epsilon<1/2$, there exist constants $c_{\epsilon}$ and $b_{\epsilon}^{\mathrm{rad}}$ such that $$0<c_{\epsilon}\le 1, \qquad 0<b_{\epsilon}^{\mathrm{rad}}.$$ For all integers $n,d\ge 1$, all $M\ge 1$, and all $0\le \sigma\le 2$, the minimax mean-squared risk $\mathsf R_{n,d,\epsilon,M,\sigma}$ of Definition P-9 satisfies $$c_{\epsilon}M^2 \left\{ \frac1n+\min\left(1,\frac d{n^2}\right) +\sigma^2\min\left(1,\frac{d^2}{n^2\log^2(en)}\right) \right\} \le \mathsf R_{n,d,\epsilon,M,\sigma}.$$ Moreover, for the same constants and every such $n,d,M,\sigma$, there are a capped alphabet size $d_{\mathrm{rad}}$, a source family, a padding map into $\{1,\ldots,d\}$, an embedding into $\mathcal P_{d,\epsilon,M,\sigma}$, and a coupling realizing the radius-channel construction with source constant $b_{\epsilon}^{\mathrm{rad}}$. Along this realization, for all source laws $P_0,P_1$, $$\tau(P_1)-\tau(P_0) = M\frac{\sigma}{2} \{\psi(P_1)-\psi(P_0)\},$$ and for every estimator $\widehat\tau$ taking values in $[-M,M]$, some source law $P$ satisfies $$c_{\epsilon}M^2\sigma^2 \min\left(1,\frac{d^2}{n^2\log^2(en)}\right) \le \mathbb E_P\{(\widehat\tau-\tau(P))^2\}.$$

For every overlap parameter $\epsilon$ with $0<\epsilon<1/2$, there are real constants $c_{\epsilon}$ and $C_{\epsilon}$ such that $$0<c_{\epsilon}\le 1,\qquad 1\le C_{\epsilon},\qquad c_{\epsilon}\le C_{\epsilon}.$$ For every $n,d\in\mathbb N$, $M\in\mathbb R$, and $\sigma\in\mathbb R$, suppose that

• (Sample and alphabet sizes.) $n\ge 1$ and $d\ge 1$.
• (Outcome envelope.) $M\ge 1$.
• (Radius range.) $0\le \sigma\le 2$.

Let $\mathsf R_{n,d,\epsilon,M,\sigma}$ be the minimax mean-squared risk in Definition P-9 over the real-outcome class $\mathcal P_{d,\epsilon,M,\sigma}$ with fixed overlap $\epsilon$, conditional exchangeability, consistency, conditional mean normalization, conditional second central moment envelope $M$, and approximate-homogeneity radius $\sigma M$. Define $$u_{n,d}=\frac{d^2}{n^2\log^2(en)}, \qquad h_{n,d,\sigma}=\sigma^2+\frac{d}{n^2},$$ and write $$\ell_{n,d,\sigma} = \frac{1}{n} + \min\left\{1,\frac{d}{n^2}\right\} + \sigma^2\min\left\{1,u_{n,d}\right\}, \qquad r_{n,d,\sigma} = \frac{1}{n} + \min\left\{1,u_{n,d},h_{n,d,\sigma}\right\}.$$ Then $$c_{\epsilon}M^2\ell_{n,d,\sigma} \le \mathsf R_{n,d,\epsilon,M,\sigma} \le C_{\epsilon}M^2r_{n,d,\sigma}.$$

There exist constants $c,C\in(0,\infty)$, with $c\le C$, such that the following hold.

• (Exact homogeneity.) For every pair of integers $n,d\ge 1$, $$c\left\{n^{-1}+\min\left(1,\frac d{n^2}\right)\right\} \le n^{-1}+\min\left\{1,\frac{d^2}{n^2\log^2(en)},\frac d{n^2}\right\} \le C\left\{n^{-1}+\min\left(1,\frac d{n^2}\right)\right\},$$ and $$c\left\{n^{-1}+\min\left(1,\frac d{n^2}\right)\right\} \le n^{-1}+\min\left(1,\frac d{n^2}\right) \le C\left\{n^{-1}+\min\left(1,\frac d{n^2}\right)\right\}.$$
• (Unrestricted radius.) For every pair of integers $n,d\ge 1$, $$c\left\{n^{-1}+\min\left(1,\frac{d^2}{n^2\log^2(en)}\right)\right\} \le n^{-1}+\min\left(1,\frac{d^2}{n^2\log^2(en)}\right) \le C\left\{n^{-1}+\min\left(1,\frac{d^2}{n^2\log^2(en)}\right)\right\},$$ and $$c\left\{n^{-1}+\min\left(1,\frac{d^2}{n^2\log^2(en)}\right)\right\} \le n^{-1}+\min\left(1,\frac d{n^2}\right) +4\min\left(1,\frac{d^2}{n^2\log^2(en)}\right) \le C\left\{n^{-1}+\min\left(1,\frac{d^2}{n^2\log^2(en)}\right)\right\}.$$
• (Class equality at radius two.) For every alphabet size $d$, every $\epsilon\in\mathbb R$, and every $M\in\mathbb R$, the laws represented by $\mathcal P_{d,\epsilon,M}^{\mathrm{unr}}$ in Definition P-2 are exactly the laws represented by $\mathcal P_{d,\epsilon,M,2}$ in Definition P-1.
• (Endpoint identity.) For every pair of integers $n,d\ge 1$, the radius-two upper frontier expression is exactly $$n^{-1}+\min\left(1,\frac{d^2}{n^2\log^2(en)}\right).$$