On the Utility Gain of Iterative Bayesian Update for Locally
  Differentially Private Mechanisms
Héber H. Arcolezi Selene Cerna Catuscia Palamidessi
This paper investigates the utility gain of using Iterative Bayesian Update
(IBU) for private discrete distribution estimation using data obfuscated with
Locally Differentially Private (LDP) mechanisms. We compare the performance of
IBU to Matrix Inversion (MI), a standard estimation technique, for seven LDP
mechanisms designed for one-time data collection and for other seven LDP
mechanisms designed for multiple data collections (e.g., RAPPOR). To broaden
the scope of our study, we also varied the utility metric, the number of users
n, the domain size k, and the privacy parameter {\epsilon}, using both
synthetic and real-world data. Our results suggest that IBU can be a useful
post-processing tool for improving the utility of LDP mechanisms in different
scenarios without any additional privacy cost. For instance, our experiments
show that IBU can provide better utility than MI, especially in high privacy
regimes (i.e., when {\epsilon} is small). Our paper provides insights for
practitioners to use IBU in conjunction with existing LDP mechanisms for more
accurate and privacy-preserving data analysis. Finally, we implemented IBU for
all fourteen LDP mechanisms into the state-of-the-art multi-freq-ldpy Python
package (https://pypi.org/project/multi-freq-ldpy/) and open-sourced all our
code used for the experiments as tutorials.