A Framework for Private Matrix Analysis

Abstract

We study private matrix analysis in the sliding window model where only the last $W$ updates to matrices are considered useful for analysis. We give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also initiate and show efficient differentially private algorithms for two important variants of principal component analysis: sparse principal component analysis and non-negative principal component analysis. Prior to our work, no such result was known for sparse and non-negative differentially private principal component analysis even in the static data setting. These algorithms are obtained by identifying sufficient conditions on positive semidefinite matrices formed from streamed matrices. We also show a lower bound on space required to compute low-rank approximation even if the algorithm gives multiplicative approximation and incurs additive error. This follows via reduction to a certain communication complexity problem.

arXiv comment41 pages

References in corpus (9)

• How To Break Anonymity of the Netflix Prize Dataset
• Truncated Power Method for Sparse Eigenvalue Problems
• A direct formulation for sparse PCA using semidefinite programming
• Gradient Descent Happens in a Tiny Subspace
• The Noisy Power Method: A Meta Algorithm with Applications
• Beating Randomized Response on Incoherent Matrices
• Private Decayed Sum Estimation under Continual Observation
• Sparse PCA through Low-rank Approximations
• Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians

Cited by in corpus (1)

• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces