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

Ivan Lau, Jonathan Scarlett
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7123-7128, 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?

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-lau26a, title = {Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?}, author = {Lau, Ivan and Scarlett, Jonathan}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {7123--7128}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/lau26a/lau26a.pdf}, url = {https://proceedings.mlr.press/v336/lau26a.html}, 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?} }
Endnote
%0 Conference Paper %T Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation? %A Ivan Lau %A Jonathan Scarlett %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-lau26a %I PMLR %P 7123--7128 %U https://proceedings.mlr.press/v336/lau26a.html %V 336 %X 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?
APA
Lau, I. & Scarlett, J.. (2026). Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:7123-7128 Available from https://proceedings.mlr.press/v336/lau26a.html.

Related Material