R.I.P.
๐ป
Ghosted
Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
July 03, 2026 ยท Grace Period ยท ๐ COLT 2026
Authors
Ivan Lau, Jonathan Scarlett
arXiv ID
2607.02896
Category
cs.IT: Information Theory
Cross-listed
cs.LG,
math.ST,
stat.ML
Citations
0
Venue
COLT 2026
Abstract
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?
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Information Theory
R.I.P.
๐ป
Ghosted
A Vision of 6G Wireless Systems: Applications, Trends, Technologies, and Open Research Problems
R.I.P.
๐ป
Ghosted
Towards Smart and Reconfigurable Environment: Intelligent Reflecting Surface Aided Wireless Network
๐
๐
The Cartographer
Wireless Communications with Unmanned Aerial Vehicles: Opportunities and Challenges
R.I.P.
๐ป
Ghosted
Reconfigurable Intelligent Surfaces for Energy Efficiency in Wireless Communication
๐
๐
The Cartographer