Minimax Optimal Procedures for Locally Private Estimation

1 Introduction

• The paper develops private analogues of Le Cam’s, Fano’s, and Assouad’s methods, pairing minimax lower bounds with matching upper bounds from specific private procedures.These techniques support results for mean, median, high-dimensional and sparse sequence, generalized linear model, and density estimation.Source: §1 · p. 2, §1.1 · p. 3
• The introduction motivates differential privacy as a formal disclosure-limiting framework and emphasizes local privacy, where data providers do not trust the statistician.Local privacy is presented as a stringent but important setting for minimax risk analysis, with roots in Warner’s randomized-response formulation.Source: §1 · p. 2
• The paper addresses conflicting views of differential privacy by quantifying when privacy constraints impose statistical costs and when optimal procedures retain efficient estimation.Prior work includes criticism that private data release can perform poorly and results showing asymptotically optimal rates for some non-local private estimators.Source: §1 · p. 2

1.1 Our contributions

• Local differential privacy is studied through minimax risk to characterize optimal estimation rates as functions of privacy and problem parameters.The framework treats privacy as an abstract estimator constraint, independent of particular procedures or mechanisms.Source: §1 · p. 1, §1.1 · p. 2
• Optimal mechanisms can outperform widely used private procedures while preserving the same privacy guarantee and computational requirements.For drug-use proportion estimation, the theory-identified mechanism achieves roughly a five-fold reduction in mean-squared error relative to Laplace noise addition.Source: §1.1 · pp. 2–3, Figure 1 · p. 3

2.1 Classical minimax framework

• The classical framework models a distribution class P, parameter functional θ(P) in Θ, semi-metric error ρ, and nondecreasing loss Φ with Φ(0)=0.The parameter space depends on the problem, such as real-valued means or spaces of densities.Source: §2.1 · p. 4
• Given i.i.d. observations from P, estimators are measurable functions of the sample and are evaluated by risk; squared absolute error yields mean-squared error for univariate means.The classical minimax risk takes the supremum over P and infimum over estimators.Source: §2.1 · pp. 4–5

2.2 Local differential privacy

• Local privacy transforms each raw observation through a conditional privacy mechanism, potentially sequentially interactive, before estimation uses the privatized data.In the non-interactive case, each privatized observation depends only on its corresponding raw observation; interactive dependence can aid stochastic approximation and optimal estimators.Source: §2.2 · p. 5
• An α-DLP view requires the conditional probability of every output event under any two inputs, given prior outputs, to differ by at most exp(α).A mechanism is α-DLP when every privatized variable satisfies this condition.Source: §2.2 · pp. 5–6
• Small α makes distinguishing two possible raw values difficult, with any equal-prior test approaching random guessing; randomized response attains disclosure error 1/(1 + e^α) in the binary case.The section relates this interpretation to Warner’s randomized response mechanism.Source: §2.2 · p. 6

2.3 α-private minimax risks

• The α-private minimax risk restricts estimators to privatized observations and optimizes over α-LDP mechanisms to characterize the best estimation rate as a function of α.The mechanism class Qα contains all conditional distributions satisfying the α-LDP property.Source: §2.3 · p. 7
• As α →+∞, the privacy constraint becomes vacuous and the α-private minimax risk reduces to classical minimax risk, while the paper focuses primarily on α ∈(0, 1].These values correspond to reasonable disclosure-risk levels as illustrated by the privacy interpretation.Source: §2.3 · p. 7

3 Bounds on pairwise divergences: Le Cam’s bound and variants

• The section begins from classical two-point testing and develops private lower bounds together with new optimal procedures for one-dimensional mean and median estimation.The private results are presented as analogues of Le Cam’s classical method.Source: §3 · p. 7, §3.1 · pp. 7–8

3.1 A private version of Le Cam’s bound

• The private Le Cam bound applies to α-locally private observations and reduces the effective sample size from n to at most 4α²n for α ∈[0, 23⁄35].It provides sharp α-private minimax lower bounds and follows from the KL contraction results.Source: §3.1 · p. 8

3.2.2 One-dimensional median estimation

• For median estimation, the minimax error retains parametric scaling with effective sample size α²n, and a private projected stochastic-gradient procedure attains the upper bound.The procedure is essentially a sequential variant of randomized response and is reported to outperform more naive estimators in salary experiments.Source: §3.2 · p. 8, §3.2.2 · pp. 10–11

3.2 Some applications of the private Le Cam bound

• The private Le Cam framework covers mean, median, and conditional-probability estimation, with bounds stated for α ∈[0,1] and extended up to universal constant privacy levels.The applications illustrate distinct privacy effects, including polynomially smaller effective sample sizes for some mean-estimation models and α²n scaling for medians.Source: §3.2 · p. 8

3.2.1 One-dimensional mean estimation

• For one-dimensional mean estimation, the α-private minimax risk is 1/(nα²) when k=2 and scales as (nα²)^−k/(k+1) generally, reaching (nα²)^−1 under bounded support.A truncated Laplace mechanism achieves the upper bound, while privacy is more restrictive for unbounded domains than for bounded ones.Source: §3.2.1 · p. 9

3.3 Pairwise upper bounds on Kullback-Leibler divergences

• Theorem 1 shows that local differential privacy contracts pairwise distributions through a total-variation-dependent KL bound, even making induced KL finite when the original KL is infinite.This contraction underlies the section’s minimax lower bounds and extends to sequentially interactive channels through a tensorization inequality.Source: §3.3 · pp. 11–12

4 Bounds on private mutual information: Fano’s method

• The classical Fano framework is generalized from separated parameter families to neighborhood sizes and separation functions, providing the information-theoretic basis for the private results.The construction considers a uniformly distributed index and samples drawn conditionally from the corresponding distribution family.Source: §4 · p. 13

4.1 A private version of Fano’s method

• Private Fano’s method lower bounds non-interactive α-private minimax risk for 2δ-separated distribution families through a variational mutual-information bound.The method applies to privatized samples generated by a non-interactive channel and optimizes over uniformly bounded functions.Source: §4.1 · pp. 13–14

4.2 Some applications of the private Fano bound

• The applications establish sharp α-private minimax characterizations for compactly supported d-dimensional and 1-sparse mean estimation using private Fano lower bounds and direct mechanism analysis for upper bounds.The compact-support restriction addresses difficulties with differential privacy on non-compact spaces.Source: §4.2 · p. 14, §4.2.3 · p. 16

4.2.1 Classical mean estimation in d dimensions

• For d-dimensional means supported on ℓp-balls with p ∈ [1, 2], privacy imposes a multiplicative d/α^2 mean-squared-error penalty and reduces effective sample size to α^2n/d.For p = 2, the lower-bound scaling matches the upper bound; for large n, both bounds scale as d/(nα^2) across p ∈ [1, 2].Source: §4.2.1 · p. 15

4.2.2 Estimation of high-dimensional sparse vectors

• For 1-sparse means, local privacy makes estimation impossible when d ≥ n, contrasting with the non-private regime where sparsity permits d ≍ e^n.The non-interactive result leaves open whether modifying the privatizing mechanism can enable localization after important variables are identified.Source: §4.2.2 · pp. 15–16

4.2.3 Optimal mechanisms: attainability for mean estimation

• The optimal mean-estimation mechanisms are unbiased α-private views tailored to ℓ2- and ℓ∞-ball geometry, and their associated estimators attain the minimax rates.The procedures are efficiently implementable by rejection sampling; the Laplacian mechanism is suboptimal in d dimensions because it incurs quadratic rather than linear dimension dependence.Source: §4.2.3 · pp. 16–17

4.3 Variational bounds on private mutual information

• The variational bound is no weaker up to constants than the earlier mutual-information bound and can be stronger because it avoids interchanging supremum and summation.For non-interactive product samples, the result extends through the mutual-information chain rule and conditional independence.Source: §4.3 · pp. 18–19

5.1 A private version of Assoud’s method

• The private Assouad bound applies to any locally differentially private channel, including interactive settings, under a coordinate-wise Hamming-separation condition.Its proof relies on a variational quantity that jointly handles multiple distribution mixtures.Source: §5.1 · p. 20

5.2 Some applications of the private Assouad bound

• Proposition 3 yields sharp α-private minimax characterizations for problems with natural coordinate-wise structure, including generalized linear models and nonparametric density estimation.The Hamming-separation requirement is common in such estimation problems, and the result applies to interactive channels Q.Source: §5.2 · p. 20

5.2.1 Generalized linear model estimation under local privacy

• Local privacy enables asymptotically minimax-optimal GLM estimation through unbiased noisy stochastic gradients and interactive stochastic gradient descent.The construction leverages optimal mean-estimation mechanisms, while logistic-regression lower bounds show the convergence guarantee cannot generally be improved.Source: §5.2.1 · pp. 21–22
• In this model, locally private estimation has sample-size degradation n 7→n(eα−1)2, and the estimators achieve this rate, while the minimax lower bound is local for parameters shrinking to θ⋆=0.Source: §5.2.1 · p. 23

5.2.2 Density estimation under local privacy

• Local privacy changes the nonparametric density-estimation exponent from 2β/(2β +1) to 2β/(2β +2), degrading Lipschitz-density rates from n−2/3 to n−1/2.Orthogonal-series estimators with the proposed privacy mechanism achieve the sharp minimax bound for all β ≥1, whereas direct Laplace perturbation is suboptimal.Source: §5.2.2 · pp. 24–25

5.3 Variational bounds on paired divergences

• The variational-bound framework indexes product distributions by a Boolean hypercube and defines paired and marginal mixtures for bounding symmetrized divergences.These constructions provide the theorem underlying the variational inequality used in Proposition 3’s minimax lower bound.Source: §5.3 · p. 26
• Theorem 3 establishes variational bounds for multiple paired divergences under any α-locally differentially private channel.Source: §5.3 · p. 26
• Theorem 3 generalizes Theorem 1 from d = 1, while requiring the supremum to remain outside the summation for sharp results.Source: §5.3 · p. 26
• Combining the non-private Assouad inequality with Theorem 3 yields Proposition 3 for locally private channels.Source: §5.3 · p. 26
• Pinsker’s inequality and Cauchy-Schwarz provide an intermediate bound that applies when Pν induces a 2δ-Hamming separation for Φ ◦ρ.Source: §5.3 · p. 26

6 Experiments

• The experiments use three publicly available sensitive datasets as proxies for evaluating privacy-preserving mechanisms and estimation schemes.The public datasets also make the experimental data freely available.Source: §6 · p. 27

6.1.1 Mean salary estimation

• For heavy-tailed salaries, choosing moment k ≈ 3 substantially improves mean estimation, whereas k < 2 converges too slowly and k = ∞ has excessive variance and radius.The experiments use 2010 University of California salaries, whose population contains 252,540 employees and has long tails.Source: §6.1 · p. 27, §6.1.1 · p. 28
• At α = 1, private mean estimation incurs approximately 6% average error, versus .2% for a non-private estimator observing half the population.These results use the best post-hoc moment choice at each privacy level, including α = ∞ for no privacy.Source: §6.1.1 · p. 28, Table 1 · p. 28

6.1.2 Median salary estimation

• Figure 6 compares private stochastic gradient descent with a naive noisy-truncated median estimator across sample sizes and assumed median-radius values.The SGD curve is lower than the naive estimator in the plotted comparisons for α = 1.Source: §6.1.2 · p. 28, Figure 6 · p. 29

2. We compute the naive private median (41) with Wi

• For private median estimation, minimax-optimal SGD substantially outperforms the naive estimator, by approximately a factor of 6 even when r = 2 med(P), and achieves mean performance below 1.The non-private stochastic gradient estimator has error approximately 0.25, while private SGD’s relative error is at most 4 · 10−5 for all radii tested.Source: §2 · pp. 29–30

6.2 Drug use and hospital admissions

• For drug-use proportions, the minimax optimal ℓ∞-sampling strategy outperforms equally private Laplace noise addition; its mean error is roughly d ≈ 5 times lower.The NEDREDV dataset contains N = 959,715 emergency-department visits from 2004 and includes d = 27 common drugs.Source: §6.2 · pp. 30–31

6.3 Censorship, privacy, and logistic regression

• In logistic regression, the ℓ2-optimal randomized-response strategy dominates naive Laplace noise addition, although privacy degrades classification more substantially at d ≈450 than at d = 24.The Laplace mechanism is essentially random guessing in the higher-dimensional case, while the optimal ℓ2-mechanism performs similarly across dimensions; non-private estimation remains best.Source: §6.3 · pp. 31–32, Figure 7 · p. 32

7 Conclusions

• The main contribution links minimax statistical decision theory with differential privacy through divergence inequalities that contract distributions and generalize Le Cam, Fano, and Assouad lower bounds.These results yield sharp minimax estimation rates under local privacy.Source: §7 · p. 32
• The framework shows that privacy is costly when a distribution family is poorly correlated with every binary-valued function, because the contraction becomes strong.The examples in Sections 4.2, 5.2.1, and 5.2.2 instantiate this framework.Source: §7 · p. 32
• Sharp convergence rates across standard estimation procedures reveal a continuum for trading local privacy against accurate statistical utility.This continuum allows procedures to be adjusted to the privacy or utility needs of statisticians and sampled populations.Source: §7 · p. 32
• The results leave open whether Corollary 3 can be tensorized for interactive mechanisms, potentially using directed information for channels with feedback.They also raise extensions to standard non-local differential privacy and other disclosure-limitation models.Source: §7 · p. 32
• Several results are pessimistic: differential privacy may cause substantial inferential-accuracy losses, particularly in high-dimensional settings.This motivates mechanisms that preserve differential privacy’s strengths while reducing its adverse effects on inference.Source: §7 · p. 33

A Proof of Theorem 1 and related results

• The proof appendix collects the main-result proofs, beginning with Theorem 1.Theorem 1’s proof represents the marginal distributions and privacy channels with densities, then bounds their difference and log-density ratio using two auxiliary lemmas.Source: A Proof of Theorem 1 and related results · p. 37, §A.1 · p. 37

A.1 Proof of Theorem 1

• The theorem proof combines Lemmas 3 and 4, applies Lemma 3 to the numerator, and concludes because the final integral is at most one.Lemma 3 applies to any α-locally differentially private channel and uses cα = min{2, eα}.Source: §A.1 · pp. 37–38

A.2 Proof of Corollary 3

• A.2 defines the induced marginal distribution of each privatized variable Z_i conditional on prior outputs.The proof introduces the conditional marginal M_ν^(i)(· | z_1:i−1), integrating over X_i.Source: §A.2 · p. 39
• A.2 applies the KL chain rule to express the divergence between induced distributions through integrated conditional divergences.The argument uses a shorthand for the integrated KL divergence of the conditional Z_i distributions.Source: §A.2 · p. 39
• A.2 invokes α-differential privacy and Theorem 1 to bound the conditional-output divergence using the conditional distribution of X_i given the packing index.The mechanism distribution Q_i(· | X_i, Z_1:i−1) is treated as α-differentially private for X_i.Source: §A.2 · p. 39
• A.2 combines these steps to obtain the claimed result for Corollary 3.The conclusion follows after applying the privacy-based divergence bound and the conditional-independence simplification.Source: §A.2 · p. 39
• A.2 simplifies the conditional law of X_i because the samples are conditionally independent given the packing index V = ν.Thus P_ν^(i)(· | z_1:i−1) equals the unconditional conditional-on-index distribution P_ν^(i).Source: §A.2 · p. 39

B Proof of minimax bounds associated with Le Cam’s method

• B collects proofs of the paper’s minimax lower bounds for specific problems in Section 3.This appendix section concerns lower bounds associated with Le Cam’s method.Source: B Proof of minimax bounds associated… · p. 39

B.1 Proof of Corollary 1

• The mean-rate proof separates lower and upper bounds, establishing the result for α ∈(0, 1] while noting analogous results for finite α.The lower-bound argument uses Le Cam’s method, and the upper-bound argument combines truncation with Laplacian noise.Source: §B.1 · pp. 39–40
• The mean lower bound uses Le Cam’s method on a three-point family whose mean gap is 2δ.The construction enforces E[|X|^k] = 1 and applies Pinsker’s inequality and Corollary 3 to the privatized samples.Source: §B.1 · p. 40
• The mean upper bound privatizes each truncated observation by adding Laplace noise, with Zi := [Xi]T + Wi and Wi drawn independently.The resulting Zi is α-differentially private for Xi, and the estimator is formed from the privatized observations.Source: §B.1 · p. 40
• Choosing T = (nα2)1/(2k) yields the upper bound in equation (9).The truncation controls the moment-based bias while the Laplace perturbation contributes the privacy-dependent error.Source: §B.1 · pp. 40–41

B.2 Proof of Corollary 2

• The median lower bound uses two-point distributions with medians r and −r, reducing estimation to testing through gaps in function values.The proof then applies Pinsker’s inequality and Corollary 3 for α ≤1.Source: §B.2 · p. 41

C Proof of Theorem 2 and related results

• Section C collects the proof of Theorem 2 together with related corollaries.The supplied passage states the section’s scope but does not provide further proof details.Source: C Proof of Theorem 2 and related results · p. 41

C.1 Proof of Theorem 2

• Theorem 2 is proved by reducing arbitrary output spaces to finite partitions, expressing the mechanism through probability mass functions, and taking a supremum over partition sizes.The proof invokes the characterization of KL divergence through finite partitions and recovers the general case after establishing the finite-range claim.Source: §C.1 · p. 42
• Local differential privacy constrains the conditional mass functions through the lower envelope m0, enabling a shifted function class bounded by (e^α −1)m0.The proof identifies q(z | x) with the privacy-controlled function class and uses constant shifts by m0(z) to obtain the stated bound.Source: §C.1 · p. 42
• The resulting bounds establish Theorem 2 after summing the m0 terms and using z m0(z) ≤1.The appendix concludes by combining the preceding inequalities to obtain the theorem’s stated result.Source: §C.1 · p. 43

C.2 Proof of Inequality (22)

• Inequality (22) follows in the non-interactive setting by using product structure, conditional independence, and the mutual-information chain rule after assuming finite output range.Conditioning reduces entropy, while conditional independence removes the conditioning on prior outputs; Theorem 2 then completes the argument.Source: §C.2 · p. 43

D Proofs of multi-dimensional mean-estimation results

• Multidimensional mean-estimation proofs first reduce estimation to testing among indices in a subset V of R^d using inequality (19).The remaining proof work focuses on constructing packings and controlling testing information.Source: D Proofs of multi-dimensional… · p. 44
• The packing step constructs a well-separated V whose cardinality relative to neighborhood size N_δ is sufficiently large for separation δ.This geometric condition is the key problem-specific requirement in the second proof step.Source: D Proofs of multi-dimensional… · p. 44
• The final step applies Theorem 2 and inequality (22), bounding their supremum through the operator norm of Cov(V) under uniform sampling.The generalized Fano reduction permits a sampling scheme that keeps Cov(V) relatively small, enabling the information bound.Source: D Proofs of multi-dimensional… · p. 44

D.1 Proof of Corollary 4

• D.1 constructs a k-dimensional hypercube family whose mean vectors form a 2t/k-separated ℓ2 packing with log-cardinality at least max{k/6, 2}.The construction embeds Vk = {−1, 1}k into Rd and defines distributions supported in the ℓ1 ball.Source: §D.1 · pp. 44–45
• D.1 combines the packing with mutual-information bounds for non-interactive α-local privacy and private Fano testing to derive the mean-estimation minimax lower bound.The proof chooses t = k/6 and then optimizes over an integer k near the privacy- and sample-size-dependent quantity.Source: §D.1 · p. 45

D.1.1 An alternative lower bound for Corollary 4

• D.1.1 replaces the single-coordinate construction with a denser hypercube distribution supported on {−1/k1/p, 1/k1/p}k × {0}d−k, preserving unit ℓp norm.The construction fixes p ∈ [1, 2] and defines coordinate probabilities through the hypercube parameter ν and δ.Source: §D.1.1 · p. 46
• D.1.1 obtains a 2t/k1/p-separated ℓ2 packing with log-cardinality at least max{k/6, 2}, then applies Lemma 6 and private Fano testing to recover the corollary.The argument selects k = max{1, min{d, n(eα − 1)2}} and combines the resulting bound with inequality (50).Source: §D.1.1 · pp. 46–47

D.2 Proof of Corollary 5

• D.2 proves the sparse lower bound using the packing V = {±ej}d, whose mean vectors are 1-sparse and form a 2δr ℓ2 packing, also yielding a δr ℓ∞ packing.The proof bounds mutual information for non-interactive α-differential privacy and applies Fano’s inequality with t = 0.Source: §D.2 · pp. 47–48
• D.2 establishes the matching sparse upper bound with the sampling strategy (26) and an ℓ1-regularized estimator for an s-sparse true mean.The analysis uses coordinatewise concentration and selects λ to obtain the claimed minimax upper bound, including the displayed d log d/n term.Source: §D.2 · p. 48

D.3 Proof of inequality (24)

• D.3 proves inequality (24) by combining a Varshamov–Gilbert hypercube packing of size at least exp(d/8), Laplace sampling, and private Fano’s inequality.The argument uses point-mass distributions and takes δ2 = d2/(48nα2), assuming d ≥ 10 without loss of generality.Source: §D.3 · pp. 48–49

• Conditional independence in Figure 2 establishes the marginalization identity needed for the proof’s tensorization steps.The identity uses conditional independence in Q and independence of X_i and Z_1:i−1 under P_±j.Source: E Proof of Theorem 3 · pp. 49, 51
• The proof applies the KL chain rule to conditional distributions, sums the resulting divergences over j, and bounds the terms T_j,i.The chain-rule step is explicitly identified as analogous to the proof of Corollary 3 [29, Chapter 5].Source: E Proof of Theorem 3 · pp. 49–50
• An infimal measure lower-bounds the pairwise conditional mass functions, enabling the proof to control the divergence terms via Lemma 4.The argument assumes finite Z without loss of generality and uses m_0(z | z_1:i−1) ≤ min{m_+j(z | z_1:i−1), m_−j(z | z_1:i−1)}.Source: E Proof of Theorem 3 · p. 50
• Differential privacy bounds the remaining supremum, rescaling by (e^α −1), and substitution completes the proof.The final step uses that m_0 sums to at most one.Source: E Proof of Theorem 3 · pp. 50–51

Proof strategy

• The proof first reduces logistic-regression estimation to a multiple binary hypothesis-testing problem using a sharper version of Assouad’s method.This reduction provides Hamming separation for the squared-error loss.Source: F Proof of logistic regression lower… · p. 52

Privacy-based testing bound

• Theorem 3, applied through inequality (40), controls the binary testing error after bounding suprema involving covariance structures of randomly selected elements of {−1, 1}^d.The symmetry of the testing problems simplifies these bounds and yields the lower bound in Corollary 6.Source: F Proof of logistic regression lower… · p. 52

Logistic-model construction

• The constructed alternatives set θ_ν = δν for ν ∈ {−1, 1}^d and define a base distribution whose conditional model is standard logistic regression.Under this construction, θ_ν is the population logistic-loss optimizer, and coordinate signs of an estimator induce the associated binary decisions.Source: F Proof of logistic regression lower… · p. 52

Symmetry calculation

• The remaining variational bound follows by conditioning on all coordinates except one, applying Jensen’s inequality and symmetry, and using orthogonality with standard matrix inequalities.This establishes inequality (56), which supplies the quantity needed to complete the lower-bound derivation.Source: F Proof of logistic regression lower… · pp. 53–54

G.1 Proof of the lower bound (36)

• The density-estimation lower bound uses smooth bump-function densities indexed by hypercube corners, enabling Assouad’s lemma through Hamming separation.The construction keeps the densities in a trigonometric Sobolev class and uses a local packing suited to privacy-induced information contraction.Source: §G.1 · pp. 54–56
• For α ≤1, the privacy-aware KL bound scales as cnα^2/k^(2β+1), improving the standard n/k^(2β) divergence bound by roughly a factor of k.Choosing k appropriately completes the minimax lower-bound proof.Source: §G.1 · p. 56

G.2 Proof of the upper bound (36)

• The matching upper bound expands densities in Fourier coordinates, controls the mean-squared L2 error, and chooses k = (nα^2)^(1/(2β+2)).The resulting error bound depends on constants B0, ck, and r.Source: §G.2 · pp. 56–57

H Information bounds; H.1 Proof of Lemma 5; H.2 Proof of Lemma 6; H.3 Proof of Lemma 7

• The information-bound appendices prove mutual-information and KL-divergence bounds by applying Theorem 2 to hypercube sets, assuming r = 1, identifying functions with finite-dimensional vectors, and using covariance and an operator norm equal to 2.Source: H Information bounds · p. 57, §H.1 · p. 57, §H.2 · p. 58

H.4 Proof of Lemma 9

• Lemma 9 reduces the supremum in the divergence bound to functions constant on a partition of [0,1], yielding a finite-dimensional optimization over R^(2k).Krein–Milman and convexity restrict attention to extreme-point functions taking values in {−1,1}.Source: §H.4 · pp. 59–61

I Technical arguments; I.1 Proof of Lemma 1

• The technical proof of Lemma 1 converts estimator separation into testing errors by averaging over mixtures and then taking an infimum over testing procedures.This supplies the Assouad-style reduction used in the lower-bound argument.Source: §I.1 · pp. 61–62

I.2 Proof of unbiasedness for sampling strategy (25)

• The appendix establishes unbiasedness of sampling strategy (25) by rotational symmetry and spherical-coordinate integration over a half-ball.The calculation applies first to v = e1 and then extends by scaling and rotational symmetry.Source: §I.2 · pp. 62–63
• For α ≤1, Stirling’s approximation and the bound (e^α + 1)/(e^α − 1) ≤3/α imply that the sampling output satisfies ∥Z∥2 ≤4r.This provides the norm control required by the sampling-based technical arguments.Source: §I.2 · p. 63

Odd-dimensional case

• Using Corollary 3.7 of Duchi et al., the proof computes conditional expectations for sampling strategy (26), assuming z and x lie in {−1, 1}^d.The general result follows by scaling, and the odd-dimensional case uses symmetry and the 2^(d−1) vectors with positive inner product.Source: §I.3 · p. 63

Even-dimensional case

• For even d, the proof accounts for vectors satisfying ⟨z, x⟩=0, whose inclusion makes the relevant nonnegative-inner-product set have cardinality 2^(d−1)+1.The even-dimensional conditional-expectation calculation follows from this adjusted counting argument.Source: §I.3 · pp. 63–64

Unbiasedness conclusion

• Inverting the constant multipliers on x in the preceding equations shows that sampling strategy (26) is unbiased.This conclusion applies after combining the odd- and even-dimensional calculations.Source: §I.3 · p. 64