Lower Bounds for Locally Private Estimation via Communication Complexity
In collaboration with Stanford University
AuthorsJohn Duchi, Ryan Rogers
In collaboration with Stanford University
AuthorsJohn Duchi, Ryan Rogers
We develop lower bounds for estimation under local privacy constraints—including differential privacy and its relaxations to approximate or Ré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