Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
Abstract
We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query Q: ℝ→{0,1} chosen by a central learner. The distribution has mean in [−λ,λ] and k-th central moment at most σk, for a fixed k>1. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every k>1, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set Q−1(1) is restricted to a union of at most s intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order (λσ/(sε2))log(1/δ), giving the full tradeoff between sample complexity and interval complexity to within k-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.
Related
- A statistical theory for blind denoising: minimax estimation of the noise level from a single sample
- Nonparametric hazard rate estimation with associated kernels and minimax bandwidth choice
- Minimax rates for pointwise CATE estimation: the role of design smoothness
- Nearly-minimax variance estimation under rough random design
- Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds
BibTeX
@misc{lau2026nonadaptive,
title = {{Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff}},
author = {Ivan Lau and Jonathan Scarlett},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08564},
eprint = {2609.08564},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08564},
}
RIS
TY - UNPB
TI - Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
AU - Ivan Lau
AU - Jonathan Scarlett
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08564
UR - https://arxiv.org/abs/2609.08564
AB - We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query Q: ℝ→{0,1} chosen by a central learner. The distribution has mean in [−λ,λ] and k-th central moment at most σ^k, for a fixed k>1. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every k>1, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set Q^−1(1) is restricted to a union of at most s intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order (λσ/(sε^2))log(1/δ), giving the full tradeoff between sample complexity and interval complexity to within k-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.
ER -