Fisher Information as a Utility Metric for Frequency Estimation under Local Differential Privacy

Local Differential Privacy (LDP) is the de facto standard technique to ensure privacy for users whose data is collected by a data aggregator they do not necessarily trust. This necessarily involves a tradeoff between user privacy and aggregator utility, and an important question is to optimize utility (under a given metric) for a given privacy level. Unfortunately, existing utility metrics are either hard to optimize for, or they only indirectly relate to an aggregator's goal, leading to theoretically optimal protocols that are unsuitable in practice. In this paper, we introduce a new utility metric for when the aggregator tries to estimate the true data's distribution in a finite set. The new metric is based on Fisher information, which expresses the aggregators information gain through the protocol. We show that this metric relates to other utility metrics such as estimator accuracy and mutual information and to the LDP parameter \varepsilon. Furthermore, we show that under this metric, we can approximate the optimal protocols as \varepsilon \rightarrow 0 and \varepsilon \rightarrow \infty, and we show how the optimal protocol can be found for a fixed \varepsilon, although the latter is computationally infeasible for large input spaces.