Timezone: »

Near-optimal Differentially Private Principal Components
Kamalika Chaudhuri · Anand D Sarwate · Kaushik Sinha

Mon Dec 03 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor

Principal components analysis (PCA) is a standard tool for identifying good low-dimensional approximations to data sets in high dimension. Many current data sets of interest contain private or sensitive information about individuals. Algorithms which operate on such data should be sensitive to the privacy risks in publishing their outputs. Differential privacy is a framework for developing tradeoffs between privacy and the utility of these outputs. In this paper we investigate the theory and empirical performance of differentially private approximations to PCA and propose a new method which explicitly optimizes the utility of the output. We demonstrate that on real data, there this a large performance gap between the existing methods and our method. We show that the sample complexity for the two procedures differs in the scaling with the data dimension, and that our method is nearly optimal in terms of this scaling.

Author Information

Kamalika Chaudhuri (UCSD)
Anand D Sarwate (Rutgers, The State University of New Jersey)
Kaushik Sinha (The Ohio State University)

More from the Same Authors