Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

July 03, 2026 ยท Grace Period ยท ๐Ÿ› COLT 2026

โณ Grace Period
This paper is less than 90 days old. We give authors time to release their code before passing judgment.
Authors Ivan Lau, Jonathan Scarlett arXiv ID 2607.02896 Category cs.IT: Information Theory Cross-listed cs.LG, math.ST, stat.ML Citations 0 Venue COLT 2026
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?
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Information Theory