Non adaptive one bit communication matches interactive methods in learning averages
Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
Information TheoryMachine Learning
Summary
This paper looks at a way to estimate the average of some unknown data when each person sharing data can only send back one yes-or-no answer. Usually, more than one round of messages might seem needed to get a good estimate, but the authors show that just one round of fixed questions works just as well. They also study how the complexity of the questions affects how many people you need to ask. Their work helps understand the balance between the simplicity of questions and the number of samples needed to accurately estimate the average.
mean estimation1-bit communicationdistributed learningnon-adaptive protocolsminimax ratesample complexitycentral momentquery functioninterval complexity
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.