<div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote">Hi all, A reminder that tomorrow, Abhradeep Thakurta will give a talk on new results in differential privacy.  Abstract below.</div><div class="gmail_quote">

<br></div><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div>Sharon</div><div><br></div><div> BUsec Calendar:  <a href="http://www.bu.edu/cs/busec/" target="_blank">http://www.bu.edu/cs/busec/</a></div>

<div> BUsec Mailing list:  <a href="http://cs-mailman.bu.edu/mailman/listinfo/busec" target="_blank">http://cs-mailman.bu.edu/mailman/listinfo/busec</a></div>


<div> How to get to BU from MIT:  Try the CT2 bus or MIT&#39;s &quot;Boston Daytime</div><div> Shuttle&quot; <a href="http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html" target="_blank">http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html</a></div>




<div><br></div><div>*******</div><div><br></div><div>[Privacy Year Event]</div><div>Title: (Nearly) Optimal Differentially Private Singular Subspace Computation</div><div>Speaker: Abhradeep Guha Thakurta, Stanford University and Microsoft Research</div>




<div>Wednesday, December 18, 10am – 11:30am</div><div>MCS137, 111 Cummington St, Boston MA</div><div><br></div><div>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-&gt;\infty.</div>




<div><br></div><div>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).</div>




<div><br></div><div>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.</div><div><br></div><div>




Joint work with: Cynthia Dwork, Kunal Talwar and Li Zhang.</div><div></div></div>
</div></div>
</div><br><br></div>
</div><br><br clear="all"><br>-- <br>Sharon Goldberg<br>Computer Science, Boston University<br><a href="http://www.cs.bu.edu/~goldbe" target="_blank">http://www.cs.bu.edu/~goldbe</a>
</div>