5807a685d1a9ab3b599035bc566ce2b9-Reviews.html

SUMMARY: This paper is a NIPS-formatted version of an ArXiV manuscript, and uses a Fano/LeCam-style argument to derive a lower bound on estimation algorithms that operate on private data when the algorithm is not trusted by the data holder. As a corollary, randomized response turns out to be an optimal strategy in some sense. As a caveat to this review, I did not go through the supplementary material. This confusion may be exacerbated by statements such as those at the bottom of page 4: "Thus, for suitably large sample sizes n, the effect of providing differential privacy at a level \alpha …" The authors should avoid making such overly broad (and perhaps incorrect) statements when describing their results. In particular, experimental results suggest that \alpha \approx 1 may be the most one can expect for certain learning problems (under differential privacy), so it is unclear the the bound tells us about this case.