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

In this paper, we study the problem of mean estimation under 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 (ε, δ)-PAC for any distribution with a bounded mean μ ∈ [-λ, λ] and a bounded k-th central moment mathbbE[|X-μ|k] ≤ σk for any fixed k > 1. Moreover, 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(λ/σ)) localization cost. For the finite-variance case (k=2), our estimator's sample complexity has an extra multiplicative O(log(σ/ε)) 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 λ/σ, 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 σ given (possibly loose) bounds, (iii) require only two stages of adaptivity to achieve order-optimal sample complexity at the expense of more general 1-bit queries, and (iv) leverage multiple local samples per 1-bit query to proportionally reduce communication costs.