Instance Selection Methods in Automated Algorithm Configuration

Empirical performance evaluation is crucial for algorithm configuration and performance optimization. Prior work showed that comparing the running time of two algorithms can be accelerated by evaluating them on strategically selected instances. We explore this approach in the context of automated algorithm configuration, adapting prior methods to leverage empirical performance models and introducing two active learning-inspired methods. We evaluate these methods on two performance comparison situations arising during configuration, achieving speedups of 5 to 3,000 times over the random instance sampling method of state-of-the-art configurators. We then integrate the best methods into the model-based configurator sequential model-based algorithm configurator (SMAC). In two of five running time optimization scenarios, we nearly double the performance gain of SMAC. An ablation study confirms that instance selection drives this improvement, indicating substantial potential for advancing algorithm configuration.