Near-Optimal Algorithms for Differentially-Private Principal Components

By Kamalika Chaudhuri, Anand D. Sarwate, Kaushik Sinha. 2012

178 citations recorded by the source corpus.

Principal components analysis (PCA) is a standard tool for identifying good low-dimensional approximations to data in high dimension. Many data sets of interest contain private or sensitive information about individuals. Algorithms which operate on such data should be sensitive to the privacy risks in publishing their outputs. Differential privacy is a framework for developing tradeoffs between privacy and the utility of these outputs. In this paper we investigate the theory and empirical performance of differentially private approximations to PCA and propose a new method which explicitly optimizes the utility of the output. We show that the sample complexity of the proposed method differs from the existing procedure in the scaling with the data dimension, and that our method is nearly optimal in terms of this scaling. We furthermore illustrate our results, showing that on real data there is a large performance gap between the existing method and our method.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Signal Processing and Machine Learning with Differential Privacy (2013, positive): “From these two settings, the literature has spread to cover more complex data processing algorithms such as realtime signal processing [11]–[13], classification [14]–[16], dimensionality reduction [17], [18], and auction design [19].”
Differentially private multi-party computation (2014, methodology): “classification [27, 9], k-means clustering [4], principal component analysis [7, 8, 23, 26].”
A Principled Approach to Learning Stochastic Representations for Privacy in Deep Neural Inference (2020, methodology): “…learning algorithms, such as logistic regression (Chaudhuri & Monteleoni, 2009), statistical risk minimization (Chaudhuri et al., 2009), principal component analysis (Jiang et al., 2013; Chaudhuri et al., 2013), and deep learning (Shokri & Shmatikov, 2015; Abadi et al., 2016), to name a few.”
Privacy and Statistical Risk: Formalisms and Minimax Bounds (2014, background): “This focus is diﬀerent from much of the work on optimality guarantees in private data analysis [16, 6, 26], though there have been a few authors who have studied population quantities (for example, Beimel and colleagues [4, 3] in the Probably Approximately Correct (PAC) model for concept learning).”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, methodology): “Within differential privacy, there are many algorithms for tasks that are related to learning mixtures of Gaussians, notably PCA [12, 49, 18, 33] and clustering [55, 39, 57, 56, 8, 62, 43].”
Private Empirical Risk Minimization, Revisited (2014, unknown): “[8] and Kapralov and Talwar [25].”
Private Heavy Hitters and Range Queries in the Shuffled Model (2019, background): “There have been several recent works that study differentially private algorithms in the central or local models for various statistical and learning tasks [25, 43, 47, 8, 14, 13, 15].”
Towards Measuring Membership Privacy (2017, methodology): “DP has been widely applied to complete privacy preserving machine learning tasks with different machine learning algorithms such as regression [44], SVM [34], principal component analysis [8], empirical risk minimization [7], and deep learning [36].”
A Stability-based Validation Procedure for Differentially Private Machine Learning (2013, background): “The past few years have seen an explosion in the literature on differentially private algorithms, and there currently exist differentially private algorithms for many statistical and machine-learning tasks such as classification [4, 15, 23, 10], regression [18], PCA [2, 5, 17, 12], clustering [2], d”
Privacy-Preserving Machine Learning: Threats and Solutions (2018, methodology): “This method was used for achieving DP-PCA by sampling a random k-dimensional subspace that approximates the top-k PCA subspace 20 .”
Blockchain-Based Privacy Preserving Deep Learning (2018, background): “2) Techniques based on differential privacy have been proposed to guarantee the confidentiality of personal data while training a differentially-private model [18], [19], [20], [21], [22], [23], [24], [25].”
Federated Learning for Healthcare Informatics (2019, background): “boosting [21], principal component analysis [14], support vector machine [78], but also deep learning research [1,”
INSPECTRE: Privately Estimating the Unseen (2018, unknown): “, 2017), principal component analysis (Chaudhuri et al., 2013; Kapralov & Talwar, 2013; Hardt & Price, 2014), ordinary least squares (Sheffet, 2017), and much more.”
Privacy-Preserving Distributed Multi-Task Learning with Asynchronous Updates (2017, background): “Differentially private learning has been widely studied in the literature, examples including Chaudhuri et al. [9, 10] where an efficient differentially private empirical risk minimization was developed, Jain and Thakurta [26] studied kernel learning under three practical models, and Kusner et al.…”
On differentially private low rank approximation (2013, background): “Independent of our work, Chaudhuri et al. [6] pro-pose and evaluate the exponential mechanism for PCA.”