Differentially Private Assouad, Fano, and Le Cam
This work addresses the challenge of proving lower bounds in differentially private statistical estimation, which is crucial for privacy-preserving data analysis, though it is incremental as it adapts existing techniques to a new context.
The authors tackled the problem of establishing lower bounds for statistical estimation under differential privacy by proposing analogues of Le Cam's method, Fano's inequality, and Assouad's lemma. They applied these results to derive optimal sample complexity bounds for discrete distribution estimation and tight lower bounds for other distribution classes, such as product distributions and Gaussian mixtures.
Le Cam's method, Fano's inequality, and Assouad's lemma are three widely used techniques to prove lower bounds for statistical estimation tasks. We propose their analogues under central differential privacy. Our results are simple, easy to apply and we use them to establish sample complexity bounds in several estimation tasks. We establish the optimal sample complexity of discrete distribution estimation under total variation distance and $\ell_2$ distance. We also provide lower bounds for several other distribution classes, including product distributions and Gaussian mixtures that are tight up to logarithmic factors. The technical component of our paper relates coupling between distributions to the sample complexity of estimation under differential privacy.