betaFeedback

WorksComputer Science

Dimension-Free Private Mean Estimation is Impossible Without the Covariance

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.

Introduction

Statistical inference and machine learning algorithms are designed to extract population-level insights from data, but in doing so, they routinely reveal information about the individuals whose data they process. The risks of privacy violations are well documented, ranging from reconstruction [17, 16, 19, 27], membership-inference [22, 36, 7, 18 SSSS17, YGFJ18] and the unintended memorization of training data [10, 8, 20, 3]. Differential privacy (DP) [15] provides a rigorous framework for mitigating these risks by limiting the effect of any individual’s data on the distribution of an algorithm’s output, and has become a standard approach to privacy protection in statistics and machine learning.

At the same time, ensuring privacy can come at a substantial cost in statistical accuracy, especially in high-dimensional settings. This has motivated an extensive literature characterizing the tradeoffs between privacy, sample size, and accuracy, across a range of high-dimensional statistical and machine learning tasks. A central question is whether private algorithms can exploit structure in the underlying distribution to reduce this cost.

Gaussian mean estimation. A natural setting in which to study these tradeoffs is Gaussian mean estimation. Given independent samples from a Gaussian distribution with unknown mean μ∈Rd\mu\in\mathbb{R}^{d} and covariance matrix Σ\Sigma, the goal is to estimate μ\mu accurately in Euclidean distance. Mean estimation is a fundamental statistical task in its own right and serves as a building block for more complex procedures, including regression and optimization. Its simplicity also makes it an ideal setting in which we can isolate the interplay between privacy, dimensionality, and covariance structure.

Summary of our contributions. In this work, we compare the optimal error achievable for private Gaussian mean estimation when the covariance is unknown to the optimal error when the covariance is known (i.e., given as input to the algorithm). In the known covariance setting, recent work [13] shows that the optimal Euclidean error scales as

O~(tr⁡(Σ)n+tr⁡(Σ1/2)log⁡(1/δ)εn),(1)\widetilde{\mathcal{O}}\left(\sqrt{\frac{\operatorname{tr}(\Sigma)}{n}}+\frac{\operatorname{tr}(\Sigma^{1/2})\sqrt{\log(1/\delta)}}{\varepsilon n}\right), \tag*{(1)}

where the first term is the statistical rate of Gaussian mean estimation, and the second term is the additional error due to privacy. Remarkably, the bound achieved by [13] is “dimension-free”—the error depends only on the geometry of the data, and is independent of the ambient dimension dd. Our main contributions show that this dimension-free behavior cannot be recovered in the unknown covariance setting. Our first contribution shows that for a sample of size nn, the optimal error in the unknown covariance setting can be larger by a factor of d/n\sqrt{d}/n than the optimal error in the known covariance setting. Our second contribution considers the setting when the covariance is promised to be diagonal: we show that even under this additional promise, the optimal error in the unknown covariance setting can be larger by a factor of d/n1.5\sqrt{d}/n^{1.5} than the optimal error in the known covariance setting. Table 1 summarizes our main contributions.

SettingError blowupObstruction
General covarianceerror⁡unknown=Θ~ε,δ(1+dn)⋅error⁡known\operatorname{error}_{\mathrm{unknown}} = \widetilde{\Theta}_{\varepsilon,\delta}\left(1+\sqrt{\frac{d}{n}}\right)\cdot\operatorname{error}_{\mathrm{known}}Subspace estimation
Diagonal covarianceerror⁡unknown=Θ~ε,δ(1+dn1.5)⋅error⁡known\operatorname{error}_{\mathrm{unknown}} = \widetilde{\Theta}_{\varepsilon,\delta}\left(1+\frac{\sqrt{d}}{n^{1.5}}\right)\cdot\operatorname{error}_{\mathrm{known}}Identifying large variance coordinates

Table 1. error⁡unknown\operatorname{error}_{\mathrm{unknown}} and error⁡known\operatorname{error}_{\mathrm{known}}, respectively, denote the Euclidean error in the unknown and known covariance settings. The known covariance bound, and the upper bound for unknown diagonal covariance are due to [13]. The upper bound for unknown general covariance is a folklore algorithm based on the framework from [TCKMS22] and presented in Section B. The lower bounds for error⁡unknown\operatorname{error}_{\mathrm{unknown}} in both settings are Theorems 2.1 and 3.2 of this work.

Our bounds highlight two fundamental challenges for mean estimation with unknown covariance. In the promised diagonal setting, we show that every private mean estimation algorithm must, in some sense, “identify” many of the coordinates with the largest variances. And, in the general covariance setting, we show that every private mean estimation algorithm must learn the subspace spanned by the covariance.

In addition to our lower bounds for mean estimation in Euclidean distance, we show that in the more challenging setting of estimation in Mahalanobis error—where the error of the estimator in each direction is required to be proportional to the variance in that direction—private mean estimation with unknown covariance is impossible whenever n≤d−2n \le d - 2. This is in stark contrast to the known covariance setting where the optimal Mahalanobis error is finite at essentially all sample sizes.

Our results

All of our lower bounds apply to the approximate DP setting defined below.

Definition 1.1 (Differential Privacy [15]). A randomized algorithm A:X∗→W\mathcal{A}:\mathcal{X}^* \to\mathcal{W} is (ε,δ)(\varepsilon,\delta)-differentially private, if, for all neighboring datasets X,X′X,X', i.e. datasets that differ on a single entry, and all measurable subsets W⊂WW \subset\mathcal{W} we have

Pr⁡[A(X)∈W]≤eεPr⁡[A(X′)∈W]+δ.\Pr[\mathcal{A}(X) \in W] \le e^\varepsilon\Pr[\mathcal{A}(X') \in W] + \delta.

In order to facilitate comparison between the error in the known and unknown covariance settings, and to present a scale-free “cost” of not knowing the covariance, we define the known and unknown covariance Bayes risk.

Definition 1.2 (Bayes risk). Let Aε,δ\mathcal{A}_{\varepsilon,\delta} denote the set of (ε,δ)(\varepsilon,\delta)-DP algorithms, and let P\mathcal{P} be a prior distribution over μ∈Rd\mu\in\mathbb{R}^d and positive semi-definite Σ∈Rd×d\Sigma\in\mathbb{R}^{d\times d}. The unknown-covariance Bayes risk with respect to the prior P\mathcal{P} is defined as:

Rε,δ(P,n)=inf⁡{α≥0:∃A∈Aε,δ s.t. Pr⁡(μ,Σ)∼PX∼N(μ,Σ)⊗n[∥A(X)−μ∥2≤α]≥34}.\mathfrak{R}_{\varepsilon,\delta}(\mathcal{P},n) = \inf\left\{\alpha\ge0 : \exists\mathcal{A} \in\mathcal{A}_{\varepsilon,\delta}\ \text{s.t.}\ \Pr_{\substack{(\mu,\Sigma)\sim\mathcal{P}\\ X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}}\left[\left\|\mathcal{A}(X)-\mu\right\|_2 \le\alpha\right] \ge\frac{3}{4}\right\}.

We also define the known-covariance Bayes risk (i.e., the risk when the algorithm is given the

nchumu

covariance as input) with respect to the prior P\mathcal{P} by:

Rε,δknown(P,n)=inf⁡{α≥0:∃ A∈Aε,δ s.t. Pr⁡(μ,Σ)∼PX∼N(μ,Σ)⊗n[∥A(X;Σ)−μ∥2≤α]≥34}.\mathcal{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P},n)=\inf\left\{\alpha\ge0:\exists\,\mathcal{A}\in\mathcal{A}_{\varepsilon,\delta}\ \text{s.t.}\ \underset{\substack{(\mu,\Sigma)\sim\mathcal{P}\\X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}}{\Pr}\left[\lVert\mathcal{A}(X;\Sigma)-\mu\rVert_2\le\alpha\right]\ge\frac{3}{4}\right\}.

Our results demonstrate the impossibility of private mean estimation with both dimension-free error and dimension-free sample complexity in two settings. Each setting highlights a distinct aspect of private mean estimation that requires many samples: In the first setting, the variance in each basis direction is fixed, and the difficulty stems from the fact that the basis directions are chosen uniformly at random, while in the second setting, the basis directions are fixed, and the difficulty stems from the fact that the variance in each direction is chosen from a suitably pathological distribution.

General covariance

In this setting, we consider mean estimation when the mean μ\mu and the covariance Σ\Sigma are sampled from the prior Psub\mathcal{P}_{\mathrm{sub}} defined by

(μ,Σ)∼Psub(d,k)⟺{μ∼N(0,d2Id)Σ=DDT where D∼Hd,k.(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{sub}}(d,k)\Longleftrightarrow \begin{cases} \mu\sim\mathcal{N}(0,d^2I_d)\\ \Sigma=DD^{\mathsf{T}}\ \text{where }D\sim\mathcal{H}_{d,k}. \end{cases}

where Hd,k\mathcal{H}_{d,k} is the uniform distribution over d×kd\times k matrices with orthonormal columns. Note that the effective dimension of every matrix in the support of the prior is kk, and that the resulting distributions N(μ,Σ)\mathcal{N}(\mu,\Sigma) are highly structured—the data are isotropic in a kk-dimensional subspace. Indeed, if Σ\Sigma is known, then the problem reduces to Gaussian mean estimation with covariance IkI_k. Using the bound in (1) for the error in the known covariance setting yields

Rε,δknown(Psub,n)=O~ε,δ(kn+kn).(2)\mathcal{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)=\widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{k}{n}}+\frac{k}{n}\right). \tag*{(2)}

On the other hand, when Σ\Sigma is unknown, a folklore algorithm based on the FriendlyCore framework of [TCKMS22] (presented in Section B for completeness) bounds the unknown covariance risk by O~ε,δ(tr⁡(Σ)n+dtr⁡(Σ)n)\widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{\operatorname{tr}(\Sigma)}{n}}+\frac{\sqrt{d\operatorname{tr}(\Sigma)}}{n}\right), which yields

Rε,δ(Psub,n)=O~ε,δ(kn+dkn).(3)\mathcal{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)=\widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{k}{n}}+\frac{\sqrt{dk}}{n}\right). \tag*{(3)}

Our main result shows that when n≪kn\ll k the folklore estimator is optimal—in particular, a private algorithm cannot take advantage of the low dimensional structure until it has seen almost every direction in the span of Σ\Sigma.

Theorem 2.1. For all n,k,d∈Nn,k,d\in\mathbb{N} with k≲dk\lesssim d and nlog⁡n≲kn\log n\lesssim k, if ε≤1\varepsilon\le1 and δ≲1/n\delta\lesssim1/n then every (ε,δ)(\varepsilon,\delta)-DP algorithm M\mathcal{M} satisfies

Pr⁡(μ,Σ)∼PsubX∼N(μ,Σ)⊗n[∥M(X)−μ∥2≥dkn]≥14.\underset{\substack{(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{sub}}\\X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}}{\Pr}\left[\lVert\mathcal{M}(X)-\mu\rVert_2\ge\frac{\sqrt{dk}}{n}\right]\ge\frac{1}{4}.

In particular, Rε,δ(Psub,n)≥dkn\mathcal{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)\ge\frac{\sqrt{dk}}{n}.

Theorem 2.1 is tight in two respects: First, it matches the upper bound in (3) for the setting where nlog⁡n<kn \log n < k, and second, once n≳k+ε−1n \gtrsim k + \varepsilon^{-1}, one can use the results of [SS21] to learn Σ\Sigma exactly and recover the bound in (2). Additionally, for the setting of nlog⁡n<kn \log n < k, comparing the bound in Theorem 2.1 and the bound in (2) yields the following scale-free bound on the cost of unknown covariance in private mean estimation,

Rε,δ(Psub,n)=Ω~ε,δ(1+dk)⋅Rε,δknown(Psub,n).\mathfrak{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)=\widetilde{\Omega}_{\varepsilon,\delta}\left(1+\sqrt{\frac{d}{k}}\right)\cdot\mathfrak{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n).

Setting k≈nlog⁡nk\approx n\log n recovers the blowup for general covariance in Table 1.

Diagonal covariance

While the previous setting leverages the randomness in the basis vectors, in the second setting, we instead fix the basis vectors (i.e., we consider diagonal covariance), and leverage the randomness in the variances themselves. To do so, we consider the prior Pdiag\mathcal{P}_{\mathrm{diag}} defined by

References

  1. [1][AAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. “On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians.” International Conference on Algorithmic Learning Theory. ALT 2021.
  2. [2][ALNP24] Martin Aumüller, Christian Janos Lebeda, Boel Nelson, and Rasmus Pagh. “PLAN: Variance-Aware Private Mean Estimation.” Privacy Enhancing Technologies Symposium. PETS 2024. (Link).arxiv.org/abs/2306.08745
  3. [3][BBFST21] Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. “When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?” arXiv preprint arXiv:2012.06421 (2021). (Link).DOI
  4. [4][BGSUZ21] Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. “Covariance-Aware Private Mean Estimation Without Private Covariance Estimation.” Advances in Neural Information Processing Systems. NeurIPS 2021. (Link).arxiv.org/abs/2106.13329
  5. [5][BHS23] Gavin Brown, Samuel B. Hopkins, and Adam Smith. “Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions.” Conference on Learning Theory. COLT 2023.arxiv.org/abs/2301.12250
  6. [6][BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. “Private Hypothesis Selection.” Advances in Neural Information Processing Systems. NeurIPS 2019.arxiv.org/abs/1905.13229
  7. [7][BUV14] Mark Bun, Jonathan Ullman, and Salil Vadhan. “Fingerprinting Codes and the Price of Approximate Differential Privacy.” ACM Symposium on Theory of Computing. STOC 2014. (Link).
  8. [8][Car+21] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, et al. “Extracting training data from large language models.” USENIX Security Symposium. USENIX Security 2021. (Link).arxiv.org/abs/2012.07805
  9. [9][CDMM26] Sitan Chen, Jingqiu Ding, Mahbod Majid, and Walter McKelvie. “Computation-Utility-Privacy Tradeoffs in Bayesian Estimation.” ACM Symposium on Theory of Computing. STOC 2026. (Link).
  10. [10][CLEKS19] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. “The secret sharer: Evaluating and testing unintended memorization in neural networks.” USENIX Security Symposium. USENIX Security 2019. (Link).arxiv.org/abs/1802.08232
  11. [11][CWZ19] T. Tony Cai, Yichen Wang, and Linjun Zhang. “The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Differential Privacy.” arXiv preprint arXiv:1902.04495 (2019). (Link).arxiv.org/abs/1902.04495
  12. [12][CWZ23] T. Tony Cai, Yichen Wang, and Linjun Zhang. “Score attack: A lower bound technique for optimal differentially private learning.” arXiv preprint arXiv:2303.07152 (2023). (Link).arxiv.org/abs/2303.07152
  13. [13][DJYZZ24] Yuval Dagan, Michael Jordan, Xuelin Yang, Lydia Zakynthinou, and Nikita Zhivotovskiy. “Dimension-free private mean estimation for anisotropic distributions.” Advances in Neural Information Processing Systems. NeurIPS 2024. (Link).arxiv.org/abs/2411.00775
  14. [14][DL22] Jules Depersin and Guillaume Lecué. “Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms.” Probability Theory and Related Fields 183.3 (2022).arxiv.org/abs/2102.00995
  15. [15][DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. “Calibrating Noise to Sensitivity in Private Data Analysis.” Conference on Theory of Cryptography. TCC 2006. (Link).
  16. [16][DMT07] Cynthia Dwork, Frank McSherry, and Kunal Talwar. “The price of privacy and the limits of LP decoding.” ACM Symposium on Theory of Computing. STOC 2007. (Link).DOI
  17. [17][DN03] Irit Dinur and Kobbi Nissim. “Revealing information while preserving privacy.” ACM Symposium on Principles of Database Systems. PODS 2003. (Link).DOI
  18. [18][DSSUV15] Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. “Robust Traceability from Trace Amounts.” IEEE Symposium on Foundations of Computer Science. FOCS 2015. (Link).DOI
  19. [19][DY08] Cynthia Dwork and Sergey Yekhanin. “New efficient attacks on statistical disclosure control mechanisms.” International Cryptology Conference. CRYPTO 2008. (Link).DOI
  20. [20][Fel20] Vitaly Feldman. “Does learning require memorization? A short tale about a long tail.” ACM Symposium on Theory of Computing. STOC 2020. (Link).arxiv.org/abs/1906.05271
  21. [21][GLSUZ26] Renaud Gaucher, Ephraim Linder, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. A Simple Presentation of Robust Membership Inference Attacks. 2026. arXiv: 2610.36458 [cs. CR]. (Link).arxiv.org/abs/2610.36458
  22. [22]Nils Homer, Szabolcs Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V. Pearson, Dietrich A. Stephan, et al. “Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays.” PLoS Genetics 4.8 (2008). (Link).DOI
  23. [23]Rohith Kuditipudi, John C. Duchi, and Saminul Haque. “A Pretty Fast Algorithm for Adaptive Private Mean Estimation.” Conference on Learning Theory. COLT 2023.arxiv.org/abs/2301.07078
  24. [24]Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. “Privately Learning High Dimensional Distributions.” Conference on Learning Theory. COLT 2019. (Link).arxiv.org/abs/1805.00216
  25. [25]Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. “New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma.” Advances in Neural Information Processing Systems. NeurIPS 2022.arxiv.org/abs/2205.08532
  26. [26]Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar, and Kevin Tian. “On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA.” Conference on Learning Theory. COLT 2026. (Link).arxiv.org/abs/2606.21951
  27. [27]Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman. “The price of privately releasing contingency tables and the spectra of random matrices with correlated rows.” ACM Symposium on Theory of Computing. STOC 2010. (Link).DOI
  28. [28]Vishesh Karwa and Salil Vadhan. “Finite Sample Differentially Private Confidence Intervals.” Conference on Innovations in Theoretical Computer Science. ITCS 2018. (Link).arxiv.org/abs/1711.03908
  29. [29]Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. “Robust and differentially private mean estimation.” Advances in Neural Information Processing Systems. NeurIPS 2021.arxiv.org/abs/2102.09159
  30. [30]Béatrice Laurent and Pascal Massart. “Adaptive estimation of a quadratic functional by model selection.” The Annals of Statistics 28.5 (2000). (Link).
  31. [31]Arshak Minasyan and Nikita Zhivotovskiy. “Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians.” Mathematical Statistics and Learning. Vol. 8. 2025. (Link).arxiv.org/abs/2301.09024
  32. [32]Shyam Narayanan. “Better and Simpler Lower Bounds for Differentially Private Statistical Estimation.” IEEE Trans. Inf. Theor. 71.2 (Feb. 2025). ISSN: 0018-9448. DOI: 10.1109/TIT.2024.3511624. (Link).DOI
  33. [33]Victor S. Portella and Nicholas J. A. Harvey. “Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes.” Conference on Learning Theory. COLT 2025. (Link).arxiv.org/abs/2404.17714
  34. [34]Naty Peter, Eliad Tsfadia, and Jonathan Ullman. “Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes.” Conference on Learning Theory. COLT 2024. (Link).arxiv.org/abs/2307.07604
  35. [35]Adam Smith. “Privacy-Preserving Statistical Estimation with Optimal Convergence Rates.” ACM Symposium on Theory of Computing. STOC 2011.DOI
  36. [36]Sriram Sankararaman, Guillaume Obozinski, Michael I. Jordan, and Eran Halperin. “Genomic privacy and limits of individual detection in a pool.” Nature Genetics 41.9 (2009). (Link).DOI

Paper details

vlnc:W_rxjr97rk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents