# Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 69 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 30 of 31)

- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Randomized Distributed Mean Estimation: Accuracy vs Communication](https://mlsanity.com/paper/1611.07555/) (2016)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [On Communication Cost of Distributed Statistical Estimation and Dimensionality](https://mlsanity.com/paper/1405.1665/) (2014)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [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)
- [Solving Multi-Arm Bandit Using a Few Bits of Communication](https://mlsanity.com/paper/2111.06067/) (2021)
- [Interactive Inference under Information Constraints](https://mlsanity.com/paper/2007.10976/) (2020)
- [Correlated quantization for distributed mean estimation and optimization](https://mlsanity.com/paper/2203.04925/) (2022)
- [Optimal Mean Estimation without a Variance](https://mlsanity.com/paper/2011.12433/) (2020)
- [Adaptive distributed methods under communication constraints](https://mlsanity.com/paper/1804.00864/) (2018)
- [Mean Estimation from One-Bit Measurements](https://mlsanity.com/paper/1901.03403/) (2019)
- [Optimal Rates for Nonparametric Density Estimation under Communication Constraints](https://mlsanity.com/paper/2107.10078/) (2021)
- [Distributed Nonparametric Regression under Communication Constraints](https://mlsanity.com/paper/1803.01302/) (2018)
- [Efficient median of means estimator](https://mlsanity.com/paper/2305.18681/) (2023)
- [Distributed function estimation: adaptation using minimal communication](https://mlsanity.com/paper/2003.12838/) (2020)
- [Distributed Nonparametric Function Estimation: Optimal Rate of Convergence and Cost of Adaptation](https://mlsanity.com/paper/2107.00179/) (2021)
- [Communication-Constrained Bandits under Additive Gaussian Noise](https://mlsanity.com/paper/2304.12680/) (2023)
- [Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Moments](https://mlsanity.com/paper/2311.12784/) (2023)
- [Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation](https://mlsanity.com/paper/2311.13010/) (2023)
- [Quantile Multi-Armed Bandits with 1-bit Feedback](https://mlsanity.com/paper/2502.06678/) (2025)
- [Sharp Noisy Binary Search with Monotonic Probabilities](https://mlsanity.com/paper/2311.00840/) (2023)
- [Distributed Nonparametric Estimation under Communication Constraints](https://mlsanity.com/paper/2204.10373/) (2022)

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

- [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)
- [Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?](https://mlsanity.com/paper/2607.02896/) (2026)
- [Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation](https://mlsanity.com/paper/2608.02538/) (2026)
- [Batched Stochastic Linear Bandits with 1-Bit Communication Constraints](https://mlsanity.com/paper/2605.30976/) (2026)

## Abstract (arXiv)

In this paper, we study the problem of distributed mean estimation with 1-bit communication constraints. We propose a mean estimator that is based on (randomized and sequentially-chosen) interval queries, whose 1-bit outcome indicates whether the given sample lies in the specified interval. Our estimator is (ε, δ)-PAC for all distributions with bounded mean (-λ ≤ mathbbE(X) ≤ λ ) and variance (Var(X) ≤ σ2) for some known parameters λ and σ. We derive a sample complexity bound widetildeObig( fracσ2ε2logfrac1δ + logfracλσbig), which matches the minimax lower bound for the unquantized setting up to logarithmic factors and the additional logfracλσ term that we show to be unavoidable. We also establish an adaptivity gap for interval-query based estimators: the best non-adaptive mean estimator is considerably worse than our adaptive mean estimator for large fracλσ. Finally, we give tightened sample complexity bounds for distributions with stronger tail decay, and present additional variants that (i) handle an unknown sampling budget (ii) adapt to the unknown true variance given (possibly loose) upper and lower bounds on the variance, and (iii) use only two stages of adaptivity at the expense of more complicated (non-interval) queries.