CausalSmith · seminar slides
Estimating the Value of Optimal Treatment
We establish how accurately we can estimate the outcome from choosing the better treatment in each covariate group, even when some treatments are rarely observed.
slides for Estimating Optimal Treatment Value with Many Covariate Cells and Shrinking Overlap
Research Question
A practitioner wants the population value of choosing the better treatment separately in each covariate cell.
Ψ(P)=x∈[d]∑pxa∈{0,1}maxμax.
Here P is the population law, d is the number of cells, px is cell x’s population share, and μax is its outcome mean under treatment a.
- Plug-in estimation replaces shares and outcome means by sample averages.
- Rare treatments make those averages unstable.
- Taking their maximum selects upward noise near treatment ties.
Archive (2026), Theorem 3, establishes the fixed-overlap risk order min{1,d/[nlog(ed)]}, with constants depending on overlap.
With n observations and known minimum treatment probability ϵ, how does attainable precision deteriorate as ϵ shrinks?
Key Idea
Estimate a polynomial approximation to the maximum, rather than taking the maximum of noisy estimates.
- Pilot counts locate each cell’s probabilities.
- A polynomial approximates its value across treatment ties.
- Independent counts estimate polynomial terms without power-estimation bias.
- Each arm’s denominator sensitivity is paired with that arm’s count fluctuations.
informal · Theorem T-4 With n≥1 independent categorical observations, d≥2, binary treatment and outcome, and known 0<ϵ≤1/2, minimax squared risk is between universal multiples of min{1,d/[nϵlog(ed)]}.
A deterministic estimator attains this scale uniformly over unknown shares, propensities, and treatment ties.
Example
Consider equal-sized cells with treatment means around a tie:
px=d1,πx=ϵ,μ0x=21,μ1x=21+aTxde.
The treatment-one probability πx equals the overlap floor. The perturbation Txde lies in [−1,1]; amplitude 0<a≤1/2 keeps outcome means in [0,1].
Ψde(Tde)=21+2dax∈[d]∑(∣Txde∣+Txde),
This computes the family’s value; Tde collects its cell perturbations.
Negative perturbations give no gain over control. Positive perturbations give linear gain. At zero, the preferred treatment changes: the value has a corner.
How can we estimate that gain without interpreting noise as improvement?
Model
Observe n≥1 independent units Oi=(Xi,Ai,Yi) with common law P.
Covariate Xi has d≥2 categories; treatment Ai and outcome Yi are binary.
qay,x:=P(X=x,A=a,Y=y),px:=a∈{0,1}∑y∈{0,1}∑qay,x,
An atom probability qay,x records one cell, treatment, and outcome combination. Summing its four atoms gives the cell share.
The propensity is πx=(q10,x+q11,x)/px, and the arm mean is μax=qa1,x/(qa0,x+qa1,x).
For every occupied cell, require
ϵ≤πx≤1−ϵ.
The known floor 0<ϵ≤1/2 guarantees observations from both arms. Write Dd,ϵobs for these laws.
Our example places treatment one exactly at the floor.
Causal Interpretation
Let Y(a) be the potential outcome under treatment a, and P the full-data law.
- Consistency: Y=Y(A); the observed outcome belongs to the treatment received.
- Conditional exchangeability: Y(a)⊥A∣X; within a recorded cell, treatment carries no further information about either potential outcome.
- Overlap: both treatments occur in every occupied cell.
V⋆(P)=x∈[d]∑P(X=x)a∈{0,1}maxEP[Y(a)∣X=x]=Ψ{Obs(P)},
The causal optimal value V⋆(P) averages the causally better treatment’s mean. The observed marginal of (X,A,Y) is Obs(P).
These conditions identify the causal value from the observed target. Every admissible observed law has such a causal completion, so the same risk characterization applies.
Main Result
Minimax risk Rn,d,ϵ is the smallest worst-case mean squared error over all estimators. Write Ld=log(ed).
Under independent sampling and the overlap restriction, for every n≥1, d≥2, and 0<ϵ≤1/2,
c⋆min{1,nϵLdd}≤Rn,d,ϵ≤P∈Dd,ϵobssupEP[(Vn,d,ϵAF−Ψ(P))2]≤C⋆min{1,nϵLdd}.
The deterministic estimator Vn,d,ϵAF attains the scale. Positive constants c⋆,C⋆ are universal.
- nϵ is the expected rare-arm count when its propensity equals the floor throughout the population.
- Risk has constant order when nϵ≤d/Ld; above that threshold, its scale is d/(nϵLd).
- In our example, the guarantee holds for every perturbation vector, including ties in every cell.
Cell Contribution
Collect the four atom probabilities as qx=(q00,x,q01,x,q10,x,q11,x).
For a nonnegative vector u, let sa(u)=ua0+ua1 be arm mass, s(u)=s0(u)+s1(u) total mass, and Da(u)=max{sa(u),ϵs(u)} a protected denominator.
Fϵ(u)=⎩⎨⎧a∈{0,1}maxDa(u)s(u)ua1,0,u=0,u=0,u∈R+4,
This computes a weighted maximum while protecting nearly empty arm denominators.
At true probabilities, overlap makes protection inactive:
Fϵ(qx)=pxa∈{0,1}maxμax.
Summing these cell contributions gives Ψ(P). Protection also permits approximation at nearby vectors that need not satisfy overlap.
The sensitivity to changes within arm a is weighted by 1+px/sa(qx): smaller arms have more sensitive ratios.
Pilot Localization
Sample splitting uses pilot observations to choose an approximation region and independent evaluation observations to estimate its polynomial.
In an auxiliary Poisson experiment, all pilot and evaluation atom counts are independent, each with mean mqay,x. Set m=n/8 and L=Ld.
cay,x=mNay,x′,hay,x=H0{mcay,xL+mL},
Pilot count Nay,x′ gives estimated mass cay,x and uncertainty radius hay,x. The constant H0 is universal.
- The square-root term follows that atom’s count fluctuations.
- The additive term retains uncertainty when the count is zero.
Intersect each interval with the nonnegative line. Their product is rectangle Qx, with lower endpoints ℓay,x, upper endpoints uay,x, midpoint bx, and half-widths rx.
Successful localization means Gx={qx∈Qx}.
In our example, treatment-one atoms have total mass ϵ/d: their smaller fluctuations enter their own localization widths.
Polynomial Smoothing
Jiao et al. (2015) supply the strategy of polynomial approximation followed by unbiased polynomial estimation.
Within Qx, express each coordinate using a cosine. Average nearby angles with nonnegative, normalized Jackson weights JKn:
Px,Kn(bx+rx⊙cosθ)=∫[−π,π]4Fϵ(bx+rx⊙cos(θ+τ))a,y∈{0,1}∏JKn(τay)dτ,θ∈R4.
Here θ locates a point, τ shifts its angles, and ⊙ means coordinatewise multiplication.
The weights contain only finitely many oscillation frequencies. After averaging, the function is a polynomial Px,Kn, with maximum coordinate degree D=2(Kn−1).
Their average angular displacement is at most C/Kn; their average squared displacement is at most C/Kn2.
In our example, restricting this polynomial to the cell’s perturbation path smooths the gain across zero.
How do angular resolution and the pilot rectangle determine approximation error?
Approximation Balance
Let Ra,x=ra0,x+ra1,x be the total half-width within arm a. On successful localization in an occupied cell,
∣Px,Kn(qx)−Fϵ(qx)∣≤64a=0∑1(1+sa(qx)px){Kn∑y(qay,x−ℓay,x)(uay,x−qay,x)+Kn2Ra,x}.
This bounds the cell approximation error.
- Sensitivity: 1+px/sa(qx) weights each arm separately.
- Pilot uncertainty: the square-root product measures distances to the interval’s two ends. It vanishes at an endpoint.
- Resolution: the first term receives 1/Kn; the remaining boundary error receives 1/Kn2.
The square-root product is at most a constant times qay,xL/m. Pairing these fluctuations with their own arm sensitivities costs px/ϵ.
Choose Kn=max{2,⌊κL⌋}, with small universal κ>0. Then
ηx=mϵLpx+mϵL1,
and approximation error is at most Cηx. The first term comes from fluctuations; the second comes from boundary error.
Polynomial Estimation
Define D=2(Kn−1), the maximum degree in each coordinate.
Expand the polynomial around midpoint bx, using half-widths rx to normalize coordinates:
Px,Kn(v)−Fϵ(bx)=α∈{0,…,D}4∑βx,αa,y∈{0,1}∏(ray,xvay−bay,x)αay,v∈Qx.
The four exponents α specify a term, and βx,α is its coefficient.
Replace every centered power by a centered factorial statistic Uk:
Zx=Fϵ(bx)+α∈{0,…,D}4∑βx,αa,y∈{0,1}∏ray,xαayUαay(Nay,x;bay,x).
Here Nay,x are independent evaluation counts. The pilot chooses the coefficients and centers.
Conditional on the complete pilot array N′,
Eaux[Zx∣N′]=Px,Kn(qx),
where Eaux averages the auxiliary experiment.
The remaining bias is approximation error. Why does replacing powers by factorials work?
One Cell Through the Estimator
For one cell in our example, the true atoms are
q00,x=q01,x=2d1−ϵ,q10,x=dϵ(21−aTxde),q11,x=dϵ(21+aTxde).
These describe a line through the treatment tie.
Within the pilot rectangle, its true contribution is 1/(2d)+a(∣Txde∣+Txde)/(2d). The restriction of Px,Kn approximates this localized gain curve across zero.
For count N, center ζ, and degree k,
Uk(N;ζ)=t=0∑k(tk)(−ζ)k−tmt(N)t,
where (N)t=N(N−1)⋯(N−t+1) counts ordered selections of distinct records.
A squared treated-success factor ((q11,x−b11,x)/r11,x)2 is estimated by U2(N11,x;b11,x)/r11,x2.
Here U2(N;b)=N(N−1)/m2−2bN/m+b2. Its expectation is (q−b)2; using N2 would add count noise.
Applying this replacement to every term estimates the polynomial even at the exact tie, without first selecting a winning arm.
Cell Noise
Higher-degree terms reduce approximation bias but increase estimation noise.
Conditional on a successful pilot,
Eaux[(Zx−Fϵ(bx))2∣N′]≤(α∑∣βx,α∣)2e32D2/Lon Gx.
The coefficient sum measures how much the polynomial can amplify count noise. The exponential factor bounds the second moments of factorial terms.
Measure cell variation using arm widths and sensitivities:
Ra,x=ra0,x+ra1,x,wa,x=1+Da(bx)s(bx),Sxaw=2a=0∑1wa,xRa,x,
Here wa,x is arm sensitivity at the midpoint, and Sxaw bounds variation across the rectangle.
Small logarithmic degree bounds the preceding second moment by Cfacd1/16(Sxaw)2, with universal Cfac.
Clip Zx around Fϵ(bx) with radius d1/4Sxaw, obtaining Tx. Clipping controls excursions from bad pilots.
Can summing over d cells absorb the factor d1/16?
Summed Variance
The squared clipping scale retains the cell’s population mass. Define ax=pxL/(mϵ)+L2/(m2ϵ2). Then
Eaux(Sxaw)2≤Csax.
The constant Cs is universal. Thus the quantity being summed is a bound on expected squared cell variation.
raux=mϵLd,msum=x∑ax=mϵL+m2ϵ2dL2.
Here raux is the target auxiliary risk scale.
Population mass enters here: ∑xpx=1 makes the first term independent of d.
The active regime enters next: nϵ≥d/L, or d≤8mϵL, gives msum≤(L2+8L4)/(mϵL).
Consequently, d1/16msum/raux≤d−15/16(L2+8L4), which is uniformly bounded because L=log(ed).
d1/16x∑Eaux(Sxaw)2≤CsCvarraux.
The universal constant Cvar absorbs that bounded ratio. This is the connection from cell noise to aggregate variance.
Aggregate Error
Independent cell statistics make mean squared error equal summed variances plus squared summed bias.
The variance calculation already absorbs polynomial growth. Three bias contributions remain:
- Approximation: total population mass gives ∑xpx≤d.
- Clipping: cell bias is at most a constant times d−3/16EauxSxaw; squaring the sum uses the same mass calculation.
- Failed pilots: their error moments decay rapidly with L, retaining the cell scales ax.
For the approximation scales,
x∑ηx≤raux+raux,x∑ηx2≤(x∑ηx)2≤18raux.
This bounds summed approximation bias and its squared cell contributions; the active regime gives raux≤8.
Together,
Eaux(x∑Tx−Ψ(P))2≤CPmϵLd.
The universal constant CP collects the error terms. Since m=n/8, this is the required upper-bound scale.
Deterministic Estimator
Turn the auxiliary construction into a statistic using exactly n observations.
Draw M∼Pois(n/4). When M≤n, use the first M records and fair pilot/evaluation allocations.
V=⎩⎨⎧Π[0,1]x∈[d]∑Tx,0,M≤n,M>n,Vn,d,ϵAF=E[V∣O1,…,On].
Projection Π[0,1] keeps the estimate in the value range. Conditional averaging integrates the auxiliary count and allocations, producing a deterministic function of the observations.
Projection and averaging cannot increase squared-error risk. The exponentially unlikely overflow contributes at most the required scale.
Under our calibration, use this construction when nϵ≥d/L. Otherwise return 1/2, whose squared error is at most 1/4.
Why can no estimator uniformly improve the risk order?
Hard Alternatives Near Ties
Return to the equal-share example. Draw cell perturbations independently from either of two symmetric distributions η0,η1 on [−1,1].
Choose them to match moments through degree Kde, while their expected absolute perturbations differ by at least 1/(50Kde).
Here Kde is the tie family’s matched degree—the degree denoted Kabs in the scalar approximation argument.
Under z=sin2ω, degree-Kde polynomials use only low angular frequencies. A signed angular average cancels these frequencies, while the corner retains higher ones:
∣sin2ω∣=π2−π4ℓ=1∑∞4ℓ2−1cos(4ℓω).
This expands the absolute-value gain. Its nonconstant coefficients share one sign; the surviving block contains Kde terms of size proportional to Kde−2.
Approximation–moment duality, as in Wu and Yang (2019), converts this inverse-degree separation into symmetric moment-matched distributions.
Symmetry removes the signed perturbation from average value. Their value centers differ by at least a/(100Kde).
Sparse Intensity Family
Tie perturbations have bounded amplitude. A second family allows a wider range of cell intensities zx∈[0,M], with M≥2.
Before normalization, set
q11,x=dϵ(1−ϵ)zx,q10,x=dϵ(1−ϵ),q00,x=q01,x=2d(1−ϵ)2+ϵ2zx.
These are cell–arm–outcome masses. Divide by their total S(z)=1−ϵ+(ϵ/d)∑xzx to obtain law Pzsp.
Control mean is 1/2, treatment mean is zx/(1+zx), and overlap holds. Treatments tie at intensity one.
Define weighted gain ϕϵ(z)=(1−ϵ+ϵz)max{z−1,0}/(1+z). Then
Ψ(Pzsp)=21+2dS(z)1x∈[d]∑ϕϵ(zx).
This computes baseline plus normalized average gain.
We need two intensity distributions with matching moments, different gains, and common mean one so that the normalizer centers at one.
Moment Cancellation
Map angle to intensity by zM(ω)=M(1+cosω)/2. The angles ±ϑM, where ϑM=arccos(2/M−1), map to the treatment tie z=1.
Use a nonnegative periodic Jackson weight JN, normalized to integrate to one against du/(2π).
- Its frequencies satisfy ∣j∣≤2N−2.
- Its angular spread is at most a constant times 1/N.
- Multiplying by cos(4Nu) shifts its frequencies to absolute values between 2N+2 and 6N−2.
Set N=A0K, with sufficiently large universal integer A0, and kN(u)=JN(u)cos(4Nu).
HK,M(ω)=kN(ω−ϑM)+kN(ω+ϑM),WK,M=∫−ππ{1+zM(ω)}∣HK,M(ω)∣2πdω.
The signed weight HK,M places oscillations at both ties. WK,M is its absolute mass weighted by 1+z.
A degree-K polynomial in zM(ω) has frequencies at most K. The shifted weights have none there, so every polynomial moment through K cancels.
Why does the gain survive this cancellation?
Gain at the Corner
Near a tie angle, the intensity map has slope magnitude M−1.
Angular width 1/N therefore becomes intensity width proportional to M/K. Across that width, the gain changes slope by 1/2.
To see why signed oscillations retain this response, let GN be the twice-integrated weight: GN′′=kN.
- At its center, ∣GN(0)∣ is between universal multiples of 1/N.
- Its absolute integral is at most C/N2.
- Integration by parts pairs the gain’s slope change with GN(0); smooth curvature is paired with the smaller integral.
The corner contribution has scale M/N; the smooth remainder is at most CM/N2. For 2≤M≤K2, large A0 makes the corner dominate.
Localization also bounds WK,M above by a universal constant. Hence
∫−ππϕϵ{zM(ω)}WK,MHK,M(ω)2πdω≥cpKM.
This is the gain contrast retained after normalization; cp>0 is universal.
Mean-one Alternatives
Map the positive and negative parts of HK,M/WK,M into intensity space, obtaining nonnegative measures σ+,σ−.
Moment cancellation gives them equal mass t and equal first moment u.
The definition of WK,M gives
∫(1+z)d(σ++σ−)=1.
This computes their combined weighted mass. Equal masses and first moments imply 2t+2u=1, hence t+u=1/2.
Add the same atom at z0=(1−u)/(1−t):
ν0=σ−+(1−t)δz0,ν1=σ++(1−t)δz0.
Here δz0 is a unit point mass. Both distributions now have total mass one and mean one. The completion point satisfies 1/2≤z0≤2≤M.
The common atom changes neither moment differences nor the gain contrast.
informal · Theorem T-6 For integer K≥2, 2≤M≤K2, and 0≤ϵ≤1/2, two probability laws on [0,M] can share mean one and moments through K, yet differ in expected weighted gain by at least cM/K, with universal c>0.
Full Likelihood Comparison
A gain gap implies statistical difficulty only if the observations cannot reliably distinguish the alternatives.
Fix an inflation factor B>2. In the intensity family, observe all four independent Poisson counts with means Bnqay,x(z), including controls.
Let Lz be their likelihood ratio relative to z⋆=M/2, and Ez⋆ reference expectation. Then
Ez⋆[LzLw]=exp{α(z−z⋆)(w−z⋆)},
where w is another intensity and α≤2Bnϵ/(dM) measures the full likelihood’s sensitivity.
Matching moments through Ksp, the intensity family’s degree, cancels the exponential expansion through that degree. Its remaining terms are small when BnϵM/(2d) is at most a small multiple of Ksp.
The tie family has the parallel identity
E0[Lde,zLde,w]=exp{4λtra2zw},z,w∈[−1,1].
Here E0 is expectation at the tie and λtr=Bnϵ/d is treated count intensity per cell.
Degrees proportional to Ld make both complete count mixtures close after combining all cells. Randomly ordering the Poisson records transfers this difficulty to their first n observations; large fixed B controls shortage.
Lower-bound Coverage
Choose logarithmic matched degrees Ksp≍Kde≍Ld. Write xsplice=d/(Bnϵ).
Choose the tie amplitude and intensity support by
ade2=min{41,BnϵηdedKde}.
Msp=min{Ksp2,BnϵηspdKsp}.
The small universal constants ηde,ηsp>0 keep the likelihood mixtures close.
| Family | Range supplying coverage | Squared value separation: at least a universal multiple of | |---|---|---| | Perturbations around ties | ηspxspliceKsp<2 | min{1/(4Kde2),ηdexsplice/Kde} | | Cell intensities | ηspxspliceKsp≥2, so Msp≥2 | min{1,ηspxsplice/Ksp} | | Two rare-arm laws | Bounded d | min{1,1/(nϵ)} |
For sufficiently many cells, independent draws concentrate values around separated centers. Common mean one centers the intensity normalizer at one.
An estimator accurate below these gaps would distinguish close observation mixtures. Degree comparison makes the first two rows cover min{1,d/(nϵLd)}; the last supplies bounded alphabets.
Takeaways
- Precision: optimal worst-case squared risk has order min{1,d/[nϵlog(ed)]}, uniformly over unknown shares, propensities, and treatment ties.
- Estimation: local polynomials handle the maximum’s corner; factorial statistics estimate their terms without bias. Summing mass-sensitive cell scales absorbs polynomial noise.
- Necessity: matching moments hides changes in gains. Localized oscillations cancel polynomial information while retaining the gain’s change in slope.
informal · Theorem T-5 For independent observations of a common law, dn≥2, and known 0<ϵn≤1/2, uniform mean-square consistency is possible exactly when nϵnlog(edn)dn⟶0.
Here dn and ϵn are cell counts and overlap floors along the sample-size sequence. Under outcome consistency and conditional exchangeability, the same criterion governs causal optimal value.
Appendix: Matched Risk Frontier
The deterministic estimator attains the universal minimax squared-error scale for observed and causally identified values.
There exist universal real constants c⋆,C⋆,H0,κ and an integer D0 satisfying 0<c⋆≤C⋆,H0>0,κ>0,D0≥2, such that the following bounds hold for every:
- (Sample size.) Integer n≥1.
- (Alphabet size.) Integer d≥2.
- (Overlap.) Real overlap parameter 0<ϵ≤1/2.
Write Ld=log(ed) for the logarithmic alphabet scale, and let Vn,d,ϵAF be the prescribed deterministic armwise estimator with calibration constants H0,κ,D0. The observed minimax squared-error risk, Rn,d,ϵ=VinfP∈Dd,ϵobssupEP[(V−Ψ(P))2], where the infimum ranges over measurable real-valued estimators based on n observed units, satisfies c⋆min{1,nϵLdd}≤Rn,d,ϵ≤P∈Dd,ϵobssupEP[(Vn,d,ϵAF−Ψ(P))2]≤C⋆min{1,nϵLdd}. For the causal class, the same estimator and constants satisfy c⋆min{1,nϵLdd}≤VinfP∈Pd,ϵsupEObs(P)[(V−V⋆(P))2]≤P∈Pd,ϵsupEObs(P)[(Vn,d,ϵAF−V⋆(P))2]≤C⋆min{1,nϵLdd}, where the infimum again ranges over measurable real-valued estimators based on n observed units, V⋆(P) is the causal oracle value, and the expectation is under the observed marginal law Obs(P).
Appendix: Observable Upper Bound
The prescribed observed-data estimator achieves the uniform squared-error upper bound.
There exist universal constants H0>0, κ>0, 0<C⋆<∞, and an integer D0≥2 such that, for every choice of:
- (Sample size.) An integer n≥1.
- (Alphabet size.) An integer d≥2.
- (Overlap.) A public overlap parameter 0<ϵ≤1/2.
the estimator Vn,d,ϵAF specified in Definition P-7, with these tuning constants, is a measurable, deterministic function of the observed sample. For every family of sampling laws satisfying Assumption A-1 for each P∈Dd,ϵobs, the class of admissible observed laws with public overlap floor ϵ, its squared-error risk for the observed value Ψ(P) defined in Definition P-3 satisfies P∈Dd,ϵobssupEP[{Vn,d,ϵAF−Ψ(P)}2]≤C⋆min{1,nϵLdd},Ld=log(ed).
Appendix: Minimax Lower Bound
Every estimator faces the same worst-case squared-error order over the observed class.
There exists a universal constant c⋆>0 such that, for every sample size n∈N, alphabet size d∈N, and overlap parameter ϵ∈R satisfying
- (Sample size.) n≥1.
- (Alphabet size.) d≥2.
- (Overlap.) 0<ϵ≤1/2.
the minimax squared-error risk Rn,d,ϵ satisfies Rn,d,ϵ≥c⋆min{1,nϵLdd},Ld=log(ed).
Appendix: Consistency Threshold
The joint cell-count and overlap criterion exactly characterizes uniform mean-square consistency, with fixed-parameter specializations.
Let Rn,d,ϵ be the minimax squared-error risk in Definition P-4. Consider sequences (dn)n∈N of alphabet sizes and (ϵn)n∈N of overlap floors satisfying:
- (Integer alphabet.) dn∈N for every n.
- (Alphabet size.) dn≥2 for every n.
- (Positive overlap.) ϵn>0 for every n.
- (Overlap range.) ϵn≤1/2 for every n.
There exists a sequence of measurable real-valued estimators Vn, each based on n independent observed units, such that P∈Ddn,ϵnobssupEP[(Vn−Ψ(P))2]⟶0 if and only if nϵnlog(edn)dn⟶0(n→∞). For each fixed integer d≥2, there exist real constants c,C, depending on d, with 0<c≤C, such that for every integer n≥1 and every overlap floor 0<ϵ≤1/2, cmin{1,nϵ1}≤Rn,d,ϵ≤Cmin{1,nϵ1}. For each fixed overlap floor 0<ϵ≤1/2, there exist real constants c,C, depending on ϵ, with 0<c≤C, such that for every pair of integers n≥1 and d≥2, cmin{1,nlog(ed)d}≤Rn,d,ϵ≤Cmin{1,nlog(ed)d}.