# Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

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

## Key facts

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

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

- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms](https://mlsanity.com/paper/2001.08877/) (2020)
- [Locally Private Hypothesis Selection](https://mlsanity.com/paper/2002.09465/) (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)
- [Efficient median of means estimator](https://mlsanity.com/paper/2305.18681/) (2023)
- [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)
- [Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Moments](https://mlsanity.com/paper/2311.12784/) (2023)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints](https://mlsanity.com/paper/2506.13686/) (2025)

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

- [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 ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.e., two stages of querying). In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?