Greedy Restart Schedules: A Baseline for Dynamic Algorithm Selection on Numerical Black-box Optimization Problems

Lennart Schäpermeier · 2025

Read Greedy Restart Schedules: A Baseline for Dynamic Algorithm Selection on Numerical Black-box Optimization Problems by Lennart Schäpermeier (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-11440.txt.

Introduction

Lennart Schäpermeier, a solo author, sets a simple baseline for solver scheduling in a 2025 paper. On hard numerical problems, different solvers win on different instances, and meta-methods try to pick the best moment by moment. Champion solvers are often hand-built hybrids that restart fast local searches many times. His greedy schedule repeatedly picks whichever solver is doing best on the still-unsolved training problems.

The result is a fixed, problem-independent timetable. On a standard testbed it closed much of the gap between the best single solver and the ideal per-instance choice. He offers it as the baseline any fancier dynamic selector must beat.

Catalog record

CREATORLennart Schäpermeier
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-11440

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Greedy Restart Schedules: A Baseline for Dynamic Algorithm Selection on Numerical Black-box Optimization Problems Lennart Schäpermeier Abstract . In many optimization domains, there are multiple different solvers that contribute to the overall state-of-the-art, each performing better on some, and worse on other types of problem instances. Meta-algorithmic approaches, such as instance-based algorithm selection, configuration and scheduling, aim to close this gap by extracting the most performance possible from a set of (configurable) optimizers. In this context, the best performing individual algorithms are often hand-crafted hybrid heuristics which perform many restarts of fast local optimization approaches. However, data-driven techniques to create optimized restart schedules have not yet been extensively studied. Here, we present a simple scheduling approach that iteratively selects the algorithm performing best on the distribution of unsolved training problems at time of selection, resulting in a problem-independent solver schedule. We demonstrate our approach using well-known optimizers from numerical black-box optimization on the BBOB testbed, bridging much of the gap between single and virtual best solver from the original portfolio across various evaluation protocols. Our greedy restart schedule presents a powerful baseline for more complex dynamic algorithm selection models. Conference: Genetic and Evolutionary Computation Conference; July 14–18, 2025; Malaga, Spain Genetic and Evolutionary Computation Conference (GECCO ’25), July 14–18, 2025, Malaga, Spain DOI: 10.1145/3712256.3726408 ISBN: 979-8-4007-1465-8/2025/07 CCS: Mathematics of computing Continuous optimization CCS: Computing methodologies Randomized search CCS: Theory of computation Scheduling algorithms † † cc-license: by 1. Introduction In heuristic optimization, two different streams of research are constantly at odds with each other: One tries to select, design and configure an algorithm for optimal performance on a specific set of problems, while the other seeks to achieve the best generalist performance for the broadest class of problems. That both goals cannot be met simultaneously is famously summarized in no-free-lunch theorems which state that there cannot be one universally best optimizer - to improve in one subset of problems, there is a sacrifice of performance in another area ( Wolpert and Macready, 1997 ) . In the necessary trade-off, a generalist algorithm will always perform somewhat worse than each specialist algorithm in its designated area of expertise. To close this performance gap, many different methodologies have been developed by different research communities. Automated algorithm selection (AAS) , for example, tries to automate the role of a domain expert with a machine learning model that selects an algorithm for the problem instance at hand ( Xu et al., 2008 ; Kerschke et al., 2019 ) . The AAS model is trained to predict the runtimes of a set of performance-complementary algorithms on the basis of cheap-to-compute numerical instance features, the most promising one being selected to run on the actual optimization problem. Ideally, this model can efficiently select the best algorithm, only incurring additional costs in the feature computation and a forward pass of the model. In practice, however, AAS models are costly to train, can often only bridge a small part of the specialist-generalist gap, and suffer from generalization issues when extending beyond their designated training set of instances ( Kerschke and Trautmann, 2019a ; Dietrich et al., 2024 ; Cenikj et al., 2024 ) . An earlier methodological development was the adoption of principled scheduling and restarting techniques that incorporate changing population sizes (e.g., IPOP-CMA-ES ( Auger and Hansen, 2005b ) and BIPOP-CMA-ES ( Hansen, 2009 ) ), or specialized pre-solvers that quickly solve certain problem classes (e.g., HCMA ( Loshchilov et al., 2013 ) and pre-solvers in SATzilla ( Xu et al., 2008 ) ). While giving good and robust off-the-shelf performance, these techniques need to be hand-designed for each optimization domain or require deterministic runtimes, and it is unclear how much performance they leave on the table. More recently, dynamic algorithm selection (DAS) , a research direction that tries to combine the more robust scheduling approaches with the more ambitious AAS models, has emerged ( Vermetten et al., 2020 ; Schröder et al., 2022 ; Vermetten et al., 2023 ) . Instead of computing instance features up-front, a DAS model may start with a default algorithm and use the intermediate solution trajectory for feature computation, determining on-the-fly if a switch to another algorithm (and possibly warmstarting the new algorithm) would be beneficial. DAS was shown to have a promising performance potential ( Vermetten et al., 2020 ) , but its training is even more involved than AAS models, as the solution trajectory of every involved optimizer influences the further optimization procedure differently. In this paper, we explore a path between a hand-designed restarting strategy and the complications of training a robust DAS model. In particular, we introduce a data-driven restart scheduling technique: Data from an extensive benchmark run is used to derive a model-free static solver schedule. To the author’s best knowledge, there exists little literature on this scenario, i.e., scheduling heuristic optimizers with varying running times and only probabilistic success. The method introduced in this report, called greedy restart schedule (GRS), should be considered as a baseline for any algorithm scheduler in this setting. As a test case, we consider multiple CMA-ES configurations with different population sizes inspired by IPOP-CMA-ES and a selection of other local search approaches, to solve numerical black-box optimization problems. The paper is structured as follows: We begin by discussing some methodological background from numerical black-box optimization to meta-algorithmic approaches in Section 2 . Then, we dive into a schematic example and the proposed greedy restart schedule in Section 3 . Our method is then demonstrated in an experimental study across Sections 4 and 5 . Finally, we draw conclusions in Section 6 . 2. Background In this section, we introduce numerical black-box optimization and common solvers in this domain, as well as a short overview of meta-algorithmic approaches, namely feature-based problem characterization, algorithm selection and scheduling, and performance measures employed in the design and evaluation of the meta-algorithmic models. 2.1. Numerical Black-box Optimization In numerical black-box optimization (BBO), the goal is to minimize (w.l.o.g.) f:\mathcal{X}\mapsto\mathbb{R} , a function that accepts a vector of n numerical parameters x\in\mathcal{X}\subseteq\mathbb{R}^{n} and returns the objective value of the queried point. No other assumptions about properties of f can be made, such as convexity, unimodality, smoothness, analytical formulation, derivatives, etc. Numerical BBO problems can be found in application domains such as hyperparameter optimization ( Loshchilov and Hutter, 2016 ; Schneider et al., 2022 ) or engineering problems ( Long et al., 2022 ) . As practical problems often have long evaluation times, unknown properties and proprietary problem definitions, testbeds including test problems with known optima f^{*} and problem properties are used to benchmark candidate optimizers, comparing their suitability on a broad range of numerical BBO problems. The most established of these testbeds is the black-box optimization benchmark (BBOB) ( Hansen et al., 2021 ) , which includes 24 functions ( fid s) with countless problem instances ( iid s) per fid to be used for repetitions, as well as an established evaluation protocol. The BBOB uses a fixed-target evaluation scheme, where the hitting times in terms of function evaluations for different target values f^{*}+\tau are recorded, and subsequently presented in runtime profiles , which are empirical cumulative distribution functions (ECDFs) of solved targets per function evaluation

Read the complete text