Fast Perturbative Algorithm Configurators
This work addresses the efficiency of algorithm configuration, a key issue in automated machine learning and optimization, though it is incremental as it builds on existing configurators like ParamRLS and ParamILS.
The paper tackles the problem of tuning algorithm parameters efficiently, proving a linear lower bound for existing configurators and proposing a harmonic mutation operator that achieves polylogarithmic time for single-parameter tuning in unimodal or approximately unimodal spaces, with experiments showing practical superiority.
Recent work has shown that the ParamRLS and ParamILS algorithm configurators can tune some simple randomised search heuristics for standard benchmark functions in linear expected time in the size of the parameter space. In this paper we prove a linear lower bound on the expected time to optimise any parameter tuning problem for ParamRLS, ParamILS as well as for larger classes of algorithm configurators. We propose a harmonic mutation operator for perturbative algorithm configurators that provably tunes single-parameter algorithms in polylogarithmic time for unimodal and approximately unimodal (i.e., non-smooth, rugged with an underlying gradient towards the optimum) parameter spaces. It is suitable as a general-purpose operator since even on worst-case (e.g., deceptive) landscapes it is only by at most a logarithmic factor slower than the default ones used by ParamRLS and ParamILS. An experimental analysis confirms the superiority of the approach in practice for a number of configuration scenarios, including ones involving more than one parameter.