Thursday, October 1, 2009
04:30 PM in MATH 175
Professor S V N Vishwanathan
Department of Statistics, Purdue University

Boosting from an Optimization Perspective Upper and Lower Bounds

Abstract

Boosting has become a well known ensemble method. The algorithm maintains a distribution on the binary labeled examples and a new base learner is added in a greedy fashion. The goal is to obtain a small linear combination of base learners that clearly separates the examples.

We focus on a recent view of Boosting where the update algorithm for distribution on the examples is characterized by a minimization problem that uses a relative entropy as a regularization. In particular, we concentrate on algorithms that provably maximize the soft margin when the data is noisy.

By borrowing results from optimization we show how one can prove upper and lower bounds on the number of iterations needed by these modern algorithms. We will also show how to solve large scale problems based on state of the art optimization techniques.

Joint work with Manfred K Warmuth.

Refreshments will be served at 4:00 PM in HAAS 111.