Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query Q: ℝ→0,1 chosen by a central learner. The distribution has mean in [-λ,λ] and k-th central moment at most σk, for a fixed k>1. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every k>1, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set Q-1(1) is restricted to a union of at most s intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order (λσ/(svarepsilon2))log(1/δ), giving the full tradeoff between sample complexity and interval complexity to within k-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.