Sample and Threshold Differential Privacy: Histograms and applications
share
Federated analytics relies on the collection of accurate statistics about distributed users with a suitable guarantee. In this paper, we show how a strong (ϵ, δ)-privacy guarantee can be achieved for the fundamental problem of histogram generation in a federated setting, via a highly practical sampling-based procedure. Given such histograms, related problems such as heavy hitters and quantiles can be answered with provable error and privacy guarantees. Our experimental results demonstrate that this sample-and-threshold approach is both accurate and scalable.
READ FULL TEXT