Hydra: Automatically Configuring Algorithms for Portfolio-Based Selection

By Lin Xu, Holger H. Hoos, Kevin Leyton-Brown. 2010

231 citations recorded by the source corpus.

The AI community has achieved great success in designing high-performance algorithms for hard combinatorial problems, given both considerable domain knowledge and considerable effort by human experts. Two influential methods aim to automate this process: automated algorithm configuration and portfolio-based algorithm selection. The former has the advantage of requiring virtually no domain knowledge, but produces only a single solver; the latter exploits per-instance variation, but requires a set of relatively uncorrelated candidate solvers. Here, we introduce Hydra, a novel technique for combining these two methods, thereby realizing the benefits of both. Hydra automatically builds a set of solvers with complementary strengths by iteratively configuring new algorithms. It is primarily intended for use in problem domains for which an adequate set of candidate solvers does not already exist. Nevertheless, we tested Hydra on a widely studied domain, stochastic local search algorithms for SAT, in order to characterize its performance against a well-established and highly competitive baseline. We found that Hydra consistently achieved major improvements over the best existing individual algorithms, and always at least roughly matched — and indeed often exceeded — the performance of the best portfolios of these algorithms.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Industrial and Manufacturing Engineering

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

Citations in the corpus

Improved empirical methods in reinforcement-learning evaluation (2015, background): “, 2002), satisfiability testing (Xu et al., 2010), movie recommendation (Bell et al.”
Auto-Sklearn 2.0: Hands-free AutoML via Meta-Learning (2020, methodology): “The efficient creation of algorithm portfolios is an active area of research with the Greedy Algorithm being a popular choice (Xu et al., 2010, 2011; Seipp et al., 2015; Wistuba et al., 2015b; Lindauer et al., 2017; Feurer et al., 2018; Feurer and Hutter, 2018) due to its simplicity.”
Hydra-MIP : Automated Algorithm Configuration and Selection for Mixed Integer Programming (2011, methodology): “Because a single run of a randomized configuration procedure might not yield a high-performing parameter configuration, it is common practice to perform multiple runs in parallel and to use the configuration that performs best on the training set [12, 14, 28, 13].”
Auto-WEKA: combined selection and hyperparameter optimization of classification algorithms (2012, unknown): “(This idea is conceptually related to the Hydra approach for constructing algorithm selectors [33].”
Automated Algorithm Configuration and Parameter Tuning (2012, methodology): “[70] used FocusedILS in an iterative fashion to obtain sets of configurations of SATenstein-LS that were then used in combination with”
Algorithm runtime prediction: Methods & evaluation (2012, background): “Such predictions can be used to make a per-instance decision about which of a set of given parameter configurations will perform best on a previously unseen test instance, for example in algorithm selection [104,119,116,67].”
Towards Further Automation in AutoML (2018, methodology): “Our base strategy for portfolio building is greedy submodular function minimization (Krause and Golovin, 2014), which has already been successfully applied to combinatorial optimization (Xu et al., 2010, 2011; Seipp et al., 2015).”
Algorithm Selection for Combinatorial Search Problems: A Survey (2012, background): “Automatic tuning and portfolio selection can be treated separately, as done in the Hydra portfolio builder (Xu et al., 2010).”
Auto-WEKA : combined selection and hyperparameter optimization of supervised machine learning algorithms (2014, methodology): “This idea is conceptually related to the Hydra approach for constructing algorithm selectors [Xu et al., 2010].”
Warmstarting of Model-based Algorithm Configuration (2017, methodology): “Secondly, we use an iterative, greedy forward search to select a complementary set of conﬁgurations across all previous instance sets—inspired by the per-instance selection procedure Hydra (Xu, Hoos, and Leyton-Brown 2010).”
Instance-Specific Algorithm Configuration (2014, methodology): “An alternative to regression-based approaches for instance-specific tuning, CPHydra [87] attempts to schedule solvers to maximize the probability of solving an instance within the allotted time.”