Cornell Department of Computer Science Colloquium
4:15pm, September 20, 2001
B17 Upson Hall

Computational Learning Theory and the Tradeoff Between the Computational Complexity and Statistical Soundness

Shai Ben David
Cornell University, Technion-Israeli Institute of Technology

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 and successful practical algorithms. Furthermore, the experimental success of these algorithms exceeded the most optimistic theoretical predictions.

A new challenge for theoreticians emerged - how 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 apparent tradeoff between the two main cost-measures of learning; Computational complexity and information complexity. I shall discuss some recent insights and research directions concerning two of the most common learning paradigms- Boosting and Support Vector Machines.

The talk is intended to serve as an 'introduction to current trends in computational learning theory' and will assume no prior knowledge of the topic.

host: Charles Van Loan