Tailoring Algorithms: Better Performance Through the Right Settings

Behind every computer program is a step-by-step guide that tells the computer what to do and when to do it. These guides are called algorithms. Algorithms are like toolboxes filled with instruments designed to solve specific problems. The tools and the order in which they are used to solve a problem successfully are determined by the settings chosen by the user.

As part of the EKAmBa project, we are developing methods for the automated configuration of algorithms. By combining structured search with theoretical approaches, our goal is to create methods that not only find good practical settings for an algorithm but also mathematically guarantee that we’ve found the best possible ones.

Finding the right configuration for an algorithm is like optimizing a race car. To make the car as fast as possible on different tracks, you need to find the right tires, suspension settings, and rear wing position. However, testing all possible combinations of these settings is impractical and expensive. Additionally, these settings interact with each other, so they can’t be considered in isolation.

Our approach automates this process: using something called multi-armed bandits, we leverage past experience from already tested settings to suggest and test new, promising configurations. This way, we gradually move towards the ideal settings while conserving resources like computing power. Multi-armed bandits are a popular method from probability theory that help balance between trying new options and reusing those that have proven to work well. A big advantage of this method is that it can theoretically guarantee that poor settings are tested only rarely.

With the methods we’ve developed, it is possible to tailor a generic algorithm to a specific class of problems. This allows us to optimize both the quality and the time needed to find a solution. Through this configuration process, users can unlock the full potential of an algorithm and ensure optimal performance in specific applications. This enables users to improve both the robustness and performance of their algorithms when faced with new problems.

Additional resources

TBA

Cooperation

Decision and Operation Technologies Group

Prof. Dr. Kevin Tierney

PhD student: Elias Schede

Data Science Group

Prof. Dr. Axel-Cyrille Ngonga Ngomo

PhD student: Jasmin Brandt

Associated with Prof. Dr. Eyke Hüllermeier, LMU München

Project Publications

  • Brandt, Jasmin, Viktor Bengs, Björn Haddenhorst, and Eyke Hüllermeier (2022). ‘‘Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi- bandit Feedback and Finite Budget’’. In: Advances in Neural Information Processing Systems (NeurIPS). url: https://openreview.net/forum?id=h37KyWDDC6B.
  • Brandt, Jasmin, Elias Schede, Björn Haddenhorst, Viktor Bengs, Eyke Hüllermeier, and Kevin Tierney (2023). ‘‘AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration’’. In: Proceedings of the AAAI Con- ference on Artificial Intelligence 37.10, pp. 12355–12363.
  • Brandt, Jasmin, Elias Schede, Shivam Sharma, Viktor Bengs, Eyke Hüllermeier, and Kevin Tierney (2023). ‘‘Contextual Preselection Methods in Pool-based Realtime Algorithm Configuration’’. In: Proceedings of the LWDA 2023 Workshops, Marburg (Germany), Oktober 9-11th, 2023. CEUR Workshop Proceedings. CEUR-WS.org.
  • Brandt, Jasmin, Marcel Wever, Dimitrios Iliadis, Viktor Bengs, and Eyke Hüller- meier (2023). ‘‘Iterative Deepening Hyperband’’. In: CoRR abs/2302.00511. url: https://doi.org/10.48550/arXiv.2302.00511.
  • Haddenhorst, Björn, Viktor Bengs, Jasmin Brandt, and Eyke Hüllermeier (2021). ‘‘Testification of Condorcet Winners in dueling bandits’’. In: Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence (UAI). Vol. 161. Proceedings of Machine Learning Research, pp. 1195–1205.
  • Schede, Elias, Jasmin Brandt, Alexander Tornede, Marcel Wever, Viktor Bengs, Eyke Hüllermeier, and Kevin Tierney (2022). ‘‘A Survey of Methods for Automated Algorithm Configuration’’. In: Journal of Artificial Intelligence Research (JAIR) 75, pp. 425–487.