Synergizing Theory and Practice of Automated Algorithm Design for Optimization

The first session of the working group highlighted the following challenges that need to be addressed regarding the terminology used for AAD:

• $\mathrm{■}$

  Standardize terminology for AAD – different researchers use different terms for the same concepts, thus a standardization is needed.

• $\mathrm{■}$

  Remove confusion regarding AAD terms in the literature – due to different terms being used for the same concept this leads to confusion.

• $\mathrm{■}$

  The need of an extensible framework/standardization as the field develops further – AAD is a rapidly developing field and as such there is a need for an extensible standardization.

• $\mathrm{■}$

  Principle components of design need to be identified – a starting point of the standardization would be to identify the main/principle components of designs.

Criteria Considered for Categorization

• $\mathrm{■}$

  Underlying design problem – what is the design problem being solved, e.g. determining hyperparameters, creating a new operator.

• $\mathrm{■}$

  Outcome – What is the design that is produced? Does it have to be reusable?

• $\mathrm{■}$

  High-level methodology – What optimization technique is used to generate the design?

Proposed Categorization

• $\mathrm{■}$

  Automated configuration – Involves determining the parameters and hyper-parameters, e.g. learning rate, population size, operator probabilities. Related terms: HPO, parameter tuning, parameter control.

• $\mathrm{■}$

  Automated Selection – Involves selecting algorithms. Same underlying problem in automated configuration.

• $\mathrm{■}$

  Automated Composition – Involves combining existing processes/algorithms as black box components.

• $\mathrm{■}$

  Automated Generation – Involves creating new algorithms, e.g. new move operators, new genetic operators.

Proposed Principle Components:

• $\mathrm{■}$

  Problem input – What is the input to the design program, e.g. values for parameters, potential components of an operator?

• $\mathrm{■}$

  Search space – What space is being explored to solve the problem, e.g. parameter space, program space, heuristic space.

• $\mathrm{■}$

  Methods – The optimization approaches used for search.

• $\mathrm{■}$

  Objective – What is the purpose of solving the problem, e.g. reduced workload, better design leading to better results.

• $\mathrm{■}$

  Outcome – The design produced.

Areas for further discussion:

• $\mathrm{■}$

  Is automated selection and automated configuration the same problem?

• $\mathrm{■}$

  Is the search space a principle component?

The discussions held provided a starting point to develop a standardization for AAD. There are some areas for further discussion where consensus was not reached. The aim is for this standardization proposal generated from the discussions to be taken further by interested members of the community for further discussion and possible formalization.

• $\mathrm{■}$

  What are landscape features? Do theoretical benchmarks capture them?

• $\mathrm{■}$

  Useful benchmarks for algorithm configuration

• $\mathrm{■}$

  Benchmarks on AAD

• $\mathrm{■}$

  AAD across combinatorial problem domains

• $\mathrm{■}$

  How to bridge theory and practice? What about theoretical empirics?

• $\mathrm{■}$

  Benchmarking on real-world applications

• $\mathrm{■}$

  Representativeness of benchmark data

• $\mathrm{■}$

  Theory-inspired benchmarks for understanding AAD

• $\mathrm{■}$

  Improving experimental methods for AAS etc.

• $\mathrm{■}$

  How to select instances for the transfer from training to testing

• $\mathrm{■}$

  Understanding problem spaces and problem properties better

• $\mathrm{■}$

  Benchmark sets in optimization and in AAD often tend to be small.

• $\mathrm{■}$

  Benchmarking is probably more instrumental in automated algorithm design than in “manual” algorithm design however we could not point to in which way benchmarking needs to be distinctively different.

• $\mathrm{■}$

  It is not clear whether we want to increase the size and diversity of the benchmark suites. In principle this is desirable (ML), but we do want our benchmark set to still reflect the real world. Data augmentation was successful in ML.

• $\mathrm{■}$

  Perhaps optimization heuristics even have a strength in being able to work with little training data (flexibility, adaptability).

• $\mathrm{■}$

  This touches on the question at which level the automation should take place. For one problem class? For everything? That decides the scope of the benchmark set.

• $\mathrm{■}$

  It is controversial how useful or arbitrary a feature space representation of benchmark problems is.

• $\mathrm{■}$

  Invariance properties may be a relevant and desirable aspect for features.

As a first discussion point, we discussed what is missing or not well-studied in AAC. This includes:

1. 1.

   Multi-objective AAC guided by a surrogate (e.g., Bayesian optimization) s.t. users can optimize for complementary objectives and obtain an approximated Pareto front at the end [7];

2. 2.

   AC methods with feature-dependent results (a.k.a per-instance algorithm configuration or instance-specific algorithm configuration) where the results are (I) interpretable (e.g., by providing symbolic formulas) or (II) derived from a grammar to be more expressive compared to common bounded configuration spaces;

3. 3.

   Pre-trained surrogate models that are inspired the current trend of foundation models;

4. 4.

   Text-based interfaces for AAC based on large language models (LLMS) to provide an easy user interface where domain experts can easily interact with [28];

5. 5.

   Allowing more complicated constraints in the configuration space – currently this is dominated by rejection sampling that cannot deal with highly constrained spaces;

6. 6.

   Interactive methods where one can aggregate several preferences across multiple interactions – the major difficulty lies in the aggregation;

7. 7.

   Statistical guarantees s.t. users can trust that the results are close to optimal w.r.t. the evaluated configurations (e.g., the configuration returned is not worse than any other seen with $95\%$ certainty);

8. 8.

   How to deal with low signal-noise ratios where there is a lot (maybe even heteroscedastic) noise on algorithm evaluations?

9. 9.

   How can theoretically-driven racing schemes (e.g. [30]) and user-defined utility-functions [13] be combined with Bayesian-optimization guided AAC?

10. 10.

    How can we configure our AAC methods in view of how expensive it is to run AAC methods? Simply applying AAC to AAC will be too expensive in most cases or diminishing returns have to be taken into account [21];

11. 11.

    Maybe surprisingly, the commonly used AAC packages (e.g., irace [22] and SMAC [18, 20]) do not implement all state-of-the-art ideas from other AI subfields (e.g., foundation models, constraint solving, LLMs and theoretical sound approaches).

At the end of the discussions, several promising directions were identified:

1. 1.

   What are actually the most important components of an AAC method? A systematic study across different AAC methods and application domains is still missing. This could be done based on AClib [19]. This will also require updating AClib with new scenarios, algorithms and instances.

2. 2.

   How can we make results from AAC methods more interpretable to (I) increase the users’ trust into these methods and to (II) enable theory-driven results based on empirical results? The common approaches include either using more interpretable models (e.g., linear models or symbolic models) or model-agnostic post-hoc explanations.

3. 3.

   How can we increase the robustness of AAC methods where robustness can refer to noisy algorithm evaluations, heterogeneous instance sets or stochasticity of the AAC method?

In contrast to the traditional approach of wrapping AAC around existing algorithms, an alternative is to tightly integrate AAC into the algorithms. This enables dynamic configuration (DAC) [1] while the algorithm is running and can, e.g., dynamically adapt to new challenges in the optimization landscape.
There are two major lines of work in this direction:

1. 1.

   Configuring the parameters of the algorithm dynamically. This follows the idea of the traditional AAC methods that takes the algorithm as it is and only controls its parameters [27, 5]. With DACBench [10], there is a benchmark library that allows to benchmark such approaches on various AI subfields efficiently. In addition, there is a benchmark that is on the intersection of empirical experiments and theory [6].

2. 2.

   Algorithm components can also be completely replaced by AI components and thus increase efficiency [26, 17, 8]. This can come with reduced theoretical guarantees since the learned components are typically based on neural networks.

Open problems for dynamic configurations include:

1. 1.

   How to scale DAC to large configuration spaces (i.e. many algorithm parameters)? Most current approaches deal with less than five parameters and some even struggle to perform well on more than two parameters.

2. 2.

   How to decide on which instances one should learn in a dynamic AAC strategy? An efficient learning strategy is required since dynamic configuration needs to perform well on new instances. Approaches from curriculum and self-paced learning could be promising [9].

3. 3.

   When should DAC be applied? How to efficiently determine whether dynamic configuration is beneficial beyond static configuration?

Although there is active research on AAC methods for more than a decade and there is substantial progress (e.g., tremendous speedups, efficient scaling to more algorithm parameters (at least for static AAC) and dealing with different kinds of instances), there are still many open challenges that are not yet addressed fully and open up many further research directions.

• $\mathrm{■}$

  What are the challenges for EDAs in the AAD scenarios:

  1. 1.

     The search space is mixed (continuous, integer, categorical).

  2. 2.

     There exists a hierarchy between the parameters, in the form of known a priori conditions.

  3. 3.

     There might be unknown stochastic dependencies between parameters.

  4. 4.

     The problem can be noisy, with non-Gaussian noise.

  5. 5.

     Since we often consider multiple instances, this is another area in which a different kind of noise gets introduced.

• $\mathrm{■}$

  How can the sampling be made more efficient? In sig-cGA, some variables are fixed when you are sure they should have some particular value (good theoretical results but unclear experimental results).

• $\mathrm{■}$

  How to create good synthetic functions?

• $\mathrm{■}$

  How to handle the conditional parameters? Can we just ignore the condition and sample values which have no effect (which results in a random walk of the respective values)?

• $\mathrm{■}$

  Can we use the Bayesian optimization algorithm (BOA) with Bayesian networks (or P3 or GOMEA)? Can the dependency network be created, and could this handle mixed-integer variables?

  • –

    The algorithms in questions should be capable to represent the dependency network well up to a degree.

  • –

    EDAs are also capable to handle mixed-integer problems, but we came to no conclusion how well this would work for our purpose.

• $\mathrm{■}$

  Univariate EDAs require far less work to build a model. For certain contexts, e.g., where it is very hard to figure out actual dependencies, this might already be sufficient. We have some theoretical guarantees for how to choose the parameters of univariate EDAs, preventing them from converging prematurely to bad values.

• $\mathrm{■}$

  Density estimation trees or forests (e.g., the mlpack package): how to update the trees?

  • –

    We did not come to a good conclusion.

• $\mathrm{■}$

  Use CMA-ES with handling of mixed-integer spaces (except categorical). There is a version of CMA-ES that can adapt the size of the covariance matrix.

• $\mathrm{■}$

  We can use techniques from deep reinforcement learning to learn the update function of CMA-ES. Is there a structural prior to use to speed up this training? Could we apply algorithm design, define a grammar, and apply genetic programming to this context?

  • –

    We were indecisive about the next steps.

This area is heavily underexplored so far. Some AAD approaches, like irace, exist that can be thought of as EDAs. However, they do not make use of theoretical guarantees. Partially because the theoretical results are too recent, partially because we have no guarantees for multivariate EDAs. Hence, employing complex EDAs should follow proper empirical tests.

• $\mathrm{■}$

  Everyone interprets explainability in their own way, ranging from understanding complementarity of algorithms and explaining the autoML process itself to explaining experimental data such as identification of flaws or biased data/setup of the process.

• $\mathrm{■}$

  Overarching question: when / why care for explainability if we just want better-performing algorithms?

• $\mathrm{■}$

  There are different levels of explainability: designers vs. users. For example, users want explainability to gain trust in the AAD frameworks / tools. Explanations are also always contextualized in your own (domain) knowledge, so different users might need different explanations.

• $\mathrm{■}$

  Can explainability help identify what parts of a problem are relevant, or help to identify useful guidelines from the vast amount of data collected by AAD approaches? Explanations might help understand the complexity of a model, e.g. that some HPO problems have low effective dimensionality [3].

• $\mathrm{■}$

  What are the limits of explainability: can we sufficiently explain very complex models with high fidelity? Do explanation techniques have sufficient explanatory power?

• $\mathrm{■}$

  To what extent are features useful for explainability? If we use features, should we limit ourselves only to those we fully understand and build simple models based on those?

• $\mathrm{■}$

  We need to be careful of the Rashomon effect: many possible explanations might exist based on spurious interactions, high correlation of features,…

• $\mathrm{■}$

  Diagnostic tools for the existing interpretable/explainable ML methods and theoretical proofs are still missing. Many of the IML methods are still very new, and not yet fully trusted.

• $\mathrm{■}$

  One potential way to help explainability is to use functional ANOVA or Generalized Additive Models for decomposition of the model.

• $\mathrm{■}$

  There exists a wide range of techniques which might be useful for the explainability of AAD: fANOVA, Symbolic Formulas, (automatic) Ablations, Partial Dependency Plots, Item Response Theory, Instance Footprint plots, Local Parameter Importance, landscape features, feature selection, simple explainable models, regularized models in expensive settings…

Explainability in general is gaining more attention in many communities, and there are ways in which AAD might also benefit from more explainable techniques. It is however still unclear when to focus on explainability over just improving the performance of the final algorithm. The quick growth of explainability techniques gives rise to a lot of opportunities, but we should not lose sight of the overall picture and reason about what we want to explain, why and to whom.

1. 1.

   Although the efficiency of AutoML has improved by orders of magnitude in recent years, AutoML might still be too inefficient for very expensive models (e.g., LLMS).

2. 2.

   AutoML is not always robust; e.g., a simple default pipeline sometimes (rarely) outperforms a complex AutoML system. How can users trust AutoML systems that the invested compute (and waiting) time is worth it?

3. 3.

   AutoML still does not handle all kinds of pitfalls of ML. For example, (I) class imbalance is not properly dealt with in all tools, (II) wrong or inefficient validation schemes were used or (III) ensembling is not beneficial.

4. 4.

   The user interfaces of many AutoML tools are not user-friendly. It is an open question of how verbose the output of an AutoML tool should be and what kind of warnings are required (e.g., class imbalance and fairness). Generally, designing good user interfaces without specifying the target user group is hard, but AutoML aims to be an approach for everyone.

5. 5.

   AutoGluon [11] is very fast and delivers strong performance (in particular on tabular data for supervised tasks). Is AutoML for this subtask already solved or can we outperform it by using drastically different approaches?

6. 6.

   Large language models (LLMS) pose a major challenge since they are expensive and combine several learning paradigms. Current AutoML approaches are hardly applicable [28].

7. 7.

   The hidden objectives of practitioners are not always explicitly expressed. For example, some users care only about predictive performance and others want to have rather small and interpretable models. Not all AutoML tools can address different user preferences; e.g., AutoGluon returns neither small nor interpretable models.

8. 8.

   How can AutoML help to understand the data in a better way (e.g., in data-centric approaches)?

9. 9.

   How can we design an interactive AutoML system that (I) allows users to learn from the AutoML system about the AutoML process and the data, and (II) to specify their preferences, (III) benefits from users’ input to improve the overall performance of the system (given the users’ objectives)? This might be important s.t. practitioners do not get the impression that these systems can get out of control, but they are still in charge and thus can trust the system.

10. 10.

    Surprisingly, there seems to be a large group of practitioners rather using optimizers for AutoML problems but fewer the full-fledged AutoML systems. These optimizers offer much more flexibility but require more expertise and effort to set them up. What is missing in full AutoML systems s.t. more practitioners want to use them? Learning search spaces on the fly could be one promising direction [25, 24].

11. 11.

    Large language models (such as ChatGPT) could offer new ways to interact with AutoML systems (or partially replace them) s.t. users will need even less knowledge about how to code ML systems [31].

Although AutoML is much more mature than it was a few years ago, there are still major challenges in applying AutoML in practice without expertise in ML and AutoML. One of the most crucial next steps will be to bridge the gap between the expectations, expertise, and workflows of ML practitioners and AutoML tools.