Abstract
We provide optimal lower bounds for two well-known parameter estimation (also known as statistical estimation) tasks in high dimensions with approximate differential privacy. First, we prove that for any $\alpha \le O(1)$ , estimating the covariance of a Gaussian up to spectral error $\alpha $ requires $\tilde {\Omega }\left ({{\frac {d^{3/2}}{\alpha \varepsilon } + \frac {d}{\alpha ^{2}}}}\right)$ samples, which is tight up to logarithmic factors. This result improves over previous work which established this for $\alpha \le O\left ({{\frac {1}{\sqrt {d}}}}\right)$ , and is also simpler than previous work. Next, we prove that estimating the mean of a heavy-tailed distribution with bounded kth moments requires $\tilde {\Omega }\left ({{\frac {d}{\alpha ^{k/(k-1)} \varepsilon } + \frac {d}{\alpha ^{2}}}}\right)$ samples. Previous work for this problem was only able to establish this lower bound against pure differential privacy, or in the special case of $k = 2$ . Our techniques follow the method of fingerprinting and are generally quite simple. Our lower bound for heavy-tailed estimation is based on a black-box reduction from privately estimating identity-covariance Gaussians. Our lower bound for covariance estimation utilizes a Bayesian approach to show that, under an Inverse Wishart prior distribution for the covariance matrix, no private estimator can be accurate even in expectation, without sufficiently many samples.
Funding Information
  • NSF graduate fellowship
  • Google Fellowship

This publication has 22 references indexed in Scilit: