Greybox Algorithm Configuration

1 Introduction

The internal behaviour of many algorithms depends on their parameter settings. Choosing the right parameter values can make the difference between poor and state-of-the-art performance [Hutter et al., 2009]. To select the right values of those parameters and to optimise the algorithm performance on a specific set of problem instances is known as algorithm configuration or hyper-parameter tuning. General-purpose automatic algorithm configurators, such as irace [Birattari et al., 2010; L´opez-Ib´a˜nez et al., 2016], GGA++ [Ans´otegui et al., 2015], SMAC [Hutter et al., 2011], and more recently GPS [Pushak and Hoos, 2020], are widely applied in domains such as Machine Learning (see, e.g., [Kotthoff et al., 2017]) and NP-hard problem solving (see, e.g., [Hutter et al., 2017; Hutter et al., 2010]).

The algorithm configuration problem is defined as follows (see, e.g., [Hoos, 2012]): Given a target algorithm A; a configuration space C containing all valid combinations of parameter values of A; a set of problem instances I; and a performance metric m that measures the performance of a configuration in C of target algorithm A on an instance of I; find c∗ ∈ C that optimises the performance of A on instance set I, according to metric m. Each parameter pj have domain Dj of possible values that can be of different types: categorical, ordinal or numerical. Categorical parameters have an unordered finite set of possible values and are often used to select between several heuristic components or mechanisms. Ordinal parameters have an ordered finite set of possible values. Numerical parameters are real- or integer-valued and often control aspects of an algorithm or heuristic. Parameters can also conditionally depend on each other, meaning that they are active only when another parameter takes a specific value; as a simple example, consider a Boolean parameter that activates a mechanism, whose behaviour is adjusted using a numerical parameter.

Algorithm configurators need to handle two main challenges. First, the time required to evaluate the performance of each configuration can vary from seconds to hours, and it is critical to reduce the number of evaluation for the algorithm. To do so, a possible approach is to rely on an empirical performance model that predicts how well a configuration will perform without running the target algorithm (SMAC and GGA++). Second, the possibility to configure their algorithm afterwards leads programmers to expose more parameters. To handle this large and complex search space, a critical mechanism is the sampling of new configurations to be evaluated. They can be generated based on known good configurations (irace and GGA) or improved according to predictions obtained from a performance model (SMAC and GGA++).

Despite sophisticated approaches, configurators still encounter limitations when the search space grows or the running time is too long. We aim to improve them further and tackle their limitations by exploiting information unused by current configurators.

2 Contribution

To improve current configuration methods, we want to use information already available to them but not yet used or only partially.

2.1 Approach

We look more closely at the target algorithmA, the configuration space C and the instance set I to extract knowledge that can be used by the configurator. In particular, we note the following: current configuration approaches are considering A as a black-box algorithm while in many cases its source code is accessible; the search space C is considered as if all values had equal probabilities to be good and all parameters had the same importance for performance, while this is known to be untrue [Fawcett and Hoos, 2016]; and problem instances from I are considered equally when deciding on which instance to evaluate the target-algorithm, while the time needed to solve them can be predicted thanks to a set a characteristic features to avoid wasteful evaluations.

2.2 Results and OngoingWork

In most cases, C contains a default value for each parameter, which is provided by the developers or based on prior researches, and thus reveals a deeper understanding of the mechanism behind the parameter or extensive testing on relevant problem instances. We exploited this prior knowledge from experts by focusing the sampling around those default values with a truncated normal distribution. We achieved a significant performance improvement over a set of wellstudied configuration scenarios [Anastacio and Hoos, 2020]. We think that the default values are only a small part of the expert knowledge that can be gathered from the users. Hence we are exploring more sophisticated ways of collecting this information and integrating it into the configuration process.

Extracting the information contained in the source-code of A can be done through metrics and features. Those algorithm features further improve empirical performance models such as the ones contained in SMAC or GGA++. A first paper exploring this avenue for Algorithm Selection is currently under review in Artificial Intelligence Journal. Transforming our algorithm features such that they describe a specific set of parameter values is not trivial, but software engineering methods, such as partial program evaluation or code slicing, offer promising possibilities.

The instances contained in I have various running time and often come with instance features that are used for example by SMAC's model to predict how long is needed to solve them. However, when current configurators choose on which instances to evaluate A, they sample them uniformly. We are investigating methods to reduce the time spent on running the algorithm by prioritizing instances that have an expected low running time and high variance between configurations, such that we can easily discriminate between configurations without spending too much time on algorithm evaluations.

3 Conclusion

This research aims at improving current algorithm configurators and is based on the key idea that the different elements given to current configurators contain knowledge that so far remains untapped. Our work on using the knowledge contained in the default-value to bias the search toward a promising area of the configuration space has already led to significant improvements [Anastacio and Hoos, 2020], and we are now exploring possibilities to use source-code features for the algorithm and chose more wisely the instances on which to run the target algorithm.

Based on this research, we will develop a new configurator that leverages this new extracted knowledge. Moreover, existing configurators could implement our methods to improve their own performance.