EECS Joint Colloquium Distinguished Lecture Series

Wednesday, September 17, 2003
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.

Professor Peter Bartlett

Depts. of EECS and Statistics,
University of California, Berkeley


The Role of Convexity in Prediction Problems




In pattern classification and other prediction problems, two families of algorithms have been successfully applied in a broad variety of areas: kernel methods and boosting algorithms. Both approaches optimize a convex criterion on a convex function space. In addition to its computational advantages, convexity has statistical advantages. This talk will review boosting and kernel methods, and present error bounds for these methods, in terms of a measure of complexity of the function class called the Rademacher averages. In particular, we show that convexity leads to a better estimation rate, the rate at which the error approaches its optimal value. In pattern classification, the natural loss function is the indicator function for a misclassification, which is not convex. Kernel and boosting methods for pattern classification substitute a convex function for the discrete loss function. We show how this substitution affects performance, and characterize the class of convex surrogates which allow asymptotically optimal performance.


Peter Bartlett is a professor in the Division of Computer Science and Department of Statistics at the University of California at Berkeley. He is the co-author, with Martin Anthony, of the book Learning in Neural Networks: Theoretical Foundations. He has served as an associate editor of the journals Machine Learning, Mathematics of Control Signals and Systems, the Journal of Machine Learning Research, and the Journal of Artificial Intelligence Research. In 2001, he was awarded the Malcolm McIntosh Prize for Physical Scientist of the Year in Australia, for his work in statistical learning theory. He was a fellow, senior fellow and professor in the Australian National University's Institute for Advanced Studies (1993-2003), and Miller Institute Visiting Research Professor in Statistics and Computer Science at U.C. Berkeley in Fall 2001. His research interests include machine learning, statistical learning theory, and adaptive control.