Lower Bounds for Locally Private Estimation via Communication Complexity

Publication date 1 February 2019

Abstract: We develop lower bounds for estimation under local privacy constraints---including differential privacy and its relaxations to approximate or R'{e}nyi differential privacy---by showing an equivalence between private estimation and communication-restricted estimation problems. Our results apply to arbitrarily interactive privacy mechanisms, and they also give sharp lower bounds for all levels of differential privacy protections, that is, privacy mechanisms with privacy levels

v a r e p s i l o n i n [0, i n f t y)

. As a particular consequence of our results, we show that the minimax mean-squared error for estimating the mean of a bounded or Gaussian random vector in

d

dimensions scales as

f r a c d n c d o t f r a c d m i n v a r e p s i l o n, v a r e p s i l o n^{2}

.

This page was built for publication: Lower Bounds for Locally Private Estimation via Communication Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6313457)