← All papers

Interaction Is Unnecessary for Order-Optimal One-Bit Mean Estimation

Abstract

We resolve the open question of whether interaction is necessary for order-optimal one-bit mean estimation under a finite central moment. Let $\mu\in[-\lambda,\lambda]$ and $\mathbb E|X-\mu|^k\leq\sigma^k$ for fixed $k>1$. We construct a fully nonadaptive protocol whose query list is fixed before any bit is observed and whose sample complexity matches the adaptive one-bit minimax rate in every moment regime. The refinement cost is $(\sigma/\epsilon)^{k/(k-1)}\log(1/\delta)$ for $1<k<2$, $(\sigma/\epsilon)^2\log(\sigma/\epsilon)\log(1/\delta)$ for $k=2$, and $(\sigma/\epsilon)^2\log(1/\delta)$ for $k>2$, plus the optimal $\log(\lambda/\sigma)$ localization cost. The protocol first runs an existing nonadaptive codebook localizer. It then uses only decoding, not new queries, to choose a padded path through a prequeried dictionary of shifted modulo maps. Adjacent modulo remainders have finite-valued differences that are locally constant near the mean. Their variance is therefore charged only to samples that cross a scale-dependent boundary. A dyadic tail identity pays for all scales with one central-moment budget. This removes both the location dependence and the tail aliasing that obstruct global one-shot refinement.

Keywords: one-bit quantization, distributed mean estimation, communication constraints, interactivity, minimax estimation, information constraints

Full text (PDF) · source repository · doi:10.5281/zenodo.21698589