ColloquiaTalk by Shai Ben-David: Monday March 10th

[Meridel Trimble]

-------------------------------------------------------------------------------

TOYOTA TECHNOLOGICAL INSTITUTE 
-------------------------------------------------------------------------------
Date: Monday, March 10th, 2003

Time: 2:30 p.m. 

Place: Ryerson Hall 251 

Speaker: Shai Ben-David
CS Department, Technion, Haifa, Israel and School of ECE, Cornell University, NY

Title: Computational Learning Theory –
tradeoffs between Computational Complexity and Statistical Soundness

Abstract: 
 In the past decade machine learning witnessed a fascinating interplay between 
theory and practice. Several ideas that were originally developed by 
theoreticians were translated into popular andsuccessful practical algorithms. 
Furthermore, the experimental success of these algorithms exceeds the most 
optimistic theoretical predictions, thus creating a new challenge for 
theoreticians - to justify the
unexpected success of their own algorithmic ideas. In some cases, further 
research results in even more pessimistic theoretical predictions.
 In this talk I will survey these developments from the point of view of the 
interplay between the two main cost measures of learning; Computational 
complexity and informational complexity.
Here, “informational complexity” refers to questions like “How many training 
examples are required to provide a certain statistical soundness guarantee?” 
And “computational complexity” refers to the computation applied to the 
training data to extract from it the learner’s conclusions.
 I shall discuss some recent insights and research directions concerning three 
of the most common learning paradigms – Neural Networks, Boosting, and Support 
Vector Machines.

*Refreshments will be served after the talk in Ryerson 255* 

If you wish to meet with the speaker, please send e-mail to Meridel Trimble 
mtrimble at uchicago.edu