Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation
2026-08-03 • Information Theory
Information TheoryMachine Learning
AI summaryⓘ
The authors study the problem of estimating the average (mean) of a set of numbers when each data point can only be communicated as a single yes/no (one-bit) answer. They focus on distributions with certain constraints on their spread and moments. Previous best methods needed two steps: first roughly finding the average, then refining it adaptively. The authors show that you don't need this back-and-forth; you can choose all questions ahead of time randomly and still get the best possible accuracy with the same number of samples. This solves an open problem by proving interaction is not required for optimal performance.
one-bit mean estimationsample complexityadaptive vs non-adaptivecentral momentsminimax optimalityrandomized protocolsconfidence intervalsorder-optimaldistribution localizationstatistical queries
Authors
Jiachen Hu, Han Zhong
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 $[-λ,λ]$ and absolute $k$-th central moment at most $σ^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 $ε$ and confidence $1-δ$, its sample complexity scales as \[ \log\fracλσ + \begin{cases} (σ/ε)^2\log(1/δ), & k>2,\\ (σ/ε)^2\log(σ/ε)\log(1/δ), & k=2,\\ (σ/ε)^{k/(k-1)}\log(1/δ), & 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}.