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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 18 references that are in the map.
- First posted on arXiv 3 Aug 2026.

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

- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms](https://mlsanity.com/paper/2001.08877/) (2020)
- [Optimal Mean Estimation without a Variance](https://mlsanity.com/paper/2011.12433/) (2020)
- [Mean Estimation from One-Bit Measurements](https://mlsanity.com/paper/1901.03403/) (2019)
- [Interaction is necessary for distributed learning with privacy or communication constraints](https://mlsanity.com/paper/1911.04014/) (2019)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Robust Mean Estimation under Quantization](https://mlsanity.com/paper/2601.07074/) (2026)
- [Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?](https://mlsanity.com/paper/2607.02896/) (2026)

## Built on by (most cited first, 2 of 2)

- [Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff](https://mlsanity.com/paper/2609.08564/) (2026)
- [Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation](https://mlsanity.com/paper/2609.27860/) (2026)

## Abstract (arXiv)

This paper is concerned with one-bit mean estimation, where each independent sample is represented by a single binary message. We consider distributions on ℝ with mean in [-λ,λ] and absolute k-th central moment at most σ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 ε and confidence 1-δ, its sample complexity scales as [ logfracλσ + begincases (σ/ε)2log(1/δ), & k>2, (σ/ε)2log(σ/ε)log(1/δ), & k=2, (σ/ε)k/(k-1)log(1/δ), & 1<k<2, endcases ] 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 citep[Open Problem~1]lau2026open.