Instance Selection Methods in Automated Algorithm Configuration

The European Journal on Artificial Intelligence

Abstract

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.

Authors 3

1. Marie Anastacio corresponding Aachen

   RWTH Aachen University · Leiden University

   Affiliation as printed

   AIM, RWTH Aachen University, Aachen, Germany

   Leiden University

2. Théo Matricon

   Centre National de la Recherche Scientifique · Université de Bordeaux · Laboratoire Bordelais de Recherche en Informatique

   Affiliation as printed

   CNRS, LaBRI, Universtité de Bordeaux, Talence, France

3. Holger H. Hoos Aachen

   RWTH Aachen University · Leiden University · University of British Columbia

   Affiliation as printed

   AIM, RWTH Aachen University, Aachen, Germany

   Department of Computer Science, University of British Columbia (UBC), Vancouver, Canada

   Leiden University