Oracle inequalities for computationally adaptive model selection

By Alekh Agarwal, Peter L. Bartlett, John C. Duchi. 2012

17 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Control and Systems Engineering, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Control and Systems Engineering

In Management Science and Operations Research

Citations in the corpus

Hyper-Parameter Optimization: A Review of Algorithms and Applications (2020, methodology): “The SHA model was built upon the multi-armed bandit formulation (Agarwal et al., 2012; Sparks et al., 2015).”
Non-stochastic Best Arm Identification and Hyperparameter Optimization (2015, methodology): “We build upon these previous works, and in particular study the multi-armed bandit formulation proposed in [7] and [9], where each arm corresponds to a fixed hyperparameter setting, pulling an arm corresponds to a fixed”
Computational and Statistical Tradeoffs in Learning to Rank (2016, background): “As a solution, recent advances in [7, 23, 8, 1, 16] introduce hierarchies of algorithmic solutions, ordered by the respective computational complexity, for several fundamental machine learning applications.”
Automating model search for large scale machine learning (2015, unknown): “[6] and Jamieson et.”
MLbase: A Distributed Machine-learning System (2013, methodology): “In spite of this, even within statistical machine learning, an understanding of computational techniques for algorithm selection and application is only beginning to appear [7].”
An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization (2020, methodology): “Theoretical Results In this section, we prove that the proposed SS method is asymptotically optimal using the tools from multi-armed bandit (MAB) (Agarwal et al., 2012; Sparks et al., 2015; Jamieson and Talwalkar, 2016).”