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

In one-bit mean estimation, a central estimator must infer the mean of a distribution based only on binary messages from independent samples. While previous research established that a two-stage adaptive protocol—where an initial localization stage informs subsequent refinement queries—achieves optimal sample complexity, it remained an open question whether this interaction is strictly necessary. This paper addresses the COLT 2026 open problem by determining if a fully non-adaptive protocol, where all queries are fixed before observing any data, can match the optimal adaptive rate.

The authors introduce a randomized, non-adaptive protocol that separates the estimation into localization and refinement stages, both of which are fixed in advance. The key technical innovation is a center-independent fixed-scale refinement construction. By using two independent one-bit samples and pairwise-independent block signs, the protocol forms an exactly conditionally unbiased estimator for each compactly supported component of the mean. The authors then aggregate these components through a multiscale reconstruction, where the variance is controlled by the tail probability at each scale, allowing for efficient estimation without needing to adapt queries to the localization center.

The study demonstrates that interaction is not required for order-optimal one-bit mean estimation. The proposed non-adaptive protocol achieves a sample complexity that matches the known minimax lower bounds for all $k > 1$. Specifically, the complexity scales as $\log(\lambda/\sigma)$ plus a refinement term that depends on the moment order $k$: $(σ/ε)^2$ for $k > 2$, $(σ/ε)^2 \log(σ/ε)$ for $k = 2$, and $(σ/ε)^{k/(k-1)}$ for $1 < k < 2$. This result provides a negative answer to the conjecture that interaction is essential for general queries.