{"id":"01e60361-665f-43cc-951b-63a69ad69d2f","arxiv_id":"2501.18502","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For one-bit distributed mean estimation with unknown variance, a two-round adaptive protocol achieves the optimal asymptotic MSE, and for many log-concave distributions no non-adaptive protocol can match it.","lead":"This paper studies how to estimate an unknown mean when each of many users sends just one bit, and the variance is also unknown. It shows that a simple two-round adaptive protocol is optimal and strictly beats any one-round non-adaptive protocol for several common distributions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Non-adaptive lower bound is invalid: T(f_X) in Table 2 uses the wrong branch of h and contradicts an explicit threshold-encoder Hellinger calculation, so the claimed adaptivity gap is unproven.","rationale":"The reader's weakest-assumption analysis correctly identified Theorem 3.2 as the load-bearing step, but the more serious problem is internal: the Hellinger bound used in that theorem is numerically contradicted by an explicit allowed encoder, and the discrepancy comes from an ambiguity in h^{-1}. The paper defines h(x)=2phi'(x)f_X(x) and h* = max_{x>=0} h(x), then writes T = integral_0^{h*} phi'(h^{-1}(t)) h^{-1}(t) dt without specifying that h is two-to-one on each side of its maximum. In the proof of Theorem B.1, x_a(eps) is the supremum of the superlevel set {|f(x+eps)-f(x-eps)| >= a}, which for small eps is approximately {h(x) >= a/eps}; its upper endpoint is on the decreasing right branch of h, not the increasing left branch. The numerical values in Table 2 are consistent with the left branch: for GGD beta=1.5 they give T=0.040, while the right-branch integral is about 1.6. This is not merely a factor-two looseness: the tabulated T is smaller than the Hellinger distance induced by the simple threshold encoder Y=1{X<=0}, which is 2 f_X(0)^2 eps^2 + o(eps^2) ~ 0.453 eps^2 for beta=1.5. Hence Theorem B.1, as used, is false, and the derived C_non is not a valid lower bound. The adaptive upper and lower bounds (Theorems 4.1 and 4.3) may still be correct, and the paper's non-adaptive protocol analysis (Theorem 3.1 modulo the noted K-factor typo) may be salvageable, but the main information-theoretic contribution, the quantified strict suboptimality of non-adaptive protocols, rests entirely on the invalid lower bound. The simulations cannot repair this because they compare particular schemes at finite n, not the asymptotic minimax lower bound, and they lack error bars. Therefore the appropriate verdict is rejection of the central claim as currently supported; a corrected Hellinger analysis would be needed to see whether any positive gap survives.","tokens_in":32874,"tokens_out":22747,"duration_ms":230279,"concrete_test":"Recompute the T integral in Theorem 3.2 using x_a(eps) as the right-continuous decreasing inverse of h on [x*, infinity), i.e. T = integral_{x*}^{infty} phi'(x) x |h'(x)| dx for GGD beta=1.5 and for the hyperbolic secant. If the resulting C_non = 0.1034/T falls below C_adapt = 1/(4 f_X(0)^2), the claimed gap collapses. Independently, evaluate H^2 between Bern(1/2 - f_X(0)eps) and Bern(1/2 + f_X(0)eps) for the allowed encoder Y=1{X<=0}; if this exceeds eps^2 T(f_X) for the tabulated T, Theorem B.1 is false.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim that adaptive protocols strictly beat all non-adaptive protocols for generalized Gaussian beta<1.85 and for the hyperbolic secant rests on Theorem 3.2's lower bound C_non = 0.1034 / T(f_X), which depends on Theorem B.1's per-letter bound H^2(P_Yi^+, P_Yi^-) <= eps^2 T(f_X). This bound is not valid as stated and is contradicted by the values in Table 2. For GGD beta=1.5, Table 2 gives T=0.040. But the simple allowed encoder Y = 1{X <= 0} under the two hypotheses mu = +/- eps*sigma (taking sigma=1, mu=0 after location shift) yields Bernoulli probabilities 1/2 +/- f_X(0) eps + o(eps). With the paper's definition H^2 = (1/2) sum (sqrt(p+)-sqrt(p-))^2, this gives H^2 = 2 f_X(0)^2 eps^2 + o(eps^2) = 0.453 eps^2, an order of magnitude larger than 0.040 eps^2. The source is branch ambiguity: h(x)=2 phi'(x) f_X(x) is not monotone; it rises from 0 to a maximum h* and then decays. The proof's x_a(eps) = sup A_eps(a) is the rightmost point of the superlevel set, i.e. the decreasing (right) branch of h, but the numerical T in Table 2 corresponds to the increasing (left) branch. Recomputing T on the correct right branch for beta=1.5 gives T approximately 1.6, so C_non = 0.1034/T is about 0.06, far below C_adapt = 1.10. The same problem afflicts all Table 2 entries: each T is smaller than 2 f_X(0)^2, which is the minimum required by the threshold-at-the-mean encoder. Thus the strict suboptimality gap claimed in Sections 2.2 and 4.3 is not established; it is an artifact of an invalid Hellinger bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies one-bit distributed mean estimation for scale-location families with unknown variance. It proposes a two-threshold non-adaptive protocol, a multi-threshold non-parametric estimator, and a two-round adaptive protocol, and derives asymptotic normality and mean-squared-error limits for these schemes. It also gives lower bounds: a Van Trees-based lower bound for adaptive protocols and a Le Cam/Hellinger-based lower bound for non-adaptive protocols. The headline claim is that for generalized Gaussian distributions with 1 < beta < 1.85 and for the hyperbolic secant, the asymptotic minimax MSE of the best non-adaptive protocol is strictly larger than the σ²/(4 f_X(0)²) achieved by the simple adaptive protocol.","tokens_in":33326,"tokens_out":19297,"duration_ms":178618,"significance":"If correct, the paper would establish a clean separation between adaptive and non-adaptive one-bit protocols for a broad class of symmetric log-concave distributions. The adaptive-protocol half is a genuine contribution: the two-round protocol is simple, the claimed optimal constant σ²/(4 f_X(0)²) is plausible, and the lower-bound strategy via Van Trees and per-letter Fisher information bounds is credible. The non-adaptive lower bound is also an interesting approach. However, the main advertised strict-suboptimality gap is currently not supported: the numerical evaluation of T(f_X) in Table 2 uses the wrong branch of the non-monotone function h, and the same error propagates into Figures 3–6 and the claims in Sections 2.2 and 4.3. The paper therefore needs substantial correction before its central claim can be considered established. No code or data are provided, but the appendices contain lengthy proofs.","major_comments":[{"comment":"The constant T(f_X) is evaluated on the wrong branch of h(x)=2φ'(x)f_X(x). For GGD beta=1.5, f_X(0)≈0.476, so the threshold encoder Y=1{X≤0} under μ=±ε (σ=1) gives Bernoulli probabilities 1/2 ± f_X(0)ε + o(ε). With the paper's H² convention, this yields H²(P_Y⁺,P_Y⁻) = 2 f_X(0)² ε² + o(ε²) ≈ 0.453 ε². Theorem B.1 therefore forces any valid T(f_X) to be at least ≈0.453, but Table 2 reports T=0.040. The resolution is that h is non-monotone: the proof's x_a(ε)=sup A_ε(a) selects the decreasing (right) branch of h, while the numerical T in Table 2 corresponds to the increasing (left) branch. Recomputing on the right branch gives T≈1.4 for beta=1.5, so C_non=0.1034/T≈0.074, far below C_adapt=1.1035. The claimed strict suboptimality gap for GGD beta<1.85 and for the hyperbolic secant is therefore not established; it is an artifact of the branch choice. All Table 2 entries need to be recomputed with the branch that is actually used in the proof.","section":"§3.3, Theorem 3.2; §4.3, Table 2; Appendix B"},{"comment":"The asymptotic MSE formulas in Theorem 3.1 are algebraically incorrect. From Eq. (23), sqrt(n_i)(α_i − (θ_i−μ)/σ) converges to N(0, σ_i²/f_i²). Since n_i=K_i n, the corresponding sqrt(n) covariance is σ_i²/(K_i f_i²), not K_i σ_i²/f_i². The covariance matrix Σ in the delta-method step should therefore be diag(σ_1²/(K_1 f_1²), σ_2²/(K_2 f_2²)), and the factors K_1, K_2 belong in the denominator in the final formulas. This invalidates the displayed expressions for n·MSE(μ̂_c) and n·MSE(σ̂_c) and the simulation curves labeled 'Asymptotic (Non-adaptive)' in Section 5. It does not by itself invalidate Theorem 4.1, but it is a correctness error in a stated theorem used for benchmarking.","section":"§3.2, Theorem 3.1 and Appendix A"},{"comment":"The proof of Theorem B.1 assumes that the superlevel set A_ε(a) is a symmetric interval and that h^{-1} is single-valued on [0,h^*]. This requires h to be unimodal, which is not implied by the stated assumptions (φ symmetric, differentiable, strictly convex, polynomially bounded). The custom density in Eq. (20), with its 0.0675 sin²(4x/2.023076) perturbation, is an example where h is not obviously single-peaked. If h has multiple local maxima, the equivalence x_a(ε)=h^{-1}(a/(2ε)+o(1)) can fail, and the change of variables that defines T(f_X) is not justified. The theorem statement should either add a unimodality condition on h or the proof should be extended to handle non-unimodal h.","section":"Appendix B, Theorem B.1"}],"minor_comments":[{"comment":"The second line of Eq. (23) writes sqrt(n_2)(α_1 − ...) but should refer to α_2.","section":"Appendix A, Eq. (23)"},{"comment":"The displayed bound in Lemma C.1 contains '+exp(η log n_3/3)' inside the second factor. With the plus sign the right-hand side diverges as n_3→∞, so the lemma would not imply the claimed convergence. Lemmas H.1 and H.2 have a minus sign in the same place, suggesting a typo, but the statement should be corrected.","section":"Appendix H, Lemma C.1"},{"comment":"The sentence 'Using the fact that equation 58 holds for every δ>0' cites Eq. (58), which is the final lower bound; the intended reference appears to be the bound in Lemma D.1.","section":"Appendix D, proof of Theorem 4.3"},{"comment":"The notation σ_i² in Theorem 3.1 collides with the true scale parameter σ; a different symbol, such as v_i, would avoid confusion.","section":"Notation, Theorem 3.1"}],"recommendation":"major_revision","confidential_remarks":"The branch error in T(f_X) is decisive: it invalidates the paper's headline claim that non-adaptive protocols are strictly suboptimal for generalized Gaussian beta<1.85 and for the hyperbolic secant. The adaptive-protocol analysis and its matching lower bound appear salvageable, but the manuscript should not be accepted until the authors recompute T(f_X) on the correct branch, correct Theorem 3.1, and substantially revise the claims and figures. If the recomputation shows that no positive gap remains for the named distributions, the paper's scope and significance will need to be reassessed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the adaptive protocol and its analysis are probably right, but the paper's headline claim—that non-adaptive protocols are strictly suboptimal for unknown variance—is not supported. The non-adaptive lower bound rests on a squared Hellinger bound (Theorem B.1) that is invalid, and the numerical values of T(f_X) that produce the claimed gap come from the wrong branch of h(x). On top of that, Theorem 3.1's MSE formulas have an algebraic slip.\n\nThe problem is well-motivated, and the paper does real work. Extending Kipnis and Duchi to scale-location families with unknown variance is a natural next step, and the two-round adaptive scheme is simple and sensible. The proof of Theorem 4.1 (asymptotic normality with variance σ^2/(4f_X(0)^2)) is careful, and the Van Trees lower bound in Theorem 4.3 looks credible. If the adaptive upper and lower bounds hold up, that is a solid contribution.\n\nThe soft spot is load-bearing. The stress-test example is decisive: for GGD with β=1.5, Table 2 lists T(f_X)=0.040, but the allowed encoder Y=1{X≤0} between hypotheses µ=±εσ gives H^2≈2f_X(0)^2 ε^2≈0.453 ε^2. A universal upper bound of 0.040 ε^2 cannot stand next to that instance. The reason is branch ambiguity: x_a(ε) is the supremum of the superlevel set, which is the right (decaying) branch of h, but the numbers in Table 2 match the left (rising) branch. On the right branch for β=1.5, T is about 1.6, so C_non≈0.06, well below C_adapt≈1.10. The strict gap for β<1.85 and the hyperbolic secant is therefore unproven. The same problem likely affects all Table 2 entries.\n\nSeparately, Theorem 3.1 states the asymptotic MSE with K_i σ_i^2/f_i^2 in the covariance, but the delta method gives σ_i^2/(K_i f_i^2). That's a clean algebraic error, independent of the Hellinger issue.\n\nThe adaptive theorems may be salvageable, and the problem deserves attention, but the paper currently overclaims. I'd send it to peer review—the adaptive part is worth referee time—and the referee should insist that the non-adaptive lower bound either be proved correctly or explicitly demoted to a conjecture.","headline":"The adaptive protocol and its analysis look solid, but the paper's headline claim—strict suboptimality of non-adaptive protocols—rests on an invalid Hellinger bound and the wrong branch of h, so the current version overclaims.","tokens_in":33888,"tokens_out":7452,"would_cite":false,"duration_ms":64634,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A two-round adaptive protocol achieves the exact asymptotic MSE for one-bit mean estimation with unknown variance, and non-adaptive protocols provably fall behind for many log-concave distributions.","keywords":["one-bit communication","distributed mean estimation","unknown variance","adaptive protocols","minimax MSE","log-concave distributions","generalized Gaussian","squared Hellinger distance"],"falsifier":"Evaluate $T(f_X)$ for the standard normal: if $0.1034/T(f_X)\\le 1/(4f_X(0)^2)$, the lower bound does not certify a gap for the Gaussian, matching the paper's Figure 10. A decisive test would be to exhibit, for one distribution in the stated class, a non-adaptive threshold protocol whose large-$n$ MSE is below $0.1034\\,\\sigma^2/T(f_X)$, which would falsify Theorem 3.2.","tokens_in":32632,"feed_emoji":"📊","tokens_out":17191,"duration_ms":139057,"temperature":0.7,"pith_summary":"The paper settles the leading constant of one-bit distributed mean estimation when the variance is also unknown. It shows that a simple two-round adaptive scheme—first a coarse estimate from a vanishing fraction of users, then a thresholded second round at the estimated mean—achieves asymptotic mean squared error $\\sigma^2/(4 f_X(0)^2)$ per user. It proves a matching lower bound for all sequential one-bit adaptive protocols on symmetric strictly log-concave densities whose Fisher-information profile is maximized at the origin, so the scheme is asymptotically minimax. On the non-adaptive side, it gives a universal lower bound $0.1034\\,\\sigma^2/T(f_X)$; for generalized Gaussian shape parameter $\\beta<1.85$ and for the hyperbolic secant this exceeds the adaptive value, so one-shot protocols are provably inferior. The paper's simulations confirm the gap.","feed_headline":"With unknown variance, two-round one-bit estimation beats one-shot","feed_subtitle":"Adaptive scheme hits the asymptotic MSE limit; one-shot schemes fall behind for common distributions.","key_machinery":"The non-adaptive lower bound is carried by a refined squared-Hellinger analysis. For two nearby means $\\mu\\pm\\epsilon\\sigma$, the shifted densities are decomposed into level sets of their pointwise difference, and Theorem B.1 bounds the per-user Hellinger distance between the induced one-bit transcripts by $\\epsilon^2(T(f_X)+o(1))$, where $h(x)=2\\varphi'(x)f_X(x)$, $h^*=\\max_{x\\ge0}h(x)$, and $T(f_X)=\\int_0^{h^*}\\varphi'(h^{-1}(t))h^{-1}(t)\\,dt$. Le Cam's two-point method then converts this into the universal constant $0.1034$. The adaptive lower bound uses the Van Trees inequality (the Bayesian Cramér–Rao bound) together with Lemma D.1, which bounds the Fisher information of any single one-bit observation by $(2f_X(0)/\\sigma)^2+\\delta$; its reciprocal gives $\\sigma^2/(4f_X(0)^2)$. The upper bound is quantile inversion at a broadcast threshold.","core_discovery":"The central claim, in the authors' terms, is that unknown variance changes the comparison between adaptive and non-adaptive one-bit mean estimation in a quantifiable way. Theorem 4.1 gives $\\lim_{n\\to\\infty} n\\,\\mathrm{MSE}(\\hat\\mu_f)=\\sigma^2/(4f_X(0)^2)$ for the two-round protocol, and Theorem 4.3 shows any sequential adaptive protocol satisfies $\\lim n\\,\\mathbb{E}[(\\hat\\mu-\\mu)^2]\\ge\\sigma^2/(4f_X(0)^2)$ under a shape condition on $\\eta(x)=f_X(x)^2/(F_X(x)F_X(-x))$. Theorem 3.2, by contrast, gives $\\lim \\sup_\\mu n\\,\\mathrm{MSE}(\\hat\\mu)\\ge 0.1034\\sigma^2/T(f_X)$ for every non-adaptive protocol over symmetric strictly log-concave $f_X=e^{-\\varphi(x)}$. Comparing $C_{\\mathrm{adapt}}=1/(4f_X(0)^2)$ with $C_{\\mathrm{non}}=0.1034/T(f_X)$ shows that the non-adaptive floor is strictly higher for generalized Gaussian densities with $1<\\beta<1.85$ and for the hyperbolic secant, establishing a positive gap.","pith_inferences":["A sharper distribution-dependent replacement for the universal constant $0.1034$ in Theorem 3.2 could extend the strict gap beyond $\\beta<1.85$; the paper already conjectures its non-adaptive lower bound is loose.","The per-bit Fisher-information bound suggests a quantitative multi-bit analogue: most of the benefit of adaptivity is captured by the first bit, and extra bits should buy only a limited constant-factor improvement.","The layer-cake/Hellinger construction is not tied to scalar thresholds and could plausibly give non-adaptive lower bounds for high-dimensional mean estimation under coordinatewise one-bit constraints, one of the open directions named by the authors."],"forward_implications":["For every distribution satisfying the conditions of Theorem 4.3, the two-round protocol is asymptotically minimax among sequential one-bit adaptive protocols, so no additional rounds can reduce the constant.","For generalized Gaussian densities with $1<\\beta<1.85$ and for the hyperbolic secant, every non-adaptive one-bit protocol has asymptotic MSE at least $C_{\\mathrm{non}}\\sigma^2/n$ with $C_{\\mathrm{non}}>C_{\\mathrm{adapt}}$, giving a provable price for non-adaptivity.","The two-threshold non-adaptive scheme also yields a strongly consistent estimator of the scale parameter $\\sigma$ with asymptotic MSE of order $1/n$, although the paper does not claim optimality for variance estimation.","The nonparametric multi-threshold estimator extends one-bit mean estimation beyond scale-location families, but its MSE is not $O(1/n)$ unless the support is bounded, so parametric structure is what delivers the fast rates."],"supporting_citations":[{"why":"Supplies the one-bit quantile-inversion estimator and the adaptive lower-bound method that this paper extends to unknown variance.","marker":"(Kipnis & Duchi, 2022)"},{"why":"Provides the Gaussian adaptive-versus-non-adaptive gap and the layer-cake Hellinger decomposition used in Theorem B.1.","marker":"(Cai & Wei, 2022a)"},{"why":"Gives the Gaussian benchmark with known variance and shows non-adaptive protocols can be order-optimal there, framing the variance-unknown gap.","marker":"(Cai & Wei, 2024)"},{"why":"The two-point method that converts the Hellinger bound into the non-adaptive MSE lower bound.","marker":"(Le Cam, 1973)"},{"why":"Textbook statement of Le Cam's method and information bounds used in the converse proofs.","marker":"(Polyanskiy & Wu, 2024)"},{"why":"Cited theorem of Le Cam's method invoked directly in the proof of Theorem 3.2.","marker":"(Wu, 2020)"},{"why":"Supplies the total-variation to Bhattacharyya inequality used to pass from Hellinger distance to TV distance.","marker":"(Tsybakov, 2009)"},{"why":"The Bayesian Cramér–Rao (Van Trees) inequality underlying the adaptive lower bound.","marker":"(Van Trees, 2004)"},{"why":"Provides the form of the Van Trees inequality used in Theorem 4.3.","marker":"(Gill & Levit, 1995)"},{"why":"The Fisher-information chain rule that splits the adaptive transcript's information across users.","marker":"(Zamir, 1998)"}],"fun_headline_variants":["Unknown variance tilts one-bit mean estimation toward adaptivity","Two-round one-bit estimation beats one-shot when variance is unknown","Adaptive one-bit estimation beats one-shot under unknown variance","One-bit estimation: adaptivity pays off with unknown variance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The strict-suboptimality comparison stands on the non-adaptive lower bound's regularity conditions—$f_X=e^{-\\varphi(x)}$ with $\\varphi$ symmetric, differentiable, strictly convex, and polynomially bounded—so for merely log-concave or heavier-tailed distributions (the Laplace is explicitly excluded) the paper proves no gap.","fun_headline_variants_meta":{"raw":{"variants":["Unknown variance tilts one-bit mean estimation toward adaptivity","Two-round one-bit estimation beats one-shot when variance is unknown","Adaptive one-bit estimation beats one-shot under unknown variance","One-bit estimation: adaptivity pays off with unknown variance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000252,"raw_usage":{"total_tokens":1611,"prompt_tokens":1044,"completion_tokens":567,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":499}},"tokens_in":660,"tokens_out":567,"duration_ms":5976,"temperature":1.0,"reasoning_tokens":499,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T23:18:06.083290+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate $T(f_X)$ for the standard normal: if $0.1034/T(f_X)\\le 1/(4f_X(0)^2)$, the lower bound does not certify a gap for the Gaussian, matching the paper's Figure 10. A decisive test would be to exhibit, for one distribution in the stated class, a non-adaptive threshold protocol whose large-$n$ MSE is below $0.1034\\,\\sigma^2/T(f_X)$, which would falsify Theorem 3.2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the one-bit quantile-inversion estimator and the adaptive lower-bound method that this paper extends to unknown variance."},{"cited_title":"Convergence of estimates under dimensionality restrictions","cited_arxiv_id":null,"evidence_quote":"The two-point method that converts the Hellinger bound into the non-adaptive MSE lower bound."},{"cited_title":"Information Theory: From Coding to Learning","cited_arxiv_id":null,"evidence_quote":"Textbook statement of Le Cam's method and information bounds used in the converse proofs."},{"cited_title":"A proof of the fisher information inequality via a data processing argument","cited_arxiv_id":null,"evidence_quote":"The Fisher-information chain rule that splits the adaptive transcript's information across users."}],"review_version":1}