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

CardsList
  1. Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy

    Mar 20, 2026T. Tony Cai, Yicheng LiCovariance EstimationParameter Estimation

  2. Private Adaptive Covariance Estimation via Gaussian Graphical Models

    May 22, 2026Cecilia Ferrando, Miguel Fuentes, Brett Mullins +2Differential PrivacyCovariance Estimation