PhD student Yasha Pushak and Affiliate Professor Holger Hoos win 2018 PPSN Best Paper Award
Computer Science PhD student Yasha Pushak and Affiliate Professor Holger Hoos won the best paper award at the 15th international conference on Parallel Problem Solving from Nature (PPSN 2018) in Coimbra, Portugal. Their paper, titled "Algorithm Configuration Landscapes: More Benign than Expected?" was one of 8 accepted PPSN 2018 publications nominated for the award, and chosen as the single winner based on a combination of assessment by the program committee and the quality of presentation at the conference, determined by voting of the audience. The award came with 1000 EUR prize money, generously provided by Springer.
Important and challenging computation problems are typically solved through the use of highly parameterized algorithms. These parameters can be set to control the behaviour and performance of the algorithms. In the last two decades, the development of automated algorithm configuration procedures has emerged as a hot topic of research, which can often improve the performance of these algorithms by several orders of magnitude by finding high-quality parameter configurations.
State of the art algorithm configurators rely on powerful search heuristics to explore the space of parameter configurations. These techniques are typically quite costly (often requiring days or even weeks to find high-quality parameter configurations). These configurators are designed with the assumption that finding high-quality parameter configurations is a challenging optimization problem. Consider, for example, the problem of trying to climb to the highest point of a rugged mountain with a large number of peaks in a dense fog: if you always climb up the steepest hill, you will likely find yourself stuck at a peak that is far from the highest on the mountain. To avoid this behaviour, most configurators are designed to spend quite a bit of time exploring the entire "landscapes" of the algorithm configuration problem -- including regions that don't initially appear promising, just to be certain that they haven't missed anything.
Yasha Pushak and Holger Hoos hypothesized that the landscapes induced by algorithm configuration problems are likely much simpler and more structured than previously assumed. By way of analogy, consider the task of choosing a temperature at which to bake a cake: if you set the temperature parameter too high the cake will surely burn, but if you set it too low your cake won't bake. Finding the optimal baking temperature, then, can be viewed as finding the right trade-off between "too high" and "too low", which results in a relatively simple optimization landscape with only one "peak". Yasha Pushak and Holger Hoos believe that this sort of trade-off is likely present for most numerical algorithm parameters, and they developed a statistical procedure to test for this structure. They applied their methodology to a large set of parameters in several commonly studied algorithm configuration scenarios. They found that their statistical tests were unable to reject their hypothesis in 99.5% of the cases they studied.
Yasha Pushak and Holger Hoos believe that the insights gained from their work will lead to ground-breaking advances in the state of the art in algorithm configuration procedures -- that their results can be exploited to develop new configuration procedures that can find high quality parameter configurations using substantially less computational resources than current methods.
Congratulations, Yasha and Holger!