Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
stat.ML · cs.IT · cs.LG · math.ST
Quick verdict
Proves non-adaptive (even i.i.d.) 1-bit queries attain adaptive minimax rates for k>1, plus the s-interval sample tradeoff; rigorous, order-wise, theoretical.
Summary
The paper resolves an open problem posed by Lau and Scarlett (2026a): whether query-side adaptivity is necessary for order-optimal distributed 1-bit mean estimation of distributions with mean in [-lambda,lambda] and bounded k-th central moment (k>1). The authors show it is not: a non-adaptive protocol, whose queries may even be i.i.d., attains the adaptive minimax sample complexity for every k>1 (Theorem 1), recovering the three known regimes — (sigma/epsilon)^2*log(1/delta) for k>2, an extra log(sigma/epsilon) factor at k=2, and (sigma/epsilon)^(k/(k-1))*log(1/delta) for 1<k<2 — plus an O(log(lambda/sigma)) localization cost. The key idea is to fix all queries in advance over dyadic cell banks, assign independent Rademacher signs per cell, and let the decoder — after localizing a center c to within 8*sigma — select cells, discard responses touching near-center intervals, and reweight by inverse probabilities to restore the tail-local variance property. A second contribution (Theorem 2) gives matching upper and lower bounds when each query's one-set is a union of at most s intervals, adding Theta_k((1/s)(lambda/sigma)(sigma/epsilon)^2*log(1/delta)) samples; Corollary 3 reads off the minimum interval budget preserving the unrestricted rate. Limitations: results are order-wise with hidden k-dependent constants, query design requires exact knowledge of (k,lambda,sigma), the setting is one-dimensional, and no empirical validation appears in the provided text.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 1
● low 3
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- For every k>1, a non-adaptive 1-bit protocol with i.i.d. queries attains the adaptive minimax sample complexity over P(k,λ,σ) (Theorem 1).
- The minimax sample complexity for non-adaptive 1-bit estimators whose queries are at most s-interval equals Θ_k(log(λ/σ) + R_k(σ/ε,δ) + (1/s)(λ/σ)(σ/ε)²·log(1/δ)) (Theorem 2).
- Every realized query one-set in the constructions is a finite union of intervals — O(λ/σ) components in Theorem 1 and at most s in Theorem 2 — unlike concurrent constructions.
- Corollary 3 identifies, up to k-dependent constants, the smallest interval budget s preserving the unrestricted 1-bit minimax sample rate.
Strengths
Complete resolution of the posed open problem in the strongest protocol class
Theorem 1 shows i.i.d. (not merely non-adaptive) queries match the adaptive minimax rates of Lau & Scarlett (2026b, Thms 5 and 9) for every k>1, with the three regimes in (1) and an O(log(λ/σ)) localization term.
Clean and fully proven decoding-side architecture shift
Figure 1 formalizes moving the center c from query selection to decoding; the near-center filter (15)-(16) with |F_i(c)|≤3 and p≥1/8, plus inverse-probability reweighting (17), provably restores tail-local variance (Lemma 3, 2304·ℓ_i²·τ_i(c) in Lemma 8); Lemmas 6-7 identities verify directly.
Genuinely new tradeoff characterization beyond matching rates
i.i.d. conversion handled rigorously, not asserted
Transparent positioning relative to concurrent work
Weaknesses
Order-wise results with unspecified k-dependent constants
Exact knowledge of (k, λ, σ) assumed for query design
Theorem 2 holds only in restricted regimes
One-dimensional setting only
Optimality leans on companion-paper lower bounds and a partially unobserved proof
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a purely theoretical contribution to communication-constrained statistical estimation. Setting: n agents each hold one sample from an unknown distribution P with mean μ ∈ [−λ, λ] and k-th central moment at most σ^k (k > 1); each agent returns one bit Y = Q(X) for a measurable query Q. The paper makes two claims. First (Theorem 1), a non-adaptive protocol — in fact with i.i.d. queries — achieves the adaptive 1-bit minimax sample complexity for every k > 1, matching (Lau & Scarlett 2026b, Theorems 5 and 9): O(log(λ/σ)) + O_k((σ/ε)²·log(1/δ)) for k > 2, an extra log(σ/ε) at k = 2, and O_k((σ/ε)^(k/(k−1))·log(1/δ)) for 1 < k < 2; each realized one-set is a finite union of O(λ/σ) intervals. Second (Theorem 2), matching bounds for non-adaptive estimators whose queries are s-interval: Θ_k(log(λ/σ) + R_k(σ/ε, δ) + (1/s)(λ/σ)(σ/ε)²·log(1/δ)), valid for ε ∈ (0, c_k·σ) and δ < δ_k; Corollary 3 reads off the minimum s preserving the unrestricted rate. The open problem answered was posed by the authors themselves (2026a); three concurrent works (Miao; Hu & Zhong; the VALG candidates) reached the same negative answer via different refinements.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Is adaptivity necessary for 1-bit mean estimation?
No. This paper proves that for distributions with mean in [-λ,λ] and bounded k-th central moment (k>1), a protocol whose queries are all fixed in advance — even drawn i.i.d. from one distribution — achieves the same minimax sample complexity as the best adaptive (sequential) protocol, answering an open question of Lau and Scarlett (2026a).
How many 1-bit samples does mean estimation need?
Up to constants depending on k: (σ/ε)²·log(1/δ) when k>2, an extra log(σ/ε) factor when k=2, and (σ/ε)^(k/(k-1))·log(1/δ) when 1<k<2, plus an additive O(log(λ/σ)) localization cost for the range λ.
What is the cost of restricting each query to at most s intervals?
An additional Θ_k((1/s)(λ/σ)(σ/ε)²·log(1/δ)) samples (Theorem 2). To keep the unrestricted-rate sample complexity, the interval budget s must grow on the order of λ/σ (order-wise, per Corollary 3).
How does this paper differ from the concurrent solutions of Miao and of Hu-Zhong?
All concurrent works collect localization and refinement bits in parallel and use the decoded center only at decoding time. Miao (2026) uses dyadic-offset and signed-grid refinements; Hu and Zhong (2026) use a successive-scale decomposition. This paper adapts the prior two-stage refinement to fixed queries, and — unlike the concurrent constructions — its queries use finitely many interval components and it uniquely proves the s-interval sample-interval tradeoff (Theorem 2).
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled 80k-char excerpt (head and tail) with explicit '[...sampling gap...]' markers; parts of Section 3's lower-bound development, Appendix C, and portions of Appendices D and F.4 were skipped, so the Theorem 2 lower bound was assessed from its statement and visible fragments only.
- The excerpt cuts off mid-Appendix F.3, so the reference list and any code/data availability statements fall beyond the end of the provided text and were not audited.
- No experiments appear in the provided text; this is consistent with a pure theory paper but was verified only against the excerpt.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.