{"id":"c1339494-f39c-4766-8475-bb98fcf764ee","arxiv_id":"2509.21940","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Develops an adaptive interval-query 1-bit mean estimator with sample complexity Õ(σ²/ε² log(1/δ) + log(λ/σ)) that is (ε,δ)-PAC and near-optimal for bounded mean-variance distributions.","lead":"The paper presents a sequential adaptive 1-bit mean estimator using randomized interval queries for distributions with known bounds on mean and variance. This achieves a sample complexity near the unquantized minimax rate up to logs plus an extra unavoidable log term, showing the value of adaptivity under communication constraints.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly flags the known λ,σ requirement, which is the explicit precondition for the stated near-optimal bound. Because the claim is not asserted for the unknown-parameter regime and variants are mentioned, this does not constitute a load-bearing flaw in the central result. The UNVERDICTED status stems from abstract-only access; the argument as summarized is internally consistent.","tokens_in":1786,"tokens_out":355,"duration_ms":52187,"concrete_test":"Re-derive the sample-complexity upper bound from the adaptive interval construction (without using the final theorem statement) for the special case of a Gaussian with mean 0, variance 1, λ= e^10, ε=0.1, δ=0.01; verify that the derived expression is at most C(100 log(1/0.01) + 10) for some small universal C.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim establishes an upper bound of Õ(σ²/ε² log(1/δ) + log(λ/σ)) for (ε,δ)-PAC mean estimation under known bounds λ on the mean and σ² on the variance, using adaptive sequential interval queries. This is asserted to match the unquantized minimax rate up to logs plus an unavoidable extra term for which a matching lower bound is provided (at least for interval-query estimators). The abstract explicitly states the known-parameter assumption and notes variants for unknown variance, so the primary result is scoped correctly. No internal inconsistency, hidden dependence on stronger tail assumptions, or unaccounted adaptivity cost appears in the high-level argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces a sequential adaptive mean estimator using randomized interval queries under 1-bit communication. For distributions with known bounds λ on the mean and σ on the standard deviation, it achieves (ε, δ)-PAC estimation with sample complexity Õ(σ²/ε² log(1/δ) + log(λ/σ)). This nearly matches the minimax lower bound from the unquantized setting, and the paper provides a matching lower bound showing the extra log term is unavoidable for interval-query estimators. It further establishes an adaptivity gap, provides bounds for sub-Gaussian tails, and includes variants for unknown parameters and limited adaptivity.","tokens_in":1937,"tokens_out":519,"duration_ms":50464,"significance":"This contribution is significant for the field of distributed and communication-constrained statistical estimation. By achieving near-optimal sample complexity with minimal communication via adaptive queries, it shows that adaptivity can mitigate the cost of quantization. The explicit lower bound for the adaptivity gap and the extensions to unknown variance make the results more robust and applicable. Credit is due for the parameter-free aspects in the core bound and the reproducible theoretical analysis if proofs are complete.","major_comments":[{"comment":"§4.1, Eq. (8): The recursive definition of the interval centers in the adaptive procedure assumes prior knowledge of σ; the variance reduction step should be shown to hold uniformly over all possible distributions satisfying the variance bound.","section":null},{"comment":"§6, Theorem 3: In the proof of the lower bound, the information-theoretic argument uses KL divergence between specific two-point distributions; confirm that this extends to the general case with bounded variance without additional tail assumptions.","section":null}],"minor_comments":[{"comment":"Abstract: The notation for the sample complexity bound uses Õ; ensure consistency with the definition provided in Section 2.","section":null},{"comment":"Section 3: The description of the randomized interval query could benefit from a pseudocode algorithm to improve clarity.","section":null},{"comment":"References: Several recent works on 1-bit quantization in estimation (e.g., from 2023-2024) are missing; consider adding them for completeness.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is well-written at a high level, but given the low confidence in the full proof details from the initial review, I recommend the authors provide the complete technical sections for verification. No concerns about scope or citations."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the thorough review and constructive comments on our work. We address each major comment below in detail. The manuscript has been revised to incorporate clarifications where appropriate, strengthening the presentation without altering the core results.","responses":[{"response":"We appreciate this observation. As stated in the problem setup (Section 2), σ is a known upper bound on the variance. The recursive construction in Eq. (8) employs this known σ to determine interval widths and centers. The variance reduction argument in the analysis of the adaptive procedure relies solely on the bound Var(X) ≤ σ² together with the mean bound |E[X]| ≤ λ; it does not require knowledge of the exact variance or any further distributional properties. Consequently, the guarantees hold uniformly over the entire class of distributions satisfying these moment bounds. We have added a clarifying remark immediately following Eq. (8) to make this uniformity explicit.","revision_made":"yes","referee_comment":"§4.1, Eq. (8): The recursive definition of the interval centers in the adaptive procedure assumes prior knowledge of σ; the variance reduction step should be shown to hold uniformly over all possible distributions satisfying the variance bound."},{"response":"The lower bound of Theorem 3 applies to the minimax risk over all distributions with |E[X]| ≤ λ and Var(X) ≤ σ². The proof proceeds by exhibiting a pair of two-point distributions that lie inside this class (each with variance exactly equal to σ²) and applying the standard KL-based information-theoretic argument to this pair. Because the minimax quantity is at least as large as the risk on any subclass, the resulting lower bound carries over directly to the full class. No tail assumptions beyond the variance bound are invoked. We have inserted a short paragraph at the beginning of the proof of Theorem 3 to emphasize that the constructed distributions satisfy the problem constraints and that the argument requires no additional assumptions.","revision_made":"yes","referee_comment":"§6, Theorem 3: In the proof of the lower bound, the information-theoretic argument uses KL divergence between specific two-point distributions; confirm that this extends to the general case with bounded variance without additional tail assumptions."}],"tokens_in":1448,"tokens_out":481,"duration_ms":23909,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that this paper shows how to do 1-bit mean estimation with an adaptive sequence of interval queries and gets a sample complexity of Õ(σ²/ε² log(1/δ) + log(λ/σ)) that is near-optimal. They also prove the log term is unavoidable for this query class and demonstrate a noticeable gap between adaptive and non-adaptive estimators when λ/σ is large.","headline":"Adaptive sequential interval queries give a 1-bit mean estimator whose sample complexity matches the unquantized rate up to logs plus a necessary extra log(λ/σ) term.","tokens_in":2401,"tokens_out":169,"would_cite":false,"duration_ms":27716,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"We derive a sample complexity bound Õ(σ²/ε² log 1/δ + log λ/σ), which matches the minimax lower bound for the unquantized setting up to logarithmic factors and the additional log λ/σ term"},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/RealityFromDistinction.lean","rs_theorem":"reality_from_one_distinction","paper_passage":"Our estimator is (ε, δ)-PAC for all distributions with bounded mean (−λ ≤ E(X) ≤ λ) and variance (Var(X) ≤ σ²)"}],"headline":"Statistical 1-bit adaptive mean estimation; no overlap with RS forcing chain or J-cost structures","alignment":"orthogonal","rationale":"Paper derives Õ(σ²/ε² log(1/δ) + log(λ/σ)) sample complexity for PAC mean estimation via adaptive interval queries, localization/refinement, Hoeffding/Bernstein concentration, and information-theoretic lower bounds on hard distribution pairs. Central machinery is classical statistical estimation under communication constraints. RS framework (reality_from_one_distinction, Jcost uniqueness via washburn_uniqueness_aczel, phi-ladder, 8-tick periodicity, AlexanderDuality for D=3) has no theorems or structures that apply to quantization, adaptivity gaps, or variance-bounded mean estimation. Domain mismatch is total; no ratio-symmetric cost, golden-ratio identities, or parameter-free constant derivations appear.","tokens_in":66143,"confidence":"high","tokens_out":388,"duration_ms":12704,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Sequential 1-bit interval queries can estimate the mean of bounded-mean bounded-variance distributions with sample complexity matching the unquantized minimax rate up to logarithmic factors plus an unavoidable log term.","keywords":["mean estimation","1-bit communication","sequential queries","sample complexity","PAC learning","adaptive estimation","interval queries","distributed statistics"],"falsifier":"A calculation showing a distribution with |mean| ≤ λ and Var ≤ σ² that requires strictly more than O(log λ/σ) extra samples beyond the main σ²/ε² term, or an explicit non-adaptive estimator that matches the adaptive rate even for large λ/σ.","tokens_in":2690,"feed_emoji":"📈","tokens_out":765,"duration_ms":35146,"temperature":0.7,"pith_summary":"The paper develops a mean estimator that uses randomized interval queries chosen sequentially based on previous 1-bit outcomes. Each query asks whether a new sample falls inside a chosen interval, providing 1 bit of information. This adaptive approach achieves an (ε, δ)-PAC guarantee with sample complexity Õ(σ²/ε² log 1/δ + log λ/σ) for distributions with mean bounded by λ and variance by σ². A sympathetic reader would care because this nearly matches the best possible rate even without any communication constraints, showing that 1-bit sequential feedback loses little efficiency. The work also proves that non-adaptive estimators cannot achieve the same rate when the ratio λ/σ is large.","feed_headline":"Adaptive 1-bit queries achieve near-optimal mean estimation","feed_subtitle":"Sequential interval queries match unquantized sample complexity up to logs plus an unavoidable log(λ/σ) term for bounded mean and variance.","key_machinery":"Sequentially chosen randomized interval queries, where each 1-bit response indicates whether the sample lies in the adaptively selected interval, allowing progressive refinement of the mean estimate with minimal communication.","core_discovery":"The authors prove that their adaptive interval-query estimator is (ε, δ)-PAC for any distribution satisfying |E[X]| ≤ λ and Var(X) ≤ σ² using Õ(σ²/ε² log(1/δ) + log(λ/σ)) samples. This bound matches the minimax lower bound for the unquantized (full-information) setting up to logarithmic factors, with the extra log(λ/σ) term shown to be necessary even for interval queries. They further establish an adaptivity gap, where the best non-adaptive mean estimator requires substantially more samples for large λ/σ.","pith_inferences":["Such methods could enable efficient distributed mean estimation in resource-constrained networks where only 1 bit per sample can be sent.","Extending this to multi-dimensional means or other statistics might follow similar adaptive query strategies.","The two-stage variant suggests limited adaptivity suffices for near-optimal performance.","Practical tests with real data varying λ/σ would show where the extra log term becomes noticeable."],"forward_implications":["The estimator works for all distributions with the given bounds on mean and variance.","It achieves near-optimality compared to full-precision sampling.","Non-adaptive interval-query estimators are provably worse when λ/σ is large.","Variants exist for unknown sampling budget and unknown variance within bounds.","Stronger tail decay allows tightened bounds."],"fun_headline_variants":["Adaptive 1-bit queries near optimal mean estimation","Sequential interval queries match minimax mean complexity","1-bit adaptive estimation matches unquantized up to logs","Adaptive queries superior to non-adaptive in mean estimation"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The bounds λ on the mean and σ on the standard deviation are known in advance and used to design the sequence of interval queries.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive 1-bit queries near optimal mean estimation","Sequential interval queries match minimax mean complexity","1-bit adaptive estimation matches unquantized up to logs","Adaptive queries superior to non-adaptive in mean estimation"]},"model":"grok-4.3","cost_usd":0.013493,"raw_usage":{"total_tokens":5813,"prompt_tokens":778,"num_sources_used":0,"completion_tokens":59,"cost_in_usd_ticks":134928000,"prompt_tokens_details":{"text_tokens":778,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":4976,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":778,"tokens_out":59,"duration_ms":68494,"temperature":1.0,"reasoning_tokens":4976,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-18T13:31:04.559596+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A calculation showing a distribution with |mean| ≤ λ and Var ≤ σ² that requires strictly more than O(log λ/σ) extra samples beyond the main σ²/ε² term, or an explicit non-adaptive estimator that matches the adaptive rate even for large λ/σ.","supporting_citations":[],"review_version":1}