Approximate differential privacy for applications in signal processing and machine learning

Abstract

Large corporations, government entities and institutions such as hospitals and census bureaus routinely collect our personal and sensitive information for providing various services. A key technological challenge is designing algorithms for these services that provide useful results, while simultaneously maintaining the privacy of the individuals whose data are being shared. Differential privacy (DP) is a cryptographically motivated and mathematically rigorous approach for addressing this challenge. Under DP, a randomized algorithm provides privacy guarantees by approximating the desired functionality, leading to a privacy–utility trade-off. Strong (pure DP) privacy guarantees are of- ten costly in terms of utility. Motivated by the need for a more efficient mechanism with better privacy–utility trade-off, we propose Gaussian FM, an improvement to the functional mechanism (FM) that offers higher utility at the expense of a weakened (approximate) DP guarantee. We show analytically and empirically that the proposed Gaussian FM algorithm can offer orders of magnitude smaller noise than the existing FM algorithms. For a feature vector of size 101, Gaussian FM yields only 1/103 of the noise standard deviation compared to the existing FM. Furthermore, we show how Gaussian FM can exploit a correlated noise generation protocol, CAPE, in decentralized-data settings to achieve the same noise variance as its centralized counterparts, and pro- pose capeFM. As opposed to conventional decentralized differential privacy schemes, capeFM can offer the same level of utility as that of the centralized-data settings with- out compromising privacy for a range of parameter choices. We empirically show that for privacy budget ϵ as small as 10-1 with probability at least (1 – 10-5), our proposed Gaussian FM and capeFM can achieve utility close to the non-private algorithms and outperform existing state-of-the-art approaches on synthetic and real datasets.