Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision
(CS 528)

Convexity and prediction problems

Peter Bartlett
Division of Computer Science and Department of Statistics
UC Berkeley Monday, Oct. 20, 2003, 4:15PM
TCSeq 200
http://graphics.stanford.edu/ba-colloquium/

Abstract

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 the performance of these methods.

About the Speaker

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.

Contact: bac-coordinators@cs.stanford.edu

Back to the Colloquium Page