Selecting Near-Optimal Learners via Incremental Data Allocation

By Ashish Sabharwal, Horst Samulowitz, G. Tesauro. 2015

66 citations recorded by the source corpus.

We study a novel machine learning (ML) problem setting of sequentially allocating small subsets of training data amongst a large set of classifiers. The goal is to select a classifier that will give near-optimal accuracy when trained on all data, while also minimizing the cost of misallocated samples. This is motivated by large modern datasets and ML toolkits with many combinations of learning algorithms and hyper-parameters. Inspired by the principle of "optimism under uncertainty," we propose an innovative strategy, Data Allocation using Upper Bounds (DAUB), which robustly achieves these objectives across a variety of real-world datasets. We further develop substantial theoretical support for DAUB in an idealized setting where the expected accuracy of a classifier trained on $n$ samples can be known exactly. Under these conditions we establish a rigorous sub-linear bound on the regret of the approach (in terms of misallocated data), as well as a rigorous bound on suboptimality of the selected classifier. Our accuracy estimates using real-world datasets only entail mild violations of the theoretical scenario, suggesting that the practical behavior of DAUB is likely to approach the idealized behavior.

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

Citations in the corpus

A Survey on Neural Architecture Search (2019, methodology): “Other similar paradigms include searching on a subset of the data (Sabharwal et al., 2016) and searching on a down-scaled version of the data (Hinz et al.”
DeepArchitect: Automatically Designing and Training Deep Architectures (2017, background): “There has been a wide variety of theoretical and empirical research in this area [2, 4, 5, 21], including Bayesian optimization methods [12, 14, 24].”
Population Based Training of Neural Networks (2017, methodology): “For this reason, a number of methods look to speed up the updating of the posterior with information from each optimisation process by performing early stopping, using intermediate losses to predict final performance, and even modelling the entire time and data dependent optimisation process in orde”
Multi-fidelity Bayesian Optimisation with Continuous Approximations (2017, background): “Recent work has studied multi-ﬁdelity meth-ods for speciﬁc problems such as hyper-parameter tuning, active learning and reinforcement learning (Agarwal et al., 2011; Cutler et al., 2014; Li et al., 2016; Sabharwal et al., 2015; Zhang & Chaudhuri, 2015).”
A System for Massively Parallel Hyperparameter Tuning (2018, methodology): “Previous methods like Gy¨orgy & Kocsis (2011); Agarwal et al. (2011); Sabharwal et al. (2016) provide theoretical guarantees under strong assumptions on the convergence behavior of intermediate losses.”
Multi-fidelity Gaussian Process Bandit Optimisation (2016, background): “Sabharwal et al. (2015) present a UCB based idea for tuning hyper-parameters with incremental data allocation.”
Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations (2016, background): “Some literature have analysed multi-ﬁdelity methods in speciﬁc contexts such as hyper-parameter tuning, active learning and reinforcement learning [1, 5, 26, 33].”
Hyperband: Bandit-Based Configuration Evaluation for Hyperparameter Optimization (2016, methodology): “Several works propose methods that make strong assumptions on the convergence behavior of training algorithms, providing theoretical performance guarantees under these assumptions (Gy¨orgy & Kocsis, 2011; Agarwal et al., 2011; Swersky et al., 2013; 2014; Domhan et al., 2015; Sabharwal et al., 2016).”
Multi-Fidelity Black-Box Optimization with Hierarchical Partitions (2018, background): “…(Agarwal et al., 2011; Forrester et al., 2007; Huang et al., 2006a; Klein et al., 2016; Lam et al., 2015; Li et al., 2016; Poloczek et al., 2016; Sabharwal et al., 2015; Zhang & Chaudhuri, 2015), with those that are not applicationspecific focusing on a Bayesian framework without formal…”
A review of automatic selection methods for machine learning algorithms and hyper-parameter values (2016, methodology): “2001) [sometimes each with a predetermined set of combinations of hyper-parameter values (Hoffman et al. 2014; Sabharwal et al. 2016)] or hyperparameter values (Wang et al.”