{"id":"8b3ccbe1-f9fb-4574-b4c5-cbcdc2bb5148","arxiv_id":"2509.04919","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Using Bernstein bases, the Bezier mechanism estimates variance and covariance under add-remove differential privacy with optimal mean squared error 2/(epsilon^2 n^2) in the high-privacy regime.","lead":"Variance and covariance can be released privately, even when the size of the dataset is itself a secret, using a new mechanism built from Bernstein polynomials. The paper proves this mechanism is optimal at high privacy and beats natural alternatives on every dataset it tested.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's printed lower-bound constant is inconsistent with its own asymptotic claim and with the Algorithm 2 upper bound, so the minimax matching claim is not supported as stated.","rationale":"The reader's CONDITIONAL verdict is appropriate, but the most load-bearing problem I see is not the swap-model branch identified as the weakest assumption. It is the lower-bound formula in Theorem 3.1 itself, which is internally inconsistent: on any natural reading of the printed fraction, the stated constant does not have the claimed 2/epsilon^2 asymptotic and already exceeds the paper's own Algorithm 2 upper bound at epsilon = 0.1. The upper-bound proofs in Appendix D.6 and D.7 are extensive and algebraically plausible, and the Bezier mechanism idea is a genuine contribution. However, minimax optimality requires a lower bound with the same leading constant, and the printed lower bound does not supply it. I also note a second, more mechanical issue: Algorithm 2 line 6 sets ~s_y = ~b_{0,1} + ~b_{0,0}, which is inconsistent with Section 5.3 and with the proof in D.6, where the correct reconstruction is ~s_y = ~b_{0,1} + ~b_{1,1}. As printed, Algorithm 2 would not estimate covariance. I did not make this the load-bearing concern because it is likely a typographical error and the surrounding text plus proof indicate the intended algorithm, whereas the Theorem 3.1 constant problem directly affects the central optimality claim. Overall, the manuscript's main claim is not established as written, and the CONDITIONAL verdict should stand pending correction of the lower-bound theorem and the algorithm pseudocode.","tokens_in":22280,"tokens_out":31632,"duration_ms":259986,"concrete_test":"Evaluate the formula printed in Theorem 3.1 symbolically at epsilon = 0.1 and take the epsilon -> 0 limit. If the value exceeds 2/epsilon^2 or the limit coefficient differs from 2, the lower bound cannot coexist with Theorem 5.8; then the closed form in Theorem 3.1 must be corrected and the proof re-verified before the matching claim is accepted. As a secondary check, independently re-derive sigma(epsilon) from the cited Geng-Viswanath/Kulesza sum-estimation bound to confirm the intended constant is 2/epsilon^2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Algorithms 2 and 3 achieve R <= 2/epsilon^2 (1+o(1)) and match the lower bound in Theorem 3.1. The load-bearing element is therefore the constant in Theorem 3.1. As printed, the closed form for sigma(epsilon) cannot be reconciled with the rest of the paper. At epsilon = 0.1, the displayed fraction evaluates to roughly 215, whereas Theorem 5.8 promises R <= 200 (1+o(1)) for Algorithm 2. If the fraction is read as sigma(epsilon) rather than sigma(epsilon)^2, the contradiction is even worse because sigma(epsilon)^2 becomes about 4.6 x 10^4. Independently, the stated asymptotic 'sigma(epsilon)^2 ~ 2/epsilon^2' does not follow from the printed expression: expanding the fraction as epsilon -> 0 gives a coefficient near 1.94 if the fraction is sigma(epsilon)^2, or an even larger divergence if it is sigma(epsilon). Thus, on any natural reading, the printed lower bound contradicts the paper's own upper bound and does not support the claimed matching constant. This is an internal inconsistency in the central theorem, not a disagreement with an external prior. A corrected closed form or a re-derivation of the Geng-Viswanath/Kulesza bound is needed before the minimax optimality claim can be relied on.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies ε-differentially-private estimation of the centered variance and covariance of a dataset in the add-remove model, where the dataset size is also sensitive. The main claim is that, in the high-privacy regime, the normalized worst-case mean squared error R(·,·,n0) can be made 2/ε^2(1+o(1)), matching (i) the corresponding error for mean estimation in the add-remove model and (ii) swap-model variance/covariance estimation. The authors introduce the Bézier mechanism, which adds Laplace noise to the Bernstein-basis representation of the empirical moment vector, prove upper bounds for covariance (Algorithm 2) and variance (Algorithm 3), state a matching lower bound in Theorem 3.1, give two additional optimal variance mechanisms, compare their instance-dependent leading constants, and extend the framework to general moment-based statistics such as higher moments and correlation.","tokens_in":22548,"tokens_out":12714,"duration_ms":106953,"significance":"The question addressed is well motivated: the add-remove model protects dataset size, and prior covariance work has concentrated on the swap model or on uncentered covariance. If the claims are correct, the paper would establish a clean constant-factor equivalence between add-remove and swap models for variance and covariance estimation in the high-privacy regime. The Bernstein-basis sensitivity argument (Lemma 5.5) is elegant, and the delta-method decomposition of Lemma A.4 together with the exact variance computations in Appendices D.6–D.9 are genuine technical contributions. The paper does not provide code or machine-checked proofs; the contribution is analytic. However, the printed lower bound in Theorem 3.1 is internally inconsistent with the paper's own upper bounds, and the pseudocode in Algorithm 2 does not compute the claimed statistic. These issues are load-bearing for the central matching claim and must be corrected before the results can be relied upon.","major_comments":[{"comment":"The printed closed form for σ(ε) is inconsistent with the stated asymptotic and with the upper bounds in Theorems 5.8 and 5.9. On the natural reading in which the displayed fraction is σ(ε), at ε=0.1 it evaluates to approximately 2.05×10^2, so σ(ε)^2 is about 4.2×10^4, while Theorem 5.8 promises R ≤ 2/ε^2(1+o(1)) ≈ 2×10^2. On the alternative reading in which the fraction is σ(ε)^2, its small-ε limit is approximately 1.94/ε^2 rather than 2/ε^2, which still does not match the claimed asymptotic. Either way, Theorem 3.1 does not currently support the minimax matching constant. Please correct the formula, or re-derive the Geng–Viswanath/Kulesza lower bound, and verify the claimed σ(ε)^2 ≃ 2/ε^2.","section":"Theorem 3.1"},{"comment":"The lower-bound proof reduces variance estimation to sum estimation and invokes Lemma 5.1 of Kulesza et al. (2024), which is a mean/sum-estimation lower bound developed for the add-remove model. However, Theorem 3.1 is stated for both the swap and the add-remove models. The reduction itself is valid under either neighboring relation because the appended-zero construction preserves the relevant adjacency structure, but the sum-estimation lower bound must also hold under the swap model with the same constant. As written, the swap-model branch of the minimax optimality claim is unproved. Please either cite a swap-model sum lower bound with the required constant or restrict the statement of Theorem 3.1.","section":"Appendix B.1 (proof of Theorem 3.1)"},{"comment":"Line 6 of Algorithm 2 computes ˜sy = ˜b_{0,1} + ˜b_{0,0}, which estimates Σ(1−x_i) = n − Σ x_i, not Σ y_i. The correct expression, which is used in the surrounding text and in the proof of Theorem 5.8, is ˜sy = ˜b_{0,1} + ˜b_{1,1}. As printed, the algorithm does not output the quantity whose utility is analyzed, so the pseudocode needs to be corrected. This is a load-bearing error because Algorithm 2 is one of the two central mechanisms.","section":"Section 5.3, Algorithm 2"},{"comment":"The variance formula in Theorem 5.6 is inconsistent with the derivation in Appendix D.4. Appendix D.4 gives E[(µ̂_j − µ_j)^2] = (2/ε^2) Σ_{l=j}^k ((l choose j)/(k choose j))^2, whereas the theorem prints (2/ε^2)·(k choose j)·Σ_{l=j}^k (l choose j)^2, omitting the square of the binomial denominator. The printed formula is already wrong at j=0, where it gives 2(k+1)/ε^2 but the claimed bound is ≤ 2k/ε^2; for j=1 it is Θ(k^4)/ε^2 rather than the true Θ(k)/ε^2. The top-moment case j=k is correct, so the variance and covariance upper bounds are not affected, but the general moment-release guarantee advertised in Section 5.1 and used for the extensions in Section 6 is not supported as stated. Please restate and re-prove the theorem with the correct expression.","section":"Section 5.1, Theorem 5.6"}],"minor_comments":[{"comment":"The sentence defining the noisy variance says \"˜u = ˜b2\", but Algorithm 4 only defines b0 and b1; the intended expression is ˜u = ˜b1, matching line 4 of the pseudocode.","section":"Section 5.5, text before Algorithm 4"},{"comment":"The displayed bounds read \"Prob(Z∈A_n) ≤ 1 − 4 exp(...)\", but the union-bound argument gives Prob(Z∈A_n) ≥ 1 − 4 exp(...). The direction of the inequality is reversed in all three lemmas.","section":"Lemmas D.5, D.7, D.9"},{"comment":"The displayed formula for ˜b_{0,1} contains a duplicated factor: it reads \"(1−x_i)y_i(1−x_i)\" and should read \"(1−x_i)y_i\".","section":"Section 5.3, Algorithm 2 preamble"},{"comment":"The proof of Theorem 5.8 defines Z_n, Z_x, Z_y, Z_xy in terms of Z_1,...,Z_4 but does not state which Z_i corresponds to which Bernstein coefficient. Please include the mapping explicitly, since the ordering matters for checking the identities Z_x = Z_1+Z_3 and Z_y = Z_2+Z_3.","section":"Appendix D.6"},{"comment":"The o(1) terms in the lower bound are not quantified; please state whether they are as n0→∞, as ε→0, or both, since the reduction sets k=Ω(|D|^4) and n0=k.","section":"Appendix B.1 and Theorem 3.1"},{"comment":"The text refers to \"Fig. 7\" in three places, but the paper contains only two figures; the cross-references need to be fixed.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound proofs in Appendices D.6–D.9 appear coherent, and the Bernstein representation idea is promising, so I recommend major revision rather than rejection. The main blocking issue is the mis-transcribed lower-bound formula in Theorem 3.1; the Algorithm 2 pseudocode error and the swap-model citation gap are also necessary to fix. I did not find evidence of circularity or fitted constants; the issues are internal consistency problems rather than a flawed overall strategy."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe Bézier mechanism is the real thing: a clean way to release a block of moments with l1-sensitivity 1 in the add-remove model, and the noise-correlation algebra that gives variance and covariance estimators with 2/ε² error is clever. Appendices D.6–D.9 are coherent enough that a referee can check them line by line, and the instance-wise dominance of Algorithm 3 over its two alternatives is a nice bonus. The citation pattern is honest, with prior work appropriately credited.\n\nThe problem is that the stated minimax matching is not supported as printed. Theorem 3.1 displays a σ(ε) that behaves like 2/ε², so σ(ε)² behaves like 4/ε⁴—not 2/ε² as claimed. If the displayed fraction is instead meant to be σ(ε)², then the stated asymptotic and the upper bounds in Theorems 5.8 and 5.9 can be reconciled, but the theorem's notation is still wrong on its face. Either way, the printed lower bound contradicts the paper's own upper bound at small ε. That is an internal inconsistency in the load-bearing result, not a presentation quibble. The proof in Appendix B.1 also imports an add-remove sum-estimation lower bound from Kulesza et al. but never justifies the swap-model branch of the theorem; the swap claim should either be proved or dropped.\n\nThere are smaller issues worth a careful pass: Theorem 5.6's formula needs checking, and the claim that all moments up to order k are released 'at no additional privacy cost' is only shown cleanly for the top moment. These are secondary.\n\nRecommendation: don't let the current version through as-is, but don't lose the paper. The mechanism and the upper-bound analysis are worth a serious referee. If the σ(ε) expression is corrected (likely a typo—the fraction should be σ² or σ should be its square root), the swap lower bound is fixed or removed, and the moment-release statement is cleaned up, the add-remove minimax result can be made solid. I would want to see the revision before citing the 2/ε² constant.","headline":"The Bézier mechanism is a genuinely new and useful construction, but the printed lower bound contradicts its own asymptotics and the paper's upper bound, so the minimax claim needs a correction before it can be relied on.","tokens_in":23065,"tokens_out":6546,"would_cite":false,"duration_ms":57287,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","62G05","62F10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that variance and covariance estimation under the add-remove model of differential privacy can achieve the same optimal error rate as mean estimation, via a new Bernstein-basis mechanism.","keywords":["differential privacy","add-remove model","variance estimation","covariance estimation","Bézier mechanism","Bernstein basis","minimax optimality","moment estimation"],"falsifier":"Construct an $\\varepsilon$-DP estimator for the sum of the entries of a bounded dataset under swap neighboring whose normalized MSE is strictly below $\\sigma(\\varepsilon)^2(1-o(1))$ for $\\varepsilon\\to0$; because the lower-bound proof for variance and covariance reduces through sum estimation, such an estimator would directly refute Theorem 3.1's swap-model branch. Alternatively, a finite-$n$ exhaustive computation of the minimax risk for small $n$ that falls below $2/\\varepsilon^2$ for large $n$ would falsify the claimed optimal constant.","tokens_in":22081,"feed_emoji":"🔒","tokens_out":19392,"duration_ms":148767,"temperature":0.7,"pith_summary":"This paper asks whether estimating variance and covariance under the add-remove model of differential privacy — the model that also hides the size of the dataset — is harder than under the swap model or than estimating the mean. It answers no in the high-privacy regime: a new mechanism that adds Laplace noise to the dataset's Bernstein-basis coefficients estimates variance and covariance with normalized mean squared error $2/\\varepsilon^2(1+o(1))$, matching the paper's new lower bound and the known optimal mean-estimation rate. The same mechanism releases all moments up to a given order at no extra privacy cost, which the paper shows carries over to other moment-based statistics such as correlation, skewness, and kurtosis.","feed_headline":"Add-remove privacy does not hurt variance and covariance estimation","feed_subtitle":"Despite hiding dataset size, the Bézier mechanism reaches the same optimal error as mean estimation.","key_machinery":"The central object is the Bézier mechanism, a moment-release framework that represents unnormalized moments of a dataset by their coefficients in the Bernstein basis, where the $\\ell^1$ sensitivity is exactly 1 because the basis functions are nonnegative and sum to 1; add Laplace noise of scale $1/\\varepsilon$ to those coefficients, then invert the Bézier matrix to recover noisy moments. This representation is what lets all moments up to order $k$ be released for the price of one, and its correlated noise structure is what makes the covariance and variance ratios achieve the optimal constant.","core_discovery":"The paper's central claim is that minimax optimal variance and covariance estimation in the add-remove model is achievable at normalized mean squared error $2/\\varepsilon^2(1+o(1))$ for $\\varepsilon\\to0$, the same leading constant as mean estimation and as the swap model. The lower-bound side is a reduction from sum estimation (Theorem 3.1); the upper-bound side is the Bézier mechanism (Algorithms 2 and 3), whose noisy Bernstein coefficients recombine so that leading noise contributions cancel in the final ratio estimator. The paper further proves that among three optimal variance estimators, the Bézier-based one has the smallest instance-dependent leading constant for every dataset mean and variance.","pith_inferences":["The sensitivity-1 Bernstein representation suggests a general recipe: any nonnegative basis that sums to a constant gives a moment-release mechanism, so other polynomial or knot-based bases could yield different noise correlations — an extension the paper does not explore.","The instance-wise comparison is carried out only for variance; an analogous decomposition of the covariance estimator's leading constant would likely reveal which of the competing covariance mechanisms is best per dataset, but the paper leaves that open.","If the unproven swap-model lower bound is later established, the equivalence between swap and add-remove privacy for second-order statistics becomes a theorem; if it fails, the add-remove model may be strictly harder than swap for these statistics, and the present upper bound would be the whole story.","Because the Bézier mechanism's error formula for lower-order moments has an explicit dependence on the degree $k$, the same machinery could be used to tune the degree when estimating statistics that mix moments of different orders (e.g., ratio statistics), a testable extension of the framework."],"forward_implications":["In the high-privacy regime, private variance and covariance estimation in the add-remove model has the same normalized error constant $2/\\varepsilon^2$ as mean estimation, so these second-order statistics are asymptotically no harder than the mean.","Because the Bézier mechanism releases moments up to order $k$ at the privacy cost of a single moment, any statistic depending on those moments — correlation, skewness, kurtosis — inherits the same optimal-rate guarantee.","For variance estimation, the Bézier-based estimator (Algorithm 3) achieves a smaller instance-dependent leading constant than the two other optimal mechanisms for every possible dataset mean and variance, so it dominates them beyond the worst case.","The naive Laplace-moment baseline and the improved unnormalized-variance baseline in the add-remove model are suboptimal by constant factors ($128/\\varepsilon^2$ and $17/(2\\varepsilon^2)$ for covariance), which the new mechanism closes to $2/\\varepsilon^2$."],"supporting_citations":[{"why":"Supplies the add-remove mean-estimation lower bound that Theorem 3.1 reduces variance/covariance estimation to, and the transformed-noise estimator that the Bézier mechanism generalizes.","marker":"Kulesza et al. (2024)"},{"why":"Cited as the source of the sum-estimation lower bound that underlies the variance/covariance lower-bound reduction.","marker":"Geng and Viswanath (2014)"},{"why":"Provides the inverse Bézier matrix coefficients used to compute the moment-estimation error in Theorem 5.6.","marker":"Simsek (2013)"}],"fun_headline_variants":["Bézier mechanism hits minimax bound for add-remove variance","Add-remove privacy: Bézier matches mean estimation error","Variance under add-remove privacy: Bézier is optimal","Beyond worst-case: Bézier wins for variance privacy","Hiding dataset size? Bézier still optimal for variance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The swap-model half of the claimed lower bound rests on a sum-estimation lower bound that was proved for the add-remove model, and the paper does not show the same bound holds for swap-DP estimators, so the claim that add-remove variance and covariance are no harder than swap-model estimation is not fully established.","fun_headline_variants_meta":{"raw":{"variants":["Bézier mechanism hits minimax bound for add-remove variance","Add-remove privacy: Bézier matches mean estimation error","Variance under add-remove privacy: Bézier is optimal","Beyond worst-case: Bézier wins for variance privacy","Hiding dataset size? Bézier still optimal for variance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000154,"raw_usage":{"total_tokens":1159,"prompt_tokens":842,"completion_tokens":317,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":458,"completion_tokens_details":{"reasoning_tokens":234}},"tokens_in":458,"tokens_out":317,"duration_ms":3602,"temperature":1.0,"reasoning_tokens":234,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:25:39.903729+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct an $\\varepsilon$-DP estimator for the sum of the entries of a bounded dataset under swap neighboring whose normalized MSE is strictly below $\\sigma(\\varepsilon)^2(1-o(1))$ for $\\varepsilon\\to0$; because the lower-bound proof for variance and covariance reduces through sum estimation, such an estimator would directly refute Theorem 3.1's swap-model branch. Alternatively, a finite-$n$ exhaustive computation of the minimax risk for small $n$ that falls below $2/\\varepsilon^2$ for large $n$ would falsify the claimed optimal constant.","supporting_citations":[{"cited_title":"T., and Wang, Y","cited_arxiv_id":null,"evidence_quote":"Supplies the add-remove mean-estimation lower bound that Theorem 3.1 reduces variance/covariance estimation to, and the transformed-noise estimator that the Bézier mechanism generalizes."},{"cited_title":"and Viswanath, P","cited_arxiv_id":null,"evidence_quote":"Cited as the source of the sum-estimation lower bound that underlies the variance/covariance lower-bound reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the inverse Bézier matrix coefficients used to compute the moment-estimation error in Theorem 5.6."}],"review_version":2}