Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation

Abstract

This paper is concerned with one-bit mean estimation, where each independent sample is represented by a single binary message. We consider distributions on $\mathbb{R}$ with mean in $[-\lambda,\lambda]$ and absolute $k$-th central moment at most $\sigma^k$, where $k>1$ is fixed. For this class, previous work attained the optimal sample complexity for general queries using a two-stage protocol. The first stage localizes the mean. The second-stage queries are chosen after localization and refine the estimate around the decoded center. We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol that fixes all queries before observing the data and matches the optimal adaptive sample complexity. For target accuracy $\epsilon$ and confidence $1-\delta$, its sample complexity scales as \[ \log\frac{\lambda}{\sigma} + \begin{cases} (\sigma/\epsilon)^2\log(1/\delta),&k>2,\\ (\sigma/\epsilon)^2\log(\sigma/\epsilon)\log(1/\delta),&k=2,\\ (\sigma/\epsilon)^{k/(k-1)}\log(1/\delta),&1<k<2, \end{cases} \] up to constants depending only on $k$. In the range covered by the known lower bound, this rate is minimax optimal even among fully adaptive protocols. This gives a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation with general queries \citep[Open Problem~1]{lau2026open}.