Dimension-free Private Mean Estimation for Anisotropic Distributions

We present differentially private algorithms for high-dimensional mean estimation. Previous private estimators on distributions over ℝd suffer from a curse of dimensionality, as they require Omega(d1/2) samples to achieve non-trivial error, even in cases where O(1) samples suffice without privacy. This rate is unavoidable when the distribution is isotropic, namely, when the covariance is a multiple of the identity matrix, or when accuracy is measured with respect to the affine-invariant Mahalanobis distance. Yet, real-world data is often highly anisotropic, with signals concentrated on a small number of principal components. We develop estimators that are appropriate for such signalsunicodex2013our estimators are (varepsilon,δ)-differentially private and have sample complexity that is dimension-independent for anisotropic subgaussian distributions. Given n samples from a distribution with known covariance-proxy Sigma and unknown mean μ, we present an estimator hatμ that achieves error |hatμ-μ|2≤ α, as long as ngtrsimtr(Sigma)/α2+ tr(Sigma1/2)/(αvarepsilon). In particular, when pmbσ2=(σ12, ldots, σd2) are the singular values of Sigma, we have tr(Sigma)=|pmbσ|22 and tr(Sigma1/2)=|pmbσ|1, and hence our bound avoids dimension-dependence when the signal is concentrated in a few principal components. We show that this is the optimal sample complexity for this task up to logarithmic factors. Moreover, for the case of unknown covariance, we present an algorithm whose sample complexity has improved dependence on the dimension, from d1/2 to d1/4.