On the Impact of the Cutoff Time on the Performance of Algorithm Configurators
This work addresses a specific bottleneck in automated algorithm configuration for theoretical optimization problems, providing rigorous bounds but is incremental in scope.
The paper investigates how cutoff time affects algorithm configurators, specifically ParamRLS-F and ParamRLS-T, for tuning parameters of RLS_k on Ridge* and OneMax functions, proving that ParamRLS-F requires linear cutoff times for efficient tuning while ParamRLS-T needs at least quadratic or Ω(n log n) times.
Algorithm configurators are automated methods to optimise the parameters of an algorithm for a class of problems. We evaluate the performance of a simple random local search configurator (ParamRLS) for tuning the neighbourhood size $k$ of the RLS$_k$ algorithm. We measure performance as the expected number of configuration evaluations required to identify the optimal value for the parameter. We analyse the impact of the cutoff time $κ$ (the time spent evaluating a configuration for a problem instance) on the expected number of configuration evaluations required to find the optimal parameter value, where we compare configurations using either best found fitness values (ParamRLS-F) or optimisation times (ParamRLS-T). We consider tuning RLS$_k$ for a variant of the Ridge function class (Ridge*), where the performance of each parameter value does not change during the run, and for the OneMax function class, where longer runs favour smaller $k$. We rigorously prove that ParamRLS-F efficiently tunes RLS$_k$ for Ridge* for any $κ$ while ParamRLS-T requires at least quadratic $κ$. For OneMax ParamRLS-F identifies $k=1$ as optimal with linear $κ$ while ParamRLS-T requires a $κ$ of at least $Ω(n\log n)$. For smaller $κ$ ParamRLS-F identifies that $k>1$ performs better while ParamRLS-T returns $k$ chosen uniformly at random.