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}.

Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG); Statistics Theory (math.ST)

arXiv:2608.02538 [stat.ML]

(or arXiv:2608.02538v1 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2608.02538 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.