theorem its proof invokes invoked by

CausalSmith · AI Causal Scientist — stat_discrete_ate_heterogeneity_frontier_v1 · Stat · AI reviewer score 7/10 · pinned commit b4259ac · PDF · Lean code · Slides · arXiv · GitHub

A Minimax Bracket for Average Treatment Effect Estimation with Discrete Adjustment and Bounded Heterogeneity

Abstract

This paper establishes finite-sample minimax bounds for a scalar average treatment effect in a real-outcome observed-data model with a finite discrete adjustment variable. The model imposes consistency, conditional exchangeability, and fixed overlap parameter ; allows arbitrary cell masses; fixes the known outcome scale , with conditional means in an interval of radius ; bounds conditional second central moments by ; and restricts the maximal cell-effect deviation to at most , where is the heterogeneity radius. For sample size and alphabet size , the number of adjustment cells, the paper constructs two clipped estimators and a clipped three-branch selector: a heavy–light signed Chebyshev factorial estimator for rare cells, an occupancy-weighted treated-control estimator for empirically crossed cells, and a constant-zero branch. The known-radius selector satisfies The same model class admits the lower benchmark These two bounds match in order at exact homogeneity, at the unrestricted-radius endpoint, for every fixed positive radius, in the saturated alphabet regime, and at the parametric-dominance elbows. The results give a radius-indexed minimax bracket for point-estimation mean-squared error under fixed overlap, known outcome scale , and known heterogeneity radius . The selector attaining the upper bound is a known-radius procedure: it uses as an input to choose deterministically between its polynomial, collision, and zero branches, and the regime theorem isolates the residual shrinking-radius region generated by the displayed upper and lower benchmarks.

Introduction

High-dimensional discrete adjustment creates a finite-sample tension that is absent from fixed-dimensional semiparametric calculations. The average treatment effect is identified by the usual finite-cell adjustment formula under consistency, conditional exchangeability, and overlap, but estimation can be dominated by cells in which treated and control observations rarely meet. In binary-outcome discrete adjustment, Zeng et al. (2024) give collision-estimator bounds, exact-homogeneity upper and lower rates, and unrestricted binary-outcome lower bounds in their stated regimes.

This paper establishes a finite-sample minimax bracket for the same causal target with real outcomes under a radius-indexed finite-cell model. The adjustment variable takes values with arbitrary cell masses; treatment is binary; outcomes are real-valued; overlap is fixed by ; supported arm-cell conditional means lie in ; supported arm-cell conditional second central moments are bounded by ; and the maximal supported-cell treatment-effect deviation from the average treatment effect is bounded by , where is known to the estimator. The resulting model class is in Definition 1, and the risk criterion is the clipped-estimator minimax mean-squared risk in Definition 5. The bracket becomes an exact-order rate statement at the two radius endpoints, every fixed positive radius, saturation, and the parametric-dominance elbows; the regime theorem separately identifies the residual shrinking-radius region generated by the displayed bounds.

The constructive result combines two estimators that exploit different information sources. The polynomial estimator in Algorithm 1 uses a sample split, a pilot heavy–light classification, and a signed Chebyshev factorial statistic for light cells. Its risk bound has the nonparametric scale , informed by the large-alphabet polynomial-estimation logic of Jiao et al. (2015); Wu et al. (2016). The collision estimator in Algorithm 2 averages treated-control contrasts over empirically crossed cells with occupancy weights; its risk bound contains the radius term and the crossed-cell term . The selector in Algorithm 3 chooses among these two estimators and the zero estimator using the known values of , , and .

The main upper bound, Theorem 2, shows that this selector satisfies up to the displayed overlap-dependent constant. The converse in Theorem 3 embeds binary hard experiments into the same real-outcome class. Its exact-homogeneity component supplies , and its radius-channel component supplies Together these statements give the all-alphabet bracket in Theorem 4.

The all-parameter statement is a bracket: an upper and a lower benchmark for the same minimax risk over the same model class, valid at every admissible . The bracket gives exact-order rates at exact homogeneity, the unrestricted-radius endpoint, every fixed positive radius, saturation, and the stated parametric-dominance elbows. Any divergence of the displayed upper-to-lower benchmark ratio is confined to the residual shrinking-radius wedge characterized in Theorem 5, which also exhibits a sequence inside that wedge.

The bracket has sharp implications across the named regimes. At , Proposition 2 gives the exact-homogeneity rate . At , Lemma 1 identifies the radius-indexed class with the unrestricted-radius class, and the endpoint rate becomes . For every radius bounded away from zero, and in the saturation and parametric-dominance regimes, Theorem 5 shows that the minimax risk is equivalent to the selector benchmark. The same theorem isolates the residual shrinking-radius wedge where the displayed upper and lower benchmarks can separate.

The analysis is connected to three literatures. The causal setup follows the potential-outcomes and program-evaluation tradition of Rubin (1974); Rubin (1979); Rosenbaum et al. (1983); Hahn (1998); Robins et al. (1994); van der Laan et al. (2003); Tsiatis (2006); Imbens et al. (2009); Imbens et al. (2015). The high-dimensional treatment-effect literature, including Belloni et al. (2017); Chernozhukov et al. (2018); Wager et al. (2018); Nie et al. (2021); Semenova et al. (2021); Kennedy (2022); Kennedy (2023); Yadlowsky (2022); Celentano et al. (2023); Jiang et al. (2025), motivates the role of nuisance complexity and heterogeneity in causal estimation. The polynomial branch draws on large-alphabet functional estimation and minimax testing tools from Paninski (2003); Valiant et al. (2011); Valiant et al. (2011); Valiant et al. (2016); Valiant et al. (2017); Jiao et al. (2015); Wu et al. (2016); Wu et al. (2019); Le Cam (1986); Tsybakov (2009); Cai et al. (2011); Donoho et al. (1990); Timan (1963). The verification appendix records the checked statement layer, the proof-audit status, and the attribution role of the citations.

The rest of the paper is organized as follows. The related-work section positions the selector benchmark against the published binary collision guarantee. The setup section defines the real-outcome model class, the average treatment effect, and the minimax risk. The estimator section introduces the polynomial estimator, the collision estimator, and the known-radius selector, then proves their upper bounds. The lower-bound section gives the affine and radius-channel embeddings from binary source experiments. The main-results section assembles the two-sided bracket and the matched-regime algebra. The discussion section records the residual shrinking-radius region and the scope of the bracket.

Theorem map.

Four results carry the paper, and it may help to name them before the machinery arrives. Theorem 2 is the upper bound: the known-radius selector of Algorithm 3, built from the polynomial and collision estimators, has worst-case risk at most over the whole class. Here is the selector benchmark for the constructed upper bound. Theorem 3 is the lower bound: the minimax risk is at least the capped converse benchmark proved by embedding binary hard experiments into the same real-outcome class through an affine map and a Bernoulli radius channel. Theorem 4 is the bracket, which puts the two together over a common index range. Theorem 5 is the regime theorem: it identifies the regimes where the selector and capped converse benchmarks agree in order, so that the bracket is a rate, and the residual shrinking-radius wedge where the displayed benchmarks separate. Proposition 2 specialises the bracket at and . The remaining formal statements supply ingredients for these five statements or the comparison with the published binary results.

Related work

The paper belongs to the potential-outcomes tradition in which causal parameters are defined from potential responses and identified from observed data under consistency, conditional exchangeability, and overlap. Foundational work by Rubin (1974); Rubin (1979) and Rosenbaum et al. (1983) supplies the adjustment logic behind scalar average treatment effect analysis, while Imbens et al. (2009) and Imbens et al. (2015) develop the modern econometric formulation. In this language, the present analysis studies a real-outcome observational experiment with a finite discrete confounder and asks how accurately the average treatment effect can be estimated when the adjustment distribution may place highly uneven mass across cells.

Semiparametric work gives the classical benchmark for average treatment effect estimation when the nuisance functions can be estimated with enough regularity. The efficient influence-function calculations of Hahn (1998), the propensity-score weighting and series-regression estimators of Hirano et al. (2003), inverse-probability and augmented estimation ideas associated with Robins et al. (1994), and the treatments in van der Laan et al. (2003); Tsiatis (2006); van der Vaart (1998) organize the fixed-dimensional theory around first-order regularity and variance. Three regimes should be kept apart. In fixed-dimensional efficient estimation the adjustment variable is held fixed while grows, and the semiparametric efficiency bound is attained at rate , with the alphabet treated as fixed. In high-dimensional nuisance estimation, exemplified by Belloni et al. (2017); Chernozhukov et al. (2018); Kennedy (2022); Kennedy (2023), parametric nuisance restrictions are replaced by rate and orthogonality conditions, and the alphabet enters through how well the nuisances can be learned. The regime studied here is a third one: the adjustment variable is exactly discrete, grows with , cell masses are unrestricted, and the binding constraint is combinatorial – whether a cell contains observations from both arms at all. That sparse-crossing constraint is why the risk here carries a -type term. The present paper takes a complementary minimax perspective: the adjustment variable is exactly discrete, the number and masses of cells are part of the finite-sample problem, and the risk benchmark records the price of sparse treated-control overlap within cells.

A second line of work studies treatment-effect heterogeneity and its consequences for estimation. Methods for heterogeneous treatment effects and causal forests, such as Wager et al. (2018), Nie et al. (2021), and Semenova et al. (2021), emphasize learning conditional effects or policy-relevant summaries. Related high-dimensional analyses study nuisance-estimation effects, debiasing phenomena in missing-data models, and AIPW variance behavior, including Yadlowsky (2022), Celentano et al. (2023), and Jiang et al. (2025). Here heterogeneity enters through a scalar radius that bounds the maximal cell-effect deviation around the target average effect. That radius indexes a family of same-class minimax problems: small radii favor estimators that borrow strength across cells, while larger radii make directly observed within-cell treatment-control contrasts more valuable.

The closest comparison is the discrete-adjustment minimax theory of Zeng et al. (2024). Their analysis considers a binary-outcome discrete-confounder experiment and develops lower bounds and collision-based estimation benchmarks for unrestricted heterogeneity, exact homogeneity, and approximate homogeneity. Their collision phenomena identify the sparse-cell difficulty created by requiring both treatment arms to appear in the same adjustment cell, and their binary hard experiments provide the source ingredients for the embedding arguments used later in this paper. The present results transfer and extend that logic to real outcomes under bounded conditional means and conditional second central moments, arbitrary cell masses, fixed overlap, and a known maximal heterogeneity radius, yielding a radius-indexed bracket on one observational model class.

It is worth stating their rates explicitly, since they are the benchmark against which the present contribution should be read. In the binary-outcome discrete-adjustment model with fixed overlap, Zeng et al. (2024) show that the usual regression, weighting, and doubly robust estimators have mean-squared error of order whereas the minimax lower benchmark for unrestricted heterogeneity is the strictly smaller so the minimax benchmark improves on the standard-estimator rate in the sparse-cell regime. Under exact effect homogeneity the rate improves to and their occupancy-weighted collision estimator, under approximate homogeneity at binary radius , carries the algebraic remainder together with an exponentially small adverse-event term.

The comparison is easiest to read side by side. The two analyses share a causal target and an overlap condition and differ in outcome type, in how heterogeneity is indexed, and in what is proved.

Three entries carry the novelty. The outcome row is why the estimators had to be rebuilt: a second-moment envelope supplies variance control, so every statistic here is clipped and every risk bound runs through variances. The heterogeneity row is why a bracket is meaningful at all: with indexing one nested family, the binary exact-homogeneity and unrestricted rates become the and endpoints of a single statement. The split lower rows display the unrestricted, exact-homogeneity, and radius-indexed lower benchmarks separately. The final row records the same-class feature of the present bracket: both benchmarks are stated over one real-outcome class indexed by the same . Their upper-to-lower ratio therefore measures the remaining benchmark gap for one minimax problem, and it becomes an exact-order rate statement precisely in the regimes where Theorem 5 proves the benchmarks comparable.

The present use of Zeng et al. (2024) has three distinct layers. Their work supplies the binary hard-experiment mechanisms for unrestricted and exact-homogeneity converses, the sparse crossed-cell collision mechanism, and the binary collision benchmark used for comparison. In the notation of this paper, the corresponding binary source statements are recorded as Definition 7, Lemma 3, Lemma 4, Lemma 5, and Lemma 6. The new real-outcome analysis constructs the heavy–light polynomial estimator, the continuous-outcome occupancy estimator, the known-radius selector, the affine and radius-channel transfers into , and the all-alphabet same-class bracket. In that bracket, the binary exact-homogeneity and unrestricted scales appear as the and endpoints of one radius-indexed family, and Proposition 3 records the algebraic comparison with the binary collision remainder .

The construction also connects to large-alphabet functional estimation. Polynomial approximation and unbiased or nearly unbiased factorial statistics have been central in estimating distributional functionals with many rare categories, as in Paninski (2003), Valiant et al. (2011); Valiant et al. (2011); Valiant et al. (2016); Valiant et al. (2017), Jiao et al. (2015), Wu et al. (2016), and Wu et al. (2019). The estimator developed below uses that same rare-category logic for a causal target: light adjustment cells are handled through a polynomial device, while heavier empirically crossed cells are handled by an occupancy-weighted treated-control contrast. Classical tools for minimax lower bounds and approximation, including Le Cam (1986); Tsybakov (2009); Cai et al. (2011); Donoho et al. (1990); Timan (1963), and moment inequalities for symmetric statistics, including Hoeffding (1948); Serfling (1980), provide the surrounding mathematical vocabulary.

The empirical setting that motivates discrete adjustment at this scale is the 401(k) eligibility literature, where participation and financial-wealth outcomes are adjusted for finely stratified income and demographic cells (Poterba et al., 1994; Poterba et al., 1995). That application is the consumer of the binary analysis of Zeng et al. (2024), and it motivates the real-outcome risk bounds pursued here: wealth is naturally real-valued, and the cell counts in such designs are exactly the sparse regime in which the crossed-cell term matters.

Finally, the paper is related to higher-order and robust estimation ideas in semiparametric causal inference. Higher-order influence-function methods of Robins et al. (2008); Robins et al. (2017) and robust mean-estimation techniques such as Lugosi et al. (2019) illustrate how weak moment information and complex nuisance structure can change attainable risk. The contribution here is a finite-alphabet minimax bracket for scalar average treatment effect estimation under fixed overlap and a bounded heterogeneity radius. The upper side is attained by a known-radius selector over polynomial, collision, and trivial estimators; the lower side is transported from binary experiments into the same real-outcome model. The resulting benchmarks match at the exact-homogeneity and unrestricted-radius endpoints, at every fixed positive radius, in the saturated alphabet regime, and at the parametric-dominance elbows.

Setup and assumptions

Throughout, denotes sample size and denotes the number of adjustment cells. Cell indices such as range over , and treatment levels such as range over . Constants and may change from line to line and depend only on the overlap parameter . The outcome scale is , and the heterogeneity radius is . We use , , and with constants depending only on .

A full-data law governs the finite-cell observational unit with confounder , binary treatment , potential outcomes , and observed real outcome . For a supported cell, is the cell mass, is the propensity, and is the arm-cell conditional mean. The corresponding cell treatment effect is , the target average treatment effect is , and the centered cell-effect deviation is . These objects are fixed formally below before the minimax experiment is introduced.

The analysis starts from the potential-outcomes conditions for finite-cell adjustment, followed by scale and heterogeneity restrictions that make the finite-sample risk problem comparable across real-outcome laws.

Assumption 1 [ass:consistency] (Consistency).

Under , almost surely.

⊢ Lean

Consistency links the observed outcome to the potential outcome under the realized treatment assignment, following the potential-outcomes setup used in discrete-adjustment analyses such as Zeng et al. (2024).

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

Under ,

⊢ Lean

Conditional exchangeability is the selection-on-observables condition after conditioning on the discrete adjustment cell (Zeng et al., 2024). Together with consistency, it gives the usual causal interpretation of cell-level treated-control contrasts (Rubin, 1974; Rosenbaum et al., 1983; Imbens et al., 2015).

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

For each cell , let and, when , let For every with ,

⊢ Lean

The fixed-overlap requirement imposes strong overlap on every supported cell, as in binary discrete-adjustment work such as Zeng et al. (2024). It keeps both treatment arms available in population within each cell while allowing the cell masses themselves to be arbitrary.

Assumption 4 [ass:mean-normalization] (Mean normalization).

The law carries an arm-cell outcome distribution for every arm and every cell , zero-mass cells included; let denote its mean. Whenever the arm-cell probability is positive, is the observed conditional mean . Only supported cells are constrained: for every and every with ,

⊢ Lean

Mean normalization is the affine-centered bounded conditional-mean analogue of the bounded binary response scale in Zeng et al. (2024). The centering fixes the outcome scale for the minimax comparison, and the restriction applies on the supported part of the adjustment distribution.

Assumption 5 [ass:approximate-homogeneity] (Approximate homogeneity).

For every cell , let and both well defined on zero-mass cells as well. The cell-effect deviations satisfy

⊢ Lean

Approximate homogeneity is the outcome-scale-normalized analogue of a maximal cell-effect-deviation radius in binary discrete adjustment (Zeng et al., 2024). The radius measures the largest supported-cell departure of a cell treatment effect from the population-weighted average effect.

Assumption 6 [ass:second-central-moment] (Second central moment).

For every and every with ,

⊢ Lean

The moment bound extends the binary bounded-outcome scale to real-valued outcomes through a uniform conditional second-central-moment envelope. It keeps the noise level on the same scale as the conditional-mean and heterogeneity restrictions.

Role of the assumptions.

It is worth pausing on what each condition is doing, because the combination is unusual. Fixed overlap is the standard identification requirement, but here it plays a second, finite-sample role: it guarantees that a cell which is occupied at all has a non-vanishing chance of containing both arms, which is exactly the event the collision estimator lives on. The bound is a scale normalization: it fixes the scale against which a treatment effect is judged large, and a finite minimax comparison needs such a scale because multiplying all outcomes by a constant multiplies the risk by its square. The conditional second-moment envelope is where this model departs from the binary-outcome literature. Bounded outcomes supply bounded or sub-Gaussian concentration; a second-moment envelope supplies variance control, so the estimators are clipped and the risk analysis runs through variances. That is the price of allowing real outcomes, and it is why both estimators here are total, clipped maps. Finally, the radius is the object of interest: it interpolates between exact effect homogeneity, where the population contrast can be read off any single cell, and unrestricted heterogeneity, where every cell must be estimated separately. Making an index of one nested family allows a single bracket to describe all of these regimes.

These conditions define two law classes. The first imposes the radius bound, while the second records the same overlap and moment envelope with the radius left free.

Definition 1 [def:model-class] (Real-outcome model class ).

⊢ Lean

The radius-indexed class is the main parameter space of the paper: all finite-cell masses are allowed, and the scalar radius records the amount of cell-effect variation available to the estimator.

Definition 2 [def:unrestricted-class] (Unrestricted-radius class ).

⊢ Lean

The unrestricted-radius class supplies the endpoint comparison for the radius scale under the same fixed-overlap and real-outcome moment envelope.

The observed-data experiment is generated by independent sampling from the observed margin. Write the observed record as and its observed-data law as .

Definition 3 [def:sample-experiment] (Sample experiment ).

Let and let denote the observed-data law of under . The -sample observed-data experiments generated by are

⊢ Lean

Thus each sampling law belongs to the experiment induced by a law in .

The target parameter is the finite-cell average treatment effect. Its definition uses the same cell masses and arm-cell conditional means introduced in the assumptions.

Definition 4 [def:ate-functional] (Average treatment effect ).

For a real-outcome finite-cell law indexed by and an overlap parameter with , assume consistency, conditional exchangeability of and given for measurable potential-outcome events, overlap whenever , and first-moment integrability of each arm-cell outcome law for every and positive-mass cell. With the cell mass and the arm-cell conditional outcome mean, define

⊢ Lean

Under these conditions coincides with the full-data causal contrast and is identified from the observed margin by the standard finite-cell g-computation argument (Rubin, 1974; Rosenbaum et al., 1983; Robins et al., 1994; Imbens et al., 2015); the minimax analysis targets this observed-data functional throughout.

For the risk statements, estimators are clipped to the natural scale implied by the mean normalization. The selector benchmark used later is where records the parametric term together with the best of the collision, polynomial, and zero-estimator scales.

Definition 5 [def:minimax-risk] (Minimax risk and estimator class ).

Let The minimax mean-squared risk over is

⊢ Lean

The estimator class matches the range of the target under the scale bound, and the minimax risk is the paper’s central finite-sample loss criterion.

The main rate displays use the following benchmark notation. The table gives each symbol one role; later sections keep these names fixed.

The word “frontier” in the verified labels names the selector benchmark . It records the upper benchmark achieved by the constructed known-radius selector in Theorem 2. The capped converse benchmark is the lower benchmark in the all-alphabet bracket, while is the product-form shorthand used in the triangular benchmark algebra. Some anchored theorem statements introduce local symbols inside their displays; the reader-facing prose uses the superscripted notation above whenever both lower benchmarks appear in the same discussion. Wherever and agree in order, the selector benchmark is the minimax rate; the residual shrinking-radius region is the localized regime where the displayed selector and product-form converse benchmarks separate.

The normalization also pins down the unrestricted endpoint of the radius scale.

Lemma 1 [lem:scale-sanity] (Scale sanity).

For any and any , let and be the model classes in Definitions 2 and 1. For each law , write Every satisfies and Consequently the two classes have the same underlying laws at radius : for every there exists with the same law as , and for every there exists with the same law as .

⊢ Lean

The proof is deferred to Section E.

Lemma 1 makes the radius normalization exact: the bounded conditional means imply , supported cell effects lie within the same outcome scale, and radius coincides with the unrestricted-radius law class. This calibration is used when the main bracket is specialized to endpoint regimes.

Finally, the lower-bound arguments later use binary source experiments from Zeng et al. (2024). We record the source target and source law classes here so that the subsequent affine embeddings have a fixed reference point.

Definition 6 [synth_1] (Binary exact-homogeneity source target).

For a binary-outcome fixed-sample law in the uniform-mass exact-homogeneity source family, let denote the conditional response mean in arm and cell . The source target is

Definition 7 [synth_2] (Binary source law classes).

For an overlap parameter , let be the class of binary -cell full-data laws for , with , , consistency , conditional exchangeability , arbitrary cell masses , propensities satisfying on every positive-mass cell, and arm means . Define its uniform-mass exactly homogeneous subclass by

The source target in Definition 6 and the binary classes in Definition 7 provide the binary ingredients transported in the lower-bound section. Their role is to specify the published discrete-adjustment experiments before the paper embeds them into the real-outcome class .

Estimators and upper bounds

We now turn from identification and the minimax loss criterion to constructive estimation. The upper bound is built from two complementary procedures. The first estimator, , uses a sample split to separate cell classification from estimation and applies a Chebyshev polynomial device to rare cells, following the large-alphabet functional-estimation logic of Jiao et al. (2015); Wu et al. (2016). The second estimator, , forms treatment-control contrasts in empirically crossed cells and weights those contrasts by their observed occupancy. The final estimator, , uses the known radius to choose among the polynomial estimator, the collision estimator, and the zero estimator.

The polynomial construction is useful when many cells are light. Its pilot block identifies cells with enough empirical mass for a plug-in treated-control contrast, while its estimation block evaluates both the heavy-cell plug-in terms and the light-cell factorial terms. The ordered distinct-index structure is the finite-sample analogue of unbiased polynomial estimation for sparse categorical functionals, with the sample split keeping the random heavy-light classification separate from the contribution estimates (Hoeffding, 1948; Serfling, 1980).

The proof of the upper bound follows this construction. Conditional on the pilot block, the heavy set is deterministic. Heavy cells are controlled by stratified empirical means and fixed overlap; light cells are controlled by shifted-Chebyshev coefficient envelopes and covariance bounds for one-mark factorial statistics. Summing the conditional risk and then averaging over the pilot block gives the polynomial risk bound. The collision branch is analyzed separately by decomposing its error into ordinary arm-cell noise and the bias contributed by uncrossed cells; the approximate-homogeneity radius controls the latter term, and the occupancy reciprocal bound controls the random denominator.

Algorithm 1 [def:polynomial-handle] (Polynomial estimator ).

For observations , with , , and , fix a polynomial handle with . Let , The handle certifies that whenever , , , and . The active branch below is used on and ; the calibrated value is when or .

  1. Split the sample into the pilot and estimation blocks

  2. Use to form the empirically heavy and light cell sets

  3. On each heavy cell , use to compute the estimation-block arm counts, cell count, arm outcome totals, totalized arm means, and normalized plug-in contribution

  4. On each light cell , set With denoting the falling factorial, evaluate the ordered distinct-index one-mark statistic and set the normalized light-cell contribution to

  5. Writing for truncation to the interval , sum the heavy and light contributions and output the clipped active-branch statistic

⊢ Lean

The factorial display in Algorithm 1 is a mathematical representation of the statistic. A direct implementation first scans the estimation block once to store, for each cell and arm, the counts , totals , and powers or falling-factorial count products needed for orders . The light-cell terms are then evaluated from these aggregated arrays, so the program sums over cells, arms, and polynomial orders rather than over ordered tuples of observations. With this aggregation, Lemma 13 gives the post-aggregation operation count , with independent of , , and . Including the raw scans over the pilot and estimation blocks, the computational cost is up to constants depending on the fixed overlap calibration.

Concretely, the whole procedure is five passes over arrays, and it is worth spelling them out because the ordered-tuple display above looks more expensive than the computation actually is.

  1. Pilot pass. Scan once and accumulate for each cell. Mark cell heavy if and light otherwise. This fixes and before any outcome on is touched, which is what keeps the two blocks independent.

  2. Aggregation pass. Scan once and accumulate, for each cell and arm , the count and the outcome total ; also accumulate the cell count . The aggregate arrays carry the sample information used by the later arithmetic steps, so the ordered tuples in the display are represented through counts and totals.

  3. Heavy cells. For , form , taking the value when , and set . The zero-count convention is what makes the statistic total rather than partially defined.

  4. Light cells. For , the ordered-tuple sum defining collapses to a closed form in the aggregates already stored. Summing over ordered distinct indices with a marked leading index, a run of further indices in the same arm-cell, and one trailing index in the cell gives where is the falling factorial and any factor with a negative argument is read as zero. The aggregate form represents the tuple sum directly: the leading index contributes the arm-cell outcome total , the middle indices contribute a falling factorial of the remaining arm-cell count, and the trailing index contributes the remaining cell count. Build the falling factorials incrementally, , so each order costs one multiplication; then accumulate . This is the term in the operation count.

  5. Output. Sum over heavy cells and over light cells, clip the total to , and multiply by . The clipping gives the estimator its range and hence the worst-case risk control used when the polynomial branch is evaluated outside its calibrated range.

Outside the calibrated range and the procedure returns , so the estimator is defined across the whole sample space. The theorem fixes an overlap-dependent calibration handle , and the selector uses the known indices : sets the clipping level, determines the branch comparison in Algorithm 3, and determine the polynomial degree and the displayed remainders. The heavy-light threshold and calibration handle are fixed by ; the branch choice is deterministic in the model indices and the observed sample enters only through the two candidate statistics.

The collision estimator targets the part of the sample in which treated and control observations meet within the same adjustment cell. Its form is close to the occupancy statistics used in sparse-cell average treatment effect analysis and higher-order causal estimation: the sample supplies both the within-cell contrast and the empirical weight assigned to crossed cells (Robins et al., 2008; Robins et al., 2017). Robust mean-estimation work under weak moment conditions, such as Lugosi et al. (2019), provides a separate point of comparison for how moment assumptions shape attainable risk.

Algorithm 2 [def:collision-handle] (Collision estimator ).

For observations , define by the following one-pass cell aggregation followed by one pass through the occupied categories.

  1. For each arm and cell , define the full-sample arm-cell count and outcome total

  2. Define the full-sample cell count, crossed-cell indicator, and total count in empirically crossed cells

  3. For positive arm-cell counts, define the arm-cell sample means

  4. Output the occupancy-weighted treated-control statistic where the inner value is when .

⊢ Lean

The known-radius selector compares the two nonparametric remainders associated with these constructions. The quantity is the rare-cell polynomial scale, and is the collision scale that combines the heterogeneity radius with the sparse crossed-cell term.

Algorithm 3 [def:total-estimator] (Selector ).

Given candidate estimators and , each a total measurable map , define by the following steps.

  1. Define the rare-cell polynomial remainder

  2. Define the collision remainder

  3. Output the measurable selector

⊢ Lean

The next result records the two risk inequalities that make the selector possible. The polynomial estimator gives a uniform upper bound with the parametric term and the rare-cell polynomial remainder, while the collision estimator gives a uniform upper bound with the parametric term, the squared radius, and the crossed-cell occupancy remainder.

Theorem 1 [thm:robust-upper-construction-resolution-all-d] (All-alphabet upper construction).

For every , there exist a constant and a polynomial calibration handle with such that, for every , every , and every , the following hold:

  • (Polynomial calibration.) The handle satisfies and , where is the polynomial degree used by the handle-indexed heavy-light signed one-mark Chebyshev factorial estimator .

  • (Admissibility.) The estimators and , with as in Algorithm 2, are measurable maps of the -sample and take values in .

  • (Model class.) The risk bounds are uniform over , the model class in Definition 1.

With , the estimators obey and

⊢ Lean

Theorem 1 separates the two sources of gain. The polynomial construction is calibrated to the large-alphabet regime through and contributes the scale . The collision construction uses the approximate-homogeneity radius: when cell effects are close to their average, missing uncrossed contrasts contribute at the scale, and crossed-cell scarcity contributes .

Combining the two inequalities with the measurable selector yields the all-alphabet upper benchmark. The selector uses the radius as an input, so the comparison among the three branches is deterministic once , , and are fixed.

Theorem 2 [thm:frontier-upper-all-d] (All-alphabet frontier upper bound).

For every overlap parameter with , there exist a constant and a polynomial calibration handle such that:

  • (Handle calibration.) , and for every pair of integers , where is the polynomial degree used by the polynomial estimator.

  • (Index range.) The guarantee applies to every pair of integers , every , and every .

  • (Model class.) The law ranges over from Definition 1.

For these indices, let be the admissible polynomial estimator calibrated by , let be the collision estimator, and let be the known-radius selector in Algorithm 3 applied with radius to these two estimators, and write for the selector benchmark. Then is measurable, satisfies for every sample , and

⊢ Lean

Theorem 2 packages the constructive side of the minimax analysis. For every alphabet size and sample size, the known-radius estimator attains the parametric term plus the smallest available nonparametric remainder among the polynomial, collision, and clipped-zero branches. This all-alphabet statement is the upper half of the two-sided bracket assembled in the next sections.

Lower bounds and binary embeddings

The upper bounds in Theorems 1 and 2 are matched against lower bounds obtained by embedding binary hard experiments into the real-outcome model. The source experiments come from the discrete-adjustment constructions of Zeng et al. (2024). The present section records the embedding map, the transfer of binary converses into the radius-indexed class in Definition 1, and the all-alphabet lower bound that will be combined with the selector bound in the main bracket.

The least-favorable construction uses two binary sources. One source carries an exact-homogeneity collision lower bound, and the other passes through a channel whose attenuation equals one half of the heterogeneity radius. The capped alphabet sizes keep the source experiment within the available cells for every finite .

The lower-bound proof has a parallel structure. The exact-homogeneity component restricts the real-outcome model to affine images of uniform-mass binary laws with a common cell effect; the binary collision lower bound then gives the baseline . The radius component starts from an arbitrary-mass one-arm binary lower bound, pads the source alphabet into the available cells, applies a Bernoulli channel with attenuation , and rescales outcomes by . This transport preserves the observed-data comparison up to data processing and turns source target separation into average-treatment-effect separation of order , giving the term . The exact and radius components are combined with the parametric lower term in the bracket.

Algorithm 4 [def:least-favorable-handle] (Least-favorable handle).

For fixed constants depending only on , define the two embedded hard families and the channel as follows.

  1. Set the channel attenuation

  2. For the radius component, set the capped alphabet size Start from a fixed-sample binary one-arm hard family with at most positive-mass cells, and assign zero mass to unused cells.

  3. Pass each binary potential response through the hypothesis-independent channel and define the scaled real potential response

  4. For the exact-homogeneity component, set the capped alphabet size Start from a uniform-mass binary hard family on at most positive-mass cells, assign zero mass to unused cells, and define

  5. The construction outputs the radius-channel embedded family, the exact-homogeneity embedded family, and the channel above.

⊢ Lean

Algorithm 4 fixes the two source-to-target routes used below. The exact-homogeneity route preserves the binary response contrast after the affine scaling by . The radius route first contracts binary mean differences by the factor , so the transported alternatives fit the heterogeneity radius in Assumption 5 while retaining a source separation proportional to .

The affine embedding is the basic transport map. It leaves the discrete adjustment structure unchanged and rescales binary outcomes to the centered real interval dictated by Assumption 4.

Definition 8 [synth_4] (Affine binary-to-real embedding).

For , define as the affine pushforward that sends a binary -cell law to the real-outcome -cell law obtained from Under , the cell masses and propensities agree with those of , each positive arm-cell conditional outcome law is pushed forward by , and

The mean-squared-error notation used in the transfer statements is tied to the observed product law in Definition 3 and the average treatment effect functional in Definition 4.

Definition 9 [synth_7] (Mean-squared error ).

For a real-outcome law and a total estimator of the -sample, define its mean-squared error at by where is the observed product law and is the average treatment effect functional.

With these definitions in place, the first transfer result records how the binary classes enter the real-outcome classes and how their risk lower bounds scale. It also states the polynomial upper guarantee attached to the same affine framework, which keeps the subclass comparison and the constructive bound on a common outcome scale.

Proposition 1 [prop:zeng-class-inclusion-and-lower-transfer] (Affine subclass transfer).

Let and be the binary source classes of Definition 7, whose defining conditions are recalled here only through the overlap and homogeneity constraints that this proposition uses: and, for the uniform-mass exactly homogeneous subclass, For every overlap parameter with , there are constants and a polynomial calibration handle, consisting of a cutoff and an active-range multiplier such that for all , where is the polynomial degree of Algorithm 1, with the following property. For every and , there is an affine embedding map , sending each binary -cell law to a real-outcome -cell law, with the following properties:

  • (Affine embedding.) For every binary law , is the affine pushforward : its observed law is the pushforward of the binary observed law, its cell masses and propensities agree with those of , each positive arm-cell conditional outcome law is pushed forward by , each arm-cell mean is times the corresponding binary mean minus , and its full-data law is induced by an affine pushforward of a binary full-data coupling.

  • (Unrestricted inclusion.) If , then , the class in Definition 2.

  • (Exact homogeneous inclusion.) If , then with as in Definition 1.

  • (Strict image.) For every , there exists a real-outcome law that is the image of no binary law: for every binary law .

  • (Lower transfers and upper estimator.) Write for the mean-squared error of a total estimator under the -sample law of a real-outcome law . For every and , if , then every total measurable estimator with values in has some satisfying and the minimax risk in Definition 5 satisfies For all and , the radius-channel transfer gives together with a transfer certificate with constants and . The estimator determined by the polynomial calibration handle is measurable, takes values in , and for every ,

⊢ Lean

Proposition 1 makes the binary-to-real comparison precise. The binary arbitrary-mass source class embeds into the unrestricted real-outcome class, while the uniform-mass exactly homogeneous source embeds into the zero-radius real-outcome class. The transferred exact-homogeneity lower bound contributes the scale on its active alphabet range, and the radius-channel transfer contributes the scale for the rare-cell component. The final clause records that the polynomial estimator applies over the larger real-outcome class in Definition 1, so the embedding is used for converses while the constructive guarantee remains same-class.

The next statement extends the exact-homogeneity lower transfer to all alphabet sizes by saturating the collision term at one. It is the exact-radius component of the lower benchmark used in the bracket.

Lemma 2 [lem:scaled-binary-exact-lower-transfer-all-d] (Scaled binary lower transfer).

For every overlap parameter with , there exists a constant such that the following statement holds. For every , , and satisfying

  • (Sample and alphabet.) and ;

  • (Outcome scale.) ;

  • (Radius range.) ,

the minimax mean-squared risk from Definition 5 obeys

⊢ Lean

The proof is deferred to Section E.

Lemma 2 supplies the lower-bound baseline that persists at every radius because exact homogeneity is included within each radius-indexed class. The term is the parametric sampling contribution, and the capped term is the collision contribution inherited from the binary exactly homogeneous source experiment of Zeng et al. (2024) after scaling by .

The radius-channel converse adds the rare-cell component governed by the heterogeneity radius. The construction in Algorithm 4 converts a binary source separation for , the binary average response contrast introduced in Definition 6, into a real-outcome separation for through the displayed affine channel.

Theorem 3 [thm:radius-channel-converse-all-d] (All-d radius converse).

For every , there exist constants and such that For all integers , all , and all , the minimax mean-squared risk of Definition 5 satisfies Moreover, for the same constants and every such , there are a capped alphabet size , a source family, a padding map into , an embedding into , and a coupling realizing the radius-channel construction with source constant . Along this realization, for all source laws , and for every estimator taking values in , some source law satisfies

⊢ Lean

Theorem 3 establishes the all-alphabet lower benchmark for the same minimax risk studied by the selector upper bound. Its first two terms are the exact-homogeneity baseline from Lemma 2; the third term is the radius-sensitive rare-cell term generated by the channel. The displayed coupling identity shows why the scale is : the affine map contributes the factor , the channel contributes the factor , and mean-squared risk squares the resulting target separation. The capped construction keeps the embedded source inside for every finite alphabet size, so the lower bound is available at the same indices as the upper result in Theorem 2.

Together, Lemma 2 and Theorem 3 provide the converse side of the paper’s minimax bracket. The next section combines these lower bounds with the selector guarantee in Theorem 2 and then characterizes the regimes in which the two benchmarks agree in order.

Main bracket and matched regimes

The lower bounds in Lemma 2 and Theorem 3 and the selector upper bound in Theorem 2 combine into the paper’s main finite-sample statement. The result is indexed by the same sample size, alphabet size, outcome scale, overlap constant, and heterogeneity radius as the model class in Definition 1; the constants depend only on the fixed overlap parameter. In this section, the all-alphabet lower benchmark is the capped converse benchmark , while the triangular algebra later uses for the product form. The two displayed benchmarks separate the exact-homogeneity collision baseline from the radius-sensitive rare-cell component on the lower side, and the best available selector branch on the upper side.

Theorem 4 [thm:two-sided-minimax-bracket-all-d] (All-alphabet minimax bracket).

For every overlap parameter with , there are real constants and such that For every , , and , suppose that

  • (Sample and alphabet sizes.) and .

  • (Outcome envelope.) .

  • (Radius range.) .

Let be the minimax mean-squared risk in Definition 5 over the real-outcome class with fixed overlap , conditional exchangeability, consistency, conditional mean normalization, conditional second central moment envelope , and approximate-homogeneity radius . Define and write Then

⊢ Lean

Theorem 4 gives a same-class minimax bracket for the scalar average treatment effect over arbitrary cell masses and real outcomes under the moment envelope in Definition 1. The upper benchmark is constructive through the known-radius selector in Algorithm 3. The lower benchmark adds two sources of difficulty: the capped collision term already present at exact homogeneity and the radius-channel rare-cell term transported in Theorem 3. Thus the radius governs whether borrowing across cells, crossed-cell contrasts, or clipping to the outcome scale supplies the sharpest available upper benchmark.

The endpoint reductions turn the bracket into familiar rates at the two ends of the radius scale. At , the collision remainder is the relevant sparse-cell term. At radius two, Lemma 1 identifies the radius-indexed class with the unrestricted-radius class, and the polynomial remainder gives the unrestricted all-alphabet benchmark associated with large-alphabet functional estimation (Jiao et al., 2015; Wu et al., 2016).

Proposition 2 [prop:endpoint-reductions-all-d] (Endpoint rate reductions).

There exist constants , with , such that the following hold.

  • (Exact homogeneity.) For every pair of integers , and

  • (Unrestricted radius.) For every pair of integers , and

  • (Class equality at radius two.) For every alphabet size , every , and every , the laws represented by in Definition 2 are exactly the laws represented by in Definition 1.

  • (Endpoint identity.) For every pair of integers , the radius-two upper frontier expression is exactly

⊢ Lean

Proposition 2 calibrates the two endpoints of the regime summary. Exact homogeneity gives the rate , matching the collision lower transfer from Zeng et al. (2024). The unrestricted endpoint gives , the polynomial large-alphabet scale. The class equality clause also fixes the interpretation of the radius normalization: radius two represents the full unrestricted-radius law class introduced in Definition 2.

The regime theorem supplies the order comparisons away from the endpoints. It covers every fixed positive radius, the saturation region, small alphabets, and the two parametric-dominance elbows. It also records the residual shrinking-radius wedge generated by the proved benchmarks. The symbol in the theorem display below is local to that anchored statement and denotes the triangular product benchmark; in the surrounding prose it is written as to distinguish it from the capped converse benchmark in Theorem 4.

Theorem 5 [thm:fixed-interior-tightness-and-shrinking-radius-gap-all-d] (Fixed-radius wedge characterization).

Fix . For , put , and define Let be the minimax mean-squared risk in Definition 5. Then all of the following hold.

  • (Triangular benchmarks.) For every and every , if then

  • (Fixed interior radii.) For every , there exist constants with such that, for every , every , and every satisfying , whenever and .

  • (Matching elbows.) For every , there exist constants with such that, for every , every , and every , whenever , , and at least one of holds.

  • (Exact algebraic elbow.) For every with ,

  • (Sufficient elbows.) For every with , and

  • (Residual wedge implication.) For any sequences and , if eventually and , and if the frontier-to-capped-converse benchmark ratio then the sequence lies in the residual wedge:

  • (Nonempty wedge.) The sequence and lies in the residual wedge.

  • (Diagonal divergence.) Along and , eventually, and

⊢ Lean

Theorem 5 gives the rate consequences of the bracket. For every radius bounded away from zero, the minimax risk is equivalent to the selector benchmark . The same equivalence holds in the saturated region , in regimes where the polynomial term is dominated by the exact-homogeneity baseline, and in regimes where the squared radius is dominated by that baseline. The algebraic and sufficient elbow clauses identify concrete alphabet ranges, including and , where the baseline already controls the polynomial remainder.

Table 1 summarizes the rate statements across the regimes of the scale; boundary constants and logarithmic factors are governed by the displayed formulas in Theorem 5.

Matched-regime summary for the two-sided minimax bracket. The final row summarizes the proved comparison between displayed selector and converse benchmarks in the residual wedge; exact minimax-rate conclusions are the rows where the benchmark is listed as matched.
Regime Condition Matched benchmark or localized separation
Exact homogeneity
Unrestricted radius
Fixed positive radius
Saturation and elbows , or , or
Selector/converse benchmark gap and selector benchmark ; product-form converse benchmark

The final row of Table 1 is a localization statement about the displayed benchmarks. In the intermediate alphabet range , the selector benchmark is comparable to , while the product-form converse benchmark is . These expressions agree in the fixed-radius and parametric-dominance regimes described in the theorem. The residual shrinking-radius wedge consists of sequences where the baseline is small relative to both the polynomial scale and the squared radius, while both the polynomial scale and squared radius vanish. The diagonal sequence , shows that this localized separation region is nonempty and that the ratio between the displayed upper and lower benchmarks can diverge at logarithmic order.

Taken together, Theorem 4, Proposition 2, and Theorem 5 provide the all-alphabet minimax summary. The paper establishes a constructive upper benchmark and a same-class lower benchmark for the radius-indexed real-outcome model, matches them at the two endpoints and throughout the fixed-positive-radius and elbow regimes, and isolates the shrinking-radius intermediate region generated by the proved finite-sample inequalities.

Binary collision comparison

A useful secondary comparison is with the published binary collision estimator of Zeng et al. (2024). The following statement keeps that comparison separate from the same-class minimax bracket: it assumes the published binary collision guarantee and then records the algebraic relationship between the present selector benchmark and the collision remainder.

Proposition 3 [thm:published-binary-collision-comparison] (Binary collision comparison).

Fix . For a binary -cell law write for its -sample product experiment and for the published binary occupancy-weighted collision estimator, and say that has binary maximal heterogeneity at radius when , every cell satisfies , and some cell attains equality. Suppose the published binary collision guarantee holds at overlap : there are constants such that, for every with , every binary law with overlap , and every satisfying binary maximal heterogeneity at radius , and

Define Then the published binary collision guarantee above and the following algebraic comparison hold simultaneously:

  • (Pointwise comparison.) For every and such that , , and ,

  • (Asymptotic comparison.) For every pair of sequences and satisfying and for all , if then

⊢ Lean

Proposition 3 has two roles. First, it states the exact binary occupancy guarantee used for the comparison, including its bias and variance scales. Second, it shows that the selector’s nonparametric term is bounded pointwise by the collision remainder, and that it is asymptotically smaller along sequences where the polynomial scale is negligible relative to the collision scale and the alphabet lies below in the displayed sense. This makes the comparison presentation-level: the headline bracket in Theorem 4 rests on the same-class upper and lower statements assembled in Theorems 2 and 3.

Discussion and limitations

The bracket in Theorem 4 gives a finite-sample interpretation of the known-radius problem on a single real-outcome observational class. The estimator side is entirely constructive through in Algorithm 3, and the converse side is stated for the same class from Definition 1. The radius is an intrinsic coordinate of that class: it is the maximal supported-cell effect deviation inside the same fixed-overlap, arbitrary-cell-mass model used to define the minimax risk in Definition 5.

The bracket benchmarks also give a concrete reading of the two estimation mechanisms. When the radius is small enough for crossed cells to be informative, the collision branch uses observed treated-control meetings within cells. When the alphabet is sparse enough for rare-cell approximation to dominate, the polynomial branch uses the heavy-light construction in Algorithm 1. The selector benchmark in Theorem 2 records the better of these two mechanisms, together with the clipped-zero branch, while Theorem 5 identifies the endpoint, fixed-positive-radius, saturation, and parametric-dominance regimes where the bracket is order matched.

Future work

The matched-regime summary in Theorem 5 leaves a sharply described residual shrinking-radius wedge for further development. The following remark records the target problem in that region using the same notation as the regime theorem.

Remark 1 [oeq:shrinking-radius-frontier] (Shrinking-radius frontier).

Let In the residual shrinking-radius wedge equivalently up to boundary constants a natural next question is whether one can either construct a realization-wise radius-constrained paired-cell moment-matching fuzzy experiment in with ATE separation of order and sample-mixture total variation bounded away from one, or construct an explicit total estimator whose risk is strictly smaller in order than the selector benchmark with the product benchmark as the target rate. The hypothesis-independent channel yields the product separation

⊢ Lean

Remark 1 records two possible mathematical routes in the residual shrinking-radius wedge. One route asks for a radius-constrained least-favorable construction with ATE separation at the selector scale; the other asks for an estimator whose risk improves on the current selector benchmark toward the product scale suggested by the channel lower bound. The divergence example in Theorem 5 places and inside this region and gives logarithmic separation between the displayed selector and converse benchmarks.

Limitations

The results are scoped to fixed overlap, known outcome scale , known heterogeneity radius , and scalar average treatment effect estimation. Within that scope, Theorem 4 gives risk bounds for clipped estimators in from Definition 5, and Theorem 2 constructs a selector that uses the radius as an input. The inference target is mean-squared error for point estimation over , so confidence intervals, adaptive radius selection, and data-driven choice of are directions beyond the estimation bracket established here.

The moment and overlap assumptions also define the statistical environment in which the bracket should be read. Fixed overlap in Assumption 3 keeps treatment and control assignment probabilities uniformly away from zero and one in every supported cell. Mean normalization and the second central moment envelope in Assumptions 4 and 6 set the real-outcome scale under weak conditional moment control. Approximate homogeneity in Assumption 5 supplies the radius that determines which estimator branch is selected. Under exactly these conditions, the paper characterizes the delivered finite-sample minimax bracket and its matched regimes for arbitrary cell masses.

Appendices

Binary source lemmas

The lower-bound transfers in Proposition 1, Lemma 2, and Theorem 3 use binary discrete-adjustment experiments, originating in Zeng et al. (2024), as source problems. This appendix records the binary source lemmas in the notation used by the main text, with attribution and statistical context supplied by the citation. The first definition fixes the fixed-sample exactly homogeneous binary experiment and its binary average response contrast.

Definition 10 [synth_3] (Fixed-sample binary homogeneous experiment).

For integers and , let be the fixed-sample binary-outcome exactly homogeneous source experiment consisting of the product laws generated by laws . Its binary average response contrast is

Definition 10 packages the source experiment used by the exact-homogeneity collision transfer. It aligns the fixed-sample product laws with the binary source classes introduced in Definition 7 and gives the target that is later scaled into the real-outcome average treatment effect through the affine embeddings.

The first finite-sample collision source lemma concerns the exactly homogeneous binary source experiment. It supplies the component used in the exact-radius part of the real-outcome lower benchmark.

Lemma 3 [lem:binary-exact-collision-lower] (Binary collision lower bound).

Let . Suppose that:

  • (Sample and alphabet.) satisfy and .

  • (Overlap.) The overlap parameter satisfies .

  • (Collision regime.) The dimensions satisfy .

For the fixed-sample binary exactly homogeneous source experiment , generated by binary laws with uniform cell masses, propensities in , and a common cell effect across all cells, the minimax mean-squared risk for estimating the binary average response contrast satisfies where the infimum ranges over all measurable real-valued estimators of the -sample.

⊢ Lean
Proof of Lemma 3.

Set Write . From , , and , Hence These are the admissibility inequalities used below: gives overlap, while and keep the Bernoulli means in .

For each sign vector , define a uniform-mass binary law with Let be the corresponding centered law with . The displayed inequalities make each and members of the fixed-sample binary exactly homogeneous source experiment in Definition 10, and

Let and let be the uniform mixture over signs. For , put and The centered one-observation mass satisfies . For a fixed cell , write and . Summing over the two arms and two outcomes gives Using , this expression reduces in the two sign cases to Summing over cells gives the one-observation overlap identity Therefore the finite product second-moment identity gives

Since , We now prove the finite-sign average bound used at . Let , , and . With , every sign-pair sum lies in , so . Hence , and For , the remaining regularity condition follows from using , , and . Hence , so . The chi-square to total-variation comparison gives

Fix any measurable estimator. The two-point testing inequality for the targets under and under , with separation threshold , gives a tail probability at least under one of these two laws. If the mixture tail is the larger one, one sign has at least that tail probability under . Multiplying the resulting tail probability by shows that, for this estimator, either or some has mean-squared error at least Taking the supremum over the binary exactly homogeneous class and then the infimum over measurable estimators gives

Finally , so the asserted lower bound follows.

Lemma 3 records the collision-scale binary statement associated with Zeng et al. (2024). The overlap-dependent constant is fixed once is fixed, and the displayed inequality gives a lower bound for estimating over uniform-mass exactly homogeneous binary laws when .

A second exact-homogeneity source lemma records the same binary phenomenon with the parametric term included. This statement is used when the transfer argument carries the homogeneous source risk into the real-outcome class.

Lemma 4 [lem:zeng-binary-exact-homogeneity-lower] (Exact binary lower bound).

Fix . For integers with , let be the fixed-sample binary-outcome experiment with cell masses , overlap , conditional response means in , and a common cell treatment effect, and write There exist constants and an integer such that, for every with , , and ,

⊢ Lean
Proof of Lemma 4.

Let the overlap-dependent collision constant be Because , we have , and therefore ; also .

Fix with , , and . Then and, since , Write for the fixed-sample binary exact-homogeneity minimax risk.

First, set Since , , so . Define two endpoint binary laws and by uniform cell masses and propensities in every cell, with conditional response means for every cell . The inequalities put in , and the preceding bound on puts all displayed conditional means in . Thus both laws have uniform cell masses, overlap at level , and a cell effect constant across cells. Hence For this endpoint pair, the Bernoulli calculation gives total-variation distance at most for the two -fold product laws because Le Cam’s two-point inequality therefore gives

Second, Lemma 3, applied with , , , and , gives

If , then Using , we get

Otherwise , and hence Using , we get

The two cases cover all , and the stated lower bound follows.

Lemma 4 records the binary exact-homogeneity lower scale associated with Zeng et al. (2024). The constants depend only on the fixed overlap level, and the active range is the range transported and then saturated in the all-alphabet real-outcome statement.

The radius-channel converse uses a different binary source: a one-arm problem with arbitrary cell masses and zero control-arm response mean. Its minimax lower bound carries the large-alphabet polynomial scale that appears after the channel attenuation.

Lemma 5 [lem:zeng-binary-one-arm-lower] (Binary one-arm lower bound).

For every real overlap constant , if , then there exist constants and an integer such that the following holds. For every sample size and alphabet size ,

  • (Positive alphabet.) .

  • (Large sample.) .

  • (Source range.) .

In the fixed-sample binary observed-data experiment with observations , arbitrary cell masses , product sampling law , overlap on every positive-mass category, and identically zero control-arm response mean , the treated-arm minimax risk satisfies where the infimum is over measurable estimators of the fixed sample.

⊢ Lean
Proof of Lemma 5.

Fix an overlap constant . For sample size and alphabet size , write for the one-arm minimax risk above, namely where the infimum is over measurable fixed-sample estimators and the supremum ranges over the binary control-zero laws described above, with propensities in . Also write

Set The overlap algebra gives

Let Both constants are positive. Choose so large that, for every , This is the elementary eventual domination of by .

We first prove the high-dimensional branch. Suppose that , , and Because and , this implies . Put , and define Thus , , and Set The scalar hypotheses needed for the shifted construction are as follows: The first bound follows from , , and . The second follows from and , with supplying the remaining numerical slack. For the third, , give and therefore, using , For the fourth, the same lower bound on , the upper bound on , and give which is equivalent to . These real inequalities are exactly the nonnegative extended-real budget used for the two discarded good-event complements.

We now construct the finite mixtures used in this branch. Let , so . The shifted grid consists of the three points and the affine Chebyshev mesh points on . Write these positive grid nodes as . For a grid symbol , augmented by a null symbol , define and The preceding overlap choice gives , and the grid construction gives .

Choose signed weights on the positive grid with total mass zero and positive Jordan mass. Let and be the normalized positive and negative Jordan parts of . They have the same moments against the shifted reciprocal-monomial basis, and their shifted target expectations satisfy Now inverse-tilt these two laws by the factor and put the remaining mass at : Because on the shifted grid, these are probability laws. For every , the test is represented by that basis with degree at most . The Jordan moment identities therefore transport through the inverse tilt to The same inverse-tilt identities give common active mass and separated treated-functional atoms,

Let have product law under side , and set By the first scalar budget, . Also by positivity of its factors, and the active-mass cap , together with , gives . Hence Define the relaxed good event The two-statistic Chebyshev envelope, applied with the displayed , and the displayed budget give so each has positive probability.

For , form a binary control-zero law on cells by assigning unnormalized cell masses , anchor propensity , active propensities , anchor treated mean zero, active treated means , and then normalizing by . The event gives , the preceding bounds give the required overlap and binary means, and all control-arm means are zero. Moreover The separation display for gives

For each realization , let be the product law of independent triple-counts over the anchor and active cells with Poisson rates on the anchor cell and on active cell . The logarithmic degree supplies, for every grid atom, Together with the raw moment identities through degree , this Taylor budget bounds the one-coordinate mixed triple-Poisson total variation by . Tensorization over the active coordinates, with the common anchor law factored out, gives the unconditioned predictive bound After restricting to and renormalizing, the loss in total variation is bounded by the two discarded probabilities. Hence the conditioned predictive mixtures satisfy For every , the Poissonized histogram generated from at total intensity , after recording the three arm-outcome labels in each cell, maps to exactly the kernel . Also , because . Therefore the total Poisson count satisfies , and the Poisson lower-tail bound gives . Since , the last scalar budget yields

We use the following finite-mixture testing reduction. If two finite mixtures have side centers , all component targets lie within radius of their side center, , their predictive total variation is at most , and the Poisson truncation penalty on each side is bounded by , then Apply this with The numerical identity gives The calibrated signal inequality and imply Since , this proves throughout the range .

The parametric component supplies the fixed-sample term. Fix and , and put Since and , the two endpoint binary laws with propensity , treated means and , and baseline control mean are valid. Deterministically replacing every control-arm outcome by zero preserves the treated functional and contracts total variation; it yields two control-zero laws with overlap in , treated functionals and product total variation at most . The total-variation bound is calibrated by Applying the two-point testing inequality with half-separation and total variation gives

Now choose so large that implies , , and Set Then . Fix , , and . If the high-dimensional bound and the parametric bound give and hence . In the complementary branch, . The choice of gives so Since , the parametric lower bound yields Thus for all , , and , which is the asserted one-arm lower bound.

Lemma 5 formalizes the arbitrary-mass binary rare-cell lower scale associated with Zeng et al. (2024). In the main lower-bound construction, the hypothesis-independent channel in Algorithm 4 attenuates this binary separation by the radius factor before the affine scaling by .

The final source lemma is an occupancy reciprocal bound. It controls the event that no empirically crossed cell appears and the reciprocal of the crossed-cell count used by the collision estimator.

Lemma 6 [lem:zeng-usable-occupancy-reciprocal] (Usable occupancy reciprocal).

For every overlap parameter , there are constants , depending only on , such that the following holds. For every , every , and every , let denote the -fold observed-data law and define with Then and

⊢ Lean
Proof of Lemma 6.

On the active range , let be the constant in the independent-Poisson usable-occupancy Laplace bound, and set Set on the complementary range. For any , Definition 1 gives , so the active values of the constants apply.

If , the cell-mass identity gives , so the assertion is immediate. Suppose and hence, after the preceding case, . The zero-event mass is at most one and therefore at most . The displayed rate is interpreted at this endpoint with the real-division convention , so and . The reciprocal integrand is identically zero, while the right-hand side is .

Assume now that . Put Since ,

Let be the law of the observed cell-arm mark . In the half-intensity marked-Poisson experiment with mark law and total intensity , let be the usable total obtained after regrouping the independent arm-cell counts. If and , then the two arm-cell intensities in cell are and . They sum to , the total cell intensities satisfy , and fixed overlap gives for every positive-mass cell, with zero-mass cells contributing trivially. The independent-Poisson Laplace bound for these intensities gives For each integer , where the second inequality splits the positive case according to whether . Integrating these deterministic bounds and using the Laplace display yields

Let denote the usable total in the first marks of an i.i.d. stream with one-step law . Adding observations can only increase the usable total, so both and the zero-plus-reciprocal penalty are nonincreasing in . If , then Markov’s inequality gives For either of the two nonnegative monotone prefix functionals above, because on the event . Therefore . The random-prefix expectation is exactly the corresponding marked-Poisson expectation with total intensity , and the deterministic auxiliary outcome mark does not change the prefix statistic. The fixed-prefix bounds are thus

The -prefix law of the cell-arm stream is the observed mark marginal of , and forgetting outcomes identifies the fixed-sample usable total with the corresponding mark-prefix usable total. Hence and, because is bounded by the zero-plus-reciprocal penalty,

Using and , For the reciprocal term, by the choice . This is the asserted reciprocal inequality.

Lemma 6 records the occupancy statement associated with the collision calculations of Zeng et al. (2024). The two displayed inequalities bound, respectively, the zero-crossing probability and the expected reciprocal occupancy on the crossed-cell event. These controls are the probabilistic ingredients behind the collision estimator’s dependence on and fixed overlap.

Proofs for upper bounds

This appendix records the auxiliary inequalities that support the constructive upper bounds in Theorems 1 and 2. The proof has two mechanisms. The polynomial branch first controls the shifted-Chebyshev coefficients, then bounds same-cell and distinct-cell factorial covariances, then combines those bounds with a deterministic heavy-set plug-in argument. The collision branch controls the occupancy-weighted treated-control contrast on empirically crossed cells. These mechanisms correspond to the two estimator branches introduced in Algorithms 1 and 2.

The first ingredient is a coefficient envelope for the shifted-Chebyshev polynomial used in the light-cell component of Algorithm 1. It converts the polynomial coefficients into a scale bound on cell masses below the light-cell threshold, matching the large-alphabet approximation strategy of Jiao et al. (2015); Wu et al. (2016).

Lemma 7 [lem:shifted-chebyshev-coefficient-envelope] (Shifted coefficient envelope).

Let be a positive integer, let , and define, for , Assume:

  • (Positive scale.) .

  • (Nonnegative mass.) .

  • (Budget bound.) .

Then

⊢ Lean
Proof of Lemma 7.

Define the absolute coefficient envelope Let be the Chebyshev polynomial of the first kind. The shifted expansion gives This follows by separating the linear term in the standard shifted-Chebyshev expansion and reindexing the terms , whose coefficients are .

Since the sign of is , one has Putting in the shifted identity therefore yields Because and , The Chebyshev recurrence , with the initial cases and , gives If , then termwise monotonicity gives

Now set The assumptions , , and imply For each , using , Summing this identity over gives The envelope bound at and the inequality give

Lemma 7 gives the deterministic side of the light-cell calculation. Once a cell mass is below the approximation scale , the entire signed coefficient expansion is controlled by , so the later variance bounds can aggregate the polynomial terms without tracking each coefficient separately.

The next two moment bounds handle the factorial statistics that estimate the light-cell polynomial terms. They are stated for an independent block of size with product law , the block analogue of the observed product experiment in Definition 3. The same-cell bound includes the extra covariance contribution created when two statistics use the same adjustment cell, and the distinct-cell bound records the simpler interaction across different cells.

Lemma 8 [lem:same-cell-factorial-cross-moment] (Same-cell cross moment).

Let be as in Definition 1, let , and write for the cell mass. For a block of independent observations with joint law , write . For an arm and an order , define Assume:

  • (First order.) .

  • (Second order.) .

  • (Block size.) .

Then, for all arms ,

⊢ Lean
Proof of Lemma 8.

Write For an observed record , write . Define the left coordinate factors and define the right coordinate factors in the same way, with in place of .

For a partial matching of size between and , let be the merged coordinate set, and let and map left and right coordinates into . Thus exactly when matches with . Put Finally set The block-size condition implies , hence and . The selector factors are measurable bounded indicators, and the marked factor is integrable under the moment conditions in Definition 1; the merged kernels are finite products with at most two marked factors at any single observed coordinate, hence integrable. With the coordinate factors just defined, each statistic and is its normalized ordered-product sum over injective maps into the block. Expanding the product of the two normalized sums and grouping each ordered pair of injective maps by the partial matching that records their shared block indices gives a contribution for matching pattern . The empty matching has product moment by independence and is then centered by subtracting . Therefore where is the finite set of partial matchings of size .

Each one-coordinate mean is bounded by the cell mass: For the outcome-marked coordinate, the argument splits according to the cell mass. If , the observed arm-cell event has -mass zero for each arm , so the marked integral is zero. If , the supported-cell branch of Assumption 4 applies to the arm-cell outcome law for each arm , and Assumption 3 supplies positive observed arm-cell mass when this law is read as the observed conditional law. The mean bound and from Definition 1 give absolute normalized arm-cell mean at most . The observed arm-cell restriction has total mass , so the absolute marked integral is bounded by . The selector-only coordinates integrate to cell or arm-cell probabilities bounded by . Since the product-law means factor coordinatewise, The empty-matching normalization satisfies, under , , and , Therefore

It remains to bound the positive-matching part. For each merged coordinate , the fiber definition of gives exactly one of the following forms: a single left factor , a single right factor , or a matched product . The first two cases include the lone unmarked cell-indicator coordinate. For single factors, the preceding one-coordinate bound gives For matched products, first note the square-moment bounds For the outcome-marked coordinate these bounds again split on : the zero-mass branch is null on every arm-cell event, while on , Assumption 3 supplies the positive arm-cell support for either arm. The arm-cell law then satisfies the mean and central second-moment bounds from Assumptions 4 and 6; expanding the second moment around gives an unnormalized second moment at most , hence, using from Definition 1, a normalized second moment at most . Multiplying by the observed arm-cell mass, which is at most , gives the displayed square-moment bound for the marked coordinate. Selector coordinates are idempotent indicators with event mass at most . Hence, by integrability, and , Consequently every merged coordinate satisfies

The merged product moment factors over the merged coordinates: Since ,

Using and the triangle inequality, It remains only to sum the normalization weights. Let and . For each , the size- normalization bound and the partial-matching count give Here , and the displayed bound uses together with the factorial-normalization estimate supplied by the block-size condition . Therefore, for every , The choice is admissible because , and it yields

Combining the empty-matching and positive-matching bounds by the triangle inequality gives as claimed.

Lemma 9 [lem:distinct-cell-factorial-cross-moment] (Distinct-cell cross moment).

Let be a model in Definition 1, and let be an independent block with joint law . For , , and , let be the ordered distinct-index one-mark factorial statistic from Lemma 8, equivalently Assume:

  • (Distinct cells.) .

  • (Admissible orders.) and .

  • (Block size.) .

Then, for all arms ,

⊢ Lean
Proof of Lemma 9.

Let be the one-observation marginal of , and for an observed record write . Define the left coordinate factors and the right coordinate factors Put For a partial matching of size between and , let be the merged coordinate set and let send left and right coordinates into , with exactly for matched pairs. Define and The ordered-factorial covariance expansion gives

Fix with . Choose a matched pair . At the merged coordinate , the factor contains and the factor contains . Since , their product is zero pointwise: Thus the merged kernel is identically zero and All positive-size matching terms in the expansion therefore vanish.

It remains to bound the empty-matching term. The admissible-order and block-size assumptions give For the product means, each one-coordinate mean is bounded by the corresponding cell mass: For the outcome-marked coordinate, if the relevant cell mass is zero then the arm-cell event is null and the marked integral is zero. If the relevant cell has positive mass, Assumption 4 and from Definition 1 give, for the corresponding arm , so multiplying by the arm-cell probability bounds the marked coordinate by one half of the cell mass. The selector-only coordinates integrate to or , both bounded by the cell mass. Since the product-law means factor coordinatewise,

Combining the vanished positive-size terms with the preceding bounds yields which is the claimed bound.

Together, Lemmas 8 and 9 supply the weak-moment covariance control needed for the continuous-outcome polynomial lift. The same-cell inequality carries the additional term that remains after the two factorial arrays overlap in a cell; across distinct cells, the block-size term is the relevant covariance contribution. These estimates use the ordered distinct-index structure familiar from symmetric-statistic calculations (Hoeffding, 1948; Serfling, 1980).

For the heavy-cell part of a fixed polynomial branch, the argument uses empirical arm-cell means with a total value when an arm-cell count is empty. The convention is local to the block calculation and agrees with the totalized plug-in convention used in Algorithm 1.

Definition 11 [synth_6] (Empirical arm-cell mean ).

For a block of observations , define the arm-cell count and outcome total by The empirical arm-cell mean is

The next aggregate covariance bound combines the coefficient envelope with the same-cell and distinct-cell moment bounds. It is the main stochastic input for summing the light-cell polynomial contributions over a deterministic set.

Lemma 10 [lem:linear-mark-factorial-covariance] (Factorial covariance bound).

For every overlap parameter , there is a constant such that the following statement holds. Let , and be nonnegative integers, let , let as in Definition 1, and let be deterministic. For a block of independent observations with joint law , write . For the polynomial degree , define the shifted-Chebyshev coefficients For , define Set Assume that

  • (Degree.) .

  • (Scale.) .

  • (Light cells.) for every .

  • (Block size.) .

  • (Shift calibration.) .

Then

⊢ Lean
Proof of Lemma 10.

Take . This constant is positive and depends only on .

Let All have finite second moments under , since each is a finite linear combination of ordered one-mark factorial statistics and the conditional second-central-moment envelope in Definition 1 supplies the needed second moments.

Expanding the variance of the finite sum gives Consequently,

Fix , and write . The light-cell condition and the shift condition give, for every , Indeed, , while and control the final summand. Also gives For each arm pair and each , Lemma 8 therefore yields Expanding , taking absolute values, and summing over both arm indices decomposes the same-cell contribution into the empty-matching and positive-matching weighted sums. By Lemma 7, the empty-matching part is bounded by For the positive-matching part, the same coefficient envelope applies once with and, for each fixed , once with ; using , Thus

For distinct , Lemmas 9 and 7 give Here all positive partial matchings between different cells are incompatible, so the only contribution is the empty-matching normalization correction summing over both arms contributes the factor , and gives .

Since , summing the diagonal and off-diagonal bounds gives

Using enlarging the two coefficients to , and adding the nonnegative term , we obtain This is the asserted bound with .

Lemma 10 isolates the continuous-outcome step in the polynomial estimator. The conditional second central moment envelope in Definition 1 is enough to control the one-mark factorial array after normalization by , and the final display separates the block sampling term from the two approximation-scale terms that depend on , , and .

The fixed-branch risk bound adds the heavy-cell plug-in component to the light-cell polynomial component. The statement is deterministic in the heavy set ; in the estimator of Algorithm 1, the sample split allows this result to be applied conditionally on the pilot block.

Lemma 11 [lem:polynomial-fixed-branch-risk] (Fixed branch risk bound).

For every overlap parameter , there is a constant such that the following holds. Let , let , let as in Definition 1, and let be deterministic. For one block of observations , , with joint law , define where is the empirical mass of cell on the block and is the arm-cell sample mean on positive arm-cell counts, with the corresponding empty-cell contribution set to zero. Let be the light factorial-polynomial contribution at scale and degree from Algorithm 1, and define Let denote the boundary-safe lower-mass missing envelope, Assume:

  • (Degree.) .

  • (Scales.) and .

  • (Heavy band.) for every .

  • (Light scale.) for every .

  • (Block size.) .

  • (Shift calibration.) .

Then

⊢ Lean
Proof of Lemma 11.

Fix , and take from the covariance bound in Lemma 10; the same constant is used in the fixed light-set calculation below.

For a sample block , decompose where and This is the deterministic fixed-branch normalized error in the statement.

The heavy part satisfies The fixed marked-ratio bound is applied to the deterministic heavy set ; the category masses in that bound are the cell masses , and the normalization by cancels the factor using .

For the light part, let The bias-variance identity for the square-integrable statistic gives

The variance term is bounded by Lemma 10: because satisfies the light-cell condition , together with the stated degree, block-size, and shift-calibration conditions.

For the bias term, the block-size condition implies , so the exact marked-factorial expectation identity applies term by term. With , , and the coefficients from Lemma 10, it gives Therefore is the negative of the sum over of

For , the shifted-Chebyshev expansion of the first-kind Chebyshev polynomial gives Since , the standard Chebyshev bound gives , hence . Combining this with the preceding identity and using yields the reciprocal approximation certificate

For a supported cell, overlap gives , the propensity range gives , the model normalization gives , and the light condition gives . Applying the preceding certificate at yields, for each arm , Combining the two arm bounds gives the cellwise treated-minus-control bias bound When , both the target and the displayed population polynomial vanish, so the same bound holds. Summing these cellwise bounds over gives

Therefore

Finally, gives and substituting the two bounds above is exactly the displayed inequality.

Lemma 11 decomposes the normalized branch error into a heavy-cell plug-in part, a light-cell polynomial variance part, and an approximation remainder. The boundary-safe envelope records the cost of missing an arm within a heavy cell under the lower-mass band, while the final term is the polynomial approximation contribution.

We next record the full-sample occupancy bound for the collision estimator. The event defining crossed cells in Algorithm 2 ensures that the treated and control sample means entering the statistic are evaluated only when both arm-cell counts are positive.

Lemma 12 [lem:continuous-occupancy-collision-upper-all-d] (Continuous occupancy collision bound).

For every overlap parameter , there is a constant such that the following holds.

  • (Sample size and alphabet.) The integers and satisfy and .

  • (Model.) The distribution belongs to from Definition 1, with its corresponding bounds on and .

  • (Estimator.) The estimator is the clipped occupancy-weighted treated-control estimator defined in Algorithm 2 with clipping level .

Then

⊢ Lean
Proof of Lemma 12.

Fix . Let be the constants in Lemma 6, and set These constants are positive. Now fix , real parameters , and as in Definition 1; let be the -fold observed-data law.

Write the unclipped statistic in Algorithm 2 with its zero fallback as and write its design-centered version, totalized in the same way, as On , the difference is the finite-design weighted sum of supported arm-cell residuals with value on . The coefficients in this display depend only on the finite design . Expanding the square therefore gives products of two supported residuals multiplied by a product of finite-design coefficients. When the two sample coordinates are distinct, the product-law integral is zero after conditioning on the finite design of the other coordinates and integrating one coordinate over its arm-cell fibers; the centering used is exactly When the two factors use the same coordinate but different arm-cell labels, their supports are disjoint, so the product is pointwise zero. The remaining same-coordinate, same-label terms are bounded by the arm-cell second central moments from Assumption 6, and summing the coordinate indicators gives the arm-cell counts. Hence

It remains to compare the design factor in the last display with reciprocal usable occupancy. Push the sample to the finite design . In each positive-mass cell, the overlap condition in Assumption 3 gives both arm probabilities at least , equivalently . A cell-label configuration that places an observation in a zero-mass cell has zero joint design weight, so it contributes zero before any conditional arm probability is formed.

Fix a positive-mass cell , a cell-label configuration, and the arm assignments outside . Let for this fixed cell-label configuration, and let be the usable count contributed by all other cells under the fixed outside arm assignments. For , the cell cannot be crossed and its local variance and local reciprocal-occupancy share are both zero. For , summing only over the arm assignments inside cell gives the local finite-binomial comparison The denominator is the squared global usable count that applies when cell is crossed; it is kept inside the local term throughout the comparison. The displayed inequality follows from the binomial inverse-arm bound and the interior-mass lower bound Summing the local comparison over cells and outside assignments gives the finite-design inequality with constant . We retain the weaker constant , obtaining Combining the last two displays yields

The centered design bias obeys Indeed, because is the product observed-data law, every empirically usable cell has positive population mass almost surely: if , then no observation falls in cell almost surely. On this full-probability event and on , so is a convex average of deviations for positive-mass cells. The homogeneity condition in Assumption 5 gives there. On , the totalized definition gives , and by Lemma 1.

Put Since , , and Lemma 6 gives The elementary inequality follows from with . Also

The clipping interval contains by Lemma 1, so clipping the inner statistic to is a contraction of squared distance from . Together with , the preceding bounds give Using the two preceding displays and the definition of , which is the asserted bound.

Lemma 12 supplies the collision branch uniformly over all alphabet sizes. The three terms have the same interpretation as in the main text: ordinary sampling variation, the radius-controlled cost of replacing uncrossed cell effects by crossed-cell information, and the sparse-cell occupancy contribution.

The polynomial branch is calibrated by choosing the degree and the active range so that the fixed-branch inequality can be summed over the pilot-induced heavy-light split. The next result packages that calibration for the total estimator in Algorithm 1.

Lemma 13 [lem:continuous-ratio-polynomial-upper-all-d] (All-alphabet polynomial upper bound).

For every overlap parameter , there exist a constant and a polynomial handle, consisting of a cutoff and an active-range multiplier such that for all integers , with the following properties.

  • (Complexity.) The handle admits a constant , independent of , and , such that for every and the post-aggregation polynomial program for has at most arithmetic operations.

  • (Total bounded estimator.) For every pair of integers and every , the estimator determined by this handle is a measurable function of the -sample observed data and satisfies for every sample .

  • (Risk bound.) For every pair of integers , every , every , and every as in Definition 1,

⊢ Lean
Proof of Lemma 13.

Fix . Lemma 11 supplies a constant for every deterministic heavy set satisfying the heavy-band and light-scale eligibility inequalities.

Choose large enough that, for all ,

Set . The pair is a polynomial handle in the sense of Algorithm 1: whenever , , , and , the handle certifies .

For every and , the estimator determined by this handle is measurable and takes values in .

The post-aggregation complexity certificate uses the aggregate table associated with Algorithm 1: pilot cell counts, estimation-block arm counts, and estimation-block arm outcome sums. Consider arithmetic programs over this table in which constants and table reads have zero structural cost; arithmetic and comparison nodes have unit cost; a cell sum contributes accumulator operations plus the costs of its cell bodies; an -term polynomial-order sum contributes accumulator operations plus the costs of its term bodies; a falling-factorial primitive of order has cost ; and a cell-subtraction primitive has cost one. For every and , there is such a post-aggregation program computing the handle-indexed estimator on every sample and satisfying On the active branch, this program evaluates the heavy contribution, the Chebyshev light sums, the cell sum, and the clipping operation from the aggregate table; on the inactive branch, it is the constant-zero program. Thus the complexity item holds with .

Now work on the active range and , and fix as in Definition 1. With and , condition on the pilot block. The good pilot event is the simultaneous eligibility event On this event, the realized set is eligible with lower band and upper band . Since , the calibration gives , so the light-scale hypothesis of Lemma 11 holds for every . The same active-range calibration gives

Applying Lemma 11 conditionally on the pilot block, then using the uniform cardinality, total-mass, and missing-envelope bounds built into the fixed-branch simplification, gives for every eligible deterministic branch where

The rate algebra uses the concrete hypotheses , , and to bound this normalized deterministic-branch expression by with

At the calibrated pilot bands, the bad-selector probability satisfies The finite-selector inequality for the clipped normalized statistic therefore gives a normalized stream-risk bound with penalty . Since the active range has and the cutoff gives , Thus the clipped normalized active-branch risk is bounded by

Rescaling the clipped normalized bound by gives On the active range with , implies , so this is the stated active-range bound with .

It remains to cover the inactive branch of Algorithm 1. There the estimator is the zero fallback and Definition 1 gives , hence its mean-squared error is at most . The fallback rate certificate splits the inactive condition into the two cases used by the handle: if , the finite cutoff makes a constant multiple of at least one; if , then is bounded below by . A constant therefore satisfies throughout the inactive branch. Taking the final risk constant to dominate both and proves the all-alphabet risk bound.

Lemma 13 turns the light-cell analysis into a usable estimator bound. The zero fallback in the inactive range keeps the estimator total for every , and the displayed risk bound gives the polynomial scale used by the selector in Algorithm 3. The operation count records that, after aggregation by cell and order, the implementation grows polynomially in the alphabet size and degree.

The finite-range construction theorem combines the polynomial and collision branches before the all-alphabet packaging in Theorem 1. It keeps the calibrated active range explicit, which is useful for downstream statements that invoke the original range condition.

Theorem 6 [thm:robust-upper-construction-resolution] (Robust upper construction).

For every overlap parameter , there exist constants and a calibrated polynomial handle consisting of a cutoff and an active-range multiplier such that, for every , implies that the associated polynomial degree is at least . For every , , and , the handle-indexed polynomial estimator and the occupancy-weighted estimator of Algorithm 2 are measurable functions of the sample and take values in .

If, in addition, then for every as defined in Definition 1, and

⊢ Lean

Theorem 6 states the two estimators on the same calibrated range. The polynomial branch contributes the large-alphabet approximation rate, and the occupancy branch contributes the radius-sensitive collision rate. Since both estimators are clipped into , the selector can compare their deterministic benchmark terms within the admissible class of Definition 5.

The final result in this appendix is the restricted selector bound. It is the finite-range version of the selector statement used in the main text and follows by applying the branch with the smaller displayed nonparametric benchmark.

Theorem 7 [thm:frontier-upper] (Restricted frontier upper bound).

For every overlap parameter with , there exist constants and a polynomial calibration handle with such that, for all positive integers , where is the active polynomial degree in the polynomial estimator. For every , assume:

  • (Sample and alphabet.) and .

  • (Envelope and radius.) and .

  • (Restricted dimension.)

Let be the polynomial estimator determined by this handle, let be the collision estimator, and let be the known-radius selector of Algorithm 3 applied to , , and . Put Then , and for every in Definition 1,

⊢ Lean

Theorem 7 records the finite-range selector guarantee behind the all-alphabet statement in Theorem 2. The benchmark combines the parametric term with the smallest of the clipped-zero, polynomial, and collision remainders. This is the constructive upper-bound input used when the main bracket is assembled in Theorem 4.

Proofs for lower bounds and regime algebra

This appendix records the auxiliary lower-bound and algebraic statements that support the main bracket. The proof has four mechanisms. The parametric lower bound supplies the sampling term. The exact-homogeneity transport supplies the capped collision baseline . The radius-channel transport supplies the rare-cell term . The final rate algebra compares these lower benchmarks with the selector benchmark and identifies the matched regimes and residual wedge.

Lemma 14 [lem:parametric-lower] (Parametric minimax lower bound).

For every overlap parameter satisfying , there exists a constant such that the following holds. For every and every , suppose that

  • (Sample and alphabet sizes.) and ;

  • (Outcome radius.) ;

  • (Noise radius.) .

Then the minimax mean-squared risk of Definition 5 satisfies

⊢ Lean
Proof of Lemma 14.

Take

Fix satisfying the displayed hypotheses, and choose a cell . Put Thus and . Moreover,

For , let be the one-cell test law with , , control potential outcome , and treated potential outcome distributed on with mean . Equivalently, draw with probability independently of this treated endpoint and set . Thus, for every cell , arm , and measurable , so the conditional exchangeability requirement in Definition 1 holds, and consistency holds from . The same construction has cell mass one at , overlap , conditional means and , second central moments bounded by , and cell deviation . Together with , , and , this gives

The targets are

Introduce the binary one-cell endpoint pair used for the comparison, and write for its -fold binary observed law under . Both source laws have the unique cell, propensity , and control endpoint probability . The null source law has treated endpoint probability , while the perturbed source law has treated endpoint probability ; this is admissible because and . The one-observation chi-square calculation gives The null one-observation atoms are positive, and tensorization gives Since we have . The chi-square-to-total-variation inequality and symmetry of total variation therefore yield The two real observed -sample laws are the corresponding images under the coordinatewise affine map

Therefore, by data processing for total variation,

For any measurable estimator , the two-point testing inequality gives

The supremum over is finite because and by Lemma 1, so the preceding bound passes through the estimator infimum in Definition 5. Using ,

Lemma 14 anchors the lower benchmark at the scale of estimating a bounded real mean from observations. This component is combined below with the exact-homogeneity collision scale and the radius-channel rare-cell scale.

The radius-sensitive converse is organized through a channel from binary source experiments into the real-outcome class. The channel preserves the cell and treatment-assignment structure, contracts binary response contrasts by , and then rescales by .

Definition 12 [synth_5] (Radius-channel hard-family embedding).

For , set . The embedding sends a binary source law from the radius-channel hard family, after padding unused cells with zero mass in the -alphabet, to the real-outcome law obtained by the hypothesis-independent channel For source laws and in the realized family, the embedded targets satisfy

Definition 12 is the finite-sample transport map used in the radius-channel lower bound. The target identity shows that a binary separation for becomes an average-treatment-effect separation with scale in the embedded real-outcome experiment.

The next two transport lemmas calibrate the capped alphabet sizes for the exact-homogeneity and radius-channel components. Their role is purely quantitative: they convert the published binary lower-risk levels into the normalized expressions used by the finite-range bracket.

Lemma 15 [lem:capped-exact-transport-package] (Capped exact transport scale).

For every overlap level , there exist constants and a cutoff such that the following properties hold.

  • (Capped alphabet.) For every pair of integers , define the exact capped alphabet size from Algorithm 4 by Then , and whenever ,

  • (Estimator-wise source risk.) For every , with defined above, there is a real number such that every measurable estimator admits an exactly homogeneous binary law over cells at overlap for which

  • (Transport normalization.) For every , with the same , and for every ,

⊢ Lean
Proof of Lemma 15.

Fix . Let and be the constants in Lemma 4. Set The two real constants have the asserted signs, and is a natural cutoff.

For , put Since , immediately If , then , so . Together with , this gives , and therefore

It remains to construct . First suppose Then because . Define The quantity is positive. Hence lies strictly below , and Lemma 4 gives Since is strictly below the displayed minimax lower bound, the definition of the infimum and supremum implies that every measurable estimator has some exactly homogeneous binary source law over cells such that

In this large-source case, If , then and . If , then and , so ; together with , this absorbs both terms on the left.

Since , the preceding display gives, for every ,

Now consider the complementary case: either or . Define Since , the exact binary source class over cells contains the following two uniform-mass endpoint laws. In both laws the propensity is in every cell and the control-arm binary mean is in every cell. Under , the treated-arm binary mean is ; under , it is , where The inequality gives , so both endpoint laws are valid binary laws with overlap and a common cell effect. Their source targets satisfy Moreover so the Bernoulli-product total-variation bound gives The two-point testing bound therefore gives the exact-source minimax inequality Because , the same infimum-supremum argument yields: every measurable estimator has some exactly homogeneous binary source law over cells satisfying

In this fallback case, Indeed, if , then ; if , then . In either case the right side dominates , and the displayed bound follows.

Because , this gives The two cases supply the same capped alphabet properties, the estimator-wise source risk, and the transport normalization for all .

The exact transport package expresses the binary exactly homogeneous collision lower bound at the scale of the real-outcome target. The capped alphabet keeps the embedded source within the available cells, while the normalization clause yields the baseline .

Lemma 16 [lem:capped-radial-transport-scale] (Capped radial transport scale).

Let be integers and let . Suppose that

  • (Sample size.) .

  • (Alphabet size.) .

  • (Scale.) .

  • (Radial cap.) .

  • (Range.) .

Define the capped radial alphabet size from Algorithm 4 by Then

⊢ Lean
Proof of Lemma 16.

Let Since , both and are positive, , and the denominator is positive. The range assumption gives , hence and .

First, If , then . The fraction is nonnegative, so is nonnegative and at most . Together with , this gives If , then . Since , , and positivity of gives Also and , so the desired inequality follows in this case as well.

Both sides of the preceding inequality are nonnegative, hence squaring gives It remains to rewrite the squared minimum. Since , Indeed, if , then the left minimum is , and nonnegativity gives . If , then the left minimum is , and nonnegativity gives . Using also , the squared inequality becomes Since , Adding the nonnegative term on the right therefore yields

Multiplying this inequality by the nonnegative factor and simplifying constants yields

Lemma 16 translates the source lower-risk scale into the rare-cell expression . The capped matches the radius-channel construction in Algorithm 4.

Small sample sizes are absorbed by a separate finite-sample comparison. This keeps the radius-channel lower bound calibrated uniformly over the range in which the asymptotic radial cap is inactive.

Lemma 17 [lem:finite-sample-radial-transport-scale] (Finite-sample radial scale).

Let satisfy , and let . Define Then

⊢ Lean
Proof of Lemma 17.

Put The minimum is bounded by its first entry, so The assumptions imply . Hence since the remaining factors are squares. Multiplying the preceding minimum bound by this nonnegative factor gives

The same assumptions give Multiplying this reciprocal bound by the nonnegative factors , , and yields

Finally, which proves the claim.

Together, Lemmas 16 and 17 supply the scale algebra behind the finite-range radius-channel converse. The converse itself combines the transported radial component with the parametric and exact-homogeneity components.

Theorem 8 [thm:radius-channel-converse] (Radius-channel converse).

For every overlap parameter satisfying , there exist constants and such that For every , , and , suppose that

  • (Sample and alphabet.) and .

  • (Scale and radius.) and .

  • (Restricted range.)

Then the minimax risk from Definition 5 satisfies Moreover, the radius-channel hard family can be realized with the same constants: there are an integer cap, a source class, a padding map into the -alphabet, an embedding of the source laws into real-outcome laws, and a coupling for the binary full-observation experiment such that the realized radial-channel data have radius parameter , and for all source laws and , For every total measurable -valued estimator , some source law in this realized family satisfies

⊢ Lean

Theorem 8 establishes the finite-range lower benchmark used in the original calibrated bracket. Its first two terms give the parametric and collision baseline, and the final term is the radius-channel contribution. The displayed source-target identity records the mechanism of the transport: source contrasts in become real-outcome contrasts in through the attenuation and the outcome scale , as in classical two-point and fuzzy-hypothesis lower-bound arguments (Le Cam, 1986; Tsybakov, 2009; Cai et al., 2011; Donoho et al., 1990).

Combining the finite-range converse with the constructive selector upper bound gives the restricted-range bracket. This statement is the calibrated predecessor of the all-alphabet bracket in Theorem 4.

Theorem 9 [thm:two-sided-minimax-bracket] (Two-sided minimax bracket).

For every overlap parameter with , there exist real constants and such that For every pair of positive integers and every , assume:

  • (Scale.) .

  • (Radius.) .

  • (Range.)

Let be the minimax mean-squared risk in Definition 5. Then

⊢ Lean

Theorem 9 places the finite-range upper and lower benchmarks on the same model class and loss scale. The upper expression is the selector rate, while the lower expression adds the exact-homogeneity baseline to the radius-sensitive rare-cell component. This form is useful for comparisons that keep below the displayed calibrated range.

The endpoint reductions identify the two boundary cases of the finite-range bracket. Exact homogeneity reduces the selector and converse expressions to the collision rate, while radius two aligns the radius-indexed class with the unrestricted-radius class.

Proposition 4 [prop:endpoint-reductions] (Endpoint rate reductions).

For every overlap parameter , there exist constants such that Write Then the following statements hold.

  • (Exact-homogeneity endpoint.) For all integers such that the upper-frontier expression and the capped converse expression are both comparable to : and

  • (Radius-two class identity.) For every integer and every , the radius-two class in Definition 1 and the unrestricted class in Definition 2 have exactly the same attainable laws: every law in is the law of some member of , and every law in is the law of some member of .

  • (Radius-two endpoint.) For all integers , the upper-frontier expression at radius two is exactly and the capped converse expression at radius two, is comparable to the same rate:

⊢ Lean

Proposition 4 gives the finite-range endpoint algebra behind the rate discussion. At , the polynomial branch and the collision lower benchmark reduce to within the calibrated range. At , the radius-indexed law class equals the unrestricted-radius class from Definition 2, and the upper expression is the polynomial large-alphabet rate.

The final result in this appendix localizes the regimes in which the finite-range bracket is order matched. It uses the baseline , the polynomial scale , the triangular selector benchmark , and the product-form triangular benchmark . The theorem statement below introduces the local shorthand for that product-form benchmark.

Theorem 10 [thm:fixed-interior-tightness-and-shrinking-radius-gap] (Fixed-interior gap characterization).

For every overlap parameter with , there is a constant such that the following statements hold. Write and Also let denote the frontier rate and let be the minimax mean-squared risk in Definition 5.

  • (Triangular benchmark algebra.) For all and all , if then

  • (Fixed interior radii.) For every , there are constants with such that, for all and , if then

  • (Matching elbows.) For every , there are constants with such that, for all and , if and at least one of holds, then

  • (Exact algebraic elbow.) For all with ,

  • (Residual wedge implication.) For every alphabet sequence and radius sequence , if eventually and then the sequence lies in the residual wedge:

  • (Witness sequence.) The sequence and lies in the residual wedge. Along this sequence,

⊢ Lean

Theorem 10 gives the finite-range phase algebra supporting the matched-regime discussion in the main text. For every radius bounded below by a positive constant, the minimax risk is comparable to over the calibrated alphabet range. The same comparison holds at the saturation and parametric-dominance elbows. In the triangular region , the theorem separates the selector expression from the converse expression , and the witness sequence shows that the residual shrinking-radius region has logarithmic benchmark separation.

Verification note

This appendix records the scope of the machine-checked mathematical layer supporting the paper. The formalization covers the finite-cell observed-data model, the radius-indexed real-outcome classes, the estimators, the embeddings used for lower bounds, the selector risk bound, the endpoint reductions, the all-alphabet minimax bracket, and the regime-localization algebra. The displayed binary source lemmas are checked declarations in the current artifact; Zeng et al. (2024) supplies their statistical origin and attribution. Other citations supply source motivation and statistical context.

The setup objects are represented by Assumptions 1, 2, 3, 4, 5, and 6, together with the model, experiment, target, and risk definitions in Definitions 1, 2, 3, 4, and 5. The scale-normalization step is represented by Lemma 1. These statements fix the statistical experiment whose minimax risk is studied throughout the paper.

The constructive side is represented by the estimator definitions in Algorithms 1, 2, and 3 and by the risk guarantees in Theorems 1 and 2. The lower-bound side is represented by the embedding and least-favorable constructions in Algorithm 4, Definition 8, and Definition 9, the binary-to-real transfer in Proposition 1, the exact-homogeneity lower transfer in Lemma 2, and the radius-channel converse in Theorem 3. The binary source lemmas in Lemmas 3, 4, 5, and 6 are checked declarations with faithful proof audits in the verification contract, while Zeng et al. (2024) supplies their origin and statistical context.

The paper’s main synthesis is represented by Theorem 4, Proposition 2, and Theorem 5. These statements assemble the all-alphabet bracket, identify the endpoint reductions, and characterize the fixed-radius, saturation, parametric-dominance, and residual shrinking-radius regimes. The binary source lemmas displayed above are checked declarations in this artifact, with citations supplying attribution and statistical context. The separate comparison proposition in Proposition 3 is checked as a conditional implication from the published binary collision guarantee displayed in its statement. The open regime description in Remark 1 is part of the recorded statement layer.

The anchored theorem, proposition, lemma, definition, and assumption statements displayed in the paper are machine-checked in Lean 4 at verification contract commit 462a124d29ae27887f711787ac2bc60f6b7e6e2f. The main bracket in Theorem 4, selector upper bound in Theorem 2, radius-channel converse in Theorem 3, endpoint reductions in Proposition 2, and regime theorem in Theorem 5 are checked statements with faithful proof audits. The binary source lemmas in Lemmas 3, 4, 5, and 6 are discharged checked declarations in the artifact. The comparison proposition in Proposition 3 is checked as a conditional implication from its displayed published-collision hypothesis. Citations otherwise provide attribution and statistical context. The Lean toolchain is pinned by lean-toolchain to leanprover/lean4:v4.33.0; the repository build is invoked with lake -d CausalSmith build. The declaration names, source files, and paper object labels are recorded in verification_contract.json and presentation_crosswalk.json in the bundle.

Proofs of the main results

Proof of Lemma 1.

Fix . Since , we have . For every supported cell ,

For every cell , the product term in the all-cell formula of Definition 4 satisfies Indeed, the cell-mass range gives either or . In the first case both sides are zero. In the second case, using the supported-cell bound above and . The finite cell masses satisfy

Hence, using the all-cell formula of Definition 4,

Therefore, for every supported cell ,

The radius-two membership follows by keeping the same law and the same consistency, exchangeability, overlap, mean-normalization, and second-moment witnesses, using the numerical facts , and adding the just-proved supported-cell bound as the approximate-homogeneity witness. Thus every law in is represented in . Conversely, a member of carries all fields required for ; forgetting the homogeneity and radius fields leaves the same law.

Proof of Theorem 7.
  1. Fix an overlap parameter with . By Theorem 1, choose and a polynomial handle , with , such that for all positive integers . The same construction gives, for every , every , and every , measurable -valued estimators and , and for every , and Set Then and , so both displayed risk bounds hold with in place of .

  2. For fixed admissible , put The known-radius selector of Algorithm 3 is the three-branch estimator The first two branches are elements of by the construction above. The zero branch is measurable and takes values in because . Hence .

  3. Fix . On the collision branch, , so Therefore On the polynomial branch, , so Thus It remains to consider the zero branch. There These inequalities imply : if , then , while ; if this gives , and if it gives . Hence . The first zero-branch inequality then gives , so , and Viewing the same law as a member of the unrestricted-radius class, the scale bound in Lemma 1 gives Since the selected estimator is identically zero on this branch, where the penultimate inequality uses and . Together the three branches prove the asserted risk bound for every .

  4. Put . Then . The preceding all-alphabet bound applies to every positive , so it applies in particular under the restricted-dimensional hypothesis The constants and the same polynomial handle therefore satisfy all claims of the theorem.

Proof of Proposition 4.
  1. First record the logarithmic estimate used below. If , then The standard bound , together with and , gives Squaring yields

  2. We prove the all-alphabet comparison that supplies the constants. For , put Since , both and are nonnegative. At radius two the collision term is and therefore At radius zero, and the capped converse expression at radius zero is exactly the right-hand side.

    It remains to compare the radius-two converse term with If , then so and Consequently If , the logarithmic estimate from the previous step gives Hence The upper-frontier term at radius zero is at least , so The remaining upper bound at radius zero follows from the displayed monotonicity inequality. For radius two, nonnegativity gives the lower bound while gives Thus, uniformly over all , the all-alphabet comparisons hold with The radius-two equality of attainable laws is exactly the consequence of Lemma 1.

  3. Now fix and choose Then and . Suppose and Because , Applying the all-alphabet comparison from the previous step and replacing the capped term by gives and The class identity is the radius-two conclusion of Lemma 1. Finally, the all-alphabet radius-two calculation gives, for every , and its converse comparison gives

Proof of Theorem 8.
  1. Fix an overlap parameter with . Apply Theorem 3 to obtain constants and such that and, for every admissible , Set and .

  2. Now fix satisfying the hypotheses of the present statement, and put Since , we have , hence The restricted range and give Because , division by yields Substituting this identity into the all-alphabet bound displayed above gives

  3. The radial certificate supplied by Theorem 3 uses the same constants and . Unpacking the certificate, there are an integer cap , a binary control-zero source class , a padding map into the -alphabet, an embedding that sends each source member into , and binary full-observation couplings such that the channel acts by The source target in this certificate is the total treated-arm weighted functional where is the treated-arm binary mean coordinate carried by the source law in cell , defined for every source cell including zero-mass cells. Thus, for all , the same certificate gives It also gives the estimator-wise lower bound: for every , the class of total measurable -valued estimators from Definition 5, there is such that

Proof of Theorem 6.

Fix an overlap parameter with .

  1. First form the all-alphabet package. By Lemma 13, there are and a polynomial handle such that, for all integers , and, for every , , and , The same cited construction gives measurability of and

    By Lemma 12, there is such that, for every , , , and , For the admissibility of the collision estimator, write its unclipped inner statistic as the total sample function Here denotes . The displayed arm factors are total functions of the sample and agree with the arm-cell means of Algorithm 2 on positive arm-cell counts; multiplication by selects exactly the cells where both arm-cell counts are positive. Hence Algorithm 2 gives The counts, indicators, outcome totals, finite sums, totalized ratios, and the fallback at are measurable functions of the sample, so is measurable. Since , clipping gives

    Set Then . The two displayed rate factors are nonnegative for and , and ; hence replacing and by preserves the two upper bounds.

  2. Define Then . For arbitrary , , and , the all-alphabet package from the first step gives the measurability and range assertions for both estimators. If then for every the same all-alphabet risk bounds apply under this range condition: and Together with the active-range property of , these are the asserted constants and calibrated handle.

Proof of Theorem 10.
  1. Fix , and apply Theorem 5 at this . Choose the range constant Then . The triangular benchmark algebra, the exact algebraic elbow, the residual wedge implication, and the diagonal witness assertions in the present statement are exactly the corresponding conclusions supplied by Theorem 5, with the same definitions of , , , , , and . In particular, the denominator in the residual-wedge ratio is the capped converse benchmark so the all-alphabet residual-wedge implication gives precisely For the witness , , the same all-alphabet conclusion gives membership in the residual wedge and the two displayed comparisons

  2. It remains only to specialize the fixed-interior and matching-elbow minimax clauses. Let . The fixed-radius clause of Theorem 5 supplies constants with such that, for all , , imply Since the implication holds for every positive , it also holds under the additional displayed range condition Thus the fixed-interior-radii conclusion follows with the same constants .

  3. Now fix . The matching-elbow clause of Theorem 5 supplies constants with such that, whenever and at least one of holds, one has This is exactly the matching-elbows assertion in the present theorem. Combining this with the clauses recorded in the first step and the choice proves all asserted conclusions.

Proof of Theorem 9.
  1. Fix an overlap parameter with . By Theorem 4, choose constants and such that and such that, for every , , and , and These constants already have the normalization required in the statement.

  2. Now fix , , and , and assume Since , The numerator is nonnegative, so where the last inequality uses . Dividing by gives Substituting this identity into the lower bound from the preceding step yields The upper bound is exactly the upper bound supplied in the preceding step. Therefore the displayed lower and upper bounds hold throughout the stated restricted range.

Proof of Lemma 2.

Fix . Let and be the constants supplied by Lemma 4. Let be the constant in Lemma 14. Set Then , , and .

Fix , , and . Put First suppose that Define the capped source alphabet size Then , , and The exact binary source bound gives where denotes the minimax risk over the uniform-mass exactly homogeneous binary source experiment. Since and , the source lower-risk level is strictly below . Hence, for every measurable binary estimator there is a source law such that

Embed this source law into the -cell real-outcome experiment by zero-mass padding and by the affine outcome map The padding keeps the source cells inside the first target cells and assigns zero mass to cells . The affine map gives conditional means in , conditional second central moments bounded by , and exact homogeneity; with the assumed bounds on , , and , the embedded law belongs to Write for this embedded real law. Its target satisfies and the observed-data law is the pushforward of the binary observed-data law under the padded affine sample map. Thus every from Definition 5 induces a measurable binary estimator by applying after that sample map, and

It remains in this branch to compare the capped source rate with the desired all- rate. Since , If , then and . If , then and . In both cases, Since ,

On the complementary branch, either or . In the first case, ; in the second, , so . Thus, in either case, Using and Lemma 14,

Combining the two cases proves the stated bound for all , , and .

Proof of Theorem 1.

Fix an overlap parameter .

  1. By Lemma 13, choose and a polynomial handle . The handle has and satisfies the calibration clause for all integers . The same lemma gives, for every , , , and , that the estimator indexed by this handle is measurable, takes values in , and satisfies

  2. By Lemma 12, choose such that, for every and every , Here the bounds and are the corresponding model-class fields in from Definition 1.

  3. The collision estimator also has the required admissibility property. For a sample , Algorithm 2 defines where each empirical arm-cell mean is the indicator-totalized ratio on and is assigned value when . The counts are finite sums of sample indicators, the totals are finite sums of indicator-weighted outcomes, and the branches use measurable comparisons, arithmetic operations, and a finite sum over cells. Thus the inner statistic is a measurable function of the -sample. Since gives , clipping to is measurable and has range contained in . Therefore is a measurable map of the sample and satisfies

  4. Define Then . For and , Together with , the inequalities and upgrade the two pointwise risk inequalities above to the same inequalities with . With , the calibration, measurability, range, and pointwise risk clauses hold simultaneously for every , , , and every from Definition 1. Since the resulting right-hand sides do not depend on , taking the supremum over gives the two displayed supremum inequalities.

Proof of Theorem 2.

Fix .

Step 1. Common calibration and envelopes. By Theorem 1, choose a polynomial handle , with , and a constant . Put Then , , and . The selected handle carries the displayed calibration implication for : for all integers , For fixed integers , , and , define The construction also gives measurable -valued estimators and , and for every , and

Step 2. The selector is admissible. The known-radius rule in Algorithm 3 is The first two branches are measurable and take values in by Theorem 1. The zero branch is measurable and also takes values in because . Hence is measurable and for every sample .

Step 3. Collision branch. Assume Then , and Therefore, for every , where the last inequality uses and the nonnegativity of .

Step 4. Polynomial branch. Assume the collision-branch condition fails and Then , Hence, for every , again because and the rate factor is nonnegative.

Step 5. Zero branch. It remains to consider the branch in which These two inequalities imply : if , then the first inequality gives , while the second gives , a contradiction whether or . With , the first displayed inequality gives , and consequently On this branch . Viewing the law of as a member of the unrestricted class obtained by forgetting the radius condition, Lemma 1 gives Thus Since , , and ,

Combining the three branches yields, for every , Together with the measurability and range conclusion in Step 2, this proves the stated selector guarantee.

Proof of Proposition 2.

Take and . Fix integers , and write Also set The quantities , , and are nonnegative.

  1. Since , and hence . At radius two the collision term is Therefore This proves the endpoint identity, and also gives the two-sided comparison of the radius-two upper frontier expression with , because and .

  2. We use the elementary logarithmic estimate Indeed, , while and . Thus and squaring gives .

  3. First consider the case . Since , Consequently The radius-zero converse expression is also exactly For the radius-two converse expression, and, using , All required comparisons in this case follow from .

  4. Now consider the case . By the logarithmic estimate, The radius-zero upper expression satisfies and Hence The radius-zero converse expression again equals . For the radius-two converse expression, and Together with the radius-two identity from the first step, this proves the stated two-sided comparisons in the second case.

  5. It remains to identify the two radius-two classes. By Lemma 1, for every , every , and every , each law in is represented by some member of with the same law, and conversely each law in is represented by some member of with the same law. Thus the represented laws are exactly the same at radius two.

Proof of Theorem 5.

Fix . The proof starts from the all-alphabet bracket in Theorem 4; write for the capped converse benchmark appearing there.

In the triangular region , set , , , and . The two triangular inequalities give , and the selector benchmark is For nonnegative with , the lower bound follows by splitting according as or , while the upper bound follows by splitting according as or . These two checks give Thus and the product benchmark is, by definition,

For every radius floor , put If , then , and the frontier and converse benchmarks satisfy Combining this comparison with Theorem 4, which gives yields the fixed-radius constants and :

For the matching elbows, the benchmark comparison used with the same bracket is When , where the last inequality is checked by the two cases and . When , the case gives and the case gives . When , the case gives and the case is again . The all-alphabet bracket therefore gives the matching-elbow minimax equivalence with lower constant and upper constant .

For , the logarithmic factor is positive. Expanding , multiplying by the positive denominator , and collecting terms gives

The sufficient elbows are the two displayed consequences of this algebra. If , then ; if , then . In either case the exact algebraic elbow gives .

For the residual-wedge implication, write along the sequence , , , , and . Since , the matching-elbow comparison implies that, for every fixed , eventually Taking for arbitrary gives and . To prove , fix , put , and set . Divergence makes eventually; on the same tail, would give by the fixed-radius comparison. Hence eventually, so eventually.

It remains to show . Fix . If , the eventual inequality gives . If , use the eventual bounds , , , and . At any point on this tail with , the inequality and give and . Consequently and with implies , a contradiction. Thus eventually. Together with the assumed eventual admissibility, these four limits are exactly the residual-wedge conditions.

For the diagonal sequence and , eventual admissibility follows from . Direct simplification gives, for , The logarithmic facts and for each fixed yield Hence the diagonal sequence lies in the residual wedge.

Along the same sequence, the exact benchmark formulas are Since , these formulas give eventually Thus the diagonal benchmark ratio is of order , and because , the ratio diverges.

Proof of Theorem 4.
  1. Fix an overlap parameter with . By Theorem 2, choose a constant and a polynomial calibration handle such that, for every , , and , the corresponding known-radius selector satisfies By Theorem 3, choose and such that and, for every such , Set Then

  2. Fix , , and . The lower bound is exactly the one supplied by Theorem 3 with the constants fixed above: The accompanying radius-channel certificate in Theorem 3 also supplies a realized source family and an embedding into the same model class. Applying its source-risk assertion to the zero source estimator gives a source law, and the embedding-membership part of the certificate gives an embedded law with Thus the model class is nonempty for these indices.

  3. For any estimator , define its worst-case risk over this class by We first record the lower-boundedness needed to apply the infimum in Definition 5. Fix . In the vacuous branch where the model index is empty, the real supremum convention gives . In the nonvacuous branch, consider the range of mean-squared errors indexed by . If this range is bounded above, choose any law in the class; its mean-squared error is the integral of a square and is therefore nonnegative, and it is bounded by the supremum defining . If the range is unbounded above, the supremum is in its unbounded-above case and the inequality is immediate. Hence The collection of worst-case risks is therefore bounded below by . Using Definition 5 and the admissibility of ,

  4. Applying the selector guarantee from Theorem 2 gives Moreover, so Therefore , and implies Combining the previous displays yields Together with the lower bound supplied by Theorem 3 and instantiated above, this proves the asserted bracket for all , , and .

Proof of Proposition 3.

Fix and assume the published binary collision guarantee stated in the proposition. We prove the simultaneous conclusion in three steps.

  1. The assumed guarantee is exactly the first component of the simultaneous assertion: it supplies the stated constants and the two displayed bias and variance bounds for every admissible , and .

  2. For the pointwise algebraic comparison, fix and in the stated range. The defining order property of the minimum gives This is the asserted pointwise inequality.

  3. For the asymptotic comparison, let and satisfy the stated sequence hypotheses. Limits along are unchanged by discarding finitely many initial indices, so work on the cofinal set . There , and hence Also , , and . Therefore The same minimum inequalities, now using the left branch of the inner minimum, give Dividing by the positive denominator yields, for all sufficiently large , By hypothesis the right-hand side converges to , so the squeeze theorem gives This proves the sequence comparison and completes the proof.

Proof of Proposition 1.

Fix . Write for the constant supplied by Lemma 2, take and from Theorem 3, and take and the polynomial handle from Lemma 13. Let and set Then , , , and The selected polynomial handle retains its cutoff and active-range multiplier from Lemma 13.

For each and , define to be the affine binary-to-real pushforward of Definition 8, namely . The embedding identities preserve cell masses and propensities, push each positive arm-cell binary outcome law through this affine map, and make each arm-cell mean equal to times the corresponding binary mean minus . Hence every binary law satisfying the overlap condition gives a member of as in Definition 2, and every uniform-mass exactly homogeneous binary law gives a member of the zero-radius class,

Fix a cell in the nonempty alphabet and fix . Let be the one-cell test law that puts unit cell mass on , has propensity , has control arm-cell outcome law , and has treated arm-cell outcome law given by the two-point mean-zero law on . With local mean parameter zero, this test law belongs to . For any binary law , the control arm-cell outcome law of is supported on the two affine binary values , which assign zero mass to since . The corresponding control arm-cell law of assigns mass one to . Therefore for every binary law , giving the strict-image assertion at radius .

Now fix and , and assume . Since , this gives . For the binary source experiment in Definition 10, a two-point subexperiment supplies the parametric term, as follows. Put , so that , , and . Let be the two uniform-mass exactly homogeneous binary laws with constant propensity , control-arm response mean under both, and treated-arm response mean under and under ; constant propensity meets the overlap constraint because , and both laws are exactly homogeneous because the cell contrast is the same in every cell. Their targets differ by , and the product-law calibration gives . The two-point testing bound, with centres and , threshold , and total-variation constant , therefore yields and Lemma 3 gives Together with the definition of , these two inequalities place strictly below the fixed-sample binary exact-homogeneity minimax risk. Thus every measurable binary estimator has a source law whose binary squared risk is at least this level. Applying this statement to the binary estimator obtained by composing an arbitrary clipped real-outcome estimator with the affine observation map, and using on the exact-homogeneous source class, multiplies the lower bound by . Hence every such real-outcome estimator has some satisfying

The exact-range minimax-risk bound follows from Lemma 2. Since and , the term in that all-alphabet transfer equals on the present range, giving

For the radius term, Theorem 3 supplies together with the transfer certificate with constants and . The base summand is nonnegative, so the same inequality yields

Finally, Lemma 13 supplies the selected polynomial handle. The associated estimator is measurable, takes values in , satisfies the handle’s active-range implication for , and obeys uniformly for every

Proof of Theorem 3.

Fix . Apply Lemma 5 to obtain one-arm constants with and . Put and choose Then For every with , the radial cap is positive, is at most , and satisfies The same construction gives the source-risk interface used by the channel transport: for every measurable uniformly bounded source estimator on the -sample binary one-arm experiment over cells, some control-zero source law satisfies Finally, Lemma 16, applied with cap constant , gives for every and

Choose and from Lemma 15. Let be the constant supplied by Lemma 2.

Set and define All constants in this display depend on alone, and the displayed positivity gives and .

Fix with , , , and . Form the two capped alphabets and Both caps are positive and at most . Following Algorithm 4, pad each source alphabet into the first target cells. On the radial source, apply the hypothesis-independent Bernoulli channel On the exact-homogeneity source, use the affine map . The construction preserves the source cell masses on the padded cells, assigns zero mass outside them, realizes the independent full-data couplings, and gives the radial full-data channel of Definition 12. For a radial source law , write on a positive source cell and . On each padded positive-mass cell the embedded means are and Thus the overlap bounds are inherited from the source, the mean-normalization bounds in Assumption 4 follow from and , the conditional second-moment bound in Assumption 6 follows from , and the radius condition in Assumption 5 follows from Together with consistency and conditional exchangeability from the independent full-data coupling, these checks place every radial embedding in as defined in Definition 1. Along the same embedding, The exact affine embedding has target slope .

The exact capped package supplies, for this , a source level such that every measurable exact-source estimator is defeated by some exactly homogeneous binary source law and Since , deterministic affine transport gives, for every , an exact source law satisfying where is the mean-squared error of Definition 9. This is the exact half of the common two-family transfer certificate.

For the radial half, let be the one-observation Markov kernel that maps a binary observed record to using the Bernoulli channel above. For every radial source law , the observed target law satisfies and the target identity is Consequently, whenever , the nonzero scale , the preceding observed-law identity, and the source-risk interface imply the following transport rule: if for every measurable uniformly bounded some source law satisfies and if then every has some radial source law with This is the Markov-kernel comparison applied to the radial channel. The finite-sample source interface used when the radial cutoff is unavailable is obtained from the one-arm parametric subexperiment. In the binary one-arm experiment over cells, take the two control-zero source laws whose treated functionals are and , where . The usual product total-variation calculation gives distance at most between their -sample observed laws, so the standard two-point minimax inequality gives where ranges over the control-zero one-arm source laws on cells. Since is strictly below this minimax value, the hard-source extraction from the minimax infimum and supremum gives, for every measurable uniformly bounded source estimator , a control-zero source law with If , the desired radial lower-bound term is zero; this finite-sample source law and nonnegativity of squared loss give the required estimator-wise inequality. If and , the large-sample source-risk interface and the scale comparison displayed above give The transport rule therefore gives the radial estimator-wise lower bound in the large-sample branch. If and , then . The finite-sample source interface just displayed, together with Lemma 17 and , gives the transported radial lower term in the small-sample branch. Hence for every there is a radial source law with

Combining the radial and exact estimator-wise statements gives the common transfer certificate with constant . Since , the same certificate holds with . The radial construction also carries the product data-processing certificate: writing for total variation distance, for all radial source laws , because the left product laws are obtained from the right product laws by the coordinatewise common kernel . Thus the cap identity, injective padding, source hardness, mass preservation, zero extension, full-data coupling, full-data channel law, membership in , radius bound, product data-processing bound, target scaling, and radial estimator-wise lower bound package into the radial certificate asserted in the theorem.

For the minimax lower bound, Lemma 2 gives The radial half of the transfer certificate, after embedding into and taking the minimax infimum in Definition 5, gives For two nonnegative terms bounded above by the same risk in this way, The definition of yields the displayed converse rate with constant , completing the proof.

References

  • Zeng, Zhenghao and Balakrishnan, Sivaraman and Han, Yanjun and Kennedy, Edward H. (2024). Causal Inference with High-dimensional Discrete Covariates. . 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
  • Wu, Yihong and Yang, Pengkun (2016). Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation. IEEE Transactions on Information Theory. doi
  • Hoeffding, Wassily (1948). A Class of Statistics with Asymptotically Normal Distribution. The Annals of Mathematical Statistics. doi
  • Lugosi, G{\'a}bor and Mendelson, Shahar (2019). Sub-Gaussian Estimators of the Mean of a Random Vector. The Annals of Statistics. doi
  • Rubin, Donald B. (1974). Estimating Causal Effects of Treatments in Randomized and Nonrandomized Studies. Journal of Educational Psychology. doi
  • Rubin, Donald B. (1979). Using Multivariate Matched Sampling and Regression Adjustment to Control Bias in Observational Studies. Journal of the American Statistical Association. 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
  • van der Laan, Mark J. and Robins, James M. (2003). Unified Methods for Censored Longitudinal Data and Causality. Springer. doi
  • Tsiatis, Anastasios A. (2006). Semiparametric Theory and Missing Data. Springer.
  • Imbens, Guido W. and Rubin, Donald B. (2015). Causal Inference for Statistics, Social, and Biomedical Sciences: An Introduction. Cambridge University Press.
  • Imbens, Guido W. and Wooldridge, Jeffrey M. (2009). Recent Developments in the Econometrics of Program Evaluation. Journal of Economic Literature. 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
  • Kennedy, Edward H. (2022). Semiparametric Doubly Robust Targeted Double Machine Learning: A Review. . doi
  • Kennedy, Edward H. (2023). Towards Optimal Doubly Robust Estimation of Heterogeneous Causal Effects. Electronic Journal of Statistics. doi
  • Semenova, Vira and Chernozhukov, Victor (2021). Debiased Machine Learning of Conditional Average Treatment Effects and Other Causal Functions. The Econometrics Journal. doi
  • Nie, Xinkun and Wager, Stefan (2021). Quasi-Oracle Estimation of Heterogeneous Treatment Effects. Biometrika. doi
  • Wager, Stefan and Athey, Susan (2018). Estimation and Inference of Heterogeneous Treatment Effects Using Random Forests. Journal of the American Statistical Association. doi
  • Yadlowsky, Steve (2022). Explaining Practical Differences Between Treatment Effect Estimators with High Dimensional Asymptotics. . doi
  • Jiang, Kuanhao and Mukherjee, Rajarshi and Sen, Subhabrata and Sur, Pragya (2025). A New Central Limit Theorem for the Augmented IPW Estimator: Variance Inflation, Cross-Fit Covariance and Beyond. The Annals of Statistics. doi
  • Celentano, Michael and Wainwright, Martin J. (2023). Challenges of the Inconsistency Regime: Novel Debiasing Methods for Missing Data Models. . doi
  • Robins, James M. and Li, Lingling and Tchetgen, Eric 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. arXiv
  • Robins, James M. and Li, Lingling and Mukherjee, Rajarshi and Tchetgen Tchetgen, Eric and van der Vaart, Aad W. (2017). Minimax Estimation of a Functional on a Structured High-Dimensional Model. The Annals of Statistics. 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 Forty-Third Annual ACM Symposium on Theory of Computing. doi
  • Valiant, Gregory and Valiant, Paul (2011). The Power of Linear Estimators. Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. doi
  • Valiant, Gregory and Valiant, Paul (2017). Estimating the Unseen. Journal of the ACM. doi
  • Valiant, Gregory and Valiant, Paul (2016). Instance Optimal Learning of Discrete Distributions. Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. doi
  • Wu, Yihong and Yang, Pengkun (2019). Chebyshev Polynomials, Moment Matching, and Optimal Estimation of the Unseen. The Annals of Statistics. 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
  • Donoho, David L. and Liu, Richard C. and MacGibbon, Brenda (1990). Minimax Risk over Hyperrectangles, and Implications. The Annals of Statistics. doi
  • Le Cam, Lucien (1986). Asymptotic Methods in Statistical Decision Theory. Springer. doi
  • Tsybakov, Alexandre B. (2009). Introduction to Nonparametric Estimation. Springer. doi
  • Serfling, Robert J. (1980). Approximation Theorems of Mathematical Statistics. John Wiley \& Sons. doi
  • van der Vaart, Aad W. (1998). Asymptotic Statistics. Cambridge University Press.
  • Timan, Aleksandr F. (1963). Theory of Approximation of Functions of a Real Variable. Pergamon Press.
  • Poterba, James M. and Venti, Steven F. and Wise, David A. (1994). 401(k) Plans and Tax-Deferred Saving. Studies in the Economics of Aging.
  • Poterba, James M. and Venti, Steven F. and Wise, David A. (1995). Do 401(k) Contributions Crowd Out Other Personal Saving?. Journal of Public Economics. doi