Title: (Nearly) Optimal Differentially Private Singular Subspace Computation
Speaker: Abhradeep Guha Thakurta, Stanford University and Microsoft Research
Time: Wednesday, December 18, 10am – 11:30am
Place: MCS137, 111 Cummington St, Boston, MA
Abstract: In this work we study the problem of releasing the principal rank-k right singular subspace for a given matrix A\in R^{m x n} while preserving differential privacy. We study the problem in the context where each row of A is the private information belonging to an individual. We show that there exists an (\epsilon,\delta)-differentially private algorithm that can capture almost all the variance of A captured by the true principal rank-k right singular subspace, up to an additive error of O(k\sqrt n). We further show that the error can be significantly improved if the eigen spectrum of A^T A has a gap of \omega(\sqrt n) between k-th and (k+1)-th eigen values. As a corollary, we show that under the eigen gap above, the private subspace converges to the non-private subspace as m->\infty.
We also study the subspace estimation problem in the online setting, where the rows of the matrix arrive online. Using a variant of the Follow the Perturbed Leader algorithm of Kalai and Vempala, 2005, we manage to obtain a differentially private algorithm which has (nearly) optimal error (regret).
Finally, using the recent lower bounding technique of Bun, Ullman and Vadhan, 2013, we show that our results are essentially tight, both in the offline and the online setting.
Joint work with: Cynthia Dwork, Kunal Talwar and Li Zhang.
________________________________________
More info on BU Security Group
Busec mailing list
Busec@cs.bu.edu
http://cs-mailman.bu.edu/mailman/listinfo/busec