CausalSmith · AI Causal Scientist — stat_discrete_ate_minimax_loggap_polynomial_upper_match · Stat · AI reviewer score 8/10 · pinned commit 99fa82c · PDF · Lean code · Slides · arXiv · GitHub

Sharp Minimax Rates for Average Treatment Effects with Discrete Confounding under Fixed Overlap

Abstract

This paper studies minimax estimation of the average treatment effect in a finite-alphabet observational model with binary treatment and outcome, unrestricted categorywise nuisance functions, and fixed overlap. For each fixed interior overlap level $ϵ \in (0, 1/2)$ , there are $ϵ$ -dependent constants $a_{ϵ}, ρ_{ϵ}, C_{ϵ} > 0$ and a cutoff $N_{ϵ}$ such that, for every sample size $n \geq N_{ϵ}$ and positive covariate alphabet size $d \leq ρ_{ϵ} n lo g n$ , the minimax mean-squared risk over the overlap-restricted iid experiment class is $\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}$ up to constants depending on $ϵ$ . Over that same range $n \geq N_{ϵ}$ , $d > 0$ , $d \leq ρ_{ϵ} n lo g n$ , the upper bound is attained by a computable two-split hybrid estimator with universal numerical tuning: pilot-certified heavy categories are estimated by empirical treatment-control ratios, while pilot-certified light categories are estimated by a Chebyshev reciprocal polynomial whose monomials are lifted by factorial moments. Within the range $n \geq N_{ϵ}$ and $d \leq ρ_{ϵ} n lo g n$ , the rate implies a parametric regime $d = O (n lo g n)$ and a consistency frontier $d = o (n lo g n)$ . The paper also gives an overlap-phase upper envelope: a centered estimator has risk at most $n^{- 1} + 4 (1/2 - ϵ)^{2}$ for every positive $n, d$ , and at the randomized endpoint $ϵ = 1/2$ the minimax risk is bracketed between $1/ (100 n)$ and $1/ n$ for every positive $n, d$ .

Introduction

Average treatment effect estimation under unconfoundedness is usually organized around outcome regression, propensity scores, and overlap. In regular low-dimensional models, this program leads to semiparametric efficiency theory and first-order robust estimators (Hahn, 1998; Hirano et al., 2003; Robins et al., 1994; Bang et al., 2005; van der Laan et al., 2006). Modern high-dimensional causal inference extends the same target with structured nuisance estimation, orthogonal moments, and debiasing (Belloni et al., 2017; Chernozhukov et al., 2018; Chernozhukov et al., 2022). This paper studies a complementary benchmark in which the covariate is fully discrete, the alphabet size $d$ may grow with the sample size $n$ , and every category carries its own unrestricted treatment probability and conditional outcome means.

The benchmark isolates the cost of discrete confounding under fixed overlap. The observed data are iid triples $O_{i} = (X_{i}, A_{i}, Y_{i})$ , with $X_{i} \in {1, \dots, d}$ , binary treatment $A_{i}$ , and binary outcome $Y_{i}$ . Under the overlap level $ϵ$ , every positive-mass category has treatment probability in $[ϵ, 1 - ϵ]$ . The target is the adjusted average treatment effect $τ (P) = k = 1 \sum d p_{k} {μ_{1 k} - μ_{0 k}},$ written in the body as a homogeneous four-cell functional so that categories with small empirical support can be analyzed directly. Under consistency and conditional exchangeability, this observed-law functional has the usual potential-outcome interpretation.

The main result gives the sharp fixed-interior minimax rate. For each fixed $ϵ \in (0, 1/2)$ , Theorem 1 establishes constants $a_{ϵ}, ρ_{ϵ}, C_{ϵ} > 0$ and $N_{ϵ} < \infty$ such that, for $n \geq N_{ϵ}$ and $d \leq ρ_{ϵ} n lo g n$ , $a_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} \leq R_{n, d, ϵ} \leq C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$ The same result records the parametric interior $d = O (n lo g n)$ , where the risk is of order $1/ n$ , and the consistency frontier $d = o (n lo g n)$ along sequences inside the displayed calibrated range.

The estimator attaining the upper bound is explicit. It splits the sample into a pilot half and an estimation half. Categories with large pilot counts enter a ratio branch, using empirical treated and untreated outcome proportions. For $n \geq N_{0}$ , categories with small pilot counts enter a polynomial branch. The polynomial is a Chebyshev-based approximation to the reciprocal terms in the categorywise treatment-control contrast, and its monomials are estimated through normalized falling-factorial moments of the four treatment-outcome cell counts. Theorem 2 records that this hybrid is computable with operation count linear in $d$ and polynomial in the logarithmic degree $M (n)$ . The same numerical tuning is used across fixed interior overlap levels.

The rate closes the logarithmic upper-bound gap left by the closest discrete-covariate causal benchmark. Zeng et al. (2024) show that standard plug-in, inverse-probability-weighted, and doubly robust estimators have worst-case upper scale $d^{2} / n^{2} + 1/ n$ in a strong-overlap finite-alphabet model, while their lower bound has scale $d^{2} / {n^{2} (lo g n)^{2}} + 1/ n$ . For each fixed $ϵ \in (0, 1/2)$ , the hybrid construction developed here attains the lower-bound scale for $n \geq N_{ϵ}$ , $d > 0$ , and $d \leq ρ_{ϵ} n lo g n$ . The lower side is transferred from their fixed-sample control-zero construction, and the upper side is supplied by the ratio-polynomial estimator.

The estimator reflects the same approximation principle that appears in large-alphabet nonsmooth functional estimation (Paninski, 2003; Jiao et al., 2015; Wu et al., 2016; Han et al., 2020). Sparse categories have too little information for stable cellwise ratio estimation. A degree of order $lo g n$ balances approximation bias against factorial-moment variance, producing the logarithmic improvement in the large-alphabet term. Heavy categories are handled separately because their denominators are large enough for direct ratio estimation to achieve the required aggregate rate.

The paper also characterizes the randomized endpoint behavior. Theorem 2 gives a centered estimator with risk at most $\frac{1}{n} + 4 (1/2 - ϵ)^{2}$ for every $n, d$ and every $ϵ \in (0, 1/2]$ . At $ϵ = 1/2$ , treatment is randomized within each positive-mass category, and the minimax risk lies between $1/ (100 n)$ and $1/ n$ . Combining the centered estimator with the hybrid estimator yields a deterministic upper envelope involving $\frac{1}{n} + min {\frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}, (1/2 - ϵ)^{2}}$ within the fixed-interior calibration range.

The appendix records the mathematical statements and proof details used in the paper, including the product-law bridge in Lemma 20. The paper proceeds as follows. The next section reviews related work. The setup section defines the finite-alphabet experiment class, overlap cone, ATE functional, minimax risk, and hybrid estimator. The main-results section states the fixed-interior minimax theorem and the overlap-adaptive envelope. The discussion interprets the rate, the estimator, and the endpoint comparison. The appendices give the auxiliary probability, approximation, factorial-moment, heavy-cell, light-cell, and main-theorem proofs.

The paper sits at the intersection of causal inference for average treatment effects, high-dimensional observational methods, minimax theory for nonsmooth functionals, and large-alphabet discrete-distribution estimation. In the potential-outcomes tradition of Rubin (1974) and Rosenbaum et al. (1983), identification and estimation of average treatment effects are organized around consistency, conditional exchangeability, and overlap. Semiparametric analyses then characterize efficient influence functions and regular estimators under smooth low-dimensional structure (Hahn, 1998; Hirano et al., 2003; Robins et al., 1994). Doubly robust and targeted procedures extend this program by combining outcome regression and propensity-score estimation in ways that preserve first-order behavior under appropriate nuisance control (Bang et al., 2005; van der Laan et al., 2006). The present analysis uses that causal estimand and overlap vocabulary, but its rate question is driven by unrestricted finite-alphabet confounding: the covariate alphabet may grow with the sample size, and the categorywise nuisance functions are unconstrained across cells.

High-dimensional causal inference has developed complementary tools for flexible nuisance estimation and valid inference under structural restrictions. Orthogonal and debiased methods use moment equations that reduce sensitivity to first-stage regularization error (Belloni et al., 2017; Chernozhukov et al., 2018; Chernozhukov et al., 2022); related analyses clarify how overlap, support, and design complexity shape attainable performance in observational problems (D’Amour et al., 2021; Jin et al., 2025). Work on higher-order influence functions and nonparametric bias correction shows that estimating causal functionals can require corrections beyond first-order semiparametric theory when nuisance features are complex (Robins et al., 2008; Robins et al., 2009; Robins et al., 2017; Liu et al., 2017; Kennedy et al., 2024). The fixed-overlap discrete model considered here gives a complementary benchmark with combinatorial complexity: each category carries its own treatment probability and conditional outcome means, so the sharp rate depends on the number of categories.

The minimax perspective follows the classical decision-theoretic treatment of statistical rates (Bickel et al., 1993; van der Vaart, 1998; Tsybakov, 2009). For nonsmooth functionals, sharp procedures often combine approximation theory with bias correction, and logarithmic factors can mark the difference between plug-in behavior and the optimal risk (Lepski et al., 1999; Cai et al., 2011). Classical unseen-species work provides an early large-alphabet precedent (Fisher et al., 1943; Good et al., 1956; Efron et al., 1976). Modern large-alphabet functional estimation uses polynomial approximation and unbiased estimation of polynomial moments to attain sharp rates for entropy, support size, and related functionals (Paninski, 2003; Valiant et al., 2011; Valiant et al., 2017; Orlitsky et al., 2016; Wu et al., 2019; Jiao et al., 2015; Wu et al., 2016; Han et al., 2015; Han et al., 2020). The estimator constructed in this paper imports that approximation-and-factorial-moment logic into the causal four-cell contribution associated with each covariate category, while ratio estimation handles categories with enough observations.

The closest comparison is Zeng et al. (2024), whose strong-overlap discrete-covariate model is the one adopted here, with the covariate alphabet size $d$ allowed to grow with the sample size $n$ . Three of their results fix the benchmark. First, they show that the standard estimator class collapses: when the categorywise nuisances are fitted on the same sample that is used for the final average, the outcome-regression, inverse-probability-weighted, and doubly robust estimators of the ATE coincide numerically with a single count-based plug-in rule. Second, they bound that rule’s worst-case mean-squared error at the scale $d^{2} / n^{2} + 1/ n$ , with an overlap-dependent constant, so $d / n \to 0$ is sufficient for consistency of every estimator in that class; their companion worst-case-bias bound shows that the same condition is also necessary there, which makes $d / n \to 0$ the consistency benchmark for standard practice in this model. Third, their minimax lower bound over the same class of experiments scales as $d^{2} / (n^{2} lo g^{2} n) + 1/ n$ in the regime $d ≲ n lo g n$ , a factor $(lo g n)^{2}$ below their upper bound in the large-alphabet term. In the discussion following their Theorem 2, and again in their concluding discussion, Zeng et al. (2024) state that this gap is unresolved in both directions: either a polynomial-approximation estimator improves the upper bound, or the lower bound can be tightened.

The gap matters for more than bookkeeping. Robins et al. (1997) showed that unrestricted high-dimensional adjustment can obstruct uniform model-free inference, so a benchmark in which the categorywise nuisances carry no smoothness, sparsity, or ordering structure is exactly where plug-in reasoning is least trustworthy, and where the attainable rate rather than the behavior of a familiar estimator has to settle the question.

The present paper resolves that gap on the upper-bound side. For each fixed $ϵ \in (0, 1/2)$ , it constructs a computable balanced ratio-polynomial hybrid estimator whose worst-case mean-squared error is of the lower-bound scale $d^{2} / (n^{2} lo g^{2} n) + 1/ n$ for $n \geq N_{ϵ}$ , positive $d$ , and $d \leq ρ_{ϵ} n lo g n$ . In that calibrated range the logarithmically sharpened large-alphabet term and the parametric $1/ n$ component are both attained, so the minimax rate is identified, and the consistency benchmark moves from the $d / n \to 0$ of the standard estimator class to $d / (n lo g n) \to 0$ .

Setup and assumptions

Throughout the paper, $C$ denotes a finite positive constant whose value may change from line to line, with dependence displayed when it matters. Asymptotic notation is along sequences in the sample size $n$ and the alphabet size $d$ , with the overlap level $ϵ$ treated as fixed unless stated otherwise. Category indices range over $k \in {1, \dots, d}$ , treatment arms and outcomes range over ${0, 1}$ , and all risks are mean-squared risks under the product law generated by the observed-data distribution.

The observed-data model is finite and fully discrete. We first fix the variables and sampling law, then impose overlap, define the experiment class, and express the target functional as a sum of categorywise four-cell contributions.

Definition 1 [synth_7] (Observed treatment, outcome, and potential outcomes).

We write $A \in {0, 1}$ for the observed binary treatment, with $A = 1$ denoting treated status and $A = 0$ untreated status, and $Y \in {0, 1}$ for the observed binary outcome. The potential outcomes $Y (0)$ and $Y (1)$ are ${0, 1}$ -valued random variables on the same probability space as the observed variables, where $Y (a)$ is the outcome that would be recorded under treatment level $a \in {0, 1}$ .

Assumption 1 [ass:iid-sampling] (IID observed-data model).

The observed data are $O_{i} = (X_{i}, A_{i}, Y_{i})$ , $i = 1, \dots, n$ , with $O_{1}, \dots, O_{n} \sim iid P$ , where the covariate $X$ takes values in ${1, \dots, d}$ , the treatment $A$ and outcome $Y$ are binary. For each category $k \in {1, \dots, d}$ write $p_{k} = P (X = k)$ for the category mass, $π_{k} = P (A = 1 ∣ X = k)$ for the treatment probability, and, for each treatment arm $a \in {0, 1}$ , $μ_{ak} = E_{P} [Y ∣ A = a, X = k]$ for the conditional mean outcome.

⊢ Lean

Assumption 1 is the standard independent and identically distributed sampling condition for a finite-alphabet observational study (Zeng et al., 2024). It allows the law $P$ to assign arbitrary probabilities to the category–treatment–outcome cells, so all heterogeneity across categories is carried by the unrestricted masses, propensities, and conditional outcome means.

Assumption 2 [ass:overlap] (Fixed overlap).

For the overlap level $ϵ$ , every category $k$ with category mass $p_{k} > 0$ satisfies $ϵ \leq π_{k} \leq 1 - ϵ .$

⊢ Lean

Assumption 2 is the standard strong overlap condition (Zeng et al., 2024). It fixes an interior range for each positive-mass category, ensuring that both treatment arms are represented at the population level in every category contributing to the target.

Definition 2 [def:experiment-class] (Experiment class

E_{n, d, ϵ}

For $n, d \in N$ and $0 < ϵ \leq 1/2$ , the overlap-restricted iid experiment class is $E_{n, d, ϵ} := {P^{\otimes n} : P \in Prob ({1, \dots, d} \times {0, 1}^{2}) and P satisfies A ss u m pt i o n 2} .$ The law $P^{\otimes n}$ is formed from the single-observation law in Assumption 1.

⊢ Lean

Definition 3 [def:overlap-cone] (Overlap cone

C_{ϵ}

The overlap-restricted cone of nonnegative four-cell vectors is $C_{ϵ} := {u = (u_{00}, u_{01}, u_{10}, u_{11}) \in R_{+}^{4} : ϵ (u_{00} + u_{01} + u_{10} + u_{11}) \leq u_{10} + u_{11} \leq (1 - ϵ) (u_{00} + u_{01} + u_{10} + u_{11})} .$

⊢ Lean

Definition 4 [def:cell-functional] (Cell functional

ϕ (u)

For $u = (u_{00}, u_{01}, u_{10}, u_{11}) \in C_{ϵ}$ as in Definition 3, define $ϕ (u) := ⎩ ⎨ ⎧ (u_{00} + u_{01} + u_{10} + u_{11}) [\frac{u _{11}}{u _{10} + u _{11}} - \frac{u _{01}}{u _{00} + u _{01}}], 0, u \neq = (0, 0, 0, 0), u = (0, 0, 0, 0) .$

⊢ Lean

Definition 5 [def:ate-functional] (Average treatment effect

τ (P)

For a probability law $P$ on ${1, \dots, d} \times {0, 1} \times {0, 1}$ , with arbitrary masses on this finite observation alphabet, define, for $a, y \in {0, 1}$ and $k \in {1, \dots, d}$ , the joint cell mass $q_{ak y} = P (A = a, X = k, Y = y),$ and set $q_{k} = (q_{0 k 0}, q_{0 k 1}, q_{1 k 0}, q_{1 k 1}) .$ The average treatment effect functional is $τ (P) = k = 1 \sum d ϕ (q_{k}) .$

⊢ Lean

The experiment class in Definition 2 is the decision-theoretic object over which risks are evaluated. The cone in Definition 3 rewrites fixed overlap directly in terms of the four joint treatment–outcome masses within a category, and Definitions 4 and 5 turn those cell masses into the categorywise contribution and the population ATE functional. This representation is useful because the analysis can treat the target as a sum of homogeneous finite-alphabet cell functionals.

Definition 6 [def:minimax-risk] (Minimax risk

R_{n, d, ϵ}

$R_{n, d, ϵ} := τ in f P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ - τ (P))^{2}] .$ The infimum ranges over all measurable estimators $τ$ based on $O_{1}, \dots, O_{n}$ .

⊢ Lean

Definition 6 measures the worst-case mean-squared error over the fixed-overlap experiment class. The main rate theorem below evaluates this risk and compares it with the performance of a concrete estimator.

The extrema in the minimax risk.

Throughout the paper the two extrema in Definition 6 are the ordinary ones: the inner supremum is the supremum of a nonempty family of nonnegative reals that is bounded above, and the outer infimum is taken over a family of nonnegative reals bounded below by $0$ . Three facts supply this. Whenever $n > 0$ , $d > 0$ , and $0 < ϵ \leq 1/2$ , the class $E_{n, d, ϵ}$ of Definition 2 is nonempty, since the law with $p_{k} = 1/ d$ and $π_{k} = 1/2$ for every category satisfies Assumption 2. The sample space $({1, \dots, d} \times {0, 1} \times {0, 1})^{n}$ is finite, so an estimator takes finitely many values and is a bounded function of the sample. And $∣ τ (P) ∣ \leq 1$ for every law $P$ , since Definitions 4 and 5 express $τ (P) = \sum_{k} p_{k} (μ_{1 k} - μ_{0 k})$ as a convex combination of differences of conditional means in $[0, 1]$ . Together they bound the squared losses $(τ - τ (P))^{2}$ uniformly over the class, so $R_{n, d, ϵ}$ is a well-defined number in $[0, 1]$ and no extended-real value arises.

Readers comparing the text with the machine-checked development will find one bookkeeping difference. That development makes $R_{n, d, ϵ}$ a real number by fiat, assigning the value $0$ to a supremum over an empty family or over a family with no real upper bound, and reading the quotients in the displayed rate as real division with $x /0 = 0$ . The appendix proofs therefore carry the corresponding boundary cases explicitly, even though the paragraph above shows that the supremum and infimum defining $R_{n, d, ϵ}$ are the ordinary ones throughout.

The estimator uses one deterministic split to classify categories by pilot abundance and the other split to estimate the resulting heavy and light contributions. In words, before any notation: cut the sample in half; use the first half only to sort categories into those with enough observations and those without; on the well-observed categories estimate the treatment-control contrast by the obvious empirical ratios, computed from the second half; on the sparse categories, where those ratios are unstable, replace the contrast by a polynomial of degree about $lo g n$ that approximates it, and estimate that polynomial without bias from falling-factorial moments of the second-half cell counts; add the two parts and clip the total to $[- 1, 1]$ . The definitions below record the split counts, the polynomial notation, and the calibrated hybrid estimator built from these steps, and a step-by-step evaluation recipe follows the definition.

Definition 7 [def:sample-splits] (Sample splits

I_{0}, I_{1}

and counts

N_{ak y}^{(j)}

For a sample $O_{1}, \dots, O_{n}$ with $O_{i} = (X_{i}, A_{i}, Y_{i}) \in {1, \dots, d} \times {0, 1} \times {0, 1}$ , define the deterministic half-sample splits, their sizes, and the logarithmic scale $I_{0} = {1, \dots, ⌊ n /2 ⌋}, I_{1} = {⌊ n /2 ⌋ + 1, \dots, n}, m_{j} = ∣ I_{j} ∣, L = lo g (e n),$ and, for each split $j \in {0, 1}$ , treatment arm $a \in {0, 1}$ , category $k \in {1, \dots, d}$ , and outcome $y \in {0, 1}$ , the split cell count $N_{ak y}^{(j)} = # {i \in I_{j} : (A_{i}, X_{i}, Y_{i}) = (a, k, y)} .$

⊢ Lean

Definition 8 [synth_3] (Chebyshev polynomials, falling factorials, and four-cell monomials).

For $M \in N$ , $T_{M}$ denotes the degree- $M$ Chebyshev polynomial of the first kind, characterized by $T_{M} (cos θ) = cos (M θ)$ for every $θ \in R$ . For a real number $z$ and an integer $t \geq 1$ , the falling factorial is $(z)_{t} = z (z - 1) \dots (z - t + 1)$ , with $(z)_{0} = 1$ ; it is applied to the split cell counts as $(N_{ak y}^{(1)})_{r_{a y}}$ and to the estimation-split size as $(m_{1})_{∣ r ∣} = \prod_{ℓ = 0}^{∣ r ∣ - 1} (m_{1} - ℓ)$ , the empty product being $1$ . For a four-cell vector $u = (u_{00}, u_{01}, u_{10}, u_{11})$ and a multi-index $r = (r_{a y})_{a, y \in {0, 1}} \in N_{0}^{4}$ of total degree $∣ r ∣ = \sum_{a, y \in {0, 1}} r_{a y}$ , the monomial $u^{r}$ is $\prod_{a, y \in {0, 1}} u_{a y}^{r_{a y}}$ . For a category $k$ and a multi-index $r$ , the normalized factorial-moment monomial is $m_{k, r} = \frac{\prod _{a, y \in {0, 1}} ( N _{ak y}^{(1)} ) _{r_{a y}}}{( m _{1} ) _{∣ r ∣}} .$

Definition 9 [def:hybrid-estimator-handle] (Hybrid estimator

τ_{n}^{hyb}

Using the deterministic splits $I_{0}, I_{1}$ , split sizes $m_{j}$ , logarithmic scale $L = lo g (e n)$ , and split counts $N_{ak y}^{(j)}$ from Definition 7, set $A_{0} = 6, λ_{0} = 256, b_{0} = 4096,$ $D_{A_{0}} = 8 lo g (9 A_{0} /8) = 8 lo g (27/4),$ and $α_{0} = min {1, \frac{1}{32 lo g A _{0}}, \frac{1}{256 D _{A_{0}}}} .$ For $n \geq 2$ , define $M (n) = max {2, ⌊ α_{0} L ⌋}, B (n) = b_{0} L / m_{1} .$ Let $N_{0}$ be the least numerical cutoff such that, for every $n \geq N_{0}$ , $α_{0} L \geq 2, 4 M (n)^{2} \leq m_{1}, 4 M (n) / m_{1} \leq 3 B (n) /4.$ For every $n$ , define the pilot-certified heavy and light category sets $H_{n} = {k : a, y \sum N_{ak y}^{(0)} > λ_{0} L}, L_{n} = H_{n}^{c} (n \geq N_{0}), L_{n} = \emptyset (n < N_{0}),$ so that for $n < N_{0}$ every category is treated by the ratio branch below. For $n \geq N_{0}$ , abbreviate $M = M (n)$ and $B = B (n)$ . Put $N_{k}^{(1)} = a, y \sum N_{ak y}^{(1)}, N_{ak}^{(1)} = y \sum N_{ak y}^{(1)},$ and define the heavy-category ratio contribution $h_{k} = \frac{N _{k}^{(1)}}{m _{1}} {\frac{N _{1 k 1}^{(1)}}{N _{1 k}^{(1)}} 1 {N_{1 k}^{(1)} > 0} - \frac{N _{0 k 1}^{(1)}}{N _{0 k}^{(1)}} 1 {N_{0 k}^{(1)} > 0}} .$ Define $H_{M} (x) = \frac{1 - T _{M} ( 1 - 2 x )}{2 M ^{2}}, E_{M} (x) = \frac{H _{M} ( x )}{x}, G_{M} (x) = \frac{1 - E _{M} ( x )}{x},$ where $E_{M}$ and $G_{M}$ are interpreted by polynomial continuation at zero. For $u = (u_{00}, u_{01}, u_{10}, u_{11})$ , set $s_{a} (u) = u_{a 0} + u_{a 1}, s (u) = s_{0} (u) + s_{1} (u),$ $t_{1} (u) = u_{11}, t_{0} (u) = u_{01},$ and define the light-cell polynomial $P_{M, B} (u) = \frac{s ( u ) t _{1} ( u )}{B} G_{M} (\frac{s _{1} ( u )}{B}) - \frac{s ( u ) t _{0} ( u )}{B} G_{M} (\frac{s _{0} ( u )}{B}) .$ Expand $P_{M, B} (u) = ∣ r ∣ \leq M \sum c_{r} u^{r} .$ For each category $k$ , define $P_{k} = ∣ r ∣ \leq M \sum c_{r} \frac{\prod _{a, y} ( N _{ak y}^{(1)} ) _{r_{a y}}}{( m _{1} ) _{∣ r ∣}} .$ The heavy and light sums are $T_{H} = k \in H_{n} \sum h_{k}, T_{L} = k \in L_{n} \sum P_{k} .$ The truncated balanced ratio-polynomial hybrid estimator is $τ_{n}^{hyb} = max {- 1, min (1, T_{H} + T_{L})} .$ The same calibrated estimator is used for every overlap level.

⊢ Lean

The split in Definition 7 separates category selection from contribution estimation. The polynomial notation in Definition 8 supports unbiased estimation of polynomial cell functionals through factorial moments. The estimator in Definition 9 then combines direct ratio estimation on pilot-certified heavy categories with a Chebyshev-based polynomial contribution on pilot-certified light categories, using fixed numerical tuning.

Computing the hybrid estimator.

The definition is a finite recipe in the split counts, and it evaluates in the following steps. Throughout, $L = lo g (e n)$ , $M = M (n)$ , and $B = B (n)$ are the scale, degree, and light-cell scale fixed in Definition 9; the cutoff $N_{0}$ there is the least integer meeting the three displayed inequalities, so it is pinned down by the numerical constants $α_{0}, λ_{0}, b_{0}$ alone and can be tabulated once, before any data are seen.

Pilot counts and classification. From the pilot split $I_{0}$ , form the counts $N_{ak y}^{(0)}$ and the category totals $N_{k}^{(0)} = \sum_{a, y} N_{ak y}^{(0)}$ . Place category $k$ in $H_{n}$ when $N_{k}^{(0)} > λ_{0} L$ . For $n \geq N_{0}$ the remaining categories form $L_{n}$ ; for $n < N_{0}$ every category goes to the ratio branch.
Estimation counts. From the estimation split $I_{1}$ , form $N_{ak y}^{(1)}$ together with the arm totals $N_{ak}^{(1)} = \sum_{y} N_{ak y}^{(1)}$ and the category totals $N_{k}^{(1)} = \sum_{a, y} N_{ak y}^{(1)}$ .
Ratio branch. For each $k \in H_{n}$ , evaluate $h_{k}$ from the displayed ratio formula; an arm with no observation contributes zero through the accompanying indicator.
Polynomial coefficients. Compute the reciprocal coefficients $g_{M, j}$ , $0 \leq j \leq M - 2$ , of the continuation $G_{M}$ , which are the coefficients characterized in Definition 13 and are read off from those of the Chebyshev polynomial $T_{M}$ . They depend on $n$ alone, so one list serves every category.
Light branch. For each $k \in L_{n}$ and each arm $a$ , accumulate the normalized factorial moments $m_{k, r}$ of Definition 8 against the weights $B^{- 1} g_{M, j} B^{- j} (t j)$ prescribed by the sparse-arm expansion of Lemma 8, and set $P_{k} = A_{1, k} - A_{0, k}$ . This evaluates $P_{k} = \sum_{∣ r ∣ \leq M} c_{r} m_{k, r}$ directly from counts, so the multivariate polynomial $P_{M, B}$ enters only through those weights.
Aggregate and truncate. Add the heavy sum $T_{H}$ and the light sum $T_{L}$ , then clip the total to $[- 1, 1]$ .

Every step reads only the split counts, and the computability statement of Theorem 2 bounds the whole evaluation by $K d M (n)^{4}$ operations for a universal integer $K$ , with $M (n)$ of order $lo g n$ .

We next connect the observed-data functional to the usual potential-outcome interpretation of the ATE. The following assumptions are stated separately from the experiment class because the minimax problem is formulated on observed laws, while causal interpretation uses a full-data overlay.

Assumption 3 [ass:consistency] (Observed-outcome consistency).

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

⊢ Lean

Assumption 3 is the standard consistency condition linking the recorded outcome to the potential outcome under the realized treatment (Zeng et al., 2024). It gives the observed binary outcome its causal interpretation once treatment is assigned.

Assumption 4 [ass:conditional-exchangeability] (Conditional exchangeability).

The potential outcomes satisfy $(Y (0), Y (1)) ⊥ A ∣ X .$

⊢ Lean

Assumption 4 is the standard conditional exchangeability condition (Zeng et al., 2024). Together with Assumptions 3 and 2, it identifies the category-adjusted contrast represented by $τ (P)$ in Definition 5; this is the finite-alphabet version of the usual adjustment argument in observational causal inference (Rubin, 1974; Rosenbaum et al., 1983).

Main results

The preceding section defined the overlap-restricted experiment class, the ATE functional, the minimax risk, and the balanced ratio-polynomial hybrid estimator. We now state the rate conclusions. Two auxiliary definitions fix the product-law notation used in the statements and the centered estimator used at the randomized endpoint.

Definition 10 [synth_10] (Centered endpoint estimator

τ_{ctr}

For $n \in N$ with $n > 0$ and observed units $O_{i} = (X_{i}, A_{i}, Y_{i}) \in {1, \dots, d} \times {0, 1} \times {0, 1}$ , define the centered endpoint estimator by $τ_{ctr} (O_{1}, \dots, O_{n}) = \frac{1}{n} i = 1 \sum n 2 (2 A_{i} - 1) (Y_{i} - \frac{1}{2}) .$

The centered estimator in Definition 10 is a linear contrast tailored to the near-randomization regime. It supplies the benchmark used below when overlap approaches the randomized endpoint.

Definition 11 [synth_13] (Product sampling laws).

For a finite index set $J$ and a probability law $P$ for one observed unit $O = (X, A, Y)$ , $P^{\otimes J}$ denotes the product law on families $(O_{j})_{j \in J}$ under which the coordinates are independent and each coordinate has law $P$ . For a sample $O_{1}, \dots, O_{n}$ with single-observation law $P$ on ${1, \dots, d} \times {0, 1} \times {0, 1}$ , we write $μ_{n} = P^{\otimes n}$ for the $n$ -fold product law of the observed sample.

The notation in Definition 11 keeps the single-observation law and its product sample law explicit. The minimax bounds below are stated over the same product-law experiment class as in Definition 2.

Theorem 1 [thm:sharp-minimax-fixed-interior] (Sharp fixed-interior minimax rate).

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

(Matched minimax envelope.) For every $n, d$ , every single-observation law $P$ , and every sample law $μ_{n}$ in the experiment class $E_{n, d, ϵ}$ of Definition 2, if $d > 0, n \geq N_{ϵ}, d \leq ρ_{ϵ} n lo g n,$ then the minimax risk $R_{n, d, ϵ}$ of Definition 6 and the truncated balanced ratio-polynomial hybrid estimator $τ_{n}^{hyb}$ of Definition 9 satisfy $a_{ϵ} r_{n, d} \leq R_{n, d, ϵ} \leq P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ_{n}^{hyb} - τ (P))^{2}] \leq C_{ϵ} 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 $μ_{n}$ in $E_{n, d, ϵ}$ , if $d > 0, n \geq N_{ϵ}, d \leq K n lo g n, d \leq ρ_{ϵ} n lo g n,$ then $\frac{a _{ϵ}}{n} \leq R_{n, d, ϵ} \leq \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} \leq ρ_{ϵ} n_{j} lo g n_{j}$ eventually, the minimax risk converges to zero exactly along the sequences satisfying the vanishing normalized dimension condition: $R_{n_{j}, d_{j}, ϵ} \to 0 ⟺ \frac{d _{j}}{n _{j} lo g n _{j}} \to 0.$

⊢ Lean

Theorem 1 identifies the fixed-interior minimax mean-squared-error rate for each fixed $ϵ \in (0, 1/2)$ , positive $d$ , $n \geq N_{ϵ}$ , and $d \leq ρ_{ϵ} n lo g n$ as $n^{- 1} + d^{2} {n^{2} (lo g n)^{2}}^{- 1}$ through matching lower and upper bounds. The lower side uses the fixed-sample discrete-covariate lower-bound construction of Zeng et al. (2024), which enters through the transfer step recorded as Lemma 2; the upper side is attained by the hybrid estimator already defined in Definition 9. The theorem also records the parametric interior $d = O (n lo g n)$ , where the risk is of order $1/ n$ , and the consistency criterion $d = o (n lo g n)$ along sequences satisfying the displayed fixed-interior dimension range.

One feature of the statement deserves comment. The displayed bounds concern $R_{n, d, ϵ}$ and a supremum over the whole class, so they do not depend on the particular law $P$ and sample law $μ_{n}$ that the statement quantifies over. Those two quantifiers carry the requirement that $E_{n, d, ϵ}$ be inhabited at the pair $(n, d)$ : the conclusion is asserted exactly when some overlap law witnesses the class, which is the condition that makes the worst-case risk an ordinary supremum in the sense discussed with Definition 6.

The rate has the same two-component structure as other nonsmooth large-alphabet functional problems: an ordinary sampling term and an approximation-driven large-alphabet term (Jiao et al., 2015; Wu et al., 2016; Han et al., 2020). In this causal problem, the approximation term enters through the cell contribution $ϕ$ of Definition 4; heavy categories are handled by ratios, while light categories use a polynomial approximation whose coefficients can be estimated through factorial moments. The logarithmic denominator in the second term is the gain supplied by the polynomial branch relative to purely cellwise plug-in behavior.

The next result separates implementation, fixed-overlap calibration, near-randomization control, and the randomized endpoint. Its fixed-overlap statement uses the same numerical hybrid construction for every interior overlap class, while the deterministic selected estimator combines the hybrid and centered estimators according to their displayed envelopes.

Theorem 2 [thm:overlap-adaptive-universal-hybrid] (Overlap adaptive hybrid envelope).

With $τ_{n}^{hyb}$ as in Definition 9 and $R_{n, d, ϵ}$ as in Definition 6, the following assertions hold.

Computability. There is a universal integer $K > 0$ such that, for every $n, d \in 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}, \dots, O_{n}$ , evaluates exactly to $τ_{n}^{hyb}$ .
Fixed-overlap hybrid calibration. For every overlap level $ϵ$ with $0 < ϵ < 1/2$ , there are constants $C_{ϵ}, ρ_{ϵ} > 0$ and an integer $N_{ϵ}$ such that, for all $n, d \in N$ with $n > 0$ , $d > 0$ , $n \geq N_{ϵ}$ , and $d \leq ρ_{ϵ} n lo g n,$ the hybrid estimator satisfies $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ_{n}^{hyb} - τ (P))^{2}] \leq C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$ For the deterministic estimator $τ_{C_{ϵ}, ϵ} = {τ_{n}^{hyb}, τ_{ctr}, if C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( l o g n ) ^{2}}} \leq \frac{1}{n} + 4 (1/2 - ϵ)^{2}, otherwise,$ one also has $R_{n, d, ϵ} \leq P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ_{C_{ϵ}, ϵ} - τ (P))^{2}] \leq max {C_{ϵ}, 4} [\frac{1}{n} + min {\frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}, (1/2 - ϵ)^{2}}] .$
Centered randomization bound. For every overlap level $ϵ$ with $0 < ϵ \leq 1/2$ and every $n, d \in N$ with $n > 0$ and $d > 0$ , the centered estimator $τ_{ctr} = \frac{1}{n} i = 1 \sum n 2 (2 A_{i} - 1) (Y_{i} - \frac{1}{2})$ satisfies $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ_{ctr} - τ (P))^{2}] \leq \frac{1}{n} + 4 (1/2 - ϵ)^{2} .$
Endpoint randomization bracket. For every $n, d \in N$ with $n > 0$ and $d > 0$ , $\frac{1}{100 n} \leq R_{n, d, 1/2} \leq \frac{1}{n} .$

⊢ Lean

Theorem 2 gives a computable form of the estimator and an overlap-phase envelope. The operation count is polynomial in the degree $M (n)$ and linear in the alphabet size $d$ , giving an explicit count-based procedure with the stated risk certificate. For every fixed interior overlap level, the same hybrid tuning from Definition 9 attains the sharp fixed-interior upper rate for $n \geq N_{ϵ}$ , $d > 0$ , and $d \leq ρ_{ϵ} n lo g n$ .

The two branches of the selector call for a word on status. The hybrid estimator $τ_{n}^{hyb}$ and the centered estimator $τ_{ctr}$ are each computable from the sample alone. The rule $τ_{C_{ϵ}, ϵ}$ that chooses between them is not: it compares the two risk certificates, and $C_{ϵ}$ is an existence constant produced by the fixed-overlap upper-bound argument rather than a tabulated tuning parameter shipped with the procedure. The selector is accordingly an oracle-calibrated device for stating one envelope that covers both regimes, and the implementable objects in this paper are the two branches themselves.

The centered estimator in Definition 10 explains the endpoint behavior. As $ϵ$ approaches $1/2$ , treatment assignment is close to randomized within each category, and the bound in Theorem 2 contracts to the $1/ n$ scale. The selected estimator therefore records, in one displayed envelope, the large-alphabet fixed-interior contribution and the near-randomization contribution. The endpoint bracket gives the exact order $1/ n$ at $ϵ = 1/2$ , completing the comparison between the interior fixed-overlap regime and the randomized endpoint.

Discussion and extensions

What the fixed-interior rate says, read as econometrics, is that discrete confounding has a price of its own. Splitting the rate into the ordinary sampling term $1/ n$ and the large-alphabet term $d^{2} / {n^{2} (lo g n)^{2}}$ separates the parametric contribution from the additional large-alphabet contribution in this unrestricted finite-covariate model. Because the covariate distribution here is unrestricted across categories, the fixed-interior minimax lower bound makes this price a benchmark within the stated finite-covariate experiment class and range $n \geq N_{ϵ}$ , $d \leq ρ_{ϵ} n lo g n$ , complementing classical semiparametric ATE theory for regular low-dimensional models (Hahn, 1998; Hirano et al., 2003; Robins et al., 1994; Bang et al., 2005; van der Laan et al., 2006) and higher-order analyses of nonregular causal functionals (Robins et al., 2008; Robins et al., 2009; Robins et al., 2017; Liu et al., 2017; Kennedy et al., 2024). The statement holds for each fixed $ϵ \in (0, 1/2)$ , positive $d$ , $n \geq N_{ϵ}$ , and $d \leq ρ_{ϵ} n lo g n$ .

Within this calibrated range, the estimator in Definition 9 explains how the rate is attained constructively. Heavy categories are estimated through empirical treatment-control ratios, where the relevant denominators are large enough for the ratio behavior to be controlled. Light categories are handled through a Chebyshev-derived polynomial approximation to the cell contribution in Definition 4, with factorial moments converting the polynomial into an unbiased split-sample estimate of its population analogue. The resulting hybrid treats the singular ratio structure of $ϕ$ as an approximation problem on sparse cells and as an ordinary ratio-estimation problem on sufficiently populated cells.

This decomposition also clarifies the logarithmic factor. In the finite-alphabet experiment class of Definition 2, the alphabet size can create many categories whose population mass is too small for direct ratio estimation to behave parametrically. Polynomial approximation spreads the information in those sparse cells across a degree of order $lo g n$ , and the factorial-moment construction makes that approximation estimable from counts. The main theorem therefore turns the large-alphabet causal difficulty into the same approximation-versus-variance balance that appears in nonsmooth functional estimation, while preserving the adjusted ATE target in Definition 5.

The endpoint statements in Theorem 2 connect the fixed-interior result to the randomized boundary. When $ϵ = 1/2$ , treatment is randomized within every positive-mass category, and the minimax risk is bracketed at the parametric scale $1/ n$ . For interior values close to the endpoint, the centered estimator has the displayed risk bound $1/ n + 4 (1/2 - ϵ)^{2}$ . The selected estimator combines this endpoint behavior with the hybrid envelope, yielding the upper scale $\frac{1}{n} + min {\frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}, (1/2 - ϵ)^{2}}$ within the fixed-interior calibration range. Thus the same analysis gives both a sharp fixed-class rate and a deterministic upper envelope that reflects proximity to randomized assignment.

The results are also informative for high-dimensional causal inference. In many semiparametric and machine-learning approaches, structural conditions on nuisance functions, such as smoothness, sparsity, or predictive structure, shape attainable rates (Balakrishnan et al., 2023; Jin et al., 2025). Here the category probabilities and outcome regressions are unrestricted, so the rate isolates the cost of discrete confounding itself. The parametric interior regime $d = O (n lo g n)$ and the consistency criterion $d = o (n lo g n)$ , both under the stated calibration range of Theorem 1, give concrete benchmarks against which additional structural restrictions can be compared.

Limitations and future work.

A remaining open direction is the triangular-array lower-envelope problem in which the overlap level varies with sample size, $ϵ = ϵ_{n}$ , especially near the randomized endpoint. The fixed-class theorem establishes the sharp rate for each fixed $0 < ϵ < 1/2$ in its calibrated large-sample range, and the endpoint bracket establishes the parametric scale at $ϵ = 1/2$ . The combined upper envelope in Theorem 2 supplies a deterministic attainable bound across the fixed-interior calibration range. A matching lower envelope for sequences $ϵ_{n}$ would characterize the transition between the fixed-interior sparse-cell difficulty and the randomized endpoint behavior.

Appendices

Proofs and auxiliary lemmas

This appendix records the auxiliary statements that support the lower bound, the hybrid upper bound, and the endpoint comparison. The first group fixes count notation for arbitrary subsamples and gives the pilot event that separates categories by population mass with polynomially small error probability.

Definition 12 [synth_1] (Category and cell counts).

For observations $O_{i} = (X_{i}, A_{i}, Y_{i})$ indexed by a finite set $I$ , a category $k \in {1, \dots, d}$ , and an arm $a \in {0, 1}$ , the category count, the arm-specific category count, and the arm-specific outcome-one count are $N_{k} = i \in I \sum 1 {X_{i} = k}, N_{ak} = i \in I \sum 1 {X_{i} = k, A_{i} = a}, N_{ak 1} = i \in I \sum 1 {X_{i} = k, A_{i} = a, Y_{i} = 1} .$ For the deterministic pilot split $I_{0}$ of Definition 7 we write $m_{0} = ∣ I_{0} ∣$ for its size and $N_{k}^{(0)} = \sum_{a, y \in {0, 1}} N_{ak y}^{(0)}$ for the pilot count of category $k$ .

Lemma 1 [lem:pilot-sandwich] (Pilot sandwich tail bound).

Let $L = lo g (e n)$ and let $m_{0} = ∣ I_{0} ∣$ be the pilot-split size from Definition 7. For a threshold $t \in R$ , define $H (t) = {k : N_{k}^{(0)} > t L}, L (t) = H (t)^{c},$ and $B_{-} (t) = \frac{t L}{2 m _{0}}, B_{+} (t) = \frac{2 t L}{m _{0}} .$ The pilot heavy/light sandwich has the following two polynomial tail guarantees.

(Arbitrary polynomial exponent.) For every $K > 0$ and $c > 0$ , there exist constants $t_{0} > 0$ , $C > 0$ , and $N$ such that, for every $t \geq t_{0}$ , every $n \geq N$ , every dimension $d$ satisfying $d \leq c n L$ , every probability law $P$ on ${1, \dots, d} \times {0, 1}^{2}$ , and every sample law $μ_{n}$ satisfying the iid sampling condition in Assumption 1, $μ_{n} (H (t) \neq \subseteq {k : p_{k} \geq B_{-} (t)} or L (t) \neq \subseteq {k : p_{k} \leq B_{+} (t)}) \leq C n^{- K} .$
(Fixed threshold specialization.) For every $c > 0$ , there exist constants $C > 0$ and $N$ such that, for every $n \geq N$ , every dimension $d$ satisfying $d \leq c n L$ , every probability law $P$ on ${1, \dots, d} \times {0, 1}^{2}$ , and every sample law $μ_{n}$ satisfying the iid sampling condition in Assumption 1, $μ_{n} (H (256) \neq \subseteq {k : p_{k} \geq B_{-} (256)} or L (256) \neq \subseteq {k : p_{k} \leq B_{+} (256)}) \leq C n^{- 4} .$

⊢ Lean

Proof of Lemma 1.

Fix $n, d, P, t$ , and let $μ_{n}$ be a sample law satisfying Assumption 1; thus $μ_{n} = P^{\otimes n}$ . Write $L = lo g (e n)$ , $m_{0} = ∣ I_{0} ∣ = ⌊ n /2 ⌋$ , and $p_{k} = P (X = k)$ . For a category $k$ , set $Z_{ik} = 1 {X_{i} = k}, i \in I_{0},$ so that $N_{k}^{(0)} = i \in I_{0} \sum Z_{ik} .$ Under Assumption 1, the one-observation mean of this indicator is $p_{k}$ , and $N_{k}^{(0)}$ is the Bernoulli count from the deterministic pilot split of size $m_{0}$ .

The pilot heavy and light sets used in the bad event are $H = {k : ⌊ t L ⌋ < N_{k}^{(0)}}, L = H^{c} .$ Equivalently, since $N_{k}^{(0)}$ is integer-valued, $k \in H$ exactly when $t L < N_{k}^{(0)}$ . Thus $B_{t} = {H \neq \subseteq {k : p_{k} \geq t L / (2 m_{0})} or L \neq \subseteq {k : p_{k} \leq 2 t L / m_{0}}} .$ If the heavy-set condition fails, then for some $k$ , $p_{k} < t L / (2 m_{0})$ and $⌊ t L ⌋ < N_{k}^{(0)}$ , hence $t L < N_{k}^{(0)}$ . If the light-set condition fails, then for some $k$ , $2 t L / m_{0} < p_{k}$ and $k \in / H$ ; equivalently $⌊ t L ⌋ \geq N_{k}^{(0)}$ , which gives $N_{k}^{(0)} \leq t L$ . Hence $B_{t} \subseteq k = 1 ⋃ d {p_{k} < \frac{t L}{2 m _{0}}, t L < N_{k}^{(0)}} \cup k = 1 ⋃ d {\frac{2 t L}{m _{0}} < p_{k}, N_{k}^{(0)} \leq t L} .$

Both count tails below are Bernoulli-count tails for the ambient iid sequence $(O_{i})_{i \geq 0}$ , whereas $B_{t}$ is an event of the sample law $μ_{n}$ . The pilot count $N_{k}^{(0)}$ depends only on the first $n$ observations, so Lemma 20 identifies the law of that segment under $P^{\otimes \infty}$ with $μ_{n} = P^{\otimes n}$ , and the two tails may be read off on either side.

For any $ℓ \in R$ , the Bernoulli-count upper tail used here gives $m_{0} p_{k} < ℓ /2 ⟹ μ_{n} {ℓ < N_{k}^{(0)}} \leq exp {- ℓ (lo g 2 - 1/2)} .$ Applying this with $ℓ = t L$ bounds the upper-count branch whenever $p_{k} < t L / (2 m_{0})$ .

Similarly, the lower-tail bound gives $2 ℓ < m_{0} p_{k} ⟹ μ_{n} {N_{k}^{(0)} \leq ℓ} \leq exp {- m_{0} p_{k} /8} \leq exp {- ℓ /4} .$ Applying this with $ℓ = t L$ bounds the lower-count branch whenever $2 t L / m_{0} < p_{k}$ .

Now fix a category $k$ . For the first cellwise event in the displayed union, either $p_{k} < t L / (2 m_{0})$ , in which case the event is contained in ${t L < N_{k}^{(0)}}$ and the upper-tail bound applies, or the mass inequality fails, in which case the event is empty. For the second cellwise event, either $2 t L / m_{0} < p_{k}$ , in which case the event is contained in ${N_{k}^{(0)} \leq t L}$ and the lower-tail bound applies, or the mass inequality fails, in which case the event is empty. Taking the union bound over the $d$ categories therefore yields, for $t \geq 0$ , $n \geq 2$ , and every $μ_{n}$ satisfying Assumption 1, $μ_{n} (B_{t}) \leq d [exp {- (t L) (lo g 2 - 1/2)} + exp {- (t L) /4}] .$

Now fix $K > 0$ and $c > 0$ . Since $lo g 2 - 1/2 > 0$ , set $t_{0} = max {\frac{K + 4}{lo g 2 - 1/2}, 4 (K + 4)}, C = 2 c, N = 2.$ For $t \geq t_{0}$ , $K + 4 \leq t (lo g 2 - 1/2), K + 4 \leq t /4.$ Thus, whenever $n \geq N$ , $d \leq c n L$ , and $μ_{n}$ satisfies Assumption 1, $μ_{n} (B_{t}) \leq d [e^{- (t L) (l o g 2 - 1/2)} + e^{- (t L) /4}] \leq c n L \cdot 2 e^{- (K + 4) L} \leq 2 c n^{2} e^{- (K + 4) L} = 2 c e^{- (K + 4)} n^{- K - 2} \leq 2 c n^{- K} .$ Here $L \leq n$ for $n \geq 1$ , and $e^{- q L} = e^{- q} n^{- q}$ has been used with $q = K + 4$ , together with $e^{- (K + 4)} \leq 1$ and $n^{- K - 2} \leq n^{- K}$ for $n \geq 1$ . This proves the arbitrary-polynomial assertion.

For the fixed calibration, take $K = 4$ and $t = 256$ . The numerical inequalities $8 \leq 256 (lo g 2 - 1/2), 8 \leq 256/4$ follow from $0.6931471803 < lo g 2$ and elementary arithmetic. The same decay calculation gives, for every $c > 0$ , the choices $C = 2 c$ and $N = 2$ , and hence $μ_{n} (B_{256}) \leq C n^{- 4} .$ This is the stated fixed-calibration bound.

∎

Definition 12 extends the split-count notation of Definition 7 to arbitrary index sets, which is useful for the heavy-cell residual and missing-arm bounds below. Lemma 1 is the probabilistic gate for the hybrid estimator: categories selected as heavy have population mass at least a lower multiple of $L / m_{0}$ , while categories selected as light have population mass at most an upper multiple of $L / m_{0}$ , up to a tail probability that can be made polynomially small. The fixed-threshold clause is the specialization used by the numerical tuning in Definition 9.

The next statements supply the lower-bound transfer and the randomized-endpoint comparison. The transfer invokes the fixed-sample discrete-covariate lower bound of Zeng et al. (2024) on a control-zero subclass, where the ATE functional in Definition 5 coincides with the treated-response functional used in that source.

Lemma 2 [lem:ate-lower-bound-transfer] (ATE lower-bound transfer).

Fix an overlap level $ϵ$ with $0 < ϵ < 1/2$ . For the minimax risk $R_{n, d, ϵ}$ in Definition 6, there exist constants $a_{ϵ}, b_{ϵ} > 0$ and an integer $N_{ϵ}$ such that, for every $n, d \in N$ , if $d > 0$ , $n \geq N_{ϵ}$ , and $d \leq b_{ϵ} n lo g n,$ then $R_{n, d, ϵ} \geq a_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$

⊢ Lean

Proof of Lemma 2.

With the cell-mass notation of Definition 5, write $μ_{ak} (P) = \frac{q _{ak 1}}{q _{ak 0} + q _{ak 1}}$ for every arm $a \in {0, 1}$ and category $k$ , using the totalized real-ratio convention that the displayed value is $0$ when $q_{ak 0} + q_{ak 1} = 0$ . On positive arm cells this is the usual conditional mean $E_{P} [Y ∣ A = a, X = k]$ . Define the control-zero subclass by $D_{0}^{(n, d)} (ϵ) := {P^{\otimes n} \in E_{n, d, ϵ} : μ_{0 k} (P) = 0 for every k = 1, \dots, d} .$ For $P^{\otimes n} \in D_{0}^{(n, d)} (ϵ)$ , write the treated-arm functional as $ψ_{1} (P) = k = 1 \sum d p_{k} μ_{1 k} .$ For this auxiliary subclass risk, the supremum over $D_{0}^{(n, d)} (ϵ)$ is the order-theoretic supremum over the displayed class, equal to $0$ when that class is empty.

Since $0 < ϵ < 1/2$ , the fixed-sample control-zero lower-bound statement of (Zeng et al., 2024) gives constants $a_{ϵ}, b_{ϵ} > 0$ and $N_{ϵ} \in N$ such that, for every $n, d$ with $0 < d$ , $N_{ϵ} \leq n$ , and $d \leq b_{ϵ} n lo g n$ , $a_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} \leq ψ in f P^{\otimes n} \in D_{0}^{(n, d)} (ϵ) sup E_{P} [(ψ - ψ_{1} (P))^{2}],$ where the infimum is over measurable estimators based on $O_{1}, \dots, O_{n}$ .

We next identify the ATE functional on this subclass from the displayed finite-cell definitions. For a fixed category $k$ , set $s_{ak} = q_{ak 0} + q_{ak 1}, p_{k} = s_{0 k} + s_{1 k} .$ If $q_{k} = (0, 0, 0, 0)$ , then $ϕ (q_{k}) = 0$ , $p_{k} = 0$ , and hence $ϕ (q_{k}) = p_{k} (μ_{1 k} - μ_{0 k}) .$ If $q_{k} \neq = (0, 0, 0, 0)$ , Definitions 4 and 5 give $ϕ (q_{k}) = p_{k} {\frac{q _{1 k 1}}{s _{1 k}} - \frac{q _{0 k 1}}{s _{0 k}}} = p_{k} (μ_{1 k} - μ_{0 k}),$ where the second equality is the totalized definition of $μ_{ak}$ . Summing over categories yields $τ (P) = k = 1 \sum d p_{k} (μ_{1 k} - μ_{0 k}) .$ For $P^{\otimes n} \in D_{0}^{(n, d)} (ϵ)$ , the defining control-zero condition gives $μ_{0 k} = 0$ for every $k$ , so $τ (P) = k = 1 \sum d p_{k} (μ_{1 k} - μ_{0 k}) = k = 1 \sum d p_{k} μ_{1 k} = ψ_{1} (P) .$

The class suprema used below are bounded above on inhabited classes. For any overlap law $P$ , the same finite-cell identity gives $τ (P) = k = 1 \sum d p_{k} (μ_{1 k} - μ_{0 k}) .$ The category masses satisfy $p_{k} \geq 0$ and $\sum_{k = 1}^{d} p_{k} = 1$ , and the totalized binary outcome means satisfy $0 \leq μ_{ak} \leq 1$ . Hence $∣ μ_{1 k} - μ_{0 k} ∣ \leq 1$ for each $k$ , so $∣ τ (P) ∣ \leq k = 1 \sum d p_{k} ∣ μ_{1 k} - μ_{0 k} ∣ \leq k = 1 \sum d p_{k} = 1.$ For any estimator $τ$ , pointwise domination on the finite sample alphabet gives $∣ τ (o_{1}, \dots, o_{n}) ∣ \leq o_{1}^{'}, \dots, o_{n}^{'} \sum ∣ τ (o_{1}^{'}, \dots, o_{n}^{'}) ∣.$ Combining this inequality with $∣ τ (P) ∣ \leq 1$ yields $∣ τ (o_{1}, \dots, o_{n}) - τ (P) ∣ \leq o_{1}^{'}, \dots, o_{n}^{'} \sum ∣ τ (o_{1}^{'}, \dots, o_{n}^{'}) ∣ + 1.$ After squaring and integrating under $P^{\otimes n}$ , $E_{P} [(τ - τ (P))^{2}] \leq {o_{1}, \dots, o_{n} \sum ∣ τ (o_{1}, \dots, o_{n}) ∣ + 1}^{2} .$ For $P^{\otimes n} \in D_{0}^{(n, d)} (ϵ)$ , the identity $τ (P) = ψ_{1} (P)$ gives the same bound with $ψ_{1} (P)$ in place of $τ (P)$ . Each displayed mean squared error is also nonnegative because it is the integral of a square.

Fix a measurable estimator $τ$ . In the real-valued order convention used for these risks, a supremum over an empty class is $0$ . The displayed envelope makes the squared-loss family bounded above whenever the relevant class is inhabited, so an inhabited supremum lies above each of its indexed values. If $D_{0}^{(n, d)} (ϵ)$ is empty, its subclass supremum is therefore $0$ . The ambient supremum over $E_{n, d, ϵ}$ is also $0$ when the ambient class is empty; when it is inhabited, the envelope applies and any member supplies a nonnegative mean squared error below the supremum. Hence the estimatorwise comparison holds in the empty-subclass case.

If $D_{0}^{(n, d)} (ϵ)$ is inhabited, take $P^{\otimes n} \in D_{0}^{(n, d)} (ϵ)$ . By the definition of the subclass, the same product law is in $E_{n, d, ϵ}$ , and the target identity gives $E_{P} [(τ - ψ_{1} (P))^{2}] = E_{P} [(τ - τ (P))^{2}] \leq Q^{\otimes n} \in E_{n, d, ϵ} sup E_{Q} [(τ - τ (Q))^{2}],$ where the upper boundedness needed for the final supremum is supplied by the preceding envelope. Taking the supremum over $P^{\otimes n} \in D_{0}^{(n, d)} (ϵ)$ gives, for every measurable $τ$ , $P^{\otimes n} \in D_{0}^{(n, d)} (ϵ) sup E_{P} [(τ - ψ_{1} (P))^{2}] \leq P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ - τ (P))^{2}] .$ The same empty-class convention and nonnegativity show that every subclass worst-case risk is bounded below by $0$ . Taking the infimum over the common measurable estimator class therefore yields $ψ in f P^{\otimes n} \in D_{0}^{(n, d)} (ϵ) sup E_{P} [(ψ - ψ_{1} (P))^{2}] \leq R_{n, d, ϵ} .$

Combining the cited lower bound with this restriction comparison yields $a_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} \leq R_{n, d, ϵ}$ for every $n, d$ in the stated range.

∎

Lemma 3 [lem:near-randomization-linear-upper] (Near-randomization linear bound).

For $n \in N$ with $n > 0$ , $d \in N$ , a law $P$ on ${1, \dots, d} \times {0, 1}^{2}$ , and a sample law $μ_{n}$ , suppose that $μ_{n} \in E_{n, d, ϵ}$ in the sense of Definition 2. Thus $0 < ϵ \leq 1/2$ , $μ_{n} = P^{\otimes n}$ , and $P$ satisfies overlap at level $ϵ$ . Define $τ_{ctr} = \frac{1}{n} i = 1 \sum n 2 (2 A_{i} - 1) (Y_{i} - \frac{1}{2}) .$ Then, for $τ (P)$ as in Definition 5, $\int (τ_{ctr} (O_{1}, \dots, O_{n}) - τ (P))^{2} d μ_{n} \leq \frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2} .$

⊢ Lean

Proof of Lemma 3.

For one observation $z = (x, a, y)$ , define $W (z) = 2 (2 a - 1) (y - \frac{1}{2}),$ with $a, y \in {0, 1}$ . Then $τ_{ctr} = \frac{1}{n} i = 1 \sum n W (O_{i}), W (z)^{2} = 1 for every z .$

Writing $q_{ak y} = P (A = a, X = k, Y = y)$ , direct summation gives $E_{P} [W (O)] = k = 1 \sum d {q_{1 k 1} - q_{1 k 0} + q_{0 k 0} - q_{0 k 1}} .$

For the sums below, set $p_{k} = a = 0 \sum 1 y = 0 \sum 1 q_{ak y}, π_{k} = \frac{q _{1 k 0} + q _{1 k 1}}{p _{k}}, μ_{ak} = \frac{q _{ak 1}}{q _{ak 0} + q _{ak 1}},$ using ordinary real division, so a quotient with zero denominator is assigned the value zero. If $p_{k} > 0$ , overlap and $ϵ > 0$ make both arm masses positive, and the definitions give $q_{1 k 1} = μ_{1 k} π_{k} p_{k}, q_{1 k 0} = (1 - μ_{1 k}) π_{k} p_{k},$ and $q_{0 k 1} = μ_{0 k} (1 - π_{k}) p_{k}, q_{0 k 0} = (1 - μ_{0 k}) (1 - π_{k}) p_{k} .$ Hence $q_{1 k 1} - q_{1 k 0} + q_{0 k 0} - q_{0 k 1} = p_{k} (μ_{1 k} - μ_{0 k}) + 2 (π_{k} - \frac{1}{2}) p_{k} (μ_{1 k} + μ_{0 k} - 1) .$ If $p_{k} = 0$ , all four joint masses in category $k$ are zero; with the totalized definitions above, both weighted terms also vanish because they are multiplied by $p_{k}$ . Thus the same identity holds with zero contribution in that category.

By Definition 5, $τ (P) = \sum_{k = 1}^{d} ϕ (q_{k})$ , with $q_{k} = (q_{0 k 0}, q_{0 k 1}, q_{1 k 0}, q_{1 k 1})$ . For a category with $p_{k} = 0$ , the preceding zero-mass argument gives $q_{k} = 0$ , so the zero-cell branch in Definition 4 gives $ϕ (q_{k}) = 0 = p_{k} (μ_{1 k} - μ_{0 k})$ . For a category with $p_{k} > 0$ , overlap and $ϵ > 0$ give positive treated and control arm masses, and the nonzero-cell branch of Definition 4 gives $ϕ (q_{k}) = p_{k} {\frac{q _{1 k 1}}{q _{1 k 0} + q _{1 k 1}} - \frac{q _{0 k 1}}{q _{0 k 0} + q _{0 k 1}}} = p_{k} (μ_{1 k} - μ_{0 k}) .$ Summing over categories yields $τ (P) = k = 1 \sum d p_{k} (μ_{1 k} - μ_{0 k}) .$ Combining this identity with the preceding category identity gives the exact bias identity $E_{P} [W (O)] - τ (P) = k = 1 \sum d 2 (π_{k} - \frac{1}{2}) p_{k} (μ_{1 k} + μ_{0 k} - 1) .$

The class assumptions give $0 < ϵ \leq 1/2$ and, on every category with $p_{k} > 0$ , $ϵ \leq π_{k} \leq 1 - ϵ$ . The totalized outcome means satisfy $0 \leq μ_{ak} \leq 1$ for every category and arm. Hence, for every positive-mass category, $π_{k} - \frac{1}{2} \leq \frac{1}{2} - ϵ, ∣ μ_{1 k} + μ_{0 k} - 1∣ \leq 1,$ and therefore $2 (π_{k} - \frac{1}{2}) p_{k} (μ_{1 k} + μ_{0 k} - 1) \leq 2 (\frac{1}{2} - ϵ) p_{k} .$ For a zero-mass category, $p_{k} = 0$ makes both sides of this last bound equal to zero. Applying the triangle inequality to the bias identity and using $\sum_{k = 1}^{d} p_{k} = 1$ gives $∣ E_{P} [W (O)] - τ (P) ∣ \leq k = 1 \sum d 2 (\frac{1}{2} - ϵ) p_{k} = 2 (\frac{1}{2} - ϵ) .$

The sample law in the class is the product law, and $n > 0$ , so $E_{μ_{n}} [τ_{ctr}] = E_{P} [W (O)] .$ Moreover, independence gives $Var_{μ_{n}} (τ_{ctr}) = \frac{1}{n} Var_{P} (W (O)) \leq \frac{1}{n} E_{P} [W (O)^{2}] = \frac{1}{n} .$

Finally, the bias–variance identity gives $\int (τ_{ctr} - τ (P))^{2} d μ_{n} = Var_{μ_{n}} (τ_{ctr}) + (E_{μ_{n}} [τ_{ctr}] - τ (P))^{2} .$ Combining the preceding variance and bias bounds yields $\int (τ_{ctr} - τ (P))^{2} d μ_{n} \leq \frac{1}{n} + {2 (\frac{1}{2} - ϵ)}^{2} = \frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2} .$

∎

Lemma 4 [lem:one-category-bernoulli-lower] (One-category Bernoulli lower bound).

For any positive integers $n$ and $d$ , the minimax mean-squared-error risk $R_{n, d, ϵ}$ of Definition 6, evaluated at randomization $ϵ = 1/2$ , satisfies $\frac{1}{100 n} \leq R_{n, d, 1/2} .$

⊢ Lean

Proof of Lemma 4.

Since $d > 0$ , the category space is nonempty. Set $δ = \frac{2/5}{n} .$ Since $n > 0$ , $n \geq 1$ , and hence $δ \geq 0$ , $δ \leq 2/5$ , and $δ^{2} = \frac{4}{25 n} .$

Consider two laws $P_{0}$ and $P_{1}$ on the $d$ -category observation space. Under both laws, $X$ is uniform on the category space and $A ∣ X \sim Bernoulli (1/2)$ . Under $P_{0}$ , both treatment-arm outcome means equal $1/2$ . Under $P_{1}$ , the control outcome mean equals $1/2$ and the treated outcome mean equals $1/2 + δ$ . The bounds above give $0 \leq 1/2 + δ \leq 1$ , so these Bernoulli probabilities are valid. For each $P_{j}$ , membership of the product sample law in $E_{n, d, 1/2}$ is obtained from $0 < 1/2$ , $1/2 \leq 1/2$ , the defining identity of the iid product law $P_{j}^{\otimes n}$ , and the overlap fact that every positive-mass category has treatment probability $1/2$ . Thus the two product sample laws belong to $E_{n, d, 1/2}$ .

For these two laws, $τ (P_{0}) = 0, τ (P_{1}) = δ, ∣ τ (P_{1}) - τ (P_{0}) ∣ = δ .$

We next bound the total variation distance between the product laws. Write $p_{j, k a y} = P_{j} (X = k, A = a, Y = y)$ . The null law assigns positive mass to every singleton of the finite observation space, so $P_{1} ≪ P_{0}$ , and hence $P_{1}^{\otimes n} ≪ P_{0}^{\otimes n}$ . The finite chi-squared formula gives $1 + χ^{2} (P_{1} ∥ P_{0}) = k = 1 \sum d a, y \in {0, 1} \sum \frac{p _{1, k a y}^{2}}{p _{0, k a y}} .$ For a fixed category $k$ , the two control cells agree with the null and contribute $1/ (2 d)$ . The two treated cells contribute $\frac{{ d ^{- 1} ( 1/2 ) ( 1/2 - δ ) } ^{2}}{d ^{- 1} ( 1/2 ) ( 1/2 )} + \frac{{ d ^{- 1} ( 1/2 ) ( 1/2 + δ ) } ^{2}}{d ^{- 1} ( 1/2 ) ( 1/2 )} = \frac{1}{2 d} (1 + \frac{δ ^{2}}{( 1/2 ) ( 1 - 1/2 )}) .$ Summing over the $d$ categories yields $χ^{2} (P_{1} ∥ P_{0}) = \frac{( 1/2 ) δ ^{2}}{( 1/2 ) ( 1 - 1/2 )} = 2 δ^{2} .$

By tensorization of chi-squared divergence over the iid product law, $1 + χ^{2} (P_{1}^{\otimes n} ∥ P_{0}^{\otimes n}) = (1 + \frac{( 1/2 ) δ ^{2}}{( 1/2 ) ( 1 - 1/2 )})^{n} .$ The single-observation chi-squared value is nonnegative, so $(1 + x)^{n} \leq exp (n x)$ gives $1 + χ^{2} (P_{1}^{\otimes n} ∥ P_{0}^{\otimes n}) \leq exp (n \frac{( 1/2 ) δ ^{2}}{( 1/2 ) ( 1 - 1/2 )}) .$ Using $δ^{2} = 4/ (25 n)$ , $n \frac{( 1/2 ) δ ^{2}}{( 1/2 ) ( 1 - 1/2 )} = \frac{8}{25} \leq lo g 2,$ and therefore $χ^{2} (P_{1}^{\otimes n} ∥ P_{0}^{\otimes n}) \leq 1.$ The chi-squared-to-total-variation comparison on the finite product space, together with symmetry of total variation, yields $P_{0}^{\otimes n} - P_{1}^{\otimes n}_{TV} = P_{1}^{\otimes n} - P_{0}^{\otimes n}_{TV} \leq \frac{1}{2} χ^{2} (P_{1}^{\otimes n} ∥ P_{0}^{\otimes n}) \leq \frac{1}{2} .$

Now fix any measurable estimator $τ$ . With $s = δ /2$ , the separation above and the total-variation bound imply $j = 0, 1 max P_{j}^{\otimes n} (∣ τ - τ (P_{j}) ∣ \geq \frac{δ}{2}) \geq \frac{1}{4} .$

On each of the two laws, $(\frac{δ}{2})^{2} P_{j}^{\otimes n} (∣ τ - τ (P_{j}) ∣ \geq \frac{δ}{2}) \leq E_{P_{j}^{\otimes n}} [(τ - τ (P_{j}))^{2}] .$ Therefore $j = 0, 1 max E_{P_{j}^{\otimes n}} [(τ - τ (P_{j}))^{2}] \geq \frac{δ ^{2}}{16} = \frac{1}{100 n} .$

It remains to compare these two risks with the supremum in Definition 6. A point of that supremum is a single-observation law $P$ together with the class membership assertion $P^{\otimes n} \in E_{n, d, 1/2}$ . For any such $P$ , the overlap part of the membership assertion gives $∣ τ (P) ∣ \leq 1$ . Since the sample alphabet is finite, every sample point $ω$ satisfies $∣ τ (ω) ∣ \leq ω^{'} \in ({1, \dots, d} \times {0, 1}^{2})^{n} \sum ∣ τ (ω^{'}) ∣.$ Thus, under the product law generated by any such single-observation law $P$ , $E_{P^{\otimes n}} [(τ - τ (P))^{2}] \leq ω^{'} \in ({1, \dots, d} \times {0, 1}^{2})^{n} \sum ∣ τ (ω^{'}) ∣ + 1^{2} .$ This finite upper bound applies uniformly over the indexed family in the supremum of Definition 6. Since $P_{0}^{\otimes n}$ and $P_{1}^{\otimes n}$ are members of $E_{n, d, 1/2}$ , that supremum is an upper bound for the two displayed risks. Hence the worst-case risk of the fixed estimator $τ$ is at least $1/ (100 n)$ . The class of measurable estimators is nonempty, for instance by the constant-zero estimator, so taking the infimum over estimators in Definition 6 gives $\frac{1}{100 n} \leq R_{n, d, 1/2} .$

∎

Lemma 5 [lem:randomized-endpoint-minimax] (Randomization endpoint risk).

Let $n, d \in N$ satisfy $n > 0$ and $d > 0$ . For the minimax MSE risk $R_{n, d, ϵ}$ defined in Definition 6, exact randomization satisfies $\frac{1}{100 n} \leq R_{n, d, 1/2} \leq \frac{1}{n} .$

⊢ Lean

Proof of Lemma 5.

Lemma 4 gives the lower bound $\frac{1}{100 n} \leq R_{n, d, 1/2} .$

For the upper bound, take the centered endpoint estimator of Definition 10, $τ_{ctr} = \frac{1}{n} i = 1 \sum n 2 (2 A_{i} - 1) (Y_{i} - \frac{1}{2}) .$ It is measurable because the sample space is finite. To compare the infimum in Definition 6 with this estimator, interpret the displayed extrema there as real-valued order extrema and first check the bounded-below condition for the family of worst-case risks. Fix any measurable estimator. If $E_{n, d, 1/2}$ is empty, its worst-case risk is the supremum over an empty family and equals $0$ . If $E_{n, d, 1/2}$ is nonempty and the squared-loss integrals over the class are bounded above, any class member gives a nonnegative integral below the supremum, so the supremum is at least $0$ . If $E_{n, d, 1/2}$ is nonempty and those integrals are unbounded above, the same real-valued order convention evaluates the supremum at $0$ . Thus every worst-case risk in the infimum is bounded below by $0$ , and the infimum is no larger than the worst-case risk of $τ_{ctr}$ : $R_{n, d, 1/2} \leq μ_{n} = P^{\otimes n} \in E_{n, d, 1/2} sup \int (τ_{ctr} (O_{1}, \dots, O_{n}) - τ (P))^{2} d μ_{n} .$

It remains to bound this worst-case risk. If $E_{n, d, 1/2}$ is empty, the displayed supremum is $0$ , and $0 \leq 1/ n$ because $n > 0$ . Otherwise, for every member $μ_{n} = P^{\otimes n} \in E_{n, d, 1/2}$ , Lemma 3 applied with $ϵ = 1/2$ gives $\int (τ_{ctr} (O_{1}, \dots, O_{n}) - τ (P))^{2} d μ_{n} \leq \frac{1}{n} + 4 (\frac{1}{2} - \frac{1}{2})^{2} = \frac{1}{n} .$

Thus every term in the nonempty supremum is at most $1/ n$ , so $μ_{n} = P^{\otimes n} \in E_{n, d, 1/2} sup \int (τ_{ctr} (O_{1}, \dots, O_{n}) - τ (P))^{2} d μ_{n} \leq \frac{1}{n} .$ Therefore $R_{n, d, 1/2} \leq 1/ n$ . Combining this upper bound with the lower bound proves $\frac{1}{100 n} \leq R_{n, d, 1/2} \leq \frac{1}{n} .$

∎

Lemma 2 is the lower half of the matched fixed-interior rate in Theorem 1. Lemma 3 controls the centered estimator by a sampling term and a squared distance from the randomized endpoint. Combining the one-category lower bound in Lemma 4 with that centered upper bound at $ϵ = 1/2$ yields the endpoint bracket in Lemma 5.

The following selector lemma turns the hybrid fixed-interior envelope and the centered near-randomization envelope into a deterministic method choice.

Lemma 6 [lem:combined-upper-envelope] (Combined envelope selector).

Fix constants $ϵ, C_{ϵ}, ρ_{ϵ} \in R$ and $N_{ϵ} \in N$ . Assume:

(Interior overlap.) $0 < ϵ < 1/2$ .
(Positive constants.) $C_{ϵ} > 0$ and $ρ_{ϵ} > 0$ .
(Hybrid bound.) For every $n, d \in N$ , if $0 < n$ , $N_{ϵ} \leq n$ , and $d \leq ρ_{ϵ} n lo g n$ , then the hybrid estimator $τ_{n}^{hyb}$ of Definition 9 satisfies $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{n}^{hyb} - τ (P))^{2}] \leq C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$

Then for every $n, d \in N$ with $0 < n$ , $N_{ϵ} \leq n$ , and $d \leq ρ_{ϵ} n lo g n$ , set $K_{ϵ} = max {C_{ϵ}, 4} .$ Define the $C_{ϵ}, ϵ$ -dependent selected estimator $τ_{C_{ϵ}, ϵ}^{sel}$ to be $τ_{n}^{hyb}$ when $C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} \leq \frac{1}{n} + 4 (1/2 - ϵ)^{2}$ and to be $τ_{ctr}$ otherwise. This selected estimator satisfies $R_{n, d, ϵ} \leq P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{C_{ϵ}, ϵ}^{sel} - τ (P))^{2}] \leq K_{ϵ} [\frac{1}{n} + min {\frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}, (1/2 - ϵ)^{2}}],$ where $R_{n, d, ϵ}$ is the minimax risk of Definition 6.

⊢ Lean

Proof of Lemma 6.

Fix $n, d$ satisfying the displayed hypotheses, and set $K_{ϵ} = max {C_{ϵ}, 4} .$ The rate term used below is the real-valued expression $\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}},$ which is the displayed quantity in the hybrid-bound hypothesis and in the selector rule.

The centered estimator satisfies the uniform bound $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{ctr} - τ (P))^{2}] \leq \frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2} .$ Indeed, when the experiment class is inhabited, Lemma 3 applies to each product law in the class and the supremum preserves the same upper bound. When the class is empty, the real-valued indexed supremum over that empty index type is $0$ , and the same bound follows from nonnegativity of the displayed right-hand side.

We compare the two branches in the deterministic definition of $τ_{C_{ϵ}, ϵ}^{sel}$ . If $C_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}) \leq \frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2},$ then the selector returns $τ_{n}^{hyb}$ , and the assumed hybrid bound gives $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{C_{ϵ}, ϵ}^{sel} - τ (P))^{2}] \leq C_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}) = min {C_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}), \frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2}} .$ If the displayed inequality fails, then $\frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2} \leq C_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}),$ the selector returns $τ_{ctr}$ , and the centered bound gives the same conclusion with the second branch: $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{C_{ϵ}, ϵ}^{sel} - τ (P))^{2}] \leq min {C_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}), \frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2}} .$ Thus, in all cases, $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{C_{ϵ}, ϵ}^{sel} - τ (P))^{2}] \leq min {C_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}), \frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2}} .$

The sample space is finite, so the selected estimator is measurable. To compare this estimator with the infimum in $R_{n, d, ϵ}$ , first note that every measurable estimator has nonnegative worst-case mean squared error in the real-valued order used by the displayed extremum. If $E_{n, d, ϵ}$ is empty, the indexed supremum is $0$ . If $E_{n, d, ϵ}$ is inhabited and the family of mean squared errors over $E_{n, d, ϵ}$ is bounded above, then one nonnegative squared-loss integral lies below the supremum. If that family has no real upper bound, the real-valued supremum is the supremum of the empty set, hence $0$ . Hence the range over which the infimum defining $R_{n, d, ϵ}$ is taken is bounded below, and evaluating that infimum at the selected estimator yields $R_{n, d, ϵ} \leq P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{C_{ϵ}, ϵ}^{sel} - τ (P))^{2}] .$

It remains to simplify the deterministic envelope. Since $K_{ϵ} \geq C_{ϵ}$ , $K_{ϵ} \geq 4$ , and the scalar terms $1/ n$ , $d^{2} / (n^{2} (lo g n)^{2})$ , and $(1/2 - ϵ)^{2}$ are nonnegative, $C_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}) \leq K_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}})$ and $\frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2} \leq K_{ϵ} (\frac{1}{n} + (\frac{1}{2} - ϵ)^{2}) .$ If $\frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}} \leq (\frac{1}{2} - ϵ)^{2},$ then the first of these deterministic bounds gives $min {C_{ϵ} (\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}), \frac{1}{n} + 4 (\frac{1}{2} - ϵ)^{2}} \leq K_{ϵ} {\frac{1}{n} + min (\frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}, (\frac{1}{2} - ϵ)^{2})} .$ In the remaining case, $(\frac{1}{2} - ϵ)^{2} \leq \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}},$ the same conclusion follows from the second deterministic bound. Combining the selector bound with this deterministic comparison proves the stated upper envelope with $K_{ϵ} = max {C_{ϵ}, 4}$ .

∎

Lemma 6 formalizes the comparison made in Theorem 2. Once the fixed-interior hybrid bound is available, the selector chooses the smaller displayed certificate between the hybrid estimator and the centered estimator, producing an upper envelope with the minimum of the large-alphabet term and the near-randomization term.

The remaining statements establish the hybrid upper bound by separating calibration, polynomial approximation, factorial-moment estimation, and heavy-cell ratio control. The first calibration result collects deterministic inequalities implied by the numerical constants in Definition 9.

Lemma 7 [lem:calibration-consequences] (Calibration consequences).

Let $L = lo g (e n)$ , let $ℓ = lo g n$ , and let $m_{1} = ∣ I_{1} ∣$ be the second split size from Definition 7. Let $M = M (n)$ and $B = B (n)$ be the polynomial degree and light-cell approximation scale from Definition 9. If $n \geq N_{0}$ and $L \geq 240$ , then $0 < ℓ, ℓ \leq L, L \leq 2 ℓ, 0 < m_{1}, n \leq 2 m_{1}, M \leq L, B \leq \frac{8192 L}{n}, (6^{2 M})^{2} L^{6} \leq n .$

⊢ Lean

Proof of Lemma 7.

Because $n \geq N_{0}$ , the calibration cutoff gives $α_{0} L \geq 2, 4 M (n)^{2} \leq m_{1}, \frac{4 M ( n )}{m _{1}} \leq \frac{3 B ( n )}{4} .$ In particular $L > 0$ . The identity $L = lo g (e n) = 1 + lo g n = 1 + ℓ$ is valid for this positive $n$ . Since $L \geq 240$ , we have $ℓ = L - 1 > 0, ℓ \leq L, L = 1 + ℓ \leq 2 ℓ .$

The definition $M (n) = max {2, ⌊ α_{0} L ⌋}$ gives $M \geq 2$ . Hence $4 M^{2} \leq m_{1}$ implies $0 < m_{1}$ . For the deterministic second split, $m_{1} = n - ⌊ n /2 ⌋,$ and therefore $n \leq 2 m_{1}$ .

Since $α_{0} L \geq 2$ , the maximum in the definition of $M (n)$ is attained by the floor term: $M = ⌊ α_{0} L ⌋ .$ Using $α_{0} \leq 1$ and $L > 0$ , $M \leq α_{0} L \leq L .$

By the definition $B (n) = 4096 L / m_{1}$ and the bound $n \leq 2 m_{1}$ , $B = \frac{4096 L}{m _{1}} \leq \frac{8192 L}{n} .$

Finally we verify the calibrated growth inequality. Since $α_{0} \leq (32 lo g 6)^{- 1}$ and $M \leq α_{0} L$ , $4 M lo g 6 \leq \frac{L}{8}, so 6^{4 M} \leq exp (L /8) .$ Also $L \geq 240$ gives $lo g L = lo g 12 + lo g (L /12) \leq 11 + (L /12 - 1) \leq L /8,$ and hence $L^{6} = exp (6 lo g L) \leq exp (3 L /4) .$ Multiplying, $6^{4 M} L^{6} \leq exp (7 L /8) \leq exp (L - 1) = n .$ Since $(6^{2 M})^{2} = 6^{4 M}$ , this is exactly $(6^{2 M})^{2} L^{6} \leq n .$ The displayed conclusions follow.

∎

The Chebyshev branch is encoded through reciprocal coefficients and coefficient envelopes. These statements are the approximation-theoretic part of the construction, in the same spirit as polynomial methods for nonsmooth discrete-distribution functionals (Jiao et al., 2015; Wu et al., 2016; Han et al., 2020).

Definition 13 [synth_19] (Chebyshev reciprocal coefficients

g_{M, j}

For an integer $M \geq 2$ , we say $g_{M, j}$ , $0 \leq j \leq M - 2$ , are the Chebyshev reciprocal coefficients when they are the unique real coefficients satisfying $\frac{1 - \frac{1 - T _{M} ( 1 - 2 x )}{2 M ^{2} x}}{x} = j = 0 \sum M - 2 g_{M, j} x^{j},$ with the left-hand side interpreted by polynomial continuation at $x = 0$ , where $T_{M}$ is the degree- $M$ Chebyshev polynomial of the first kind.

Lemma 8 [lem:sparse-arm-expansion] (Sparse arm expansion).

For any sample $O_{1}, \dots, O_{n}$ , with each $O_{i} = (X_{i}, A_{i}, Y_{i}) \in {1, \dots, d} \times {0, 1}^{2}$ , and any category $k \in {1, \dots, d}$ , let $M = M (n)$ and $B = B (n)$ be the polynomial degree and light-cell approximation scale of Definition 9. For each arm $a \in {0, 1}$ , define $A_{a, k} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) m_{k, r^{a, c, j, t}},$ where $g_{M, j}$ are the coefficients of $G_{M}$ , $r^{a, c, j, t}$ is the four-cell exponent vector determined by $u^{r^{a, c, j, t}} = u_{c} u_{a 1} u_{a 0}^{t} u_{a 1}^{j - t}$ , and $m_{k, r^{a, c, j, t}}$ is the corresponding normalized factorial-moment monomial computed from the sample. Then the factorial-moment polynomial estimate for category $k$ satisfies $P_{k} = A_{1, k} - A_{0, k} .$

⊢ Lean

Proof of Lemma 8.

Fix the sample and the category $k$ , and abbreviate $M = M (n)$ and $B = B (n)$ , using the split and calibration notation of Definitions 7 and 9. For a cell $c \in {0, 1}^{2}$ , let $e_{c}$ be the four-cell unit multi-index. For each arm $a$ , degree index $j$ , and binomial index $t$ , the sparse index used in the factorial lift is $r^{a, c, j, t} = e_{c} + e_{(a, 1)} + t e_{(a, 0)} + (j - t) e_{(a, 1)} .$ Equivalently, its associated four-cell monomial is $u_{c} u_{a 1} u_{a 0}^{t} u_{a 1}^{j - t}$ . Let $γ_{j, t} = B^{- 1} g_{M, j} B^{- j} (t j) .$ The normalized factorial-moment monomial $m_{k, r}$ is the one in Definition 8. Thus the sparse arm contribution for arm $a$ is precisely $A_{a, k} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum γ_{j, t} m_{k, r^{a, c, j, t}} .$

The sparse factorial-polynomial contribution for category $k$ is defined as the treated sparse arm minus the control sparse arm. Substituting the preceding display for $a = 1$ and $a = 0$ gives $P_{k} = A_{1, k} - A_{0, k} .$

∎

Lemma 9 [lem:factorial-moment-mean] (Factorial mean identity).

Let $P$ be a probability law for one observation $O = (X, A, Y)$ with $X \in {1, \dots, d}$ and $A, Y \in {0, 1}$ , and let $k \in {1, \dots, d}$ . Let $P^{\otimes \infty}$ denote the ambient infinite iid product law generated by $P$ . Suppose that $n \geq N_{0}$ , where $N_{0}$ is the calibration cutoff in Definition 9. For $q_{k} = (P (X = k, A = a, Y = y))_{a, y \in {0, 1}},$ the factorial-moment polynomial estimate $P_{k}$ from Definition 9, evaluated on the first $n$ coordinates under $P^{\otimes \infty}$ , satisfies $\int P_{k} (O_{1}, \dots, O_{n}) d P^{\otimes \infty} = P_{M (n), B (n)} (q_{k}) .$

⊢ Lean

Proof of Lemma 9.

Write $μ_{\infty} = P^{\otimes \infty}, M = M (n), B = B (n), m_{1} = ∣ I_{1} ∣,$ where $μ_{\infty}$ is the ambient iid product law. For a cell $c = (a, y) \in {0, 1}^{2}$ , write $q_{c} = q_{ak y} = P (X = k, A = a, Y = y), q_{k} = (q_{c})_{c \in {0, 1}^{2}} .$ Since $n \geq N_{0}$ , the calibration in Definition 9 gives $4 M^{2} \leq m_{1} .$ Because $M \geq 2$ , this implies $M \leq m_{1}$ .

For any multi-index $r = (r_{c})_{c}$ with $∣ r ∣ \leq m_{1}$ , the normalized factorial monomial satisfies $\int m_{k, r} d μ_{\infty} = c \in {0, 1}^{2} \prod q_{c}^{r_{c}} .$ Indeed, on the estimation split $I_{1}$ , define $L_{i} = {(A_{i}, Y_{i}), ⋆, X_{i} = k, X_{i} \neq = k .$ The variables $L_{i}$ , $i \in I_{1}$ , are iid, and $P (L_{i} = c) = q_{c}$ . Expanding $\prod_{c} (N_{k c}^{(1)})_{r_{c}}$ counts ordered injective assignments of $∣ r ∣$ requested labels to distinct indices in $I_{1}$ . There are $(m_{1})_{∣ r ∣}$ such assignments, each has probability $\prod_{c} q_{c}^{r_{c}}$ , and division by $(m_{1})_{∣ r ∣}$ gives the displayed identity.

For the sparse arms in Lemma 8, write $A_{a, k} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) m_{k, r^{a, c, j, t}} .$ That lemma gives the pointwise identity $P_{k} = A_{1, k} - A_{0, k} .$

For $a \in {0, 1}$ , $j \in {0, \dots, M - 2}$ , $t \in {0, \dots, j}$ , and $c \in {0, 1}^{2}$ , the sparse exponent $r^{a, c, j, t} = e_{c} + e_{a 1} + t e_{a 0} + (j - t) e_{a 1}$ has total degree $∣ r^{a, c, j, t} ∣ = j + 2 \leq M \leq m_{1} .$

Therefore the factorial-monomial identity applies in every summand of each sparse arm. Finite-sum linearity gives, for each $a \in {0, 1}$ , $\int A_{a, k} d μ_{\infty} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) q_{k}^{r^{a, c, j, t}} .$

By the definition of $r^{a, c, j, t}$ , $q_{k}^{r^{a, c, j, t}} = q_{c} q_{a 1} q_{a 0}^{t} q_{a 1}^{j - t} .$ Thus, for each fixed $a$ and $j$ , $t = 0 \sum j c \in {0, 1}^{2} \sum (t j) q_{k}^{r^{a, c, j, t}} = c \in {0, 1}^{2} \sum q_{c} q_{a 1} (q_{a 0} + q_{a 1})^{j},$ by the binomial theorem.

Consequently, for each $a \in {0, 1}$ , $\int A_{a, k} d μ_{\infty} = \frac{s ( q _{k} ) t _{a} ( q _{k} )}{B} j = 0 \sum M - 2 g_{M, j} (\frac{s _{a} ( q _{k} )}{B})^{j} = \frac{s ( q _{k} ) t _{a} ( q _{k} )}{B} G_{M} (\frac{s _{a} ( q _{k} )}{B}),$ where $t_{1} (q_{k}) = q_{11}$ and $t_{0} (q_{k}) = q_{01}$ .

Subtracting the two arm identities and using Lemma 8, $\int P_{k} d μ_{\infty} = \frac{s ( q _{k} ) t _{1} ( q _{k} )}{B} G_{M} (\frac{s _{1} ( q _{k} )}{B}) - \frac{s ( q _{k} ) t _{0} ( q _{k} )}{B} G_{M} (\frac{s _{0} ( q _{k} )}{B}) = P_{M, B} (q_{k}),$ where the final equality is the definition of the light-cell polynomial in Definition 9. Substituting $M = M (n)$ and $B = B (n)$ gives the claimed identity.

∎

Lemma 10 [lem:chebyshev-reciprocal-certificate] (Polynomial approximation certificate).

Fix a degree $M \in N$ , a real scale $B$ , the overlap level $ϵ$ , and a four-cell vector $u$ . Assume:

(Degree.) $M \geq 1$ .
(Overlap level.) $ϵ > 0$ .
(Cone membership.) $u \in C_{ϵ}$ , where $C_{ϵ}$ is the overlap-restricted cone in Definition 3.
(Mass bound.) $s (u) \leq B$ .

For the light-cell polynomial $P_{M, B}$ from Definition 9 and the homogeneous cell contribution $ϕ$ from Definition 4, $∣ P_{M, B} (u) - ϕ (u) ∣ \leq \frac{2 B}{ϵ M ^{2}} .$

⊢ Lean

Proof of Lemma 10.

Let $G_{M} (x) = \sum_{j = 0}^{M - 2} g_{M, j} x^{j}$ . The shifted-Chebyshev expansion gives, for every real $x$ , $T_{M} (1 - 2 x) = 1 - 2 M^{2} x + 2 M^{2} x^{2} G_{M} (x) .$ If $0 \leq x \leq 1$ , then $∣ T_{M} (1 - 2 x) ∣ \leq 1$ , and the displayed identity implies $x ∣1 - x G_{M} (x) ∣ \leq \frac{1}{M ^{2}} .$

First consider $u = 0$ . Then $s (u) = s_{0} (u) = s_{1} (u) = u_{01} = u_{11} = 0$ , so both $P_{M, B} (u)$ and $ϕ (u)$ equal $0$ . Since $s (u) \leq B$ , this case also gives $B \geq 0$ , and hence $∣ P_{M, B} (u) - ϕ (u) ∣ = 0 \leq \frac{2 B}{ϵ M ^{2}} .$

Now suppose $u \neq = 0$ . Nonnegativity of the four coordinates gives $s (u) \geq 0$ , and $u \neq = 0$ gives $s (u) > 0$ . Since $s (u) \leq B$ , we have $B > 0$ . The overlap inequalities give $s_{1} (u) \geq ϵs (u) > 0, s_{0} (u) = s (u) - s_{1} (u) \geq ϵs (u) > 0.$ Also $s_{a} (u) \leq s (u) \leq B$ , so $x_{a} := \frac{s _{a} ( u )}{B} \in [0, 1], a \in {0, 1} .$

For each arm $a$ , the preceding Chebyshev certificate gives $1 - \frac{s _{a} ( u )}{B} G_{M} (\frac{s _{a} ( u )}{B}) \leq \frac{B}{s _{a} ( u ) M ^{2}} .$ Using $0 \leq u_{a 1} \leq s_{a} (u)$ , this yields $B^{- 1} s (u) u_{a 1} G_{M} (\frac{s _{a} ( u )}{B}) - s (u) \frac{u _{a 1}}{s _{a} ( u )} \leq \frac{B}{ϵ M ^{2}} .$ Indeed, the left-hand side equals $\frac{s ( u ) u _{a 1}}{s _{a} ( u )} 1 - \frac{s _{a} ( u )}{B} G_{M} (\frac{s _{a} ( u )}{B}),$ and the factor $s (u) / s_{a} (u)$ is at most $1/ ϵ$ .

Finally, $P_{M, B} (u) - ϕ (u) = [B^{- 1} s (u) u_{11} G_{M} (\frac{s _{1} ( u )}{B}) - s (u) \frac{u _{11}}{s _{1} ( u )}] - [B^{- 1} s (u) u_{01} G_{M} (\frac{s _{0} ( u )}{B}) - s (u) \frac{u _{01}}{s _{0} ( u )}] .$ The triangle inequality and the two arm bounds give $∣ P_{M, B} (u) - ϕ (u) ∣ \leq \frac{B}{ϵ M ^{2}} + \frac{B}{ϵ M ^{2}} = \frac{2 B}{ϵ M ^{2}} .$

∎

Lemma 8 rewrites the light-cell statistic as treated and control sparse-arm pieces. Lemma 9 then identifies the mean of the factorial-moment statistic with the polynomial target $P_{M (n), B (n)} (q_{k})$ . Lemma 10 supplies the light-cell approximation error on the overlap cone when the cell mass lies below the approximation scale.

Heavy categories are controlled by ratio residuals and missing-arm probabilities. The next two bounds apply to deterministic category sets, which allows them to be conditioned on the pilot split before summing over the selected heavy categories.

Lemma 11 [lem:heavy-residual-bound] (Fixed-set residual variance).

Let $P$ be a probability law on the finite observed-data alphabet ${1, \dots, d} \times {0, 1}^{2}$ , let $I$ be a finite index set, and write $m = ∣ I ∣$ . For observations $O_{i} = (X_{i}, A_{i}, Y_{i})$ , $i \in I$ , drawn independently from $P$ , let $H \subseteq {1, \dots, d}$ be deterministic and fix $a \in {0, 1}$ .

Assume:

(Overlap.) The overlap level $ϵ$ satisfies $ϵ > 0$ , and for every category $k$ with $p_{k} = P (X = k) > 0$ , $ϵ \leq π_{k} \leq 1 - ϵ .$
(Positive mass on $H$ .) For every $k \in H$ , $p_{k} > 0$ .

With counts computed from the sample, $R_{a} (H) = k \in H \sum N_{k} \frac{1 { N _{ak} > 0 }}{N _{ak}} {N_{ak 1} - μ_{ak} N_{ak}} .$ Then $E_{P} [R_{a} (H)^{2}] \leq \frac{2 m}{ϵ} k \in H \sum p_{k} .$

⊢ Lean

Proof of Lemma 11.

For an observation array $z = (O_{i})_{i \in I}$ , with $O_{i} = (X_{i}, A_{i}, Y_{i})$ , write $N_{k} (z) = i \in I \sum 1 {X_{i} = k}, N_{ak} (z) = i \in I \sum 1 {X_{i} = k, A_{i} = a},$ and $N_{ak 1} (z) = i \in I \sum 1 {X_{i} = k, A_{i} = a, Y_{i} = 1} .$ Let $m = ∣ I ∣$ , and put $C_{ak} (z) = N_{k} (z) \frac{1 { N _{ak} ( z ) > 0 }}{N _{ak} ( z )}, ξ_{ak, i} (z) = 1 {X_{i} = k, A_{i} = a} {Y_{i} - μ_{ak}} .$ With the convention that the displayed ratio is zero when $N_{ak} (z) = 0$ , the residual can be written as $R_{a} (H) = k \in H \sum C_{ak} (z) i \in I \sum ξ_{ak, i} (z),$ because $\sum_{i} ξ_{ak, i} = N_{ak 1} (z) - μ_{ak} N_{ak} (z)$ .

Expand the square as a double sum over pairs $(k, i)$ and $(l, j)$ . If $i \neq = j$ , then the factor $C_{ak} (z) C_{a l} (z) ξ_{a l, j} (z)$ is unchanged when only the outcome coordinate of observation $i$ is replaced; conditioning on all other coordinates and using the centered arm-category residual gives integral zero. If $i = j$ and $k \neq = l$ , then the two category indicators cannot both hold for the same observation, so the product of residuals is identically zero. Hence only the diagonal terms remain: $E_{P^{\otimes I}} [R_{a} (H)^{2}] = k \in H \sum i \in I \sum E_{P^{\otimes I}} [C_{ak} (z)^{2} ξ_{ak, i} (z)^{2}] .$

For each fixed $k$ and $i$ , the multiplier $C_{ak} (z)^{2}$ is nonnegative and depends only on the category and treatment coordinates of the array. The one-coordinate conditional Bernoulli variance bound gives $E_{P^{\otimes I}} [C_{ak} (z)^{2} ξ_{ak, i} (z)^{2}] \leq E_{P^{\otimes I}} [C_{ak} (z)^{2} 1 {X_{i} = k, A_{i} = a}] .$ Therefore, for each fixed $k$ , $i \in I \sum E_{P^{\otimes I}} [C_{ak} (z)^{2} ξ_{ak, i} (z)^{2}] \leq E_{P^{\otimes I}} [i \in I \sum C_{ak} (z)^{2} 1 {X_{i} = k, A_{i} = a}] = E_{P^{\otimes I}} [N_{k} (z)^{2} \frac{1 { N _{ak} ( z ) > 0 }}{N _{ak} ( z )}] .$

Let $ρ_{ak} = P (A = a ∣ X = k)$ , so $ρ_{1 k} = π_{k}$ and $ρ_{0 k} = 1 - π_{k}$ . For $k \in H$ , the positive-mass hypothesis gives $p_{k} > 0$ . Overlap gives $ρ_{ak} \geq ϵ$ , and $ρ_{ak} \leq 1$ because it is an arm probability. Put $E_{k} = {X = k}, R_{ak} = {X = k, A = a} .$ Then $R_{ak} \subset E_{k}$ , and under the one-observation law $P (E_{k}) = p_{k}, P (R_{ak}) = p_{k} ρ_{ak}, P (E_{k} ∖ R_{ak}) = p_{k} (1 - ρ_{ak}), P (E_{k}^{c}) = 1 - p_{k} .$ Partition the product sample space according to $U = {i : O_{i} \in E_{k}}, V = {i : O_{i} \in R_{ak}} .$ The nested relation forces $V \subset U$ . For fixed $U, V$ with $V \subset U$ , independence gives the product probability $(p_{k} ρ_{ak})^{∣ V ∣} {p_{k} (1 - ρ_{ak})}^{∣ U ∣ - ∣ V ∣} (1 - p_{k})^{m - ∣ U ∣},$ and the integrand equals $∣ U ∣^{2} \frac{1 { ∣ V ∣ > 0 }}{∣ V ∣} .$ Summing over all such pairs and then collecting first by $t = ∣ U ∣$ and then by $s = ∣ V ∣$ gives $E_{P^{\otimes I}} [N_{k}^{2} \frac{1 { N _{ak} > 0 }}{N _{ak}}] = t = 0 \sum m (t m) p_{k}^{t} (1 - p_{k})^{m - t} t^{2} s = 0 \sum t (s t) ρ_{ak}^{s} (1 - ρ_{ak})^{t - s} \frac{1 { s > 0 }}{s} .$

It remains to bound the inner reciprocal-count sum. For every integer $s \geq 0$ , with the left side interpreted as zero at $s = 0$ , $\frac{1 { s > 0 }}{s} \leq \frac{2}{s + 1} .$ Since $0 < ρ_{ak} \leq 1$ , the binomial weights are nonnegative, and therefore $s = 0 \sum t (s t) ρ_{ak}^{s} (1 - ρ_{ak})^{t - s} \frac{1 { s > 0 }}{s} \leq 2 s = 0 \sum t (s t) ρ_{ak}^{s} (1 - ρ_{ak})^{t - s} \frac{1}{s + 1} = \frac{2}{( t + 1 ) ρ _{ak}} s = 0 \sum t (s + 1 t + 1) ρ_{ak}^{s + 1} (1 - ρ_{ak})^{t - s} = \frac{2 { 1 - ( 1 - ρ _{ak} ) ^{t + 1} }}{( t + 1 ) ρ _{ak}} \leq \frac{2}{( t + 1 ) ρ _{ak}} .$ Here the middle equality uses $(s t) / (s + 1) = (s + 1 t + 1) / (t + 1)$ , and the final inequality uses $(1 - ρ_{ak})^{t + 1} \geq 0$ . Hence, using $t^{2} / (t + 1) \leq t$ and the binomial first moment, $E_{P^{\otimes I}} [N_{k}^{2} \frac{1 { N _{ak} > 0 }}{N _{ak}}] \leq t = 0 \sum m (t m) p_{k}^{t} (1 - p_{k})^{m - t} \frac{2 t}{ρ _{ak}} = \frac{2 m p _{k}}{ρ _{ak}} \leq \frac{2 m p _{k}}{ϵ} .$

Summing over $k \in H$ gives $E_{P^{\otimes I}} [R_{a} (H)^{2}] \leq k \in H \sum \frac{2 m p _{k}}{ϵ} = \frac{2 m}{ϵ} k \in H \sum p_{k} .$

∎

Lemma 12 [lem:missing-arm-envelope] (Missing-arm second moment).

Let $J$ be a finite sample-index set and write $m = ∣ J ∣$ . For a probability law $P$ on ${1, \dots, d} \times {0, 1}^{2}$ , a deterministic category set $H \subseteq {1, \dots, d}$ , and an arm $a \in {0, 1}$ , define $Z_{ak} = N_{k} 1 {N_{ak} = 0},$ where $N_{k}$ is the number of observations in category $k$ and $N_{ak}$ is the number of observations in category $k$ and arm $a$ in the $J$ -indexed iid sample from $P$ .

Assume:

(Sample size.) $m \geq 3$ .
(Overlap.) The overlap level $ϵ$ satisfies $ϵ > 0$ , and for every category $k$ with $p_{k} = P (X = k) > 0$ , $ϵ \leq P (A = 1 ∣ X = k) \leq 1 - ϵ .$
(Mass floor.) $B > 0$ , and $p_{k} \geq B$ for every $k \in H$ .

Then $E_{P^{\otimes J}} (k \in H \sum Z_{ak})^{2} \leq m + m^{2} [\frac{∣ H ∣}{{ ( ( m - 2 ) /2 ) ϵ } ^{2} B}]^{2} .$

⊢ Lean

Proof of Lemma 12.

For a sample $z = (O_{1}, \dots, O_{m})$ , let $Z_{ak} (z)$ be the missing-arm category count $Z_{ak} (z) = {# {i : X_{i} = k}, 0, # {i : X_{i} = k, A_{i} = a} = 0, otherwise .$ Thus $\sum_{k \in H} Z_{ak} (z)$ is the fixed missing-arm count over $H$ for arm $a$ . Let $ρ_{ak} = P (A = a ∣ X = k), u = \frac{m - 2}{2} ϵ, f_{k} = p_{k} exp (- u p_{k}) .$ The assumptions $m \geq 3$ , $ϵ > 0$ , and $B > 0$ give $u > 0$ , and the mass floor gives $p_{k} \geq B > 0$ for every $k \in H$ . Hence $ρ_{ak}$ is the ordinary conditional arm probability on $H$ , with $0 \leq ρ_{ak} \leq 1$ , and overlap gives $ϵ \leq ρ_{ak}$ , equivalently $ϵ p_{k} \leq p_{k} ρ_{ak}$ .

We first record the exact second moment. For a fixed category $k$ , expand $Z_{ak}^{2}$ by separating one selected index from two ordered distinct selected indices. The one-index event requires $O_{i}$ to lie in category $k$ outside arm $a$ , while the whole sample avoids the arm- $a$ subcell in category $k$ . Its probability is $p_{k} (1 - ρ_{ak}) (1 - p_{k} ρ_{ak})^{m - 1} .$ For an ordered pair $i \neq = j$ , the corresponding two-index event has probability ${p_{k} (1 - ρ_{ak})}^{2} (1 - p_{k} ρ_{ak})^{m - 2} .$ Summing over the $m$ one-index choices and the $(m)_{2} = m (m - 1)$ ordered pairs gives the diagonal contribution $m p_{k} (1 - ρ_{ak}) (1 - p_{k} ρ_{ak})^{m - 1} + (m)_{2} {p_{k} (1 - ρ_{ak})}^{2} (1 - p_{k} ρ_{ak})^{m - 2} .$ For distinct $k, l$ , the same-index part in $Z_{ak} Z_{a l}$ is zero because the category events are disjoint. The remaining ordered-pair event places one selected observation in category $k$ outside arm $a$ , the other in category $l$ outside arm $a$ , and the whole sample outside the two forbidden arm- $a$ subcells. Since those forbidden subcells are disjoint, its probability is $p_{k} (1 - ρ_{ak}) p_{l} (1 - ρ_{a l}) (1 - p_{k} ρ_{ak} - p_{l} ρ_{a l})^{m - 2} .$ Therefore $\int (k \in H \sum Z_{ak} (z))^{2} d P^{\otimes m} (z) = k \in H \sum [m p_{k} (1 - ρ_{ak}) (1 - p_{k} ρ_{ak})^{m - 1} + (m)_{2} {p_{k} (1 - ρ_{ak})}^{2} (1 - p_{k} ρ_{ak})^{m - 2}] + k \in H \sum l \in H ∖ {k} \sum (m)_{2} p_{k} (1 - ρ_{ak}) p_{l} (1 - ρ_{a l}) (1 - p_{k} ρ_{ak} - p_{l} ρ_{a l})^{m - 2} .$

For the diagonal terms, $0 \leq p_{k} \leq 1$ , $0 \leq ρ_{ak} \leq 1$ , $(m)_{2} \leq m^{2}$ , and $ϵ p_{k} \leq p_{k} ρ_{ak}$ imply $m p_{k} (1 - ρ_{ak}) (1 - p_{k} ρ_{ak})^{m - 1} + (m)_{2} {p_{k} (1 - ρ_{ak})}^{2} (1 - p_{k} ρ_{ak})^{m - 2} \leq m p_{k} + m^{2} f_{k}^{2} .$ Indeed, the first summand is at most $m p_{k}$ . For the second summand, $(1 - p_{k} ρ_{ak})^{m - 2} \leq exp {- (m - 2) ϵ p_{k}} = exp (- u p_{k})^{2},$ and $p_{k} (1 - ρ_{ak}) \leq p_{k}$ .

For $k \neq = l$ , disjointness of the two category events gives $p_{k} + p_{l} \leq 1$ , and hence $p_{k} ρ_{ak} + p_{l} ρ_{a l} \leq 1$ . Together with the two overlap inequalities, $(1 - p_{k} ρ_{ak} - p_{l} ρ_{a l})^{m - 2} \leq exp {- (m - 2) (p_{k} ρ_{ak} + p_{l} ρ_{a l})} \leq exp {- (m - 2) ϵ (p_{k} + p_{l})} \leq exp (- u p_{k}) exp (- u p_{l}) .$ Using also $p_{k} (1 - ρ_{ak}) \leq p_{k}$ , $p_{l} (1 - ρ_{a l}) \leq p_{l}$ , and $(m)_{2} \leq m^{2}$ , we obtain $(m)_{2} p_{k} (1 - ρ_{ak}) p_{l} (1 - ρ_{a l}) (1 - p_{k} ρ_{ak} - p_{l} ρ_{a l})^{m - 2} \leq m^{2} f_{k} f_{l} .$

Substituting the diagonal and cross envelopes into the exact expansion and collecting the square of the exponential sum gives $\int (k \in H \sum Z_{ak} (z))^{2} d P^{\otimes m} (z) \leq m k \in H \sum p_{k} + m^{2} (k \in H \sum f_{k})^{2} .$ The category masses over $H$ sum to at most one, so the first term is at most $m$ .

It remains to bound the exponential sum. For $t > 0$ , $exp (- t) \leq t^{- 2} .$ Applying this with $t = u p_{k}$ , and using $p_{k} \geq B$ , gives $p_{k} exp (- u p_{k}) \leq \frac{1}{u ^{2} p _{k}} \leq \frac{1}{u ^{2} B} .$ Therefore $k \in H \sum f_{k} \leq \frac{∣ H ∣}{u ^{2} B} .$

Since each $f_{k} \geq 0$ , combining the last two bounds and substituting $u = ((m - 2) /2) ϵ$ yields $\int (k \in H \sum Z_{ak} (z))^{2} d P^{\otimes m} (z) \leq m + m^{2} \frac{∣ H ∣}{( ( \frac{m - 2}{2} ϵ ) ^{2} B )}^{2} .$

∎

Lemma 11 gives the variance scale for centered ratio noise over a fixed heavy set. Lemma 12 controls the contribution from categories whose empirical denominator in an arm is zero; the mass floor supplied by the pilot sandwich makes this event sufficiently rare in aggregate.

For light categories, the factorial-moment analysis uses product-moment and coefficient-sum controls. These statements quantify how multinomial dependence across cells and categories enters the variance calculation.

Lemma 13 [lem:factorial-product-moment] (Factorial product moment).

Fix $n, d \in N$ , $P \in Prob ({1, \dots, d} \times {0, 1}^{2})$ , a category $k \in {1, \dots, d}$ , and four-cell multi-indices $r, s$ . Using the split counts and split size in Definition 7, let $m_{k, r} = \frac{\prod _{(a, y)} ( N _{ak y}^{(1)} ) _{r_{a y}}}{( m _{1} ) _{∣ r ∣}},$ where $(z)_{t}$ denotes the falling factorial and $∣ r ∣ = \sum_{(a, y)} r_{a y}$ . Let $q_{ak y}$ denote the treatment–outcome cell mass in category $k$ , as in Definition 5. Assume:

(Nonempty estimation split.) $m_{1} > 0$ .
(Degree ordering.) $∣ r ∣ \leq ∣ s ∣$ .
(Split-size condition.) $4∣ s ∣^{2} \leq m_{1}$ .

Then, under the iid product law generated by $P$ , $E_{P^{\otimes n}} [m_{k, r} m_{k, s}] \leq e (a, y) \prod q_{ak y}^{r_{a y}} (a, y) \prod (q_{ak y} + \frac{∣ s ∣}{m _{1}})^{s_{a y}} .$

⊢ Lean

Proof of Lemma 13.

Let $C = {0, 1} \times {0, 1}$ , let $m = m_{1}$ , and write $q_{a y} = q_{ak y}, r_{a y} = r (a, y), s_{a y} = s (a, y), ∣ r ∣ = (a, y) \in C \sum r_{a y}, ∣ s ∣ = (a, y) \in C \sum s_{a y} .$ Adjoin one extra label $\emptyset$ for observations outside category $k$ . For the $j$ -th observation in the estimation split define $Z_{j} = {(a, y), \emptyset, (X_{j}, A_{j}, Y_{j}) = (k, a, y), X_{j} \neq = k, α_{a y} = q_{a y}, α_{\emptyset} = 1 - (a, y) \in C \sum q_{a y} .$ The variables $Z_{1}, \dots, Z_{m}$ are iid on $C \cup {\emptyset}$ with masses $α$ . Extend $r, s$ by setting $r_{\emptyset} = s_{\emptyset} = 0$ . If $N_{b} = # {j : Z_{j} = b}$ , then $m_{k, r} = \frac{\prod _{b \in C \cup {\emptyset}} ( N _{b} ) _{r_{b}}}{( m ) _{∣ r ∣}}, m_{k, s} = \frac{\prod _{b \in C \cup {\emptyset}} ( N _{b} ) _{s_{b}}}{( m ) _{∣ s ∣}} .$ This is just the split-count notation of Definition 7, with the outside-category exponent equal to zero.

For an overlap choice $H = (H_{b})_{b \in C \cup {\emptyset}}, 0 \leq H_{b} \leq min {r_{b}, s_{b}},$ set $∣ H ∣ = b \sum H_{b}, t_{b} (H) = r_{b} + s_{b} - H_{b}, A_{H} = b \prod (H _{b} r _{b}) (H _{b} s _{b}) H_{b}! .$ The cellwise falling-factorial product identity gives $b \prod (N_{b})_{r_{b}} b \prod (N_{b})_{s_{b}} = H \sum A_{H} b \prod (N_{b})_{t_{b} (H)} .$

Taking expectations and using the factorial moment formula for multinomial counts, $E [m_{k, r} m_{k, s}] = H \sum A_{H} \frac{( m ) _{∣ r ∣ + ∣ s ∣ - ∣ H ∣}}{( m ) _{∣ r ∣} ( m ) _{∣ s ∣}} b \prod α_{b}^{r_{b} + s_{b} - H_{b}} .$

The normalization ratio satisfies, for every such $H$ , $\frac{( m ) _{∣ r ∣ + ∣ s ∣ - ∣ H ∣}}{( m ) _{∣ r ∣} ( m ) _{∣ s ∣}} \leq \frac{e}{m ^{∣ H ∣}} .$ Indeed, if $∣ s ∣ = 0$ then also $∣ r ∣ = 0$ , and the bound is immediate. Otherwise put $u = m - ∣ s ∣$ . The assumptions $4∣ s ∣^{2} \leq m$ and $∣ r ∣ \leq ∣ s ∣$ imply $u > 0$ and $2∣ s ∣^{2} \leq u$ . Also $(m)_{∣ r ∣ + ∣ s ∣ - ∣ H ∣} \leq m^{∣ r ∣ + ∣ s ∣ - ∣ H ∣}, (m)_{∣ r ∣} \geq u^{∣ r ∣}, (m)_{∣ s ∣} \geq u^{∣ s ∣} .$ Hence the ratio is at most $\frac{m ^{∣ r ∣ + ∣ s ∣ - ∣ H ∣}}{u ^{∣ r ∣ + ∣ s ∣}} = \frac{( m / u ) ^{∣ r ∣ + ∣ s ∣}}{m ^{∣ H ∣}} .$ Since $m / u = 1 + ∣ s ∣/ u$ , $(∣ r ∣ + ∣ s ∣) lo g (m / u) \leq (∣ r ∣ + ∣ s ∣) \frac{∣ s ∣}{u} \leq 1,$ and therefore $(m / u)^{∣ r ∣ + ∣ s ∣} \leq e$ .

Because all masses $α_{b}$ are nonnegative, $E [m_{k, r} m_{k, s}] \leq e H \sum A_{H} m^{- ∣ H ∣} b \prod α_{b}^{r_{b} + s_{b} - H_{b}} .$

The remaining overlap sum factors by coordinates: $H \sum A_{H} m^{- ∣ H ∣} b \prod α_{b}^{r_{b} + s_{b} - H_{b}} = b \prod h = 0 \sum m i n (r_{b}, s_{b}) (h r _{b}) (h s _{b}) h! m^{- h} α_{b}^{r_{b} + s_{b} - h} .$

For each $b$ and each $0 \leq h \leq min {r_{b}, s_{b}}$ , one has $h \leq s_{b}$ and $(h r _{b}) h! = (r_{b})_{h} \leq r_{b}^{h} \leq ∣ r ∣^{h} \leq ∣ s ∣^{h} .$ The assumption $m_{1} > 0$ gives $m > 0$ , and $α_{b} \geq 0$ . After rewriting $α_{b}^{r_{b} + s_{b} - h} = α_{b}^{r_{b}} α_{b}^{s_{b} - h}$ , the preceding coefficient bound gives $(h r _{b}) (h s _{b}) h! m^{- h} α_{b}^{r_{b} + s_{b} - h} \leq α_{b}^{r_{b}} (h s _{b}) (\frac{∣ s ∣}{m})^{h} α_{b}^{s_{b} - h} .$ The right-hand summands are nonnegative for every $0 \leq h \leq s_{b}$ , so enlarging the summation range and applying the binomial theorem yields $h = 0 \sum m i n (r_{b}, s_{b}) (h r _{b}) (h s _{b}) h! m^{- h} α_{b}^{r_{b} + s_{b} - h} \leq α_{b}^{r_{b}} h = 0 \sum s_{b} (h s _{b}) (\frac{∣ s ∣}{m})^{h} α_{b}^{s_{b} - h} = α_{b}^{r_{b}} (α_{b} + \frac{∣ s ∣}{m})^{s_{b}} .$

Multiplying these coordinatewise bounds gives $E [m_{k, r} m_{k, s}] \leq e b \prod α_{b}^{r_{b}} b \prod (α_{b} + \frac{∣ s ∣}{m})^{s_{b}} .$ The $\emptyset$ -coordinate contributes $1$ , since $r_{\emptyset} = s_{\emptyset} = 0$ . Replacing $b$ by $(a, y) \in C$ and $m$ by $m_{1}$ yields $E_{P^{\otimes n}} [m_{k, r} m_{k, s}] \leq e (a, y) \prod q_{ak y}^{r_{a y}} (a, y) \prod (q_{ak y} + \frac{∣ s ∣}{m _{1}})^{s_{a y}} .$

∎

Lemma 14 [lem:coefficient-sum-certificate] (Coefficient sum certificate).

Let $M$ be a positive integer and let $z \geq 0$ . With $g_{M, j}$ denoting the coefficients of the polynomial continuation $G_{M}$ from Definition 9, define $g_{M}^{+} (z) = j \in {0, \dots, M - 2} \sum ∣ g_{M, j} ∣ z^{j},$ with the sum interpreted as empty when $M = 1$ . Then $g_{M}^{+} (z) \leq 6^{M} max {1, z^{M \dot{-} 2}},$ where $M \dot{-} 2 = max {M - 2, 0}$ .

⊢ Lean

Proof of Lemma 14.

All powers below have nonnegative integer exponents; in particular, the exponent $M - 2$ in the statement is interpreted as natural-number subtraction, so it equals $0$ when $M = 1$ . Let $T_{M}$ be the Chebyshev polynomial and let $G_{M}$ be the polynomial continuation used in Definition 9. The continuation has coefficients $g_{M, j}$ satisfying $T_{M} (1 - 2 x) = 1 - 2 M^{2} x + 2 M^{2} x^{2} G_{M} (x) .$

For these coefficients, the closed form is $g_{M, j} = (- 1)^{j} \frac{2 ^{2 j + 3}}{M ( M + j + 2 )} (2 j + 4 M + j + 2) (j \geq 0) .$ Because $M > 0$ , the factor after $(- 1)^{j}$ is nonnegative. Hence $∣ g_{M, j} ∣ = \frac{2 ^{2 j + 3}}{M ( M + j + 2 )} (2 j + 4 M + j + 2) = (- 1)^{j} g_{M, j},$ and therefore, for every $z$ , $g_{M}^{+} (z) = 0 \leq j < M - 1 \sum ∣ g_{M, j} ∣ z^{j} = 0 \leq j < M - 1 \sum g_{M, j} (- z)^{j} = G_{M} (- z) .$

Taking $z = 1$ in this identity and substituting $x = - 1$ in the Chebyshev identity gives $T_{M} (3) = 1 + 2 M^{2} + 2 M^{2} g_{M}^{+} (1) .$ The sum defining $g_{M}^{+} (1)$ is nonnegative. Since $M \geq 1$ , we have $M^{2} \geq 1$ , and the displayed identity implies $g_{M}^{+} (1) \leq T_{M} (3) .$

The Chebyshev recurrence and the standard positivity bound $T_{m} (x) \geq 1$ for $x \geq 1$ give, at $x = 3$ , $T_{0} (3) = 1, T_{1} (3) = 3, T_{m + 2} (3) = 6 T_{m + 1} (3) - T_{m} (3), T_{m} (3) \geq 0.$ Induction using these facts yields $T_{M} (3) \leq 6^{M} .$ Consequently, $g_{M}^{+} (1) \leq 6^{M} .$

Now split according to $z$ . If $0 \leq z \leq 1$ , then $z^{j} \leq 1$ for every index in the sum, so $g_{M}^{+} (z) = 0 \leq j < M - 1 \sum ∣ g_{M, j} ∣ z^{j} \leq 0 \leq j < M - 1 \sum ∣ g_{M, j} ∣ = g_{M}^{+} (1) \leq 6^{M} \leq 6^{M} max {1, z^{M - 2}} .$

If $1 \leq z$ , then every index in the finite sum satisfies $j \leq M - 2$ with the same natural-number subtraction convention. Hence $z^{j} \leq z^{M - 2}$ , and $g_{M}^{+} (z) \leq z^{M - 2} 0 \leq j < M - 1 \sum ∣ g_{M, j} ∣ = z^{M - 2} g_{M}^{+} (1) \leq 6^{M} z^{M - 2} \leq 6^{M} max {1, z^{M - 2}} .$

The two cases prove the claimed bound.

∎

Lemma 13 is the basic moment inequality for normalized falling-factorial monomials. Lemma 14 bounds the one-arm absolute coefficient sum generated by the Chebyshev reciprocal polynomial, which keeps the light-cell variance compatible with the logarithmic degree calibration in Lemma 7.

The aggregate heavy-cell result and the sparse factorial-polynomial definitions now prepare the two branches of the hybrid estimator for the final light-cell rate bound.

Lemma 15 [lem:universal-heavy-cell-rate] (Heavy-cell rate bound).

For every overlap level $ϵ$ satisfying $0 < ϵ < 1/2$ , there exist constants $C_{ϵ}, ρ_{ϵ} > 0$ and an integer $N_{ϵ}$ such that the following holds. For every $n, d$ , every single-observation law $P$ on ${1, \dots, d} \times {0, 1}^{2}$ , and every sample law $μ_{n}$ , if

(Sample size.) $n \geq N_{ϵ}$ ;
(Dimension range.) $d \leq ρ_{ϵ} n lo g n$ ;
(Experiment membership.) $μ_{n}$ and $P$ belong to the overlap-restricted iid product-law experiment class $E_{n, d, ϵ}$ of Definition 2,

then the aggregate heavy-cell ratio estimator satisfies $\int ⎩ ⎨ ⎧ T_{H} (O_{1}, \dots, O_{n}) - k \in H_{n} (O_{1}, \dots, O_{n}) \sum ϕ (q_{k}) ⎭ ⎬ ⎫^{2} d μ_{n} \leq C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$

⊢ Lean

Proof of Lemma 15.

Write $L = lo g (e n), m_{j} = ∣ I_{j} ∣ (j = 0, 1),$ and let $N_{0}$ denote the calibration cutoff in Definition 9. For $n \geq N_{0}$ , the implemented heavy set $H_{n}$ is the pilot set at threshold $256$ : $H = {k : ⌊ 256 L ⌋ < N_{k}^{(0)}} .$ The corresponding pilot-bad event is $B = {\neg (\forall k \in H, \frac{256 L}{2 m _{0}} \leq p_{k}) or \neg (\forall k \in / H, p_{k} \leq \frac{2 \cdot 256 L}{m _{0}})} .$

For every sample, the empirical arm ratios in $h_{k}$ use totalized division, so the ratio is $0$ when the corresponding arm count is zero; with this convention each such ratio lies in $[0, 1]$ . Hence the absolute empirical ratio contribution of category $k$ is at most $N_{k}^{(1)} / m_{1}$ , and summing over the selected categories gives $∣ T_{H} ∣ \leq k \in H_{n} \sum \frac{N _{k}^{(1)}}{m _{1}} \leq k \sum \frac{N _{k}^{(1)}}{m _{1}} = \frac{m _{1}}{m _{1}} \leq 1.$ For an overlap law $P$ , the category vector $q_{k}$ from Definition 5 lies in the overlap cone of Definition 3. If $p_{k} = 0$ , then $q_{k} = 0$ and Definition 4 sets $ϕ (q_{k}) = 0$ . If $p_{k} > 0$ , the arm masses in $q_{k}$ are positive and the displayed formula in Definition 4 gives $ϕ (q_{k}) = p_{k} (μ_{1 k} - μ_{0 k}),$ where the binary-outcome regressions $μ_{0 k}$ and $μ_{1 k}$ lie in $[0, 1]$ . Thus, in both cases, $∣ ϕ (q_{k}) ∣ \leq p_{k}$ . Since the category masses sum to one, $k \in H_{n} \sum ϕ (q_{k}) \leq k \in H_{n} \sum p_{k} \leq k \sum p_{k} = 1.$ Thus the squared heavy-cell error is bounded by $4$ pointwise for the overlap laws considered below. The fixed-threshold pilot sandwich from Lemma 1, applied with dimension constant $1$ , gives constants $C_{0} > 0$ and $N_{bad}$ such that, whenever $n \geq N_{bad}$ and $d \leq n L$ , $P^{\otimes n} (B) \leq C_{0} n^{- 4} .$ With $C_{bad} = 4 C_{0}$ , the range bound gives $\int_{B} T_{H} - k \in H_{n} \sum ϕ (q_{k})^{2} d P^{\otimes n} \leq C_{bad} n^{- 4} .$

Set $K_{ϵ}^{H} = \frac{16}{ϵ} + 12 + \frac{1}{ϵ ^{4}}, C_{ϵ} = 4 K_{ϵ}^{H} + C_{bad}, ρ_{ϵ} = 1,$ and take $N_{ϵ} = max {8, N_{0}, N_{bad}} .$ These constants satisfy the required positivity conditions.

Assume $n \geq N_{ϵ}$ , $d \leq ρ_{ϵ} n lo g n$ , and $μ_{n} \in E_{n, d, ϵ}$ . The experiment-class assumption gives $μ_{n} = P^{\otimes n}$ and $ϵ$ -overlap for $P$ . Also $n \geq 8$ , $n \geq N_{0}$ , $n \geq N_{bad}$ , and, since $lo g n \leq L$ , $d \leq n L .$ Let $B_{-} = \frac{256 L}{2 m _{0}} .$ On $B^{c}$ , the first half of the pilot sandwich and the equality $H_{n} = H$ give $k \in H_{n} ⟹ B_{-} \leq p_{k} .$

Fix a deterministic category set $H$ satisfying $p_{k} \geq B_{-}$ for every $k \in H$ , and fix $a \in {0, 1}$ . Define $S_{a} (H) = k \in H \sum \frac{N _{k}^{(1)}}{m _{1}} \frac{N _{ak 1}^{(1)}}{N _{ak}^{(1)}} 1 {N_{ak}^{(1)} > 0}, θ_{a} (H) = k \in H \sum p_{k} μ_{ak},$ where the displayed ratio is taken to be $0$ when $N_{ak}^{(1)} = 0$ . The empirical category-mass centering is $k \in H \sum \frac{N _{k}^{(1)}}{m _{1}} μ_{ak} .$ The pointwise decomposition about this centering is $S_{a} (H) - k \in H \sum \frac{N _{k}^{(1)}}{m _{1}} μ_{ak} = \frac{1}{m _{1}} [k \in H \sum N_{k}^{(1)} \frac{1 { N _{ak}^{(1)} > 0 }}{N _{ak}^{(1)}} {N_{ak 1}^{(1)} - μ_{ak} N_{ak}^{(1)}} - k \in H \sum μ_{ak} N_{k}^{(1)} 1 {N_{ak}^{(1)} = 0}] .$

The first bracket is the aggregate centered ratio residual $R_{a} (H)$ of Lemma 11, formed on the estimation split: the index set is $I_{1}$ , so $m = m_{1}$ ; the category set $H$ is deterministic and carries $p_{k} \geq B_{-} > 0$ ; and $P$ has overlap at level $ϵ$ . Lemma 11 therefore gives $\int [k \in H \sum N_{k}^{(1)} \frac{1 { N _{ak}^{(1)} > 0 }}{N _{ak}^{(1)}} {N_{ak 1}^{(1)} - μ_{ak} N_{ak}^{(1)}}]^{2} d P^{\otimes n} \leq \frac{2 m _{1}}{ϵ} k \in H \sum p_{k} .$

For the second bracket, $0 \leq μ_{ak} \leq 1$ , so its square is bounded by the square of the missing-arm count $k \in H \sum N_{k}^{(1)} 1 {N_{ak}^{(1)} = 0} .$ Since $n \geq 8$ we have $m_{1} \geq 3$ , and the categories in $H$ have mass at least $B_{-} > 0$ , so that count meets the hypotheses of Lemma 12 on the estimation split, with $m = m_{1}$ and mass floor $B = B_{-}$ . Combining the domination just recorded with the second moment of Lemma 12 gives $\int [k \in H \sum μ_{ak} N_{k}^{(1)} 1 {N_{ak}^{(1)} = 0}]^{2} d P^{\otimes n} \leq m_{1} + m_{1}^{2} [\frac{∣ H ∣}{{(( m _{1} - 2 ) /2 ) ϵ } ^{2} B _{-}}]^{2} .$ Together with $(x - y)^{2} \leq 2 x^{2} + 2 y^{2}$ , the two bracket bounds give $\int (S_{a} (H) - k \in H \sum \frac{N _{k}^{(1)}}{m _{1}} μ_{ak})^{2} d P^{\otimes n} \leq \frac{4 \sum _{k \in H} p _{k}}{m _{1} ϵ} + \frac{2}{m _{1}} + 2 [\frac{∣ H ∣}{{(( m _{1} - 2 ) /2 ) ϵ } ^{2} B _{-}}]^{2} .$

For the empirical category-mass fluctuation, use the one-observation score $g_{a, H} (O) = μ_{a X} 1 {X \in H} .$ Its second-split average is the empirical category-mass centering, its expectation is $θ_{a} (H)$ , and $0 \leq g_{a, H} \leq 1$ . The iid bounded-score variance bound therefore gives $\int (k \in H \sum \frac{N _{k}^{(1)}}{m _{1}} μ_{ak} - θ_{a} (H))^{2} d P^{\otimes n} \leq \frac{1}{m _{1}} .$ Splitting $S_{a} (H) - θ_{a} (H)$ at the empirical category-mass centering yields $\int {S_{a} (H) - θ_{a} (H)}^{2} d P^{\otimes n} \leq \frac{8 \sum _{k \in H} p _{k}}{m _{1} ϵ} + \frac{6}{m _{1}} + 4 [\frac{∣ H ∣}{{(( m _{1} - 2 ) /2 ) ϵ } ^{2} B _{-}}]^{2} .$

The probability-mass identities give $k \in H \sum p_{k} \leq k \sum p_{k} = 1,$ and the finite-set cardinality bound gives $∣ H ∣ \leq d$ . The split-size calibration for $n \geq 8$ gives $\frac{n}{2} \leq m_{1}, \frac{n}{8} \leq \frac{m _{1} - 2}{2}, \frac{256 L}{n} \leq B_{-},$ and $lo g n \leq L$ . Hence $\frac{8 \sum _{k \in H} p _{k}}{m _{1} ϵ} + \frac{6}{m _{1}} + 4 [\frac{∣ H ∣}{{(( m _{1} - 2 ) /2 ) ϵ } ^{2} B _{-}}]^{2} \leq K_{ϵ}^{H} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$

Let $V = K_{ϵ}^{H} {n^{- 1} + d^{2} / [n^{2} (lo g n)^{2}]}$ . The preceding deterministic bound applies uniformly to every fixed $H$ whose elements have mass at least $B_{-}$ . To pass to the random pilot-heavy set on $B^{c}$ , partition the pilot sample space into the fibers on which $H_{n} = H$ . The partition is carried out on the ambient iid sequence, whose first $n$ coordinates have law $P^{\otimes n}$ by Lemma 20, so every integral below may equally be read under either law. On each contributing fiber, the good-pilot implication gives $p_{k} \geq B_{-}$ for every $k \in H$ . The fixed- $H$ arm error is a function of the estimation split, while the fiber is determined by the pilot split, so the product law factors the restricted integral into the fiber probability times the fixed- $H$ product-law integral. Summing over the eligible fibers and using that their probabilities sum to at most one gives, for each $a \in {0, 1}$ , $\int_{B^{c}} {S_{a} (H_{n}) - θ_{a} (H_{n})}^{2} d P^{\otimes n} \leq V .$

The heavy contribution and target decompose into their two arm components: $T_{H} - k \in H_{n} \sum ϕ (q_{k}) = {S_{1} (H_{n}) - θ_{1} (H_{n})} - {S_{0} (H_{n}) - θ_{0} (H_{n})} .$ Thus $(x - y)^{2} \leq 2 x^{2} + 2 y^{2}$ gives $\int_{B^{c}} T_{H} - k \in H_{n} \sum ϕ (q_{k})^{2} d P^{\otimes n} \leq 4 K_{ϵ}^{H} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$

The bad-event contribution satisfies $\int_{B} T_{H} - k \in H_{n} \sum ϕ (q_{k})^{2} d P^{\otimes n} \leq C_{bad} n^{- 4} \leq C_{bad} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}},$ because $n^{- 4} \leq n^{- 1}$ for $n \geq 8$ and $n^{- 1} \leq n^{- 1} + d^{2} / [n^{2} (lo g n)^{2}]$ . Adding the integrals over $B$ and $B^{c}$ , and using $μ_{n} = P^{\otimes n}$ , yields $\int T_{H} - k \in H_{n} \sum ϕ (q_{k})^{2} d μ_{n} \leq (4 K_{ϵ}^{H} + C_{bad}) {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}},$ which is the claimed bound with the chosen $C_{ϵ}$ .

∎

Definition 14 [synth_20] (Sparse factorial-polynomial means).

Given a law $P$ , a category $k \in {1, \dots, d}$ , a degree $M$ , and a scale $B$ , write $q_{k} = (q_{0 k 0}, q_{0 k 1}, q_{1 k 0}, q_{1 k 1})$ for the four-cell mass vector of category $k$ under $P$ . For an arm $a \in {0, 1}$ , the sparse-arm mean is $\overset{ˉ}{A}_{a, k} (P, M, B) = \frac{s ( q _{k} ) t _{a} ( q _{k} )}{B} G_{M} (\frac{s _{a} ( q _{k} )}{B}),$ with $s$ , $s_{a}$ , $t_{a}$ , and $G_{M}$ as in Definition 9. The sparse factorial-polynomial mean of category $k$ is the difference of the two arm means, $\overset{ˉ}{P}_{k} = P_{M, B} (q_{k}) = \overset{ˉ}{A}_{1, k} (P, M, B) - \overset{ˉ}{A}_{0, k} (P, M, B) .$

Lemma 16 [lem:factorial-moment-variance] (Factorial moment variance bound).

Use the split notation and hybrid-estimator calibration in Definitions 7 and 9. For any sample size $n$ , alphabet size $d$ , probability law $P$ on the finite observed-data alphabet, and category $k$ , let $\overset{ˉ}{P}_{k}$ denote the sparse factorial-polynomial mean of the light-cell statistic $P_{k}$ . Suppose that

(Split size.) $m_{1} > 0$ .
(Degree and scale.) $M (n) > 0$ and $B (n) > 0$ .
(Sample-size calibration.) $4 M (n)^{2} \leq m_{1}$ .
(Mass envelope.) The category mass $p_{k} = P (X = k)$ satisfies $p_{k} + \frac{4 M ( n )}{m _{1}} \leq B (n) and p_{k} \leq B (n) .$

Then, under the ambient infinite iid product law $P^{\otimes \infty}$ , $\int (P_{k} - \overset{ˉ}{P}_{k})^{2} d P^{\otimes \infty} \leq 8 (e + 1) (B (n) 6^{M (n)})^{2} .$

⊢ Lean

Proof of Lemma 16.

All expectations below are taken under the iid sequence law generated by $P$ , equivalently under the corresponding $n$ -fold product law for functions of $O_{1}, \dots, O_{n}$ . Write $M = M (n)$ , $B = B (n)$ , $m_{1} = ∣ I_{1} ∣$ , and $q = q_{k}$ . The coefficients in the sparse expansion are the coefficients of the polynomial continuation $G_{M}$ : $g_{M, j} = (- 1)^{j} \frac{2 ^{2 j + 3}}{M ( M + j + 2 )} (2 j + 4 M + j + 2), G_{M} (x) = j = 0 \sum M - 2 g_{M, j} x^{j} .$ For $a \in {0, 1}$ , $c \in {0, 1}^{2}$ , and $0 \leq t \leq j \leq M - 2$ , let $r^{a, c, j, t}$ be the sparse multi-index determined by $u^{r^{a, c, j, t}} = u_{c} u_{a 1} u_{a 0}^{t} u_{a 1}^{j - t} .$ The sparse arm mean is $\overset{ˉ}{A}_{a, k} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) q^{r^{a, c, j, t}},$ and the sparse polynomial mean is $\overset{ˉ}{P}_{k} = \overset{ˉ}{A}_{1, k} - \overset{ˉ}{A}_{0, k} .$ For a nonnegative four-cell vector $v$ , set $E_{a} (v) = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) v^{r^{a, c, j, t}} .$ The triangle inequality gives $∣ \overset{ˉ}{A}_{a, k} ∣ \leq E_{a} (q)$ . We first record the envelope bound used for both $q$ and its shifted version. If $v \geq 0$ , $\sum_{c} v_{c} \leq B$ , $M > 0$ , and $B > 0$ , then summing first over $c$ and then using the binomial theorem gives $E_{a} (v) = B^{- 1} (c \sum v_{c}) v_{a 1} j = 0 \sum M - 2 ∣ g_{M, j} ∣ (\frac{v _{a 0} + v _{a 1}}{B})^{j} .$ The coefficient-sum certificate in Lemma 14 gives, for every $z \geq 0$ , $j = 0 \sum M - 2 ∣ g_{M, j} ∣ z^{j} \leq 6^{M} max {1, z^{M - 2}} .$ In the envelope application, $z = (v_{a 0} + v_{a 1}) / B$ lies in $[0, 1]$ . Since $0 \leq v_{a 1} \leq \sum_{c} v_{c} \leq B$ , $E_{a} (v) \leq B^{- 1} (c \sum v_{c})^{2} 6^{M} \leq B 6^{M} .$ Applying this with $v = q$ , using $q \geq 0$ and $\sum_{c} q_{c} = p_{k} \leq B$ , gives $∣ \overset{ˉ}{P}_{k} ∣ \leq ∣ \overset{ˉ}{A}_{1, k} ∣ + ∣ \overset{ˉ}{A}_{0, k} ∣ \leq 2 B 6^{M}, \overset{ˉ}{P}_{k}^{2} \leq 4 (B 6^{M})^{2} .$

The sample arm contribution has the parallel factorial-moment expansion $A_{a, k} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) \frac{\prod _{b, y} ( N _{bk y}^{(1)} ) _{r_{b y}^{a, c, j, t}}}{( m _{1} ) _{∣ r^{a, c, j, t} ∣}}, P_{k} = A_{1, k} - A_{0, k} .$ For a multi-index $r$ , write $F_{r} = \frac{\prod _{b, y} ( N _{bk y}^{(1)} ) _{r_{b y}}}{( m _{1} ) _{∣ r ∣}} .$ For two displayed terms with multi-indices $r$ and $s$ , the range restrictions give $∣ r ∣ = j + 2 \leq M$ and $∣ s ∣ = j^{'} + 2 \leq M$ . Suppose first that $∣ r ∣ \leq ∣ s ∣$ . Since $∣ s ∣ \leq M$ and $4 M^{2} \leq m_{1}$ , the split-size condition in Lemma 13 applies and gives $E [F_{r} F_{s}] \leq e q^{r} (q + \frac{∣ s ∣}{m _{1}} 1)^{s} .$ Coordinatewise nonnegativity of $q$ , the inequality $∣ s ∣ \leq M$ , and monotonicity of nonnegative monomials yield $E [F_{r} F_{s}] \leq e (q + \frac{M}{m _{1}} 1)^{r} (q + \frac{M}{m _{1}} 1)^{s} .$ When $∣ s ∣ \leq ∣ r ∣$ , the same argument with $r$ and $s$ interchanged gives the same bound. The unweighted factorial monomial product is nonnegative pointwise, and the product of the two displayed coefficients is bounded above by the product of their absolute values. Hence $E [(B^{- 1} g_{M, j} B^{- j} (t j) F_{r^{a, c, j, t}}) (B^{- 1} g_{M, j^{'}} B^{- j^{'}} (t ^{'} j ^{'}) F_{r^{a, c^{'}, j^{'}, t^{'}}})] \leq e B^{- 1} g_{M, j} B^{- j} (t j) (q + \frac{M}{m _{1}} 1)^{r^{a, c, j, t}} B^{- 1} g_{M, j^{'}} B^{- j^{'}} (t ^{'} j ^{'}) (q + \frac{M}{m _{1}} 1)^{r^{a, c^{'}, j^{'}, t^{'}}} .$ Expanding $A_{a, k}^{2}$ as the finite double sum, applying this estimate term by term, and reassembling the absolute-coefficient sums gives $E [A_{a, k}^{2}] \leq e E_{a} (q + \frac{M}{m _{1}} 1)^{2} .$ The shifted vector is nonnegative and has total mass $b, y \sum (q_{b y} + \frac{M}{m _{1}}) = p_{k} + \frac{4 M}{m _{1}} \leq B,$ by the shifted light-cell mass condition. Applying the envelope bound to the shifted vector gives $E [A_{a, k}^{2}] \leq e (B 6^{M})^{2} (a = 0, 1) .$ Using $(u - v)^{2} \leq 2 u^{2} + 2 v^{2}$ with $u = A_{1, k}$ and $v = A_{0, k}$ , $E [P_{k}^{2}] \leq 2 E [A_{1, k}^{2}] + 2 E [A_{0, k}^{2}] \leq 4 e (B 6^{M})^{2} .$

Finally, pointwise, $(P_{k} - \overset{ˉ}{P}_{k})^{2} \leq 2 P_{k}^{2} + 2 \overset{ˉ}{P}_{k}^{2},$ because $(P_{k} + \overset{ˉ}{P}_{k})^{2} \geq 0$ . Integrating and substituting the two bounds above gives $E [(P_{k} - \overset{ˉ}{P}_{k})^{2}] \leq 2 \cdot 4 e (B 6^{M})^{2} + 2 \cdot 4 (B 6^{M})^{2} = 8 (e + 1) (B 6^{M})^{2},$ as required.

∎

Lemma 17 [lem:factorial-moment-covariance] (Off-diagonal factorial covariance).

Use the split notation and calibration $m_{1}$ , $M (n)$ , and $B (n)$ from Definitions 7 and 9. For each category $k$ , let $P_{k}$ be the factorial-moment polynomial estimate from Definition 9, computed from the first $n$ coordinates of the ambient iid sequence, and let $\overset{ˉ}{P}_{k} = \overset{ˉ}{A}_{1, k} (P, M (n), B (n)) - \overset{ˉ}{A}_{0, k} (P, M (n), B (n))$ denote the corresponding sparse factorial-polynomial mean, written as the treated sparse-arm mean minus the control sparse-arm mean.

For any single-observation law $P$ on ${1, \dots, d} \times {0, 1}^{2}$ and any two categories $k, l \in {1, \dots, d}$ , suppose that

Distinct categories. $k \neq = l$ .
Positive calibration. $M (n) > 0$ and $B (n) > 0$ .
Second-split size. $4 M (n)^{2} \leq m_{1}$ .
Light masses. $p_{k} \leq B (n)$ and $p_{l} \leq B (n)$ .

Then, under the ambient infinite iid product law $P^{\otimes \infty}$ , $E_{P^{\otimes \infty}} [(P_{k} - \overset{ˉ}{P}_{k}) (P_{l} - \overset{ˉ}{P}_{l})] \leq \frac{8 M ( n ) ^{2}}{m _{1}} {B (n) 6^{M (n)}}^{2} .$

⊢ Lean

Proof of Lemma 17.

Let $μ$ be the iid product law generated by $P$ on the sample sequence, and abbreviate $M = M (n), B = B (n), m = m_{1}, R = B 6^{M}, η = \frac{2 M ^{2}}{m} .$ Write the polynomial continuation as $G_{M} (x) = j = 0 \sum M - 2 g_{M, j} x^{j} .$ For $h \in {k, l}$ , let $q_{h}$ be the four-cell vector of category $h$ under $P$ , and write $q_{h}^{r} = \prod_{b, y} (q_{h})_{b y}^{r_{b y}}$ . For an arm $a \in {0, 1}$ , a cell $c \in {0, 1}^{2}$ , and integers $0 \leq t \leq j \leq M - 2$ , let $r^{a, c, j, t}$ be the multi-index determined by $u^{r^{a, c, j, t}} = u_{c} u_{a 1} u_{a 0}^{t} u_{a 1}^{j - t} .$ The sparse arm contribution and its sparse mean are $A_{a, h} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) \frac{\prod _{b, y} ( N _{bh y}^{(1)} ) _{r_{b y}^{a, c, j, t}}}{( m ) _{∣ r^{a, c, j, t} ∣}},$ $\overset{ˉ}{A}_{a, h} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) q_{h}^{r^{a, c, j, t}} .$ Thus $P_{h} = A_{1, h} - A_{0, h}, \overset{ˉ}{P}_{h} = \overset{ˉ}{A}_{1, h} - \overset{ˉ}{A}_{0, h} .$ The size condition $4 M^{2} \leq m$ , together with $M > 0$ , gives $M \leq m$ . Since each displayed sparse multi-index has total degree $j + 2 \leq M$ , the factorial-moment identity gives, for $h = k, l$ , $\int A_{a, h} d μ = \overset{ˉ}{A}_{a, h} (a = 0, 1), \int P_{h} d μ = \overset{ˉ}{P}_{h} .$ Consequently, by expanding the centered product and integrating term by term, $\int (P_{k} - \overset{ˉ}{P}_{k}) (P_{l} - \overset{ˉ}{P}_{l}) d μ = \int P_{k} P_{l} d μ - \overset{ˉ}{P}_{k} \overset{ˉ}{P}_{l} .$

For $h \in {k, l}$ and $a \in {0, 1}$ , define the absolute arm envelope $Env_{a, h} = j = 0 \sum M - 2 t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) q_{h}^{r^{a, c, j, t}} .$ Fix two sparse monomials with multi-indices $r$ and $s$ from categories $k$ and $l$ , and put $F_{h, r} = \frac{\prod _{b, y} ( N _{bh y}^{(1)} ) _{r_{b y}}}{( m ) _{∣ r ∣}} .$ The product of the two normalized factorial counts is an average over ordered injective selections for the $k$ -monomial and ordered injective selections for the $l$ -monomial. Because $k \neq = l$ , an observation cannot satisfy both category patterns; hence exactly the disjoint pairs of selections contribute. There are $(m)_{∣ r ∣ + ∣ s ∣}$ such ordered pairs, and independence gives the same cell-mass product $q_{k}^{r} q_{l}^{s}$ for each pair. Therefore $\int F_{k, r} F_{l, s} d μ = Γ_{r, s} q_{k}^{r} q_{l}^{s}, Γ_{r, s} = \frac{( m ) _{∣ r ∣ + ∣ s ∣}}{( m ) _{∣ r ∣} ( m ) _{∣ s ∣}} .$ For sparse terms, $∣ r ∣ \leq M$ and $∣ s ∣ \leq M$ . We next bound the normalization factor. Suppose first that $∣ r ∣ \leq ∣ s ∣$ . If $∣ s ∣ = 0$ , then $∣ r ∣ = 0$ and $Γ_{r, s} = 1$ . If $∣ s ∣ > 0$ , the condition $4∣ s ∣^{2} \leq m$ follows from $∣ s ∣ \leq M$ and $4 M^{2} \leq m$ , and it implies $2∣ s ∣ \leq m$ . Using $Γ_{r, s} = \frac{( m - ∣ r ∣ ) _{∣ s ∣}}{( m ) _{∣ s ∣}},$ we have $Γ_{r, s} \leq 1$ . Also $Γ_{r, s} \geq \frac{( m - 2∣ s ∣ ) ^{∣ s ∣}}{m ^{∣ s ∣}} = (1 - \frac{2∣ s ∣}{m})^{∣ s ∣} \geq 1 - \frac{2∣ s ∣ ^{2}}{m},$ where the last step is Bernoulli’s inequality, using $- 1 \leq - 2∣ s ∣/ m$ . Hence $∣ Γ_{r, s} - 1∣ \leq \frac{2∣ s ∣ ^{2}}{m} \leq η .$ The case $∣ s ∣ \leq ∣ r ∣$ is identical after exchanging $r$ and $s$ , using the symmetry of $Γ_{r, s}$ . Since the four-cell masses are nonnegative, $\int F_{k, r} F_{l, s} d μ - q_{k}^{r} q_{l}^{s} \leq η q_{k}^{r} q_{l}^{s}, ∣ r ∣, ∣ s ∣ \leq M .$ Multiplying by the two sparse coefficients, summing over the two finite arm expansions, and using the triangle inequality yields $\int A_{a, k} A_{b, l} d μ - \overset{ˉ}{A}_{a, k} \overset{ˉ}{A}_{b, l} \leq η Env_{a, k} Env_{b, l} .$

For $h = k, l$ , the coordinates of $q_{h}$ are nonnegative and sum to $p_{h}$ . For fixed $j$ , positivity of $B$ and of the binomial coefficients gives $t = 0 \sum j c \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) q_{h}^{r^{a, c, j, t}} = B^{- 1} ∣ g_{M, j} ∣ B^{- j} t = 0 \sum j c \in {0, 1}^{2} \sum (t j) (q_{h})_{c} (q_{h})_{a 1} (q_{h})_{a 0}^{t} (q_{h})_{a 1}^{j - t} = B^{- 1} ∣ g_{M, j} ∣ B^{- j} s (q_{h}) (q_{h})_{a 1} ((q_{h})_{a 0} + (q_{h})_{a 1})^{j} .$ Summing in $j$ , and using $s_{a} (q_{h}) = (q_{h})_{a 0} + (q_{h})_{a 1}$ , yields $Env_{a, h} = B^{- 1} s (q_{h}) (q_{h})_{a 1} j = 0 \sum M - 2 ∣ g_{M, j} ∣ {\frac{s _{a} ( q _{h} )}{B}}^{j} .$ The light-cell hypotheses give $p_{h} = s (q_{h}) \leq B$ , while $(q_{h})_{a 1} \leq s (q_{h})$ and $B > 0$ . Hence $B^{- 1} s (q_{h}) (q_{h})_{a 1} \leq B^{- 1} s (q_{h})^{2} \leq B, 0 \leq \frac{s _{a} ( q _{h} )}{B} \leq 1.$ It remains to record the coefficient envelope used in this display. For every $z \geq 0$ , $j = 0 \sum M - 2 ∣ g_{M, j} ∣ z^{j} \leq 6^{M} max {1, z^{M - 2}} .$ Indeed, the sign pattern of the explicit coefficients gives $\sum_{j = 0}^{M - 2} ∣ g_{M, j} ∣ = G_{M} (- 1)$ . The defining Chebyshev identity for the continuation, evaluated at $- 1$ , gives $T_{M} (3) = 1 + 2 M^{2} + 2 M^{2} j = 0 \sum M - 2 ∣ g_{M, j} ∣,$ so nonnegativity of the coefficient sum implies $\sum_{j = 0}^{M - 2} ∣ g_{M, j} ∣ \leq T_{M} (3)$ . The Chebyshev recurrence gives $T_{M} (3) \leq 6^{M}$ . If $0 \leq z \leq 1$ , termwise monotonicity gives $\sum ∣ g_{M, j} ∣ z^{j} \leq \sum ∣ g_{M, j} ∣ \leq 6^{M}$ . If $z \geq 1$ , then $j \leq M - 2$ on the displayed range, so $\sum ∣ g_{M, j} ∣ z^{j} \leq z^{M - 2} \sum ∣ g_{M, j} ∣ \leq 6^{M} z^{M - 2}$ . This proves the stated envelope. Taking $z = s_{a} (q_{h}) / B$ makes the maximum equal to $1$ , and therefore $Env_{a, h} \leq B 6^{M} = R .$ Hence, for all $a, b \in {0, 1}$ , $\int A_{a, k} A_{b, l} d μ - \overset{ˉ}{A}_{a, k} \overset{ˉ}{A}_{b, l} \leq η R^{2} .$

Define $C_{ab} = \int A_{a, k} A_{b, l} d μ - \overset{ˉ}{A}_{a, k} \overset{ˉ}{A}_{b, l} .$ Expanding the two arm contrasts gives $\int P_{k} P_{l} d μ - \overset{ˉ}{P}_{k} \overset{ˉ}{P}_{l} = C_{11} - C_{10} - C_{01} + C_{00} .$ Therefore $\int P_{k} P_{l} d μ - \overset{ˉ}{P}_{k} \overset{ˉ}{P}_{l} \leq ∣ C_{11} ∣ + ∣ C_{10} ∣ + ∣ C_{01} ∣ + ∣ C_{00} ∣ \leq 4 η R^{2} = \frac{8 M ^{2}}{m} {B 6^{M}}^{2} .$

Combining this bound with the centering identity and using $x \leq ∣ x ∣$ yields $\int (P_{k} - \overset{ˉ}{P}_{k}) (P_{l} - \overset{ˉ}{P}_{l}) d μ \leq \frac{8 M ( n ) ^{2}}{m _{1}} {B (n) 6^{M (n)}}^{2} .$

∎

Lemma 18 [lem:false-light-envelope] (False-light error envelope).

Let $P$ be a probability law on ${1, \dots, d} \times {0, 1}^{2}$ . Suppose that:

(Overlap.) For every category $k$ with $p_{k} > 0$ , the treatment probability satisfies $ϵ \leq π_{k} \leq 1 - ϵ .$
(Calibration cutoff.) The sample size satisfies $n \geq N_{0}$ , where $N_{0}$ is the least numerical cutoff satisfying the calibration inequalities used in the estimator.
(Logarithmic scale.) With $L = lo g (e n)$ , one has $L \geq 240$ .

For the pilot-light indicator $S_{k} = 1 {k \in L_{n}}$ , the selected false-light error over categories whose population mass exceeds the light-cell threshold satisfies $E_{P^{\otimes n}} ⎩ ⎨ ⎧ k \in {1, \dots, d} p_{k} > B (n) /4 \sum S_{k} (P_{k} - ϕ (q_{k})) ⎭ ⎬ ⎫^{2} \leq 8 (e + 1) 819 2^{2} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$

⊢ Lean

Proof of Lemma 18.

All expectations below are under the iid infinite product law generating the observation sequence, with each statistic evaluated on its first $n$ coordinates. Let $L = lo g (e n), ℓ = lo g n, m_{j} = ∣ I_{j} ∣ (j = 0, 1), B = B (n), M = M (n), G = 6^{2 M} .$ The deterministic split construction of Definition 7 gives $m_{0} = ⌊ n /2 ⌋, m_{1} = n - ⌊ n /2 ⌋ .$ By Lemma 7, $0 < ℓ, ℓ \leq L, L \leq 2 ℓ, m_{1} > 0, n \leq 2 m_{1}, M \leq L,$ $B \leq \frac{8192 L}{n}, G^{2} L^{6} \leq n .$

In particular $n > 0$ . Since $B = 4096 L / m_{1}$ , $L > 0$ , and $m_{1} > 0$ , also $B > 0$ , and hence $B^{2} \leq \frac{819 2 ^{2} L ^{2}}{n ^{2}} .$

Because $n > 0$ , $L = 1 + ℓ$ . Since $L \geq 240$ , $exp (- 49 L) \leq exp (- L) = \frac{1}{e n} \leq \frac{1}{n} .$ Moreover $G \geq 1$ , so $L^{4} \leq L^{6} \leq G^{2} L^{6} \leq n$ . Together with $ℓ \leq L$ , this gives $L^{2} ℓ^{2} \leq L^{4} \leq n .$ Therefore $\frac{d ^{2} L ^{2}}{n ^{3}} \leq \frac{d ^{2}}{n ^{2} ℓ ^{2}} \leq \frac{1}{n} + \frac{d ^{2}}{n ^{2} ℓ ^{2}} .$

Let $F = {k : p_{k} > B /4}, S_{k} = 1 {k \in L_{n}}, e_{k} = S_{k} (P_{k} - ϕ (q_{k})) .$ By the definition of the false-light error, the selected false-light error is $\sum_{k \in F} e_{k}$ . For each sample, Cauchy’s inequality gives $(k \in F \sum e_{k})^{2} \leq ∣ F ∣ k \in F \sum e_{k}^{2} .$

Fix $k \in F$ . The cutoff defining $N_{0}$ in Definition 9 and the assumption $n \geq N_{0}$ give $α_{0} L \geq 2, 4 M^{2} \leq m_{1}, \frac{4 M}{m _{1}} \leq \frac{3 B}{4} .$ Since $M \geq 2$ , the bound $4 M^{2} \leq m_{1}$ gives $16 \leq m_{1}$ . With the split identities above, this implies $m_{0} > 0$ and $m_{1} \leq 2 m_{0}$ .

Write $G_{M} (x) = j = 0 \sum M - 2 g_{M, j} x^{j}, g_{M, j} = (- 1)^{j} \frac{2 ^{2 j + 3}}{M ( M + j + 2 )} (2 j + 4 M + j + 2) .$ Let $e_{b y}$ denote the unit multi-index at the four-cell coordinate $(b, y) \in {0, 1}^{2}$ . In the next display, $a y$ is a single four-cell label, say $a y = (b, y^{'})$ , and $e_{a y}$ is the corresponding unit multi-index. For $a \in {0, 1}$ , $a y \in {0, 1}^{2}$ , and $0 \leq t \leq j \leq M - 2$ , set $r (a, a y, j, t) = e_{a y} + e_{a 1} + t e_{a 0} + (j - t) e_{a 1}, ∣ r (a, a y, j, t) ∣ = j + 2.$ For a multi-index $r$ , the factorial-moment monomial is $m_{k, r} = \frac{\prod _{(b, y) \in {0, 1}^{2}} ( N _{bk y}^{(1)} ) _{r_{b y}}}{( m _{1} ) _{∣ r ∣}},$ where $(z)_{s}$ denotes the falling factorial. The $a$ -arm sparse factorial-moment contribution is $P_{k, a}^{sp} = j = 0 \sum M - 2 t = 0 \sum j a y \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) m_{k, r (a, a y, j, t)} .$ By Definition 9, $P_{k} = \sum_{∣ r ∣ \leq M} c_{r} m_{k, r}$ in collected coefficient form, where each $c_{r}$ is obtained by expanding the two arms of $P_{M, B}$ through the coefficients $g_{M, j}$ and the binomial expansion of the arm masses, and summing the resulting sparse coefficients $c_{u} = B^{- 1} g_{M, j} B^{- j} (t j)$ over the sparse indices $u = (j, t, a y)$ with $r_{u} = r$ . Since $r \mapsto m_{k, r}$ enters linearly in each coefficient, regrouping this finite double sum arm by arm yields $P_{k} = P_{k, 1}^{sp} - P_{k, 0}^{sp} .$

For a nonnegative four-cell vector $v$ , define the absolute sparse arm envelope $A_{a} (v) = j = 0 \sum M - 2 t = 0 \sum j a y \in {0, 1}^{2} \sum B^{- 1} g_{M, j} B^{- j} (t j) v^{r (a, a y, j, t)}, v^{r} = (b, y) \in {0, 1}^{2} \prod v_{b y}^{r_{b y}} .$ Set $v_{a y}^{(k)} = q_{k, a y} + \frac{M}{m _{1}} .$ This vector is nonnegative. Fix two sparse indices $u = (j, t, a y)$ and $u^{'} = (j^{'}, t^{'}, a y^{'})$ with $0 \leq t \leq j \leq M - 2$ and $0 \leq t^{'} \leq j^{'} \leq M - 2$ . Both multi-indices $r_{u}, r_{u^{'}}$ have degree at most $M$ , so $4 max {∣ r_{u} ∣, ∣ r_{u^{'}} ∣}^{2} \leq 4 M^{2} \leq m_{1}$ . Apply Lemma 13 to the degree-ordered pair. Its unshifted monomial factor is bounded coordinatewise by $(v^{(k)})^{r}$ , since $q_{k, cy} \leq q_{k, cy} + M / m_{1}$ . Its shifted monomial factor is also bounded coordinatewise by the corresponding power of $v^{(k)}$ : if $s$ is the larger-degree multi-index in the ordered pair, then $∣ s ∣ \leq M$ , and hence $q_{k, cy} + \frac{∣ s ∣}{m _{1}} \leq q_{k, cy} + \frac{M}{m _{1}} = v_{cy}^{(k)} for every coordinate cy .$ Using these two coordinatewise bounds, and swapping $u, u^{'}$ before applying Lemma 13 when the opposite degree order holds, gives $E [(c_{u} m_{k, r_{u}}) (c_{u^{'}} m_{k, r_{u^{'}}})] \leq e ∣ c_{u} ∣ (v^{(k)})^{r_{u}} ∣ c_{u^{'}} ∣ (v^{(k)})^{r_{u^{'}}},$ where $c_{u} = B^{- 1} g_{M, j} B^{- j} (t j)$ and $r_{u} = r (a, a y, j, t)$ . Expanding the square of $P_{k, a}^{sp}$ , summing this bound over all ordered pairs of sparse indices, and collecting the two sums into the envelope gives $E [(P_{k, a}^{sp})^{2}] \leq e A_{a} (v^{(k)})^{2}, a = 0, 1.$

The shifted vector has total mass $a y \sum v_{a y}^{(k)} = p_{k} + \frac{4 M}{m _{1}} \leq p_{k} + \frac{3 B}{4} \leq B (1 + \frac{p _{k}}{B}) .$ Let $R = \sum_{a y} v_{a y}$ , $A_{a} (v) = v_{a 0} + v_{a 1}$ , and $g_{M}^{+} (z) = j = 0 \sum M - 2 ∣ g_{M, j} ∣ z^{j} .$ For every nonnegative $v$ with $R \leq B w$ and $w \geq 1$ , the binomial summation in the sparse envelope gives $A_{a} (v) = B^{- 1} R v_{a 1} g_{M}^{+} (\frac{A _{a} ( v )}{B}),$ and, since $0 \leq A_{a} (v) / B \leq R / B \leq w$ with $w \geq 1$ , Lemma 14 gives $g_{M}^{+} (\frac{A _{a} ( v )}{B}) \leq 6^{M} max {1, (\frac{A _{a} ( v )}{B})^{M - 2}} \leq 6^{M} w^{M - 2} .$ Since $v_{a 1} \leq R \leq B w$ , these displays imply $A_{a} (v) \leq B 6^{M} w^{M} .$ Applying this with $v = v^{(k)}$ and $w = 1 + p_{k} / B$ yields $A_{a} (v^{(k)}) \leq B 6^{M} (1 + \frac{p _{k}}{B})^{M}, a = 0, 1.$ Since $P_{k}$ is the difference of the two sparse-arm contributions, $(x - y)^{2} \leq 2 x^{2} + 2 y^{2}$ yields $E [P_{k}^{2}] \leq 4 e {B 6^{M} (1 + \frac{p _{k}}{B})^{M}}^{2} .$ Because $k \in F$ and $B > 0$ , $p_{k} > 0$ . The overlap condition and Definition 4 give $∣ ϕ (q_{k}) ∣ \leq p_{k}$ . Since $p_{k} / B \geq 0$ and $M \geq 2$ , $\frac{p _{k}}{B} \leq 6^{M} (1 + \frac{p _{k}}{B})^{M},$ and therefore $ϕ (q_{k})^{2} \leq {B 6^{M} (1 + \frac{p _{k}}{B})^{M}}^{2} .$ Using $(x - t)^{2} \leq 2 x^{2} + 2 t^{2}$ , $E [(P_{k} - ϕ (q_{k}))^{2}] \leq 8 (e + 1) B^{2} {6^{M} (1 + \frac{p _{k}}{B})^{M}}^{2} .$

The indicator $S_{k}$ is determined by the pilot split, while $P_{k} - ϕ (q_{k})$ is computed from the estimation split and a fixed target. The split factorization gives $E [S_{k}^{2} (P_{k} - ϕ (q_{k}))^{2}] = E [S_{k}^{2}] E [(P_{k} - ϕ (q_{k}))^{2}] .$ Since $S_{k} \in {0, 1}$ , $E [S_{k}^{2}] = E [S_{k}]$ . The indicator integral is the probability of the pilot-light event: $E [S_{k}] = P^{\otimes n} {k \in L_{n}} .$ For $n \geq N_{0}$ , the event ${k \in L_{n}}$ is contained in ${N_{k}^{(0)} \leq 256 L} .$ The false-light condition $p_{k} > B /4$ , the identity $B = 4096 L / m_{1}$ , and $m_{1} \leq 2 m_{0}$ imply $2 (256 L) < m_{0} p_{k} .$ The pilot lower-tail bound for this threshold gives $E [S_{k}] \leq exp (- \frac{m _{0} p _{k}}{8}) .$ Since $p_{k} / B > 1/4$ , $1 + \frac{p _{k}}{B} \leq 5 \frac{p _{k}}{B}, 6 (1 + \frac{p _{k}}{B}) \leq 30 \frac{p _{k}}{B} .$ Also $6 (1 + p_{k} / B) \geq 1$ , so $lo g (6 (1 + p_{k} / B)) \geq 0$ ; and from $lo g x \leq x - 1$ for $x > 0$ , $lo g (6 (1 + \frac{p _{k}}{B})) \leq 30 \frac{p _{k}}{B} .$ Together with $M \leq L$ , $B = 4096 L / m_{1}$ , and $m_{1} \leq 2 m_{0}$ , this yields $2 M lo g (6 (1 + \frac{p _{k}}{B})) \leq 60 L \frac{p _{k}}{B}, 256 L \frac{p _{k}}{B} \leq \frac{m _{0} p _{k}}{8} .$ Consequently $- \frac{m _{0} p _{k}}{8} + 2 M lo g (6 (1 + \frac{p _{k}}{B})) \leq - 196 L \frac{p _{k}}{B} \leq - 49 L,$ and hence $exp (- \frac{m _{0} p _{k}}{8}) {6^{M} (1 + \frac{p _{k}}{B})^{M}}^{2} \leq exp (- 49 L) .$ Combining the preceding displays gives the single-cell bound $E [e_{k}^{2}] \leq 8 (e + 1) B^{2} exp (- 49 L) .$

Since $∣ F ∣ \leq d$ , integrating the pointwise Cauchy bound and applying the single-cell estimate gives $E (k \in F \sum e_{k})^{2} \leq ∣ F ∣ k \in F \sum 8 (e + 1) B^{2} exp (- 49 L) \leq d^{2} 8 (e + 1) B^{2} exp (- 49 L) .$

Using the bounds on $B^{2}$ , $exp (- 49 L)$ , and the rate algebra above, $d^{2} 8 (e + 1) B^{2} exp (- 49 L) \leq 8 (e + 1) 819 2^{2} \frac{d ^{2} L ^{2}}{n ^{3}} \leq 8 (e + 1) 819 2^{2} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$

∎

Lemma 15 aggregates the ratio branch over pilot-certified heavy categories at the target rate. The sparse means in Definition 14 identify the population polynomial quantities used to center the light-cell statistics. The variance bound in Lemma 16, the off-diagonal covariance bound in Lemma 17, and the false-light envelope in Lemma 18 together control the stochastic and pilot-selection terms that arise in the polynomial branch.

The light-cell theorem combines computability, approximation bias, factorial-moment variance, covariance control, and pilot classification. It is the complementary upper-bound component to Lemma 15.

Lemma 19 [lem:light-cell-polynomial] (Light-cell polynomial rate).

Fix an overlap level $ϵ$ with $0 < ϵ \leq 1/2$ . The hybrid estimator is computable in the real-arithmetic count model: there is a universal constant $K \in N$ , $K > 0$ , such that for every $n, d$ a real-arithmetic program using the split-count vector evaluates $τ_{n}^{hyb}$ exactly and uses at most $K d M (n)^{4}$ arithmetic and comparison operations.

There are constants $C_{ϵ}, c_{ϵ} > 0$ , depending only on $ϵ$ , such that, for every $n, d$ , every $P \in Prob ({1, \dots, d} \times {0, 1}^{2})$ , and every sample law $μ_{n}$ , if

(Experiment class.) $μ_{n} = P^{\otimes n}$ belongs to the overlap-restricted iid product-law experiment class $E_{n, d, ϵ}$ of Definition 2;
(Dimension range.) $d \leq c_{ϵ} n lo g n$ ;

then the light-cell contribution $T_{L}$ satisfies $\int T_{L} (O_{1}, \dots, O_{n}) - k \in L_{n} \sum ϕ (q_{k})^{2} d μ_{n} \leq C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} .$

⊢ Lean

Proof of Lemma 19.

The computability assertion uses the real-arithmetic program model in which an instruction is an input read, a constant, one of the arithmetic operations $+, -, \times, /$ , or a nonpositive comparison branch. Input and constant instructions have cost zero, and each arithmetic or branch instruction has cost one. The arithmetic is total: division by zero is interpreted as the real value $0$ . A branch node is compiled as an expression-tree node containing its test and both alternatives, so its operation count is the count of the test, plus the counts of both alternatives, plus one for the branch instruction. A finite list sum $x_{1} + \dots + x_{s}$ is compiled recursively as $x_{1} + (x_{2} + \dots + (x_{s} + 0) \dots)$ ; hence its cost is the sum of the costs of the listed expressions plus one addition for each list entry. The corresponding list product is compiled with a terminal factor $1$ and contributes one multiplication for each list entry.

The falling-factorial factors use the guarded natural-subtraction expression $x \dot{-} i = {0, x - i, x - i \leq 0, x - i > 0,$ implemented by one nonpositive branch with test $x - i$ and alternatives $0$ and $x - i$ . On natural-valued count inputs this evaluates to the truncated difference, and its operation count is $2 ops (x) + 3$ . Consequently the recursive expression $(x)_{0} = 1$ , $(x)_{r + 1} = (x \dot{-} r) (x)_{r}$ has cost $r {2 ops (x) + 4}$ . A split-count read has cost zero, so a falling-factorial expression of a split count of order $r$ costs $4 r$ . Thus a factorial monomial of multi-degree $∣ r ∣$ , including the final division by $(m_{1})_{∣ r ∣}$ , costs $4∣ r ∣ + 5.$ For a light-polynomial term indexed by $(j, t, a, y)$ , the multi-degree is $j + 2$ , and multiplication by its coefficient gives cost $4 j + 14$ . Using the list-sum convention above, summing the four cell terms costs at most $50 M (n)$ , summing over $t = 0, \dots, j$ costs at most $51 M (n)^{2}$ , and summing over $j = 0, \dots, M (n) - 2$ gives one treatment-arm factorial-polynomial expression with cost at most $52 M (n)^{3}$ . The two treatment arms and their subtraction therefore give the light-cell expression cost $ops {one light category} \leq 105 M (n)^{4} .$ The heavy ratio expression has cost $11$ . The selected-category expression is defined by cases. If $n < N_{0}$ , it is the heavy ratio expression; in this range $H_{n}$ is the full category set and $L_{n} = \emptyset$ , so this expression is exact for the selected contribution. Its cost is $11 \leq 110 M (n)^{4}$ . If $n \geq N_{0}$ , the expression branches on the first-split category count minus the threshold constant. The category-count expression is the list sum of the four split-count reads and costs four additions, the subtraction of the threshold contributes one more operation, the branch contains both the light expression and the heavy ratio expression, and the branch instruction itself contributes one operation. Since $M (n) \geq 2$ , this selected-category branch also satisfies $ops {one selected category} \leq 110 M (n)^{4} .$ Summing these selected-category expressions over $d$ categories uses the same recursive list sum and adds $d$ summation nodes. The resulting expression computes $T_{H} + T_{L}$ exactly, hence $ops {T_{H} + T_{L}} \leq 111 d M (n)^{4} .$ For $d > 0$ , the final clamp to $[- 1, 1]$ , as displayed in Definition 9, has cost $4 ops {T_{H} + T_{L}} + 6 \leq 450 d M (n)^{4} .$ For $d = 0$ , the compiled program is the zero-cost constant zero, which agrees with the empty-category hybrid estimator. Thus, for every $n, d$ , there is a real-arithmetic program reading the hybrid split-count vector, returning $τ_{n}^{hyb}$ exactly on every sample, and satisfying $ops {τ_{n}^{hyb}} \leq 450 d M (n)^{4} .$ The computability clause therefore holds with the universal constant $K = 450$ .

For the light-cell risk bound, fix $n, d, P$ and a sample law $μ_{n}$ satisfying the hypotheses of the lemma. By the experiment-class hypothesis in Definition 2, $μ_{n} = P^{\otimes n}$ and $P$ satisfies $ϵ$ -overlap. In the endpoint case $n = 0$ , the displayed rate is interpreted with the same total real convention as the arithmetic model: real division by zero is $0$ and $lo g 0 = 0$ . In the calibrated range used below, $n > 0$ and $lo g n > 0$ , so the displayed rate has its usual analytic meaning. Set $R_{n, d} := \frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}} .$ Choose $K_{c} = 4 (e + 1) 819 2^{2} + 16819 2^{2}, K_{b} = (\frac{65536}{ϵ α _{0}^{2}})^{2}, K_{f} = 8 (e + 1) 819 2^{2},$ and let $C_{ϵ} = 3 (K_{c} + K_{b} + K_{f}), c_{ϵ} = 1.$ The inequalities $ϵ > 0$ and $α_{0} > 0$ make these constants positive. The estimates below are uniform over all $d$ , so the dimension-range hypothesis is accommodated by this choice of $c_{ϵ}$ .

First suppose $n \geq N_{0}$ . Write $L = lo g (e n), ℓ = lo g n, M = M (n), B = B (n), m_{0} = ∣ I_{0} ∣, m_{1} = ∣ I_{1} ∣,$ and define the genuinely light and false-light population sets, together with the pilot light indicator, $G = {k : p_{k} \leq B /4}, F = {k : p_{k} > B /4}, S_{k} = 1 {k \in L_{n}} .$ Let $\overset{ˉ}{P}_{k} = P_{M, B} (q_{k})$ be the sparse factorial-polynomial mean of $P_{k}$ . Every multi-index $r$ appearing in the expansion has $∣ r ∣ \leq M$ , and the cutoff inequalities give $∣ r ∣ \leq M \leq m_{1}$ . Hence the ordered-selection factorial-moment identity applies with the required denominator order: $E_{P^{\otimes \infty}} [\frac{\prod _{a, y} ( N _{ak y}^{(1)} ) _{r_{a y}}}{( m _{1} ) _{∣ r ∣}}] = q_{k}^{r} .$ Substituting this identity into the polynomial expansion of $P_{k}$ , equivalently applying Lemma 9, gives $E_{P^{\otimes \infty}} [P_{k}] = \overset{ˉ}{P}_{k} = P_{M, B} (q_{k}) .$ Put $W_{var} = k \in G \sum S_{k} (P_{k} - \overset{ˉ}{P}_{k}), W_{app} = k \in G \sum S_{k} (\overset{ˉ}{P}_{k} - ϕ (q_{k})), W_{sel} = k \in F \sum S_{k} (P_{k} - ϕ (q_{k})) .$ Partitioning the selected light categories into $G$ and $F$ , and adding and subtracting $\overset{ˉ}{P}_{k}$ on $G$ , gives the pointwise identity $T_{L} - k \in L_{n} \sum ϕ (q_{k}) = W_{var} + W_{app} + W_{sel} .$

The cutoff property in Definition 9 gives $2 \leq α_{0} L$ , $4 M^{2} \leq m_{1}$ , and $4 M / m_{1} \leq 3 B /4$ . The numerical definition of $α_{0}$ gives $α_{0} \leq 1/120$ , since $D_{A} = 8 lo g (27/4) > 8$ and $(256 D_{A})^{- 1} \leq 1/120$ . Combining this with $2 \leq α_{0} L$ yields $L \geq 240$ . Therefore Lemma 7 supplies $0 < ℓ, ℓ \leq L, n \leq 2 m_{1}, M \leq L, B \leq \frac{8192 L}{n}, Γ^{2} L^{6} \leq n,$ where $Γ = 6^{2 M}$ , and also $Γ \geq 1$ . For every $k \in G$ , the cutoff shift gives $p_{k} + \frac{4 M}{m _{1}} \leq B .$ Thus Lemma 16 gives, for $k \in G$ , $\int (P_{k} - \overset{ˉ}{P}_{k})^{2} d P^{\otimes \infty} \leq 8 (e + 1) (B 6^{M})^{2} .$ For distinct $k, l \in G$ , Lemma 17 gives $\int (P_{k} - \overset{ˉ}{P}_{k}) (P_{l} - \overset{ˉ}{P}_{l}) d P^{\otimes \infty} \leq \frac{8 M ^{2}}{m _{1}} (B 6^{M})^{2} .$ The pilot indicators depend on the pilot split, while the centered polynomial products depend on the estimation split; their pair expectation factors from the centered product integral and lies in $[0, 1]$ . Expanding the square over any deterministic $S \subseteq G$ yields $\int {k \in S \sum S_{k} (P_{k} - \overset{ˉ}{P}_{k})}^{2} d P^{\otimes \infty} \leq ∣ S ∣ 8 (e + 1) (B 6^{M})^{2} + ∣ S ∣^{2} \frac{8 M ^{2}}{m _{1}} (B 6^{M})^{2} .$ Taking $S = G$ and using $∣ G ∣ \leq d$ , the diagonal rate conversion follows from $(L^{2} Γ ℓ^{2})^{2} = L^{4} Γ^{2} ℓ^{4} \leq n ℓ^{2},$ where the inequality uses $ℓ \leq L$ and $Γ^{2} L^{6} \leq n$ . Thus $2 uv \leq u^{2} + v^{2}$ , with $u = d$ and $v = L^{2} Γ ℓ^{2}$ , gives $\frac{d L ^{2} Γ}{n ^{2}} \leq \frac{1}{2} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ℓ ^{2}}} = \frac{1}{2} R_{n, d} .$ The cross-rate conversion uses $L^{4} Γ ℓ^{2} \leq L^{4} Γ^{2} L^{2} = Γ^{2} L^{6} \leq n,$ and hence $\frac{d ^{2} L ^{4} Γ}{n ^{3}} \leq \frac{d ^{2}}{n ^{2} ℓ ^{2}} \leq R_{n, d} .$ Combining these algebraic inequalities with the preceding raw second-moment bound yields $\int W_{var}^{2} d P^{\otimes \infty} \leq K_{c} R_{n, d} .$

For the deterministic approximation term, overlap gives $q_{k} \in C_{ϵ}$ , and $k \in G$ gives $s (q_{k}) = p_{k} \leq B /4 \leq B$ . Applying Lemma 10 to the four-cell vector $q_{k}$ gives $∣ \overset{ˉ}{P}_{k} - ϕ (q_{k}) ∣ = ∣ P_{M, B} (q_{k}) - ϕ (q_{k}) ∣ \leq \frac{2 B}{ϵ M ^{2}} (k \in G) .$ Consequently $∣ W_{app} ∣ \leq d \frac{2 B}{ϵ M ^{2}} .$ The cutoff inequality $2 \leq α_{0} L$ gives $M \geq α_{0} L /2$ , while Lemma 7 gives $B \leq 8192 L / n$ and $ℓ \leq L$ . Therefore $\frac{2 B}{ϵ M ^{2}} \leq \frac{65536}{ϵ α _{0}^{2} n L} \leq \frac{65536}{ϵ α _{0}^{2} n ℓ},$ and hence, pointwise in the sample, $W_{app}^{2} \leq (\frac{65536}{ϵ α _{0}^{2}})^{2} \frac{d ^{2}}{n ^{2} ℓ ^{2}} \leq K_{b} R_{n, d} .$

For the false-light term, observe that $W_{sel} = \sum_{k \in F} S_{k} (P_{k} - ϕ (q_{k}))$ is exactly the selected false-light error of Lemma 18: the summation there ranges over the categories with $p_{k} > B /4$ , which is the set $F$ . Its hypotheses hold in the present case: the overlap condition $ϵ \leq π_{k} \leq 1 - ϵ$ holds for every category of positive mass because $P^{\otimes n} \in E_{n, d, ϵ}$ , the calibration cutoff $n \geq N_{0}$ is the standing assumption of this case, and $L \geq 240$ was derived above from the cutoff property and the numerical value of $α_{0}$ . Since $W_{sel}$ is a function of the first $n$ observations, Lemma 20 makes its second moment under $P^{\otimes \infty}$ equal to its second moment under $P^{\otimes n}$ , and Lemma 18 gives directly $\int W_{sel}^{2} d P^{\otimes \infty} = E_{P^{\otimes n}} [W_{sel}^{2}] \leq 8 (e + 1) 819 2^{2} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ℓ ^{2}}} = K_{f} R_{n, d} .$

The bound for $W_{var}$ is obtained on the infinite-product representation of the iid sample and transported to $P^{\otimes n}$ by Lemma 20, which identifies the law of the first $n$ coordinates and hence equates the integrals of functions of those coordinates. Using $(x + y + z)^{2} \leq 3 (x^{2} + y^{2} + z^{2})$ , the pointwise bound on $W_{app}^{2}$ , and the two second-moment bounds, we obtain $\int ⎩ ⎨ ⎧ T_{L} - k \in L_{n} \sum ϕ (q_{k}) ⎭ ⎬ ⎫^{2} d P^{\otimes n} \leq 3 \int (W_{var}^{2} + W_{app}^{2} + W_{sel}^{2}) d P^{\otimes n} \leq 3 (K_{c} + K_{b} + K_{f}) R_{n, d} = C_{ϵ} R_{n, d} .$ Since $μ_{n} = P^{\otimes n}$ , this is the desired bound under $μ_{n}$ .

If $n < N_{0}$ , then $L_{n} = \emptyset$ by Definition 9. The light contribution and its selected target are both zero, so the left-hand side is zero. Since $R_{n, d} \geq 0$ , the same bound holds in this case.

∎

Lemma 19 establishes that the count-based hybrid estimator is computable with operation count linear in $d$ and polynomial in $M (n)$ , and that the light-cell contribution attains the same rate as the heavy-cell branch under the displayed dimension range. Together with Lemma 15, it gives the upper envelope used in Theorem 1 and Theorem 2.

Verification note

This appendix records the verification boundary for the finite-alphabet product-law formulation used throughout the paper. The formal development represents the observed-data experiment in two compatible ways: a finite single-observation law for $O = (X, A, Y)$ , as used in Assumption 1 and Definition 2, and an ambient infinite iid sample sequence from which finite sample segments can be extracted. The following statement gives the bridge between those two views.

Lemma 20 [lem:ambient-sample-marginal] (Ambient sample marginal law).

Let $P$ be a probability law on a measurable single-observation space, and let $n \in N$ . Write $P^{\otimes \infty}$ for the infinite product law on sequences $(O_{i})_{i \geq 0}$ , and write $P^{\otimes n}$ for the finite product law on $n$ -tuples. Then the coordinate restriction map $(O_{i})_{i \geq 0} ⟼ (O_{i})_{i \in {0, \dots, n - 1}}$ pushes $P^{\otimes \infty}$ forward to $P^{\otimes n}$ : $(P^{\otimes \infty}) \circ ((O_{i})_{i \geq 0} \mapsto (O_{i})_{i \in {0, \dots, n - 1}})^{- 1} = P^{\otimes n} .$ In particular, for the observed-data laws $P$ used in Assumption 1, the initial sample segment has the $n$ -fold product law $P^{\otimes n}$ appearing in Definition 2.

⊢ Lean

Proof of Lemma 20.

Let $Ω = X^{N}, μ_{\infty} = P^{\otimes \infty}, Z_{i} (ω) = ω_{i} .$ By the construction of the infinite product measure, the coordinate process $(Z_{i})_{i \geq 0}$ is independent and each coordinate has marginal law $P$ : $(Z_{i})_{#} μ_{\infty} = P for every i \in N .$

For fixed $n$ , define the finite coordinate map $C_{n} (ω) = (Z_{i} (ω))_{i \in Fin (n)} = (ω_{i})_{i = 0}^{n - 1} .$ The finite-dimensional law of an independent process is the product of its one-dimensional marginals, hence $(C_{n})_{#} μ_{\infty} = i \in Fin (n) ⨂ (Z_{i})_{#} μ_{\infty} = i \in Fin (n) ⨂ P = P^{\otimes n} .$

This is exactly $(P^{\otimes \infty}) \circ C_{n}^{- 1} = P^{\otimes n} .$ Taking $X$ to be the observed-data alphabet and $P$ to be the single-observation law in Assumption 1 gives the $n$ -fold product law used in Definition 2.

∎

Lemma 20 justifies using an infinite iid product space as an ambient construction while retaining the finite-sample experiment class in Definition 2 as the law governing $O_{1}, \dots, O_{n}$ . This connection is useful for statements that are naturally organized around coordinate projections, while the statistical risk in Definition 6 remains the finite- $n$ mean-squared risk under $P^{\otimes n}$ .

The verification covers the finite-alphabet iid observational model, the potential-outcome overlay, the overlap-restricted four-cell cone, the cell functional, the ATE functional, the minimax risk, the deterministic split counts, and the hybrid estimator defined in Assumption 1, Assumption 2, Definition 3, Definition 4, Definition 5, Definition 6, Definition 7, and Definition 9. The auxiliary proof layer verifies the estimator, approximation, calibration, residual, missing-arm, factorial-moment, and aggregation statements used by the main rate theorems. The theorem statements and the proofs written in this paper are machine-checked in Lean 4. That check covers the steps carried out here, including each step in which a published conclusion is invoked, and it stops at the boundary of any such conclusion: the source proof behind a cited input is not itself formalized, and a theorem depending on one is certified conditionally on it. The theorem-local verification footnotes name the published conclusions entering in this way, so a reader can see for each result which published input, if any, its certificate rests on.

Proofs of the main results

Proof of Theorem 1.

Fix an overlap level $0 < ϵ < 1/2$ , and use the theorem’s cited fixed-sample control-zero one-arm minimax lower-bound input at this overlap level. Write $r_{n, d} = \frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}} .$

First derive the fixed-interior upper envelope for the hybrid estimator. From Lemma 19 choose constants $C_{L}, c_{L} > 0$ such that, whenever $P^{\otimes n} \in E_{n, d, ϵ}$ and $d \leq c_{L} n lo g n$ , $E_{P^{\otimes n}} ⎩ ⎨ ⎧ T_{L} - k \in L_{n} \sum ϕ (q_{k}) ⎭ ⎬ ⎫^{2} \leq C_{L} r_{n, d} .$ From Lemma 15 choose $C_{H}, c_{H} > 0$ and $N_{H} < \infty$ such that, whenever $n \geq N_{H}$ , $P^{\otimes n} \in E_{n, d, ϵ}$ , and $d \leq c_{H} n lo g n$ , $E_{P^{\otimes n}} ⎩ ⎨ ⎧ T_{H} - k \in H_{n} \sum ϕ (q_{k}) ⎭ ⎬ ⎫^{2} \leq C_{H} r_{n, d} .$ Set $C_{up} = 2 (C_{L} + C_{H}), ρ_{up} = min {c_{L}, c_{H}}, N_{up} = N_{H} .$ For a sample array $o_{1 : n}$ , define the pilot targets $T_{H}^{\circ} (P, o_{1 : n}) = k \in H_{n} (o_{1 : n}) \sum ϕ (q_{k}), T_{L}^{\circ} (P, o_{1 : n}) = k \in L_{n} (o_{1 : n}) \sum ϕ (q_{k}) .$ The sets $H_{n} (o_{1 : n})$ and $L_{n} (o_{1 : n})$ partition ${1, \dots, d}$ , hence $T_{H}^{\circ} (P, o_{1 : n}) + T_{L}^{\circ} (P, o_{1 : n}) = k = 1 \sum d ϕ (q_{k}) = τ (P),$ where the last equality is Definition 5. The interval bound needed for truncation follows from the cell formula. For each category, write $p_{k} = a, y \in {0, 1} \sum q_{ak y}, s_{ak} = q_{ak 0} + q_{ak 1}, μ_{ak} = q_{ak 1} / s_{ak},$ with the empty-arm value interpreted by the totalized convention $μ_{ak} = 0$ when $s_{ak} = 0$ . By Definition 4, the zero vector has $ϕ (0) = 0$ , so a zero-mass category contributes $0 = p_{k} {μ_{1 k} - μ_{0 k}}$ . On a positive-mass category satisfying overlap, the two arm masses are positive, and the displayed formula in Definition 4 gives $ϕ (q_{k}) = p_{k} {\frac{q _{1 k 1}}{s _{1 k}} - \frac{q _{0 k 1}}{s _{0 k}}} = p_{k} {μ_{1 k} - μ_{0 k}} .$ Summing this identity and using Definition 5 gives $τ (P) = k = 1 \sum d p_{k} {μ_{1 k} - μ_{0 k}} .$ Here $p_{k} \geq 0$ , $\sum_{k = 1}^{d} p_{k} = 1$ , and the totalized binary-outcome means satisfy $0 \leq μ_{ak} \leq 1$ . Therefore $∣ μ_{1 k} - μ_{0 k} ∣ \leq 1$ for every $k$ , and $∣ τ (P) ∣ \leq k = 1 \sum d p_{k} ∣ μ_{1 k} - μ_{0 k} ∣ \leq k = 1 \sum d p_{k} = 1.$ Thus $τ (P) \in [- 1, 1]$ . Let $Π_{[- 1, 1]} (x) = max {- 1, min {1, x}} .$ The elementary projection inequality ${Π_{[- 1, 1]} (x) - τ (P)}^{2} \leq {x - τ (P)}^{2}$ holds for every real $x$ . Applying it to $x = T_{H} (o_{1 : n}) + T_{L} (o_{1 : n})$ , and then using $(u + v)^{2} \leq 2 u^{2} + 2 v^{2}$ , gives the pointwise bound $(τ_{n}^{hyb} - τ (P))^{2} \leq 2 {T_{H} - T_{H}^{\circ} (P, \cdot)}^{2} + 2 {T_{L} - T_{L}^{\circ} (P, \cdot)}^{2} .$ Integrating with respect to $P^{\otimes n}$ and using the two component bounds yields, for $n \geq N_{up}$ and $d \leq ρ_{up} n lo g n$ , $E_{P^{\otimes n}} [(τ_{n}^{hyb} - τ (P))^{2}] \leq C_{up} r_{n, d} .$ Taking the supremum over $P^{\otimes n} \in E_{n, d, ϵ}$ gives the same bound for the worst-case risk of $τ_{n}^{hyb}$ . Since this estimator is a measurable estimator on the finite sample space and hence is one admissible estimator in the infimum defining $R_{n, d, ϵ}$ in Definition 6, $R_{n, d, ϵ} \leq P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{n}^{hyb} - τ (P))^{2}] \leq C_{up} r_{n, d} .$
The lower-transfer step is supplied by Lemma 2, applied with the cited fixed-sample control-zero one-arm lower-bound input of Zeng et al. (2024). Thus there are $a_{low}, ρ_{low} > 0$ and $N_{low} < \infty$ such that, for $0 < d$ , $n \geq N_{low}$ , and $d \leq ρ_{low} n lo g n$ , $a_{low} r_{n, d} \leq R_{n, d, ϵ} .$ Define $a_{ϵ} = a_{low}, ρ_{ϵ} = min {ρ_{up}, ρ_{low}}, C_{ϵ} = C_{up}, N_{ϵ} = max {N_{up}, N_{low}} .$ These constants are positive, with $N_{ϵ} < \infty$ . If $0 < d$ , $n \geq N_{ϵ}$ , and $d \leq ρ_{ϵ} n lo g n$ , then both the upper and lower ranges apply, so $a_{ϵ} r_{n, d} \leq R_{n, d, ϵ} \leq P^{\otimes n} \in E_{n, d, ϵ} sup E_{P^{\otimes n}} [(τ_{n}^{hyb} - τ (P))^{2}] \leq C_{ϵ} r_{n, d} .$ This is the sharp sandwich assertion.
Fix $K > 0$ . Set $C_{K} = C_{ϵ} (1 + K^{2}) .$ Then $C_{K} > 0$ . Suppose $0 < d$ , $n \geq N_{ϵ}$ , $d \leq K n lo g n$ , and $d \leq ρ_{ϵ} n lo g n$ . The sample size is positive by the displayed range: if $n = 0$ , then $K n lo g n = 0$ , contradicting $0 < d \leq K n lo g n$ . If $lo g n \leq 0$ , then $K n \geq 0$ and therefore $K n lo g n \leq 0$ , again contradicting $0 < d \leq K n lo g n$ . Thus $lo g n > 0$ . With both sides of $d \leq K n lo g n$ nonnegative, squaring gives $d^{2} \leq K^{2} n (lo g n)^{2} .$ Dividing by the positive denominator $n^{2} (lo g n)^{2}$ gives $\frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}} \leq \frac{K ^{2}}{n} .$ Hence $r_{n, d} = \frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}} \leq \frac{1 + K ^{2}}{n} .$ The lower side of the sandwich gives $\frac{a _{ϵ}}{n} \leq a_{ϵ} r_{n, d} \leq R_{n, d, ϵ},$ and the upper side gives $R_{n, d, ϵ} \leq C_{ϵ} r_{n, d} \leq \frac{C _{ϵ} ( 1 + K ^{2} )}{n} = \frac{C _{K}}{n} .$ This proves the parametric interior assertion.
Let $n_{j}, d_{j}$ be sequences with $n_{j} \to \infty$ , with $d_{j} > 0$ eventually, and with $d_{j} \leq ρ_{ϵ} n_{j} lo g n_{j}$ eventually. Finite initial indices leave convergence unchanged, so work on the tail where $n_{j} \geq N_{ϵ}$ , $n_{j} \geq 2$ , $d_{j} > 0$ , and the displayed range condition holds. Define $η_{j} = \frac{d _{j}}{n _{j} lo g n _{j}}, r_{j} = \frac{1}{n _{j}} + η_{j}^{2} .$ On this tail, $r_{j} = r_{n_{j}, d_{j}}$ and $η_{j} \geq 0$ . The overlap class is nonempty for such $d_{j}$ : since $d_{j} > 0$ , the endpoint parametric law on ${1, \dots, d_{j}}$ with uniform category masses, treatment probability $1/2$ , and both binary response means $1/2$ has propensity $1/2$ in every positive-mass category, and therefore satisfies the $ϵ$ -overlap condition because $0 < ϵ < 1/2$ . Applying the sandwich on the tail gives $a_{ϵ} r_{j} \leq R_{n_{j}, d_{j}, ϵ} \leq C_{ϵ} r_{j} .$ If $R_{n_{j}, d_{j}, ϵ} \to 0$ , then $0 \leq r_{j} \leq a_{ϵ}^{- 1} R_{n_{j}, d_{j}, ϵ}$ eventually, so $r_{j} \to 0$ . Since $0 \leq η_{j}^{2} \leq r_{j},$ we have $η_{j}^{2} \to 0$ , and the eventual nonnegativity of $η_{j}$ gives $η_{j} \to 0$ . Conversely, if $η_{j} \to 0$ , then $1/ n_{j} \to 0$ and $η_{j}^{2} \to 0$ , so $r_{j} \to 0$ . Since minimax risks are nonnegative, the eventual bound $0 \leq R_{n_{j}, d_{j}, ϵ} \leq C_{ϵ} r_{j}$ then yields $R_{n_{j}, d_{j}, ϵ} \to 0$ . Therefore $R_{n_{j}, d_{j}, ϵ} \to 0 ⟺ \frac{d _{j}}{n _{j} lo g n _{j}} \to 0.$

∎

Proof of Theorem 2.

Computability. Use the real-arithmetic program model in which a program is a finite register list with input reads, real constants, additions, subtractions, multiplications, divisions, and branch comparisons. Input reads and constants have cost zero, while each arithmetic operation and comparison has cost one. Division is the total real-field operation, so division by a zero denominator returns zero. A branch comparison has a test expression and two branch expressions and returns the first branch when the test value is nonpositive and the second branch otherwise.

For $n, d \in N$ , the input alphabet for the program is ${0, 1} \times {1, \dots, d} \times {0, 1} \times {0, 1} .$ At input coordinate $(j, k, a, y)$ the program reads the real number $N_{ak y}^{(j)} = # {i \in I_{j} : (X_{i}, A_{i}, Y_{i}) = (k, a, y)} .$ Equivalently, the input vector is the collection of the $8 d$ split cell counts $N_{ak y}^{(j)}$ . Sums and products below are compiled as expression trees folded onto the initial constants $0$ and $1$ : a list sum has cost equal to the sum of the costs of its entries plus one addition for each entry, and a list product has cost equal to the sum of the costs of its entries plus one multiplication for each entry. Thus a four-term category count has cost $4$ , not $3$ .

If $d = 0$ , the program is the constant-zero program. Its operation count is zero, and its value agrees with $τ_{n}^{hyb}$ , since the heavy and light sums range over the empty alphabet and the truncation of zero is zero.

Now suppose $d > 0$ , and write $M = M (n)$ . A split-count input has cost zero. For a natural-valued expression $x$ , the truncated subtraction $(x - i)_{+}$ is compiled as a branch on $x - i$ , returning $0$ on the nonpositive branch and $x - i$ on the positive branch. This expression has cost $2 op (x) + 3$ . The falling factorial $x (x - 1)_{+} \dots (x - r + 1)_{+}$ is compiled by the corresponding folded product, so its cost is $r {2 op (x) + 4}$ . Therefore, for a split-count input $x$ , the falling-factorial expression of order $r$ has cost $4 r$ .

For a multi-index $r$ , the factorial monomial expression is $\frac{\prod _{a, y} ( N _{ak y}^{(1)} ) _{r_{a y}}}{( m _{1} ) _{∣ r ∣}},$ with the same total division convention as the program model. The folded product over the four cells contributes $4∣ r ∣ + 4$ operations, and the final division by the constant denominator contributes one more, giving $op {factorial monomial r} = 4∣ r ∣ + 5.$ For the multi-indices used in the arm expansion of $P_{M, B}$ , $∣ r ∣ = j + 2$ . After multiplication by its coefficient, one fixed-cell summand at level $(j, t)$ has cost $4 j + 14.$ Since $M \geq 2$ , the nested sums in one treatment arm satisfy $op {sum over (a, y) at fixed j, t} \leq 50 M,$ $op {sum over t at fixed j} \leq 51 M^{2}, op {one arm sum} \leq 52 M^{3} .$ Subtracting the two arm sums gives the light-cell expression, and hence $op {light-cell expression for category k} \leq 105 M^{4} .$

The heavy expression for category $k$ is $\frac{N _{k}^{(1)}}{m _{1}} {\frac{N _{1 k 1}^{(1)}}{N _{1 k 0}^{(1)} + N _{1 k 1}^{(1)}} - \frac{N _{0 k 1}^{(1)}}{N _{0 k 0}^{(1)} + N _{0 k 1}^{(1)}}},$ where $N_{k}^{(1)} = \sum_{a, y} N_{ak y}^{(1)}$ , again using total division at zero denominators. This expression has cost $11$ and agrees exactly with $h_{k}$ . The pilot count expression $\sum_{a, y} N_{ak y}^{(0)}$ has cost $4$ , so the comparison expression $\sum_{a, y} N_{ak y}^{(0)} - λ_{0} L$ has cost $5$ . For $n \geq N_{0}$ , the selected category expression branches to the light expression when the pilot count is at most $λ_{0} L$ and to the heavy expression when it is larger. Its cost is at most $5 + 105 M^{4} + 11 + 1 \leq 110 M^{4},$ where the final $1$ is the branch comparison itself. For $n < N_{0}$ , the selected category expression is the heavy expression, whose cost $11$ is also at most $110 M^{4}$ . Thus each selected category expression has operation count at most $110 M (n)^{4}$ .

Summing the $d$ selected category expressions uses one addition node per category in the folded sum, so the untruncated expression has cost at most $111 d M (n)^{4} .$ The truncation $x ⟼ max {- 1, min {1, x}}$ is compiled by two branch comparisons, with the relevant expression duplicated in the branch subtrees. Consequently $op {clamp (x)} = 4 op (x) + 6.$ For $d > 0$ , this gives $op (A_{n, d}) \leq 4 \cdot 111 d M (n)^{4} + 6 \leq 450 d M (n)^{4},$ because $1 \leq d M (n)^{4}$ . Together with the zero-alphabet branch, the compiled program $A_{n, d}$ satisfies $op (A_{n, d}) \leq 450 d M (n)^{4}$ and, for every sample, $A_{n, d} ((N_{ak y}^{(j)})_{j, k, a, y}) = τ_{n}^{hyb} (O_{1 : n}) .$ Taking $K = 450$ proves the computability clause.
Fixed-interior hybrid bound. Fix $0 < ϵ < 1/2$ . Let $C_{L}, c_{L} > 0$ be the constants supplied by Lemma 19, and let $C_{H}, ρ_{H} > 0$ and $N_{H} \in N$ be the constants supplied by Lemma 15. Set $C_{ϵ} = 2 (C_{L} + C_{H}), ρ_{ϵ} = min {c_{L}, ρ_{H}}, N_{ϵ} = N_{H} .$ These constants are positive in the required real coordinates.

For a sample $z = O_{1 : n}$ , define $T_{H}^{\circ} (P, z) = k \in H_{n} (z) \sum ϕ (q_{k}), T_{L}^{\circ} (P, z) = k \in L_{n} (z) \sum ϕ (q_{k}) .$ Since $L_{n} (z) = H_{n} (z)^{c}$ , $T_{H}^{\circ} (P, z) + T_{L}^{\circ} (P, z) = τ (P) .$ Also $τ (P) \in [- 1, 1]$ for every law in the overlap class. Hence the truncation map is contractive around $τ (P)$ , and $(τ_{n}^{hyb} (z) - τ (P))^{2} \leq [{T_{H} (z) - T_{H}^{\circ} (P, z)} + {T_{L} (z) - T_{L}^{\circ} (P, z)}]^{2} \leq 2 {T_{H} (z) - T_{H}^{\circ} (P, z)}^{2} + 2 {T_{L} (z) - T_{L}^{\circ} (P, z)}^{2} .$ Integrating under any $P^{\otimes n} \in E_{n, d, ϵ}$ gives $E_{P} [(τ_{n}^{hyb} - τ (P))^{2}] \leq 2 C_{H} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} + 2 C_{L} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} = C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}},$ whenever $0 < n$ , $N_{ϵ} \leq n$ , and $d \leq ρ_{ϵ} n lo g n$ . The light and heavy bounds apply because this dimension condition implies both $d \leq c_{L} n lo g n and d \leq ρ_{H} n lo g n .$ Taking the supremum over $P^{\otimes n} \in E_{n, d, ϵ}$ proves the fixed-interior calibration bound for $τ_{n}^{hyb}$ . In the auxiliary zero-alphabet case used by the selector lemma, the experiment class is empty and the displayed upper bound follows from the empty-supremum convention and nonnegativity of the rate.
Selector envelope. Apply Lemma 6 with the constants just constructed and with the hybrid bound from the previous step. For every $n, d \in N$ with $0 < n$ , $0 < d$ , $N_{ϵ} \leq n$ , and $d \leq ρ_{ϵ} n lo g n$ , the selected estimator that chooses $τ_{n}^{hyb}$ when $C_{ϵ} {\frac{1}{n} + \frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}} \leq \frac{1}{n} + 4 (1/2 - ϵ)^{2}$ and chooses $τ_{ctr}$ otherwise satisfies $R_{n, d, ϵ} \leq P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ_{C_{ϵ}, ϵ}^{sel} - τ (P))^{2}]$ and $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ_{C_{ϵ}, ϵ}^{sel} - τ (P))^{2}] \leq max {C_{ϵ}, 4} [\frac{1}{n} + min {\frac{d ^{2}}{n ^{2} ( lo g n ) ^{2}}, (1/2 - ϵ)^{2}}] .$
Centered randomization bound. Fix $0 < ϵ \leq 1/2$ , $0 < n$ , and $0 < d$ . For every $P^{\otimes n} \in E_{n, d, ϵ}$ , Lemma 3 gives $E_{P} [(τ_{ctr} - τ (P))^{2}] \leq \frac{1}{n} + 4 (1/2 - ϵ)^{2} .$ The right-hand side is independent of $P$ , so taking the supremum over the experiment class gives $P^{\otimes n} \in E_{n, d, ϵ} sup E_{P} [(τ_{ctr} - τ (P))^{2}] \leq \frac{1}{n} + 4 (1/2 - ϵ)^{2} .$ The same conclusion covers the empty-class branch through the same empty-supremum convention.
Endpoint bracket. For $0 < n$ and $0 < d$ , Lemma 5 gives directly $\frac{1}{100 n} \leq R_{n, d, 1/2} \leq \frac{1}{n} .$ This is the endpoint bracket.

∎

References

Zhenghao Zeng and Sivaraman Balakrishnan and Yanjun Han and Edward H. Kennedy (2024). Causal Inference with High-dimensional Discrete Covariates. arXiv preprint arXiv:2405.00118. doi
Jiantao Jiao and Venkat, Kartik and Yanjun Han and Weissman, Tsachy (2015). Minimax Estimation of Functionals of Discrete Distributions. IEEE Transactions on Information Theory. doi
Han, Yanjun and Jiao, Jiantao and Weissman, Tsachy (2020). Minimax Estimation of Divergences Between Discrete Distributions. IEEE Journal on Selected Areas in Information Theory. doi
Wu, Yihong and Yang, Pengkun (2016). Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation. IEEE Transactions on Information Theory. doi
Liu, Lin and Mukherjee, Rajarshi and Newey, Whitney K. and Robins, James M. (2017). Semiparametric Efficient Empirical Higher Order Influence Function Estimators. arXiv preprint arXiv:1705.07577. doi
Rubin, Donald B. (1974). Estimating Causal Effects of Treatments in Randomized and Nonrandomized Studies. Journal of Educational Psychology. doi
Rosenbaum, Paul R. and Rubin, Donald B. (1983). The Central Role of the Propensity Score in Observational Studies for Causal Effects. Biometrika. doi
Hahn, Jinyong (1998). On the Role of the Propensity Score in Efficient Semiparametric Estimation of Average Treatment Effects. Econometrica. doi
Hirano, Keisuke and Imbens, Guido W. and Ridder, Geert (2003). Efficient Estimation of Average Treatment Effects Using the Estimated Propensity Score. Econometrica. doi
Robins, James M. and Rotnitzky, Andrea and Zhao, Lue Ping (1994). Estimation of Regression Coefficients When Some Regressors Are Not Always Observed. Journal of the American Statistical Association. doi
Bang, Heejung and Robins, James M. (2005). Doubly Robust Estimation in Missing Data and Causal Inference Models. Biometrics. doi
van der Laan, Mark J. and Rubin, Daniel (2006). Targeted Maximum Likelihood Learning. The International Journal of Biostatistics. doi
Robins, James M. and Ritov, Ya'acov (1997). Toward a Curse of Dimensionality Appropriate {(CODA)} Asymptotic Theory for Semi-Parametric Models. Statistics in Medicine. doi
Belloni, Alexandre and Chernozhukov, Victor and Fern{\'a}ndez-Val, Iv{\'a}n and Hansen, Christian (2017). Program Evaluation and Causal Inference with High-Dimensional Data. Econometrica. doi
Chernozhukov, Victor and Chetverikov, Denis and Demirer, Mert and Duflo, Esther and Hansen, Christian and Newey, Whitney and Robins, James (2018). Double/Debiased Machine Learning for Treatment and Structural Parameters. The Econometrics Journal. doi
Chernozhukov, Victor and Newey, Whitney K. and Singh, Rahul (2022). Automatic Debiased Machine Learning of Causal and Structural Effects. Econometrica. doi
D'Amour, Alexander and Ding, Peng and Feller, Avi and Lei, Lihua and Sekhon, Jasjeet (2021). Overlap in Observational Studies with High-Dimensional Covariates. Journal of Econometrics. doi
Jin, Jikai and Syrgkanis, Vasilis (2025). Structure-Agnostic Optimality of Doubly Robust Learning for Treatment Effect Estimation. arXiv preprint arXiv:2402.14264. doi
Bickel, Peter J. and Klaassen, Chris A. J. and Ritov, Ya'acov and Wellner, Jon A. (1993). Efficient and Adaptive Estimation for Semiparametric Models. Springer.
van der Vaart, Aad W. (1998). Asymptotic Statistics. Cambridge University Press.
Tsybakov, Alexandre B. (2009). Introduction to Nonparametric Estimation. Springer. doi
Lepski, O. and Nemirovski, A. and Spokoiny, V. (1999). On estimation of the L r norm of a regression function. Probability Theory and Related Fields. doi
Cai, T. Tony and Low, Mark G. (2011). Testing Composite Hypotheses, Hermite Polynomials and Optimal Estimation of a Nonsmooth Functional. The Annals of Statistics. doi
Robins, James M. and Li, Lingling and Tchetgen Tchetgen, Eric J. and van der Vaart, Aad W. (2008). Higher Order Influence Functions and Minimax Estimation of Nonlinear Functionals. Probability and Statistics: Essays in Honor of David A. Freedman. doi
Robins, James M. and Tchetgen Tchetgen, Eric J. and Li, Lingling and van der Vaart, Aad W. (2009). Semiparametric Minimax Rates. Electronic Journal of Statistics. doi
Robins, James M. W. and Li, Lingling and Mukherjee, Rajarshi and Tchetgen Tchetgen, Eric J. and van der Vaart, Aad (2017). Minimax Estimation of a Functional on a Structured High-Dimensional Model. The Annals of Statistics. doi
Kennedy, Edward H. and Balakrishnan, Sivaraman and Robins, James M. and Wasserman, Larry (2024). Minimax Rates for Heterogeneous Causal Effect Estimation. The Annals of Statistics. doi
Balakrishnan, Sivaraman and Kennedy, Edward H. and Wasserman, Larry (2023). The Fundamental Limits of Structure-Agnostic Functional Estimation. arXiv preprint arXiv:2305.04116. doi
Fisher, Ronald A. and Corbet, A. Steven and Williams, C. B. (1943). The Relation Between the Number of Species and the Number of Individuals in a Random Sample of an Animal Population. The Journal of Animal Ecology. doi
Good, I. J. and Toulmin, G. H. (1956). The Number of New Species, and the Increase in Population Coverage, When a Sample Is Increased. Biometrika. doi
Efron, Bradley and Thisted, Ronald (1976). Estimating the Number of Unseen Species: How Many Words Did Shakespeare Know?. Biometrika. doi
Paninski, Liam (2003). Estimation of Entropy and Mutual Information. Neural Computation. doi
Valiant, Gregory and Valiant, Paul (2011). Estimating the unseen. Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. doi
Valiant, Gregory and Valiant, Paul (2017). Estimating the Unseen. Journal of the ACM. doi
Orlitsky, Alon and Suresh, Ananda Theertha and Wu, Yihong (2016). Optimal Prediction of the Number of Unseen Species. Proceedings of the National Academy of Sciences. doi
Wu, Yihong and Yang, Pengkun (2019). Chebyshev Polynomials, Moment Matching, and Optimal Estimation of the Unseen. The Annals of Statistics. doi
Han, Yanjun and Jiao, Jiantao and Weissman, Tsachy (2015). Minimax Estimation of Discrete Distributions Under \<inline-formula\> \<tex-math notation="LaTeX"\>$\ell _1$ \</tex-math\>\</inline-formula\> Loss. IEEE Transactions on Information Theory. doi

Formal layer — Lean correspondence

Every object below is formalized in Lean 4. Click a verified row to view its statement; the rest link to the Lean source.

Setups (4)

Setup S-1 — Finite-alphabet i.i.d. observational world, in TWO explicitly bridged views. (a) CANONICAL / statement view: one observed unit is O = (X, A, Y) : Fin d x Bool x Bool; the single-observation law P is a probability Measure (built from a PMF) on that finite type with ARBITRARY cell masses; the n-sample law is the finite i.i.d. product Measure.pi (fun _ : Fin n => P), and every statement, estimator (a measurable Fin n -> Obs -> R) and the minimax inf/sup live HERE. (b) AMBIENT view, used only to import IIDSample-typed Causalean declarations: the infinite i.i.d. product Omega_inf = (ℕ -> Obs) with mu_inf = MeasureTheory.Measure.infinitePi (fun _ : ℕ => P), whose coordinate process Z i omega = omega i is a genuine Causalean.Stat.IIDSample (ℕ -> Obs) Obs mu_inf P. BRIDGE (both directions available, in scope, for arbitrary P): Causalean.Stat.iidSample_finN_pushforward pushes mu_inf forward along the first-n-coordinates map onto Measure.pi (fun _ : Fin n => P), so any event/integral of the first n coordinates has equal mass in the two views. Primitives p_k = P(X=k), pi_k = P(A=1|X=k), mu_{ak} = E[Y|A=a,X=k], q_{aky} = P(X=k,A=a,Y=y) and the four-cell vector q_k are DERIVED real-valued readouts of the single-observation law P (finite sums over atoms), not independent fields. Scalars epsilon in (0,1/2], c in (0,inf) are plain reals. — HIGHEST-LEVERAGE REUSE DECISION, and the closest analogue in the library. Causalean.Estimation.MinimaxATE.Model realizes ALMOST exactly this world: Obs C = C x Bool x Bool over a Fintype C, binary treatment and binary outcome, obsReal/obsPMF/obsLaw the single-observation law, productLaw = Measure.pi over Fin n, nMSE the n-sample MSE, minimaxMiss the sup-over-class miss, plus the Chebyshev/Markov bridge nMiss_sq_le_nMSE. BLOCKING MISMATCH (verified by reading Causalean/Estimation/MinimaxATE/Model.lean lines 87-89 and 137-138): obsReal HARDCODES a UNIFORM covariate marginal (Fintype.card C)^{-1}, and ate g averages with the same uniform weights. This note's entire d^2/(n^2 log^2 n) rate is driven by ARBITRARY, in particular rare, cell masses p_k, so the uniform-P_X model is a strictly different (and for this result degenerate) world -> NOT a verbatim reuse; define-local a p_k-parameterized law in Basic.lean, keeping the Obs/productLaw/nMSE naming and construction pattern one-to-one so F3 can port MinimaxATE proof idioms. IIDSample BRIDGE (round-2 correction FLAG-IIDSample-world; see decisions.iid_world_is_finite_product_with_infinite_ambient_view). Causalean.Stat.IIDSample is the sampling primitive the concentration engines are typed over (Concentration.hoeffding_ge : (S : IIDSample Omega X mu P) -> ... -> mu.real {omega | eps <= S.sampleMean f n omega - integral f} <= exp(...), verified at Stat/Concentration/TailBounds/Hoeffding.lean:87-91), but it is a structure over an AMBIENT mu carrying an ℕ-INDEXED process Z : ℕ -> Omega -> X with iIndepFun Z mu (Stat/Sample.lean:42-48). The finite coordinate process of Measure.pi (fun _ : Fin n => P) is Fin n-indexed and therefore CANNOT itself be an IIDSample -- the prior plan's claim that this world 'exposes an IIDSample view of the product law' was wrong, and PiTransport does not repair it (iidSample_finN_pushforward CONSUMES an IIDSample to produce the finite product, it does not produce one). The world therefore carries view (b) EXPLICITLY: Basic.lean defines iidOfInfinitePi (P) : IIDSample (ℕ -> Obs) Obs (Measure.infinitePi (fun _ : ℕ => P)) P with Z := fun i omega => omega i, meas := measurable_pi_apply, indep := ProbabilityTheory.iIndepFun_infinitePi (fun _ => measurable_id), identDist/law := MeasureTheory.Measure.infinitePi_map_eval -- COMPILED 0-sorry against this repo's pinned Mathlib, so this is a verified ~10-line def, not a conjecture -- together with the transport corollary finProductLaw_eq_map : (Measure.infinitePi (fun _ : ℕ => P)).map (fun omega (k : Fin n) => omega k) = Measure.pi (fun _ : Fin n => P), which is Causalean.Stat.iidSample_finN_pushforward APPLIED to iidOfInfinitePi (its Z k omega = omega k reduces definitionally). F3's usage pattern for every IIDSample-typed engine: state the target event as a measurable set E in Set (Fin n -> Obs), apply the engine on Omega_inf, then move the bound across with Causalean.Stat.event_pullback_along_iidSample / Measure.map_apply. This holds for ARBITRARY P (infinitePi needs only IsProbabilityMeasure P, which the PMF construction supplies), so it adds NO hypothesis to any statement and imposes no restriction on the cell masses -- exactly the point of keeping the finite product as the canonical statement world. Search trace for the bridge: loogle 'MeasureTheory.Measure.infinitePi' and 'ProbabilityTheory.iIndepFun _ (MeasureTheory.Measure.infinitePi _)' -> Measure.infinitePi / infinitePi_map_eval / measurePreserving_eval_infinitePi (Mathlib.Probability.ProductMeasure) and iIndepFun_infinitePi (Mathlib.Probability.Independence.InfinitePi), all four #check-confirmed present in the pinned toolchain; globbed Causalean//Sample//*.lean -> PiTransport.lean is the ONLY Sample bridge file and carries only the IIDSample -> Measure.pi direction (read in full, 93 lines) -> the finite-to-infinite view is absent from Causalean and is built here. Search trace: read ../doc/API.md sections '## 13sa. Estimation/MinimaxATE/' and '## 12. Stat/' + '### 12a. Stat/Sample.lean'; grepped Causalean/Estimation/MinimaxATE/Model.lean for structure/def/theorem; grepped Causalean for 'alphabet' -> no large-alphabet / arbitrary-discrete-mass observational model found.
Setup S-2 — Potential-outcome overlay on S1: binary potential outcomes Y(0), Y(1) : Omega -> Bool on the same finite probability space as (X, A, Y), with consistency (Y = Y(A) a.s.) and conditional exchangeability ((Y(0),Y(1)) indep A | X). Used only by the witness cluster; the estimation/minimax cluster is stated on the observed-data law alone. — Causalean.PO (POSystem, PO.Assumptions.Consistency, PO.Assumptions.IndepCF) is the framework analogue but is regime/graph-indexed over general measurable outcome spaces -- far heavier than the two-point binary overlay needed here, where def:two-category-witness supplies its OWN explicit full-data coupling ((Y(0),Y(1)) = (0, 1{X=1}), then A | X=k ~ Bernoulli(pi_k)) and prop:two-category-confounding VERIFIES consistency/exchangeability on it directly. Define-local over Mathlib with naming aligned to Causalean.PO. Search trace: read ../doc/API.md '## 8h. PO/' index (PO/Core/Regime, PO/Core/System, PO/Assumptions/Consistency, PO/Assumptions/IndepCF, PO/ID/Exact/ATE); no finite-alphabet binary PO overlay to reuse verbatim -> not found.
Setup S-3 — Functional / experiment-class / risk layer over S1: the overlap-restricted four-cell cone C_eps as a Set of four-vectors, the homogeneous cell contribution phi, the ATE functional tau(P) = sum_k phi(q_k), the experiment class E_{n,d,eps} of overlap-satisfying product laws, and the minimax risk R_{n,d,eps} = inf over measurable estimators of the sup-over-class MSE. — The risk shape (inf over measurable estimators of sup over a class of the n-sample MSE) is exactly Causalean.Estimation.MinimaxATE.Model's minimaxMiss/nMSE pattern, but over the p_k-parameterized class of S1 rather than the uniform-P_X structure-agnostic class, and in MSE (not miss-probability) form -> define-local, importing nMiss_sq_le_nMSE's Markov-bridge idiom. Search trace: grepped ../doc/API.md for 'Minimax' -> Stat/Minimax/{TotalVariation,LeCam,Pinsker,Scheffe,ChiSquared,ChiSquaredFinite,MinimaxRisk,Fano,Assouad,Mixture} and Estimation/MinimaxATE; Stat/Minimax/MinimaxRisk.lean supplies the two-point REDUCTIONS (reused by lem:one-category-bernoulli-lower) but carries no packaged inf-sup minimax-risk DEFINITION over a law class -> the risk def is not found and is build-inline.
Setup S-4 — Estimator layer over S1: the balanced deterministic split I_0 = {1..floor(n/2)}, I_1 = the rest; split cell counts N^{(j)}_{aky}; four-cell exponent multi-indices r in N_0^4 with |r| = sum r_{ay}; the falling factorial z_r; the pilot-certified heavy/light partition (Hhat_n, Lhat_n); the light-cell factorial-moment polynomial contribution That_L; and the truncated hybrid tauhat_n^hyb. — z_r is Mathlib's Nat.descFactorial (z_r = z.descFactorial r, with z_0 = 1 definitional) -- REUSED, not redefined; Causalean.Stat.injectiveTupleCount_eq_descFactorial (Stat/UStatistic/OrderM/Basic.lean) is the exact combinatorial bridge 'ordered injective tuple count = falling factorial' that the note's eq (9) unbiasedness E[U_{k,r}] = q_k^r rests on, and is reused as the counting engine in Helpers/FactorialMoments.lean. Causalean.Stat.SampleSplit / OneShotSplit is the analogue for the two-fold split but is a RANDOM cross-fitting split over a growing index family; the note fixes a DETERMINISTIC balanced split I_0/I_1 of Fin n, so the split itself is a two-line Finset definition -> build-inline. Search trace: grepped ../doc/API.md for 'descFactorial|fallingFactorial' -> Stat/UStatistic/OrderM/Basic.lean only; grepped ../doc/API.md and Causalean/ for 'factorial moment' -> not found (no factorial-moment unbiased-lift estimator layer exists); grepped Causalean for 'Chebyshev' (case-insensitive) -> all 15 hits are Chebyshev's INEQUALITY (Experimentation/DesignBased/Chebyshev.lean, Stat/Concentration, Mathlib/InformationTheory/Fano), none is the Chebyshev POLYNOMIAL; Mathlib's Polynomial.Chebyshev.T (Mathlib.RingTheory.Polynomial.Chebyshev, confirmed via loogle with T_one/T_mul/T_natAbs) is the reused primitive for T_M.

Definitions (7)

Definition P-1 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.ExperimentClass $\mathcal E_{n,d,\epsilon}:=\{P^{\otimes n}: P\in\mathsf{Prob}(\{1,\ldots,d\}\times\{0,1\}^2),\ n,d\in\mathbb N,\ 0<\epsilon\le1/2,\text{ and }P\text{ satisfies }\mathrm{ass:overlap}\}$ .
Definition P-2 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.overlapCone $\mathcal C_\epsilon:=\{u=(u_{00},u_{01},u_{10},u_{11})\in\mathbb R_+^4: \epsilon(u_{00}+u_{01}+u_{10}+u_{11})\le u_{10}+u_{11}\le(1-\epsilon)(u_{00}+u_{01}+u_{10}+u_{11})\}$ .
Definition P-3 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.cellPhiOnCone For $u=(u_{00},u_{01},u_{10},u_{11})\in\mathcal C_\epsilon$ , define $\phi(u):=(u_{00}+u_{01}+u_{10}+u_{11})\left[\frac{u_{11}}{u_{10}+u_{11}}-\frac{u_{01}}{u_{00}+u_{01}}\right]$ when $u\neq0$ , and define $\phi(0,0,0,0):=0$ .
Definition P-4 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.ateFunctional $\tau(P):=\sum_{k=1}^{d}p_k(\mu_{1k}-\mu_{0k})=\sum_{k=1}^{d}\phi(q_k)$ .
Definition P-5 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.hybridEstimator With the deterministic splits $I_0,I_1$ , split sizes $m_j$ , scale $L=\log(en)$ , and split cell counts $N^{(j)}_{aky}$ of def:sample-splits: Set $A=6$ , and put $\lambda_0=256$ , $b_0=4096$ , $D_A=8\log(9A/8)=8\log(27/4)$ , and $\alpha_0=\min\left\{1,\frac1{32\log A},\frac1{256D_A}\right\}.$ For $n\ge2$ , put $M(n)=\max\{2,\lfloor\alpha_0L\rfloor\}$ and $B(n)=b_0L/m_1$ . Let $N_0$ be the least numerical cutoff such that, for every $n\ge N_0$ , $\alpha_0L\ge2$ , $4M(n)^2\le m_1$ , and $4M(n)/m_1\le3B(n)/4$ . For $n\ge N_0$ , abbreviate $M=M(n)$ , $B=B(n)$ , and set $\widehat{\mathcal H}_n=\left\{k:\sum_{a,y}N^{(0)}_{aky}>\lambda_0L\right\},\qquad \widehat{\mathcal L}_n=\widehat{\mathcal H}_n^c.$ Put $N_k^{(1)}=\sum_{a,y}N^{(1)}_{aky}$ , $N_{ak}^{(1)}=\sum_yN^{(1)}_{aky}$ , and $\widehat h_k=\frac{N_k^{(1)}}{m_1}\left\{\frac{N^{(1)}_{1k1}}{N^{(1)}_{1k}}\mathbf1\{N^{(1)}_{1k}>0\}-\frac{N^{(1)}_{0k1}}{N^{(1)}_{0k}}\mathbf1\{N^{(1)}_{0k}>0\}\right\}.$ Define $H_M(x)=\{1-T_M(1-2x)\}/(2M^2)$ , $E_M(x)=H_M(x)/x$ , and $G_M(x)=\{1-E_M(x)\}/x$ , using polynomial continuation at zero, and $P_{M,B}(u)=\frac{s(u)t_1(u)}B G_M\!\left(\frac{s_1(u)}B\right)-\frac{s(u)t_0(u)}B G_M\!\left(\frac{s_0(u)}B\right).$ Here $s_a(u)=u_{a0}+u_{a1}$ , $s(u)=s_0(u)+s_1(u)$ , $t_1(u)=u_{11}$ , and $t_0(u)=u_{01}$ . Expand $P_{M,B}(u)=\sum_{|r|\le M}c_ru^r$ , set $\widehat P_k=\sum_{|r|\le M}c_r\frac{\prod_{a,y}(N^{(1)}_{aky})_{r_{ay}}}{(m_1)_{|r|}},\quad \widehat T_{\mathcal H}=\sum_{k\in\widehat{\mathcal H}_n}\widehat h_k,\quad \widehat T_{\mathcal L}=\sum_{k\in\widehat{\mathcal L}_n}\widehat P_k,$ and define $\widehat\tau_n^{\mathrm{hyb}}=\max\{-1,\min(1,\widehat T_{\mathcal H}+\widehat T_{\mathcal L})\}$ . For $n<N_0$ , set $\widehat{\mathcal L}_n=\varnothing$ and use the ratio branch on every category. The estimator uses no overlap constant and is computable in $O(dM^4)$ arithmetic operations.
Definition P-6 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.minimaxRisk $\mathsf R_{n,d,\epsilon}:=\inf_{\widehat\tau}\sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}}E_P[(\widehat\tau-\tau(P))^2]$ , where the infimum is over measurable estimators based on $O_1,\ldots,O_n$ .
Definition def:sample-splits verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.splitCellCount For a sample $O_1,\ldots,O_n$ with $O_i=(X_i,A_i,Y_i)\in\{1,\ldots,d\}\times\{0,1\}\times\{0,1\}$ , define the deterministic half-sample splits, their sizes, and the logarithmic scale $I_0=\{1,\ldots,\lfloor n/2\rfloor\},\qquad I_1=\{\lfloor n/2\rfloor+1,\ldots,n\},\qquad m_j=|I_j|,\qquad L=\log(en),$ and, for each split $j\in\{0,1\}$ , treatment arm $a\in\{0,1\}$ , category $k\in\{1,\ldots,d\}$ , and outcome $y\in\{0,1\}$ , the split cell count $N^{(j)}_{aky}=\#\{i\in I_j:(A_i,X_i,Y_i)=(a,k,y)\}.$

Assumptions (4)

Assumption A-1 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.IidSampling 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.
Assumption A-2 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.Overlap $\epsilon\le\pi_k\le1-\epsilon$ for every $k$ with $p_k>0$ .
Assumption A-3 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.Consistency $Y=Y(A)$ almost surely.
Assumption A-4 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.ConditionalExchangeability $(Y(0),Y(1))\perp A\mid X$ .

Lemmas (21)

Lemma L-1 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.light_cell_polynomial There are constants $C_\epsilon,c_\epsilon>0$ and a computable calibration of $def:hybrid-estimator-handle$ such that, for every $d\le c_\epsilon n\log n$ and every $P^{\otimes n}\in\mathcal E_{n,d,\epsilon}$ , its light-cell contribution $\widehat T_{\mathcal L}$ obeys $E_P\!\left[\left\{\widehat T_{\mathcal L}-\sum_{k\in\widehat{\mathcal L}_n}\phi(q_k)\right\}^2\right]\le C_\epsilon\left\{\frac{1}{n}+\frac{d^2}{n^2\log^2 n}\right\}.$ The calibration uses a polynomial approximation of $\phi$ on the overlap-restricted four-cell cone and factorial-moment monomials from $I_1$ .
Lemma L-2 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.pilot_sandwich Let $m_0\asymp n$ , $L=\log(en)$ , $\widehat{\mathcal H}=\{k:N_k^{(0)}>tL\}$ , $\widehat{\mathcal L}=\widehat{\mathcal H}^c$ , $B_-=tL/(2m_0)$ , and $B_+=2tL/m_0$ . For every $K>0$ , sufficiently large numerical $t$ gives, uniformly over $d\le cnL$ , $P\left(\widehat{\mathcal H}\not\subseteq\{k:p_k\ge B_-\}\text{ or }\widehat{\mathcal L}\not\subseteq\{k:p_k\le B_+\}\right)\le C_Kn^{-K}.$ The choice $t=256$ is valid for $K=4$ .
Lemma L-3 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.universal_heavy_cell_rate For the threshold $\lambda_0=256$ , every fixed $0<\epsilon<1/2$ admits $C_\epsilon,\rho_\epsilon>0$ and $N_\epsilon<\infty$ such that, for $n\ge N_\epsilon$ , $d\le\rho_\epsilon n\log n$ , and $P^{\otimes n}\in\mathcal E_{n,d,\epsilon}$ , $E_P\left[\left\{\widehat T_{\mathcal H}-\sum_{k\in\widehat{\mathcal H}_n}\phi(q_k)\right\}^2\right]\le C_\epsilon\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\}.$
Lemma L-4 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.ate_lower_bound_transfer For fixed $0<\epsilon<1/2$ , there are $a_\epsilon,b_\epsilon>0$ such that, for all sufficiently large $n$ and $d\le b_\epsilon n\log n$ , $\mathsf R_{n,d,\epsilon}\ge a_\epsilon\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\}.$
Lemma L-5 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.near_randomization_linear_upper Define the centered estimator $\widehat\tau_{\mathrm{ctr}}=\frac2n\sum_{i=1}^n(2A_i-1)\left(Y_i-\frac12\right).$ For every $n,d\in\mathbb N$ , every $0<\epsilon\le1/2$ , and every $P^{\otimes n}\in\mathcal E_{n,d,\epsilon}$ , $E_P[(\widehat\tau_{\mathrm{ctr}}-\tau(P))^2]\le\frac1n+4(1/2-\epsilon)^2.$
Lemma L-6 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.one_category_bernoulli_lower For every $n,d\in\mathbb N$ , $\mathsf R_{n,d,1/2}\ge1/(100n)$ .
Lemma L-7 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.randomized_endpoint_minimax For every $n,d\in\mathbb N$ , $\frac{1}{100n}\le\mathsf R_{n,d,1/2}\le\frac1n.$
Lemma L-8 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.combined_upper_envelope Fix $0<\epsilon<1/2$ and constants $C_\epsilon,\rho_\epsilon,N_\epsilon$ for which the upper bound in Theorem thm:sharp-minimax-fixed-interior holds. For $n\ge N_\epsilon$ and $d\le\rho_\epsilon n\log n$ , choose the hybrid when $C_\epsilon\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\}\le\frac1n+4(1/2-\epsilon)^2,$ and otherwise choose $\widehat\tau_{\mathrm{ctr}}$ . The selected estimator has worst-case risk at most $K_\epsilon\left[\frac1n+\min\left\{\frac{d^2}{n^2\log^2n},(1/2-\epsilon)^2\right\}\right],\qquad K_\epsilon=\max\{C_\epsilon,4\}.$
Lemma lem:calibration-consequences verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.large_calibration_bounds Let $L=\log(en)$ , $\ell=\log n$ , $M=M(n)$ , $B=B(n)$ , and $m_1=|I_1|$ . If $n\ge N_0$ and $L\ge240$ , then $0<\ell\le L\le2\ell,\qquad 0<m_1,\qquad n\le2m_1,\qquad M\le L,\qquad B\le\frac{8192L}{n},\qquad (6^{2M})^2L^6\le n.$ In particular $1/m_1\le2/n$ .
Lemma lem:ambient-sample-marginal verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.finProductLaw_eq_map Let $P$ be a single-observation law on $\{1,\ldots,d\}\times\{0,1\}^2$ and let $n\in\mathbb N$ . Write $P^{\otimes\infty}$ for the law of the ambient infinite iid sequence $(O_i)_{i\ge1}$ generated by $P$ . Then the image of $P^{\otimes\infty}$ under the coordinate restriction $(O_i)_{i\ge1}\mapsto(O_1,\ldots,O_n)$ is the $n$ -fold product law $P^{\otimes n}$ of def:experiment-class; that is, under $P^{\otimes\infty}$ the initial segment $(O_1,\ldots,O_n)$ has law $P^{\otimes n}$ .
Lemma lem:sparse-arm-expansion verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorialPolynomialContribution_eq_sparseArms Fix $n\ge N_0$ and a category $k$ , and abbreviate $M=M(n)$ , $B=B(n)$ as in def:hybrid-estimator-handle. Let $g_{M,j}$ be the coefficients of the polynomial continuation $G_M$ , so that $G_M(x)=\sum_{j=0}^{M-2}g_{M,j}x^j$ , and for an arm $a\in\{0,1\}$ , a cell index $c\in\{0,1\}^2$ , and integers $0\le t\le j$ , let $r^{a,c,j,t}$ be the four-cell exponent vector determined by $u^{r^{a,c,j,t}}=u_cu_{a1}u_{a0}^{\,t}u_{a1}^{\,j-t}$ . With the split counts $N^{(1)}_{bky}$ and split size $m_1$ of def:sample-splits, define the sparse arm contributions $\widehat A_{a,k}=\sum_{j=0}^{M-2}\sum_{t=0}^{j}\sum_{c\in\{0,1\}^2}B^{-1}g_{M,j}B^{-j}\binom jt\frac{\prod_{b,y}(N^{(1)}_{bky})_{r^{a,c,j,t}_{by}}}{(m_1)_{|r^{a,c,j,t}|}}.$ Then the factorial-moment polynomial estimate $\widehat P_k$ of def:hybrid-estimator-handle admits the sparse two-arm representation $\widehat P_k=\widehat A_{1,k}-\widehat A_{0,k}$ .
Lemma lem:factorial-moment-mean verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialPolynomialContribution_trunc Let $P$ be a single-observation law on $d$ categories and let $k$ be a category. For every $n\ge N_0$ , the factorial-moment polynomial estimate of the light-cell contribution has exact mean $E_{P^{\otimes n}}\left[\widehat P_k\right]=P_{M(n),B(n)}(q_k).$
Lemma lem:coefficient-envelope verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.cellApproxPolynomial_coeff_envelope Write $P_{M,B}(u)=\sum_r c_ru^r$ in multi-index form over the four cells. For every degree $M$ , scale $B>0$ , and nonnegative four-cell vector $v$ , the absolute-coefficient envelope obeys $\sum_r|c_r|\,v^r\le B\,6^M\max\left\{\left(\frac{s(v)}{B}\right)^2,\left(\frac{s(v)}{B}\right)^M\right\};$ in particular it is at most $B\,6^M$ whenever $s(v)\le B$ . ↗ Lean
Lemma lem:factorial-moment-variance verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialPolynomial_centered_sq_le Let $\bar P_k$ be the sparse factorial-polynomial mean of category $k$ (the exact mean of $\widehat P_k$ under the stated conditions). If $m_1>0$ , $M(n)\ge1$ , $B(n)>0$ , $4M(n)^2\le m_1$ , and the shifted mass obeys $p_k+4M(n)/m_1\le B(n)$ together with $p_k\le B(n)$ , then $E_{P^{\otimes n}}\left[\left(\widehat P_k-\bar P_k\right)^2\right]\le8(\mathrm e+1)\left\{B(n)\,6^{M(n)}\right\}^2.$
Lemma lem:factorial-moment-covariance verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialPolynomial_centered_cross_le Let $\bar P_k$ be the sparse factorial-polynomial mean of category $k$ . For distinct categories $k\ne l$ with $p_k\le B(n)$ and $p_l\le B(n)$ , if $M(n)\ge1$ , $B(n)>0$ , and $4M(n)^2\le m_1$ , then $E_{P^{\otimes n}}\left[\left(\widehat P_k-\bar P_k\right)\left(\widehat P_l-\bar P_l\right)\right]\le\frac{8M(n)^2}{m_1}\left\{B(n)\,6^{M(n)}\right\}^2.$
Lemma lem:chebyshev-reciprocal-certificate verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.cellApproxPolynomial_error Fix a degree $M\ge1$ , a scale $B$ , and $\epsilon>0$ . For every four-cell vector $u\in\mathcal C_\epsilon$ with $s(u)\le B$ , $\left|P_{M,B}(u)-\phi(u)\right|\le\frac{2B}{\epsilon M^2}.$
Lemma lem:false-light-envelope verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.selectedFalseLightError_rate Let $P$ satisfy overlap at some level $\epsilon$ and let $S_k=\mathbf 1\{k\in\widehat{\mathcal L}_n\}$ . If $n\ge N_0$ and $\log(en)\ge240$ , then the false-light target error obeys $E_{P^{\otimes n}}\left[\left\{\sum_{k:p_k>B(n)/4}S_k\left(\widehat P_k-\phi(q_k)\right)\right\}^2\right]\le8(\mathrm e+1)8192^2\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\},$ with a constant not depending on $\epsilon$ , $d$ , or $P$ .
Lemma lem:heavy-residual-bound verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_fixedRatioResidual_sq_le Let $P$ satisfy overlap at level $\epsilon>0$ , let $H$ be a deterministic set of categories with $p_k>0$ for every $k\in H$ , fix an arm $a\in\{0,1\}$ , and draw an iid $P$ -sample of size $m$ . With counts computed from this sample, the aggregate centered ratio residual $\mathcal R_a(H)=\sum_{k\in H}N_k\frac{\mathbf 1\{N_{ak}>0\}}{N_{ak}}\left\{N_{ak1}-\mu_{ak}N_{ak}\right\}$ obeys $E\left[\mathcal R_a(H)^2\right]\le\frac{2m}{\epsilon}\sum_{k\in H}p_k:$ all off-diagonal residual products cancel exactly, and the surviving diagonal loses only one factor $1/\epsilon$ through overlap.
Lemma lem:missing-arm-envelope verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_fixedMissingCount_sq_le Let $P$ satisfy overlap at level $\epsilon>0$ , fix $B>0$ and a deterministic set $H$ of categories with $p_k\ge B$ for every $k\in H$ , an arm $a$ , and an iid $P$ -sample of size $m\ge3$ . With $Z_{ak}=N_k\mathbf 1\{N_{ak}=0\}$ and $u=((m-2)/2)\epsilon$ , the missing-arm count obeys $E\left[\left(\sum_{k\in H}Z_{ak}\right)^2\right]\le m+m^2\left[\frac{|H|}{\left\{((m-2)/2)\epsilon\right\}^2B}\right]^2.$ The diagonal contributes at most $m$ ; the off-diagonal terms and the exponentially small part of the diagonal combine into the square of the mass-exponential sum $\sum_{k\in H}p_ke^{-up_k}$ , which the mass floor $p_k\ge B$ converts into the displayed envelope.
Lemma lem:factorial-product-moment verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialMonomial_mul_trunc_le Fix $n,d\in\mathbb N$ , a probability law $P$ on $\{1,\ldots,d\}\times\{0,1\}^2$ , a category $k$ , and multi-indices $r,s$ over the four treatment--outcome cells with $|r|\le|s|$ . For a multi-index $r$ , write $\mathfrak m_{k,r}=\prod_{(a,y)}\bigl(N^{(1)}_{aky}\bigr)_{r_{ay}}/(m_1)_{|r|}$ for the normalized factorial-moment monomial of category $k$ computed from the estimation split, where $(z)_t$ is the falling factorial. Assume $m_1>0$ and $4|s|^2\le m_1$ . Then $E_{P^{\otimes n}}\bigl[\mathfrak m_{k,r}\,\mathfrak m_{k,s}\bigr]\le \mathrm e\,\prod_{(a,y)}\bigl(q_{aky}\bigr)^{r_{ay}}\prod_{(a,y)}\Bigl(q_{aky}+\tfrac{|s|}{m_1}\Bigr)^{s_{ay}}.$
Lemma lem:coefficient-sum-certificate verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.gpos_bound Let $M\ge1$ and $z\ge0$ . With $g_{M,j}$ the coefficients of the polynomial continuation $G_M$ of def:hybrid-estimator-handle, the one-arm absolute coefficient sum $g_M^+(z)=\sum_{j=0}^{M-2}|g_{M,j}|\,z^j$ satisfies $g_M^+(z)\le 6^M\max\bigl\{1,;z^{M-2}\bigr\}.$

Theorems (2)

Theorem T-2 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.sharp_minimax_fixed_interior For every fixed $0<\epsilon<1/2$ , there are constants $a_\epsilon,\rho_\epsilon,C_\epsilon>0$ and $N_\epsilon<\infty$ such that, for every $n\ge N_\epsilon$ and uniformly over $d\le\rho_\epsilon n\log n$ , the balanced ratio-polynomial hybrid in $def:hybrid-estimator-handle$ satisfies $a_\epsilon\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\}\le\mathsf R_{n,d,\epsilon}\le\sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}}E_P[(\widehat\tau_n^{\mathrm{hyb}}-\tau(P))^2]\le C_\epsilon\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\}.$ Consequently, the minimax MSE has parametric order $n^{-1}$ whenever $d=O(\sqrt n\log n)$ , and, along sequences in the displayed range, it converges to zero if and only if $d=o(n\log n)$ .
Theorem T-3 verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.overlap_adaptive_universal_hybrid The following conclusions hold. $\mathrm{(i)}$ The single computable hybrid $\widehat\tau_n^{\mathrm{hyb}}$ , with $A=6$ , $\lambda_0=256$ , $b_0=4096$ , and numerical $\alpha_0$ , does not take $\epsilon$ as input. For every fixed $0<\epsilon<1/2$ , there are $C_\epsilon,\rho_\epsilon>0$ and $N_\epsilon<\infty$ such that, for every $n\ge N_\epsilon$ and $d\le\rho_\epsilon n\log n$ , $\sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}}E_P[(\widehat\tau_n^{\mathrm{hyb}}-\tau(P))^2]\le C_\epsilon\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\}.$ Thus fixed-class overlap adaptation requires no selector. $\mathrm{(ii)}$ For every $n,d\in\mathbb N$ and $0<\epsilon\le1/2$ , the centered estimator $\widehat\tau_{\mathrm{ctr}}=\frac2n\sum_{i=1}^n(2A_i-1)\left(Y_i-\frac12\right)$ satisfies $\sup_{P^{\otimes n}\in\mathcal E_{n,d,\epsilon}}E_P[(\widehat\tau_{\mathrm{ctr}}-\tau(P))^2]\le\frac1n+4(1/2-\epsilon)^2.$ $\mathrm{(iii)}$ For every $n,d\in\mathbb N$ , $\frac{1}{100n}\le\mathsf R_{n,d,1/2}\le\frac1n.$ $\mathrm{(iv)}$ Fix $0<\epsilon<1/2$ and constants $C_\epsilon,\rho_\epsilon,N_\epsilon$ from the fixed-interior upper theorem. For $n\ge N_\epsilon$ and $d\le\rho_\epsilon n\log n$ , choose the hybrid when $C_\epsilon\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\}\le\frac1n+4(1/2-\epsilon)^2,$ and otherwise choose $\widehat\tau_{\mathrm{ctr}}$ . This deterministic choice satisfies $\mathsf R_{n,d,\epsilon}\le K_\epsilon\left[\frac1n+\min\left\{\frac{d^2}{n^2\log^2n},(1/2-\epsilon)^2\right\}\right],\qquad K_\epsilon=\max\{C_\epsilon,4\}.$ $\mathrm{(v)}$ These fixed-class and endpoint conclusions do not assert a matching lower envelope for triangular arrays $\epsilon=\epsilon_n$ .

Citeds (1)

Cited result lem:zeng-one-arm-minimax-lower verified CausalSmith.Stat.DiscreteAteMinimaxLoggap.ZengOneArmMinimaxLower Fix $0<\epsilon<1/2$ . Let $\mathcal D_0^{(n,d)}(\epsilon)$ be the fixed-sample binary-outcome subclass of $\mathcal E_{n,d,\epsilon}$ consisting of laws $P^{\otimes n}$ with arbitrary masses $p_k\ge0$ , $\sum_{k=1}^d p_k=1$ , propensities satisfying $\epsilon\le\pi_k\le1-\epsilon$ on every positive-mass category, arbitrary treated response means $\mu_{1k}\in[0,1]$ , and $\mu_{0k}=0$ for every $k$ . Define $\psi_1(P)=\sum_{k=1}^d p_k\mu_{1k}$ . There are constants $a_\epsilon,b_\epsilon>0$ and $N_\epsilon<\infty$ such that, for all $n\ge N_\epsilon$ and $d\le b_\epsilon n\log n$ , $\inf_{\widehat\psi}\sup_{P^{\otimes n}\in\mathcal D_0^{(n,d)}(\epsilon)}E_P[(\widehat\psi-\psi_1(P))^2]\ge a_\epsilon\left\{\frac1n+\frac{d^2}{n^2\log^2n}\right\},$ where the infimum is over measurable estimators based on the fixed sample of size $n$ .

Auxiliary Lean lemmas (machine-checked) (99)

Definition centeredEstimator —
Definition ControlZeroClass —
Definition DiscreteLaw —
Definition minimaxRate —
Definition mse —
Definition Obs —
Definition worstCaseMSE —
Definition selectedEstimator —
Definition HybridEstimatorComputable —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredUnitScore —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredUnitScore_sq —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredEstimator_eq_scoreMean —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredUnitScore_mean —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredScore_category_identity —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.jointMass_eq_zero_of_cellMass_eq_zero —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.cellMass_sum —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredUnitScore_bias_identity —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredUnitScore_bias_bound —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredEstimator_mean —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredUnitScore_variance_le_one —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.centeredEstimator_variance_le —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.mse_eq_variance_add_sq_bias —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.mse_le_estimator_abs_sum_bound —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.oneArmMinimaxRisk_le_minimaxRisk —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.endpointParametricLaw —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.endpointParametricPertLaw —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.endpointParametricLaw_jointMass —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.endpointParametricPertLaw_jointMass —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.endpointParametricLaw_overlap —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.endpointParametricPertLaw_overlap —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.endpointParametricLaw_ate —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.endpointParametricPertLaw_ate —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.categoryIndicator —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.categoryIndicator_mean —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.pilot_count_eq_bernoulliCount —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.pilotCategory_upper_tail —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.pilotCategory_lower_tail —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.pilotBadEvent_subset_cellwise —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.pilotBadEvent_probability —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.exp_neg_mul_logScale —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.pilot_decay_bound —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.clamp_sq_error_le —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.targetHeavy_add_targetLight —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.hybrid_mse_le_component_errors —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.canonicalClassLaw —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.hybrid_upper_fixed_interior —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorial_normalization —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.overlap_adaptive_universal_hybrid_statistical —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.lightCells_eq_pilotHeavyAt_compl_of_cutoff_le —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.selected_light_mass_le_bandwidth_quarter —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.selected_light_approximation_bias —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integrable_factorialPolynomialContribution_trunc —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialPolynomialContribution_trunc —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.iidSampleShift —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.iidSampleMap —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.categoryCellLabel —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.categoryCellLabel_measurable —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.optionCellExponent —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.exponentDegree_optionCellExponent —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.categoryCellLabel_atom_mass —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.splitSize_zero_eq —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.splitSize_one_eq —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.estimationTailIndex —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.splitCellCount_eq_tail_count —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.categoryCellLabel_fiber_card —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.estimationLabelSample —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.multinomialFactorialCount_estimationLabelSample —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorialMonomial_eq_normalized_multinomialCount —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.lightCellEstimationIID —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorialMonomial_trunc_eq_iidCount —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integrable_factorialMonomial_trunc —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialMonomial_trunc —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialMonomial_mul_trunc_le —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integrable_factorialMonomial_mul_trunc —
Definition CausalSmith.Stat.DiscreteAteMinimaxLoggap.observationExponent —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.exponentDegree_observationExponent —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.estimationTail_fiber_card —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.observationExponent_fiber_count —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.multinomialFactorialCount_observationExponent —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorialMonomial_eq_normalized_observationCount —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorialMonomial_trunc_eq_observationCount —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.obsLaw_real_cellAtom —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.observationExponent_mass_prod —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialMonomial_cross_trunc —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.vectorMass_cellVector —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.vectorArmMass_cellVector —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.obsLaw_real_singleton —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.obsLaw_real_atom —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.cellVector_mem_overlapCone —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.abs_cellPhi_cellVector_le_mass —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.multiDegree_factorialExpansionIndex —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorialExpansionIndex_prod —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorialExpansionIndex_binomial_sum —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.sparseArmEnvelope_eq —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.sparseArmEnvelope_le —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.multiMonomial_mono —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_factorialMonomial_mul_shift_le —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.integral_sparse_terms_mul_shift_le —
Lemma CausalSmith.Stat.DiscreteAteMinimaxLoggap.factorialMonomial_cross_covariance_le —

Symbol realizations (Lean @realizes) (30)

P verified realized by DiscreteLaw
q_{aky} verified realized by jointMass, jointMass_mem_unitInterval
q_k verified realized by cellVector, cellVector_mem_unitCube
p_k verified realized by cellMass, cellMass_mem_unitInterval, Overlap, twoCategoryWitness
pi_k verified realized by propensity, propensity_mem_unitInterval, Overlap, twoCategoryWitness
mu_{ak} verified realized by outcomeMean, outcomeMean_mem_unitInterval, twoCategoryWitness
O_i verified realized by productLaw, ExperimentClass
n verified realized by variable@168
d verified realized by variable@168, one_category_bernoulli_lower, randomized_endpoint_minimax
epsilon verified realized by variable@169, Overlap, ExperimentClass, variable@6
c verified realized by variable@169, pilot_sandwich
k verified realized by variable@172
X verified realized by variable@174, ConditionalExchangeability, twoCategoryWitness
A verified realized by variable@174, Consistency, ConditionalExchangeability, twoCategoryWitness
Y verified realized by variable@174, Consistency
Y(a) verified realized by PotentialLaw, Consistency, ConditionalExchangeability, twoCategoryWitness
$\mathcal E_{n,d,\epsilon}$ verified realized by ExperimentClass
$\mathcal C_\epsilon$ verified realized by overlapCone
$\phi$ verified realized by cellPhiOnCone
$\tau(P)$ verified realized by ateFunctional, ateFunctional_mem_interval
$\mathsf R_{n,d,\epsilon}$ verified realized by mse, worstCaseMSE, minimaxRisk, minimaxRisk_mem_unitInterval
I_0 verified realized by splitIndices
I_1 verified realized by splitIndices
N^{(j)}_{aky} verified realized by splitCellCount
$r=(r_{ay})_{a,y\in\{0,1\}}$ verified realized by MultiIndex
z_r verified realized by fallingFactorial
$\widehat{\mathcal H}_n,\widehat{\mathcal L}_n$ verified realized by heavyCells, lightCells, heavyCells_eq_filter_of_cutoff_le, heavyCells_eq_univ_of_lt_cutoff, lightCells_eq_empty_of_lt_cutoff, lightCells_eq_compl
$\widehat T_{\mathcal L}$ verified realized by lightContribution
$\widehat\tau_n^{\mathrm{hyb}}$ verified realized by hybridEstimator
I_a verified realized by splitIndices

Proof map 22 statements · 29 edges

Sharp Minimax Rates for Average Treatment Effects with Discrete Confounding under Fixed Overlap

Abstract

Introduction

Related work

Setup and assumptions

The extrema in the minimax risk.

Computing the hybrid estimator.

Main results

Discussion and extensions

Limitations and future work.

Appendices

Proofs and auxiliary lemmas

Verification note

Proofs of the main results

References