Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes

arXiv:2604.07796v1 Announce Type: new
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 neq 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.