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

Researchers Ivan Lau and Jonathan Scarlett have introduced a groundbreaking algorithm for statistical mean estimation that operates under extreme communication constraints. Their sequential estimator requires only 1-bit responses—simple yes/no answers indicating whether each data sample exceeds an adaptively chosen threshold. This approach achieves what they term "order-optimal" sample complexity for any distribution with a bounded mean and bounded k-th central moment (k>1), meaning it performs as well as theoretically possible given these constraints.

For distributions where k≠2 (non-Gaussian tails), their estimator's sample complexity matches the fundamental lower bounds for unquantized estimation plus an unavoidable O(log(λ/σ)) localization cost. However, for the common finite-variance case (k=2), they discovered a fundamental limitation: 1-bit quantization imposes an extra O(log(σ/ϵ)) multiplicative penalty, which they prove is unavoidable through novel information-theoretic lower bounds.

The research reveals a dramatic "adaptivity gap"—non-adaptive estimators must sample linearly with the search space parameter λ/σ, making them vastly less efficient than their adaptive approach. The authors also present practical variants that handle unknown sampling budgets, adapt to unknown scale parameters using loose bounds, and achieve similar performance with only two stages of adaptivity using more complex 1-bit queries. This work bridges theoretical statistics with practical constraints in distributed sensing and federated learning where communication bandwidth is severely limited.