Pith. sign in

REVIEW 4 major objections 6 minor 25 references

Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond

T0 review · 4 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2509.04919 v1 pith:FMWVUHNV submitted 2025-09-05 stat.ML cs.DScs.LG

Shokichi Takakura , Seng Pei Liew , Satoshi Hasegawa This is my paper · ORCID
classification stat.MLcs.DScs.LG MSC 68P2762G0562F10
keywords differentialprivacyadd-removemodelvarianceestimationcovarianceBéziermechanismBernsteinbasisminimaxoptimalitymoment
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

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.

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 (4)
  1. [Theorem 3.1] 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.
  2. [Appendix B.1 (proof of Theorem 3.1)] 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.
  3. [Section 5.3, Algorithm 2] 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.
  4. [Section 5.1, Theorem 5.6] 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.
minor comments (6)
  1. [Section 5.5, text before Algorithm 4] 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.
  2. [Lemmas D.5, D.7, D.9] 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.
  3. [Section 5.3, Algorithm 2 preamble] 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".
  4. [Appendix D.6] 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.
  5. [Appendix B.1 and Theorem 3.1] 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.
  6. [Section 7] The text refers to "Fig. 7" in three places, but the paper contains only two figures; the cross-references need to be fixed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bounds are direct Laplace-sensitivity calculations and the lower bounds are imported from external prior work; the noted swap-model and σ(ε)-notation issues are correctness gaps, not input-output equivalences.

full rationale

The central claim (Algorithms 2 and 3 achieve R≤2/ε²(1+o(1)) and match Theorem 3.1) is not forced by the paper's own definitions or fitted values. Algorithm 2/3 utility is proved in Appendices D.6/D.7 by writing the estimator as clip(f(Z/n),...), applying the generic Taylor lemma A.4, and bounding E[Δ(Z)²]≤2/ε² explicitly (Lemmas D.6, D.8). No parameter is fitted to the target; the constant 2/ε² is the variance of the Laplace noise. The lower bound in Theorem 3.1 is a reduction to sum/mean estimation, citing external results (Kulesza et al. 2024; Geng and Viswanath 2014), not the authors' own mechanisms. The Bézier mechanism is presented as a special case of the matrix mechanism and a generalization of Kulesza et al.'s transformed noise addition, which is an honest relationship disclosure, not a renamed result. Two correctness flags, not circularity: (1) Appendix B.1's proof of the swap-model branch invokes Lemma 5.1 of Kulesza et al., a lower bound stated for the add-remove mean-estimation problem; the paper does not show this lower bound transfers to swap-DP estimators, so the swap-model half of Theorem 3.1 is unsupported as written. (2) The displayed σ(ε) formula in Theorem 3.1 appears to denote σ(ε)² (its asymptotics are 2/ε² while the theorem multiplies by an extra square), creating an internal notational inconsistency with the claimed matching upper bound. There is also a citation mismatch: Section 3 attributes the sum-estimation lower bound to Geng and Viswanath (2014), while Appendix B.1 invokes Lemma 5.1 of Kulesza et al. (2024). Neither issue is an equation that reduces to its own input; they are omitted justifications or typos and should be weighed as correctness risk rather than circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard DP background, the add-remove sensitivity of Bernstein coefficients, and a lower-bound lemma imported from Kulesza et al. No parameters are fitted to data; the privacy degree k and clipping bounds are design choices. No new entities are postulated.

assumptions (4)
  • domain assumption Records lie in [0,1]^d after clipping and linear rescaling.
    Section 2 states this WLOG assumption and uses it for the variance and covariance range [-1/4, 1/4] and for sensitivity bounds.
  • domain assumption The lower bound for sum estimation in Lemma 5.1 of Kulesza et al. (2024) holds with constant sigma(epsilon)^2.
    Theorem 3.1 proof in Appendix B.1 takes this as a black box; the paper does not re-derive it.
  • standard math Bernstein basis partition of unity and the inverse Bezier matrix formula.
    Used in Lemma 5.5, Lemma 5.7, and Theorem 5.6; standard polynomial algebra.
  • domain assumption Lemma A.4 Taylor approximation conditions hold for the noise vectors and data distributions.
    All utility upper bounds rely on this asymptotic linearization; the paper verifies the conditions for Laplace noise but it is still an additional structural assumption on the estimator's smoothness and clipping.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond." pith.science (2026). https://pith.science/paper/FMWVUHNV

@misc{pith2026250904919,
  author       = {Pith},
  title        = {Pith review of: Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FMWVUHNV}},
  note         = {Machine review of arXiv:2509.04919}
}
read the original abstract

In this paper, we study the problem of estimating the variance and covariance of datasets under differential privacy in the add-remove model. While estimation in the swap model has been extensively studied in the literature, the add-remove model remains less explored and more challenging, as the dataset size must also be kept private. To address this issue, we develop efficient mechanisms for variance and covariance estimation based on the \emph{B\'{e}zier mechanism}, a novel moment-release framework that leverages Bernstein bases. We prove that our proposed mechanisms are minimax optimal in the high-privacy regime by establishing new minimax lower bounds. Moreover, beyond worst-case scenarios, we analyze instance-wise utility and show that the B\'{e}zier-based estimator consistently achieves better utility compared to alternative mechanisms. Finally, we demonstrate the effectiveness of the B\'{e}zier mechanism beyond variance and covariance estimation, showcasing its applicability to other statistical tasks.

Figures

Figures reproduced from arXiv: 2509.04919 by the authors.

Figure 1
Figure 1. Comparison of covariance and variance es [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Comparison of optimal mechanisms for vari [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 20 canonical work pages

  1. [1]

    Aitsam, M. (2022). Differential Privacy Made Easy . In 2022 International Conference on Emerging Trends in Electrical, Control, and Telecommunication Engineering (ETECTE) , pages 1--7. IEEE

    work page 2022

  2. [2]

    and Rubinstein, B

    Aldà, F. and Rubinstein, B. (2017). The Bernstein Mechanism: Function Release under Differential Privacy . Proceedings of the AAAI Conference on Artificial Intelligence , 31(1)

    work page 2017

  3. [3]

    Amin, K., Dick, T., Kulesza, A., Munoz, A., and Vassilvitskii, S. (2019a). Differentially Private Covariance Estimation . In Wallach, H., Larochelle, H., Beygelzimer, A., d Alch\' e -Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems , volume 32. Curran Associates, Inc

    work page 2019

  4. [4]

    Amin, K., Gillenwater, J., Joseph, M., Kulesza, A., and Vassilvitskii, S. (2022). Plume: Differential privacy at scale . arXiv preprint arXiv:2201.11603

    arXiv 2022

  5. [5]

    Amin, K., Kulesza, A., Munoz, A., and Vassilvtiskii, S. (2019b). Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy . In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pages 263--271. PMLR

    work page 2019

  6. [6]

    Biswas, S., Dong, Y., Kamath, G., and Ullman, J. (2020). Coinpress: Practical private mean and covariance estimation . Advances in Neural Information Processing Systems , 33:14475--14485

    work page 2020

  7. [7]

    Dalenius, T. (1977). Towards a methodology for statistical disclosure control . statistik Tidskrift , 15(429-444):2--1

    work page 1977

  8. [8]

    Dong, W., Liang, Y., and Yi, K. (2022). Differentially private covariance revisited . Advances in Neural Information Processing Systems , 35:850--861

    work page 2022

Show all 25 references
  1. [9]

    Dwork, C., Roth, A., et al. (2014). The algorithmic foundations of differential privacy . Foundations and Trends in Theoretical Computer Science , 9(3--4):211--407

    2014

  2. [10]

    and Viswanath, P

    Geng, Q. and Viswanath, P. (2014). The optimal mechanism in differential privacy . In 2014 IEEE international symposium on information theory , pages 2371--2375. IEEE

    2014

  3. [11]

    Gillenwater, J., Joseph, M., and Kulesza, A. (2021). Differentially private quantiles . In International Conference on Machine Learning , pages 3713--3722. PMLR

    2021

  4. [12]

    R., and Pagh, R

    Imola, J., Boninsegna, F., Keller, H., Aamand, A., Chowdhury, A. R., and Pagh, R. (2025). Differentially private quantiles with smaller error. arXiv preprint arXiv:2505.13662

    2025

  5. [13]

    P., Upadhyay, J., and Lampert, C

    Kalinin, N. P., Upadhyay, J., and Lampert, C. H. (2025). Continual release moment estimation with differential privacy. arXiv preprint arXiv:2502.06597

    2025 arXiv

  6. [14]

    and Vadhan, S

    Karwa, V. and Vadhan, S. (2018). Finite Sample Differentially Private Confidence Intervals . In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , pages 44--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik

    2018

  7. [15]

    T., and Wang, Y

    Kulesza, A., Suresh, A. T., and Wang, Y. (2024). Mean Estimation in the Add-Remove Model of Differential Privacy . In Forty-first International Conference on Machine Learning

    2024

  8. [16]

    T., and Wang, Y

    Kulesza, A., Suresh, A. T., and Wang, Y. (2025). General Staircase Mechanisms for Optimal Differential Privacy . In Li, Y., Mandt, S., Agrawal, S., and Khan, E., editors, Proceedings of The 28th International Conference on Artificial Intelligence and Statistics , volume 258 of...

    2025

  9. [17]

    Li, C., Miklau, G., Hay, M., McGregor, A., and Rastogi, V. (2015). The matrix mechanism: optimizing linear counting queries under differential privacy . The VLDB journal , 24(6):757--781

    2015

  10. [18]

    Lorentz, G. G. (2012). Bernstein polynomials . American Mathematical Soc

    2012

  11. [19]

    McSherry, F. D. (2009). Privacy integrated queries: an extensible platform for privacy-preserving data analysis . In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data , pages 19--30

    2009

  12. [20]

    Portella, V. S. and Harvey, N. (2024). Lower bounds for private estimation of Gaussian covariance matrices under all reasonable parameter regimes . arXiv preprint arXiv:2404.17714

    2024 arXiv

  13. [21]

    A., Tandon, A., and Sharma, A

    Rameshwar, V. A., Tandon, A., and Sharma, A. (2025). Optimal Tree-Based Mechanisms for Differentially Private Approximate CDFs . In 2025 17th International Conference on COMmunication Systems and NETworks (COMSNETS) , pages 1269--1274

    2025

  14. [22]

    K., Sahay, S., and Ahammad, P

    Rogers, R., Subramaniam, S., Peng, S., Durfee, D., Lee, S., Kancha, S. K., Sahay, S., and Ahammad, P. (2021). Linkedin's audience engagements API: A privacy preserving data analytics system at scale . Journal of Privacy and Confidentiality , 11:3

    2021

  15. [23]

    Simsek, Y. (2013). Functional equations from generating functions: a novel approach to deriving identities for the Bernstein basis functions . Fixed Point Theory and Applications , 2013(1):80

    2013

  16. [24]

    Swanberg, M., Globus-Harris, I., Griffith, I., Ritz, A., Groce, A., and Bray, A. (2019). Improved Differentially Private Analysis of Variance . Proceedings on Privacy Enhancing Technologies

    2019

  17. [25]

    J., Zhang, C

    Wilson, R. J., Zhang, C. Y., Lam, W., Desfontaines, D., Simmons-Marengo, D., and Gipson, B. (2020). Differentially Private SQL with Bounded User Contribution . Proceedings on Privacy Enhancing Technologies

    2020

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.