A Framework for the Runtime Analysis of Algorithm Configurators

Despite the widespread usage of algorithm configurators to tune algorithmic parameters, there is still little theoretical understanding of their performance. In this thesis, we build a theoretical foundation for the field of algorithm configuration to enable the derivation of specific statements regarding the performance of algorithm configurators. We use the devised framework to prove tight bounds on the time required by specific configurators to identify the optimal parameter values of randomised local search and simple evolutionary algorithms for standard benchmark function classes. Our framework allows us to derive insights regarding the impact of the parameters of algorithm configurators, in particular the cutoff time and performance metric used to compare configurations, as well as to characterise parameter landscapes. In the general case, we present necessary lower bounds and sufficient upper bounds on the cutoff time if the time taken to reach a specific target fitness value is used as the performance metric. For specific simple algorithm configuration scenarios, we show that our general lower bounds are tight and that the same optimal parameter values can be identified using smaller cutoff times if the performance metric is instead taken to be the fitness value obtained within the available time budget, which also reduces the required amount of problem-specific information. Our insights enable the design of mutation operators that are provably asymptotically faster for unimodal and approximately unimodal parameter landscapes and slower by only a logarithmic factor in the worst case. In addition to our contributions to the theory of algorithm configuration, the mathematical techniques derived in this thesis represent a substantial improvement over the state-of-the-art in the field of fixed-budget analysis.