Interaction Is Unnecessary for Order-Optimal One-Bit Mean Estimation

Abstract

We resolve the open question of whether interaction is necessary for order-optimal one-bit mean estimation under a finite central moment. Let $\mu\in[-\lambda,\lambda]$ and $\mathbb{E}|X-\mu|^k\leq\sigma^k$ for fixed $k>1$. We construct a fully nonadaptive protocol whose query list is fixed before any bit is observed and whose sample complexity matches the adaptive one-bit minimax rate in every moment regime. The refinement cost is $(\sigma/\epsilon)^{k/(k-1)}\log(1/\delta)$ for $1<k<2$, $(\sigma/\epsilon)^2\log(\sigma/\epsilon)\log(1/\delta)$ for $k=2$, and $(\sigma/\epsilon)^2\log(1/\delta)$ for $k>2$, plus the optimal $\log(\lambda/\sigma)$ localization cost. The protocol first runs an existing nonadaptive codebook localizer. It then uses only decoding, not new queries, to choose a padded path through a prequeried dictionary of shifted modulo maps. Adjacent modulo remainders have finite-valued differences that are locally constant near the mean. Their variance is therefore charged only to samples that cross a scale-dependent boundary. A dyadic tail identity pays for all scales with one central-moment budget. This removes both the location dependence and the tail aliasing that obstruct global one-shot refinement.

Main results

Theorem. Fix $k>1$. There are constants $c_k,C_k>0$ such that for every $\lambda\geq\sigma>0$, $0<\epsilon\leq c_k\sigma$, and $\delta\in(0,1/2)$, a fully nonadaptive one-bit protocol satisfies

$$ \sup_{D\in\mathcal{D}(k,\lambda,\sigma)} \mathbb{P}_D\{|\widehat\mu-\mu(D)|>\epsilon\}\leq\delta $$

using

$$ n\leq C_k\left\{\log\frac{\lambda}{\sigma} +\mathfrak r_k(\sigma,\epsilon,\delta)\right\} $$

samples.

Keywords

one-bit mean estimation, nonadaptive protocol, distributed estimation, communication constraints, heavy-tailed moments, minimax rate

Files

• main_old_2026-07-30.pdf, the paper as first published, with its OpenTimestamps proof main_old_2026-07-30.pdf.ots.
• main.pdf, the current version.
• supplement_old_2026-07-30.pdf, the supplement as first published, with its OpenTimestamps proof supplement_old_2026-07-30.pdf.ots.
• source: aistats2027.sty, main.tex, references.bib, supplement.tex.
• also: main.bbl.