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.
Description
[2004.06830] Differentially Private Assouad, Fano, and Le Cam
%0 Journal Article
%1 acharya2020differentially
%A Acharya, Jayadev
%A Sun, Ziteng
%A Zhang, Huanyu
%D 2020
%K bounds differential-privacy inequality readings
%T Differentially Private Assouad, Fano, and Le Cam
%U http://arxiv.org/abs/2004.06830
%X 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.
@article{acharya2020differentially,
abstract = {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.},
added-at = {2020-05-03T11:10:49.000+0200},
author = {Acharya, Jayadev and Sun, Ziteng and Zhang, Huanyu},
biburl = {https://www.bibsonomy.org/bibtex/275e3649d96e53adb828710c6d3a19b24/kirk86},
description = {[2004.06830] Differentially Private Assouad, Fano, and Le Cam},
interhash = {390435a2ace6dc9fdc46ced8863e37d4},
intrahash = {75e3649d96e53adb828710c6d3a19b24},
keywords = {bounds differential-privacy inequality readings},
note = {cite arxiv:2004.06830},
timestamp = {2020-05-03T11:10:49.000+0200},
title = {Differentially Private Assouad, Fano, and Le Cam},
url = {http://arxiv.org/abs/2004.06830},
year = 2020
}