More Like this

1. Task-aware Privacy Preservation for Multi-dimensional Data

   Cheng, J.; Tang, A.; Chinchali, S. (January 2022, International Conference on Machine Learning)

   Local differential privacy (LDP) can be adopted to anonymize richer user data attributes that will be input to sophisticated machine learning (ML) tasks. However, today’s LDP approaches are largely task-agnostic and often lead to severe performance loss – they simply inject noise to all data attributes according to a given privacy budget, regardless of what features are most relevant for the ultimate task. In this paper, we address how to significantly improve the ultimate task performance with multi-dimensional user data by considering a task-aware privacy preservation problem. The key idea is to use an encoder-decoder framework to learn (and anonymize) a task-relevant latent representation of user data. We obtain an analytical near-optimal solution for the linear setting with mean-squared error (MSE) task loss. We also provide an approximate solution through a gradient-based learning algorithm for general nonlinear cases. Extensive experiments demonstrate that our task-aware approach significantly improves ultimate task accuracy compared to standard benchmark LDP approaches with the same level of privacy guarantee. 

   more » « less
2. Locally Differentially Private Frequency Estimation with Consistency

   https://doi.org/10.14722/ndss.2020.24157  

   Wang, Tianhao; Lopuhaa-Zwakenberg, Milan; Li, Zitao; Skoric, Boris; Li, Ninghui (February 2020, NDSS'20: Proceedings of the NDSS Symposium)

   Local Differential Privacy (LDP) protects user privacy from the data collector. LDP protocols have been increasingly deployed in the industry. A basic building block is frequency oracle (FO) protocols, which estimate frequencies of values. While several FO protocols have been proposed, the design goal does not lead to optimal results for answering many queries. In this paper, we show that adding post-processing steps to FO protocols by exploiting the knowledge that all individual frequencies should be non-negative and they sum up to one can lead to significantly better accuracy for a wide range of tasks, including frequencies of individual values, frequencies of the most frequent values, and frequencies of subsets of values. We consider 10 different methods that exploit this knowledge differently. We establish theoretical relationships between some of them and conducted extensive experimental evaluations to understand which methods should be used for different query tasks. 

   more » « less
3. Discrete distribution estimation under user-level local differential privacy

   Acharya, Jayadev; Liu, Yuhan; Sun, Ziteng (April 2023, Proceedings of Machine Learning Research)

   Ruiz, Francisco; Dy, Jennifer; van de Meent, Jan-Willem (Ed.)

   We study discrete distribution estimation under user-level local differential privacy (LDP). In user-level $$\varepsilon$$-LDP, each user has $$m\ge1$$ samples and the privacy of all $$m$$ samples must be preserved simultaneously. We resolve the following dilemma: While on the one hand having more samples per user should provide more information about the underlying distribution, on the other hand, guaranteeing the privacy of all $$m$$ samples should make the estimation task more difficult. We obtain tight bounds for this problem under almost all parameter regimes. Perhaps surprisingly, we show that in suitable parameter regimes, having $$m$$ samples per user is equivalent to having $$m$$ times more users, each with only one sample. Our results demonstrate interesting phase transitions for $$m$$ and the privacy parameter $$\varepsilon$$ in the estimation risk. Finally, connecting with recent results on shuffled DP, we show that combined with random shuffling, our algorithm leads to optimal error guarantees (up to logarithmic factors) under the central model of user-level DP in certain parameter regimes. We provide several simulations to verify our theoretical findings. 

   more » « less
4. Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints

   Acharya, Jayadev; Kairouz, Peter; Liu, Yuhan; Sun, Ziteng (March 2021, Proceedings of Machine Learning Research)

   We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor, and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on recently proposed method of chi squared contractions. 

   more » « less
5. CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy

   https://doi.org/10.1145/3243734.3243742  

   Zhang, Zhikun; Wang, Tianhao; Li, Ninghui; He, Shibo; Chen, Jiming (October 2018, CCS '18 Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security)

   Marginal tables are the workhorse of capturing the correlations among a set of attributes. We consider the problem of constructing marginal tables given a set of user’s multi-dimensional data while satisfying Local Differential Privacy (LDP), a privacy notion that protects individual user’s privacy without relying on a trusted third party. Existing works on this problem perform poorly in the high-dimensional setting; even worse, some incur very expensive computational overhead. In this paper, we propose CALM, Consistent Adaptive Local Marginal, that takes advantage of the careful challenge analysis and performs consistently better than existing methods. More importantly, CALM can scale well with large data dimensions and marginal sizes. We conduct extensive experiments on several real world datasets. Experimental results demonstrate the effectiveness and efficiency of CALM over existing methods. 

   more » « less