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

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

Ivan Lau, Jonathan Scarlett

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

Submitted: 2026-07-03

Comments: COLT 2026 Open Problem

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

Terminology

• In Conference on Learning Theory — 8× in this paper
• Adaptivity — 7× in this paper · explained in 1 episode
• Sample Complexity — 7× in this paper · explained in 15 episodes
• Quantization — 2× in this paper · explained in 12 episodes
• Decode — 1× in this paper · explained in 2 episodes
• Edge Devices — 1× in this paper · explained in 2 episodes
• Fisher Information — 1× in this paper · explained in 3 episodes

Sources

• Robust Mean Estimation under Quantization
• Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes

Related papers

• Clipped Affine Policy: Low-Complexity Near-Optimal Online Power Control for Energy Harvesting Communications over Fading Channels
• Discrepancy for Random Linear Codes
• A New Approach to Code Smoothing Bounds
• Contextual Memory-Enhanced Source Coding for Low-SNR Communications
• Symmetry-Enforced Quadratic Approximate-Degradability Bounds for Noisy Landau-Streater Channels
• Anonymous Shamir's Secret Sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions