Beyond worst-case analysis in private singular vector computation

By Moritz Hardt, Aaron Roth. 2012

126 citations recorded by the source corpus.

We consider differentially private approximate singular vector computation. Known worst-case lower bounds show that the error of any differentially private algorithm must scale polynomially with the dimension of the singular vector. We are able to replace this dependence on the dimension by a natural parameter known as the coherence of the matrix that is often observed to be significantly smaller than the dimension both theoretically and empirically. We also prove a matching lower bound showing that our guarantee is nearly optimal for every setting of the coherence parameter. Notably, we achieve our bounds by giving a robust analysis of the well-known power iteration algorithm, which may be of independent interest. Our algorithm also leads to improvements in worst-case settings and to better low-rank approximations in the spectral norm.

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

Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “For non-convex problem under differential privacy, [15][9][13] studied private SVD.”
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.”
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].”
Differential Privacy and Machine Learning: a Survey and Review (2014, background): “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.”
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].”
Privacy-preserving Analysis of Correlated Data (2016, background): “…et al., 2006), and there is a growing body of work on differentially private learning algorithms (Chaudhuri et al., 2011; Jain et al., 2012; Kifer et al., 2012; Chaudhuri et al., 2012; Hardt and Roth, 2013; Wang et al., 2015; Duchi et al., 2013; Bassily et al., 2014; Imtiaz and Sarwate, 2015).”
Differentially Private Matrix Completion, Revisited (2017, methodology): “Comparison with Private Power Iteration (PPI) method [25]: Private PCA via PPI provides utility guarantees dependent on the gap between the top and the kth eigenvalue of the input matrix A for some k > 1, whereas private Oja’s utility guarantee is gap-independent.”