Timezone: »

 
Poster
New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
Gautam Kamath · Argyris Mouzakis · Vikrant Singhal

Wed Nov 30 09:00 AM -- 11:00 AM (PST) @ Hall J #817
in Poster Session 3 »
We prove new lower bounds for statistical estimation tasks under the constraint of $(\varepsilon,\delta)$-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 $\Omega(d^2)$ samples, and in spectral norm requires $\Omega(d^{3/2})$ samples, both matching upper bounds up to logarithmic factors. 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 $\Omega(d/(\alpha^2 \varepsilon))$ lower bound for estimating the mean of a distribution with bounded covariance to $\alpha$-error in $\ell_2$-distance. Prior known lower bounds for all these problems were either polynomially weaker or held under the stricter condition of $(\varepsilon,0)$-differential privacy.
Keywords: machine learning · differential privacy · mean estimation · lower bounds · learning · data privacy · covariance estimation · Gaussians · Statistics
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Gautam Kamath (University of Waterloo)
Argyris Mouzakis (University of Waterloo)
Vikrant Singhal (University of Waterloo)

More from the Same Authors