From Data to Knowledge - 304 - Alekh Agarwal
Channel: ckleinastro
Date: 2012-05-09

Slides: http://lyra.berkeley.edu/CDIConf/pdfs/AgarwalBerkeleyStreamingTalk.pdf

Alekh Agarwal: "Oracle inequalities for large scale model selection". A video from the UC Berkeley Conference: From Data to Knowledge: Machine-Learning with Real-time and Streaming Applications (May 7-11, 2012).

Abstract
Alekh Agarwal (UC Berkeley, EECS)
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 Peter Bartlett, John Duchi and Clement Levrard.