Metraipolis › archive › dc_30c8f88fead0

Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff — arXiv:2609.08564

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08564
License (as archived)
CC0-1.0
Archived
2026-10-16T13:59:36.268Z
SHA-256 of the archived text
31fa60d2be3c91f6e4425b9ede3b0e9c94a7ffe6fe61d94fa23d0e03f22854d7
Stable URL of this page
https://metraipolis.com/documento/dc_30c8f88fead0

How to cite

Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff — arXiv:2609.08564 — arXiv (en), https://arxiv.org/abs/2609.08564 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_30c8f88fead0 (Metraipolis archive dc_30c8f88fead0, sha256 31fa60d2be3c91f6e4425b9ede3b0e9c94a7ffe6fe61d94fa23d0e03f22854d7)
BibTeX
@misc{dc30c8f88fead0,
  title = {Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff — arXiv:2609.08564},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08564},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_30c8f88fead0; sha256 31fa60d2be3c91f6e4425b9ede3b0e9c94a7ffe6fe61d94fa23d0e03f22854d7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08564. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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: \mathbb{R}\to\{0,1\}$ chosen by a central learner. The distribution has mean in $[-\lambda,\lambda]$ and $k$-th central moment at most $\sigma^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 $(\lambda\sigma/(s\varepsilon^2))\log(1/\delta)$, 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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LG).
Categorie arXiv: Machine Learning (stat.ML) ; Information Theory (cs.IT); Machine Learning (cs.LG); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2609.08564 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:39:43.286Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).