  We analyze general model selection procedures using penalized empirical loss
minimization under computational constraints. While classical model selection
approaches do not consider computational aspects of performing model selection,
we argue that any practical model selection procedure must not only trade off
estimation and approximation error, but also the computational effort required
to compute empirical minimizers for different function classes. We provide a
framework for analyzing such problems, and we give algorithms for model
selection under a computational budget. These algorithms satisfy oracle
inequalities that show that the risk of the selected model is not much worse
than if we had devoted all of our omputational budget to the optimal function
class.
