{"id":"38d59fed-7398-4716-a412-2b76d3c78088","arxiv_id":"2608.02538","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"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 problem in the negative.","lead":"This paper shows that estimating a distribution's mean from one-bit-per-sample messages does not require a second interactive round to hit the statistically optimal rate: all queries can be fixed before seeing any data. The construction settles a 2026 COLT open problem, but a numerical slip in the paper's main variance bound needs repair.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Variance bound (4.6) is arithmetically false as printed: (1536+6144·16)/222 ε² = 449.7 ε² ≫ ε²/32, so the Chebyshev and median steps do not follow; the constant 222 must be ~3.2×10^6 to preserve the stated rates.","rationale":"The reader's weakest assumption is exactly the load-bearing concern: the numerical variance accounting in (4.4)–(4.6) is false as printed. I independently checked the supporting identities used before and after the faulty display: Lemma 3.2's fixed-scale estimator, the tail-weighted second-moment bound, the tail summation (4.5), and the rate summation are internally consistent, assuming the ceiling in the definition of M in (3.14). No deeper flaw in the query construction was found. The error is an off-by-constant in the replicate count that is repairable: increasing the 222 in (3.14) to about 3.2×10^6 preserves every stated rate and the minimax conclusion, provided the imported localization guarantee and lower bound are accepted. Therefore the appropriate verdict remains CONDITIONAL, not a rejection of the core construction.","tokens_in":14758,"tokens_out":11422,"duration_ms":104563,"concrete_test":"Recompute (4.4)–(4.6) with the stated N_i = ⌈222 s0² 2^{i(2−κ)} / ε²⌉: the i = 0 variance term alone is 1536/222 ε² ≈ 6.92 ε², already violating ε²/32. Then replace the constant 222 by C = 3,194,880 in (3.14) and verify that (1536 + 6144 Σ_{i=1}^M 2^{iκ} p_i) ε²/C ≤ ε²/32 holds using (4.5). If the corrected inequality holds and the rates are unchanged, the proof is repaired without affecting the stated sample complexity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1.1 depends on Chebyshev (4.7) and median amplification (4.8), both of which require Var(μ̂_r | F_loc) < ε²/32. Equation (4.6) claims this from (3.14) and (4.5), but the displayed arithmetic is wrong: (1536 + 6144·16)/222 = 99840/222 ≈ 449.7, not < 1/32. Even the i = 0 term alone is 1536/222 ≈ 6.92 ε², already exceeding ε²/32. Thus Theorem 1.1 is not established as printed. The failure is specifically in the numerical variance accounting, not in the center-independent query construction: replacing the replicate-count constant 222 with any C ≥ 99840·32 = 3,194,880 in (3.14) makes (4.6) valid. Since C is O_k(1), the three refinement rates in (1.1) and the minimax conclusion are unchanged. A secondary caveat is that Proposition 2.1 and the matching lower bound are imported from an unreviewed Lau–Scarlett preprint, so the optimality claim inherits their status; this is independent of the arithmetic flaw.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14980,"tokens_out":5273,"duration_ms":50994,"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":[{"comment":"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":"Section 4, Eq. (4.6)"},{"comment":"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.","section":"Section 2/Proposition 2.1"}],"minor_comments":[{"comment":"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":"Section 4, just before (4.6)"},{"comment":"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.","section":"Section 4, sample complexity paragraph"},{"comment":"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.","section":"Appendix E, Eq. (E.4)"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The arithmetic error in (4.6) is substantive enough to invalidate the proof as written, but it is a constant-factor fix and does not threaten the construction or the claimed rates. I am recommending major revision rather than rejection. The editor may also want to verify the status of the heavily cited Lau–Scarlett preprints (2026a, 2026b), since the optimality and localization guarantees depend on them; if those preprints are not eventually published or peer-reviewed, the paper's external dependencies should be flagged more prominently."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the headline: the main claim is likely correct, but Theorem 1.1 is not proven as printed. The paper gives a fully non-adaptive one-bit protocol matching the adaptive minimax rate for D_k(λ,σ), answering Lau and Scarlett's COLT 2026 Open Problem 1 in the negative. The mechanism is genuinely new — fixed-scale refinement queries that don't depend on the localized center, using a random grid shift, pairwise-independent block signs, and a second query to supply the selected-block mass. If the variance accounting is fixed, this is a real result.\n\nCredit where it's earned. I re-derived the core identities and they're sound: the step-integration identity (3.1), Lemma 3.2's conditional unbiasedness and tail-weighted second-moment bounds, the telescoping decomposition, the tail bound (4.5), and the rate sums. Appendix C is a nice touch — they show a deterministic grid shift fails outright and explain why randomization is needed. They also disclose concurrent work by Miao; no overclaiming.\n\nThe soft spot is specific, and it's load-bearing. Equation (4.6) asserts\n\n(1536 + 6144·16)/222 ε² = 99840/222 ε² < ε²/32,\n\nbut 99840/222 ≈ 449.7. Even the i = 0 term alone is 1536/222 ≈ 6.9 ε². The Chebyshev bound (4.7) and the median argument (4.8) both require Var < ε²/32, so the proof as written fails exactly there. It's repairable: replace 222 by any constant ≥ 99840·32 ≈ 3.2×10^6 and (4.6) holds, with all rates unchanged. That makes this a gap in the proof, not a refutation of the result — but the constant is off by orders of magnitude, and a referee should ask the authors to recheck every constant in Section 4, not just this line.\n\nTwo smaller caveats. Proposition 2.1 (localization) and the matching lower bound are imported from an unreviewed Lau–Scarlett preprint, so the optimality claim inherits that status. And the paper's own numbers in the sample-complexity sum deserve a second look once the constants are redone.\n\nWho it's for: anyone in communication-constrained or one-bit mean estimation, and anyone tracking when adaptivity is essential in interactive estimation. It deserves a serious referee — important question, novel construction, one demonstrable arithmetic error with a clear repair. Send it, but instruct the reviewer to verify constants.","headline":"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.","tokens_in":15641,"tokens_out":9690,"would_cite":true,"duration_ms":93746,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F10","62G05","62G32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["one-bit mean estimation","fully non-adaptive protocols","minimax sample complexity","heavy-tailed distributions","central moment constraints","randomized block queries","adaptive vs non-adaptive","median-of-means"],"falsifier":"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.","tokens_in":14443,"feed_emoji":"📊","tokens_out":6192,"duration_ms":69192,"temperature":0.7,"pith_summary":"The paper tries to prove that, for distributions on the real line with bounded mean and bounded k-th central moment, a randomized protocol that fixes all one-bit queries before seeing any data can match the sample complexity of the best adaptive protocols. It identifies the previously open question of whether interaction between localization and refinement is essential, and answers it in the negative for general measurable queries. A sympathetic reader would care because this means one-bit distributed estimation can be run as a single batch where users precompute their queries, while still achieving order-optimal accuracy across heavy-tailed regimes. The main proof devices are a randomly shifted block partition, pairwise-independent block signs, and a two-query construction that yields an exactly conditionally unbiased estimator at every scale.","feed_headline":"Fully nonadaptive protocol hits adaptive lower bound for 1-bit means","feed_subtitle":"Randomized block queries fixed before data give the same order-optimal rate as interactive designs.","key_machinery":"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","core_discovery":"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,","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Nonadaptive 1-bit means match adaptive optimal rate","Interaction not needed for optimal 1-bit mean estimation","Nonadaptive protocol matches adaptive lower bound for 1-bit means","No interaction needed: 1-bit means are order-optimal nonadaptively","Randomized block queries cut interaction for optimal 1-bit means"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Nonadaptive 1-bit means match adaptive optimal rate","Interaction not needed for optimal 1-bit mean estimation","Nonadaptive protocol matches adaptive lower bound for 1-bit means","No interaction needed: 1-bit means are order-optimal nonadaptively","Randomized block queries cut interaction for optimal 1-bit means"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000473,"raw_usage":{"total_tokens":2250,"prompt_tokens":870,"completion_tokens":1380,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":1295}},"tokens_in":614,"tokens_out":1380,"duration_ms":11118,"temperature":1.0,"reasoning_tokens":1295,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T05:13:08.038320+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}