# On the Impact of the Cutoff Time on the Performance of Algorithm Configurators

arXiv: https://arxiv.org/abs/1904.06230 · HTML: https://mlsanity.com/paper/1904.06230/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2019.

## Built on by (most cited first, 3 of 3)

- [Automated Dynamic Algorithm Configuration](https://mlsanity.com/paper/2205.13881/) (2022)
- [A Survey of Methods for Automated Algorithm Configuration](https://mlsanity.com/paper/2202.01651/) (2022)
- [AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration](https://mlsanity.com/paper/2212.00333/) (2022)

## Abstract (arXiv)

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 RLSk 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 kappa (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 RLSk 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 RLSk for Ridge* for any kappa while ParamRLS-T requires at least quadratic kappa. For OneMax ParamRLS-F identifies k=1 as optimal with linear kappa while ParamRLS-T requires a kappa of at least Omega(nlog n). For smaller kappa ParamRLS-F identifies that k>1 performs better while ParamRLS-T returns k chosen uniformly at random.