Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel adaptive mean estimator for 1-bit mean estimation using randomized threshold queries, achieving $(\epsilon, \delta)$-PAC guarantees for distributions with bounded means and $k$-th central moments. The estimator achieves order-optimal sample complexity across various tail regimes (values of $k$), matching unquantized minimax lower bounds (up to a localization cost) for $k \neq 2$ and incurring only a logarithmic penalty for $k=2$, which is proven to be a fundamental limit. The work also demonstrates a significant adaptivity gap, showing that non-adaptive estimators require sample complexity that scales linearly with the search space, making them less efficient.
Even with extreme 1-bit constraints, adaptive thresholding can achieve order-optimal sample complexity for mean estimation across diverse tail distributions, outperforming non-adaptive methods by orders of magnitude.
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.