Mean Estimation from One-Bit Measurements

Abstract

We consider the problem of estimating the mean of a symmetric log-concave distribution under the constraint that only a single bit per sample from this distribution is available to the estimator. We study the mean squared error as a function of the sample size (and hence the number of bits). We consider three settings: first, a centralized setting, where an encoder may release $n$ bits given a sample of size $n$, and for which there is no asymptotic penalty for quantization; second, an adaptive setting in which each bit is a function of the current observation and previously recorded bits, where we show that the optimal relative efficiency compared to the sample mean is precisely the efficiency of the median; lastly, we show that in a distributed setting where each bit is only a function of a local sample, no estimator can achieve optimal efficiency uniformly over the parameter space. We additionally complement our results in the adaptive setting by showing that \emph{one} round of adaptivity is sufficient to achieve optimal mean-square error.

Accepted for publication in the IEEE Transactions on Information Theory

References in corpus (5)

• On Communication Cost of Distributed Statistical Estimation and Dimensionality
• On Quantizer Design for Distributed Bayesian Estimation in Sensor Networks
• Optimality guarantees for distributed statistical estimation
• Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints
• Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms

Cited by in corpus (3)

• Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms
• Resource Allocation and Dithering of Bayesian Parameter Estimation Using Mixed-Resolution Data
• Gaussian Approximation of Quantization Error for Estimation from Compressed Data