AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration
Authors: Jasmin Brandt, Elias Schede, Björn Haddenhorst, Viktor Bengs, Eyke Hüllermeier, Kevin Tierney
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We examine AC-Band on several standard datasets for evaluating theoretical approaches for AC. We note that while these datasets refer exclusively to runtimes, AC-Band is applicable to other target metrics (see Section Problem Formulation). In our experiments, we address the following two research questions: Q1: Is AC-Band able to find high quality configurations in less CPU time than state-of-the-art AC methods with guarantees? Q2: How does AC-Band scale with k? |
| Researcher Affiliation | Academia | 1Department of Computer Science, Paderborn University, Germany 2Decision and Operation Technologies Group, Bielefeld University, Germany 3Institute of Informatics, LMU Munich, Germany 4Munich Center for Machine Learning (MCML), Germany |
| Pseudocode | Yes | Algorithm 1: Combinatorial Successive Elimination (CSE) Algorithm 2: Arm Elimination( Θ , b, l, I ) Algorithm 3: AC-Band |
| Open Source Code | Yes | Code: https://github.com/DOTBielefeld/ACBand |
| Open Datasets | Yes | We use one SAT and two MIP datasets that have been used before to assess theoretical works on AC (Weisz et al. 2020). ... The SAT dataset contains precomputed runtimes of configurations of the Mini Sat SAT solver (E en and S orensson 2003) obtained by solving instances that are generated using CNFuzz DD (Weisz, Gy orgy, and Szepesv ari 2018). ... The MIP datasets curated by Weisz et al. (2020) are generated using an Empirical Performance Model (EPM)(Hutter et al. 2014). |
| Dataset Splits | No | In addition, we use the average runtime over instances as the validation loss and consequently return the configuration with smallest average runtime. (While "validation loss" is mentioned, no specific dataset split percentages or counts for training, validation, and testing are provided in the paper.) |
| Hardware Specification | No | In our case, the k configurations in a subset of CSE can be evaluated in parallel for an instance given that k CPUs are available. (No specific hardware models or detailed specifications are provided.) |
| Software Dependencies | Yes | In particular, the EPM is trained on the CPLEX solver (IBM 2020). The citation (IBM 2020) refers to 'ILOG CPLEX Optimization Studio 20.1.0: User s Manual.' |
| Experiment Setup | Yes | Due to space constraints, we only show results for two datasets for δ = 0.05 since this setting has also been used in previous work (Weisz et al. 2020). ... With a small value of k, AC-Band lies on the Pareto front... In particular, with k = 2 AC-Band is 72% percent faster... (Figure 2 also shows specific values for alpha such as "α = 0.01", "α = 0.001"). |