mlsanityData to 13 Oct 2026

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

arXiv 2607.02896 ↗First posted 3 Jul 2026cs.IT cs.LG math.ITcited by 2

Not on the map. Why?

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?

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

Builds on

17 of 23 references.

References · 17

  1. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  2. 2018Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraintscited by 33
  3. 2013Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimationcited by 24
  4. 2020Unified lower bounds for interactive high-dimensional estimation under information constraintscited by 22
  5. 2020Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithmscited by 17
  6. 2020Locally Private Hypothesis Selectioncited by 17
  7. 2020Optimal Mean Estimation without a Variancecited by 13
  8. 2019Mean Estimation from One-Bit Measurementscited by 9
  9. 2019Interaction is necessary for distributed learning with privacy or communication constraintscited by 8
  10. 2022The Role of Interactivity in Structured Estimationcited by 7
  11. 2023Efficient median of means estimatorcited by 7
  12. 2026Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimescited by 6
5 more
  1. 2025Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexitycited by 5
  2. 2026Robust Mean Estimation under Quantizationcited by 5
  3. 2023Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Momentscited by 4
  4. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  5. 2025The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraintscited by 3

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimationcited by 2
  2. 2026VALG: An Agentic System for ML Theory Researchcited by 2

Similar, not cited

Close in wording, no citation either way

  1. 2026Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
  2. 2026Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation
  3. 2022On the Mean Square Error Optimal Estimator in One-Bit Quantized Systems
  4. 2026Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
  5. 2022On One-Bit Quantization
  6. 2022Resolution Limits of Non-Adaptive 20 Questions Search for a Moving Target
  7. 2026Pre-Registering the Detectable Effect: A Paired-MDE Budget for 4-bit Quantization Benchmarks, with a Pilot Audit
  8. 2024Linear and Nonlinear MMSE Estimation in One-Bit Quantized Systems under a Gaussian Mixture Prior