REVIEW 2 major objections 4 minor 18 references
Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation
T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read The paper constructs a fully non-adaptive one-bit mean estimator that matches the adaptive minimax rate, showing interaction is not necessary for order-optimal one-bit mean estimation.
desk verdict The construction is genuinely new and the result is likely correct, but Theorem 1.1 is not proven as printed: the variance bound (4.6) is arithmetically false, and the fix (inflating a constant) leaves the rates intact. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the fixed-scale refinement estimator Z_g(c), built from two one-bit query maps applied to two fresh samples: a signed-threshold query and a block-sign query. The queries are attached to blocks of length 16s in a randomly shifted partition; pairwise-independent block signs cancel all off-block contributions, and the second query supplies the selected-block centering correction. The estimator is conditionally unbiased with E[Z_g(C)|H] = E_P[g(X-C)], and its conditional variance is bounded by 384s²||ġ||²∞ Pr{|X-C| ≥ s/2}, so high scales are charged only through tail probabilities. This tail-weighted variance control is what makes the multiscale decomposition of the identi
What would settle it
Recompute the variance line (4.6): 1536 + 6144·16 = 99840, and 99840/222 ≈ 449.7, which is not less than 1/32. Even the i=0 term alone, 1536 s0²/N0 with N0 = ⌈222 s0²/ε²⌉, is about 6.9 ε², already exceeding ε²/32. A reader can verify this by direct arithmetic; a corrected theorem requires a substantially larger constant in the definition of N_i.
Extended reading notes
Core claim
The paper claims that for every fixed k>1, if the mean lies in [-λ,λ] and the absolute k-th central moment is at most σ^k, then an (ε,δ)-accurate fully non-adaptive one-bit protocol exists with sample complexity O_k(log(λ/σ)) plus a refinement term: (σ/ε)^2 log(1/δ) for k>2, (σ/ε)^2 log(σ/ε) log(1/δ) for k=2, and (σ/ε)^{k/(k-1)} log(1/δ) for 1<k<2. In the regime where the known adaptive lower bound applies, this rate is minimax optimal even among fully adaptive randomized protocols. The key move is to fix all queries in advance: a randomly shifted block partition and pairwise-independent block signs let the decoder select the block containing the localized center only after the bits arrive,
Load-bearing premise
The argument's load-bearing step is the numerical variance bound 99840/222 ε² < ε²/32, which is false as printed; if that inequality is not repaired, the Chebyshev step and median amplification do not follow.
Editorial extensions
If this is right
- Users can commit to queries before seeing any data, so one-bit estimation can be run as a batch protocol without a second round of communication.
- The sample-complexity decomposition log(λ/σ)+refinement shows that localization cost is additive and negligible when ε is much smaller than σ.
- The construction yields exact conditional unbiasedness from two binary messages per replicate, simplifying the median-of-means amplification step.
- Where the adaptive lower bound applies, no adaptive protocol can improve on this non-adaptive rate, so interaction has no minimax value for general one-bit queries.
- The adaptivity gap previously demonstrated for threshold and interval queries does not extend to arbitrary measurable queries, highlighting their extra power.
Reading between the lines
- The numerical variance-bound gap at (4.6) — 99840/222 ε² is not less than ε²/32 — appears repairable by enlarging the replicate-count constant; if so, the stated rates and the center-independent construction survive even though the printed proof does not verify the bound.
- The two-query block-sign construction may transfer to other one-bit distributed estimation problems, such as quantile or scale estimation, where a decoder must locate a relevant region after all queries are fixed.
- A direct numerical check of the k=2 case would be especially informative: the extra log(σ/ε) factor is the sharp distinguishing prediction between this protocol and a simpler k>2-style bound.
- The structural idea — random shifts plus cancellating block signs — is likely portable to higher-dimensional mean estimation under finite moments, though the paper does not address that setting.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a fully non-adaptive randomized one-bit protocol for mean estimation over distributions with bounded k-th central moment (k > 1). The protocol fixes all binary queries before observing any sample, uses a non-adaptive localization stage plus a center-independent multiscale refinement stage, and is claimed to achieve the same order-optimal sample complexity as the best adaptive protocol. The main technical contribution is a fixed-scale refinement estimator whose two binary queries are independent of the later-decoded center, using random shifted blocks, pairwise-independent block signs, and a safety indicator to obtain exact conditional unbiasedness and tail-weighted variance bounds. The paper claims this gives a negative answer to a COLT 2026 open problem on the necessity of interaction.
Significance. If the result holds, it is a substantial contribution: it resolves an open problem and shows that, for general measurable one-bit queries, adaptivity is not needed for order-optimal mean estimation under finite-moment assumptions. The construction is explicit, the center-independent query design is elegant, and the proof contains several independently checkable identities (the step-integration identity, the conditional unbiasedness lemma, and the multiscale bias decomposition). The claimed rates match the known adaptive lower bound, so the paper would close an important gap. The main technical novelty — exact conditional unbiasedness with queries fixed before localization — is valuable beyond the specific application.
major comments (2)
- [Section 4, Eq. (4.6)] The displayed variance bound is arithmetically false. From (4.4) and (3.14), the claim is Var(\hat\mu_r | F_loc) ≤ (1536 + 6144·16)/222 · ε² = 99840/222 · ε² ≈ 449.7 ε², which is not less than ε²/32. Even the i = 0 term alone gives 1536/222 ε² ≈ 6.92 ε². Since (4.7) and (4.8) both rely on Var < ε²/32, Theorem 1.1 is not established as printed. The issue is repairable: replacing the constant 222 in (3.14) by any C ≥ 99840·32 = 3,194,880 (which is k-dependent) makes (4.6) valid without changing any of the stated rates. This is a load-bearing numerical error, not a refutation of the construction.
- [Section 2/Proposition 2.1] The localization guarantee is imported from Lau and Scarlett (2026b, Theorem 16 and Appendix D), which is a preprint. The paper's optimality and even the bias bound in (4.2) depend on this guarantee. While citing external results is normal, the manuscript should state explicitly that Proposition 2.1 is an external theorem and not proved here; this is also relevant to the status of the claimed negative answer to the open problem, since the matching lower bound is likewise external. This does not affect the internal correctness of the new construction, but should be clarified.
minor comments (4)
- [Section 4, just before (4.6)] The notation in (4.6) is slightly misleading: the displayed expression should include the factor ε² consistently, and the final inequality should be C/222 ε² < ε²/32 only for C < 222/32, which is not the case. Please correct the arithmetic and adjust the constant.
- [Section 4, sample complexity paragraph] The absorption of the localization log(1/δ) term into the refinement terms is asserted briefly. It is valid because ε ≤ σ/2 makes (σ/ε)^2 ≥ 4, but the manuscript should spell this out in one sentence.
- [Appendix E, Eq. (E.4)] The factor 8 in (E.4) comes from two terms each bounded by 4; this is correct but not immediately obvious. Consider adding a parenthetical to explain the constant for readability.
- [Throughout] The paper repeatedly cites 'Lau and Scarlett (2026b)' for the lower bound and localization. Since these are arXiv preprints, the references should include the arXiv identifiers and, if available, the publication status.
Circularity Check
No circularity: the non-adaptive construction is derived from first principles; external results are used only as benchmarks/inputs, not as disguised conclusions.
full rationale
The paper's central claim is a new fully non-adaptive one-bit protocol whose queries are fixed before data observation. The construction in Section 3 and Lemma 3.2 is proved directly from the definitions of the query maps, the random block partition, pairwise-independent block signs, and the step-integration identity (3.1), with no parameter fitted to data and no target rate assumed. The multiscale estimator in (3.14)-(3.15) is an explicit, self-contained recipe; the bias and variance bounds in (4.1)-(4.6) follow from elementary inequalities and the tail bound (4.5). The matching lower bound and localization subroutine are imported from Lau and Scarlett (2026b), a different author group, and are used as external benchmarks and inputs, not as the source of the non-adaptive protocol's guarantees. The open problem cited is the question being answered, not an assumption of the answer. The paper also cites concurrent work by Miao only as comparison, not as load-bearing evidence. There is no self-citation chain supporting the main theorem, no fitted parameter renamed as a prediction, and no known result repackaged under new coordinates. The arithmetic error in (4.6) — where 99840/222 ε² is claimed to be < ε²/32 — is a serious correctness flaw in the proof as printed, but it is not circular reasoning: the intended bound can be repaired by enlarging the replicate-count constant 222 to a k-dependent O(1) constant, and the claimed rates do not depend on that constant. Correctness risk is therefore distinct from circularity, and no circular step is present.
Assumptions & free parameters
free parameters (7)
- Replicate-count constant 222 in N_i = ⌈222 s_0² 2^{i(2−κ)}/ε²⌉ =
222
- Base scale s_0 = 64σ =
64σ
- Block length L = 16s =
16s
- Safety margin 4s =
4s
- Localization radius 50σ =
50σ
- Operative moment order κ = min{k,3} =
min{k,3}
- Median size K = 2⌈4 log(2/δ)⌉ + 1 =
2⌈4 log(2/δ)⌉+1
assumptions (6)
- domain assumption Localization guarantee (Proposition 2.1), deferred to Lau and Scarlett (2026b, Theorem 16, Appendix D)
- domain assumption Matching adaptive lower bound of Lau and Scarlett (2026b)
- domain assumption Distribution class D_k(λ,σ) with known (λ,σ,k) and fully known query parameters
- standard math Lyapunov, Minkowski, and Markov inequalities
- standard math Hoeffding's inequality for the median amplification (4.8)
- standard math Fubini / measurability for conditioning on the localization σ-field
Cite this review
Pith. "Pith review of Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation." pith.science (2026). https://pith.science/paper/XQQGTEVO
@misc{pith2026260802538,
author = {Pith},
title = {Pith review of: Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation},
year = {2026},
howpublished = {\url{https://pith.science/paper/XQQGTEVO}},
note = {Machine review of arXiv:2608.02538}
}
abstract
This paper is concerned with one-bit mean estimation, where each independent sample is represented by a single binary message. We consider distributions on $\mathbb{R}$ with mean in $[-\lambda,\lambda]$ and absolute $k$-th central moment at most $\sigma^k$, where $k>1$ is fixed. For this class, previous work attained the optimal sample complexity for general queries using a two-stage protocol. The first stage localizes the mean. The second-stage queries are chosen after localization and refine the estimate around the decoded center. We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol that fixes all queries before observing the data and matches the optimal adaptive sample complexity. For target accuracy $\epsilon$ and confidence $1-\delta$, its sample complexity scales as \[ \log\frac{\lambda}{\sigma} + \begin{cases} (\sigma/\epsilon)^2\log(1/\delta), & k>2,\\ (\sigma/\epsilon)^2\log(\sigma/\epsilon)\log(1/\delta), & k=2,\\ (\sigma/\epsilon)^{k/(k-1)}\log(1/\delta), & 1<k<2, \end{cases} \] up to constants depending only on $k$. In the range covered by the known lower bound, this rate is minimax optimal even among fully adaptive protocols. This gives a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation with general queries \citep[Open Problem~1]{lau2026open}.
Figures
Reference graph
Works this paper leans on
-
[1]
Abdalla, P. and Chen, J. (2026). Robust mean estimation under quantization.arXiv preprint arXiv:2601.07074
arXiv 2026
-
[2]
L., Sun, Z
Acharya, J., Canonne, C. L., Sun, Z. and Tyagi, H. (2022). The role of interactivity in structured estimation. InConference on Learning Theory. PMLR
2022
-
[3]
Boufounos, P. T. (2011). Universal rate-efficient scalar quantization.IEEE transactions on information theory,581861–1872
2011
-
[4]
Cai, T. T. and Wei, H. (2020). Distributed gaussian mean estimation under communication constraints: Optimal rates and communication-efficient algorithms.arXiv preprint arXiv:2001.08877
arXiv 2020
-
[5]
Cai, T. T. and Wei, H. (2022). Distributed adaptive gaussian mean estimation with unknown variance: Interactive protocol helps adaptation.The Annals of Statistics,501992–2020
2022
-
[6]
Cherapanamjeri, Y., Tripuraneni, N., Bartlett, P. L. and Jordan, M. I. (2020). Optimal mean estimation without a variance.arXiv preprint arXiv:2011.12433
arXiv 2020
-
[7]
and Feldman, V
Dagan, Y. and Feldman, V. (2020). Interaction is necessary for distributed learning with privacy or communi- cation constraints. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
2020
-
[8]
and Oliveira, R
Devroye, L., Lerasle, M., Lugosi, G. and Oliveira, R. I. (2016). Sub-gaussian mean estimators
2016
Show all 18 references
-
[9]
and Duchi, J
Kipnis, A. and Duchi, J. C. (2022). Mean estimation from one-bit measurements.IEEE Transactions on Information Theory,686276–6296
2022
-
[10]
and Vatedka, S
Kumar, R. and Vatedka, S. (2025). One-bit distributed mean estimation with unknown variance.arXiv preprint arXiv:2501.18502
2025 arXiv
-
[11]
and Scarlett, J
Lau, I. and Scarlett, J. (2025). Sequential 1-bit mean estimation with near-optimal sample complexity.arXiv preprint arXiv:2509.21940
2025 arXiv
-
[12]
and Scarlett, J
Lau, I. and Scarlett, J. (2026a). Open problem: Is interaction necessary for order-optimal 1-bit mean esti- mation?arXiv preprint arXiv:2607.02896
-
[13]
and Scarlett, J
Lau, I. and Scarlett, J. (2026b). Order-optimal sequential 1-bit mean estimation in general tail regimes. arXiv preprint arXiv:2604.07796
-
[14]
Lee, J. C. and Valiant, P. (2022). Optimal Sub-Gaussian Mean Estimation inR. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE
2022
-
[15]
Miao, Y. (2026). Universal refinement without interaction: Order-optimal 1-bit mean estimation.arXiv preprint arXiv:2607.24358
2026 arXiv
-
[16]
T., Felix, X
Suresh, A. T., Felix, X. Y., Kumar, S. and McMahan, H. B. (2017). Distributed mean estimation with lim- ited communication. InInternational conference on machine learning. PMLR
2017
-
[17]
and Mitzenmacher, M
Vargaftik, S., Ben-Basat, R., Portnoy, A., Mendelson, G., Ben-Itzhak, Y. and Mitzenmacher, M. (2021). Drive: One-bit distributed mean estimation.Advances in Neural Information Processing Systems,34 362–377
2021
-
[18]
Zhang, Y., Duchi, J., Jordan, M. I. and Wainwright, M. J. (2013). Information-theoretic lower bounds for distributed statistical estimation with communication constraints.Advances in Neural Information Pro- cessing Systems,26. 15
2013
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.