Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
- 9 December 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (2) , 1376-1388
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.
Keywords
All Related Versions
Funding Information
- NSF graduate fellowship
- Google Fellowship
This publication has 22 references indexed in Scilit:
- Private Hypothesis SelectionIEEE Transactions on Information Theory, 2021
- High-Dimensional Probability2018
- Tight Lower Bounds for Differentially Private Selection2017
- Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures2017
- Interactive fingerprinting codes and the hardness of preventing false discovery2016
- Robust Traceability from Trace Amounts2015
- Efficient Algorithms for Privately Releasing Marginals via Convex RelaxationsDiscrete & Computational Geometry, 2015
- Preventing False Discovery in Interactive Data Analysis Is Hard2014
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Condition Numbers of Gaussian Random MatricesSIAM Journal on Matrix Analysis and Applications, 2005