The Racing Algorithm: Model Selection for Lazy Learners

By Oded Maron, Andrew W. Moore. 1997

How researchers see this paper

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

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, background): “, Snoek et al. (2015a) and Springenberg et al. (2016) proposed using Bayesian neural networks, which scale linearly with n, to model the posterior. Adaptive conguration evaluation is not a new idea. Maron and Moore (1997) and Mnih and Audibert (2008) considered a setting where the training time is r”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, methodology): “This idea was later used for example by Jennison et al. (1982); Maron and Moore (1997) or by Even-Dar et al. (2006) in the context of bounded bandit models, in which each arm ν a is a probability distribution on [0 , 1]. m best arm identiﬁcation with m > 1 was considered for example by…”
Cross-disciplinary perspectives on meta-learning for algorithm selection (2009, methodology): “This study relates more to the growing body of work on dynamic algorithm selection [Armstrong et al. 2006; Streeter et al. 2007] and tuning of parameters via racing algorithms [Maron and Moore 1997] than to the focus of this article on the more static algorithm selection problem.”
Parameter tuning for configuring and analyzing evolutionary algorithms (2011, methodology): “Well-known examples in this category are ANOVA [34] and racing [35].”
Comparing parameter tuning methods for evolutionary algorithms (2009, methodology): “Nannen and Eiben have introduced a method for Relevance Estimation and Value Calibration of parameters (REVAC) in [16], [15].”
Fast cross-validation via sequential testing (2012, background): “Maron and Moore (1994, 1997) introduce the so-called Hoeffding Races which are based on the nonparametric Hoeffding bound for the mean of the test error.”
A Survey of Automatic Parameter Tuning Methods for Metaheuristics (2020, methodology): “F -Race, which is inspired from the algorithm Hoeffding race [49], [50] in machine learning for model selection, was proposed in [45] and comprehensively studied in [31].”
A review and comparison of strategies for multi-step ahead time series forecasting based on the NN5 forecasting competition (2011, methodology): “In the Algorithm 1, we presented the winner-take-all approach (noted WINNER) (Maron and Moore, 1997) which consists of comparing the set of models y q and selecting the best one in terms of testing error e LOO ( k ) (see line 7).”
Automatically improving the anytime behaviour of optimisation algorithms (2014, methodology): “F-Race [12] is a racing procedure [46] for the selection of the best among a given set of algorithm configurations, by means of the non-parametric Friedman’s two-way analysis of variance by ranks, and its associated post-hoc test [16].”
Preference-based Evolutionary Direct Policy Search (2013, methodology): “The racing framework is an uncertainty handling scheme introduced in [9], [10].”
The irace package: Iterated racing for automatic algorithm configuration (2016, methodology): “Birattari et al. [19,20] proposed an automatic conﬁguration approach, F-Race, based on racing [64] and Friedman’s non-parametric two-way analysis of variance by ranks.”
Empirical Bernstein stopping (2008, methodology): “Following the procedure of Maron and Moore (1997), we evaluated the Hoeﬀding and empirical Bernstein races on the task of selecting the best k for k -nearest neighbor regression and classiﬁcation through leave-one-out cross-validation.”
Neuroevolutionary reinforcement learning for generalized control of simulated helicopters (2011, methodology): “For this work, we adapt a strategy recently proposed by Heidrich-Meisner and Igel [32] that uses selection races , a technique originally developed by Maron and Moore [50], to determine how many episodes to spend evaluating each policy.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, background): “In principle, these learning problems are very similar to the value-based racing task (Maron and W., 1994; Maron and Moore, 1997), where the goal is to select the k arms with the highest means.”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, background): “In principle, these learning problems are very similar to the value-based racing task [38, 39], where the goal is to select the k arms with the highest means.”
Scalable Gaussian process-based transfer surrogates for hyperparameter optimization (2017, background): “The Racing Algorithm by Maron [40] follows a similar principle but is focused on lazy learners where the expensive part is testing rather than training.”
Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm (2014, methodology): “The Hoeﬀding race (HR) algorithm [21, 22] is an adaptive sampling method that makes use of the Hoeﬀding bound to construct conﬁdence intervals for the empirical mean estimates of the options.”