Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation

arXiv:2608.02538v1 Announce Type: cross Abstract: This paper is concerned with one-bit mean estimation, where each independent sample is represented by a single binary message. We consider distributions on R with mean in [-lambda,lambda] and absolute k-th central moment at most sigma^k, where k>1 is fixed. For this class, previous work attained the optimal sample complexity for general queries using a two-stage protocol. The first stage localizes the mean. The second-stage queries are chosen after localization and refine the estimate around the decoded center. We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol that fixes all queries before observing the data and matches the optimal adaptive sample complexity. For target accuracy epsilon and confidence 1-elta, its sample complexity scales as [ logfrac{lambda}{sigma} + egin{cases} (sigma/epsilon)^2log(1/elta), & k>2, (sigma/epsilon)^2log(sigma/epsilon)log(1/elta), & k=2, (sigma/epsilon)^{k/(k-1)}log(1/elta), & 1<k<2, end{cases} ] up to constants depending only on k. In the range covered by the known lower bound, this rate is minimax optimal even among fully adaptive protocols. This gives a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation with general queries itep[Open Problem~1]{lau2026open}.

Source: arXiv cs.LG | 2026-08-04