Dimension-Free Private Mean Estimation is Impossible Without the Covariance
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 . 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 is smaller than the effective dimension , the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of . Second, when the sample size is larger than the effective dimension, even for diagonal covariance matrices with effective dimension bounded by , the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of . 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
| Setting | Error blowup | Obstruction |
|---|---|---|
| General covariance | {\displaystyle\mathrm{error}_{\mathrm{unknown}}=\tilde{\Theta}_{\varepsilon,\delta}\mathopen{}\mathclose{{\left(1+\sqrt{\frac{d}{n}}}}\right)\cdot\mathrm{error}_{\mathrm{known}}} | Subspace estimation |
| Diagonal covariance | {\displaystyle\mathrm{error}_{\mathrm{unknown}}=\tilde{\Theta}_{\varepsilon,\delta}\mathopen{}\mathclose{{\left(1+\frac{\sqrt{d}}{n^{1.5}}}}\right)\cdot\mathrm{error}_{\mathrm{known}}} | Identifying large variance coordinates |
| Covariance family | Upper bound (prior work) | Lower bound (this work) |
|---|---|---|
| Random rank- orthogonal projector | \displaystyle\tilde{O}_{\varepsilon,\delta}\mathopen{}\mathclose{{\left(\sqrt{\frac{k}{n}}+\frac{\sqrt{dk}}{n}}}\right) [ 40 ] | \displaystyle\Omega\mathopen{}\mathclose{{\left(\frac{\sqrt{dk}}{n}}}\right) for ( Theorem 2.1 ) |
| Inverse chi-squared diagonal prior | [ 13 ] | \displaystyle\Omega\mathopen{}\mathclose{{\left(\frac{d^{3/2}}{n^{2}}}}\right) for ( Theorem 3.2 ) |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| \bar{y}_{i}\leftarrow\frac{4\ell}{n}\sum_{y_{j}\in B_{i}}\mathopen{}\mathclose{{\left\|{y_{j}}}}\right\|_{2}^{2} |
Differential Privacy
Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.
See all 309 papers