Beating randomized response on incoherent matrices

By Moritz Hardt, Aaron Roth. 2011

99 citations recorded by the source corpus.

Computing accurate low rank approximations of large matrices is a fundamental data mining task. In many applications however the matrix contains sensitive information about individuals. In such case we would like to release a low rank approximation that satisfies a strong privacy guarantee such as differential privacy. Unfortunately, to date the best known algorithm for this task that satisfies differential privacy is based on naive input perturbation or randomized response: Each entry of the matrix is perturbed independently by a sufficiently large random noise variable, a low rank approximation is then computed on the resulting matrix. We give (the first) significant improvements in accuracy over randomized response under the natural and necessary assumption that the matrix has low coherence. Our algorithm is also very efficient and finds a constant rank approximation of an m x n matrix in time O(mn). Note that even generating the noise matrix required for randomized response already requires time O(mn).

Subfields: Artificial Intelligence, Computational Mechanics

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 Computational Mechanics

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”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, methodology): “Hardt and Roth [18] gave a privacy preserving version of an algorithm of [16] that uses randomize projections onto the image space of a given matrix.”
PrivEx: Private Collection of Traffic Statistics for Anonymous Communication Networks (2014, background): “…to ( (cid:15), δ ) -differential privacy by observing the parameters’ relation to σ as follows [14]: Thus, rather than, as in previous works [10,14], having the system designer select not-very-meaningful values of (cid:15) and δ , and computing σ as above to determine how much noise to add, we…”
Analyze gauss: optimal bounds for privacy-preserving principal component analysis (2014, background): “The problem of low-rank approximation has also received substantial attention in the differential privacy literature [4, 14, 23, 21, 9, 17, 18].”
Understanding Alternating Minimization for Matrix Completion (2013, methodology): “Privacy-preserving spectral analysis: Our work is also closely related to a line of work on differentially private singular vector computation [21], [22], [23].”
Random Projections, Graph Sparsification, and Differential Privacy (2013, background): “Exponential Sanitizer [4, 27] O(n logn/ε) Intractable Multiplicative Weight [17, 19]∗ Õ( p |E| log k/ε) O(n(2))”
Beyond worst-case analysis in private singular vector computation (2012, methodology): “This problem was ﬁrst considered by Gupta, Roth, and Ullman [GRU12] who gave methods for e ﬃ ciently releasing synthetic data for graph cuts with additive error O ( n 1 .”
Near-Optimal Algorithms for Differentially-Private Principal Components (2012, methodology): “Hardt and Roth (2013) show a method for guaranteeing differential privacy under an entry-wise neighborhood condition using the power method for calculating singular values.”
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, methodology): “…method for computing private, approximate solutions to high-dimensional optimization problems is objective perturbation [6]; to apply this method, we require the optimization problems to have certain properties (namely, strong convexity and bounded norms of gradients), which do not apply to PCA.”
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].”
On differentially private low rank approximation (2013, background): “In order to point out the diﬀerences between our work and the recent papers of [10, 3], we give the deﬁnition of ( (cid:15), δ )-diﬀerential privacy.”
Differentially Private Matrix Completion, Revisited (2017, background): “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.”