# Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

arXiv: https://arxiv.org/abs/2609.08564 · HTML: https://mlsanity.com/paper/2609.08564/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 37 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Builds on (most cited first, 4 of 4)

- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Robust Mean Estimation under Quantization](https://mlsanity.com/paper/2601.07074/) (2026)
- [Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation](https://mlsanity.com/paper/2608.02538/) (2026)
- [VALG: An Agentic System for ML Theory Research](https://mlsanity.com/paper/2608.13060/) (2026)

## Abstract (arXiv)

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 (λσ/(svarepsilon2))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.