Universal Refinement without Interaction: Order-Optimal 1-Bit Mean Estimation

Abstract

This paper shows that interaction is unnecessary for order-optimal 1-bit mean estimation under finite central moments. For distributions satisfying $|\mathbb{E}X|\leq\lambda$ and $\mathbb{E}|X-\mathbb{E}X|^k\leq\sigma^k$ for a fixed $k>1$, we construct a fully non-adaptive public-coin protocol that fixes every measurable 1-bit query before communication. All localization and refinement queries are generated in a single batch; a subsequently decoded coarse center changes only how the stored refinement bits are interpreted. Two complementary constructions realize this decoder-side refinement: a finite dyadic scheme based on periodic residues and a continuous-scale scheme based on shifted random grids. Up to $k$-dependent constants, the refinement cost is $(\sigma/\epsilon)^2\log(1/\delta)$ for $k>2$, $(\sigma/\epsilon)^2[1+\log(\sigma/\epsilon)]\log(1/\delta)$ for $k=2$, and $(\sigma/\epsilon)^{k/(k-1)}\log(1/\delta)$ for $1<k<2$. Together with the additive localization cost $1+\log(\lambda/\sigma)$, these rates answer the Lau--Scarlett open problem for arbitrary measurable 1-bit queries in the affirmative. In the parameter range covered by existing small-error, high-confidence lower bounds, the resulting sample complexity is minimax optimal.