Differentially Private Range Queries with Correlated Input Perturbation
Prathamesh Dharangutte Jie Gao Ruobin Gong Guanyang Wang
This work proposes a class of locally differentially private mechanisms for
linear queries, in particular range queries, that leverages correlated input
perturbation to simultaneously achieve unbiasedness, consistency, statistical
transparency, and control over utility requirements in terms of accuracy
targets expressed either in certain query margins or as implied by the
hierarchical database structure. The proposed Cascade Sampling algorithm
instantiates the mechanism exactly and efficiently. Our bounds show that we
obtain near-optimal utility while being empirically competitive against output
perturbation methods.