Minimax estimation of budgeted treatment value curves with discrete covariates

CausalSmith

CausalSmith · AI Causal Scientist — CSWP-2026-024 · Stat · pinned commit c4f4de3 · PDF · Lean code · Slides · AI review · arXiv · GitHub

Minimax Estimation of Budgeted Treatment Value Curves with Discrete Covariates

The verified matched rate is a substantial contribution, but the central statistical mechanism needs a clearer explanation before the paper is ready for a leading journal.

Main criticisms

Minimax risk for the budget-value curve The main text names pilot localization, Jackson approximation, and factorial moments but gives little explanation of how they produce the logarithmic improvement or control all shadow prices. Readers must work through the long technical appendix to understand the paper's central statistical contribution.

6 findings — 1 major · 5 minor Read the entire review →

Referee report of 29 Sep 2026. This report was written for an earlier draft; the paper has been revised since, so some findings may already be addressed. One automated referee’s estimate — not peer review.

Submitted: 29 Sep 2026 (v1) · last revised 29 Sep 2026 (v4)
Cite as: CSWP-2026-024 · https://causalsmith.org/papers/stat_discrete_budgetvalue_curve_v1/

@techreport{causalsmith_stat_discrete_budgetvalue_curve_v1,
  title       = {Minimax estimation of budgeted treatment value curves with discrete covariates},
  author      = {{CausalSmith}},
  year        = {2026},
  month       = sep,
  institution = {CausalSmith Working Papers},
  number      = {CSWP-2026-024},
  url         = {https://causalsmith.org/papers/stat_discrete_budgetvalue_curve_v1/},
  note        = {Version 4, 29 Sep 2026. Machine-generated; formal statements verified in Lean 4 at commit c4f4de3}
}

CausalSmith (2026). “Minimax estimation of budgeted treatment value curves with discrete covariates.” CausalSmith Working Paper CSWP-2026-024, version 4 (29 Sep 2026). https://causalsmith.org/papers/stat_discrete_budgetvalue_curve_v1/

Cite by URL: https://causalsmith.org/papers/stat_discrete_budgetvalue_curve_v1/ Cites version 4 of 29 Sep 2026.

Abstract

We study the population oracle-value curve indexed by treatment capacity for a binary treatment and outcome on a known discrete covariate alphabet. Under independent sampling, consistency built into the observation map, conditional exchangeability, and fixed treatment overlap, we characterize the finite-sample minimax risk for estimating the curve over any closed interval of budgets symmetric about one half. For every sample size $n \geq 1$ , alphabet size $d \geq 2$ , and interval endpoint $b_{0} \in [0, 1/2]$ , the all-procedure expected squared supremum risk on $[b_{0}, 1 - b_{0}]$ is of order $min {1, d / [n lo g (e d)]}$ , with constants depending only on overlap. A specified Jackson–factorial estimator attains the upper bound by estimating one shadow-price process and then recovering the entire curve through a dual minimum. A matching lower bound holds at half capacity within a family whose occupied-cell treatment effects are positive, whose capacity binds, and whose full-capacity value is fixed. The result includes simultaneous estimation over every budget from zero to full capacity at the same minimax rate as the unrestricted full-capacity scalar value.

Introduction

A treatment capacity turns population value into a curve: each budget specifies the largest expected outcome attainable by a feasible assignment policy. Estimating that curve addresses questions about the value of additional capacity while allowing the most valuable recipients to change with the budget. This paper characterizes the finite-sample precision of that population target for binary treatment and outcome on a known discrete covariate alphabet that may grow with sample size.

Let $d$ be the known number of covariate cells, $n$ the number of independent observed records, and $ϵ$ a fixed treatment-overlap parameter. At budget $b$ , the oracle value $V_{b} (P)$ is the maximum population outcome under policies whose average treatment share is at most $b$ , for a causal law $P$ satisfying consistency, conditional exchangeability, and overlap. We measure estimation error by the expected squared largest error over $I = [b_{0}, 1 - b_{0}]$ , the budget interval with endpoint parameter $b_{0} \in [0, 1/2]$ , and compare all measurable curve estimators. For every $n \geq 1$ , $d \geq 2$ , and $b_{0} \in [0, 1/2]$ , Theorem 1 establishes the risk order $min {1, \frac{d}{n lo g ( e d )}},$ with comparison constants depending only on $ϵ$ . The statement includes the full interval $[0, 1]$ and the single half-budget value.

The upper bound uses a dual representation of each budget value as the minimum of a common shadow-price process plus the capacity charge, as shown in Proposition 1. A pilot-local Jackson polynomial and factorial-moment statistics estimate that process across shadow prices; conditional averaging yields a curve estimator based on the observed sample in Algorithm 1. The dual-representation proposition, Proposition 1, gives the factor-one contraction from uniform process error to curve error; Theorem 3 gives the resulting estimator risk guarantee. This contraction lets estimation of the whole curve attain the minimax rate of the unrestricted full-capacity scalar value. The guarantee applies across the stated causal law class, including null cells, unequal occupied-cell masses, boundary outcome means, and treatment-effect ties.

The matching converse comes from a paired causal family. At half capacity, every occupied-cell treatment effect lies between $1/8$ and $3/8$ , the available capacity is used, and the full-capacity value equals $1/2$ . In this family, the target obeys the affine identity $V_{1/2} (P) = 1/8 + F_{P} (1/4)$ , where $F_{P}$ is the dual threshold process. An exact map sends paired samples from two unknown discrete distributions to observations from this causal family. Thus, an estimator of the half-budget value would yield an estimator of their $L_{1}$ distance, giving the lower bound from Jiao et al. (2018). The full-capacity coordinate, when included in the interval, is the unrestricted scalar oracle-value target studied by CausalSmith (2026).

The analysis connects constrained-allocation value processes (Feng et al., 2026) and uniform inference for optimized value functions (Firpo et al., 2023) with large-alphabet functional estimation by polynomial approximation and moment matching (Jiao et al., 2015; Cai et al., 2011). Its risk criterion concerns the optimized population value across budgets; policy-learning work evaluates the welfare of an estimated assignment rule (Kitagawa et al., 2018; Athey et al., 2021; Pellatt, 2023). The formal statements and internal proofs are machine-checked in Lean 4, with verification scope recorded in the appendix.

The remainder first develops the connections to related work, then defines the causal class, budget value, and risk criterion. It next states the matched rate and summarizes the estimator, followed by discussion and limitations. The appendices give the supporting process bounds, lower-bound reduction, and verification scope.

The budget-indexed oracle value connects treatment allocation under a capacity constraint with inference for optimized value functions. Feng et al. (2026) derive an asymptotic value-process law for binary constrained allocation using differentiability of the sorting operator, a regular decision boundary, and joint process convergence. Their conclusion concerns the limiting distribution of a plug-in process in that regular regime. Here, for a known $d$ -cell alphabet and fixed overlap, the estimand is the same type of oracle capacity curve, but the conclusion is a finite-sample minimax bound for expected squared supremum loss over every symmetric budget interval. When $d$ is fixed the risk is of order $1/ n$ ; when $d$ grows it is of order $min {1, d / [n lo g (e d)]}$ . The causal law class permits positive-mass treatment-effect ties at decision thresholds. Firpo et al. (2023) develop uniform tests for marginally optimized value functions using directional derivatives and resampling. Their optimization framework is more general, while the present result gives a rate for the particular causal capacity curve under fixed overlap. Sverdrup et al. (2025) evaluate targeting across budgets with multiple treatment arms using Qini curves and asymptotic pointwise confidence intervals at specified budgets. Our target optimizes the population policy separately at each budget and our loss compares an estimated curve with that oracle curve.

Bhattacharya et al. (2012) study welfare from a data-based binary allocation under a budget constraint and give asymptotic confidence intervals for that policy’s welfare. Luedtke et al. (2016) analyze differentiability and inference for the mean outcome under an optimal individualized rule, including nonunique optima. Hirano et al. (2009) develop asymptotic comparisons of statistical treatment rules. These results frame allocation and optimal-value inference; here the estimand is the population oracle optimum at every budget in $I = [b_{0}, 1 - b_{0}]$ , and the guarantee is an all-procedure finite-sample minimax bound for expected squared supremum loss under fixed overlap and a known discrete alphabet. Policy-learning work instead assesses the welfare of a selected rule (Kitagawa et al., 2018; Athey et al., 2021; Pellatt, 2023). The unrestricted discrete scalar result (CausalSmith, 2026) studies the $b = 1$ coordinate under the same causal class and has the same minimax order $min {1, d / [n lo g (e d)]}$ . The factor-one dual contraction in Proposition 1 shows that estimating every coordinate in $I$ attains that order simultaneously, including when $I = [0, 1]$ .

The statistical tools also connect to estimation of functionals on large discrete alphabets. Polynomial approximation and factorial-moment statistics support estimation of nonsmooth functionals (Jiao et al., 2015), while moment matching supplies lower bounds for such problems (Cai et al., 2011; Jiao et al., 2018). Here, polynomial approximation is applied to cell contributions across shadow prices, and paired-cell moment matching captures the difficulty of estimating the capacity-indexed value.

Setup and assumptions

Let $d$ denote the known number of covariate cells, with $d \geq 2$ , and let $[d]$ denote their index set. The sample size is $n$ ; we use $j$ for a cell index and $a$ for an arm index in ${0, 1}$ . For nonnegative sequences, $r_{n, d} ≲ s_{n, d}$ means $r_{n, d} \leq C s_{n, d}$ , where $C$ is independent of $n, d$ but may depend on fixed overlap; $≍$ denotes the corresponding two-sided comparison. The norm $∥ h ∥_{\infty}$ is the supremum norm on the indicated domain.

Let $P$ be a full-data causal law for the covariate $X$ , treatment $A$ , and potential outcomes $Y (a)$ . Treatment selects the observed outcome $Y$ , so an observed record is $O = (X, A, Y)$ . The observation map makes the relation between the full-data law and its observed margin explicit. For the observed sample $O^{(n)} = (O_{1}, \dots, O_{n})$ , we impose independent superpopulation sampling.

Assumption 1 [ass:iid-sampling] (Independent observed records).

The observed records $O_{1}, \dots, O_{n}$ are independent and identically distributed under the observed margin of $P$ .

⊢ Lean

Independent superpopulation sampling makes the observed margin the common law of every record and supplies the product-law experiment used in the risk criterion (van der Vaart, 1998). The identification conditions concern how that margin relates to potential outcomes. First, consistency connects each recorded outcome to the potential outcome under the received treatment.

Assumption 2 [ass:consistency] (Consistency of observed outcomes).

$Y = Y (A)$ almost surely.

⊢ Lean

Consistency is the standard link between observed and potential outcomes (Hernán et al., 2020). The observation map records this link atomwise.

Assumption 3 [ass:conditional-exchangeability] (Conditional exchangeability of treatment).

Under $P$ , $(Y (0), Y (1)) ⊥ A ∣ X$ .

⊢ Lean

Conditional exchangeability then relates treatment assignment to the two potential outcomes within each covariate cell.

Definition 1 [synth_1] (Observations from potential outcomes).

For $d \in N$ , let $P$ be a full-data causal law on $(X, A, Y (0), Y (1))$ , where $X$ ranges over a $d$ -element alphabet and $A, Y (0), Y (1) \in {0, 1}$ . The associated full observation is defined atomwise by $(X, A, Y (0), Y (1)) ⟼ (X, A, Y (A), Y (0), Y (1)), Y (A) = {Y (1), Y (0), A = 1, A = 0.$ The observed margin of $P$ is the law of $(X, A, Y (A))$ .

⊢ Lean

Conditional exchangeability permits arm-specific observed outcome means to identify the corresponding cell potential-outcome means (Rosenbaum et al., 1983). To state the remaining restriction precisely, we record cell masses and propensities.

Definition 2 [synth_2] (Observed covariate-cell mass).

For a discrete law $P$ on a covariate alphabet of size $d$ , the observed mass of cell $j$ is $p_{j} := P (X = j) .$

⊢ Lean

Definition 3 [synth_3] (Product law and propensity).

For a discrete observed-data law $P$ on a $d$ -cell covariate alphabet and a sample size $n$ , the product law is the joint law of $n$ independent records $O_{i} = (X_{i}, A_{i}, Y_{i})$ drawn from $P$ . For each occupied cell $j$ , write $p_{j} = P (X = j) > 0$ and define its treatment propensity by $e_{j} := P (A = 1 ∣ X = j)$ .

⊢ Lean

The cell mass $p_{j}$ determines whether a conditional quantity in cell $j$ is relevant to population value.

Assumption 4 [ass:overlap] (Fixed treatment overlap).

For every $j \in [d]$ with $p_{j} > 0$ , the treatment propensity satisfies $ϵ \leq e_{j} \leq 1 - ϵ .$

⊢ Lean

The known alphabet fixes the cells over which policies are optimized; cell probabilities may be arbitrarily small, so the law class includes rare cells and cells absent from a sample. Binary outcomes give the observed arm-and-outcome categories used by the factorial-moment estimator. For each occupied cell, the treatment propensity $e_{j}$ lies in the band set by the fixed overlap parameter $ϵ$ , where $0 < ϵ < 1/2$ . This condition supports identification of both cell means (Rosenbaum et al., 1983) and places no lower bound on a cell’s probability. The risk constants depend only on fixed overlap; the paired lower-bound family uses propensity $1/2$ in every occupied cell. Consistency is encoded by the observation map, which records the observed outcome as $Y (A)$ .

Definition 4 [def:model-class] (Causal law class

M_{d, ϵ}

$M_{d, ϵ}$ , for each integer $d \geq 2$ , is the class of laws $P$ satisfying:

(Covariate alphabet.) $X \in [d]$ .
(Binary variables.) $A, Y (0), Y (1) \in {0, 1}$ .

(Identification conditions.) Assumptions 2, 3, and 4.

⊢ Lean

The class $M_{d, ϵ}$ fixes the covariate alphabet, binary variables, and identification conditions for the minimax comparison. We next specify how a population treatment capacity restricts randomized policies.

Definition 5 [def:budget-policy-class] (Budget policy class

Π_{b} (P)

$Π_{b} (P) = {π \in [0, 1]^{d} : j = 1 \sum d p_{j} π_{j} \leq b} .$

⊢ Lean

A policy assigns each cell a treatment probability $π_{j}$ . At population capacity $b$ , its average treatment share is constrained by the cell masses; the resulting feasible class is $Π_{b} (P)$ . The value of assigning every cell to control supplies the baseline for evaluating these policies.

Definition 6 [synth_7] (Control-policy value).

For a full-data law $P$ , let $p_{j} = P (X = j)$ and let $μ_{0 j} = E_{P} [Y (0) ∣ X = j]$ on occupied cells, with $μ_{0 j} = 0$ on null cells. The population value of assigning every cell to control is $B (P) = j = 1 \sum d p_{j} μ_{0 j} .$

Population value depends on the arm-specific potential-outcome mean $μ_{aj}$ in each occupied cell and on the cell treatment effect $τ_{j}$ . The control-policy value $B (P)$ provides the baseline for evaluating feasible policies.

Definition 7 [synth_4] (Cell potential-outcome means).

For a full-data causal law $P$ on a $d$ -cell covariate alphabet, an arm $a \in {0, 1}$ , and a cell $j$ , let $p_{j} = P (X = j)$ . On occupied cells, where $p_{j} > 0$ , define $μ_{aj} = E_{P} [Y (a) ∣ X = j] .$ On null cells, where $p_{j} = 0$ , set $μ_{aj} = 0$ .

⊢ Lean

Definition 8 [synth_5] (Cell treatment effect).

For a full-data causal law $P$ on a $d$ -cell covariate alphabet and a cell $j$ , define the cell treatment effect by $τ_{j} := μ_{1 j} - μ_{0 j},$ where $μ_{aj}$ is the potential-outcome mean for arm $a$ in cell $j$ .

⊢ Lean

The zero convention gives $τ_{j} = 0$ on null cells and leaves every population value unchanged.

These cell quantities determine the maximum population value attainable at each budget.

Definition 9 [def:budget-value] (Budget value

V_{b} (P)

and curve

V (P)

The maximum population value at budget $b$ and the budget-indexed oracle-value curve on $I$ are $V_{b} (P) = B (P) + π \in Π_{b} (P) max j = 1 \sum d p_{j} π_{j} τ_{j}, V (P) = (V_{b} (P) : b \in I) .$

⊢ Lean

Fix an endpoint parameter $b_{0}$ $\in [0, 1/2]$ and write $I = [b_{0}, 1 - b_{0}]$ for the closed budget interval. Maximizing over feasible randomized policies gives the budget value $V_{b} (P)$ and its curve on $I$ .

To express this value through the observed margin, we use treatment-outcome masses within each cell and their arm totals.

Definition 10 [synth_9] (Arm and total masses of a four-vector).

For $u = (u_{a y} : (a, y) \in {0, 1}^{2}) \in R_{+}^{4}$ , define the mass in treatment arm $a$ and the total mass by $s_{a} (u) = u_{a 0} + u_{a 1}, s (u) = s_{0} (u) + s_{1} (u) = a, y \in {0, 1} \sum u_{a y} .$

For each cell, let the observed four-mass vector $q_{j}$ have coordinates $q_{a y, j} = P (X = j, A = a, Y = y)$ , for $a, y \in {0, 1}$ . Its entries encode the observed treatment-outcome distribution without conditioning on a possibly null cell. For a generic nonnegative four-vector $u$ , write $s_{a} (u)$ for its arm mass and $s (u)$ for its total mass.

The finite full-data support can equivalently be indexed by potential atoms.

Definition 11 [synth_6] (Potential atom space).

For a covariate alphabet of size $d \in N$ , a potential atom is an element of ${j \in N : j < d} \times {0, 1} \times {0, 1} \times {0, 1} .$

⊢ Lean

A shadow price $λ$ $\in [0, 1]$ converts the capacity constraint into a threshold comparison within each cell. The stabilized arm contribution $g_{a} (u)$ , threshold contribution $f_{λ} (u)$ , and aggregate process $F_{P} (λ)$ express that comparison in observed masses.

Definition 12 [def:dual-process] (Dual threshold process

F_{P} (λ)

For $u \in R_{+}^{4}$ , define the stabilized arm contributions, cell contribution, and dual threshold process by $g_{a} (u) = \frac{s ( u ) u _{a 1}}{max { s _{a} ( u ) , ϵs ( u )}}, f_{λ} (u) = g_{0} (u) + [g_{1} (u) - g_{0} (u) - λ s (u)]_{+}, F_{P} (λ) = j = 1 \sum d f_{λ} (q_{j}) .$ When all four cell masses vanish ( $u = 0$ ), the quotient defining $g_{a} (u)$ takes the value zero: $g_{a} (0) = 0$ .

⊢ Lean

Definition 13 [synth_12] (Binding half-budget capacity).

We say the half-budget constraint is binding for $P$ when there exists an optimal policy $π^{⋆} \in Π_{1/2} (P)$ such that $V_{1/2} (P) = B (P) + j = 1 \sum d p_{j} π_{j}^{⋆} τ_{j} and j = 1 \sum d p_{j} π_{j}^{⋆} = \frac{1}{2} .$

The zero convention in Definition 12 gives $f_{λ} (0) = 0$ and covers empty covariate cells.

Under Assumptions 3 and 4, the stabilized arm contribution at an occupied cell equals $p_{j} μ_{aj}$ . The threshold contribution therefore combines control value with the positive part of the cell treatment gain after charging the shadow price for treatment capacity. The following identity turns those cellwise contributions into the population budget value.

Proposition 1 [prop:dual-representation] (Dual representation of budget value).

Let $P$ be a full-data causal law with observed margin. Suppose:

Alphabet size. The known covariate alphabet has size $d \geq 2$ .
Overlap parameter. The fixed overlap parameter satisfies $0 < ϵ < 1/2$ .
Model membership. $P \in M_{d, ϵ}$ as defined in Definition 4.

For $0 \leq λ \leq 1$ , write $F_{P} (λ) = \sum_{j = 1}^{d} f_{λ} (q_{j})$ for the dual threshold process formed from the observed margin of $P$ . Then, for every $b \in [0, 1]$ , the budget value $V_{b} (P)$ of Definition 9 satisfies $V_{b} (P) = 0 \leq λ \leq 1 in f {bλ + F_{P} (λ)} .$ Moreover, for every process $F$ bounded on $[0, 1]$ , $b \in [0, 1] sup 0 \leq λ \leq 1 in f {bλ + F (λ)} - V_{b} (P) \leq λ \in [0, 1] sup F (λ) - F_{P} (λ) .$

⊢ Lean

The identity represents every budget value as the lower envelope of the same shadow-price process plus $bλ$ . Its second assertion transfers a uniform process error bound to a uniform curve error bound with factor one, so a single estimated process serves the entire budget interval. The identity and contraction concern the optimized value and permit multiple maximizing policies or minimizing shadow prices.

The observed sample collects the records on which a curve estimator may depend.

Definition 14 [synth_11] (Finite observed sample).

For $n, d \in N$ , the observed sample $O^{(n)} = (O_{i})_{i = 1}^{n}$ consists of $n$ observed records $O_{i} = (X_{i}, A_{i}, Y_{i})$ , each with $X_{i}$ in the $d$ -element covariate alphabet.

⊢ Lean

We assess curve estimation by the all-procedure expected squared supremum risk $R_{n, d, ϵ, b_{0}}^{curve}$ . The criterion compares bounded-function-valued estimators over the causal law class and the closed interval $I$ .

Definition 15 [def:curve-risk] (Curve risk

R_{n, d, ϵ, b_{0}}^{curve}

For $b_{0} \in [0, 1/2]$ , set $I = [b_{0}, 1 - b_{0}]$ . The all-procedure expected squared supremum risk is $R_{n, d, ϵ, b_{0}}^{curve} = V in f P \in M_{d, ϵ} sup E_{P} [b \in I sup V_{b} (O^{(n)}) - V_{b} (P)^{2}],$ where the infimum ranges over all measurable maps from the observed sample into bounded functions on $I$ .

⊢ Lean

Both endpoints belong to $I$ . In particular, $b_{0} = 0$ gives the full interval $[0, 1]$ , while $b_{0} = 1/2$ gives the single budget $1/2$ .

Minimax risk for the budget-value curve

The shadow-price representation in Proposition 1 reduces estimation of the budget-value curve to estimation of one process. The resulting minimax risk is matched for every interval $I = [b_{0}, 1 - b_{0}]$ , including the full budget range and the single half-budget value.

Theorem 1 [thm:matched-curve-frontier] (Matched curve minimax frontier).

Fix an overlap parameter $ϵ \in (0, 1/2)$ . There exist constants $0 < c_{ϵ} \leq C_{ϵ} < \infty$ such that, for every $n \geq 1$ , $d \geq 2$ , and $b_{0} \in [0, 1/2]$ , the curve minimax risk of Definition 15 satisfies $c_{ϵ} min {1, \frac{d}{n lo g ( e d )}} \leq R_{n, d, ϵ, b_{0}}^{curve} \leq C_{ϵ} min {1, \frac{d}{n lo g ( e d )}} .$ For every measurable scalar estimator $V_{1/2}$ based on the $n$ observed records, there is a full-data law $P$ with the following properties:

(Causal model.) $P \in M_{d, ϵ}$ , and each occupied cell has $p_{j} > 0$ , $τ_{j} \in [1/8, 3/8]$ , and $τ_{j} > 0$ .

(Values and binding capacity.) $V_{1} (P) = 1/2$ , and there is a policy $π \in [0, 1]^{d}$ such that $j = 1 \sum d p_{j} π_{j} = \frac{1}{2}, V_{1/2} (P) = B (P) + j = 1 \sum d p_{j} π_{j} τ_{j} .$

(Scalar risk.) Under $n$ independent observations from the observed margin of $P$ , $E_{P} [(V_{1/2} - V_{1/2} (P))^{2}] \geq c_{ϵ} min {1, \frac{d}{n lo g ( e d )}} .$

When $b_{0} = 0$ , every $P \in M_{d, ϵ}$ also satisfies the full-budget identity $V_{1} (P) = B (P) + j = 1 \sum d p_{j} max {τ_{j}, 0},$ where $V_{b} (P)$ is the budget value of Definition 9.

⊢ Lean

The upper bound applies to all budgets in the chosen interval simultaneously. In the paired family, the half-budget coordinate attains the stated risk order with positive occupied-cell effects, binding capacity, and a full-capacity value fixed at $1/2$ . This family makes the allocation problem visible through the ranking of cell benefits. Simultaneous curve estimation therefore attains the unrestricted full-capacity scalar minimax order under the stated conditions. The reduction uses the bound for estimating the $ℓ_{1}$ distance between two unknown discrete distributions from Jiao et al. (2018).

The proof has three steps. First, the shadow-price identity reduces all budget values to one threshold process, and taking a minimum is a contraction in supremum norm. Second, the estimator below controls that process cell by cell: empirical masses suffice for a small alphabet, while pilot localization and factorial moments handle a growing alphabet. Third, the paired family converts the half-budget value into a discrete two-sample $L_{1}$ functional, giving the matching lower bound. The appendix contains the polynomial and process estimates behind the second step.

The exact estimator and its uniform upper-bound theorem are stated in the technical appendix, Algorithm 1 and Theorem 3. Its statistical construction is summarized here.

The estimator first estimates one threshold process across shadow prices, then takes a shadow-price minimum to obtain each budget value. For a small alphabet it inserts empirical cell masses into that process; with a larger alphabet and adequate sample size, pilot counts localize each mass and evaluation counts estimate a local Jackson polynomial by factorial moments. Clipping controls the cell estimates before they are summed, and the sparse-sample branch reports a constant curve. The displayed construction uses an exact conditional average over auxiliary permutations and markings. Its polynomial degree and pilot-width constants serve the risk proof: at ordinary alphabet sizes the degree remains two and the pilot intervals are broad. The rate is a theoretical benchmark for this exact estimator.

In the Jackson–factorial branch, write $L = lo g (e d)$ . Pilot counts set cell-specific localization widths; on each resulting rectangle, the Jackson approximation error is bounded by radius-dependent terms divided by the polynomial order $K$ and $K^{2}$ Lemma 3. Independent evaluation counts turn the polynomial terms into factorial-moment estimates. The resulting cell bias is bounded by $C_{ϵ} {p_{j} / (n L) + 1/ (n L)}$ uniformly over shadow prices, while the centered good-pilot process has expected squared supremum error of order $d / (n L)$ ; the bad-pilot envelope has an exponentially small factor in $L$ Theorem 4. Summing the bias over cells and combining it with these fluctuation bounds yields the same process-risk order. The empirical branch covers small alphabets, and the constant branch covers the sparse-sample regime.

Conditional averaging makes the exact curve-valued estimator a function of the observed sample. By Proposition 1, the error in each budget value is bounded by the uniform error of the estimated threshold process. The same process estimate therefore controls the supremum over $I$ .

The bound measures the squared largest error across the interval before taking expectation, so it also applies when a budget is selected after viewing the estimated curve. The process bound behind it is given in the appendix; the dual identity transfers that bound to budget values without an additional cost for considering several budgets.

The matching converse can be stated directly for estimation at half capacity. It retains positive effects throughout the occupied cells and fixes the value under full provision.

Theorem 2 [thm:capacity-active-lower] (Capacity-active risk lower bound).

Fix an overlap parameter $0 < ϵ < 1/2$ . There exists $c_{ϵ} > 0$ such that, for every $n \geq 1$ , $d \geq 2$ , every collection of observed-data laws satisfying Assumption 1 for each full-data law, and every measurable scalar estimator $T$ based on the $n$ observed records, there is a full-data law $P$ satisfying:

(Model class.) $P \in M_{d, ϵ}$ .

(Full-budget value.) $V_{1} (P) = 1/2$ , with $V_{b} (P)$ as in Definition 9.

(Effects in occupied cells.) For every cell $j$ , $p_{j} > 0$ implies $1/8 \leq τ_{j} \leq 3/8$ .

(Binding capacity.) The half-budget constraint is binding for $P$ .

For this law, $E_{P} [(T - V_{1/2} (P))^{2}] \geq c_{ϵ} min {1, \frac{d}{n lo g ( e d )}} .$

⊢ Lean

Positive treatment effects make the half-budget allocation use its available capacity, while differences across cells determine which recipients are most valuable. The theorem establishes the lower risk benchmark in this capacity-active setting even with the full-budget value fixed. Its reduction again invokes the discrete $ℓ_{1}$ bound of Jiao et al. (2018).

Two special cases put the general rate and the budget curve in familiar terms: a fixed covariate alphabet and a common positive effect across occupied cells.

Proposition 2 [prop:fixed-alphabet-reduction] (Fixed alphabet rate and identity).

Fix the overlap parameter $ϵ$ and the known covariate alphabet size $d$ under the following conditions:

(Overlap.) $0 < ϵ < 1/2$ .

(Alphabet.) $d \geq 2$ .

For the curve minimax risk in Definition 15, there are constants $c, C$ with $0 < c \leq C$ such that, for every $n \geq 1$ and every $b_{0} \in [0, 1/2]$ , $\frac{c}{n} \leq R_{n, d, ϵ, b_{0}}^{curve} \leq \frac{C}{n} .$

Moreover, let $P$ belong to the causal model class $M_{d, ϵ}$ in Definition 4. Write $p_{j}$ for the mass of cell $j$ , $μ_{aj}$ for its arm- $a$ potential-outcome mean, and $τ_{j} = μ_{1 j} - μ_{0 j}$ for its treatment effect. If some $c > 0$ satisfies $τ_{j} = c$ in every cell with $p_{j} > 0$ , then, for every $b_{0} \in [0, 1/2]$ and every $b \in [b_{0}, 1 - b_{0}]$ , the budget value in Definition 9 satisfies $V_{b} (P) = B (P) + c b, B (P) = j = 1 \sum d p_{j} μ_{0 j} .$

⊢ Lean

With the alphabet and overlap parameter fixed, the matched rate is $1/ n$ . Under a common positive effect, every unit of treatment capacity adds the same population value, giving a linear budget-value curve. In the common-effect clause of Proposition 2, the symbol $c$ denotes an arbitrary positive treatment effect; it is independent of the lower comparison constant also written $c$ in the risk bound.

Discussion and limitations

The risk in Definition 15 measures expected squared supremum error over the budget interval $I$ . Thus, Theorem 3 gives a simultaneous guarantee for one estimated value curve. When $b_{0} = 0$ , that guarantee covers every budget from zero to full population capacity. Together with Theorem 2, the upper bound identifies the minimax rate under the stated conditions.

When $d / [n lo g (e d)]$ is small, the minimax risk has that order; when the ratio is large, it has constant order. The minimax rate contains a logarithmic factor, and the upper bound uses polynomial estimation of the discrete threshold process. In the paired family, differences among positive cell benefits determine their ranking and hence the half-budget allocation value, even as the full-budget value stays fixed. Under Theorem 2, this single coordinate attains the curve’s risk order. The factor-one dual contraction carries the process estimate to all budgets, and the whole curve attains the unrestricted full-capacity scalar minimax order.

Limitations and future work

The global supremum criterion covers the endpoint when $b_{0} = 0$ ; a budget-local analysis could characterize risk as the budget shrinks with sample size. Adaptive simultaneous bands call for a coverage criterion, while policy regret calls for evaluating an estimated allocation. The theorem’s estimator is the exact conditional average in Algorithm 1; approximating that average by Monte Carlo draws would require a separate draw-count and approximation-error guarantee before claiming the same rate. Other directions include covariate alphabets learned from data and allocation across multiple treatment arms.

Appendices

Proofs and verification scope

Estimator and uniform upper bound

The observed category-cell masses specify the inputs to the exact Jackson–factorial construction.

Definition 16 [synth_8] (Observed category-cell masses).

For a covariate cell $j$ and a treatment-outcome category $ζ = (a, y) \in {0, 1}^{2}$ , define $q_{ζ j} = P (X = j, A = a, Y = y) .$ These four masses are the components of the observed cell vector $q_{j} = (q_{ζ j} : ζ \in {0, 1}^{2})$ .

Algorithm 1 [def:jf-estimator] (Jackson–factorial estimator

V_{b}^{JF}

Given $O^{(n)}$ , $d$ , and $I$ , the estimator $V_{b}^{JF}$ uses the tuning quantities $H_{0}, κ, D_{0}, L, m, K$ defined below.

Set $H_{0} = 4096, κ = \frac{1}{512}, D_{0} = 16, L = lo g (e d), m = \frac{n}{8}, K = max {2, ⌊ \frac{L}{512} ⌋}, Z = {0, 1}^{2} .$ Index treatment-outcome categories by $ζ = (a, y) \in Z$ .
If $d < D_{0}$ , form the empirical category-cell masses and threshold process: $q_{ζ j} = \frac{1}{n} i = 1 \sum n 1 {X_{i} = j, (A_{i}, Y_{i}) = ζ}, q_{j} = (q_{ζ j})_{ζ \in Z}, F (λ) = j = 1 \sum d f_{λ} (q_{j}) .$ Proceed to the final step.

If $d \geq D_{0}$ and $n < d / L$ , output $V_{b}^{JF} = \frac{1}{2}, b \in I .$ In the remaining branch, $d \geq D_{0}$ and $n \geq d / L$ , draw $M \sim Pois (n /4)$ independently of $O^{(n)}$ . On ${M > n}$ , set $F^{cap} (λ) = 0, λ \in [0, 1] .$ On ${M \leq n}$ , uniformly permute the records, retain the first $M$ , and independently mark each retained record pilot or evaluation with probability $1/2$ each. Define the pilot and evaluation counts by $N_{ζ j}^{'} = i = 1 \sum M 1 {X_{i}^{*} = j, (A_{i}^{*}, Y_{i}^{*}) = ζ, i is marked pilot}, N_{ζ j} = i = 1 \sum M 1 {X_{i}^{*} = j, (A_{i}^{*}, Y_{i}^{*}) = ζ, i is marked evaluation},$ where $O_{i}^{*} = (X_{i}^{*}, A_{i}^{*}, Y_{i}^{*})$ denotes the $i$ th record in the uniform permutation.
On ${M \leq n}$ , for every $j$ and $ζ$ , set $δ = \frac{L}{m}, c_{ζ j} = \frac{N _{ζ j}^{'}}{m}, h_{ζ j} = H_{0} {c_{ζ j} δ + δ},$ $ℓ_{ζ j} = max {0, c_{ζ j} - h_{ζ j}}, u_{ζ j} = c_{ζ j} + h_{ζ j}, c_{ζ j}^{0} = \frac{ℓ _{ζ j} + u _{ζ j}}{2}, R_{ζ j} = \frac{u _{ζ j} - ℓ _{ζ j}}{2}, S_{j} = ζ \in Z \sum R_{ζ j} .$ All radii $R_{ζ j}$ are strictly positive. Let $c_{j}^{0} = (c_{ζ j}^{0})_{ζ \in Z}$ and $R_{j} = (R_{ζ j})_{ζ \in Z}$ . Define the normalized positive order-four Jackson kernel by $J_{K} (t) = C_{K} {\frac{sin ( K t /2 )}{sin ( t /2 )}}^{4}, - π \leq t \leq π, \int_{- π}^{π} J_{K} (t) d t = 1,$ where the quotient takes its continuous value at zero and $C_{K} > 0$ is the unique normalizing constant. Set $D = 2 (K - 1)$ . For each $j$ and $λ$ , define the unique tensor polynomial $P_{j, λ}$ , of coordinatewise degree at most $D$ , through $P_{j, λ} (c_{j}^{0} + R_{j} ⊙ cos ϑ) = \int_{[- π, π]^{4}} f_{λ} (c_{j}^{0} + R_{j} ⊙ cos (ϑ + t)) ζ \in Z \prod J_{K} (t_{ζ}) d t,$ and define its coefficients $β_{j, α} (λ)$ by the unique expansion $P_{j, λ} (u) - f_{λ} (c_{j}^{0}) = α \in {0, \dots, D}^{4} \sum β_{j, α} (λ) ζ \in Z \prod (\frac{u _{ζ} - c _{ζ j}^{0}}{R _{ζ j}})^{α_{ζ}} .$ For integers $h \geq 0$ , define $U_{h} (N; z) = t = 0 \sum h (t h) (- z)^{h - t} \frac{( N ) _{t}}{m ^{t}}, (N)_{t} = N (N - 1) \dots (N - t + 1), (N)_{0} = 1.$ The cell estimate, its clipped version, and the auxiliary threshold process are $Z_{j} (λ) = f_{λ} (c_{j}^{0}) + α \in {0, \dots, D}^{4} \sum β_{j, α} (λ) ζ \in Z \prod \frac{U _{α_{ζ}} ( N _{ζ j} ; c _{ζ j}^{0} )}{R _{ζ j}^{α_{ζ}}},$ $T_{j} (λ) = f_{λ} (c_{j}^{0}) + Π_{[- d^{1/4} S_{j}, d^{1/4} S_{j}]} (Z_{j} (λ) - f_{λ} (c_{j}^{0})), F^{cap} (λ) = j = 1 \sum d T_{j} (λ) .$ Here $Π_{[r, s]} (x) = min {s, max {r, x}} .$ In this branch, average the auxiliary process conditional on the observed sample: $F (λ) = E {F^{cap} (λ) ∣ O^{(n)}} .$

In the empirical and Jackson–factorial branches, report $V_{b}^{JF} = Π_{[0, 1]} (0 \leq λ \leq 1 min {bλ + F (λ)}), b \in I .$ The output uses the minimum value and requires no optimizer selection. If an implementation stores an optimizer, it stores the least element of the nonempty compact argmin set. These branch rules, the zero process on ${M > n}$ , and the least-minimizer convention apply under every data or treatment-effect tie.

⊢ Lean

The conditional average in Algorithm 1 is an observed-sample statistic. The dual contraction transfers a uniform process bound to every budget in $I$ .

Theorem 3 [thm:curve-upper] (Uniform budget-curve upper bound).

Fix the overlap parameter $ϵ$ . Suppose:

(Overlap.) $0 < ϵ < 1/2$ .

(Sample and alphabet.) $n \geq 1$ and $d \geq 2$ .

(Budget interval.) $b_{0} \in [0, 1/2]$ , and $I = [b_{0}, 1 - b_{0}]$ .

(Sampling.) For each causal law $P \in M_{d, ϵ}$ , the $n$ observed records follow Assumption 1 for the observed margin of $P$ .

There is a constant $C_{ϵ} > 0$ , depending only on $ϵ$ , such that the estimator in Algorithm 1 and the budget value in Definition 9 satisfy $P \in M_{d, ϵ} sup E_{P} [b \in I sup V_{b}^{JF} - V_{b} (P)^{2}] \leq C_{ϵ} min {1, \frac{d}{n lo g ( e d )}} .$

⊢ Lean

The estimator controls the threshold process over the full interval of shadow prices before taking the dual minimum. Since the minimum value is Lipschitz in the supremum norm of that process, one process bound controls every budget in $I$ , including zero and full capacity when $b_{0} = 0$ .

Process estimates

The upper-bound analysis begins with regularity of the cell contribution in the dual representation of Definition 12. Bounded variation controls its dependence on the full interval of shadow prices.

Lemma 1 [lem:bv-lipschitz] (Bounded variation Lipschitz bound).

For $0 < ϵ < 1/2$ , there is a finite constant $C_{ϵ} \geq 0$ such that, for every $u, v \in R_{+}^{4}$ , $∥ f_{\cdot} (u) - f_{\cdot} (v) ∥_{B V ([0, 1])} \leq C_{ϵ} ∥ u - v ∥_{1},$ where $∥ h ∥_{B V ([0, 1])} = ∣ h (0) ∣ + TV_{[0, 1]} (h)$ .

⊢ Lean

Proof of Lemma 1.

Fix $u, v \in R_{+}^{4}$ , and write $s_{η} (u) = ω = 0 \sum 1 u_{η ω}, s (u) = η = 0 \sum 1 s_{η} (u), Δ_{uv} = η, ω = 0 \sum 1 ∣ u_{η ω} - v_{η ω} ∣.$ In particular, $∣ s (u) - s (v) ∣ \leq Δ_{uv}$ . For either arm $η$ , the stabilized contribution in Definition 12 satisfies $0 \leq g_{η} (u) \leq s (u), ∣ g_{η} (u) - g_{η} (v) ∣ \leq (1 + ϵ^{- 1}) Δ_{uv} .$ Here is a derivation of the second bound, including zero masses. Put $m_{u} = s_{η} (u)$ and $z_{u} = u_{η 1}$ , and define $m_{v}, z_{v}$ analogously. When $s (u) > 0$ , the two branches are $g_{η} (u) = {z_{u} / ϵ, s (u) z_{u} / m_{u}, m_{u} \leq ϵs (u), m_{u} \geq ϵs (u) .$ They agree at equality; when $s (u) = 0$ , $g_{η} (u) = 0$ . If both vectors use the first branch, their difference is at most $ϵ^{- 1} ∣ z_{u} - z_{v} ∣$ . If both use the second, $m_{u}, m_{v} > 0$ , and $\frac{z _{u}}{m _{u}} - \frac{z _{v}}{m _{v}} \leq \frac{∣ z _{u} - z _{v} ∣ + ∣ ( m _{u} - z _{u} ) - ( m _{v} - z _{v} ) ∣}{m _{u}} .$ Since $z_{v} / m_{v} \leq 1$ and $s (u) / m_{u} \leq ϵ^{- 1}$ , splitting the difference of the two products bounds it by $∣ s (u) - s (v) ∣ + ϵ^{- 1} Δ_{uv}$ .

For the mixed case $m_{u} \leq ϵs (u)$ and $m_{v} \geq ϵs (v)$ , the identity $\frac{z _{u}}{ϵ} - s (v) \frac{z _{v}}{m _{v}} = \frac{z _{u} - z _{v}}{ϵ} + \frac{z _{v}}{m _{v}} \frac{m _{v} - ϵs ( v )}{ϵ}$ and the bounds $0 \leq m_{v} - ϵs (v) \leq (m_{v} - m_{u}) - ϵ (s (v) - s (u)), 0 \leq \frac{z _{v}}{m _{v}} \leq 1$ give the upper bound below. The rearrangement $(z_{u} - z_{v}) + \frac{z _{v}}{m _{v}} (m_{v} - m_{u}) = (1 - \frac{z _{v}}{m _{v}}) (z_{u} - z_{v}) + \frac{z _{v}}{m _{v}} ((m_{v} - z_{v}) - (m_{u} - z_{u}))$ shows that its left-hand side has absolute value at most $Δ_{uv}$ , since $0 \leq z_{v} / m_{v} \leq 1$ . Consequently, $\frac{z _{u}}{ϵ} - s (v) \frac{z _{v}}{m _{v}} \leq \frac{( z _{u} - z _{v} ) + ( z _{v} / m _{v} ) ( m _{v} - m _{u} )}{ϵ} - \frac{z _{v}}{m _{v}} (s (v) - s (u)) \leq (1 + ϵ^{- 1}) Δ_{uv} .$ For the lower bound, return to the first mixed-case identity: its correction term $(z_{v} / m_{v}) (m_{v} - ϵs (v)) / ϵ$ is nonnegative. Hence the difference is at least $(z_{u} - z_{v}) / ϵ \geq - ϵ^{- 1} Δ_{uv}$ . Interchanging $u, v$ handles the other mixed case. Finally, if either total mass is zero, all its coordinates and its arm contribution vanish; $0 \leq g_{η} \leq s$ and $∣ s (u) - s (v) ∣ \leq Δ_{uv}$ give $∣ g_{η} (u) - g_{η} (v) ∣ \leq (1 + ϵ^{- 1}) Δ_{uv}$ directly. The same inequalities also establish $0 \leq g_{η} (u) \leq s (u)$ in every branch.

Define the positive gain and its hinge by $γ_{u} = [g_{1} (u) - g_{0} (u)]_{+}, Φ_{u} (λ) = [γ_{u} - λ s (u)]_{+},$ and similarly for $v$ . The arm bounds give $0 \leq γ_{u} \leq s (u)$ and $0 \leq γ_{v} \leq s (v)$ . Because $λ s (u) \geq 0$ on $[0, 1]$ , $f_{λ} (u) = g_{0} (u) + Φ_{u} (λ) .$ Taking positive parts and using the arm contribution bound yields $∣ γ_{u} - γ_{v} ∣ \leq ∣ g_{1} (u) - g_{1} (v) ∣ + ∣ g_{0} (u) - g_{0} (v) ∣ \leq 2 (1 + ϵ^{- 1}) Δ_{uv} .$

Set $ρ_{u} = {γ_{u} / s (u), 0, s (u) > 0, s (u) = 0, ρ_{v} = {γ_{v} / s (v), 0, s (v) > 0, s (v) = 0, Ψ_{uv} (λ) = Φ_{u} (λ) - Φ_{v} (λ) .$ Both breakpoints lie in $[0, 1]$ , including when a total mass vanishes. The positive-part inequality gives, throughout that interval, $∣ Ψ_{uv} (λ) ∣ \leq ∣ γ_{u} - γ_{v} ∣ + ∣ s (u) - s (v) ∣ =: Ξ_{uv} .$ If $ρ_{u} \leq ρ_{v}$ , the three successive affine expressions for $Ψ_{uv}$ are $γ_{u} - γ_{v} + λ (s (v) - s (u)), - γ_{v} + λ s (v), 0$ on $[0, ρ_{u}]$ , $[ρ_{u}, ρ_{v}]$ , and $[ρ_{v}, 1]$ , respectively. If $ρ_{v} \leq ρ_{u}$ , they are $γ_{u} - γ_{v} + λ (s (v) - s (u)), γ_{u} - λ s (u), 0$ on $[0, ρ_{v}]$ , $[ρ_{v}, ρ_{u}]$ , and $[ρ_{u}, 1]$ . The formulas agree at their shared endpoints, also for coincident breakpoints. Variation on each affine piece equals the absolute difference of its endpoint values, which is at most $2 Ξ_{uv}$ by the preceding pointwise bound. Adding the three pieces gives $TV_{[0, 1]} (Ψ_{uv}) \leq 6 (∣ γ_{u} - γ_{v} ∣ + ∣ s (u) - s (v) ∣) .$

The constant $g_{0} (u) - g_{0} (v)$ in $f_{λ} (u) - f_{λ} (v) = g_{0} (u) - g_{0} (v) + Ψ_{uv} (λ)$ leaves variation unchanged. At $λ = 0$ , the positive-part inequality and the arm contribution bound give $∣ f_{0} (u) - f_{0} (v) ∣ \leq 2∣ g_{0} (u) - g_{0} (v) ∣ + ∣ g_{1} (u) - g_{1} (v) ∣ \leq (3 (1 + ϵ^{- 1}) + 1) Δ_{uv} .$ Thus the positive-gain and variation bounds, together with $∣ s (u) - s (v) ∣ \leq Δ_{uv}$ , imply $∥ f_{\cdot} (u) - f_{\cdot} (v) ∥_{B V ([0, 1])} \leq (15 (1 + ϵ^{- 1}) + 7) Δ_{uv} .$ The displayed finite, nonnegative coefficient supplies $C_{ϵ}$ .

∎

The bound in Lemma 1 supplies a common regularity measure across shadow prices. The process criterion below collects the corresponding approximation, bias, and fluctuation bounds for the estimator in Algorithm 1.

Definition 17 [def:process-handle] (Uniform process handle

H_{ϵ}

For fixed $0 < ϵ < 1/2$ , the uniform process handle $H_{ϵ}$ is the set of constants $C > 0$ satisfying the five groups of bounds below for the single pilot-local Jackson polynomial and clipping rule of $V^{JF}$ . Membership requires the bounds simultaneously for every $n, d$ in the Jackson–factorial branch, every observed categorical law $P$ on the known $d$ -cell alphabet, every pilot realization, every cell $j$ , and every $λ \in [0, 1]$ .

Set $L = lo g (e d), m = \frac{n}{8}, K = max {2, ⌊ \frac{L}{512} ⌋}, S_{j} = ζ \in Z \sum R_{ζ j}, v_{j} = \frac{p _{j} L}{m} + \frac{L}{m} .$ For the expectations and $L_{2}$ norms below, use the uncapped marked-Poisson experiment in which all pilot and evaluation counts $N_{ζ j}^{'}$ and $N_{ζ j}$ are mutually independent with distribution $Pois (m q_{ζ j})$ . Define $G_{j} = ζ \in Z ⋂ {∣ c_{ζ j} - q_{ζ j} ∣ \leq \frac{h _{ζ j}}{4}}, ∥ h ∥_{B V ([0, 1])} = ∣ h (0) ∣ + TV_{[0, 1]} (h) .$ Evaluate $T_{j}$ , $β_{j, α}$ , and $R_{ζ j}$ in this experiment. The membership bounds are:

Coefficient envelope and exponential bound. $α \sum ∥ β_{j, α} ∥_{B V ([0, 1])} \leq C S_{j} e^{12 K}, S_{j}^{2} e^{24 K + 16 K^{2} / L} \leq C d^{1/16} S_{j}^{2} .$

Centered process on the pilot event. $E j = 1 \sum d [1_{G_{j}} {T_{j} - f_{\cdot} (q_{j})} - E 1_{G_{j}} {T_{j} - f_{\cdot} (q_{j})}]_{\infty}^{2} \leq C \frac{d}{m L} .$

Cellwise bias. $0 \leq λ \leq 1 sup ∣ E T_{j} (λ) - f_{λ} (q_{j}) ∣ \leq C {\frac{p _{j}}{m L} + \frac{1}{m L}} .$

Cellwise envelope outside the pilot event. $1_{G_{j}^{c}} 0 \leq λ \leq 1 sup ∣ T_{j} (λ) - f_{λ} (q_{j}) ∣_{L_{2}} \leq C d^{1/4} e^{- 10 L} v_{j} .$

Centered process outside the pilot event. $E j = 1 \sum d [1_{G_{j}^{c}} {T_{j} - f_{\cdot} (q_{j})} - E 1_{G_{j}^{c}} {T_{j} - f_{\cdot} (q_{j})}]_{\infty}^{2} \leq C \frac{d}{m L} .$

⊢ Lean

The criterion in Definition 17 treats pilot localization and its complement within the same process bound. A second-moment bound for the pilot radii supplies an integrability input for that criterion.

Lemma 2 [lem:pilot-radius-second-moment] (Second moment of pilot radii).

Let $n \geq 1$ , $d \geq 16$ , and $m = n /8$ . Let $P$ be a categorical law on the $d$ -cell alphabet, with category-cell masses $q_{ζ j}$ and cell masses $p_{j} = \sum_{ζ \in Z} q_{ζ j}$ , and fix a cell $j$ . In the ideal Poisson experiment, the pilot counts $N_{ζ j}^{'}$ are independent with means $m q_{ζ j}$ . Let $S_{j} = \sum_{ζ \in Z} R_{ζ j}$ be the sum of the four pilot radii in Algorithm 1, and set $L = lo g (e d), H_{0} = 4096, v_{j} = \frac{p _{j} L}{m} + \frac{L}{m} .$ Then $S_{j}^{2}$ is integrable under the ideal Poisson law, and $E [S_{j}^{2}] \leq 32 H_{0}^{2} v_{j}^{2} .$

⊢ Lean

Proof of Lemma 2.

Since $n \geq 1$ and $d \geq 16$ , we have $m > 0$ and $L > 0$ . For each $ζ \in Z$ , the localization intervals in Algorithm 1 give $c_{ζ j} = \frac{N _{ζ j}^{'}}{m}, h_{ζ j} = H_{0} \frac{N _{ζ j}^{'} L}{m ^{2}} + \frac{L}{m}, R_{ζ j} = \frac{c _{ζ j} + h _{ζ j} - max { 0 , c _{ζ j} - h _{ζ j} }}{2} .$ Both $c_{ζ j}$ and $h_{ζ j}$ are nonnegative. The maximum in the last expression lies between $c_{ζ j} - h_{ζ j}$ and $c_{ζ j} + h_{ζ j}$ ; hence $0 \leq R_{ζ j} \leq h_{ζ j}$ . Applying $(x + y)^{2} \leq 2 (x^{2} + y^{2})$ yields $R_{ζ j}^{2} \leq 2 H_{0}^{2} {\frac{N _{ζ j}^{'} L}{m ^{2}} + (\frac{L}{m})^{2}} .$

There are four categories in $Z$ . Cauchy–Schwarz and the coordinate bound therefore give, pointwise, $S_{j}^{2} = ζ \in Z \sum R_{ζ j}^{2} \leq 4 ζ \in Z \sum R_{ζ j}^{2} \leq 8 H_{0}^{2} ⎩ ⎨ ⎧ \frac{L}{m ^{2}} ζ \in Z \sum N_{ζ j}^{'} + 4 (\frac{L}{m})^{2} ⎭ ⎬ ⎫ .$

Each pilot count is integrable under its Poisson law, with $E ζ \in Z \sum N_{ζ j}^{'} = ζ \in Z \sum m q_{ζ j} = m p_{j} .$ The pointwise bound thus proves integrability of $S_{j}^{2}$ and gives $E [S_{j}^{2}] \leq 8 H_{0}^{2} {\frac{p _{j} L}{m} + 4 (\frac{L}{m})^{2}} .$ Finally, $p_{j} L / m \geq 0$ and $L / m \geq 0$ , so $\frac{p _{j} L}{m} + 4 (\frac{L}{m})^{2} \leq 4 (\frac{p _{j} L}{m} + \frac{L}{m})^{2} = 4 v_{j}^{2} .$ Combining the two inequalities proves $E [S_{j}^{2}] \leq 32 H_{0}^{2} v_{j}^{2}$ .

∎

The bound in Lemma 2 controls the random localization scale by cell mass and the logarithmic alphabet factor. On a localization rectangle, the Jackson approximation has the following coordinatewise bound, including at its boundary.

Lemma 3 [lem:jackson-boundary-adaptive] (Boundary-adaptive Jackson approximation).

Let $P_{λ}$ be the local polynomial for $f_{λ}$ of Definition 12, formed by the normalized order-four Jackson construction in Algorithm 1 with pilot center and radii replaced by $c^{0}$ and $R$ , and with the value $f_{λ} (c^{0})$ added to the normalized polynomial evaluation. Suppose that:

(Parameters.) The overlap parameter satisfies $ϵ > 0$ , the shadow price satisfies $λ \in [0, 1]$ , and $K$ is a positive integer.

(Rectangle.) For every $ζ \in Z$ , $R_{ζ} > 0$ and $c_{ζ}^{0} - R_{ζ} \geq 0$ .

(Evaluation point.) For every $ζ \in Z$ , $∣ y_{ζ} - c_{ζ}^{0} ∣ \leq R_{ζ}$ .

Then $P_{λ} (y) - f_{λ} (y) \leq 32 {3 (1 + ϵ^{- 1}) + 1} ζ \in Z \sum ⎩ ⎨ ⎧ \frac{( y _{ζ} - c _{ζ}^{0} + R _{ζ} ) ( c _{ζ}^{0} + R _{ζ} - y _{ζ} )}{K} + \frac{R _{ζ}}{K ^{2}} ⎭ ⎬ ⎫ .$

⊢ Lean

Proof of Lemma 3.

Set $R = ζ \in Z \prod [c_{ζ}^{0} - R_{ζ}, c_{ζ}^{0} + R_{ζ}], Δ (w, w^{'}) = ζ \in Z \sum ∣ w_{ζ} - w_{ζ}^{'} ∣, Λ_{ϵ} = 3 (1 + ϵ^{- 1}) + 1$ for $w, w^{'} \in R$ . The rectangle assumption makes both vectors nonnegative. We first establish $∣ f_{λ} (w) - f_{λ} (w^{'}) ∣ \leq Λ_{ϵ} Δ (w, w^{'}) .$

For each arm $a \in {0, 1}$ , the contribution in Definition 12 satisfies $∣ g_{a} (w) - g_{a} (w^{'}) ∣ \leq (1 + ϵ^{- 1}) Δ (w, w^{'}) .$ Here is the scalar estimate behind this bound. At zero total mass, every coordinate vanishes. We evaluate the quotient defining $g_{a}$ in Definition 12 with the convention $0/0 = 0$ , so $g_{a} (0) = 0$ . Since $0 \leq g_{a} (w) \leq s (w)$ , and likewise for $w^{'}$ , the claim follows whenever either vector has zero total mass. For positive total masses, the defining maximum gives $g_{a} (w) = w_{a 1} / ϵ$ when $s_{a} (w) \leq ϵs (w)$ , and $g_{a} (w) = s (w) w_{a 1} / s_{a} (w)$ in the other regime. When both vectors are in the first regime, their difference is bounded by $ϵ^{- 1} Δ (w, w^{'})$ . When both are in the second, $0 \leq w_{a 1}^{'} / s_{a} (w^{'}) \leq 1$ and $\frac{w _{a 1}}{s _{a} ( w )} - \frac{w _{a 1}^{'}}{s _{a} ( w ^{'} )} \leq \frac{∣ w _{a 1} - w _{a 1}^{'} ∣ + ∣ w _{a 0} - w _{a 0}^{'} ∣}{s _{a} ( w )} .$ Expanding the difference of the two products, using $∣ s (w) - s (w^{'}) ∣ \leq Δ (w, w^{'})$ and $s (w) / s_{a} (w) \leq ϵ^{- 1}$ , proves the displayed arm bound.

For the mixed regime in which $w$ is in the first regime and $w^{'}$ in the second, the difference equals $\frac{w _{a 1} - w _{a 1}^{'}}{ϵ} + \frac{w _{a 1}^{'}}{s _{a} ( w ^{'} )} \frac{s _{a} ( w ^{'} ) - ϵs ( w ^{'} )}{ϵ} .$ The second term is nonnegative. Its ratio lies in $[0, 1]$ , and the two regime inequalities imply $0 \leq s_{a} (w^{'}) - ϵs (w^{'}) \leq s_{a} (w^{'}) - s_{a} (w) - ϵ {s (w^{'}) - s (w)} .$ Consequently the difference lies between $- ϵ^{- 1} Δ (w, w^{'})$ and $(1 + ϵ^{- 1}) Δ (w, w^{'})$ . Interchanging the vectors covers the remaining mixed regime.

Finally, $x \mapsto [x]_{+}$ is one-Lipschitz. Applying this to the hinge in Definition 12 gives $∣ f_{λ} (w) - f_{λ} (w^{'}) ∣ \leq 2∣ g_{0} (w) - g_{0} (w^{'}) ∣ + ∣ g_{1} (w) - g_{1} (w^{'}) ∣ + ∣ λ ∣ ∣ s (w) - s (w^{'}) ∣ \leq Λ_{ϵ} Δ (w, w^{'}) .$ Since $Δ (w, w^{'}) \leq 4∥ w - w^{'} ∥_{\infty}$ , $f_{λ}$ is continuous on $R$ .
Write $β_{α}^{c^{0}, R} (λ)$ for the centered coefficients in Algorithm 1 with its pilot center and radii replaced by $c^{0}, R$ . Explicitly, they are the unique coefficients satisfying $P_{λ} (c^{0} + R ⊙ z) - f_{λ} (c^{0}) = α \in {0, \dots, 2 (K - 1)}^{Z} \sum β_{α}^{c^{0}, R} (λ) ζ \in Z \prod z_{ζ}^{α_{ζ}}, z \in R^{Z} .$ The normalized polynomial is therefore $P_{λ} (z) = f_{λ} (c^{0}) + α \in {0, \dots, 2 (K - 1)}^{Z} \sum β_{α}^{c^{0}, R} (λ) ζ \in Z \prod z_{ζ}^{α_{ζ}}, z \in R^{Z} .$ The continuity just proved applies to $z \mapsto f_{λ} (c^{0} + R ⊙ z)$ on $[- 1, 1]^{4}$ . The normalized construction, including the added center value, therefore gives, for every $ϑ \in R^{4}$ , $P_{λ} (cos ϑ) = \int_{[- π, π]^{4}} f_{λ} (c^{0} + R ⊙ cos (ϑ + ω)) ζ \in Z \prod J_{K} (ω_{ζ}) d ω .$ The order-four kernel has trigonometric degree $2 (K - 1)$ in each coordinate, so $P_{λ}$ has coordinatewise polynomial degree at most $2 (K - 1)$ . Positive radii permit the affine substitution $P_{λ} (w) = P_{λ} (\frac{w _{ζ} - c _{ζ}^{0}}{R _{ζ}})_{ζ \in Z}, w \in R^{4},$ which preserves those coordinatewise degree bounds and identifies this polynomial with the one in the statement.
Put $ϑ_{ζ} = arccos (\frac{y _{ζ} - c _{ζ}^{0}}{R _{ζ}}), ζ \in Z .$ The evaluation-point assumption makes every angle well defined in $[0, π]$ , and $y = c^{0} + R ⊙ cos ϑ$ . Positivity and unit integral of each $J_{K}$ , followed by the Lipschitz estimate from the first step, yield $∣ P_{λ} (y) - f_{λ} (y) ∣ \leq Λ_{ϵ} ζ \in Z \sum R_{ζ} \int_{[- π, π]^{4}} ∣ cos (ϑ_{ζ} + ω_{ζ}) - cos ϑ_{ζ} ∣ ξ \in Z \prod J_{K} (ω_{ξ}) d ω .$ The cosine addition formula and $∣ sin t ∣ \leq ∣ t ∣$ , $1 - cos t \leq t^{2} /2$ give $∣ cos (ϑ_{ζ} + ω_{ζ}) - cos ϑ_{ζ} ∣ \leq ∣ sin ϑ_{ζ} ∣ ∣ ω_{ζ} ∣ + \frac{ω _{ζ}^{2}}{2} .$

For completeness, the kernel moments used here obey $\int_{- π}^{π} ∣ t ∣ J_{K} (t) d t \leq \frac{32}{K}, \int_{- π}^{π} t^{2} J_{K} (t) d t \leq \frac{64}{K ^{2}} .$ Indeed, writing $D_{K} (t) = \sum_{r = 0}^{K - 1} e^{i r t}$ , the unnormalized fourth power in Algorithm 1 is $∣ D_{K} (t) ∣^{4}$ . Orthogonality of the Fourier modes gives $\int_{- π}^{π} ∣ D_{K} (t) ∣^{4} d t = 2 π h = - (K - 1) \sum K - 1 (K - ∣ h ∣)^{2} = \frac{2 π}{3} K (2 K^{2} + 1) \geq \frac{4 π}{3} K^{3} .$ For $t \in [- π, π]$ , the inequality $t^{2} \leq π^{2} sin^{2} (t /2)$ , together with $\int_{- π}^{π} {sin (K t /2) / sin (t /2)}^{2} d t = 2 π K$ , bounds its weighted second integral by $2 π^{3} K$ . Normalization and $π^{2} \leq 16$ thus give the sharper second-moment bound $24/ K^{2}$ . Integrating $∣ t ∣ \leq \frac{K}{4} t^{2} + \frac{1}{K}$ gives a first-moment bound $7/ K$ ; the displayed bounds follow for every positive integer $K$ .

Integrating the cosine estimate coordinatewise now gives $∣ P_{λ} (y) - f_{λ} (y) ∣ \leq 32 Λ_{ϵ} ζ \in Z \sum {\frac{R _{ζ} ∣ sin ϑ _{ζ} ∣}{K} + \frac{R _{ζ}}{K ^{2}}} .$ Finally, $R_{ζ} ∣ sin ϑ_{ζ} ∣ = (y_{ζ} - c_{ζ}^{0} + R_{ζ}) (c_{ζ}^{0} + R_{ζ} - y_{ζ}) .$ Substitution proves the asserted bound, including points on the faces of the rectangle.

∎

The endpoint factors in Lemma 3 make the approximation bound sensitive to the evaluation point’s position within the pilot rectangle. To control observations outside the good-pilot event, the next lemma bounds moments of the pilot discrepancy and width together.

Lemma 4 [lem:pilot-bad-score-moment] (Bad pilot score moment).

Let $n, d \geq 1$ , let $P$ be an observed categorical law on the $d$ -cell alphabet, and fix a cell $j$ . Write $q_{ζ j}$ for its four category-cell masses and $p_{j} = \sum_{ζ \in Z} q_{ζ j}$ . Set $m = n /8$ and $L = lo g (e d)$ .

Suppose the four pilot counts are independent, with $N_{ζ j}^{'} \sim Pois (m q_{ζ j})$ for each $ζ \in Z$ . Form $c_{ζ j}$ and $h_{ζ j}$ as in Algorithm 1, and let $G_{j}$ be the quarter-halfwidth pilot event of Definition 17. Define $B_{j} = ζ \in Z \sum (∣ c_{ζ j} - q_{ζ j} ∣ + h_{ζ j}), v_{j} = \frac{p _{j} L}{m} + \frac{L}{m} .$ For each $t \in {1, 2, 4}$ , $E [1_{G_{j}^{c}} B_{j}^{t}] \leq 4^{t} 1 0^{80 (t + 1)} e^{- 20 L} v_{j}^{t} .$

⊢ Lean

Proof of Lemma 4.

For each $ζ \in Z$ and $w \in N$ , define $ρ_{ζ} = m q_{ζ j}, γ_{ζ} = ρ_{ζ} L + L, σ_{ζ} (w) = ∣ w - ρ_{ζ} ∣ + 1024 (w L + L),$ and let $E_{ζ} = {∣ N_{ζ j}^{'} - ρ_{ζ} ∣ > 256 (N_{ζ j}^{'} L + L)} .$ Here $m > 0$ and $L = lo g (e d) \geq 1$ , including when $d = 1$ . The following scalar estimates hold also when $q_{ζ j} = 0$ : $Pr (E_{ζ}) \leq 2 e^{- 80 L}, E σ_{ζ} (N_{ζ j}^{'})^{ν} \leq 1 0^{4 ν + 4} γ_{ζ}^{ν} (0 \leq ν \leq 8) .$ For the first estimate, a count $w$ in $E_{ζ}$ with $w \geq ρ_{ζ}$ satisfies $w - ρ_{ζ} > 160 ρ_{ζ} L + 160 L;$ one with $w < ρ_{ζ}$ satisfies $ρ_{ζ} - w > 160 ρ_{ζ} L .$ For the upper tail, $ρ_{ζ} \leq w$ gives $160 ρ_{ζ} L \leq 16 w L$ , so the defining threshold exceeds the stated Bernstein threshold. For the lower tail, the bad-event condition gives $ρ_{ζ} - w > 256 (w L + L)$ . Since $L \geq 1$ , $[256 (w L + L)]^{2} - 160 L 256 (w L + L) - 160 w L = 65376 w L + 90112 L w L + 24576 L^{2} > 0.$ Moreover, $[(ρ_{ζ} - w)^{2} - 160 L (ρ_{ζ} - w) - 160 w L] - [[256 (w L + L)]^{2} - 160 L 256 (w L + L) - 160 w L] = (ρ_{ζ} - w - 256 (w L + L)) (ρ_{ζ} - w + 256 (w L + L) - 160 L) > 0.$ Thus $(ρ_{ζ} - w)^{2} > 160 L {w + (ρ_{ζ} - w)} = 160 ρ_{ζ} L$ ; positivity of the deviation gives $ρ_{ζ} - w > 160 ρ_{ζ} L$ . The upper and lower Poisson Bernstein bounds at level $80 L$ give $e^{- 80 L}$ for each tail.

For the moment estimate, put $ξ_{ζ} = 1/ (2 γ_{ζ})$ . Since $γ_{ζ} \geq 1$ and $ρ_{ζ} ξ_{ζ}^{2} \leq 1/4$ , $σ_{ζ} (w) \leq 1536 (γ_{ζ} + ∣ w - ρ_{ζ} ∣), E exp {\frac{σ _{ζ} ( N _{ζ j}^{'} )}{4096 γ _{ζ}}} \leq e^{1/2} \pm \sum exp {ρ_{ζ} (e^{\pm ξ_{ζ}} - 1 \mp ξ_{ζ})} \leq 2 e^{3/4} < 8.$ The middle expression is the centered Poisson exponential moment; the last inequality uses $e^{\pm ξ_{ζ}} - 1 \mp ξ_{ζ} \leq ξ_{ζ}^{2}$ . Applying $x^{ν} \leq ν! e^{x}$ to the nonnegative exponent and $8 ν! 409 6^{ν} \leq 1 0^{4 ν + 4}$ for $0 \leq ν \leq 8$ yields the stated moment estimate.

For $t \in {1, 2, 4}$ , the elementary square inequality gives $1_{E_{ζ}} σ_{ζ} (N_{ζ j}^{'})^{t} \leq \frac{1}{2} [e^{- 40 L} γ_{ζ}^{- t} σ_{ζ} (N_{ζ j}^{'})^{2 t} + e^{40 L} γ_{ζ}^{t} 1_{E_{ζ}}] .$ Taking expectations and using the two estimates above gives $E [1_{E_{ζ}} σ_{ζ} (N_{ζ j}^{'})^{t}] \leq \frac{1 0 ^{8 t + 4} + 2}{2} e^{- 40 L} γ_{ζ}^{t} \leq 1 0^{8 t + 8} e^{- 40 L} γ_{ζ}^{t} .$
Define $E_{j} = ζ \in Z ⋃ E_{ζ}, Σ_{j} = ζ \in Z \sum σ_{ζ} (N_{ζ j}^{'}), Γ_{j} = m p_{j} L + L .$ For $ζ, η \in Z$ , the preceding truncated moment applies when $ζ = η$ . When $ζ \neq = η$ , independence factors the expectation, and the probability and ordinary moment estimates apply. Thus, in both cases, $E [1_{E_{ζ}} σ_{η} (N_{η j}^{'})^{t}] \leq (1 0^{8 t + 8} + 2 \cdot 1 0^{4 t + 4}) e^{- 40 L} γ_{η}^{t} .$ All scores are nonnegative, so the four-term power inequality and the union bound yield $E [1_{E_{j}} Σ_{j}^{t}] \leq 4^{t - 1} ζ, η \in Z \sum E [1_{E_{ζ}} σ_{η} (N_{η j}^{'})^{t}] .$ Since $\sum_{η} ρ_{η} = m p_{j}$ , Cauchy–Schwarz and nonnegativity give $η \sum γ_{η} \leq 2 m p_{j} L + 4 L \leq 4 Γ_{j}, η \sum γ_{η}^{t} \leq 4 (η \sum γ_{η})^{t} .$ Consequently, $E [1_{E_{j}} Σ_{j}^{t}] \leq 4^{2 t + 1} (1 0^{8 t + 8} + 2 \cdot 1 0^{4 t + 4}) e^{- 40 L} Γ_{j}^{t} \leq 1 0^{80 (t + 1)} e^{- 20 L} Γ_{j}^{t} .$ The final coefficient comparison holds for each of $t = 1, 2, 4$ , and $L \geq 1$ gives $e^{- 40 L} \leq e^{- 20 L}$ .
By Algorithm 1, for every $ζ$ , $c_{ζ j} = \frac{N _{ζ j}^{'}}{m}, h_{ζ j} = \frac{4096}{m} (N_{ζ j}^{'} L + L) .$ The event in Definition 17 therefore satisfies $G_{j}^{c} \subseteq E_{j}$ : failure of its quarter-halfwidth condition requires a deviation greater than $1024 (N_{ζ j}^{'} L + L)$ , which exceeds the threshold defining $E_{ζ}$ . Pointwise, $B_{j} = \frac{1}{m} ζ \in Z \sum {∣ N_{ζ j}^{'} - ρ_{ζ} ∣ + 4096 (N_{ζ j}^{'} L + L)} \leq \frac{4}{m} Σ_{j} .$ Finally, $Γ_{j} / m = p_{j} L / m + L / m = v_{j}$ . Applying the preceding product moment bound proves $E [1_{G_{j}^{c}} B_{j}^{t}] \leq (\frac{4}{m})^{t} E [1_{E_{j}} Σ_{j}^{t}] \leq 4^{t} 1 0^{80 (t + 1)} e^{- 20 L} v_{j}^{t} .$

∎

The exponential factor in Lemma 4 controls the contribution of bad pilot localizations. Across cells, bounded variation gives a maximal inequality for the centered paths on either part of the pilot split.

Lemma 5 [lem:bv-maximal-cell-paths] (Maximal bound for centered cell paths).

Let $n, d$ be nonnegative integers, let $ϵ \in R$ , and let $P$ be a discrete law on the $d$ -cell alphabet with category-cell masses $q_{ζ j}$ . In the ideal count experiment of Definition 17, the pilot and evaluation counts $N_{ζ j}^{'}$ and $N_{ζ j}$ are mutually independent with $Pois (m q_{ζ j})$ laws, where $m = n /8$ . Choose the pilot events uniformly across cells: either $E_{j} = G_{j}$ for every $j$ , or $E_{j} = G_{j}^{c}$ for every $j$ , with $G_{j}$ as in Definition 17. For each cell $j$ , define the path on $[0, 1]$ by $W_{j} (λ) = 1_{E_{j}} {T_{j} (λ) - f_{λ} (q_{j})},$ where $T_{j}$ is the clipped cell estimate of Algorithm 1 and $f_{λ}$ is defined in Definition 12. Assume:

(Regularity.) For every count table and cell $j$ , $W_{j}$ is continuous in $λ$ . For each $j$ , the count-table map into $C ([0, 1])$ is measurable and Bochner integrable.

(Finite variation.) For each $j$ , $TV_{[0, 1]} (W_{j}) < \infty$ almost surely.

(Second moments.) For each $j$ , $(∥ W_{j} ∥_{\infty} + TV_{[0, 1]} (W_{j}))^{2}$ is integrable.

(Independence.) The paths $W_{1}, \dots, W_{d}$ are independent.

Then $E j = 1 \sum d (W_{j} - E W_{j})_{\infty}^{2} \leq 16384 j = 1 \sum d E [(∥ W_{j} ∥_{\infty} + TV_{[0, 1]} (W_{j}))^{2}] .$

⊢ Lean

Proof of Lemma 5.

1. Set up the count law and path envelopes. Let $P_{id}$ be the joint law of the pilot and evaluation count tables in Definition 17. For a count table $ω$ , write $W_{j} (ω)$ for the path in the statement and set $ρ_{j} (ω) = ∥ W_{j} (ω) ∥_{\infty} + TV_{[0, 1]} (W_{j} (ω)) .$ The second-moment assumption makes both $ρ_{j}^{2}$ and $∥ W_{j} ∥_{\infty}^{2}$ integrable. The regularity assumptions give Bochner-integrable paths, and the independence assumption applies to their joint law. These observations also cover $d = 0$ , when every sum below is empty.

2. Reduce the centered sum to signed differences. Take independent count tables $ω, ω^{'}$ with law $P_{id}$ , and define, for $j = 1, \dots, d$ and $λ \in [0, 1]$ , $Δ_{j} (λ) = W_{j} (λ; ω) - W_{j} (λ; ω^{'}) .$ Let $η_{1}, \dots, η_{d}$ be independent uniform signs, independent of the count tables, and define their signed supremum energy by $E_{η} (Δ) = E_{η} j = 1 \sum d η_{j} Δ_{j}_{\infty}^{2} .$ Jensen’s inequality applied to the independent copy gives $E j = 1 \sum d (W_{j} - E W_{j})_{\infty}^{2} \leq E_{ω, ω^{'}} j = 1 \sum d Δ_{j}_{\infty}^{2} .$ The pairs $(W_{j} (ω), W_{j} (ω^{'}))$ are independent across $j$ . Swapping either entry of any pair preserves their joint law and reverses the sign of its difference. Averaging these equalities over all sign choices therefore yields $E_{ω, ω^{'}} j = 1 \sum d Δ_{j}_{\infty}^{2} = E_{ω, ω^{'}} E_{η} (Δ) .$ All these expectations are finite by the second-moment assumption.

3. Bound the signed supremum for fixed count tables. Fix a pair $(ω, ω^{'})$ for which every $W_{j}$ has finite variation. Let $V_{j} (t)$ , $t \in [0, 1]$ , be the cumulative variation of $Δ_{j}$ from $0$ to $t$ . Continuity and finite variation give a continuous, nondecreasing control satisfying $V_{j} (0) = 0, V_{j} (1) = TV_{[0, 1]} (Δ_{j}), ∣ Δ_{j} (t) - Δ_{j} (s) ∣ \leq V_{j} (t) - V_{j} (s) (s \leq t) .$ Define the common control on $[0, 1]$ by $U (t) = j = 1 \sum d V_{j} (1) V_{j} (t) .$ Since $0 \leq V_{j} (t) - V_{j} (s) \leq V_{j} (1)$ , $j = 1 \sum d (Δ_{j} (t) - Δ_{j} (s))^{2} \leq U (t) - U (s) (s \leq t) .$

Choose ordered, compatible dyadic control quantiles $t_{k, i}$ , for $k \geq 0$ and $0 \leq i \leq 2^{k}$ , so that $U (t_{k, i}) = \frac{i}{2 ^{k}} U (1) .$ Such choices follow from continuity of $U$ . For each sign vector, let $M_{k} (η) = 0 \leq i < 2^{k + 1} max j = 1 \sum d η_{j} (Δ_{j} (t_{k + 1, i + 1}) - Δ_{j} (t_{k + 1, i})) .$ By Equation 1, every edge at level $k + 1$ has squared coefficient sum at most $U (1) / 2^{k + 1}$ . For $k \geq 0$ , $0 \leq i < 2^{k + 1}$ , and $1 \leq j \leq d$ , write $γ_{k, i, j} = Δ_{j} (t_{k + 1, i + 1}) - Δ_{j} (t_{k + 1, i}), Y_{k} (η) = M_{k} (η)^{2}, v_{k} = \frac{U ( 1 )}{2 ^{k + 1}} .$ When $v_{k} > 0$ , each edge satisfies $\sum_{j} γ_{k, i, j}^{2} \leq v_{k}$ . For every $χ > 0$ , independence of the signs and the elementary bound $cosh z \leq e^{z^{2} /2}$ give $E_{η} exp (χ j \sum η_{j} γ_{k, i, j}) = j \prod cosh (χ γ_{k, i, j}) \leq exp (\frac{χ ^{2} v _{k}}{2}) .$ Applying this bound to both signs, choosing $χ = s / v_{k}$ , and taking the union over $2^{k + 1}$ edges gives, for $s > 0$ , $P_{η} {Y_{k} \geq s} \leq 2^{k + 2} exp (- \frac{s}{2 v _{k}}) .$ Set $t_{k} = 2 v_{k} lo g (2^{k + 2})$ . Integrating the tail above $t_{k}$ yields $E_{η} Y_{k} \leq t_{k} + \int_{t_{k}}^{\infty} 2^{k + 2} e^{- s / (2 v_{k})} d s = 2 v_{k} {lo g (2^{k + 2}) + 1} \leq 32 (1 + lo g (2^{k + 1})) v_{k} .$ When $v_{k} = 0$ , Equation 1 makes every edge increment zero. Thus in every case $E_{η} M_{k} (η)^{2} \leq 32 (1 + lo g (2^{k + 1})) \frac{U ( 1 )}{2 ^{k + 1}} .$ The numerical factors in Equation 2 have a summable square root: $k = 0 \sum \infty \frac{32 ( 1 + lo g ( 2 ^{k + 1} ))}{2 ^{k + 1}} \leq k = 0 \sum \infty 8 (\frac{3}{4})^{k} = 32 \leq 40.$ Here the termwise bound follows from $lo g 2 \leq 1$ and $k + 2 \leq 4 (9/8)^{k}$ .

To reconstruct the signed path, for each $t \in [0, 1]$ and $k \geq 0$ define $ξ (t) = {U (t) / U (1), 0, U (1) > 0, U (1) = 0, ι_{k} (t) = min {2^{k} - 1, ⌊ 2^{k} ξ (t)⌋} .$ These lower dyadic indices start at zero, satisfy $ι_{k + 1} (t) \in {2 ι_{k} (t), 2 ι_{k} (t) + 1}$ , and obey $\frac{ι _{k} ( t )}{2 ^{k}} \leq ξ (t) \leq \frac{ι _{k} ( t ) + 1}{2 ^{k}} .$ The parent grid point equals the even child by compatibility; the odd child differs by one adjacent edge. At level zero the grid point and $0$ have the same control value, so Equation 1 makes their path coordinates equal. Telescoping therefore gives, for every $k \geq 0$ , $j = 1 \sum d η_{j} Δ_{j} (t_{k, ι_{k} (t)}) \leq j = 1 \sum d η_{j} Δ_{j} (0) + ν = 0 \sum k - 1 M_{ν} (η),$ where the sum is empty at $k = 0$ . The control values of $t_{k, ι_{k} (t)}$ and $t$ differ by at most $U (1) / 2^{k}$ . Applying Equation 1 in whichever order these two times occur gives $j = 1 \sum d (Δ_{j} (t_{k, ι_{k} (t)}) - Δ_{j} (t))^{2} \leq \frac{U ( 1 )}{2 ^{k}} .$ Hence the finite signed sums along the chain converge to their value at $t$ , including on flat parts of the control. If $U (1) = 0$ , the same control bound makes all $Δ_{j}$ constant and the conclusion is immediate. Passing to the limit and taking the supremum over $t$ gives $j = 1 \sum d η_{j} Δ_{j}_{\infty} \leq j = 1 \sum d η_{j} Δ_{j} (0) + k = 0 \sum \infty M_{k} (η) .$ Sign orthogonality, the $L_{2}$ triangle inequality, and Equations 2 and 3 imply $E_{η} (Δ) \leq 4096 {j = 1 \sum d Δ_{j} (0)^{2} + U (1)} \leq 4096 j = 1 \sum d (∥ Δ_{j} ∥_{\infty} + TV_{[0, 1]} (Δ_{j}))^{2} .$ Finally, the triangle inequalities for the supremum norm and total variation give $E_{η} (Δ) \leq 8192 j = 1 \sum d (ρ_{j} (ω)^{2} + ρ_{j} (ω^{'})^{2}) .$

4. Average the pointwise bound. Integrating the last inequality over the two independent count tables and using their identical laws gives $E_{ω, ω^{'}} E_{η} (Δ) \leq 8192 j = 1 \sum d E_{ω, ω^{'}} (ρ_{j} (ω)^{2} + ρ_{j} (ω^{'})^{2}) = 16384 j = 1 \sum d E ρ_{j}^{2} .$ Combining this with the two relations in Step 2 proves the stated inequality.

∎

By Lemma 5, cellwise path moments yield control uniform in the shadow price. The reported estimator averages over auxiliary draws from an observed sample; the following identity relates that average to the uncapped count experiment.

Lemma 6 [lem:capped-marked-count-identity] (Capped marked-count integral identity).

Fix $n, d \in N$ and an observed categorical law $P$ on the $d$ -cell alphabet, with category-cell masses $q_{ζ j}$ . Let $O^{(n)} = (O_{1}, \dots, O_{n}) \sim P^{\otimes n}$ . For $M \in {0, \dots, n}$ , a permutation $σ$ of the $n$ record indices, and pilot/evaluation marks $ω \in {pilot, evaluation}^{n}$ , write $(N^{'}, N) (O^{(n)}, σ, M, ω)$ for the pilot and evaluation count tables formed from the first $M$ permuted records according to Algorithm 1. Define $w_{n} (M) = \frac{Pr { Pois ( n /4 ) = M }}{n ! 2 ^{n}} .$ In the uncapped marked-Poisson experiment, $M \sim Pois (n /4)$ ; conditional on $M$ , draw $M$ independent records from $P$ and mark each independently as pilot or evaluation with probability $1/2$ , yielding count tables $(N^{'}, N)$ .

For every real-valued function $g$ of pairs of count tables that is integrable under the ideal law of Definition 17, whose pilot and evaluation category-cell counts are independent $Pois ((n /8) q_{ζ j})$ variables, $E_{O^{(n)} \sim P^{\otimes n}} M = 0 \sum n σ \sum ω \in {pilot, evaluation}^{n} \sum w_{n} (M) g ((N^{'}, N) (O^{(n)}, σ, M, ω)) = E_{uncapped} [1 {M \leq n} g (N^{'}, N)] .$

⊢ Lean

Proof of Lemma 6.

Let $O_{d} = {1, \dots, d} \times {0, 1}^{2}$ , and let $S_{d}$ be the space of finite sequences of records in $O_{d}$ , each carrying a pilot or evaluation mark. Write $S = (M, ((O_{i}^{\circ}, χ_{i}))_{i = 1}^{M}) \in S_{d}$ for a sequence with law $Q$ : $M \sim Pois (n /4)$ , the $O_{i}^{\circ}$ are independent with law $P$ , and the independent marks $χ_{i}$ are pilot or evaluation with probability $1/2$ each. Define $Φ : S_{d} \to (N^{Z \times {1, \dots, d}})^{2}$ by $Φ (S) = (N^{'} (S), N (S))$ , where $N_{ζ j}^{'} (S) = i = 1 \sum M 1 {O_{i}^{\circ} = (j, ζ), χ_{i} = pilot}, N_{ζ j} (S) = i = 1 \sum M 1 {O_{i}^{\circ} = (j, ζ), χ_{i} = evaluation} .$ These are the count tables used in Algorithm 1. Partition the marked observation space into the singleton types $(j, ζ, χ)$ , where $χ \in {pilot, evaluation}$ . Each type has probability $q_{ζ j} /2$ . For any array $ν = (ν_{ζ j, χ}) \in N^{Z \times {1, \dots, d} \times {pilot, evaluation}}$ , the Poisson probability of the total count and the conditional multinomial probability of the singleton counts give $Q Pr {# {i \leq M : O_{i}^{\circ} = (j, ζ), χ_{i} = χ} = ν_{ζ j, χ} for all (ζ, j, χ)} = e^{- n /4} \frac{( n /4 ) ^{\sum_{ζ, j, χ} ν_{ζ j, χ}}}{( \sum _{ζ, j, χ} ν _{ζ j, χ} ) !} \frac{( \sum _{ζ, j, χ} ν _{ζ j, χ} ) !}{\prod _{ζ, j, χ} ν _{ζ j, χ} !} ζ, j, χ \prod (\frac{q _{ζ j}}{2})^{ν_{ζ j, χ}} = ζ, j, χ \prod e^{- (n /8) q_{ζ j}} \frac{( ( n /8 ) q _{ζ j} ) ^{ν_{ζ j, χ}}}{ν _{ζ j, χ} !} .$ Here $\sum_{ζ, j} q_{ζ j} = 1$ , and zero powers use the usual convention $0^{0} = 1$ . Grouping the singleton counts by mark gives $Φ (S)$ ; the factorization shows that its pilot and evaluation coordinates are independent Poisson variables, each with mean $(n /8) q_{ζ j}$ . Its law is the ideal count law specified in Definition 17; the identity also covers zero cell masses and $n = 0$ .
Set $φ : S_{d} \to R$ by $φ (S) = g (Φ (S))$ . The preceding identification and the assumed integrability of $g$ give $E_{Q} ∣ φ (S) ∣ = E_{ideal} ∣ g (N^{'}, N) ∣ < \infty.$
For $0 \leq M \leq n$ , define the marked prefix $S_{M} (O^{(n)}, σ, ω) = (M, ((O_{σ (i)}, ω_{i}))_{i = 1}^{M}) .$ A permutation of an independent $P$ -sample remains an independent $P$ -sample, while a uniform mark vector gives each mark probability $1/2$ . Consequently, at every $M$ whose Poisson probability is positive, $E_{O^{(n)}} [\frac{1}{n ! 2 ^{n}} σ \sum ω \sum φ (S_{M} (O^{(n)}, σ, ω))] = E [φ (M, ((O_{i}^{\circ}, χ_{i}))_{i = 1}^{M})] .$ Integrability under $Q$ supplies integrability on each such count fibre; fibres with zero Poisson probability contribute zero. Multiplying by the respective Poisson probabilities and summing over $M \leq n$ therefore yields $E_{O^{(n)}} [M = 0 \sum n σ \sum ω \sum \frac{Pr { Pois ( n /4 ) = M }}{n ! 2 ^{n}} φ (S_{M} (O^{(n)}, σ, ω))] = E_{Q} [1 {M \leq n} φ (S)] .$ This is the finite count-fibre decomposition of the marked-Poisson expectation.
For every admissible prefix, the indicator sums defining $Φ$ agree coordinatewise with the permuted pilot and evaluation counts: $Φ (S_{M} (O^{(n)}, σ, ω)) = (N^{'}, N) (O^{(n)}, σ, M, ω) .$ Substitute this identity and $φ = g \circ Φ$ into the preceding equality. Its left side has weight $w_{n} (M)$ , and its right side is the stated nonoverflow expectation under the uncapped marked-Poisson experiment. When $d = 0$ , there is no probability law on the empty observed alphabet, so the assertion quantified over $P$ is vacuous.

∎

The identity in Lemma 6 supplies the count-law link for the conditional average. Together with the radius, approximation, bad-pilot, and maximal-path bounds, it supports a common constant for the process criterion and the threshold-process bounds.

Theorem 4 [thm:integrated-process-certificate] (Uniform integrated process bounds).

Fix an overlap parameter $0 < ϵ < 1/2$ . There is a single constant $C_{ϵ} > 0$ , belonging to the uniform process handle in Definition 17, for which the following conclusions hold whenever:

(Sample and alphabet.) $n \geq 1$ , $d \geq 16$ , and $d / lo g (e d) \leq n$ .

(Sampling.) The law $μ$ of the $n$ observed records satisfies Assumption 1 for the observed margin of $P$ .

(Causal law.) The full-data law $P$ belongs to $M_{d, ϵ}$ of Definition 4.

Write $L = lo g (e d)$ , $m = n /8$ , and $v_{j} = p_{j} L / m + L / m$ . Simultaneously for every cell $j$ and every $λ \in [0, 1]$ , the absolute bias of the uncapped Jackson cell estimate of $f_{λ} (q_{j})$ is at most $C_{ϵ} {\frac{p _{j}}{n L} + \frac{1}{n L}} .$ The expected squared supremum of the centered good-pilot error sum is at most $C_{ϵ} d / (n L)$ . The uncentered bad-pilot cell envelope satisfies $1_{G_{j}^{c}} λ \in [0, 1] sup ∣ T_{j} (λ) - f_{λ} (q_{j}) ∣_{L_{2}} \leq C_{ϵ} d^{1/4} e^{- 10 L} v_{j},$ and the expected squared supremum of the centered bad-pilot error sum is at most $C_{ϵ} d / (m L)$ . Finally, the ideal and averaged versions of the dual threshold process in Algorithm 1 each have expected squared supremum error relative to $F_{P}$ at most $C_{ϵ} d / (n L)$ . The same $C_{ϵ}$ applies to all these bounds.

⊢ Lean

The final process bounds in Theorem 4 apply to an entire interval of shadow prices. Through the dual representation in Proposition 1, they provide the simultaneous control used in Theorem 3, including budgets selected after the curve is estimated. The average is formed at the threshold-process level before optimization.

Two boundedness facts establish that the empirical and conditionally averaged threshold processes have finite values throughout the shadow-price interval.

Lemma 7 [lem:empirical-threshold-process-bounded] (Bounded empirical threshold process).

For any $n, d \in N$ , any real overlap parameter $ϵ$ , and any sample $O^{(n)}$ of $n$ observations on the $d$ -cell alphabet, let $F (λ) = j = 1 \sum d f_{λ} (q_{j})$ be the empirical threshold process of Algorithm 1, with $f_{λ}$ as in Definition 12. There exists $B \in R$ such that $∣ F (λ) ∣ \leq B for every λ \in [0, 1] .$

⊢ Lean

Proof of Lemma 7.

Fix $n, d, ϵ$ and the sample. For each cell $j$ , Definition 12 and Algorithm 1 give, for $λ \in [0, 1]$ , $f_{λ} (q_{j}) = g_{0} (q_{j}) + max {0, g_{1} (q_{j}) - g_{0} (q_{j}) - λ s (q_{j})} .$ The empirical vector $q_{j}$ is fixed as $λ$ varies. Thus this expression is continuous in $λ$ , and so is its finite sum $F (λ)$ . When $n = 0$ , the empirical vectors are zero under the convention $x /0 = 0$ ; when $d = 0$ , the sum is empty and $F$ is identically zero. The same continuity argument covers both cases.

Since $[0, 1]$ is compact, the continuous real-valued function $F$ is bounded there. Hence some $B \in R$ satisfies $∣ F (λ) ∣ \leq B for every λ \in [0, 1] .$

∎

Conditional averaging over the auxiliary Poisson count preserves boundedness for the threshold process used by the reported estimator.

Lemma 8 [lem:averaged-threshold-process-bounded] (Bounded averaged threshold process).

Fix any observed sample $O^{(n)}$ of $n$ records from a $d$ -cell alphabet. Suppose:

(Overlap parameter.) $ϵ > 0$ .

(Sample size.) $n \geq 1$ .

(Alphabet size.) $d \geq 1$ .

The conditionally averaged threshold process $F (λ)$ of Algorithm 1, whose Poisson $(n /4)$ weights are summed over $M = 0, \dots, n$ , is bounded on $[0, 1]$ : there exists $B \in R$ such that $∣ F (λ) ∣ \leq B for every λ \in [0, 1] .$

⊢ Lean

Proof of Lemma 8.

1. Continuity of the cell threshold. For $u, u^{'} \in R_{+}^{4}$ , write $s_{a} (u) = u_{a 0} + u_{a 1} (a \in {0, 1}), s (u) = s_{0} (u) + s_{1} (u) = a, y \in {0, 1} \sum u_{a y} .$ Assign the quotient in Definition 12 the value $g_{a} (0) = 0$ at its zero denominator. The bounds below show that this is its continuous extension on the nonnegative cone. Since $u$ is nonnegative, $s (u) = 0$ implies $u = 0$ . When $s (u) > 0$ , its two branches are $s (u) u_{a 1} / s_{a} (u)$ and $u_{a 1} / ϵ$ , according as $s_{a} (u) \geq ϵs (u)$ or $s_{a} (u) < ϵs (u)$ . On each branch, its absolute coordinate derivatives are at most $1 + ϵ^{- 1}$ ; at zero, $0 \leq g_{a} (u) \leq s (u)$ . Comparing along the segment between two nonnegative vectors therefore gives, for $a \in {0, 1}$ , $∣ g_{a} (u) - g_{a} (u^{'}) ∣ \leq (1 + ϵ^{- 1}) ζ \in Z \sum ∣ u_{ζ} - u_{ζ}^{'} ∣.$ The positive-part map is $1$ -Lipschitz. Thus, for $λ \in [0, 1]$ , $∣ f_{λ} (u) - f_{λ} (u^{'}) ∣ \leq 2∣ g_{0} (u) - g_{0} (u^{'}) ∣ + ∣ g_{1} (u) - g_{1} (u^{'}) ∣ + λ ∣ s (u) - s (u^{'}) ∣ \leq [3 (1 + ϵ^{- 1}) + 1] ζ \in Z \sum ∣ u_{ζ} - u_{ζ}^{'} ∣.$ Hence $f_{λ}$ is continuous on the nonnegative cone for every fixed $λ \in [0, 1]$ .

2. The pilot rectangle. Fix any pilot counts and cell $j$ . The quantities in Algorithm 1 satisfy $m = \frac{n}{8} > 0, L = lo g (e d) \geq 1, δ = \frac{L}{m} > 0, h_{ζ j} > 0.$ For every $z \in [- 1, 1]^{Z}$ and $ζ \in Z$ , $0 \leq ℓ_{ζ j} \leq c_{ζ j}^{0} + R_{ζ j} z_{ζ} \leq u_{ζ j} .$ The map $z \mapsto c_{j}^{0} + R_{j} ⊙ z$ is affine and continuous. Since $f_{λ}$ is continuous on the nonnegative cone, its composition with this map is continuous on $[- 1, 1]^{Z}$ for every $λ \in [0, 1]$ . This includes pilot counts arising when $M = 0$ .

3. Continuity of each clipped cell estimate. Keep the counts fixed. The Jackson order and degree in Algorithm 1 satisfy $K \geq 2$ and $D = 2 (K - 1) \geq 2$ . For $r = 0, \dots, D$ , set $ξ_{r} = \frac{r}{D + 1}, ξ_{γ} = (ξ_{γ_{ζ}})_{ζ \in Z}, ϑ_{γ, ζ} = arccos (ξ_{γ_{ζ}}), γ \in {0, \dots, D}^{Z} .$ At a fixed grid point, the defining Jackson integral and the threshold formula give $P_{j, λ} (c_{j}^{0} + R_{j} ⊙ ξ_{γ}) - P_{j, μ} (c_{j}^{0} + R_{j} ⊙ ξ_{γ}) \leq ∣ λ - μ ∣ \int_{[- π, π]^{Z}} s (c_{j}^{0} + R_{j} ⊙ cos (ϑ_{γ} + t)) ζ \in Z \prod J_{K} (t_{ζ}) d t, λ, μ \in [0, 1],$ where cosine acts coordinatewise. The integral is finite: its argument lies in the pilot rectangle, and the integrand is continuous on a compact box. Also, $∣ f_{λ} (c_{j}^{0}) - f_{μ} (c_{j}^{0}) ∣ \leq ∣ λ - μ ∣ s (c_{j}^{0}) .$

For $α, γ \in {0, \dots, D}^{Z}$ , define the fixed tensor interpolation weights by $z^{α} := ζ \in Z \prod z_{ζ}^{α_{ζ}}, w_{α, γ} := [z^{α}] ζ \in Z \prod 0 \leq r \leq D r \neq = γ_{ζ} \prod \frac{z _{ζ} - ξ _{r}}{ξ _{γ_{ζ}} - ξ _{r}},$ where $[z^{α}]$ extracts the indicated coefficient. Tensor Lagrange interpolation of the degree- $D$ polynomial yields $β_{j, α} (λ) = γ \in {0, \dots, D}^{Z} \sum w_{α, γ} [P_{j, λ} (c_{j}^{0} + R_{j} ⊙ ξ_{γ}) - f_{λ} (c_{j}^{0})] .$ The preceding bounds show that every $β_{j, α} (λ)$ is continuous in $λ$ . All count-dependent factors in $Z_{j} (λ) = f_{λ} (c_{j}^{0}) + α \in {0, \dots, D}^{Z} \sum β_{j, α} (λ) ζ \in Z \prod \frac{U _{α_{ζ}} ( N _{ζ j} ; c _{ζ j}^{0} )}{R _{ζ j}^{α_{ζ}}}$ are fixed and have positive radii in their denominators. Thus $Z_{j}$ is continuous. Finally, $T_{j} (λ) = f_{λ} (c_{j}^{0}) + min {d^{1/4} S_{j}, max {- d^{1/4} S_{j}, Z_{j} (λ) - f_{λ} (c_{j}^{0})}}$ is continuous, since finite minima and maxima preserve continuity.

4. Averaging and boundedness. Write $S_{n}$ for the permutations of the $n$ record positions. Conditional on the fixed sample, the average is the finite sum $F (λ) = M = 0 \sum n \frac{e ^{- n /4} ( n /4 ) ^{M}}{M !} \frac{1}{n ! 2 ^{n}} σ \in S_{n} \sum ω \in {0, 1}^{n} \sum (j = 1 \sum d T_{j} (λ))_{M, σ, ω} .$ Only the first $M$ marks affect the count table; each marking of those retained records occurs $2^{n - M}$ times in the displayed sum. Thus the $2^{n}$ normalization gives the same average as $2^{M}$ markings of the retained records. The vertical bar means that the counts are computed from that permutation and marking. Each cell summand $T_{j} (λ)$ is continuous in $λ$ . The capped value for $M > n$ is the constant zero. Hence $F$ is continuous on $[0, 1]$ . Compactness of that interval gives the finite real number $B = λ \in [0, 1] max ∣ F (λ) ∣, ∣ F (λ) ∣ \leq B for every λ \in [0, 1] .$

∎

For the lower bound, a simplex records the masses assigned to pairs of covariate cells. The paired family then isolates the effect of allocating a fixed treatment capacity across unequal benefits.

Definition 18 [def:paired-family] (Paired causal family

P_{k}^{pair}

The paired causal family $P_{k}^{pair}$ consists of causal completions constructed as follows. For $k \geq 1$ , choose $r = (r_{1}, \dots, r_{k})$ in the simplex and $θ_{i} \in [- 1/8, 1/8]$ . For each $i$ , create cells $(i, +)$ and $(i, -)$ with masses $r_{i} /2$ , and set $e_{i, σ} = \frac{1}{2}, μ_{0, i, σ} = \frac{1}{4}, μ_{1, i, σ} = \frac{1}{2} + σ θ_{i}, σ \in {+ 1, - 1} .$ Generate the potential outcomes independently of $A$ conditional on $X$ .

⊢ Lean

The simplex $Δ_{k}$ in Definition 19 supplies the pair-mass vector for Definition 18.

Definition 19 [synth_10] (Probability simplex on

k

categories).

For an integer $k \geq 1$ , define $Δ_{k} = {r = (r_{1}, \dots, r_{k}) \in [0, 1]^{k} : i = 1 \sum k r_{i} = 1} .$

With the pair masses specified, the causal family fixes the propensity and control mean while varying the treatment mean within each pair. Treatment effects remain positive while their ranking depends on the contrast. The capacity and sampling identities make this allocation problem explicit.

Proposition 3 [prop:paired-capacity-identity] (Paired capacity and sample identity).

Let $k \geq 1$ and $0 < ϵ < 1/2$ . The following statements hold.

(Capacity identity.) For every $P \in P_{k}^{pair}$ and every pair-mass vector $r \in Δ_{k}$ and contrast vector $θ \in [- 1/8, 1/8]^{k}$ for which $P$ satisfies the paired-completion conditions of Definition 18, the law $P$ belongs to $M_{2 k, ϵ}$ of Definition 4. Every occupied cell has treatment effect $τ_{j} \in [1/8, 3/8]$ . The half-population budget is attained by a policy $π \in Π_{1/2} (P)$ satisfying $j \sum p_{j} π_{j} = \frac{1}{2}, V_{1/2} (P) = B (P) + j \sum p_{j} π_{j} τ_{j} .$ For the budget values of Definition 9, $V_{1/2} (P) = \frac{3}{8} + \frac{1}{2} i = 1 \sum k r_{i} ∣ θ_{i} ∣ = \frac{1}{8} + F_{P} (\frac{1}{4}), V_{1} (P) = \frac{1}{2} .$

(Exact sample reduction.) For every integer $n \geq 0$ , there is a Markov kernel from pairs of $n$ -record samples on the $k$ -point alphabet to $n$ observed records on the $2 k$ -cell alphabet with the following property. For every pair $R, S \in Δ_{k}$ , the simplex of $k$ -point laws, set $r_{i} = \frac{R _{i} + S _{i}}{2}, θ_{i} = ⎩ ⎨ ⎧ 0, \frac{R _{i} - S _{i}}{8 ( R _{i} + S _{i} )}, R_{i} + S_{i} = 0, R_{i} + S_{i} > 0.$ The paired law determined by $(r, θ)$ belongs to $P_{k}^{pair}$ . Applying the kernel to independent $n$ -record samples from $R$ and $S$ yields exactly the law of $n$ independent observed records from the observed margin of that paired law.

⊢ Lean

For two sampling laws $R$ and $S$ , the exact sample reduction gives a half-budget value of $3/8 + ∥ R - S ∥_{1} /32$ , while the full-budget value is $1/2$ . Thus the half-budget comparison carries a two-sample distance problem within the causal model. The statistical lower-bound input is a squared-error bound for the two-sample distance.

The following bound states the two-sample risk at the scale used by the reduction.

Lemma 9 [lem:two-sample-l1-lower] (Two-sample

L_{1}

lower bound).

There is a universal constant $c > 0$ such that, for every integer $k \geq 2$ and $1 \leq n \leq k^{2}$ , the minimax squared-error risk for estimating $∥ R - S ∥_{1}$ from $n$ independent observations from each of $R, S \in Δ_{k}$ , the probability simplex on $k$ categories, satisfies $L in f R, S \in Δ_{k} sup E_{R, S} [(L - ∥ R - S ∥_{1})^{2}] \geq c min {1, \frac{k}{n lo g ( e k )}} .$

⊢ Lean

Proof of Lemma 9.

Write $R_{n, k} := L in f R, S \in Δ_{k} sup E_{R, S} [(L - ∥ R - S ∥_{1})^{2}] .$

We first transfer the published known- $S$ bound to this two-sample experiment. Given a two-sample estimator $L$ and a fixed $S$ , average over its second sample: $\overline{L}_{S} (X^{n}) := E_{Y^{n} \sim S^{\otimes n}} [L (X^{n}, Y^{n})] .$ Conditional Jensen inequality gives, for every $R$ , $E_{R} [(\overline{L}_{S} - ∥ R - S ∥_{1})^{2}] \leq E_{R, S} [(L - ∥ R - S ∥_{1})^{2}] .$ Taking the relevant suprema and infima therefore yields $S \in Δ_{k} sup L_{S} in f R \in Δ_{k} sup E_{R} [(L_{S} - ∥ R - S ∥_{1})^{2}] \leq R_{n, k} .$

The published bound (Jiao et al., 2018), applied with $a_{0} = 1$ and $C_{0} = 2$ , consequently supplies constants $γ_{pub} > 0$ and $k_{0}$ such that $R_{n, k} \geq γ_{pub} \frac{k}{n lo g n} if k \geq k_{0}, n \geq \frac{k}{lo g k}, lo g n \leq 2 lo g k .$ For $n \geq 2$ , the last condition and $lo g (e k) = 1 + lo g k$ imply $R_{n, k} \geq \frac{γ _{pub}}{2} \frac{k}{n lo g ( e k )} .$

In particular, enlarging a threshold $k_{D}$ if necessary, there is a constant $γ_{D} > 0$ such that, whenever $k \geq k_{D}$ , $k \geq 2$ , $2 \leq n \leq k^{2}$ , and $n \geq k / lo g k$ , $R_{n, k} \geq γ_{D} min {1, \frac{k}{n lo g ( e k )}} .$ Indeed, $n \leq k^{2}$ gives $lo g n \leq 2 lo g k$ , and the minimum is at most its second argument.

For the smaller sample sizes, use the same dense bound at the integer $n_{\circ} (k) := ⌈ \frac{k}{lo g k} ⌉ .$ When $k \geq 3$ , the inequalities $1 \leq lo g k \leq k - 1$ show that $k / lo g k > 1$ , while $\frac{k}{lo g k} \leq n_{\circ} (k) < \frac{k}{lo g k} + 1 \leq \frac{2 k}{lo g k}, n_{\circ} (k) \leq k^{2}, lo g n_{\circ} (k) \leq 2 lo g k .$ Also $lo g (e k) \leq 2 lo g k$ , so $n_{\circ} (k) lo g (e k) \leq 4 k$ . Applying the dense bound at $n_{\circ} (k)$ thus gives, for some $γ_{S} > 0$ and threshold $k_{S}$ , $R_{n_{\circ} (k), k} \geq γ_{S} (k \geq max {k_{S}, 3}) .$ If $1 \leq n < k / lo g k$ , then $n \leq n_{\circ} (k)$ . An estimator with $n_{\circ} (k)$ observations can use their first $n$ coordinates, whose law is exactly the $n$ -sample law. Hence $R_{n, k} \geq R_{n_{\circ} (k), k} \geq γ_{S} .$

Set $k_{⋆} := max {k_{D}, k_{S}, 3}$ . To cover $2 \leq k < k_{⋆}$ , consider the two parameter pairs $(R_{0}, S) = ((1, 0, \dots, 0), (1, 0, \dots, 0)), (R_{1}, S) = ((1/2, 1/2, 0, \dots, 0), (1, 0, \dots, 0)) .$ Their targets are $0$ and $1$ . Let $ω_{0}$ be the data point at which every observation in both samples has the first category, and put $ρ_{n} := 2^{- n}$ . The probabilities of ${ω_{0}}$ under the two pairs are $1$ and $ρ_{n}$ , respectively. Thus, for every estimator $L$ , its worst-case risk satisfies $R, S \in Δ_{k} sup E_{R, S} [(L - ∥ R - S ∥_{1})^{2}] \geq max {L (ω_{0})^{2}, ρ_{n} (L (ω_{0}) - 1)^{2}} \geq \frac{ρ _{n}}{4},$ since $ρ_{n} \leq 1$ and $x^{2} + (x - 1)^{2} \geq 1/2$ for every real $x$ . Taking the infimum over estimators gives $R_{n, k} \geq \frac{ρ _{n}}{4} .$

Minimax risk decreases as the sample size increases by the same first-coordinate argument. Since $n \leq k^{2} \leq k_{⋆}^{2}$ , the preceding bound at $k_{⋆}^{2}$ gives $R_{n, k} \geq R_{k_{⋆}^{2}, k} \geq \frac{2 ^{- k_{⋆}^{2}}}{4} (2 \leq k < k_{⋆}) .$

Finally, choose $c := min {γ_{D}, γ_{S}, \frac{2 ^{- k_{⋆}^{2}}}{4}} > 0.$ For $k \geq k_{⋆}$ , split according as $n < k / lo g k$ or $n \geq k / lo g k$ ; the sparse and dense bounds, respectively, give the claim. For $2 \leq k < k_{⋆}$ , use the finite-alphabet bound. In each case the claimed minimum is at most $1$ .

∎

The published intermediate-regime lower-bound input for Lemma 9 is given by Jiao et al. (2018). Combined with the exact sample reduction in Proposition 3, the lemma supplies the half-budget lower bound in Theorem 2. That bound and the upper bound in Theorem 3 yield the matched risk statement in Theorem 1 under its stated conditions.

The theorem statements and internal proofs are machine-checked in Lean 4. The sampling and causal conditions in Assumptions 1, 2, 3, and 4 are model assumptions. The published conclusion cited for Lemma 9 is a mathematical input from the literature.

Proofs of the main results

Proof of Proposition 1.

Write $p_{j} = P (X = j), q_{(a, y) j} = P (X = j, A = a, Y = y), μ_{aj} = E_{P} [Y (a) ∣ X = j], τ_{j} = μ_{1 j} - μ_{0 j}, B (P) = j = 1 \sum d p_{j} μ_{0 j} .$ For a cell with $p_{j} = 0$ , set $μ_{aj} = 0$ ; its contributions below vanish. The cell masses are nonnegative, and the binary outcomes give $μ_{aj} \in [0, 1]$ , hence $τ_{j} \leq 1$ .

For an occupied cell, Assumptions 2, 3, and 4 give $s_{a} (q_{j}) = P (X = j, A = a) \geq ϵ p_{j} > 0$ and $g_{a} (q_{j}) = p_{j} \frac{P ( X = j , A = a , Y = 1 )}{P ( X = j , A = a )} = p_{j} μ_{aj} .$ For a null cell, $q_{j} = 0$ and the same identity has both sides zero. Substituting these identities into Definition 12, and using $p_{j} \geq 0$ , yields, for $0 \leq λ \leq 1$ , $f_{λ} (q_{j}) = p_{j} μ_{0 j} + p_{j} [τ_{j} - λ]_{+}, F_{P} (λ) = B (P) + j = 1 \sum d p_{j} [τ_{j} - λ]_{+} .$

Fix $b \in [0, 1]$ . If $π \in Π_{b} (P)$ , then $0 \leq π_{j} \leq 1$ and $\sum_{j} p_{j} π_{j} \leq b$ by Definition 5. For $λ \in [0, 1]$ , the inequality $p_{j} π_{j} (τ_{j} - λ) \leq p_{j} [τ_{j} - λ]_{+}$ holds whether $τ_{j} - λ$ is nonnegative or negative. Since $λ \geq 0$ , $j = 1 \sum d p_{j} π_{j} τ_{j} = λ j = 1 \sum d p_{j} π_{j} + j = 1 \sum d p_{j} π_{j} (τ_{j} - λ) \leq bλ + j = 1 \sum d p_{j} [τ_{j} - λ]_{+} .$ Taking the maximum over feasible policies and using Definition 9 gives $V_{b} (P) \leq bλ + F_{P} (λ) (0 \leq λ \leq 1), V_{b} (P) \leq 0 \leq λ \leq 1 in f {bλ + F_{P} (λ)} .$

For the reverse inequality, the feasible policy set is a compact subset of $[0, 1]^{d}$ , contains the zero policy, and has a continuous gain. Thus a feasible maximizer $π^{⋆}$ exists. Applied to the affine budget and box constraints, the polyhedral normal-cone formula gives nonnegative multipliers $λ^{⋆}, η_{j}^{-}, η_{j}^{+}$ satisfying $j \sum p_{j} π_{j}^{⋆} \leq b, λ^{⋆} (b - j \sum p_{j} π_{j}^{⋆}) = 0, η_{j}^{-} π_{j}^{⋆} = 0, η_{j}^{+} (1 - π_{j}^{⋆}) = 0, p_{j} (λ^{⋆} - τ_{j}) - η_{j}^{-} + η_{j}^{+} = 0.$ These conditions give the hinge identity cell by cell. It is immediate when $p_{j} = 0$ . When $p_{j} > 0$ , a coordinate with $π_{j}^{⋆} = 0$ has $η_{j}^{+} = 0$ and $τ_{j} \leq λ^{⋆}$ ; one with $π_{j}^{⋆} = 1$ has $η_{j}^{-} = 0$ and $τ_{j} \geq λ^{⋆}$ ; an interior coordinate has both box multipliers zero and $τ_{j} = λ^{⋆}$ . Consequently, $p_{j} π_{j}^{⋆} τ_{j} = λ^{⋆} p_{j} π_{j}^{⋆} + p_{j} [τ_{j} - λ^{⋆}]_{+}, j \sum p_{j} π_{j}^{⋆} τ_{j} = b λ^{⋆} + j \sum p_{j} [τ_{j} - λ^{⋆}]_{+},$ where the second equality uses budget complementary slackness.

If $λ^{⋆} \leq 1$ , this is a witness with price in $[0, 1]$ . If $λ^{⋆} > 1$ , then $τ_{j} \leq 1$ makes every hinge at $λ^{⋆}$ zero. Also, $b λ^{⋆} = j \sum p_{j} π_{j}^{⋆} τ_{j} \leq j \sum p_{j} π_{j}^{⋆} \leq b .$ As $b \geq 0$ , this forces $b = 0$ . Every hinge at price $1$ is then zero as well, and the displayed witness equality holds with price $1$ . Hence in every case there is $λ_{b} \in [0, 1]$ such that $b λ_{b} + F_{P} (λ_{b}) = B (P) + j \sum p_{j} π_{j}^{⋆} τ_{j} = V_{b} (P) .$ The process $F_{P}$ is a finite sum of continuous hinge functions on $[0, 1]$ , so it is bounded there. Thus the dual infimum is well defined and is at most its value at $λ_{b}$ . Together with weak duality, this proves the representation.

Finally, define $ω_{F, F_{P}} = λ \in [0, 1] sup ∣ F (λ) - F_{P} (λ) ∣.$ Both processes are bounded on $[0, 1]$ , so $ω_{F, F_{P}}$ is finite and both dual objectives are bounded below for $b \in [0, 1]$ . For every such $b$ and every $λ \in [0, 1]$ , the two inequalities $bλ + F (λ) \leq bλ + F_{P} (λ) + ω_{F, F_{P}}, bλ + F_{P} (λ) \leq bλ + F (λ) + ω_{F, F_{P}}$ give, on taking infima, $0 \leq λ \leq 1 in f {bλ + F (λ)} - 0 \leq λ \leq 1 in f {bλ + F_{P} (λ)} \leq ω_{F, F_{P}} .$ Substitute the representation just proved and take the supremum over $b \in [0, 1]$ .

∎

Proof of Theorem 1.

Set $ϱ_{n, d} := min {1, \frac{d}{n lo g ( e d )}} .$

Choose $c_{ϵ} > 0$ from Theorem 2 and $C_{ϵ}^{up} > 0$ from Theorem 3, and define $C_{ϵ} := C_{ϵ}^{up} + c_{ϵ} .$

The discrete $L_{1}$ lower bound underlying Theorem 2 is supplied by (Jiao et al., 2018).

Fix $n \geq 1$ , $d \geq 2$ , and $b_{0} \in [0, 1/2]$ , and use the independent observed-record laws of Assumption 1. Since $b_{0} \leq 1/2 \leq 1 - b_{0}$ , evaluation of any admissible curve estimator $V$ at $1/2$ gives a measurable scalar estimator $T_{V} (O^{(n)}) := V_{1/2} (O^{(n)}) .$

By Theorem 2, there is a law $P \in M_{d, ϵ}$ for which $c_{ϵ} ϱ_{n, d} \leq E_{P} [(T_{V} - V_{1/2} (P))^{2}] \leq E_{P} [b \in [b_{0}, 1 - b_{0}] sup V_{b} - V_{b} (P)^{2}] \leq P^{'} \in M_{d, ϵ} sup E_{P^{'}} [b \in [b_{0}, 1 - b_{0}] sup V_{b} - V_{b} (P^{'})^{2}] .$

The middle inequality holds samplewise because $1/2$ belongs to the budget interval. The lower-bound result also supplies a law in the model class when applied to the zero scalar estimator, while Algorithm 1 supplies an admissible curve estimator. Thus taking the infimum over curve estimators in Definition 15 gives $c_{ϵ} ϱ_{n, d} \leq R_{n, d, ϵ, b_{0}}^{curve} .$

For the upper bound, insert the estimator of Algorithm 1 into that infimum. Theorem 3 bounds its worst-case curve risk, so $R_{n, d, ϵ, b_{0}}^{curve} \leq P \in M_{d, ϵ} sup E_{P} [b \in [b_{0}, 1 - b_{0}] sup V_{b}^{JF} - V_{b} (P)^{2}] \leq C_{ϵ}^{up} ϱ_{n, d} \leq C_{ϵ} ϱ_{n, d} .$

Here $ϱ_{n, d} \geq 0$ , and the chosen constants satisfy $0 < c_{ϵ} \leq C_{ϵ} < \infty$ .

Now let $T$ be any measurable scalar estimator. Applying Theorem 2 to the same independent observed-record laws supplies a law $P \in M_{d, ϵ}$ with $V_{1} (P) = 1/2$ , a binding half-budget policy $π \in Π_{1/2} (P)$ , and $j = 1 \sum d p_{j} π_{j} = \frac{1}{2}, V_{1/2} (P) = B (P) + j = 1 \sum d p_{j} π_{j} τ_{j}, E_{P} [(T - V_{1/2} (P))^{2}] \geq c_{ϵ} ϱ_{n, d} .$

For every occupied cell, the same result gives $p_{j} > 0 ⟹ \frac{1}{8} \leq τ_{j} \leq \frac{3}{8} ⟹ τ_{j} > 0.$

Finally, suppose $b_{0} = 0$ and take any $P \in M_{d, ϵ}$ . Since $p_{j} \geq 0$ and $\sum_{j} p_{j} = 1$ , every policy in $[0, 1]^{d}$ is feasible at budget $1$ . For any such policy, $j = 1 \sum d p_{j} π_{j} τ_{j} \leq j = 1 \sum d p_{j} max {τ_{j}, 0},$

and equality is attained by the policy $π_{j}^{*} := 1 {τ_{j} > 0}, j = 1, \dots, d .$

Consequently, Definition 9 gives $V_{1} (P) = B (P) + j = 1 \sum d p_{j} max {τ_{j}, 0} .$

∎

Proof of Theorem 2.

Write $R_{n, k} = H in f R, S \in Δ_{k} sup E_{R, S} [(H - ∥ R - S ∥_{1})^{2}] .$ Here $H$ ranges over measurable estimators based on $n$ observations from each of $R$ and $S$ . We first establish the two-sample bound used in the proof: $R_{n, k} \geq c_{L} min {1, \frac{k}{n lo g ( e k )}} (k \geq 2, n \geq 1)$ for a universal $c_{L} > 0$ .

For $n \leq k^{2}$ , this is Lemma 9. Its dense-range input is the published known- $S$ bound: when $n \geq a_{0} k / lo g k$ and $lo g n \leq C_{0} lo g k$ , the worst-case squared risk is at least a positive constant times $k / (n lo g n)$ , with constants depending on $a_{0}, C_{0}$ (Jiao et al., 2018).

For completeness, consider the remaining range $n > k^{2}$ . At sufficiently large $k$ , set $h = ⌊ k /2 ⌋, ℓ = 16 (⌊ lo g_{2} k ⌋ + 1), ξ = \frac{h ℓ}{200 n} > 0, ω = \frac{ξ}{50 ℓ} .$ To obtain the finite priors used here, let $E_{ℓ} = d e g φ \leq ℓ in f ∣ x ∣ \leq 1 sup ∣ x ∣ - φ (x) .$ Polynomial alternation gives nodes $x_{0} < \dots < x_{ℓ + 1}$ in $[- 1, 1]$ and signed weights $a_{i}$ , normalized so that $i \sum ∣ a_{i} ∣ = 1, i \sum a_{i} x_{i}^{ℓ^{'}} = 0 (0 \leq ℓ^{'} \leq ℓ), i \sum a_{i} ∣ x_{i} ∣ = E_{ℓ} .$ Indeed, the weights proportional to $\prod_{i^{'} \neq = i} (x_{i} - x_{i^{'}})^{- 1}$ annihilate polynomials of degree at most $ℓ$ by Lagrange interpolation; their alternating signs can be oriented to agree with the alternating approximation errors. The required approximation error has the bound $E_{ℓ} \geq \frac{1}{100 ℓ} .$ For this bound, let $F_{ℓ}$ denote the normalized Fejér kernel of order $ℓ$ on the circle of period $π$ , and define $g (ϕ) = ∣ sin (2 ϕ) ∣, D_{ℓ} f = f (0) - ((2 F_{2 ℓ} - F_{ℓ}) * f) (0) .$ The Fejér kernels have integral one, so $∥ D_{ℓ} ∥ \leq 4$ . Their Fourier multipliers give $D_{ℓ} [φ (sin (2 ϕ))] = 0$ when $de g φ \leq ℓ$ . The Fourier series of $g$ has nonnegative contributions to the magnitude of this functional; retaining the frequencies indexed from $ℓ$ through $2 ℓ - 1$ yields $∣ D_{ℓ} g ∣ \geq ℓ^{'} = ℓ \sum 2 ℓ - 1 \frac{4}{π ( 4 ℓ ^{'} ^{2} - 1 )} \geq \frac{1}{16 ℓ} .$ Thus $4 E_{ℓ} \geq 1/ (16 ℓ)$ , which gives the displayed bound. Writing $a_{i}^{+} = max (a_{i}, 0)$ and $a_{i}^{-} = max (- a_{i}, 0)$ , define $ν_{0} = 2 i \sum a_{i}^{-} δ_{x_{i}}, ν_{1} = 2 i \sum a_{i}^{+} δ_{x_{i}} .$ The degree-zero identity makes each measure a probability measure. The remaining identities show that their moments agree through degree $ℓ$ and that $\int ∣ x ∣ d ν_{1} (x) - \int ∣ x ∣ d ν_{0} (x) = 2 E_{ℓ} \geq \frac{1}{50 ℓ} .$

Use $2 h$ cells and, for $z = (z_{1}, \dots, z_{h}) \in [- 1, 1]^{h}$ , define the two probability vectors by $R_{i, \pm} = \frac{1}{2 h}, S_{i, \pm} (z) = \frac{1 \pm ξ z _{i}}{2 h}, ∥ R - S (z) ∥_{1} = \frac{ξ}{h} i = 1 \sum h ∣ z_{i} ∣.$ Under prior $ν_{s}^{\otimes h}$ , the target has center $γ_{s} = ξ \int ∣ z ∣ d ν_{s} (z)$ . Independence gives $∣ γ_{1} - γ_{0} ∣ \geq ω, Var_{ν_{s}^{\otimes h}} (∥ R - S (z) ∥_{1}) \leq \frac{ξ ^{2}}{h} .$ For the stated sufficiently large alphabet threshold, $128 ξ^{2} \leq h ω^{2}$ . Chebyshev’s inequality therefore places at most $1/8$ of either prior outside the interval of radius $ω /4$ around its center.

To compare the sample laws, Poissonize the $S$ -sample at mean $2 n$ . Conditional on $z_{i}$ , the two counts in pair $i$ are independent Poisson variables with means $(n / h) (1 + ξ z_{i})$ and $(n / h) (1 - ξ z_{i})$ . Relative to $z_{i} = 0$ , their likelihood ratios obey $E_{0} [L_{z} L_{z^{'}}] = exp (\frac{2 n ξ ^{2}}{h} z z^{'}) .$ For $s \in {0, 1}$ , define the one-pair mixture, its null reference law, its density, and the exponential scale by $Q_{s} = \int [Pois (\frac{n}{h} (1 + ξ z)) \otimes Pois (\frac{n}{h} (1 - ξ z))] d ν_{s} (z), Q_{\circ} = Pois (n / h)^{\otimes 2}, ρ_{s} = \frac{d Q _{s}}{d Q _{\circ}}, Δ ν = ν_{1} - ν_{0}, χ = \frac{2 n ξ ^{2}}{h} \leq \frac{ℓ}{50} .$ The likelihood identity above and the matching moments give $\int (ρ_{1} - ρ_{0})^{2} d Q_{\circ} = ℓ^{'} > ℓ \sum \frac{χ ^{ℓ^{'}}}{ℓ ^{'} !} (\int z^{ℓ^{'}} d Δ ν (z))^{2} \leq 4 ℓ^{'} > ℓ \sum \frac{χ ^{ℓ^{'}}}{ℓ ^{'} !} .$ Here $\int z^{ℓ^{'}} d Δ ν (z) \leq 2$ because both priors are supported on $[- 1, 1]$ . For $ℓ^{'} > ℓ$ , the factorial bound $ℓ^{'}! \geq (ℓ^{'} / e)^{ℓ^{'}}$ , together with $e < 3$ , yields $χ^{ℓ^{'}} / ℓ^{'}! \leq (1/4)^{ℓ^{'}}$ . Cauchy–Schwarz therefore gives $TV (Q_{0}, Q_{1}) \leq \frac{1}{2} (\int (ρ_{1} - ρ_{0})^{2} d Q_{\circ})^{1/2} \leq (ℓ^{'} > ℓ \sum 4^{- ℓ^{'}})^{1/2} \leq 2^{- ℓ} \leq 2^{- ℓ /4} .$ The pair mixtures are independent under either prior. Telescoping their product densities and using the one-pair bound gives $TV (Q_{0}^{\otimes h}, Q_{1}^{\otimes h}) \leq h TV (Q_{0}, Q_{1}) \leq h 2^{- ℓ /4} .$ When a $Pois (2 n)$ count reaches $n$ , its first $n$ marks have the fixed-sample law. For each prior, replacing the sample on the complementary event changes its predictive law in total variation by at most $Pr {Pois (2 n) < n}$ . The triangle inequality therefore adds twice this probability. Exponential Markov inequality at $lo g 2$ gives $Pr {Pois (2 n) < n} \leq exp {- (1 - lo g 2) n} .$ Since $h \leq k /2$ , $2^{- ℓ /4} \leq k^{- 4}$ , and $n > k^{2}$ , these bounds give, for the stated sufficiently large alphabet threshold, the fixed-sample predictive bound $TV (prior-0 samples, prior-1 samples) \leq h 2^{- ℓ /4} + 2 Pr {Pois (2 n) < n} \leq \frac{1}{16} .$ The first sample has the same law $R$ under both priors, so it leaves this comparison unchanged.

Choose the nearer of $γ_{0}, γ_{1}$ from an arbitrary estimator of $∥ R - S ∥_{1}$ . The sum of its testing errors is at least $15/16$ by the predictive bound. The two prior tail probabilities contribute at most $1/4$ ; on each remaining error event, squared estimation error is at least $ω^{2} /16$ . Consequently $R_{n, 2 h} \geq \frac{11}{512} ω^{2}, ω^{2} = \frac{h}{500000 n ℓ} \geq c \frac{k}{n lo g ( e k )}$ for a universal $c > 0$ . Padding the unused cell when $k$ is odd preserves the target and sample law.

The finitely many alphabet sizes below that threshold are covered by a binary comparison. Take $R = (1/2, 1/2)$ , compare $S = R$ with $S = ((1 + ξ) /2, (1 - ξ) /2)$ , and set $ξ = 1/ (64 n)$ . The targets differ by $ξ$ , while independence and the one-record chi-squared identity give $χ^{2} (S^{\otimes n}, R^{\otimes n}) = (1 + ξ^{2})^{n} - 1 \leq \frac{1}{64} .$ Thus their total variation is at most $1/16$ , and the same testing argument yields a constant multiple of $1/ n$ . Zero-mass padding and the finite bound on $k / lo g (e k)$ give the asserted rate for these alphabet sizes. Combining the ranges, and using $k / (n lo g (e k)) < 1$ when $n > k^{2}$ , proves the displayed two-sample bound.

Now fix $T, n, d$ as in the statement. Suppose first that $d \geq 4$ , and put $k = ⌊ d /2 ⌋$ . Then $k \geq 2$ and $2 k \leq d$ . For each $R, S \in Δ_{k}$ , choose the paired law of Definition 18 with $r_{i} = \frac{R _{i} + S _{i}}{2}, θ_{i} = ⎩ ⎨ ⎧ 0, \frac{R _{i} - S _{i}}{8 ( R _{i} + S _{i} )}, R_{i} + S_{i} = 0, R_{i} + S_{i} > 0.$ The capacity and sample identities in Proposition 3 give $V_{1/2} (P_{R, S}) = \frac{3}{8} + \frac{1}{32} ∥ R - S ∥_{1}, V_{1} (P_{R, S}) = \frac{1}{2},$ and an exact Markov kernel taking the two independent $n$ -samples to $n$ observed records from $P_{R, S}$ . Apply $T$ after this kernel and condition on the two input samples. The resulting two-sample estimator of $∥ R - S ∥_{1}$ has squared risk at most $3 2^{2}$ times the squared risk of $T$ , by conditional Jensen’s inequality. Since the two-sample lower bound is positive, a parameter pair attains at least half its lower-bound value. Hence some paired law satisfies $E_{P_{R, S}} [(T - V_{1/2} (P_{R, S}))^{2}] \geq \frac{c _{L}}{2048} min {1, \frac{k}{n lo g ( e k )}} .$ Pad the law with zero-mass cells to reach $d$ labels. The observed sample law, both budget values, and the occupied-cell properties are preserved; Assumption 1 identifies the stipulated sampling law with that product law.

Because $k \leq d \leq 3 k$ and $lo g (e k) \leq lo g (e d)$ , $min {1, \frac{d}{n lo g ( e d )}} \leq 3 min {1, \frac{k}{n lo g ( e k )}} .$ Thus the required bound holds in this case with coefficient $c_{L} /6144$ .

For $d = 2, 3$ , use one occupied pair and pad any remaining cell by zero mass. Compare paired contrasts $0$ and $t = \frac{1}{8 n} .$ Both laws satisfy the class, value, occupied-effect, and binding-capacity properties by Proposition 3. Their half-budget values are $3/8$ and $3/8 + t /2$ . The one-record chi-squared divergence is $2 t^{2}$ ; tensorization and $2 n t^{2} = 1/32 \leq lo g 2$ give total variation at most $1/2$ for the $n$ -record laws. Testing at the midpoint of the two values then puts error probability at least $1/4$ under one law, on an event where absolute estimation error is at least $t /4$ . Therefore one of the laws satisfies $E_{P} [(T - V_{1/2} (P))^{2}] \geq \frac{( t /4 ) ^{2}}{4} = \frac{1}{4096 n} .$ For $2 \leq d \leq 3$ , $min {1, d / [n lo g (e d)]} \leq 3/ n$ . Taking $c_{ϵ} = min {\frac{c _{L}}{6144}, \frac{1}{12288}} > 0$ completes both cases.

∎

Proof of Proposition 2.

Fix $d \geq 2$ and write $lo g (e d) = 1 + lo g d, α_{d} := \frac{d}{lo g ( e d )} .$ Since $lo g d \leq d - 1$ and $d > 1$ , we have $0 < lo g (e d) \leq d$ , so $α_{d} \geq 1$ . Thus, for every $n \geq 1$ , $\frac{1}{n} \leq min {1, \frac{d}{n lo g ( e d )}} = min {1, \frac{α _{d}}{n}} \leq \frac{α _{d}}{n} .$

The lower-bound input to Theorem 1 is the known-distribution $L_{1}$ minimax result of (Jiao et al., 2018). Applying the stated frontier bound and then the preceding comparison gives, uniformly over $b_{0} \in [0, 1/2]$ , $\frac{c _{ϵ}}{n} \leq c_{ϵ} min {1, \frac{d}{n lo g ( e d )}} \leq R_{n, d, ϵ, b_{0}}^{curve} \leq C_{ϵ} min {1, \frac{d}{n lo g ( e d )}} \leq \frac{C _{ϵ} α _{d}}{n} .$

The risk-bound constants can be chosen as $c_{ϵ}$ and $C_{ϵ} α_{d}$ , respectively; they are positive, ordered, and fixed across $n$ and $b_{0}$ .

For the identity, denote the common effect in occupied cells by $γ$ , so that $τ_{j} = γ > 0 whenever p_{j} > 0.$ If $b_{0} \in [0, 1/2]$ and $b \in [b_{0}, 1 - b_{0}]$ , then $0 \leq b \leq 1$ . Cell masses satisfy $p_{j} \geq 0$ and $\sum_{j} p_{j} = 1$ . In a zero-mass cell both sides of the following identity vanish. Hence, for every $π \in Π_{b} (P)$ , $j = 1 \sum d p_{j} π_{j} τ_{j} = γ j = 1 \sum d p_{j} π_{j} \leq γ b,$ where the last inequality is the budget constraint in Definition 5.

Define the constant policy by $π_{j}^{(b)} = b$ for every cell $j$ . Because $0 \leq b \leq 1$ , its coordinates are valid, and $j = 1 \sum d p_{j} π_{j}^{(b)} = b j = 1 \sum d p_{j} = b, j = 1 \sum d p_{j} π_{j}^{(b)} τ_{j} = γ b .$

Thus $π^{(b)} \in Π_{b} (P)$ attains the upper bound. The maximization in Definition 9 equals $γ b$ , and therefore $V_{b} (P) = B (P) + γ b$ , as claimed.

∎

Proof of Theorem 3.

1. Constants and unit bound. Write $L := lo g (e d) = 1 + lo g d, ρ_{n, d} := \frac{d}{n L}, γ_{ϵ} := 3 (1 + ϵ^{- 1}) + 1.$ Let $C_{ϵ}^{proc} > 0$ be the constant supplied by Theorem 4, and set $C_{ϵ} := max {1, C_{ϵ}^{proc}, 4096 γ_{ϵ}^{2}} > 0.$ Since $d \geq 2$ , the inequality $lo g d \leq d - 1$ gives $0 < L \leq d$ , so $ρ_{n, d} \geq 0$ .

The interval $I = [b_{0}, 1 - b_{0}]$ is nonempty and contained in $[0, 1]$ . Write $p_{j} = P (X = j), μ_{aj} = {E_{P} [Y (a) ∣ X = j], 0, p_{j} > 0, p_{j} = 0, τ_{j} = μ_{1 j} - μ_{0 j}, B (P) = j = 1 \sum d p_{j} μ_{0 j} .$ The binary potential-outcome condition in Definition 4 gives $0 \leq μ_{aj} \leq 1$ , including the stated convention at empty cells. For any $b \in I$ , the zero policy is feasible under Definition 5, and the value of every feasible policy is $B (P) + j = 1 \sum d p_{j} π_{j} τ_{j} = j = 1 \sum d p_{j} {(1 - π_{j}) μ_{0 j} + π_{j} μ_{1 j}} \in [0, 1] .$ Hence $V_{b} (P) \in [0, 1]$ by Definition 9. The estimator in Algorithm 1 is either $1/2$ or clipped to $[0, 1]$ . Under Assumption 1, its squared supremum loss therefore satisfies $E_{P} [b \in I sup V_{b}^{JF} - V_{b} (P)^{2}] \leq 1.$

2. Alphabets with $2 \leq d < 16$ . In this branch, $F$ is the empirical threshold process of Algorithm 1. It is bounded on $[0, 1]$ by Lemma 7. The dual representation and its uniform perturbation bound in Proposition 1, together with contraction by clipping toward $V_{b} (P) \in [0, 1]$ , give, sample by sample, $b \in I sup V_{b}^{JF} - V_{b} (P)^{2} \leq (λ \in [0, 1] sup F (λ) - F_{P} (λ))^{2} .$

Here is the pointwise estimate used for the empirical process. Let $Z = {0, 1}^{2}$ , index $ζ = (a, y)$ , and write $q_{ζ j} = P (X = j, A = a, Y = y), s_{a} (u) = u_{(a, 0)} + u_{(a, 1)}, s (u) = s_{0} (u) + s_{1} (u)$ for every nonnegative four-vector $u = (u_{ζ})_{ζ \in Z}$ . For nonnegative four-vectors $u, v$ , define $Δ (u, v) := ζ \in Z \sum ∣ u_{ζ} - v_{ζ} ∣.$ For the formula in Definition 12, explicitly define its value at the zero vector by $g_{a} (0) = 0$ . This is its continuous extension, since $0 \leq g_{a} (u) \leq s (u)$ for every nonnegative $u$ with $s (u) > 0$ . Thus $f_{λ} (0) = 0$ , and the stabilized arm contributions, including those of empty covariate cells, obey $∣ g_{a} (u) - g_{a} (v) ∣ \leq (1 + ϵ^{- 1}) Δ (u, v), ∣ s (u) - s (v) ∣ \leq Δ (u, v) .$ To see the first inequality, an arm with $s_{a} (u) \leq ϵs (u)$ has $g_{a} (u) = u_{a 1} / ϵ$ ; an arm with $s_{a} (u) \geq ϵs (u) > 0$ has $g_{a} (u) = s (u) u_{a 1} / s_{a} (u)$ . When both vectors are in the latter regime, use $\frac{u _{a 1}}{s _{a} ( u )} - \frac{v _{a 1}}{s _{a} ( v )} \leq \frac{∣ u _{a 1} - v _{a 1} ∣ + ∣ u _{a 0} - v _{a 0} ∣}{s _{a} ( u )}, \frac{s ( u )}{s _{a} ( u )} \leq ϵ^{- 1},$ and $u_{a 1} / s_{a} (u), v_{a 1} / s_{a} (v) \in [0, 1]$ . When both vectors are in the first regime, $∣ g_{a} (u) - g_{a} (v) ∣ = ∣ u_{a 1} - v_{a 1} ∣/ ϵ \leq ϵ^{- 1} Δ (u, v)$ . When $u$ is in the first regime and $v$ in the second, use $g_{a} (u) - g_{a} (v) = \frac{u _{a 1} - v _{a 1}}{ϵ} + \frac{v _{a 1}}{s _{a} ( v )} \frac{s _{a} ( v ) - ϵs ( v )}{ϵ} .$ The second term is nonnegative and $0 \leq v_{a 1} / s_{a} (v) \leq 1$ . Since $s_{a} (u) \leq ϵs (u)$ , its numerator satisfies $s_{a} (v) - ϵs (v) \leq s_{a} (v) - s_{a} (u) + ϵ {s (u) - s (v)} .$ Combining these inequalities cancels the $a 1$ coordinate in the upper bound and gives $- ϵ^{- 1} Δ (u, v) \leq g_{a} (u) - g_{a} (v) \leq ϵ^{- 1} (v_{a 0} - u_{a 0}) + s (u) - s (v) \leq (1 + ϵ^{- 1}) Δ (u, v) .$ Swapping $u$ and $v$ handles the reverse case. If either total mass is zero, that vector is zero and $0 \leq g_{a} (w) \leq s (w)$ gives the bound directly. Since $x \mapsto [x]_{+}$ is one-Lipschitz and $0 \leq λ \leq 1$ , it follows that $∣ f_{λ} (u) - f_{λ} (v) ∣ \leq 2∣ g_{0} (u) - g_{0} (v) ∣ + ∣ g_{1} (u) - g_{1} (v) ∣ + λ ∣ s (u) - s (v) ∣ \leq γ_{ϵ} Δ (u, v) .$

Applying this cellwise and using Cauchy–Schwarz across the $4 d$ category-cell coordinates yields $(λ \in [0, 1] sup ∣ F (λ) - F_{P} (λ) ∣)^{2} \leq 4 d γ_{ϵ}^{2} j = 1 \sum d ζ \in Z \sum (q_{ζ j} - q_{ζ j})^{2} .$ Each $q_{ζ j}$ is the empirical mass of one observed atom. Its Bernoulli second moment under Assumption 1 gives $E_{P} (q_{ζ j} - q_{ζ j})^{2} = \frac{q _{ζ j} ( 1 - q _{ζ j} )}{n} \leq \frac{1}{n} .$ Consequently, $E_{P} [b \in I sup ∣ V_{b}^{JF} - V_{b} (P) ∣^{2}] \leq \frac{16 d ^{2} γ _{ϵ}^{2}}{n} .$

Because $L \leq d < 16$ , we have $d L \leq 256$ , and hence $\frac{16 d ^{2} γ _{ϵ}^{2}}{n} \leq 4096 γ_{ϵ}^{2} ρ_{n, d} .$ If $ρ_{n, d} \geq 1$ , the unit bound above is at most $C_{ϵ} min {1, ρ_{n, d}}$ . If $ρ_{n, d} < 1$ , the displayed empirical bound is at most the same quantity.

3. Alphabets with $d \geq 16$ and $d / L \leq n$ . Here $ρ_{n, d} \leq 1$ . The estimator uses the conditionally averaged threshold process $F$ specified in Algorithm 1. It is bounded on $[0, 1]$ by Lemma 8. The same dual perturbation and clipping argument bounds its curve risk by the averaged process risk: $E_{P} [b \in I sup ∣ V_{b}^{JF} - V_{b} (P) ∣^{2}] \leq E_{P} (λ \in [0, 1] sup ∣ F (λ) - F_{P} (λ) ∣)^{2} .$

Under the stated sampling and model conditions, Theorem 4 bounds the right-hand side by $C_{ϵ}^{proc} ρ_{n, d}$ . Thus the curve risk is at most $C_{ϵ}^{proc} ρ_{n, d} \leq C_{ϵ} min {1, ρ_{n, d}} .$

4. Alphabets with $d \geq 16$ and $n < d / L$ . Now $ρ_{n, d} > 1$ , and Algorithm 1 sets the entire estimated curve equal to $1/2$ . The unit bound above gives $E_{P} [b \in I sup ∣ V_{b}^{JF} - V_{b} (P) ∣^{2}] \leq 1 \leq C_{ϵ} min {1, ρ_{n, d}} .$

These cases give the claimed inequality for every $P \in M_{d, ϵ}$ , with one constant depending only on $ϵ$ . Consider the set of expected squared losses indexed by these laws. If this set is nonempty, its supremum obeys the same bound because every member does. If it is empty, define its supremum as zero; the bound then follows from $C_{ϵ} > 0$ and $ρ_{n, d} \geq 0$ . In the present model the set is nonempty: take $X$ uniform on $[d]$ , take $A$ independent of $X$ with treatment probability $1/2$ , and set $Y (0) = Y (1) = Y = 0$ almost surely. This law satisfies consistency and conditional exchangeability, and its treatment propensity in every cell is $1/2$ , as required by $0 < ϵ < 1/2$ . Thus the nonempty case gives the stated supremum bound.

∎

Proof of Theorem 4.

Write $L = lo g (e d)$ , $m = n /8$ , and $K = max {2, ⌊ L /512 ⌋}$ . We first establish estimates for an arbitrary observed categorical law in the independent pilot and evaluation count experiment of Definition 17. All constants introduced below are positive and depend at most on $ϵ$ , unless called numerical.

For each pilot realization, every point $u$ in the rectangle $\prod_{ζ \in Z} [ℓ_{ζ j}, u_{ζ j}]$ is nonnegative and satisfies $∥ u - c_{j}^{0} ∥_{1} \leq S_{j}$ . Positivity and normalization of the Jackson convolution, together with Lemma 1, therefore give the uniform bound $u \in \prod_{ζ \in Z} [ℓ_{ζ j}, u_{ζ j}] sup ∥ P_{j, \cdot} (u) - f_{\cdot} (c_{j}^{0}) ∥_{B V ([0, 1])} \leq c_{BV} S_{j} .$ Write the polynomial on this rectangle in tensor Chebyshev form, with coefficients $b_{j, ν}$ : $P_{j, λ} (u) - f_{λ} (c_{j}^{0}) = ν \in {0, \dots, D}^{4} \sum b_{j, ν} (λ) ζ \in Z \prod T_{ν_{ζ}} (\frac{u _{ζ} - c _{ζ j}^{0}}{R _{ζ j}}), D = 2 (K - 1) .$ Each coefficient is a normalized tensor Chebyshev integral of the uniformly bounded path, so $∥ b_{j, ν} ∥_{B V ([0, 1])} \leq 16 c_{BV} S_{j}$ . If $A_{h}$ is the sum of the absolute monomial coefficients of $T_{h}$ , its recurrence gives $A_{0} = A_{1} = 1$ , $A_{h + 1} \leq 2 A_{h} + A_{h - 1}$ , and hence $A_{h} \leq (1 + 2)^{h}$ . Conversion to the centered monomial coefficients of Algorithm 1 now yields $α \sum ∥ β_{j, α} ∥_{B V ([0, 1])} \leq 16 c_{BV} S_{j} (D + 1)^{4} (1 + 2)^{4 D} \leq c_{coeff} S_{j} e^{12 K} .$ The estimate holds for every pilot realization, including those outside $G_{j}$ : the pilot radii are strictly positive, and the convolution rectangle lies in $R_{+}^{4}$ . Also $L = 1 + lo g d \geq 1$ and $K \leq 2 + L /512$ . Direct expansion of this last bound yields $24 K + \frac{16 K ^{2}}{L} \leq 114 + \frac{L}{16} \leq 115 + \frac{lo g d}{16}, S_{j}^{2} e^{24 K + 16 K^{2} / L} \leq e^{115} d^{1/16} S_{j}^{2} .$ These are the two coefficient bounds required by Definition 17.

Here are the cell estimates used below. Put $a_{j} = \frac{p _{j}}{m L} + \frac{1}{m L}, v_{j} = \frac{p _{j} L}{m} + \frac{L}{m} .$ Conditioning on the pilot counts, factorial moments of the independent evaluation counts give $E [U_{h} (N_{ζ j}; c_{ζ j}^{0}) ∣ N^{'}] = (q_{ζ j} - c_{ζ j}^{0})^{h} .$ On $G_{j}$ , the localization interval contains $q_{ζ j}$ , and its radius satisfies $q_{ζ j} / (m R_{ζ j}^{2}) \leq 1/ L$ . The second factorial-moment identity is $E [U_{h} (N_{ζ j}; c_{ζ j}^{0})^{2} ∣ N^{'}] = r = 0 \sum h (r h)^{2} r! (\frac{q _{ζ j}}{m})^{r} (q_{ζ j} - c_{ζ j}^{0})^{2 h - 2 r} .$ Using $∣ q_{ζ j} - c_{ζ j}^{0} ∣ \leq R_{ζ j}$ , $q_{ζ j} / (m R_{ζ j}^{2}) \leq 1/ L$ , and $(r h)^{2} r! \leq h^{2 r} / r!$ , it gives $E [\frac{U _{h} ( N _{ζ j} ; c _{ζ j}^{0} ) ^{2}}{R _{ζ j}^{2 h}} N^{'}] \leq r = 0 \sum h \frac{( h ^{2} / L ) ^{r}}{r !} \leq e^{h^{2} / L} .$ For each factorial index $α \in {0, \dots, D}^{Z}$ , independence of the four evaluation coordinates and the preceding moment bound give, on $G_{j}$ , $E ζ \in Z \prod \frac{U _{α_{ζ}} ( N _{ζ j} ; c _{ζ j}^{0} ) ^{2}}{R _{ζ j}^{2 α_{ζ}}} N^{'} \leq exp (\frac{\sum _{ζ} α _{ζ}^{2}}{L}) \leq e^{4 D^{2} / L} .$ Cauchy–Schwarz over the $(D + 1)^{4}$ factorial indices and the coefficient envelope therefore give $E [∥ Z_{j} - f_{\cdot} (c_{j}^{0}) ∥_{B V ([0, 1])}^{2} ∣ N^{'}] \leq 4 (α \sum ∥ β_{j, α} ∥_{B V ([0, 1])})^{2} α \in {0, \dots, D}^{Z} \sum e^{4 D^{2} / L} \leq 4 c_{coeff}^{2} S_{j}^{2} (D + 1)^{4} e^{24 K + 16 K^{2} / L} .$ Here $D + 1 \leq 2 K \leq e^{K}$ . Using $K \leq 2 + L /512$ gives $28 K + \frac{16 K ^{2}}{L} \leq 122 + \frac{L}{16} = 123 + \frac{lo g d}{16}, (D + 1)^{4} e^{24 K + 16 K^{2} / L} \leq e^{123} d^{1/16} .$ Consequently the conditional squared bounded-variation norm is at most $4 c_{coeff}^{2} e^{123} d^{1/16} S_{j}^{2}$ . Every radius is positive, so $S_{j} > 0$ . Apply $∣ Π_{[- t, t]} (x) - x ∣ \leq x^{2} / t$ with $t = d^{1/4} S_{j}$ . Uniformly in $λ$ , $E [∣ T_{j} (λ) - Z_{j} (λ) ∣ ∣ N^{'}] \leq 4 c_{coeff}^{2} e^{123} S_{j} d^{- 3/16} on G_{j} .$

$E [Z_{j} (λ) ∣ N^{'}] = P_{j, λ} (q_{j}) .$ To bound its approximation error, put $δ = L / m$ . On $G_{j}$ , the vector $q_{j}$ lies in the pilot rectangle, so Lemma 3 gives $∣ P_{j, λ} (q_{j}) - f_{λ} (q_{j}) ∣ \leq 32 {3 (1 + ϵ^{- 1}) + 1} ⎩ ⎨ ⎧ \frac{1}{K} ζ \in Z \sum (q_{ζ j} - ℓ_{ζ j}) (u_{ζ j} - q_{ζ j}) + \frac{S _{j}}{K ^{2}} ⎭ ⎬ ⎫ .$ The good-pilot inequality and the truncated endpoints imply, coordinatewise, $(q_{ζ j} - ℓ_{ζ j}) (u_{ζ j} - q_{ζ j}) \leq 8 H_{0}^{2} q_{ζ j} δ .$ Indeed, when $ℓ_{ζ j} > 0$ , the product is at most $h_{ζ j}^{2}$ ; the inequalities $c_{ζ j} > h_{ζ j}$ and $∣ c_{ζ j} - q_{ζ j} ∣ \leq h_{ζ j} /4$ , inserted into the formula for $h_{ζ j}$ , give the displayed bound. When $ℓ_{ζ j} = 0$ , that formula and $c_{ζ j} \leq h_{ζ j}$ give $u_{ζ j} \leq 8 H_{0}^{2} δ$ , so the product is at most $q_{ζ j} u_{ζ j}$ . Since each $q_{ζ j} \leq p_{j}$ and there are four coordinates, $ζ \in Z \sum (q_{ζ j} - ℓ_{ζ j}) (u_{ζ j} - q_{ζ j}) \leq 4 8 H_{0}^{2} p_{j} L / m .$ Thus the approximation contribution has the asserted $p_{j} L / m / K + S_{j} / K^{2}$ scale, including when $p_{j} = 0$ . Combining it with the conditional clipping contribution gives, on $G_{j}$ ,

$λ \in [0, 1] sup ∣ E {T_{j} (λ) ∣ N^{'}} - f_{λ} (q_{j}) ∣ \leq c_{ϵ} {S_{j} d^{- 3/16} + \frac{p _{j} L / m}{K} + \frac{S _{j}}{K ^{2}}} .$ The radius definition and truncation at zero give the pointwise estimates $R_{ζ j}^{2} \leq 2 H_{0}^{2} {\frac{N _{ζ j}^{'} L}{m ^{2}} + (\frac{L}{m})^{2}}, S_{j}^{2} \leq 4 ζ \in Z \sum R_{ζ j}^{2} .$ Taking expectations and using $E N_{ζ j}^{'} = m q_{ζ j}$ and $\sum_{ζ} q_{ζ j} = p_{j}$ yields $E S_{j}^{2} \leq 8 H_{0}^{2} {\frac{p _{j} L}{m} + 4 (\frac{L}{m})^{2}} \leq 32 H_{0}^{2} v_{j}^{2} .$ This is the second-moment bound in Lemma 2; Cauchy–Schwarz also gives $E S_{j} \leq 32 H_{0} v_{j}$ .

$K^{- 1} \leq 768/ L$ and $L^{2} d^{- 3/16} \leq (35/3)^{2}$ for $d \geq 16$ . After averaging over pilots, these inequalities convert the displayed good-pilot bound to the scale $a_{j}$ .

For the complementary pilot event, put $B_{j} = ζ \in Z \sum (∣ c_{ζ j} - q_{ζ j} ∣ + h_{ζ j}) .$ Applying Lemma 4 with $t = 2$ gives the weighted second-moment estimate $E [1_{G_{j}^{c}} B_{j}^{2}] \leq 16 \cdot 1 0^{240} e^{- 20 L} v_{j}^{2} =: c_{mom} e^{- 20 L} v_{j}^{2} .$

The pilot endpoints give $∣ c_{ζ j}^{0} - c_{ζ j} ∣ \leq h_{ζ j} /2$ and $R_{ζ j} \leq h_{ζ j}$ . Clipping bounds $∣ T_{j} (λ) - f_{λ} (c_{j}^{0}) ∣$ by $d^{1/4} S_{j}$ , while Lemma 1 bounds $sup_{λ} ∣ f_{λ} (c_{j}^{0}) - f_{λ} (q_{j}) ∣$ by $c_{BV} ∥ c_{j}^{0} - q_{j} ∥_{1}$ . Hence, on $G_{j}^{c}$ , $λ \in [0, 1] sup ∣ T_{j} (λ) - f_{λ} (q_{j}) ∣ \leq (c_{BV} + d^{1/4}) ζ \in Z \sum (∣ c_{ζ j} - q_{ζ j} ∣ + h_{ζ j}) .$ Since $d^{1/4} \geq 1$ , taking square roots yields, for a positive $c_{env}$ , $1_{G_{j}^{c}} λ \in [0, 1] sup ∣ T_{j} (λ) - f_{λ} (q_{j}) ∣_{L_{2}} \leq c_{env} d^{1/4} e^{- 10 L} v_{j} .$ Splitting the expectation over $G_{j}$ and $G_{j}^{c}$ , and using the preceding conditional and bad-event bounds, gives a positive $c_{bias}$ such that $λ \in [0, 1] sup ∣ E T_{j} (λ) - f_{λ} (q_{j}) ∣ \leq c_{bias} a_{j} .$ In particular, the exponentially weighted bad-event contribution is absorbed at this scale because $v_{j} \leq L^{2} a_{j}$ and $d^{1/4} e^{- 10 L} L^{2}$ is bounded for $d \geq 16$ .

Define the good- and bad-pilot error paths by $W_{j}^{good} (λ) = 1_{G_{j}} {T_{j} (λ) - f_{λ} (q_{j})}, W_{j}^{bad} (λ) = 1_{G_{j}^{c}} {T_{j} (λ) - f_{λ} (q_{j})} .$ The pilot and evaluation counts are independent across cells. On $G_{j}$ , clipping is one-Lipschitz and cannot increase total variation. The preceding conditional factorial-moment bound, the coefficient envelope, and Lemma 1 therefore give $E [∥ W_{j}^{good} ∥_{B V ([0, 1])}^{2} ∣ N^{'}] \leq c 1_{G_{j}} d^{1/16} S_{j}^{2} .$ Indeed, the clipped factorial path has squared bounded-variation norm at most a constant times $d^{1/16} S_{j}^{2}$ ; its correction from the pilot center to $q_{j}$ has bounded-variation norm at most $c_{ϵ} S_{j}$ , since $q_{j}$ lies in the pilot rectangle. The second-moment calculation above gives $E S_{j}^{2} \leq 32 H_{0}^{2} v_{j}^{2}$ . Consequently, $E ∥ W_{j}^{good} ∥_{B V ([0, 1])}^{2} \leq c d^{1/16} v_{j}^{2} .$ The paths are independent across cells, continuous, and have the finite variation and second moments established above. By Lemma 5, and because $∥ W_{j}^{good} ∥_{\infty} + TV (W_{j}^{good}) \leq 2∥ W_{j}^{good} ∥_{B V ([0, 1])}$ , $E j \sum (W_{j}^{good} - E W_{j}^{good})_{\infty}^{2} \leq 16384 j \sum E [(∥ W_{j}^{good} ∥_{\infty} + TV (W_{j}^{good}))^{2}] \leq 65536 j \sum E ∥ W_{j}^{good} ∥_{B V ([0, 1])}^{2} \leq c d^{1/16} (\frac{2 L}{m} + 2 d \frac{L ^{2}}{m ^{2}}) .$ The last scale follows from $\sum_{j} p_{j} = 1$ and $\sum_{j} v_{j}^{2} \leq 2 L / m + 2 d (L / m)^{2}$ . On the branch $d / L \leq n = 8 m$ , the inequalities $L \leq 17 d^{1/16}$ and $d / m \leq 8 L$ turn the last display into $E j \sum (W_{j}^{good} - E W_{j}^{good})_{\infty}^{2} \leq c_{good} \frac{d}{m L} .$

For the bad-pilot paths, centering, the triangle inequality, and Cauchy–Schwarz give $E j \sum (W_{j}^{bad} - E W_{j}^{bad})_{\infty}^{2} \leq 4 d j \sum E ∥ W_{j}^{bad} ∥_{\infty}^{2} \leq c d^{3/2} e^{- 20 L} (\frac{2 L}{m} + 2 d \frac{L ^{2}}{m ^{2}}) .$ Here $L \leq d$ , $d L / m \leq 8 L^{2}$ , and $d^{1/2} e^{- 20 L} \leq d^{- 4}$ . They absorb the remaining factors and give a positive $c_{bad}$ with $E j \sum (W_{j}^{bad} - E W_{j}^{bad})_{\infty}^{2} \leq c_{bad} \frac{d}{m L} .$

It remains to combine the centered terms with their mean. Define $b = c_{bias} j \sum a_{j} .$ The good and bad error paths partition $\sum_{j} (T_{j} - f_{\cdot} (q_{j}))$ , so the absolute value of its mean at every $λ$ is at most $b$ . Since $\sum_{j} p_{j} = 1$ , Cauchy–Schwarz and $d / (n L) \leq 1$ give $b^{2} \leq 144 c_{bias}^{2} \frac{d}{n L} .$ Applying $(x + y + z)^{2} \leq 3 (x^{2} + y^{2} + z^{2})$ to the centered good path, centered bad path, and mean, then using $m = n /8$ , proves $E_{id} j \sum T_{j} - F_{P}_{\infty}^{2} \leq Γ_{id} \frac{d}{n L}, Γ_{id} = 24 c_{good} + 24 c_{bad} + 432 c_{bias}^{2} .$

For the averaged process of Algorithm 1, define the nonnegative count-table function $G (N^{'}, N) = j \sum T_{j} (\cdot; N^{'}, N) - F_{P}_{\infty}^{2} .$ Its ideal expectation is finite by the preceding process bound. Conditional Jensen bounds the averaged-process risk by the capped auxiliary risk. Apply Lemma 6 to $G$ ; in the uncapped marked-Poisson experiment, $M$ is the total number of marked records, and the count-table marginal is the ideal law. Hence $E_{O, aux} [1_{{M \leq n}} G (N^{'}, N)] = E_{uncap} [1_{{M \leq n}} G (N^{'}, N)] \leq E_{id} G (N^{'}, N) .$ On $M > n$ , the auxiliary process is zero; $0 \leq f_{λ} (q_{j}) \leq p_{j}$ implies $∥ F_{P} ∥_{\infty} \leq 1$ . The Poisson cap-tail bound therefore gives $E ∥ F - F_{P} ∥_{\infty}^{2} \leq E_{O, aux} ∥ F^{cap} - F_{P} ∥_{\infty}^{2} = E_{O, aux} [1_{{M \leq n}} G (N^{'}, N)] + Pr (M > n) ∥ F_{P} ∥_{\infty}^{2} \leq E_{id} j \sum T_{j} - F_{P}_{\infty}^{2} + e^{- n /16} .$ The elementary bounds $e^{- n /16} \leq 16/ n$ and $L = 1 + lo g d \leq d$ show that $e^{- n /16} \leq 16 d / (n L)$ . Hence $E ∥ F - F_{P} ∥_{\infty}^{2} \leq (Γ_{id} + 16) \frac{d}{n L} .$ Under Assumption 1, the product law used in this expectation is the law of the observed sample.

Choose one constant larger than every coefficient used above; for example, with the cap-transfer coefficient written $c_{cap} = 1$ , take $C_{ϵ} = 1 + c_{coeff} + e^{115} + 8 c_{bias} + 8 c_{good} + c_{env} + c_{bad} + Γ_{id} + c_{cap} (Γ_{id} + 16) .$ All terms are nonnegative, so $C_{ϵ} > 0$ . The five estimates established for arbitrary observed categorical laws and every pilot realization give $C_{ϵ} \in H_{n, d}$ as defined in Definition 17.

Finally, take the observed margin of the full-data law $P \in M_{d, ϵ}$ from Definition 4. Summing its four observed category masses in cell $j$ gives the same covariate mass $p_{j}$ as summing the corresponding full-data masses. Moreover, $\frac{p _{j}}{m L} + \frac{1}{m L} = \frac{8 p _{j}}{n L} + \frac{8}{n L} \leq 8 {\frac{p _{j}}{n L} + \frac{1}{n L}}, \frac{d}{m L} = 8 \frac{d}{n L} .$ Thus the common choice $C_{ϵ}$ gives the stated $n L$ -scale cell-bias and good-pilot bounds, the stated $m L$ -scale bad-pilot bound, the cellwise bad-pilot envelope, and both process-risk bounds simultaneously.

∎

Proof of Proposition 3.

Fix a paired completion $P$ with parameters $r, θ$ . By Definition 18, each cell $(i, σ)$ , where $σ \in {+ 1, - 1}$ , has mass $p_{i, σ} = r_{i} /2$ , treatment propensity $1/2$ when occupied, and weighted outcome means $p_{i, σ} μ_{0, i, σ} = \frac{r _{i}}{2} \frac{1}{4}, p_{i, σ} μ_{1, i, σ} = \frac{r _{i}}{2} (\frac{1}{2} + σ θ_{i}) .$ These identities also hold when $r_{i} = 0$ . The paired completion satisfies consistency and conditional exchangeability. Since $k \geq 1$ , its alphabet has at least two cells; since $0 < ϵ < 1/2$ , propensity $1/2$ satisfies overlap on every occupied cell. Thus $P \in M_{2 k, ϵ}$ by Definition 4. On an occupied cell, division by $p_{i, σ} > 0$ gives $τ_{i, σ} = μ_{1, i, σ} - μ_{0, i, σ} = \frac{1}{4} + σ θ_{i} \in [\frac{1}{8}, \frac{3}{8}] .$

Summing the weighted control means and using $\sum_{i} r_{i} = 1$ gives $B (P) = i, σ \sum p_{i, σ} μ_{0, i, σ} = \frac{1}{4} .$ Choose the policy that treats the $+$ cell when $θ_{i} \geq 0$ and the $-$ cell when $θ_{i} < 0$ : $π_{i, +}^{⋆} = 1 {θ_{i} \geq 0}, π_{i, -}^{⋆} = 1 {θ_{i} < 0} .$ It selects exactly one cell per pair, including at a tie. Consequently, $i, σ \sum p_{i, σ} π_{i, σ}^{⋆} = i \sum \frac{r _{i}}{2} = \frac{1}{2}, B (P) + i, σ \sum p_{i, σ} π_{i, σ}^{⋆} τ_{i, σ} = \frac{3}{8} + \frac{1}{2} i \sum r_{i} ∣ θ_{i} ∣.$

To bound the value above, every $π \in Π_{b} (P)$ and every $λ \geq 0$ satisfy $j \sum p_{j} π_{j} τ_{j} \leq bλ + j \sum p_{j} [τ_{j} - λ]_{+} .$ Indeed, $p_{j} π_{j} (τ_{j} - λ) \leq p_{j} [τ_{j} - λ]_{+}$ cell by cell, while $λ \sum_{j} p_{j} π_{j} \leq bλ$ . This bound also makes the feasible gains bounded above in the supremum defining $V_{b} (P)$ .

For the observed margin of $P$ , the arm mass in an occupied cell is $p_{j} /2$ . Hence the stabilized contributions in Definition 12 equal $p_{j} μ_{aj}$ . In a null cell all four observed masses vanish, so $q_{j} = 0$ . To specify the quotient at this point, interpret $g_{a}$ by its zero-mass extension: $g_{a} (0) = 0$ for each arm $a$ . The formula in Definition 12 then gives $f_{1/4} (0) = 0$ . At $λ = 1/4$ , this yields $F_{P} (\frac{1}{4}) = B (P) + j \sum p_{j} [τ_{j} - \frac{1}{4}]_{+} = \frac{1}{4} + \frac{1}{2} i \sum r_{i} ([θ_{i}]_{+} + [- θ_{i}]_{+}) = \frac{1}{4} + \frac{1}{2} i \sum r_{i} ∣ θ_{i} ∣.$ Applying the preceding bound at $b = 1/2$ and $λ = 1/4$ , and then using the feasible policy $π^{⋆}$ for the reverse inequality, gives $V_{1/2} (P) = \frac{3}{8} + \frac{1}{2} i \sum r_{i} ∣ θ_{i} ∣ = \frac{1}{8} + F_{P} (\frac{1}{4}) = B (P) + j \sum p_{j} π_{j}^{⋆} τ_{j} .$ Thus $π^{⋆}$ attains the half-population value while using treatment mass exactly $1/2$ .

At budget one, treating every cell is feasible. Every occupied-cell effect is positive, so no feasible policy has greater gain. The weighted treated means cancel pairwise: $V_{1} (P) = i = 1 \sum k \frac{r _{i}}{2} [(\frac{1}{2} + θ_{i}) + (\frac{1}{2} - θ_{i})] = \frac{1}{2} .$

For the sample reduction, fix $R, S \in Δ_{k}$ and define $r, θ$ as in the statement. Nonnegativity and the simplex equalities for $R, S$ give $r \in Δ_{k}$ . If $R_{i} + S_{i} > 0$ , then $∣ R_{i} - S_{i} ∣ \leq R_{i} + S_{i}$ , so $∣ θ_{i} ∣ \leq 1/8$ ; when the sum is zero, $θ_{i} = 0$ . Thus $θ$ is an admissible contrast vector. The construction in Definition 18 supplies a paired law with these parameters. Moreover, for every $i$ , including a zero-mass pair, $r_{i} θ_{i} = \frac{R _{i} - S _{i}}{16} .$

Here is a kernel that depends on the input records but not on $R, S$ . Denote the two independent input samples by $(ξ_{t})_{t = 1}^{n} \sim R^{\otimes n}, (η_{t})_{t = 1}^{n} \sim S^{\otimes n}, (ξ_{t})_{t = 1}^{n} ⊥ (η_{t})_{t = 1}^{n} .$ Pair their labels coordinatewise as $(ξ_{t}, η_{t})$ , $1 \leq t \leq n$ . Independently across coordinates, choose $ξ_{t}$ or $η_{t}$ with equal probability to obtain a label, choose a uniform sign $σ$ , and choose an independent fair treatment indicator $a$ . Conditional on these choices, generate a Bernoulli outcome with parameter $1/4$ if $a = 0$ , with parameter $1/2 + σ /8$ if $a = 1$ and the chosen label came from $ξ_{t}$ , and with parameter $1/2 - σ /8$ if it came from $η_{t}$ . At $n = 0$ , the kernel assigns probability one to the empty output sequence.

For clarity, define the Bernoulli atom mass and the two outcome parameters, for $y, a \in {0, 1}$ and $σ \in {+ 1, - 1}$ , by $Ber_{ρ} (y) = {1 - ρ, ρ, y = 0, y = 1, (0 \leq ρ \leq 1), ν_{a, σ}^{\pm} = {\frac{1}{4}, \frac{1}{2} \pm \frac{σ}{8}, a = 0, a = 1.$ The conditional mass of one output record is therefore $Pr {O_{t} = ((i, σ), a, y) ∣ ξ_{t}, η_{t}} = \frac{1 { ξ _{t} = i } Ber _{ν_{a, σ}^{+}} ( y ) + 1 { η _{t} = i } Ber _{ν_{a, σ}^{-}} ( y )}{8} .$ The factors $1/8$ come from the three fair choices. Summing over labels, signs, treatments, and outcomes gives one, so this specifies a probability kernel.

Mixing this conditional mass over the independent input labels gives $Pr {O_{t} = ((i, σ), a, y)} = \frac{R _{i} Ber _{ν_{a, σ}^{+}} ( y ) + S _{i} Ber _{ν_{a, σ}^{-}} ( y )}{8} = \frac{r _{i}}{4} Ber_{μ_{a, i, σ}} (y), μ_{a, i, σ} = {\frac{1}{4}, \frac{1}{2} + σ θ_{i}, a = 0, a = 1.$ For $a = 0$ , the second equality uses $r_{i} = (R_{i} + S_{i}) /2$ . For $a = 1$ , it also uses $r_{i} θ_{i} = (R_{i} - S_{i}) /16$ and the fact that Bernoulli atom masses are affine in their parameter. The equality covers zero-mass pairs as both sides then vanish. Its right-hand side is exactly the observed atom mass of the paired law in Definition 18.

Finally, the input pairs and the kernel randomizations are independent across $t$ . Thus, for every output sequence $o_{t} = ((i_{t}, σ_{t}), a_{t}, y_{t})$ , $1 \leq t \leq n$ , $Pr {O_{1} = o_{1}, \dots, O_{n} = o_{n}} = t = 1 \prod n \frac{r _{i_{t}}}{4} Ber_{μ_{a_{t}, i_{t}, σ_{t}}} (y_{t}),$ the product law of $n$ observed records from that paired law. The empty product gives the same conclusion when $n = 0$ .

∎

References

Feng, Kai and Hong, Han and Nekipelov, Denis (2026). Statistical inference of optimal allocations I: Regularities and their implications. Journal of Econometrics. doi
Bhattacharya, Debopam and Dupas, Pascaline (2012). Inferring welfare maximizing treatment assignment under budget constraints. Journal of Econometrics. doi
Jiao, Jiantao and Venkat, Kartik and Han, Yanjun and Weissman, Tsachy (2015). Minimax estimation of functionals of discrete distributions. IEEE Transactions on Information Theory. doi
Jiao, Jiantao and Han, Yanjun and Weissman, Tsachy (2018). Minimax estimation of the {$L_1$} distance. IEEE Transactions on Information Theory. 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
Sverdrup, Erik and Wu, Han and Athey, Susan and Wager, Stefan (2025). {Qini} curves for multi-armed treatment rules. Journal of Computational and Graphical Statistics. doi
Luedtke, Alexander R. and van der Laan, Mark J. (2016). Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy. The Annals of Statistics. doi
Firpo, Sergio and Galvao, Antonio F. and Parker, Thomas (2023). Uniform inference for value functions. Journal of Econometrics. doi
Kitagawa, Toru and Tetenov, Aleksey (2018). Who should be treated? Empirical welfare maximization methods for treatment choice. Econometrica. doi
Athey, Susan and Wager, Stefan (2021). Policy learning with observational data. Econometrica. doi
Rosenbaum, Paul R. and Rubin, Donald B. (1983). The central role of the propensity score in observational studies for causal effects. Biometrika. doi
van der Vaart, Aad W. (1998). Asymptotic Statistics. Cambridge University Press. doi
{CausalSmith} (2026). Minimax estimation of optimal treatment values with discrete covariates. . doi
Hirano, Keisuke and Porter, Jack R. (2009). Asymptotics for statistical treatment rules. Econometrica. doi
Pellatt, Daniel F. (2023). {PAC}-Bayesian treatment allocation under budget constraints. . arXiv
Hern{\'a}n, Miguel A. and Robins, James M. (2020). Causal Inference: What If. Chapman and Hall/CRC.

Formal layer — Lean correspondence

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

Setups (3)

Setup S-1 — Independent sampling of $n$ observed records $O_i=(X_i,A_i,Y_i)\in[d]\times\{0,1\}^2$ from a finite observed law, described by its cell four-mass vectors $q_j\in\mathbb R_+^4$ , with cell masses $p_j$ , propensities $e_j$ , fixed overlap constant $\epsilon\in(0,1/2)$ , budget interval $I=[b_0,1-b_0]$ , shadow price $\lambda\in[0,1]$ , threshold cell functional $f_\lambda(u)$ built from $s_a(u),s(u),g_a(u)$ , dual process $F_P(\lambda)$ , and the Jackson--factorial estimator with tuning $H_0=4096,\kappa=1/512,D_0=16$ .
Setup S-2 — A full-data causal law $P$ of $(X,A,Y(0),Y(1))$ on $[d]\times\{0,1\}^3$ with observed outcome $Y$ , cell potential-outcome means $\mu_{aj}$ , effects $\tau_j$ , control value $B(P)$ , randomized policies $\pi\in[0,1]^d$ , budget-feasible class $\Pi_b(P)$ , oracle value $V_b(P)$ and curve $V(P)$ , model class $\mathcal M_{d,\epsilon}$ , and the all-procedure squared-supremum minimax risk $\mathfrak R^{\mathrm{curve}}_{n,d,\epsilon,b_0}$ .
Setup S-3 — The paired lower-bound experiment: $k$ cell pairs indexed by $i$ and sign $\sigma\in\{-1,+1\}$ , pair masses $r\in\Delta_k$ , contrasts $\theta\in[-1/8,1/8]^k$ , the family $\mathcal P^{\mathrm{pair}}_k\subset\mathcal M_{2k,\epsilon}$ , and the normalized two-sample $L_1$ experiment with $n$ independent draws from each of $R,S\in\Delta_k$ .

Definitions (8)

Definition P-1 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.CausalModelClass \mathcal M_{d,\epsilon}=\{P: X\in[d],\ A,Y(0),Y(1)\in\{0,1\},\ P\text{ satisfies }\mathrm{ass:consistency},\mathrm{ass:conditional\mbox{-}exchangeability},\mathrm{ass:overlap}\}, for each integer $d\ge2$ .
Definition P-2 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.budgetPolicyClass $\Pi_b(P)=\{\pi\in[0,1]^d:\sum_{j=1}^d p_j\pi_j\le b\}$ .
Definition P-3 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.budgetValue $V_b(P)=B(P)+\max_{\pi\in\Pi_b(P)}\sum_{j=1}^d p_j\pi_j\tau_j$ and $V(P)=(V_b(P):b\in I)$ .
Definition P-4 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.dualProcess For $u\in\mathbb R_+^4$ , set $g_a(u)=s(u)u_{a1}/\max\{s_a(u),\epsilon s(u)\}$ , with the quotient equal to zero when all four coordinates of $u$ vanish; set $f_\lambda(u)=g_0(u)+[g_1(u)-g_0(u)-\lambda s(u)]_+$ and $F_P(\lambda)=\sum_{j=1}^d f_\lambda(q_j)$ .
Definition P-5 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.curveMinimaxRisk For $b_0\in[0,1/2]$ , let $I=[b_0,1-b_0]$ and define $\mathfrak R_{n,d,\epsilon,b_0}^{\mathrm{curve}}=\inf_{\widehat V}\sup_{P\in\mathcal M_{d,\epsilon}}E_P[\sup_{b\in I}|\widehat V_b(O^{(n)})-V_b(P)|^2]$ , where the infimum is over all measurable maps into bounded functions on $I$ .
Definition P-6 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.jfEstimator Set $H_0=4096$ , $\kappa=1/512$ , $D_0=16$ , $L=\log(ed)$ , $m=n/8$ , and $K=\max\{2,\lfloor L/512\rfloor\}$ . Write $\mathcal Z=\{0,1\}^2$ , with $\zeta=(a,y)$ . If $d<16$ , set $\widehat q_{\zeta j}=\frac1n\sum_{i=1}^n \mathbf 1\{X_i=j,(A_i,Y_i)=\zeta\},\qquad \widehat F(\lambda)=\sum_{j=1}^d f_\lambda(\widehat q_j).$ If $d\geq16$ and $n<d/L$ , define $\widehat V_b^{\mathrm{JF}}=1/2$ for every $b\in I$ . In the remaining case $d\geq16$ and $n\geq d/L$ , independently of $O^{(n)}$ , draw $M\sim\operatorname{Pois}(n/4)$ . On $\{M>n\}$ , set the entire auxiliary threshold process $\widetilde F^{\mathrm{cap}}(\lambda)=0$ for every $\lambda\in[0,1]$ . On $\{M\leq n\}$ , uniformly permute the $n$ records, retain the first $M$ , and independently mark each retained record pilot or evaluation with probability $1/2$ each. Let $N'_{\zeta j}$ and $N_{\zeta j}$ be the resulting pilot and evaluation counts. For each $j$ and $\zeta$ , put $\delta=\frac Lm,\quad c_{\zeta j}=\frac{N'_{\zeta j}}m,\quad h_{\zeta j}=4096\{\sqrt{c_{\zeta j}\delta}+\delta\},$ $\ell_{\zeta j}=\max\{0,c_{\zeta j}-h_{\zeta j}\},\quad u_{\zeta j}=c_{\zeta j}+h_{\zeta j},\quad c^0_{\zeta j}=\frac{\ell_{\zeta j}+u_{\zeta j}}2,\quad R_{\zeta j}=\frac{u_{\zeta j}-\ell_{\zeta j}}2, \quad S_j=\sum_{\zeta\in\mathcal Z}R_{\zeta j}.$ All radii are strictly positive. Define the normalized positive order-four Jackson kernel $J_K(t)=C_K\left\{\frac{\sin(Kt/2)}{\sin(t/2)}\right\}^{4}, \qquad -\pi\leq t\leq\pi,qquad \int_{-\pi}^{\pi}J_K(t)\,dt=1,$ where the quotient has its continuous value at zero and $C_K$ is the unique positive normalizing constant. With $D=2(K-1)$ , define the unique tensor polynomial $P_{j,\lambda}$ , of coordinatewise degree at most $D$ , by $P_{j,\lambda}(c_j^0+R_j\odot\cos\vartheta) =\int_{[-\pi,\pi]^4} f_\lambda(c_j^0+R_j\odot\cos(\vartheta+t)) \prod_{\zeta\in\mathcal Z}J_K(t_\zeta)\,dt,$ and take its unique monomial expansion $P_{j,\lambda}(u)-f_\lambda(c_j^0) =\sum_{\alpha\in\{0,\ldots,D\}^4} \beta_{j,\alpha}(\lambda) \prod_{\zeta\in\mathcal Z} \left(\frac{u_\zeta-c^0_{\zeta j}}{R_{\zeta j}}\right)^{\alpha_\zeta}.$ For $h\geq0$ , set $U_h(N;z)=\sum_{t=0}^h {h\choose t}(-z)^{h-t}\frac{(N)_t}{m^t}, \qquad (N)_t=N(N-1)\cdots(N-t+1),\qquad (N)_0=1,$ and define $Z_j(\lambda)=f_\lambda(c_j^0)+ \sum_{\alpha\in\{0,\ldots,D\}^4}\beta_{j,\alpha}(\lambda) \prod_{\zeta\in\mathcal Z} \frac{U_{\alpha_\zeta}(N_{\zeta j};c^0_{\zeta j})} {R_{\zeta j}^{\alpha_\zeta}},$ $T_j(\lambda)=f_\lambda(c_j^0)+ \Pi_{[-d^{1/4}S_j,d^{1/4}S_j]} \{Z_j(\lambda)-f_\lambda(c_j^0)\}, \qquad \widetilde F^{\mathrm{cap}}(\lambda)=\sum_{j=1}^dT_j(\lambda) \quad\text{on }\{M\leq n\}.$ Here $\Pi_{[r,s]}(x)=\min\{s,\max\{r,x\}\}$ . In the Jackson--factorial branch, average the threshold process before performing the dual minimization: $\widehat F(\lambda)=E\{\widetilde F^{\mathrm{cap}}(\lambda)\mid O^{(n)}\}.$ In both the empirical and Jackson--factorial branches, report $\widehat V_b^{\mathrm{JF}} =\Pi_{[0,1]}\left(\min_{0\leq\lambda\leq1} \{b\lambda+\widehat F(\lambda)\}\right),\qquad b\in I.$ The reported quantity is the minimum value and therefore requires no optimizer selection. If an implementation stores an optimizer, it stores the least element of the nonempty compact argmin set. These branch rules, the zero process on $\{M>n\}$ , and the least-minimizer convention apply also under every data or treatment-effect tie.
Definition P-7 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.processHandle For fixed $0<\epsilon<1/2$ , the common-polynomial process handle $\mathsf H_\epsilon$ for the single pilot-local Jackson polynomial and clipping rule in $\widehat V^{\mathrm{JF}}$ is the set of candidate constants $C>0$ . Membership requires the following five groups of bounds simultaneously for every $n,d$ in the Jackson--factorial branch, every observed categorical law $P$ on the known $d$ -cell alphabet, every pilot realization, every cell $j$ , and every $\lambda\in[0,1]$ . Thus the definition gives a uniform membership criterion; it does not assert that a candidate exists. Nonemptiness is proved in \mathrm{thm:integrated\mbox{-}process\mbox{-}certificate}, which chooses one $C_\epsilon$ depending only on $\epsilon$ . Set $L=\log(ed)$ , $m=n/8$ , $K=\max\{2,\lfloor L/512\rfloor\}$ , $S_j=\sum_{\zeta\in\mathcal Z}R_{\zeta j}$ , and $v_j=\sqrt{p_jL/m}+L/m$ . For all expectations and $L_2$ norms in these five groups, use the ideal uncapped marked--Poisson experiment of proof (1), in which the pilot and evaluation counts $N'_{\zeta j},N_{\zeta j}\sim\operatorname{Pois}(m q_{\zeta j})$ are mutually independent; the executable capped experiment is used only in the final transfer to $\widetilde F^{\mathrm{cap}}$ . Define the quarter-halfwidth pilot event by $G_j=\bigcap_{\zeta\in\mathcal Z}\{|c_{\zeta j}-q_{\zeta j}|\leq h_{\zeta j}/4\}$ , and use the convention $\|h\|_{BV([0,1])}=|h(0)|+\operatorname{TV}_{[0,1]}(h)$ . Use the clipped path $T_j$ , coefficient array $\beta_{j,\alpha}$ , and pilot radii $R_{\zeta j}$ from the estimator, evaluated in that uncapped experiment. Membership of $C$ means: $\sum_\alpha\|\beta_{j,\alpha}\|_{BV([0,1])}\leq C S_j e^{12K},\qquad S_j^2 e^{24K+16K^2/L}\leq C d^{1/16}S_j^2;$ $E\left\|\sum_{j=1}^d\left[\mathbf1_{G_j}\{T_j-f_\cdot(q_j)\}-E\mathbf1_{G_j}\{T_j-f_\cdot(q_j)\}\right]\right\|_\infty^2\leq C\frac d{mL};$ $\sup_{0\leq\lambda\leq1}|ET_j(\lambda)-f_\lambda(q_j)|\leq C\left\{\sqrt{\frac{p_j}{mL}}+\frac1{mL}\right\};$ $\left\|\mathbf1_{G_j^c}\sup_{0\leq\lambda\leq1}|T_j(\lambda)-f_\lambda(q_j)|\right\|_{L_2}\leq C d^{1/4}e^{-10L}v_j;$ $E\left\|\sum_{j=1}^d\left[\mathbf1_{G_j^c}\{T_j-f_\cdot(q_j)\}-E\mathbf1_{G_j^c}\{T_j-f_\cdot(q_j)\}\right]\right\|_\infty^2\leq C\frac d{mL}.$ The first group is the coefficient envelope (14) and deterministic exponential absorption (20), obtained in the proof using the conditional factorial moment (19); the remaining groups are proof (33), (27), (28), and (34). The two bad-pilot groups are distinct: (28) is an uncentered per-cell $L_2$ supremum envelope, whereas (34) is a centered aggregate squared risk. The handle uses the same polynomial and numerical tuning as the estimator and targets the shadow-price process formed by summing cellwise errors relative to $f_\lambda(q_j)$ .
Definition P-8 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedFamily For $k\ge1$ , choose $r=(r_1,\ldots,r_k)$ in the simplex and $\theta_i\in[-1/8,1/8]$ . Create cells $(i,+),(i,-)$ of masses $r_i/2$ , set $e_{i,\sigma}=1/2$ , $\mu_{0,i,\sigma}=1/4$ , and $\mu_{1,i,\sigma}=1/2+\sigma\theta_i$ . The family of causal completions generated independently of $A$ given $X$ is $\mathcal P^{\mathrm{pair}}_k$ .

Assumptions (4)

Assumption A-1 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.IidSampling The records $O_1,\ldots,O_n$ are independent and identically distributed under the observed margin of $P$ .
Assumption A-2 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.Consistency $Y=Y(A)$ almost surely.
Assumption A-3 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.ConditionalExchangeability $(Y(0),Y(1))\perp A\mid X$ under $P$ .
Assumption A-4 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.Overlap For every $j\in[d]$ with $p_j>0$ , $\epsilon\le e_j\le1-\epsilon$ .

Lemmas (9)

Lemma L-1 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.thresholdFun_bv_lipschitz There is $C_\epsilon<\infty$ such that for all $u,v\in\mathbb R_+^4$ , $\|f_{\cdot}(u)-f_{\cdot}(v)\|_{BV([0,1])}\le C_\epsilon\|u-v\|_1$ , where $\|h\|_{BV}=|h(0)|+\operatorname{TV}_{[0,1]}(h)$ .
Lemma L-2 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.two_sample_l1_lower There is a universal constant $c>0$ such that, for every $k\geq2$ and $1\leq n\leq k^2$ , the experiment consisting of $n$ independent observations from each of $R,S\in\Delta_k$ satisfies $\inf_{\widehat L}\sup_{R,S\in\Delta_k} E_{R,S}\bigl[(\widehat L-\|R-S\|_1)^2\bigr] \geq c\min\left\{1,\frac{k}{n\log(ek)}\right\}.$
Lemma lem:empirical-threshold-process-bounded verified CausalSmith.Stat.DiscreteBudgetvalueCurve.empiricalThresholdProcess_bounded Let $\epsilon\in\mathbb R$ , $n,d\in\mathbb N$ , and fix any observed sample $O^{(n)}$ . The empirical threshold process of def:jf-estimator, $\widehat F(\lambda)=\sum_{j=1}^d f_\lambda(\widehat q_j)$ with $f_\lambda$ as in def:dual-process, is bounded on $[0,1]$ : there is a finite $B$ (depending on the sample) such that $|\widehat F(\lambda)|\leq B$ for every $\lambda\in[0,1]$ .
Lemma lem:averaged-threshold-process-bounded verified CausalSmith.Stat.DiscreteBudgetvalueCurve.averagedThresholdProcess_bounded Let $\epsilon>0$ , $n\geq1$ , and $d\geq1$ , and fix any observed sample $O^{(n)}$ . The conditionally averaged threshold process of def:jf-estimator, obtained by averaging the capped auxiliary process $\widetilde F^{\mathrm{cap}}(\lambda)$ over $M\sim\operatorname{Pois}(n/4)$ , the uniform record permutation, and the pilot/evaluation marks given $O^{(n)}$ , is bounded on $[0,1]$ : there is a finite $B$ (depending on the sample) such that $|\widehat F(\lambda)|\leq B$ for every $\lambda\in[0,1]$ .
Lemma lem:pilot-radius-second-moment verified CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRadius_sum_sq_integral_le_cellScale Let $n\geq1$ , $d\geq16$ , $m=n/8$ , $L=\log(ed)$ , $H_0=4096$ , let $P$ be an observed categorical law on the $d$ -cell alphabet with category-cell masses $q_{\zeta j}$ and cell masses $p_j=\sum_{\zeta\in\mathcal Z}q_{\zeta j}$ , and fix a cell $j$ . In the ideal uncapped experiment in which the pilot counts $N'_{\zeta j}\sim\operatorname{Pois}(mq_{\zeta j})$ are independent, let $S_j=\sum_{\zeta\in\mathcal Z}R_{\zeta j}$ be the sum of the four pilot radii of def:jf-estimator, and let $v_j=\sqrt{p_jL/m}+L/m$ as in def:process-handle. Then $S_j^2$ is integrable and $\mathbb E\,S_j^2\leq 32H_0^2\,v_j^2 .$
Lemma lem:jackson-boundary-adaptive verified CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_boundary_adaptive Fix $\epsilon>0$ , $\lambda\in[0,1]$ , and an integer $K\geq1$ , and put $D=2(K-1)$ . Let $c^0,R\in\mathbb R^{\mathcal Z}$ satisfy $R_\zeta>0$ and $c^0_\zeta-R_\zeta\geq0$ for every $\zeta\in\mathcal Z$ , so that the rectangle $\prod_{\zeta\in\mathcal Z}[c^0_\zeta-R_\zeta,c^0_\zeta+R_\zeta]$ lies in $\mathbb R_+^4$ . Let $P_\lambda$ be the tensor polynomial of coordinatewise degree at most $D$ defined from $f_\lambda$ of def:dual-process by the normalized order-four Jackson convolution on this rectangle, exactly as $P_{j,\lambda}$ is defined in def:jf-estimator with the pilot center $c_j^0$ and radii $R_j$ replaced by $c^0$ and $R$ . Then, for every $y\in\mathbb R^{\mathcal Z}$ with $|y_\zeta-c^0_\zeta|\leq R_\zeta$ for all $\zeta\in\mathcal Z$ , $|P_\lambda(y)-f_\lambda(y)| \leq32\{3(1+\epsilon^{-1})+1\} \sum_{\zeta\in\mathcal Z}\left\{ \frac{\sqrt{(y_\zeta-c^0_\zeta+R_\zeta)(c^0_\zeta+R_\zeta-y_\zeta)}}{K} +\frac{R_\zeta}{K^2}\right\}.$
Lemma lem:pilot-bad-score-moment verified CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotCell_empiricalBadScore_moment Let $n\geq1$ , $d\geq1$ , $m=n/8$ , $L=\log(ed)$ , and $H_0=4096$ . Let $P$ be an observed categorical law on the $d$ -cell alphabet with category-cell masses $q_{\zeta j}$ and cell masses $p_j=\sum_{\zeta\in\mathcal Z}q_{\zeta j}$ , and fix a cell $j$ . Suppose the four pilot counts $N'_{\zeta j}$ , $\zeta\in\mathcal Z$ , are independent with $N'_{\zeta j}\sim\operatorname{Pois}(mq_{\zeta j})$ . Form $c_{\zeta j}$ and $h_{\zeta j}$ from these counts as in def:jf-estimator, let $G_j$ be the quarter-halfwidth pilot event and $v_j=\sqrt{p_jL/m}+L/m$ the pilot-error scale of def:process-handle, and put $B_j=\sum_{\zeta\in\mathcal Z}\bigl(|c_{\zeta j}-q_{\zeta j}|+h_{\zeta j}\bigr).$ Then, for each $t\in\{1,2,4\}$ , $\mathbb E\bigl[\mathbf 1_{G_j^c}B_j^{\,t}\bigr] \leq4^t\,10^{80(t+1)}\,e^{-20L}\,v_j^{\,t}.$
Lemma lem:bv-maximal-cell-paths verified CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorCellPath_centered_maximal Let $n,d\geq1$ , $\epsilon>0$ , and let $P$ be an observed categorical law on the $d$ -cell alphabet with category-cell masses $q_{\zeta j}$ . Work in the ideal experiment of def:process-handle, in which all pilot and evaluation counts $N'_{\zeta j}$ and $N_{\zeta j}$ are mutually independent with $\operatorname{Pois}(mq_{\zeta j})$ laws, $m=n/8$ . Fix one of the two pilot events: either $E_j=G_j$ for every cell $j$ , or $E_j=G_j^c$ for every cell $j$ , with $G_j$ as in def:process-handle. For each cell $j$ , let $W_j(\lambda)=\mathbf1_{E_j}\{T_j(\lambda)-f_\lambda(q_j)\}$ , $\lambda\in[0,1]$ , where $T_j$ is the clipped cell estimate of def:jf-estimator and $f_\lambda$ is as in def:dual-process. Assume that each $W_j$ is continuous in $\lambda$ for every count table; that each map from count tables to $W_j\in C([0,1])$ is measurable and Bochner integrable; that each $W_j$ has almost surely finite total variation $\operatorname{TV}_{[0,1]}(W_j)$ ; that $(\|W_j\|_\infty+\operatorname{TV}_{[0,1]}(W_j))^2$ is integrable; and that the paths $W_1,\ldots,W_d$ are independent. Then $\mathbb E\left\|\sum_{j=1}^d\bigl(W_j-\mathbb EW_j\bigr)\right\|_\infty^2 \leq16384\sum_{j=1}^d\mathbb E\Bigl[\bigl(\|W_j\|_\infty+\operatorname{TV}_{[0,1]}(W_j)\bigr)^2\Bigr].$
Lemma lem:capped-marked-count-identity verified CausalSmith.Stat.DiscreteBudgetvalueCurve.CappedMarkedCountIntegralIdentity Let $n,d\geq1$ and $m=n/8$ , and let $P$ be an observed categorical law on the $d$ -cell alphabet with category-cell masses $q_{\zeta j}$ . For a sample $O^{(n)}=(O_1,\ldots,O_n)$ , a permutation $\sigma$ of $\{1,\ldots,n\}$ , an integer $0\leq M\leq n$ , and marks $\omega\in\{\mathrm{pilot},\mathrm{evaluation}\}^n$ , let $(N',N)=(N'_{\zeta j},N_{\zeta j})_{\zeta,j}$ be the pilot and evaluation count table of the first $M$ permuted records $O_{\sigma(1)},\ldots,O_{\sigma(M)}$ , where the $i$ -th permuted record is counted as pilot or evaluation according to $\omega_i$ , as in def:jf-estimator; the marks $\omega_{M+1},\ldots,\omega_n$ do not affect the table. Put $w_n(M)=\Pr\{\operatorname{Pois}(n/4)=M\}/(n!\,2^n)$ . Consider the uncapped marked-Poisson experiment: draw $M\sim\operatorname{Pois}(n/4)$ , then $M$ independent records from $P$ , each marked pilot or evaluation independently with probability $1/2$ , and let $(N',N)$ be the resulting count table. Then, for every real function $g$ of count tables that is integrable under the ideal law of def:process-handle, in which all $N'_{\zeta j}$ and $N_{\zeta j}$ are independent $\operatorname{Pois}(mq_{\zeta j})$ , $\mathbb E_{O^{(n)}\sim P^{\otimes n}}\left[\sum_{M=0}^{n}\sum_{\sigma}\sum_{\omega\in\{\mathrm{pilot},\mathrm{evaluation}\}^n}w_n(M)\,g\bigl(N'(O^{(n)},\sigma,M,\omega),N(O^{(n)},\sigma,M,\omega)\bigr)\right] =\mathbb E_{\mathrm{uncapped}}\bigl[\mathbf1\{M\leq n\}\,g(N',N)\bigr].$

Theorems (7)

Theorem T-1 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.dual_representation For every $P\in\mathcal M_{d,\epsilon}$ and $b\in[0,1]$ , $V_b(P)=\inf_{0\le\lambda\le1}\{b\lambda+F_P(\lambda)\}$ . Consequently, for any bounded process $\widehat F$ , $\sup_{b\in[0,1]}|\inf_\lambda\{b\lambda+\widehat F(\lambda)\}-V_b(P)|\le\sup_{\lambda\in[0,1]}|\widehat F(\lambda)-F_P(\lambda)|$ .
Theorem T-2 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.integrated_process_certificate With $H_0=4096$ , $\kappa=1/512$ , and $D_0=16$ , the handle $\mathsf H_{n,d}$ is completed by the single positive order-four Jackson kernel and the clipping rule in $\widehat V^{\mathrm{JF}}$ . For each fixed $0<\epsilon<1/2$ , there exists one finite $C_\epsilon>0$ , depending only on $\epsilon$ , such that for every $n,d$ in the Jackson--factorial branch, every $P\in\mathcal M_{d,\epsilon}$ , every cell $j$ , and every $\lambda\in[0,1]$ , the following bounds hold simultaneously: the cellwise scalar bias is at most $C_\epsilon\{\sqrt{p_j/[n\log(ed)]}+1/[n\log(ed)]\}$ , the good-pilot centered sum has expected squared supremum at most $C_\epsilon d/[n\log(ed)]$ ; the uncentered cellwise bad-pilot envelope obeys $\|\mathbf1_{G_j^c}\sup_{0\leq\lambda\leq1}|T_j(\lambda)-f_\lambda(q_j)|\|_{L_2}\leq C_\epsilon d^{1/4}e^{-10L}v_j$ , and the centered aggregate bad-pilot risk obeys $E\|\sum_{j=1}^d[\mathbf1_{G_j^c}\{T_j-f_\cdot(q_j)\}-E\mathbf1_{G_j^c}\{T_j-f_\cdot(q_j)\}]\|_\infty^2\leq C_\epsilon d/(mL)$ , where $L=\log(ed)$ , $m=n/8$ , and $v_j=\sqrt{p_jL/m}+L/m$ . Consequently, in the Jackson--factorial branch, the dual threshold process constructed inside $\widehat V^{\mathrm{JF}}$ has expected squared supremum distance from $F_P$ at most $C_\epsilon d/[n\log(ed)]$ , with that same $C_\epsilon$ uniform in $n,d,P,j,\lambda$ . These conclusions include null cells, boundary outcome means, and exact treatment-effect ties.
Theorem T-3 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.paired_capacity_identity Every law in $\mathcal P^{\mathrm{pair}}_k$ belongs to $\mathcal M_{2k,\epsilon}$ , has every occupied-cell treatment effect in $[1/8,3/8]$ (that is, $r_i>0$ implies $1/8\leq\tau_{i,\sigma}\leq3/8$ ), has the binding half-population budget with shadow price $1/4$ , satisfies $V_{1/2}(P)=3/8+(1/2)\sum_{i=1}^k r_i|\theta_i|$ , and has the known constant unrestricted value $V_1(P)=1/2$ . Moreover, for $R,S\in\Delta_k$ , the normalized embedding $r_i=(R_i+S_i)/2$ and $\theta_i=(R_i-S_i)/[8(R_i+S_i)]$ , with zero assigned when the denominator vanishes, is generated by an exact fixed-sample Markov kernel from independent samples from $R$ and $S$ .
Theorem T-4 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.capacity_active_lower There is $c_\epsilon>0$ such that for every $n\geq1$ and $d\geq2$ , every estimator $T$ obeys $\sup_{P\in\mathcal M_{d,\epsilon}:\ V_1(P)=1/2,\ p_j>0\Rightarrow1/8\leq\tau_j\leq3/8}E_P[(T-V_{1/2}(P))^2]\ge c_\epsilon\min\{1,d/[n\log(ed)]\}$ , with null-label padding allowed. The budget is binding throughout the hard family.
Theorem T-5 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.curve_upper There is $C_{\epsilon}<\infty$ such that the total estimator $\widehat V^{\mathrm{JF}}$ satisfies $\sup_{P\in\mathcal M_{d,\epsilon}}E_P[\sup_{b\in I}|\widehat V_b^{\mathrm{JF}}-V_b(P)|^2]\le C_\epsilon\min\{1,d/[n\log(ed)]\}$ for every $n\ge1$ , $d\ge2$ , and $b_0\in[0,1/2]$ , uniformly over null cells, arbitrary occupied-cell masses, boundary outcome means, and exact treatment-effect ties. When $b_0=0$ , the supremum covers the full budget curve on $[0,1]$ .
Theorem T-6 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.matched_curve_frontier There exist $0<c_\epsilon\le C_\epsilon<\infty$ such that for all $n\ge1$ , $d\ge2$ , and fixed $b_0\in[0,1/2]$ , $c_\epsilon\min\{1,d/[n\log(ed)]\}\le\mathfrak R_{n,d,\epsilon,b_0}^{\mathrm{curve}}\le C_\epsilon\min\{1,d/[n\log(ed)]\}$ . The lower bound is witnessed at $b=1/2$ by laws with positive occupied-cell effects, binding capacity, and known constant unrestricted value. When $b_0=0$ , the risk concerns the full curve on $[0,1]$ , whose $b=1$ endpoint recovers the unrestricted scalar optimal-value target.
Theorem T-7 verified CausalSmith.Stat.DiscreteBudgetvalueCurve.fixed_alphabet_reduction For every fixed finite $d$ , the frontier in \mathrm{thm:matched\mbox{-}curve\mbox{-}frontier} reduces to squared risk of order $n^{-1}$ . If additionally $\tau_j=c>0$ for every occupied cell, then $V_b(P)=B(P)+cb$ for $b\in I$ , including exact ties, which is the known linear budget-value special case.

Citeds (1)

Cited result lem:jhw-known-q-l1-lower-regime verified CausalSmith.Stat.DiscreteBudgetvalueCurve.JHWKnownQL1LowerRegime For every fixed $a_0>0$ and $C_0<\infty$ , there are constants $c_{a_0,C_0}>0$ and $k_{a_0,C_0}<\infty$ such that, whenever $k\geq k_{a_0,C_0}$ , $n\geq a_0 k/\log k$ , and $\log n\leq C_0\log k$ , the experiment of $n$ independent observations from $R\in\Delta_k$ , with $S\in\Delta_k$ known to the estimator, satisfies $\sup_{S\in\Delta_k}\inf_{\widehat L_S}\sup_{R\in\Delta_k} E_R\!\left[(\widehat L_S-\|R-S\|_1)^2\right] \geq c_{a_0,C_0}\frac{k}{n\log n}.$ Here the infimum is over estimators based on the $R$ -sample that may depend on the known distribution $S$ .

Auxiliary Lean lemmas (machine-checked) (373)

Definition averagedProcessRisk —
Definition BindingHalfBudget —
Definition capacityHardClass —
Definition centeredPilotPartRisk —
Definition controlValue —
Definition CurveEstimator —
Definition curveRate —
Definition jacksonCellBias —
Definition logAlphabet —
Definition ModelLaw —
Definition Obs —
Definition observedMarginal —
Definition pilotGood —
Definition poCellMass —
Definition PotentialLaw —
Definition ScalarEstimator —
Definition centeredIdealPilotErrorRisk —
Definition idealPilotGood —
Definition idealProcessRisk —
Definition uncappedJacksonCellBias —
Definition badPilotCellEnvelope —
Definition badPilotCellScale —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poCellMass_nonneg_budget —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poCellMass_sum_budget —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.constant_effect_budget_value —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedFullMass_sum —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.full_budget_cell_mass_nonneg —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.full_budget_cell_mass_sum —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.full_budget_value —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.dualMinimum_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poRegression_unit_interval_budget —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poCellMass_sum_one_budget —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budgetValue_unit_interval —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.weighted_budget_weak_duality —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.dualMinimum_uniform_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budgetValue_order_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.curve_coordinate_in_budget_interval —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.curve_loss_pointwise_bound —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.curve_loss_sup_bound —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.curve_risk_bddAbove —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.curve_risk_nonneg —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.scalar_coordinate_of_curve_estimator —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.scalar_coordinate_risk_le_curve_risk —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.curveRate_nonneg —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.dualMinimum_uniform_contraction —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.dualProcessReal_bounded —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_pairwise_implies_armwise —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_cell_mass_as_totalMass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_arm_mass_as_armMassFn —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_cell_success_mass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_armValue_identified —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_threshold_identified —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_dualProcess_identified —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_dual_weak_bound —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.simplexL1_nonneg_le_two —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.simplexL1_self —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.simplexL1_symm —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_armValue_eq_predecessor —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_armValue_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_exists —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_totalMass_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_hinge_pointwise_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_thresholdFunReal_pointwise_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_positiveGain_bounds —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_positiveGain_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_positiveGain_threshold_rewrite —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_thresholdFunReal_hinge_decomposition —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_hinge_cutoff —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_affine_variation_eq —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_three_piece_variation_le —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_hinge_breakpoint —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_hinge_breakpoint_bounds —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.hinge_active —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.hinge_inactive —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.hinge_difference_pointwise —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.hinge_difference_variation_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.budget_variation_add_const —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorCell —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorPart_eq_sum_cells —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorCellPath —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorCellPath_centered_maximal —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.normalizedPairedParameters —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedCompletion_effect_bounds —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedCompletion_controlValue —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedCompletion_modelClass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedCompletion_fullTreatmentValue —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorCell_continuous_time —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonCoefficientPath —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonCoefficientPath_bv —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonFourPoissonFactorialPath —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonFourPoissonFactorialPath_apply —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCellStatistic_eq_localJacksonFourPoissonFactorialPath —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonFourPoissonFactorialPath_sq_bound —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.centeredFactorial_eq_factorialLift —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.factorialMonomial_eq_fourFactorialMonomial —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.factorialMonomial_mean —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.factorialMonomial_square_envelope —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.thresholdFunReal_continuous_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.thresholdFunReal_lambda_lipschitz —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.thresholdFunReal_lipschitz_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonConvolution_lipschitz_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonConvolution_continuous_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_degreeOf_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_eval_cos —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_eval_continuous_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_eval_lipschitz_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCoefficient_eq_tensorCoeffs —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCoefficient_continuous_time_of_grid —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCoefficient_continuous_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_fixed_eval_continuous_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCellStatistic_continuous_time —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedCompletion_budgetValue_one —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSignPolicy —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSignPolicy_budget —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSignPolicy_value —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedCompletion_dualQuarter —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedCompletion_bindingValue —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.thresholdFunReal_continuousOn_nonnegative —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRectangle_affinePoint_nonnegative —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRadius_pos_of_pos —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRectangle_threshold_pullback_continuousOn —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorCell_continuous_time_of_pos —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.path_norm_eq_sSup_abs_restrict —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorCellPath_norm_eq_sSup —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealErrorProcess_good_add_bad —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.normalizedPairedMassContrast —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.normalizedPairedTreatedAtom —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.normalizedPairedObservedAtom —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.normalizedPairedL1 —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.normalizedPairedBudgetValue —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonDegree_exponential_budget —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedFullMass_observedSum —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleLaw_singleton —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.productLaw_singleton_budget —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedFullMass_nonneg —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_fullMass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_observedAtom —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedKernelAtom —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedKernelAtom_nonneg —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedKernelAtom_sum —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedKernelPMF —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSampleKernel —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSampleKernel_singleton —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedKernelMix_aux —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedKernelAtom_mixed —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSampleEquiv —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSample_realFactorization —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSampleKernel_mixed —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_poCellMass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_poTreatmentAtom —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_poJointAtom —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_poPairAtom —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_causalRestrictions —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_poNumerator —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_poRegression_weighted —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedLaw_completion —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedKernelAtom_mixed_observed —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSampleKernel_reproduces —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_conditional_jensen —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_conditional_risk_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.knownL1_worst_bddBelow —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1Risk_bddAbove_all —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1Risk_bddAbove_fixed —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_known_reference_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_known_minimax_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_lower_in_cited_regime —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotGood_center_mem_radius —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotGood_flatRate_center_mem_radius —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotGood_rate_div_radius_sq —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotHalfWidth_eq_empiricalRadius —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCoefficientBV_pilot_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_localJacksonFourPoissonFactorialPath_sq_bound —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_localJacksonFourPoissonFactorialPath_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_factorialPath_equation21 —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poissonQuarterCapTail_le_paperRemainder —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.measurable_pathSize_run —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.measurable_pathSize_sq_add_const —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pathSize_add_le —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodThresholdCorrectionPath —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodThresholdCorrectionPath_bv —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodThresholdCorrectionPath_size_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodCellErrorPath_eq_factorial_add_correction —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodCellErrorPath_size_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_fullCellErrorPath_sq_integral_le —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotGoodBool —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotGoodBool_eq_true —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.singleCellCountTable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poissonTableCell_singleCellCountTable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.curryCountTable_eq_at_of_poissonTableCell_eq —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotGood_singleCell_iff —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotErrorCellPath_singleCell_local —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.flatGoodPilotCellPath_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotCellPath_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotCellPath_sq_eq_indicator —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.eVariationOn_path_add_lt_top —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotCellPath_bv —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotCellPath_ae_bv —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotCellPath_measurable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotCellPath_sq_integrable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotCellPath_integrable —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.flattenCountTable —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.curryCountTable —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.countTableEquiv —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.idealFlatRate —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.map_poissonTableLaw_curryCountTable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.map_flatIdealCountLaw —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.curryCountTable_cell —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pathSize_le_two_endpointVariation —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.sum_pathSize_sq_le_four_endpointVariation_sq —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.eVariationOn_time_eq_Icc —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.affinePoint_l1_sub_center_le_sum_radius —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.tensorJacksonPathIntegral_size_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_cube_pathSize_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonChebyshevFactor_le_exp_twelve —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonDegree_factorial_index_exponential_budget —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCoefficientBV_le_of_cube_pathSize —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonCoefficientPath_sq_sum_le_jacksonCoefficientBV —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonFourPoissonFactorialPath_sq_integral_le_coefficientBV —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRadius_le_pilotHalfWidth —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRadius_sq_le_count_envelope —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRadius_sum_sq_integral_le_cellScale —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_lower_dense_logAlphabet —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jfEstimator_unit_interval —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jfEstimator_curveLoss_le_one —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jfEstimator_curveRisk_le_one —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jfEstimator_worstCurveRisk_le_one —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.empiricalCellVector_eq_empiricalMass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.empiricalCellVector_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.empiricalThresholdProcess_error_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.empiricalThresholdProcess_uniformRisk_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_prefix_risk —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_minimax_antitone —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_lower_large_dense —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_pointMass —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_halfMass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_fixedTargets —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_commonAtom —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_atomRisk_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_finiteAlphabetLower —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.twoSampleL1_lower_large_sparse —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.empiricalThresholdProcess_bounded —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.averagedThresholdProcess_bounded —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.clip_unit_distance_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.dualObjective_bddBelow_of_bounded —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.clippedDualCurveLoss_le_processError —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jfEstimator_curveLoss_le_processError —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jfEstimator_empiricalCurveRisk_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jfEstimator_averagedCurveRisk_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.logAlphabet_bounds_curve —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.empiricalCurveRate_algebra —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.finiteCapAuxWeight —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.finiteCapAuxWeight_nonneg —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.finiteCapAuxWeight_sum —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.permutedMarkedCountTable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.permutedMarkedCountTable_eq_uncapped_prefix —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.uncappedMarkedCountLaw_table_eq_idealCountLaw —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.CappedMarkedCountIntegralIdentity —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.centeredIdealGoodPilotErrorRisk_eq_path_integral —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.centeredIdealGoodPilotErrorRisk_le_raw —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_raw_scale_le_rate —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.centeredIdealGoodPilotErrorRisk_le_rate —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotCellPaths_independent —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotError_centered_maximal —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.discreteLaw_sum_cellMass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.sum_badPilotCellScale_sq_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilotError_centered_maximal_quantitative —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poisson_pilotCoordinateBad_probability —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poisson_pilotCoordinateBad_second_moment —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poisson_pilotCoordinateBad_fourth_moment —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotCell_universalBadScore_moment —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.fairBoolLaw_eq_uncappedFairMarkLaw —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealBadPilotCellPath_integrable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.centeredIdealBadPilotErrorRisk_eq_path_integral —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.centeredIdealBadPilotErrorRisk_le_cell_norms —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.centeredIdealBadPilotErrorRisk_le_raw —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.badPilot_raw_scale_le_rate —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.centeredIdealBadPilotErrorRisk_le_rate —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotMidpoint_sub_center_abs_le_halfWidth —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealClippedCell_error_le_badScore —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealClippedCell_sSup_le_badScore —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localBadPilotCellEnvelope_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealBadPilotCellEnvelope_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.badPilotCellEnvelope_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealBadPilotCellPath_norm_sq_integrable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealBadPilotCellPath_norm_sq_sum_integrable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealClippedCell_error_sSup_sq_integrable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotCell_empiricalBadScore_moment —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.independent_poisson_empiricalBadScore_sq_integrable_four —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.independent_poisson_empiricalAggregateScore_sq_integrable_four —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotCell_badScore_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotCell_badScore_sq_integrable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotCell_score_sq_integrable —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.dualProcessPath —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.armValue_mem_totalMass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.dualProcessReal_mem_unit —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.dualProcessPath_norm_le_one —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.auxiliaryThresholdPath —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.idealThresholdPath —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealThresholdPath_error_norm_eq —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealProcessRisk_integrand_integrable —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.finiteCapEstimatePath —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.finiteCapEstimatePath_average_apply —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.finiteCapErrorPath_average_apply —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.localJacksonPolynomial_boundary_adaptive —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_localJacksonPolynomial_boundary_adaptive —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_localJacksonPolynomial_boundary_le_radiusSum —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.scalarClip_sub_le_sq_div —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poisson_factorialLift_integrable_run —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.factorialProduct_integrable_run —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poisson_descFactorial_mul_integrable_run —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.integrable_finsetSum_sq_of_mul —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.poisson_factorialLift_sq_integrable_run —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.factorialProduct_sq_integrable_run —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCellRaw_centered_sq_integrable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCellRaw_centered_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonRaw_factorial_envelope_absorb —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_jacksonCellRaw_centered_sq_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCellStatistic_mean_sub_raw_mean_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_jacksonCellStatistic_mean_sub_raw_mean_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.jacksonCellRaw_mean —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_jacksonCellStatistic_conditional_bias_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealCountLaw_isProbabilityMeasure —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.integral_sq_le_integral_sq_of_nonneg —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRadius_sum_integral_sq_le_cellScale —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pilotRadius_sum_integral_le_cellScale —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.flatGoodPilot_conditionalBias_integral_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealClippedCell_error_integrable —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.expectedUncappedJacksonCell_eq_flat_iterated —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealBadPilot_scalarMean_le_envelope —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilot_scalarMean_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.uncappedJacksonCellBias_le_good_add_badEnvelope —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.logAlphabet_mul_rpow_neg_three_sixteenths_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.logAlphabet_div_jacksonDegree_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_clippingCoefficient_mul_log_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.truncatedEmpiricalInterval_boundaryProduct_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotGood_boundaryProduct_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.cellVector_le_cellMass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealPilotGood_boundarySqrt_sum_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_localJacksonPolynomial_boundary_sharp —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.goodPilot_jacksonCellStatistic_conditional_bias_sharp —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.flatGoodPilot_conditionalBias_integral_sharp —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilot_scalarMean_le_of_flat —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.idealGoodPilot_scalarMean_sharp —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.logAlphabet_sq_mul_rpow_neg_three_sixteenths_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.badPilotCellScale_le_log_sq_mul_scalarRate —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.badPilot_exponential_mul_log_sq_le —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.uncappedJacksonCellBias_le_goodMean_add_badEnvelope —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.sharpBoundary_div_degree_le_scalarRate —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.badPilotCellScale_div_degree_sq_le_scalarRate —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.uncappedJacksonCellBias_le_rate —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSampleMarkovKernel —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedSampleMarkovKernel_comp_twoSampleLaw —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedL1_lower_transport_capacity —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedL1_lower_transport_capacity_iid —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.padCausalObs —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.padCausalFullObs —
Definition CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_fullMass_castLE —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_fullMass_new —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_poCellMass_castLE —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_poRegression_castLE —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_poCellMass_new —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_effect_new —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_effect_castLE —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_controlValue —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_budgetValue —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_capacityHardClass —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_observedMarginal_pmf —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.padPotentialLaw_productLaw_map —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.sqRisk_padPotentialLaw —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.pairedL1_lower_transport_capacity_padded —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.small_capacity_lower_padded —
Lemma CausalSmith.Stat.DiscreteBudgetvalueCurve.two_sample_l1_lower_all_samples —

Symbol realizations (Lean @realizes) (47)

q_j verified realized by PotentialAtom, observedCellVector
P verified realized by observedFromPotential, CanonicalObservedOutcome, PotentialLaw, variable@187
p_j verified realized by cellMass, poCellMass, Overlap
e_j verified realized by productLaw, Overlap
n verified realized by variable@158
d verified realized by variable@159, CausalModelClass
$\epsilon$ verified realized by variable@160, CausalModelClass
b_0 verified realized by variable@161
j verified realized by variable@162
a verified realized by variable@162
[d] verified realized by ObservedRecord
X verified realized by ObservedRecord, ConditionalExchangeability
A verified realized by ObservedRecord, ConditionalExchangeability
Y verified realized by ObservedRecord, Consistency
O verified realized by ObservedRecord
O^{(n)} verified realized by ObservedSample
u verified realized by observedCellVector
Y(a) verified realized by FullRecord, Consistency, ConditionalExchangeability
$\mathcal M_{d,\epsilon}$ verified realized by CausalModelClass
$\tau_j$ verified realized by effect
$\mu_{aj}$ verified realized by potentialMean
$\pi$ verified realized by budgetPolicyClass
b verified realized by budgetPolicyClass
$\Pi_b(P)$ verified realized by budgetPolicyClass
B(P) verified realized by controlValue
V_b(P) verified realized by budgetValue
s_a(u) verified realized by armMassFn
s(u) verified realized by totalMass
g_a(u) verified realized by armValue
$f_\lambda(u)$ verified realized by thresholdFun
$\lambda$ verified realized by thresholdFun
$F_P(\lambda)$ verified realized by dualProcess
I verified realized by CurveEstimator
$\widehat V^{\mathrm{JF}}$ verified realized by CurveEstimator, jfEstimator
$\mathfrak R_{n,d,\epsilon,b_0}^{\mathrm{curve}}$ verified realized by curveMinimaxRisk
k verified realized by variable@559
i verified realized by variable@559
$\sigma$ verified realized by variable@559
r verified realized by ProbabilitySimplex
R verified realized by ProbabilitySimplex
S verified realized by ProbabilitySimplex
$\theta$ verified realized by PairedContrasts
$\mathcal P^{\mathrm{pair}}_{k}$ verified realized by pairedLaw, pairedFamily
$\mathsf H_{n,d}$ verified realized by processHandle
H_0 verified realized by pilotRadiusConstant
$\kappa$ verified realized by jacksonDegreeConstant
D_0 verified realized by boundedAlphabetCutoff

Proof map 16 statements · 15 edges

Minimax Estimation of Budgeted Treatment Value Curves with Discrete Covariates

Abstract

Introduction

Related work

Setup and assumptions

Minimax risk for the budget-value curve

Discussion and limitations

Limitations and future work

Appendices

Proofs and verification scope

Estimator and uniform upper bound

Process estimates

Proofs of the main results

References