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

arXiv:2608.02538 · stat.ML, cs.IT, cs.LG, math.ST · Submitted 2026-08-03 · Read on arXiv

Jiachen Hu, Han Zhong

stat.ML, cs.IT, cs.LG, math.ST

Submitted: 2026-08-03

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Sample Complexity — 15× in this paper · explained in 15 episodes
• Accuracy — 6× in this paper · explained in 1 episode
• Adaptivity — 4× in this paper · explained in 1 episode
• Quantization — 3× in this paper · explained in 12 episodes
• Adaptation — 2× in this paper · explained in 1 episode
• Aggregation — 2× in this paper · explained in 1 episode
• Hamming Distance — 2× in this paper · explained in 2 episodes
• Alignment — 1× in this paper · explained in 1 episode
• Decode — 1× in this paper · explained in 2 episodes
• Decoupling — 1× in this paper · explained in 2 episodes

Sources

• Robust Mean Estimation under Quantization
• Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms
• Optimal Mean Estimation without a Variance
• One-Bit Distributed Mean Estimation with Unknown Variance
• Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity
• Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
• Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes
• Universal Refinement without Interaction: Order-Optimal 1-Bit Mean Estimation

Related papers

• Behavior of prediction performance metrics with rare events
• Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
• A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
• One Permutation Is All You Need: Fast, Deterministic Feature Importance and Model Stress-Testing
• Online Conformal Prediction for Non-Exchangeable Panel Data
• Deep Time-Series Forecasting in 10 Years: A Survey