<br><br>On Wednesday, December 5, 2012, Nora Conroy  wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="text-align:center">Characterizing the Sample Complexity of Private Learners<br>

</div>
<div class="gmail_quote">
<div style="text-align:center">
Kobbi Nissim, Ben Gurion University<br>

<b>11AM - 12PM</b> in MCS 148<br>
</div>
<br>
The notion of private learning [Kasiviswanathan, Lee, N, Raskhodnikova, and Smith &#39;08] is a combination of PAC (probably approximately correct) learning [Valiant 84] and differential privacy [Dwork, McSherry, N, and Smith &#39;06]. Kasiviswanathan el al. presented a generic construction of private learner for finite concept classes, where the sample complexity depends logarithmically in the size of the concept class. For concept classes of small VC dimension, this sample complexity is significantly larger than what is sufficient for non-private learning.<br>


<br>
In this talk I will motivate differential privacy and private learning, and will present some of the known bounds on the sample complexity of private learners. In particular, a recent characterization of the sample complexity as a combinatorial measure of the learned concept class.<br>


<br>
Joint work with Amos Beimel and Uri Stemmer.
</div>
</blockquote><br><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><br>