Mean Estimation from One-Bit Measurements
This work addresses efficient statistical estimation under severe communication or storage constraints, with incremental contributions to adaptive and distributed estimation theory.
The paper tackles the problem of estimating the mean of a symmetric log-concave distribution using only one-bit measurements per sample, analyzing mean squared error across centralized, adaptive, and distributed settings. It shows no asymptotic penalty in centralized settings, optimal efficiency matching the median in adaptive settings with one round of adaptivity, and impossibility of uniform optimal efficiency in distributed settings.
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.