On differentially private low rank approximation

By M. Kapralov, Kunal Talwar. 2013

140 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Extremal Mechanisms for Local Differential Privacy (2014, methodology): “The typical recipe is to propose a differentially private mechanism inspired by [11, 13, 26, 20], and then establish its near-optimality by comparing the achievable utility to a converse, for example in principal component analysis [8, 5, 19, 24], linear queries [21, 18], logistic regression [7] and”
Private selection from private candidates (2018, background): “Some examples include private PAC learning [20], private frequent itemset mining [4], private PCA [7, 19] and private multiple hypothesis testing [14, 35].”
Random Projections, Graph Sparsification, and Differential Privacy (2013, methodology): “Since then, many sanitizers for preserving DP have been proposed in the literature, including the Exponential sanitizer [4, 23, 27], the Multiplicative Update sanitizer [16–19], the Median sanitizer [30], the Boosting sanitizer [10], and the Random Projection sanitizer [25].”
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].”
A Stability-based Validation Procedure for Differentially Private Machine Learning (2013, background): “…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], density estimation [28, 19], among others.”
Differential Privacy and Machine Learning: a Survey and Review (2014, methodology): “Some other papers [14, 50, 33, 40, 21, 31, 7, 27] use the distance of the parameters in private and non-private models when the models are parametric and have the same parameters.”
Differentially Private Matrix Completion, Revisited (2017, methodology): “Most of the prior works on DP matrix completion (and low-rank approximation) [6, 13, 24, 25, 34, 20] have provided guarantees which are non-trivial only in the entry-level privacy setting, i.”
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “Efficient implementations of the exponential mechanism over infinite domains were discussed by [20], [12] and [24].”
Optimal principal component analysis in distributed and streaming models (2015, unknown): “1 of [31]) For any m, k, δ > 0, there is a family N = {P(1), .”
Private Empirical Risk Minimization, Revisited (2014, unknown): “[8] and Kapralov and Talwar [25].”
A Comprehensive Survey of Privacy-preserving Federated Learning (2021, methodology): “DP-based PPML methods can be divided into two categories: privacy-preserving models designed by adding noise to the trained model [22, 85], and privacy-preserving models designed by adding noise to the objective function [21, 219].”
The Algorithmic Foundations of Differential Privacy (2014, methodology): “Spectral learning techniques, including PCA and low rank matrix approximation have also been studied [7, 14, 33, 42, 43, 51].”
Differentially private multi-party computation (2014, methodology): “classification [27, 9], k-means clustering [4], principal component analysis [7, 8, 23, 26].”
Near-optimal Differentially Private Principal Components (2012, background): “Our first sample complexity result provides an upper bound on the number of samples required by PPCA to guarantee a certain level of privacy and accuracy.”
Analyze gauss: optimal bounds for privacy-preserving principal component analysis (2014, background): “larity of the privacy guarantee, protecting, variously, the privacy of each row in its entirety [4, 14, 21, 9], which is what we do here, or individual entries [23, 18], or norm 1 changes to any row [17].”
Beyond worst-case analysis in private singular vector computation (2012, methodology): “The lemma here is actually an easy modification of the lemma from [11].”