[Colloquium] Show and Tell Series at TTI-C (Tuesday, 9/20/05) Adam Kalai

[Katherine Cumming]

TTI-C SHOW AND TELL SERIES
 
Presented by:  Toyota Technological Institute at Chicago
 
 
Speaker: Adam Kalai, TTI-C
Speaker's home page: http://www.tti-c.org//kalai.html
 
Time: Tuesday, September 20th, 2005
Location: TTI-C Conference Room
Lunch Provided @ 12:00pm 
Seminar @ 12:15pm
 
Title: Towards learning as well as the best halfspace
 
Abstract: 
A longstanding open problem in computational learning theory is that of
"learning as well as the best halfspace."  In this problem, there is an
arbitrary and unknown joint distribution over n-dimensional vectors X and
their 0-1 labels Y.  The goal is to design an algorithm that provably learns
to predict the labels of future examples with error at most (opt + eps),
where opt is the error of the best halfspace predictor for the distribution,
for any eps > 0, using runtime and a number of samples of this distribution
that is polynomial in n and 1/eps. Since there is no relationship assumed
between X and Y, this can be also be viewed as learning with worst-case
noise.
 
We make progress on this problem by giving a simple learning algorithm that
learns such functions for a very general class of distributions on
n-dimensional vectors X (including any log-concave distribution) in time
polynomial in the dimension n (but not polynomial in 1/eps).  Note that our
distributional assumptions are only on X, and thus the algorithm tolerates
worst-case noise.
 
I will describe the simple algorithm that generalizes Fourier learning and
how SVMs with a polynomial kernel could be adapted to this problem, too.
This is joint work with Adam Klivans, Yishay Mansour, and Rocco Servedio.
 
 
 
 
 
-----------------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.  For information on future
TTI-C talks or events, please go to the TTI-C Events page,
http://www.tti-c.org/events.html.  TTI-C (1427 East 60th Street, Chicago, IL
60637)
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050915/75941114/attachment.htm