Just two years after receiving the best paper award at the 15th International Conference on Parallel Problem Solving from Nature (PPSN 2018), PhD student and Vanier Scholar Yasha Pushak and Professor Holger Hoos received another best paper award at the 22nd international Genetic and Evolutionary Computation Conference (GECCO 2020) for a line of research on automated algorithm configuration. Their second paper, titled “Golden Parameter Search: Exploiting Structure to Quickly Configure Parameters in Parallel” was the single winner of the ECOM Track at GECCO 2020, determined by voting of the audience.
Important and challenging computation problems are typically solved through the use of highly parameterized algorithms. Finding high-quality parameter settings for the algorithm can often improve their performance by several orders of magnitude. In the last two decades, automated algorithm configuration has emerged as a hot topic of research.
State of the art algorithm configurators rely on powerful search heuristics to explore the space of parameter configurations; however, they are typically quite costly, often requiring days or even weeks to find high-quality parameter configurations. These methods assume that finding high-quality parameter configurations is challenging. 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 get stuck at a peak that is far from the highest on the mountain. To avoid this, most configurators spend time exploring the entire “landscapes” of the algorithm configuration problem — including regions that don’t initially appear promising, just to be certain they haven’t missed anything.
In their 2018 PPSN award-winning paper, “Algorithm Configuration Landscapes: More Benign than Expected?” 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 the temperature is too high the cake will burn, but if it is too low the cake won’t bake. Therefore, finding the optimal temperature simply corresponds to trading off between “too high” and “too low”. Yasha Pushak and Holger Hoos developed a statistical procedure to test for similar structure in the response of algorithm parameters. They applied their procedure to a large set of parameters and were unable to reject their hypotheses in 99.5% of the cases they studied. Read more about algorithm configuration landscapes here.
Capitalizing on these insights, Yasha Pushak and Holger Hoos developed a new automated algorithm configuration procedure: Golden Parameter Search (GPS). GPS is the first of a new generation of automated algorithm configuration procedures designed to exploit structural properties of algorithm configuration landscapes. In their 2020 GECCO award-winning paper, they showed that GPS was often capable of finding similar-or better-quality parameter configurations using a fraction of the computational budget required by several other long-standing, state-of-the-art algorithm configuration procedures. Read more about GPS here.