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|\le \hat{I}»$ and $\mathbb{E}|X-\mathbb{E}X{|}^k\le \ddot{I}{ƒ}^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 $(\ddot{I}ƒ/\hat{I}\mu {)}^2\log (1/\hat{I}´)$ for $k>2$, $(\ddot{I}ƒ/\hat{I}\mu {)}^2[1+\log (\ddot{I}ƒ/\hat{I}\mu )]\log (1/\hat{I}´)$ for $k=2$, and $(\ddot{I}ƒ/\hat{I}\mu {)}^{k/(k-1)}\log (1/\hat{I}´)$ for $1<k<2$. Together with the additive localization cost $1+\log (\hat{I}»/\ddot{I}ƒ)$, 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.

22 pages, 4 figures