Abstract
In this paper, we study the problem of mean estimation under strict 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is (\epsilon, \delta)-PAC for any distribution with a bounded mean \mu \in [-\lambda, \lambda] and a bounded k-th central moment \mathbb{E}[|X-\mu|^k] \le \sigma^k for any fixed k > 1. Crucially, our sample complexity is order-optimal in all such tail regimes, i.e., for every such k value. For k
eq 2, our estimator's sample complexity matches the unquantized minimax lower bounds plus an unavoidable O(\log(\lambda/\sigma)) localization cost. For the finite-variance case (k=2), our estimator's sample complexity has an extra multiplicative O(\log(\sigma/\epsilon)) penalty, and we establish a novel information-theoretic lower bound showing that this penalty is a fundamental limit of 1-bit quantization. We also establish a significant adaptivity gap: for both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly with the search space parameter \lambda/\sigma, rendering it vastly less sample efficient than our adaptive approach. Finally, we present algorithmic variants that (i) handle an unknown sampling budget, (ii) adapt to an unknown scale parameter~\sigma given (possibly loose) bounds, and (iii) require only two stages of adaptivity at the expense of more complicated general 1-bit queries.
