Spring 2012 Seminar Series

DATE: March 15th
LOCATION: E51-335
TIME: 4:15pm
Reception immediately following in the ORC Conference Room (E40-106)

SPEAKER:
Peter Bartlett

TITLE
Oracle inequalities for large scale model selection

ABSTRACT
In many large-scale, high-dimensional prediction problems, performance is limited by computational resources rather than sample size. In this setting, we consider the problem of model selection under computational constraints: given a particular computational budget, is it better to gather more data and estimate a simpler model, or gather less data and estimate a more complex model? We introduce general procedures for model selection under computational constraints. In contrast to classical oracle inequalities, which show that a model selection scheme gives a near-optimal trade-off between approximation error and estimation error for a given sample size, we give computational oracle inequalities, which show that our methods give a near-optimal trade-off for a given amount of computation, that is, devoting all of our computational budget to the best model would not have led to a significant performance improvement.

 

Joint work with Alekh Agarwal, John Duchi and Clement Levrard.