Dimension-Free Private Mean Estimation is Impossible Without the Covariance

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

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 $d$. 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 $n$ is smaller than the effective dimension $\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 $\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$, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of $\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.