REVIEW 2 major objections 2 minor 3 cited by
Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes
T0 review · 2 major / 2 minor · reviewed 2026-05-25 · grok-4.3
Pith's one-line read An adaptive sequence of randomized 1-bit threshold queries estimates the mean to accuracy ε with sample complexity matching the unquantized rate plus small factors for any fixed moment bound k>1.
desk verdict The paper gives matching upper and lower bounds for adaptive 1-bit mean estimation under k-moment tails, with a new lower bound showing the extra log factor is necessary when k=2. 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 adaptive, sequential choice of randomized thresholds for 1-bit queries that both localizes the mean and refines the estimate in one pass.
What would settle it
An explicit 1-bit estimator (adaptive or not) for a finite-variance distribution that achieves (ε, δ)-PAC accuracy with sample complexity free of the extra log(σ/ε) factor, or a matching lower-bound proof that removes the factor.
Extended reading notes
Core claim
There exists a single adaptive procedure based on randomized threshold queries that produces an (ε, δ)-PAC mean estimate whose sample complexity is order-optimal simultaneously for every tail regime indexed by k>1. For k≠2 the complexity equals the unquantized minimax rate plus an O(log(λ/σ)) localization term; for finite variance (k=2) an extra O(log(σ/ε)) factor appears and is shown to be unavoidable by a new information-theoretic lower bound. Non-adaptive estimators, even with general interval queries, require sample complexity linear in λ/σ.
Load-bearing premise
Thresholds must be allowed to depend on all previous 1-bit outcomes and may be randomized.
Editorial extensions
If this is right
- For every k≠2 the estimator matches the best unquantized sample complexity up to the localization cost log(λ/σ).
- For k=2 the extra log(σ/ε) multiplicative penalty is fundamental and cannot be removed by any 1-bit method.
- Any non-adaptive procedure, even with interval queries, must scale linearly with λ/σ.
- Simple two-stage and multi-sample variants retain order optimality while relaxing the number of adaptive rounds or reducing total bits.
Reading between the lines
- The necessity of the log(σ/ε) term under 1-bit constraints may extend to other location estimation problems with quantization.
- The demonstrated adaptivity gap suggests that many existing non-adaptive quantization schemes in sensor networks are fundamentally inefficient for mean estimation.
- The two-stage variant offers a practical middle ground when full sequential adaptivity is costly to implement.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an adaptive estimator for 1-bit mean estimation based on sequential randomized threshold queries. It claims that the estimator is (ε, δ)-PAC for distributions with mean μ ∈ [-λ, λ] and bounded k-th central moment E[|X-μ|^k] ≤ σ^k for any fixed k > 1, with sample complexity that is order-optimal in all such regimes: matching the unquantized minimax rate plus O(log(λ/σ)) localization for k ≠ 2, and incurring an extra O(log(σ/ε)) factor for k=2 that is shown necessary by a new information-theoretic lower bound. The work also establishes an adaptivity gap (non-adaptive estimators scale linearly with λ/σ) and provides variants for unknown budgets, unknown σ, two-stage adaptivity, and multi-sample queries.
Significance. If the upper and lower bounds hold, the paper makes a solid contribution to communication-constrained estimation by giving order-optimal algorithms that work uniformly across tail regimes (k > 1) and by isolating a genuine information-theoretic penalty that appears only for finite variance. The explicit treatment of adaptivity, the novel k=2 lower bound, and the algorithmic variants for unknown parameters are all positive features. The results are relevant to both theoretical statistics and practical distributed learning settings.
major comments (2)
- [§2 and §4] §2 (Query Model) and §4 (Upper Bound Construction): The order-optimality claims, including the matching lower bound for the extra O(log(σ/ε)) factor when k=2, are derived under the adaptive randomized-threshold model. The manuscript should state more explicitly whether the same rates (or the necessity of the log penalty) continue to hold if thresholds must be deterministic or chosen non-adaptively; this modeling choice is load-bearing for the “fundamental limit of 1-bit quantization” statement.
- [§5] §5 (Lower Bound for k=2): The novel information-theoretic lower bound establishing necessity of the extra logarithmic factor is central to the finite-variance claim. The proof should be expanded to show precisely how the mutual-information or Fano-style argument accounts for the adaptive, randomized choice of thresholds; without that detail the lower-bound argument cannot be verified as tight.
minor comments (2)
- The notation for the localization cost O(log(λ/σ)) is used in several places; a single displayed equation collecting all the sample-complexity expressions (upper and lower) for each regime of k would improve readability.
- Figure 1 (or the corresponding plot of sample complexity vs. λ/σ) would benefit from an additional curve showing the non-adaptive baseline to visually illustrate the adaptivity gap claimed in §6.
Simulated Author's Rebuttal
We thank the referee for the positive evaluation and the recommendation of minor revision. We address each major comment below.
read point-by-point responses
-
Referee: [§2 and §4] §2 (Query Model) and §4 (Upper Bound Construction): The order-optimality claims, including the matching lower bound for the extra O(log(σ/ε)) factor when k=2, are derived under the adaptive randomized-threshold model. The manuscript should state more explicitly whether the same rates (or the necessity of the log penalty) continue to hold if thresholds must be deterministic or chosen non-adaptively; this modeling choice is load-bearing for the “fundamental limit of 1-bit quantization” statement.
Authors: Our results, including both the upper bounds in Section 4 and the k=2 lower bound in Section 5, are derived specifically for the adaptive randomized-threshold query model defined in Section 2. The paper makes no claim that the stated rates or the necessity of the log(σ/ε) penalty extend to deterministic or non-adaptive thresholds. Section 6 already establishes an adaptivity gap showing linear dependence on λ/σ for non-adaptive estimators under both threshold and interval queries. We will add an explicit clarifying sentence in the introduction and at the end of Section 2 stating that all optimality claims are with respect to the adaptive randomized model and that the deterministic case is left open. revision: yes
-
Referee: [§5] §5 (Lower Bound for k=2): The novel information-theoretic lower bound establishing necessity of the extra logarithmic factor is central to the finite-variance claim. The proof should be expanded to show precisely how the mutual-information or Fano-style argument accounts for the adaptive, randomized choice of thresholds; without that detail the lower-bound argument cannot be verified as tight.
Authors: We agree that greater detail on this point will improve verifiability. The appendix proof applies Fano’s inequality to a carefully constructed packing of distributions and bounds the mutual information by the worst-case information revealed by any adaptive randomized threshold sequence. We will expand the high-level argument in Section 5 and insert a new paragraph in the appendix that explicitly walks through how the supremum over adaptive randomized policies is handled in the mutual-information term, making the accounting for adaptivity and randomization fully transparent. revision: yes
Circularity Check
No significant circularity; derivations are self-contained new constructions and bounds.
full rationale
The paper derives its central claims via a novel adaptive estimator construction (upper bounds) and a new information-theoretic lower bound for the k=2 case, both obtained directly from analysis of the adaptive randomized-threshold query model. These steps do not reduce to fitted parameters renamed as predictions, self-citations as load-bearing premises, or any of the enumerated circular patterns. The order-optimality statements follow from explicit matching of independently derived upper and lower bounds rather than by construction from inputs. The modeling assumptions (adaptive randomized thresholds) are stated explicitly and do not create definitional circularity within the derivation chain.
Assumptions & free parameters
assumptions (2)
- domain assumption The unknown distribution has mean μ bounded in [−λ, λ] and finite k-th central moment bounded by σ^k
- domain assumption Randomized threshold queries are allowed and thresholds may be chosen adaptively
Cite this review
Pith. "Pith review of Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes." pith.science (2026). https://pith.science/paper/CXKREENA
@misc{pith2026260407796,
author = {Pith},
title = {Pith review of: Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes},
year = {2026},
howpublished = {\url{https://pith.science/paper/CXKREENA}},
note = {Machine review of arXiv:2604.07796}
}
abstract
In this paper, we study the problem of mean estimation under 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is $(\epsilon, \delta)$-PAC for any distribution with a bounded mean $\mu \in [-\lambda, \lambda]$ and a bounded $k$-th central moment $\mathbb{E}[|X-\mu|^k] \le \sigma^k$ for any fixed $k > 1$. Moreover, our sample complexity is order-optimal in all such tail regimes, i.e., for every such $k$ value. For $k \neq 2$, our estimator's sample complexity matches the unquantized minimax lower bounds plus an unavoidable $O(\log(\lambda/\sigma))$ localization cost. For the finite-variance case ($k=2$), our estimator's sample complexity has an extra multiplicative $O(\log(\sigma/\epsilon))$ penalty, and we establish a novel information-theoretic lower bound showing that this penalty is a fundamental limit of 1-bit quantization. We also establish a significant adaptivity gap: for both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly with the search space parameter $\lambda/\sigma$, rendering it vastly less sample efficient than our adaptive approach. Finally, we present algorithmic variants that (i) handle an unknown sampling budget, (ii) adapt to an unknown scale parameter $\sigma$ given (possibly loose) bounds, (iii) require only two stages of adaptivity to achieve order-optimal sample complexity at the expense of more general 1-bit queries, and (iv) leverage multiple local samples per 1-bit query to proportionally reduce communication costs.
Forward citations
Cited by 3 Pith papers
-
Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation
A fully non-adaptive one-bit protocol — every query fixed before data arrives — matches the minimax-optimal adaptive sample complexity for mean estimation under finite k-th moments, answering the COLT 2026 open proble...
-
Universal Refinement without Interaction: Order-Optimal 1-Bit Mean Estimation
Fully non-adaptive public-coin 1-bit queries attain the order-optimal finite-moment mean-estimation rates previously known only for adaptive protocols.
-
Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
Is interaction necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes, or can fully non-adaptive general quantizers match the adaptive rate?
Reference graph
Works this paper leans on
-
[1]
PMLR. Paes Leme, R., Sivan, B., Teng, Y ., and Worah, P. (2023). Pricing query complexity of revenue maximization. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 399–415. SIAM. Polyanskiy, Y . and Wu, Y . (2025).Information Theory: From Coding to Learning. Cambridge University Press. Ribeiro, A. and Giannakis, G. B. (2006a). Bandwidth-constrai...
-
[2]
Ask the agentn i threshold queries “IsX i,j ěa i?” forj“1, . . . , n i, wheren i is the regional sample budget determined in Step 5
-
[3]
Generate independent random variablesT i,j „Unifpa i, biqforj“n i `1, . . . ,2n i
-
[4]
Ask the agentn i randomized threshold queries “IsX i,j ěT i,j?” forj“n i `1, . . . ,2n i
-
[5]
Compute the empirical averages based on the 1-bit feedback and perform the subtraction according to (2). The learner forms the corresponding estimateˆp bi using an analogous procedure, utilizing2n i fresh samples with queries “IsX i,j ďb i?” and “IsX i,j ďT i,j?”. We summarize the empirical estimates as ˆpai “ 1 ni ˜ niÿ j“1 1pXi,j ěa iq ¸ ´ 1 ni ˜ 2niÿ j...
work page 2020
-
[6]
For a fixed distribution pair (indexed byj), an interval queryQ““IsXP rα t, βts?” is informative for distinguishing betweenD j,´ andD j,` only ifrα t, βtscontains exactly one of the two support pointstc j ˘σ{2u, i.e., ˇˇrαt, βts X tcj ˘σ{2u ˇˇ “1
-
[7]
There are at most two indicesjfor which ˇˇrαt, βts X tcj ˘σ{2u ˇˇ “1. Fact 1 can be verified by analyzing the binary feedbackB“1tXP rα t, βtsufor all cases ofrα t, βts X tcj ˘σ{2u: ˇˇrαt, βts X tcj ˘σ{2u ˇˇ P t0,2u ù ñPr X„D j,´ pB“1q “Pr X„D j,` pB“1q ù ñQis uninformative, and ˇˇrαt, βts X tcj ˘σ{2u ˇˇ “1ù ñ ˇˇ Pr X„D j,´ pB“1q ´Pr X„D j,` pB“1q ˇˇ “ 2ϵ ...
work page 2020
Reviewed May 25, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.