Differentially Private Assouad, Fano, and Le Cam
By Jayadev Acharya, Ziteng Sun, Huanyu Zhang. 2020
76 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Ananda Theertha Suresh
- Sanjiv Kumar
- Felix X. Yu
- Michael D. Riley
- Yuhan Liu
- Jakub Konecný
- Peter Richtárik
- Mehryar Mohri
In Computational Theory and Mathematics
Citations in the corpus
- Learning discrete distributions: user vs item-level privacy (2020, methodology): “Applying Theorem 9 completes the proof.”