Dagstuhl-Seminar 23332
Synergizing Theory and Practice of Automated Algorithm Design for Optimization
( 13. Aug – 18. Aug, 2023 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/23332
Organisatoren
- Martin S. Krejca (Ecole Polytechnique - Palaiseau, FR)
- Marius Lindauer (Leibniz Universität Hannover, DE)
- Manuel López-Ibáñez (University of Manchester, GB)
- Katherine M. Malan (UNISA - Pretoria, ZA)
Kontakt
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Simone Schilke (für administrative Fragen)
Automated algorithm design (AAD) is a prevalent and highly important domain, as design-dependent algorithms are used in a plethora of very different areas. Determining which algorithms and/or their parameters to choose for each given problem is a task that is infeasible to solve in this magnitude solely by humans. Computers can greatly assist in this process in a multitude of ways. Consequently, many different branches of AAD exist. This Dagstuhl Seminar brought together a diverse set of researchers from the AAD domain as well as closely related domains, from all over the world. The aim of the seminar was to provide a common platform to exchange ideas about all of the different established AAD techniques and theories, how to advance the field of AAD, and how to join forces. Most prominently, the seminar aimed at a strong exchange between researchers who work empirically and those who work theoretically. We believe that this seminar was a great success, reaching all of the intended goals.
Due to the diverse backgrounds of the participants, the seminar started with elaborate introduction rounds followed by two overview talks - one detailing the theoretical perspective of AAD, given by Carola Doerr, the other one the empirical perspective, given by Katherine M. Malan. From then on, the seminar consisted of a mix of breakout sessions and short, inspiring talks as participants felt the need to share their experiences or ideas based on the discussions. Immediately from day one, interesting breakout sessions emerged, some of which had multiple iterations, due to the interest of the participants and due to the scope of the subject. In the morning of each day, we made sure to provide a summary of all breakout sessions of the previous day in order to update everyone and to discuss what other topics could be further explored.
Topics that came up on day one were discussions about the terminology and about benchmarks, which had multiple sessions throughout the week. Both of these topics are very important when aiming to unite the community and especially when trying to bridge the gap between theory and practice. The sessions about terminology showed that different communities use different terms for similar concepts and, perhaps more worrying, terminology is not used consistently across communities, making communicating results between different areas harder. Potential solutions include to provide a freely accessible overview of the different terms and define them well, or to use whatever terminology feels appropriate for each article but specify the terms very well in the article. The sessions about benchmarks highlighted that more diverse sets of benchmark functions are desired and that it is not straightforward to transfer the existing benchmarks into a setting that is well suited for theoretical investigations. The latter point sparked other interesting discussions, summarized in the full report.
An inspiring talk was given by Kevin Leyton-Brown, who proposed that optimization should be guided based on users' utilities rather than on expected runtime of the algorithms. This led to an interesting breakout group in which various useful utility functions were discussed which could be used for realistic AAD scenarios. Another very interesting breakout group was inspired by Benjamin Doerr, who was looking for the easiest possible AAD scenario to study theoretically. In a fruitful exchange, a scenario was constructed that seemed interesting and approachable from a theoretical point and also useful from a practical point of view. The discussion emerging from this group delved into an open question that was discussed throughout the seminar, namely, what are the characteristics that make AAD scenarios a special case of the more general field of black-box optimization.
Besides these success stories, further talks led to potential collaborations and new ideas. One example was the talk by Johannes Lengler, in which he proposed how existing theoretical results for randomized optimization heuristics could be potentially interpreted as results for AAD. The ensuing discussion was about to what extent such generalizations make sense, with no clear consensus being reached so far. Nonetheless, the talk and the following in-depth discussion showed that there is significant work to be done on this topic.
The seminar also gave members who are not part of the core AAD community the opportunity to present their work and to integrate into the community. This was met with very positive feedback. Overall, we thank all of the participants for the great discussions, valuable talks, and the support, all of which made this seminar a great success. In addition, we thank the Dagstuhl staff, who supported us incredibly well and helped us run this seminar as smoothly as it did.
Creative Commons BY 4.0
Martin S. Krejca, Marius Lindauer, Manuel López-Ibáñez, and Katherine M. Malan
The design of optimization algorithms for tackling real-world problems often requires making tens to hundreds of design decisions that are reflected in the choice of algorithmic components and their hyperparameter values. Due to being a complex, tedious, error-prone, and time-consuming task, there has been major research efforts in the last decade towards developing automatic methods for algorithm design, including algorithm configuration, algorithm selection, and automated machine learning. The general problem of automated algorithm design (AAD) can be formulated as a meta-optimization problem that is mixed-variable, black-box, and stochastic, which requires the use of meta-heuristics.
Despite its relevance, AAD is not sufficiently well understood from a mathematical and theoretical point of view. However, in recent years, theoretical analyses, especially runtime guarantees, have made major contributions to relevant AAD subproblems. The next step is to advance this initial research to the more general problem of AAD. To this end, it has proven useful in the past to support theoretical analyses by empirical research, for example, by searching for optimal parameter values that are unproven yet, or by providing evidence for conjectures regarding the relationship between parameters, problem features, and algorithm performance. So far, this effort has led to a handful of publications that aim to bridge the gap between theory and practice, even including a PhD thesis and one paper winning a best-paper award at GECCO 2022. Still, the potential of such collaborations is exploited quite rarely.
This Dagstuhl Seminar aims at gaining more fundamental insights into AAD by combining theoretical and empirical research and at initiating collaborations between these two areas. To this end, we want to bring together researchers working on the theory of meta-heuristics or on empirical methods and applications of AAD, providing them with the opportunity to improve the mutual understanding between the two fields and to develop ideas about how theory and practice can help each other derive mutually useful results. The participants will work together to tackle various problems in the intersection of both domains, such as: What are the key differences between AAD and other optimization scenarios? What properties of current AAD approaches should come with mathematical guarantees? What characteristics of empirical benchmarks should carry over to benchmarks used for theoretical analysis? How can the empirical toolbox be made more appealing for theoretical research such that it can help uncover unproven, yet interesting hypotheses? How can a unified and consistent language between researchers focusing on theory or empirical results be established? We envision a dynamic seminar where questions and insights arise organically from dynamic discussion groups. This seminar will give participants the chance to meet new people and start new collaborations as well as to shape the future direction of the intersection of theory and practice for AAD.
Martin S. Krejca, Marius Lindauer, Manuel López-Ibáñez, and Katherine M. Malan
- Thomas Bäck (Leiden University, NL) [dblp]
- Bernd Bischl (LMU München, DE) [dblp]
- Chris Cameron (University of British Columbia - Vancouver, CA) [dblp]
- Nguyen Dang (University of St Andrews, GB) [dblp]
- Benjamin Doerr (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Carola Doerr (Sorbonne University - Paris, FR) [dblp]
- Tome Eftimov (Jozef Stefan Institute - Ljubljana, SI) [dblp]
- Marcus Gallagher (The University of Queensland - Brisbane, AU) [dblp]
- Nikolaus Hansen (INRIA Saclay - Palaiseau, FR) [dblp]
- Pascal Kerschke (TU Dresden, DE) [dblp]
- Lars Kotthoff (University of Wyoming - Laramie, US) [dblp]
- Martin S. Krejca (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Johannes Lengler (ETH Zürich, CH) [dblp]
- Kevin Leyton-Brown (University of British Columbia - Vancouver, CA) [dblp]
- Marius Lindauer (Leibniz Universität Hannover, DE) [dblp]
- Shengcai Liu (A*STAR - Singapore, SG)
- Manuel López-Ibáñez (University of Manchester, GB) [dblp]
- Katherine M. Malan (UNISA - Pretoria, ZA) [dblp]
- Mario Andrés Muñoz (The University of Melbourne, AU) [dblp]
- Nelishia Pillay (University of Pretoria, ZA) [dblp]
- Shinichi Shirakawa (Yokohama National University, JP) [dblp]
- Thomas Stützle (Free University of Brussels, BE) [dblp]
- Niki van Stein (Leiden University, NL) [dblp]
- Diederick Vermetten (Leiden University, NL) [dblp]
- Marcel Wever (LMU München, DE) [dblp]
- Carsten Witt (Technical University of Denmark - Lyngby, DK) [dblp]
Klassifikation
- Machine Learning
- Neural and Evolutionary Computing
Schlagworte
- automated algorithm design
- hyper-parameter tuning
- parameter control
- heuristic optimization
- black-box optimization
