arxivcs.ITcs.LGmath.STstat.ML2026-07-03
Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
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 ada…