New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma

Gautam Kamath, Argyris Mouzakis, Vikrant Singhal

We prove new lower bounds for statistical estimation tasks under the constraint of $(\epsilon ,\delta )$-differential privacy. First, we provide tight lower bounds for private covaria…