Universal Refinement without Interaction: Order-Optimal 1-Bit Mean Estimation
2026-07-27 • Information Theory
Information Theory
AI summaryⓘ
The authors show that to estimate an average value accurately with only one-bit (yes/no) answers, you don't need to interact or adaptively question the data. They design a method where all questions are fixed in advance, and the details get refined later during decoding. Their approach works for data with certain statistical properties and matches the best known theoretical limits on how many samples are needed. This solves an open problem about efficient one-bit mean estimation for general queries.
1-bit mean estimationnon-adaptive protocolspublic-coin protocolfinite central momentsminimax optimalitysample complexitylocalization queriesrandom gridsdyadic schemesLau-Scarlett problem
Authors
Yuchen Miao
Abstract
This paper shows that interaction is unnecessary for order-optimal 1-bit mean estimation under finite central moments. For distributions satisfying $|\mathbb{E}X|\leqλ$ and $\mathbb{E}|X-\mathbb{E}X|^k\leqσ^k$ for a fixed $k>1$, we construct a fully non-adaptive public-coin protocol that fixes every measurable 1-bit query before communication. All localization and refinement queries are generated in a single batch; a subsequently decoded coarse center changes only how the stored refinement bits are interpreted. Two complementary constructions realize this decoder-side refinement: a finite dyadic scheme based on periodic residues and a continuous-scale scheme based on shifted random grids. Up to $k$-dependent constants, the refinement cost is $(σ/ε)^2\log(1/δ)$ for $k>2$, $(σ/ε)^2[1+\log(σ/ε)]\log(1/δ)$ for $k=2$, and $(σ/ε)^{k/(k-1)}\log(1/δ)$ for $1<k<2$. Together with the additive localization cost $1+\log(λ/σ)$, these rates answer the Lau--Scarlett open problem for arbitrary measurable 1-bit queries in the affirmative. In the parameter range covered by existing small-error, high-confidence lower bounds, the resulting sample complexity is minimax optimal.