New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma

Abstract

We prove new lower bounds for statistical estimation tasks under the constraint of (, )-differential privacy. First, we provide tight lower bounds for private covariance estimation of Gaussian distributions. We show that estimating the covariance matrix in Frobenius norm requires (d^2) samples, and in spectral norm requires (d^3/2) samples, both matching upper bounds up to logarithmic factors. The latter bound verifies the existence of a conjectured statistical gap between the private and the non-private sample complexities for spectral estimation of Gaussian covariances. We prove these bounds via our main technical contribution, a broad generalization of the fingerprinting method to exponential families. Additionally, using the private Assouad method of Acharya, Sun, and Zhang, we show a tight (d/(^2 )) lower bound for estimating the mean of a distribution with bounded covariance to -error in _2-distance. Prior known lower bounds for all these problems were either polynomially weaker or held under the stricter condition of (, 0)-differential privacy.

Tasks

Reproductions