Unsolved

Remove polylogarithmic slack in attainable two-point rates

Sourced from the work of Spencer Compton, Gregory Valiant

§ Problem Statement

Setup

Let F\mathcal{F} be the class of all probability distributions PP on R\mathbb{R} such that PP has a density of the form

p(x)=Θgθ(xμ)dΠ(θ),p(x)=\int_{\Theta} g_\theta(x-\mu)\,d\Pi(\theta),

where μR\mu\in\mathbb{R}, Π\Pi is a probability measure on an index set Θ\Theta, and for every θΘ\theta\in\Theta, gθg_\theta is a probability density on R\mathbb{R} that is symmetric and log-concave about 00 (equivalently, gθ(t)=gθ(t)g_\theta(t)=g_\theta(-t) for all tt, and loggθ\log g_\theta is concave on its support). Then each component has mean 00, so μ(P):=EP[X]=μ\mu(P):=\mathbb{E}_P[X]=\mu is well-defined. In the adaptive estimation model, one observes X1,,Xni.i.d.PX_1,\dots,X_n \stackrel{\mathrm{i.i.d.}}{\sim} P with unknown PFP\in\mathcal{F}, and an estimator is any measurable map μ^n:RnR\hat\mu_n:\mathbb{R}^n\to\mathbb{R}.

For distributions P,QP,Q on R\mathbb{R}, define squared Hellinger distance by H2(P,Q):=12(dP/dνdQ/dν)2dνH^2(P,Q):=\frac12\int(\sqrt{dP/d\nu}-\sqrt{dQ/d\nu})^2\,d\nu, where ν\nu dominates both PP and QQ. For mNm\in\mathbb{N}, define the local Hellinger modulus at PP by

ωH(P,m):=sup{μ(Q)μ(P):QF, H ⁣(Pm,Qm)13}.\omega_H(P,m):=\sup\left\{|\mu(Q)-\mu(P)|:Q\in\mathcal{F},\ H\!\left(P^{\otimes m},Q^{\otimes m}\right)\le \frac13\right\}.

(The constant 1/31/3 can be replaced by any fixed number in (0,1)(0,1) at the cost of universal constant changes.)

Unsolved Problem

Does there exist an estimator sequence (μ^n)n1(\hat\mu_n)_{n\ge1} and universal constants C,c>0C,c>0 such that for every n1n\ge1 and every PFP\in\mathcal{F},

EP ⁣[μ^nμ(P)]CωH ⁣(P,cn),\mathbb{E}_P\!\left[|\hat\mu_n-\mu(P)|\right]\le C\,\omega_H\!\left(P,\lfloor c n\rfloor\right),

with no extra multiplicative polylogarithmic factor (for example, no factor of the form (logn)k(\log n)^k)?

§ Discussion

Loading discussion…

§ Significance & Implications

The paper’s benchmark is near-attainment up to polylogarithmic factors, leaving open whether exact constant-factor attainability is possible. Resolving this would clarify whether the remaining gap is information-theoretic or an artifact of current methods. This entry treats the question as open based on the cited source.

§ Known Partial Results

  • Compton et al. (2025): The paper gives a near-linear-time, parameter-free estimator with guarantees matching the two-point modulus up to polylogarithmic factors over a broad log-concave-mixture location class; it does not claim exact constant-factor matching. Open-status annotation here is dated 2026-02-17 and may be outdated without a dedicated follow-up literature check.

§ References

[1]

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

Spencer Compton, Gregory Valiant (2025)

Annals of Statistics (to appear)

📍 arXiv:2502.05730v3, Section 6 (Discussion), open-questions paragraph on removing polylogarithmic slack in adaptive attainability (see the explicit open-question statement in that section).

Source paper where this problem appears.

§ Tags