{"id":"fdbf6b81-3516-4496-87c2-4cb0b0fc2f11","arxiv_id":"2604.07796","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper develops an order-optimal adaptive 1-bit mean estimator for distributions with bounded k-th moments and proves a novel lower bound for the variance case.","lead":"This paper proposes an adaptive estimator for the mean of a distribution using only sequential 1-bit randomized threshold queries. It achieves order-optimal sample complexity for various tail regimes and demonstrates a fundamental limit for the finite-variance case under 1-bit constraints.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Order-optimality (including the novel k=2 lower bound) is derived under the adaptive randomized-threshold query model; this is the least-secure modeling assumption for the central claim.","rationale":"The reader’s weakest_assumption already isolates the adaptive randomized-threshold model as the key precondition. Because the paper’s optimality statements (both upper and lower) are explicitly conditioned on that model, confirming or refuting the modeling assumption is the single most direct test of whether the central claim survives.","tokens_in":1922,"tokens_out":375,"duration_ms":11677,"concrete_test":"Re-derive the k=2 lower bound (the novel information-theoretic argument) under the restriction that each threshold must be a deterministic function of the query index alone and cannot depend on previous outcomes; if the resulting lower bound drops the extra log(σ/ε) factor, the claim that this penalty is unavoidable under 1-bit quantization is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim asserts that the proposed estimator is order-optimal for every fixed k>1, matching the unquantized minimax rate plus O(log(λ/σ)) except for an unavoidable extra O(log(σ/ε)) factor when k=2, which is shown to be information-theoretically necessary. All of these rates are obtained by analyzing an adaptive procedure that selects randomized thresholds sequentially on the basis of prior 1-bit answers. The adaptivity gap result likewise compares adaptive vs. non-adaptive behavior inside the same query class. If the allowed queries are restricted to deterministic or non-adaptive thresholds, both the upper bounds and the matching lower bound for the extra logarithmic penalty cease to apply, so the “fundamental limit of 1-bit quantization” statement rests on the modeling choice that randomized adaptive thresholds are permitted.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":2102,"tokens_out":637,"duration_ms":19252,"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":[{"comment":"§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.","section":"§2 and §4"},{"comment":"§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.","section":"§5"}],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive evaluation and the recommendation of minor revision. We address each major comment below.","responses":[{"response":"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_made":"yes","referee_comment":"[§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."},{"response":"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_made":"yes","referee_comment":"[§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."}],"tokens_in":1627,"tokens_out":512,"duration_ms":34003,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The core contribution is an adaptive estimator that uses randomized thresholds chosen sequentially from previous 1-bit outcomes. It achieves the unquantized minimax rate plus a localization term for k ≠ 2, and for k=2 it incurs an extra O(log(σ/ε)) factor that the authors lower-bound as unavoidable under this query model. They also prove a clear adaptivity gap: non-adaptive schemes must pay linear in λ/σ. That gap and the k=2 lower bound are the genuinely new pieces relative to prior work on quantized estimation. The constructions look technically careful on the upper-bound side, and the variants for unknown budget or unknown σ are useful practical extensions. The main limitation is that everything is derived inside the randomized adaptive threshold model. The abstract is explicit about this, but the “fundamental limit of 1-bit quantization” phrasing only holds under those assumptions; deterministic or non-adaptive thresholds change the rates. Without the full proofs it is hard to judge tightness for general k, but the abstract claims and the stress-test note line up on the modeling choice. This is for people working on communication-constrained or quantized statistical estimation. Anyone thinking about information-theoretic limits under moment conditions will find the lower bound and the adaptivity comparison worth reading. I would send it to peer review; the new lower bound and the clean separation of adaptive versus non-adaptive regimes are substantive enough to justify referee time even if some modeling caveats need tightening.","headline":"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.","tokens_in":2571,"tokens_out":373,"would_cite":true,"duration_ms":14929,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Statistical 1-bit mean estimation under adaptive threshold queries; no structural overlap with RS J-cost, φ-ladder or forcing chain.","alignment":"orthogonal","rationale":"The paper's core construction (noisy binary-search localization, universal geometric grid with ratio-2 boundaries m_i=2^i, k-dependent exponential sample allocation n_i ∝ 2^{|i|(2-k)}, median-of-means aggregation, and the novel k=2 lower-bound argument via geometric-grid hypothesis testing) lives entirely inside non-parametric statistics and communication-constrained estimation. None of these objects invoke, parallel or contradict any RS theorem (e.g., reality_from_one_distinction, Jcost uniqueness, phi_fixed_point, DimensionForcing, AlexanderDuality_circle_linking, or the 8-tick/φ-ladder machinery). The domain (stat.ML) is one on which the RS framework expresses no opinion.","tokens_in":62457,"confidence":"high","tokens_out":205,"duration_ms":8734,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"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.","keywords":["mean estimation","1-bit quantization","adaptive sampling","PAC estimation","moment bounds","sample complexity","information-theoretic lower bounds","tail regimes"],"falsifier":"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.","tokens_in":2813,"feed_emoji":"📊","tokens_out":783,"duration_ms":17336,"temperature":0.7,"pith_summary":"The paper constructs a sequential estimator that selects randomized thresholds adaptively after each 1-bit outcome and proves it is (ε, δ)-PAC for any distribution whose mean lies in a known interval and whose k-th central moment is bounded by σ^k. The sample complexity is order-optimal for every k>1: when k≠2 it recovers the best known unquantized rate together with an unavoidable localization cost of order log(λ/σ), while for k=2 it incurs an extra multiplicative log(σ/ε) factor that the authors show is information-theoretically necessary under 1-bit constraints. The same analysis yields a large adaptivity gap, showing that any non-adaptive procedure must pay a linear factor in λ/σ. Algorithmic extensions handle unknown sample budgets and unknown scale parameters while preserving the order-optimal guarantees.","feed_headline":"Adaptive 1-bit thresholds match unquantized mean rates for any k","feed_subtitle":"Sequential randomized queries achieve order-optimal samples under arbitrary moment bounds, with a proven extra log factor only for variance.","key_machinery":"The adaptive, sequential choice of randomized thresholds for 1-bit queries that both localizes the mean and refines the estimate in one pass.","core_discovery":"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 λ/σ.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Adaptive thresholds achieve order-optimal 1-bit mean estimation for all k","Sequential 1-bit queries match unquantized rates across all tail regimes","Adaptive 1-bit estimator order-optimal for every moment bound k","Order-optimal 1-bit mean estimation with adaptive thresholds for any k"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"Thresholds must be allowed to depend on all previous 1-bit outcomes and may be randomized.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive thresholds achieve order-optimal 1-bit mean estimation for all k","Sequential 1-bit queries match unquantized rates across all tail regimes","Adaptive 1-bit estimator order-optimal for every moment bound k","Order-optimal 1-bit mean estimation with adaptive thresholds for any k"]},"model":"grok-4.3","cost_usd":0.008291,"raw_usage":{"total_tokens":3841,"prompt_tokens":834,"num_sources_used":0,"completion_tokens":73,"cost_in_usd_ticks":82912000,"prompt_tokens_details":{"text_tokens":834,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2934,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":834,"tokens_out":73,"duration_ms":17712,"temperature":1.0,"reasoning_tokens":2934,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-25T06:44:39.962714+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":2}