Non-adaptive one-bit communication matches adaptive mean estimation rates
Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
Information TheoryMachine Learning
Summary
Estimating the average value of data from many sources can be tricky when each source can only send a simple yes-or-no answer (one bit). Previous methods improved accuracy by asking questions in multiple rounds, using earlier answers to guide later questions. This paper shows that it is just as good to decide all questions ahead of time without adapting, even with the one-bit limit. They also analyze how the shape of the questions (intervals on the number line) affects how many samples are needed to get a good estimate.
What this means in practice
- •For data engineers: Design distributed systems that estimate averages efficiently using fixed 1-bit queries without multiple interaction rounds.
- •For sensor network designers: Build sensor querying schemes that meet tight communication constraints by limiting query shapes while maintaining sample efficiency.
A theory result. No direct application yet.
Authors
Ivan Lau, Jonathan Scarlett
Abstract
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: \mathbb{R}\to\{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 $(λσ/(s\varepsilon^2))\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.