[Colloquium] TTIC Colloquium: Kamalika Chaudhuri, UCSD

[Liv Leader]

When:     Monday, April 9 @ 11 a.m.

Where:    TTIC, 6045 S. Kenwood Avenue, Room 526

Who:      Kamalika Chaudhuri, UCSD

Title:       The Price of Privacy: Sample Complexity Bounds for
Differentially Private Classification

We study the problem of differentially private classification --
namely, how to learn a predictor or classifier from sensitive training
data, while still preserving the privacy of individuals in the data. A
natural
question to ask is: what is the sample requirement of a learning
algorithm that guarantees a certain level of privacy and accuracy?
Previous work studied this question in the context of discrete data
distributions, and provided an upper bound, and lower bounds for some
specific classes. In the first part of this talk, we show a new lower
bound that holds for general classification problems which obey
certain fairly-loose conditions.

In the second part of this talk, we consider this question in the
context of learning infinite hypothesis classes on continuous data
distributions. We show that in this case, even for very simple
hypothesis classes, any algorithm that uses a finite number of
samples and guarantees differential privacy must fail to return an
accurate classifier for at least some unlabeled data distributions.
This result is unlike the case with either finite hypothesis classes
or discrete data domains, in which distribution-free private learning
is possible (as was shown by previous work).

This talk is based on joint work with Daniel Hsu

Host: Jinbo Xu, j3xu at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120403/4712312f/attachment.htm