Analyze gauss: optimal bounds for privacy-preserving principal component analysis

By Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, Li Zhang. 2014

338 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Science Applications

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

In Computer Science Applications

Citations in the corpus

Tight Lower Bounds for Differentially Private Selection (2017, background): “We remark that previous fingerprinting-based lower bounds in differential privacy [16], [27], [28], [17], [18], [3] essentially correspond to setting β = O(1) in Theorem 3.”
Fingerprinting codes and the price of approximate differential privacy (2013, methodology): “mplify our analysis of robust ngerprinting codes. Our ngerprinting code technique has also been used to prove lower bounds for other types of dierentially private data analyses. Namely, Dwork et al. [DTTZ14] prove lower bounds for dierentially private principal component analysis and Bassily, Smith,”
Between Pure and Approximate Differential Privacy (2015, background): “, 2014) and private principle component analysis (Dwork et al., 2014).”
Simultaneous Private Learning of Multiple Concepts (2015, background): “The connection between fingerprinting codes and differential privacy lower bounds was established by Bun, Ullman, and Vadhan [14] in the context of private query release, and has since been extended to a number of other differentially private analyses [3, 20, 32, 13].”
Privately Learning High-Dimensional Distributions (2018, background): “These attacks apply to a number of learning problems, such as PCA [DTTZ14], ERM [BST14], and variable selection [BU17, SU17b].”
Nearly Optimal Private LASSO (2015, methodology): “The following theorem follows immediately from the proof of Corollary 16 in [14].”
Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification (2020, methodology): “To bound ‖V̂k(t)V̂k(t) − Vk(t)Vk(t)‖2, we first bound the deviation between second moment matrix ‖Mt − Σt‖ [15, 26].”
Personalized Federated Learning With Differential Privacy (2020, background): “The differentially private approaches in machine learning can be categorized according to the object it perturbs: one is to directly add noises to the training data [30], another is to add noises to the output of training at each iteration or at the end [6].”
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU (2017, methodology): “In this paper, we study the online variant of this problem, which is a learning game between a player and an adversary [2, 14, 17, 22, 26].”
Differentially Private Release and Learning of Threshold Functions (2015, background): “” This is a variant on traditional fingerprinting codes, which have been used recently to show nearly optimal lower bounds for other problems in approximate differential privacy [9], [23], [1].”
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].”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, background): “[29] prove lower bounds for differentially private principal component analysis and Bassily, Smith, and Thakurta [4] prove lower bounds for differentially private empirical risk minimization.”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “For non-convex problem under differential privacy, [15][10][13] studied private SVD. [14] investigated k-median clustering.”
Privacy-Preserving Machine Learning: Threats and Solutions (2018, methodology): “Taking PCA as an example where Eigen-decomposition is performed on the covariance matrix, Dwork et al. 18 adds symmetric Gaussian noise matrix to the covariance matrix before performing Eigen-decomposition.”
Deep Learning with Gaussian Differential Privacy (2019, neutral): “Here the sensitivity of θ is deﬁned as sens( θ ) = sup S,S | θ ( S ) − θ ( S (cid:48) ) | , where the supremum is over all neighboring datasets.”