Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
2026-07-03 • Information Theory
Information TheoryMachine Learning
AI summaryⓘ
The authors investigate how to best estimate the average of some data using only very limited (1-bit) information. They show that adapting queries step-by-step (interaction) helps reach the best possible accuracy, but only one adjustment in the process is needed. They also explore whether doing all queries without any adaptation can be just as good, but this question remains unanswered. Essentially, the study focuses on when and how limited interaction affects the best achievable estimation accuracy.
1-bit mean estimationnonparametric statisticsadaptive queryingminimax ratethreshold queriesquantizersnon-adaptive protocolsfinite-moment classes
Authors
Ivan Lau, Jonathan Scarlett
Abstract
We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.e., two stages of querying). In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?