[Busec] BUsec: Kobbi Nissim (11AM Wed)

Sharon Goldberg goldbe at cs.bu.edu
Mon Dec 3 12:30:42 EST 2012

Hi all,

Note the time change for Kobbi Nissim's colloquium -- the colloquium
will be at 11AM on Wednesday, not 3pm as was announced previously.

See you there,

---------- Forwarded message ----------
From: Nora Conroy <conroynm at bu.edu>
Date: Mon, Dec 3, 2012 at 12:07 PM
Subject: CS Colloquium this Wednesday
To: "colloq-l at cs.bu.edu" <colloq-l at cs.bu.edu>

Characterizing the Sample Complexity of Private Learners
Kobbi Nissim
Wednesday, December 5, 2012
11AM - 1PM in MCS 148

The notion of private learning [Kasiviswanathan, Lee, N, Raskhodnikova, and
Smith '08] is a combination of PAC (probably approximately correct) learning
[Valiant 84] and differential privacy [Dwork, McSherry, N, and Smith '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.

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.

Joint work with Amos Beimel and Uri Stemmer.

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list