[Busec] Fwd: busec this week: Zhenming Liu (TIME CHANGED to **Mon 11am**) and Abhradeep Thakurta (Wed 10am)

Sharon Goldberg goldbe at cs.bu.edu
Tue Dec 17 15:15:02 EST 2013

Hi all, A reminder that tomorrow, Abhradeep Thakurta will give a talk on
new results in differential privacy.  Abstract below.


 BUsec Calendar:  http://www.bu.edu/cs/busec/
 BUsec Mailing list:  http://cs-mailman.bu.edu/mailman/listinfo/busec
 How to get to BU from MIT:  Try the CT2 bus or MIT's "Boston Daytime


[Privacy Year Event]
Title: (Nearly) Optimal Differentially Private Singular Subspace Computation
Speaker: Abhradeep Guha Thakurta, Stanford University and Microsoft Research
Wednesday, December 18, 10am – 11:30am
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

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

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.

Sharon Goldberg
Computer Science, Boston University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20131217/5e97cf37/attachment.html>

More information about the Busec mailing list