cs.LGNov 4, 2026

Dimension-Free Private Mean Estimation is Impossible Without the Covariance

Authors: Renaud Gaucher, Ephraim Linder, Adam Smith, Jonathan Ullman, Lydia Zakynthinou

Organizations: Center of Applied Mathematics, École polytechnique. · Department of Computer Science, Boston University. · Khoury College of Computer Sciences, Northeastern University. · Department of Computer Science, Johns Hopkins University.

Abstract

We study the limits of differentially private Gaussian mean estimation when the covariance matrix is unknown. Prior work shows that when the covariance ΣΣ is known, the optimal sample complexity can depend only on its spectrum, rather than on the ambient dimension dd. We establish new lower bounds for Gaussian mean estimation with Euclidean error which show that private estimators cannot achieve similar guarantees when the covariance is unknown. First, when the sample size nn is smaller than the effective dimension trace(Σ)/∥Σ∥op\mathrm{trace}(Σ)/\|Σ\|_{\text{op}}, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of d/n\sqrt{d/n}. Second, when the sample size is larger than the effective dimension, even for diagonal covariance matrices with effective dimension bounded by log⁡d\log d, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of d/n3/2\sqrt{d}/n^{3/2}. Together, these results show that in the unknown covariance setting, exploiting anisotropic structure under differential privacy can require a dimension-dependent error or sample complexity.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Sep 19, 2026

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

We study differentially private covariance estimation in operator norm for mean-zero sub-Gaussian distributions with unknown covariance support and at most kk nonzero entries per row. We develop a multiscale random-threshold algorithm with sample complexity \ot(k2/α2+kd/(αε))\ot(k^2/α^2+k\sqrt d/(α\varepsilon)) for (ε,δ)(\varepsilon,δ)-differential privacy and error at most ασ2ασ^2, where dd is the dimension and σσ is a known sub-Gaussian scale. The bound improves the privacy-dependent term of the existing \ot(k2/α2+k3/2d/(αε))\ot(k^2/α^2+k^{3/2}\sqrt d/(α\varepsilon)) \citep{kumar2026curse} upper bound by a factor of k\sqrt k, and matches the lower bound of Ω~(k2/α2+kd/(αε))\widetildeΩ(k^2/α^2 + k\sqrt{d}/(α\varepsilon)) in its applicable parameter regime. Our key technical ingredient is a direct operator-norm bound on the centered fluctuations of an ideal reconstruction, exploiting conditional independence rather than accumulating entrywise errors across each row. A multiscale allocation of threshold tests balances reconstruction variance against query sensitivity. Together, these ingredients sharpen the trade-off between approximation error and privacy protection, removing the additional k\sqrt{k} factor from the privacy-dependent sample complexity.
Mar 20, 2026

Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy

Estimating covariance matrices is fundamental to a wide range of statistical applications. This paper studies minimax and adaptive estimation of high-dimensional covariance matrices under ρρ-zero-concentrated differential privacy (ρρ-zCDP) over three nested classes: the pointwise-decay class Hα\mathcal{H}_α, the row-tail class Gα\mathcal{G}_α, and the separated-block class Fα\mathcal{F}_α. We consider both squared operator norm loss and normalized squared Frobenius norm loss. For Hα\mathcal{H}_α and Gα\mathcal{G}_α, we develop center--outer dyadic estimators tailored to the refined geometry of the two classes, while for Fα\mathcal{F}_α, we develop a blockwise tridiagonal estimator. The resulting minimax-optimal rates reveal a nontrivial interplay among the smoothness αα, the loss, the geometry of the covariance class, and the privacy constraint. In contrast to the non-private setting, privacy distinguishes covariance classes that share the same leading non-private rate and induces a polynomial dependence on the ambient dimension. We further develop procedures that adapt to the unknown decay parameter over all three covariance classes under both losses, at the cost of at most polylogarithmic factors. To establish minimax lower bounds, we develop a novel differentially private van Trees inequality that connects Fisher information with the ρρ-zCDP constraint and may be useful for other private estimation problems. We also construct carefully designed prior distributions to obtain matching minimax lower bounds.
May 22, 2026

Private Adaptive Covariance Estimation via Gaussian Graphical Models

We propose PACE-GGM, a data-adaptive differentially private method for covariance estimation that concentrates its privacy budget on the most informative entries of the empirical covariance matrix, rather than perturbing all entries. This applies in the natural setting where the modeler supplies separate bounds for each variable, so that individual entries can be measured with less noise than the full matrix. In each round, our method selects a poorly approximated entry, measures it using the Gaussian mechanism, and then reconstructs a full covariance matrix using a maximum-entropy reconstruction objective, leading to a Gaussian graphical model structure. Experiments on diverse real-world datasets demonstrate consistent improvements in estimation error with respect to the Gaussian mechanism and other baselines, particularly in high-dimensional and low-to-moderate privacy regimes.