Unsolved

Characterize adaptive distribution classes where two-point rates are attainable

Sourced from the work of Spencer Compton, Gregory Valiant

§ Problem Statement

Setup

Let F\mathcal F be a nonempty class of probability distributions on R\mathbb R such that every PFP\in\mathcal F has finite mean μ(P):=xdP(x)\mu(P):=\int x\,dP(x), and F\mathcal F is translation-invariant in the sense that for every PFP\in\mathcal F and every tRt\in\mathbb R, the translated law PtP_t of X+tX+t (for XPX\sim P) also belongs to F\mathcal F. For P,QP,Q on R\mathbb R, define squared Hellinger distance by

H2(P,Q):=1dPdλdQdλdλ,H^2(P,Q):=1-\int \sqrt{\frac{dP}{d\lambda}\frac{dQ}{d\lambda}}\,d\lambda,

where λ\lambda is any common dominating measure (the value is independent of λ\lambda). For mNm\in\mathbb N, let PmP^{\otimes m} denote the mm-fold product law, and define the local mm-sample Hellinger modulus for mean estimation at PP by

ωH(P,m):=sup{μ(Q)μ(P):QF, H2 ⁣(Pm,Qm)14}.\omega_H(P,m):=\sup\Big\{|\mu(Q)-\mu(P)|:Q\in\mathcal F,\ H^2\!\big(P^{\otimes m},Q^{\otimes m}\big)\le \tfrac14\Big\}.

(Any fixed constant in (0,1)(0,1) in place of 14\tfrac14 is equivalent up to absolute-constant rescaling of sample size.)

Given i.i.d. data X1,,XnPX_1,\dots,X_n\sim P with unknown PFP\in\mathcal F, an estimator is any measurable map μ^n=μ^n(X1,,Xn)R\hat\mu_n=\hat\mu_n(X_1,\dots,X_n)\in\mathbb R.

Unsolved Problem

Determine exactly those translation-invariant classes F\mathcal F for which there exists a single sequence of estimators {μ^n}n2\{\hat\mu_n\}_{n\ge2} and constants C,k,c>0C,k,c>0 such that

supPFEP ⁣[μ^nμ(P)]ωH ⁣(P,max{1,cn})C(logn)kfor all n2.\sup_{P\in\mathcal F}\frac{\mathbb E_P\!\left[\,|\hat\mu_n-\mu(P)|\,\right]}{\omega_H\!\big(P,\max\{1,\lfloor cn\rfloor\}\big)} \le C(\log n)^k \quad\text{for all }n\ge2.

Equivalently, determine necessary and sufficient conditions on F\mathcal F under which adaptive mean estimation over F\mathcal F can match, uniformly over PP, the two-point-testing lower-bound scale given by the local Hellinger modulus, up to polylogarithmic factors.

§ Discussion

Loading discussion…

§ Significance & Implications

Compton & Valiant (2025) gives both positive and negative attainability results for different classes, indicating a nontrivial phase boundary. A full characterization would unify these examples and reveal the structural property that governs whether Le Cam two-point lower bounds are algorithmically achievable in adaptive mean estimation.

§ Known Partial Results

  • Compton et al. (2025): This paper gives a near-attainability result for mixtures of symmetric log-concave distributions with a common mean, and a non-attainability result even for symmetric unimodal distributions. These establish that attainability is class-dependent but do not provide a complete necessary-and-sufficient characterization; the problem appears open.

§ References

[1]

Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation

Spencer Compton, Gregory Valiant (2025)

Annals of Statistics (to appear)

📍 Section 6 (Discussion), Question 1, p. 30: "Characterize adaptive distribution classes where two-point rates are attainable."

Source paper where this problem appears.

§ Tags