Towards a White Box Approach to Automated Algorithm Design

Steven Adriaensen, Ann NowéIJCAI 2016 · OpenReview

Abstract

Automated algorithm design traditionally treats programs as "black boxes," optimizing parameters based solely on final performance metrics. This paper proposes a fundamental shift toward a "white box" approach by reformulating the algorithm design problem as a Markov Decision Process (MDP). By exploiting internal execution data and tracking unique execution paths, this framework enables orders-of-magnitude faster optimization and the creation of adaptive algorithms that respond to runtime context.

Introduction

The current state-of-the-art in automated algorithm design—often called Programming by Optimization (PbO)—relies on black-box configurators like ParamILS or SMAC. These tools provide a set of parameters, run the algorithm, and receive a single cost value (e.g., execution time) upon completion. However, this approach suffers from two major flaws: information waste and static designs. Black-box tools ignore when and how a decision affects performance, and they typically return a single, static configuration that cannot adapt to the specific problem state encountered during execution.

Methodology: Algorithm Design as an MDP

The core contribution of this work is the formalization of the Algorithm Design Problem (ADP) as a Markov Decision Process (MDP). In this model:

  • States ($S$): Represent the internal state of the algorithm.
  • Actions ($A$): Represent the design choices or parameter settings available at specific "choice points."
  • Transitions ($T$): Represent the execution of logic between choice points.
  • Rewards ($R$): Provide incremental feedback during execution.

By linking rewards to specific transitions, the optimizer can perform precise credit assignment, understanding exactly which decision led to a performance gain. To implement this, the authors introduced Path-based Uniform Random Sampling (PURS), a sampling agent that explores unique execution paths rather than just unique parameter configurations. This allows the system to generalize data across thousands of configurations that share the same initial execution steps.

Experimental Evaluation

The authors evaluated the white-box approach using two micro-benchmarks designed to isolate specific advantages:

Benchmark 1: Search Speedup

This benchmark features a large configuration space ($2^{20}$ possible settings) but only 21 possible execution paths. It tests how quickly an optimizer can find the optimal path when many configurations are functionally redundant.

Benchmark 1 results showing the massive speedup of white-box approaches (WB-PURS) compared to black-box methods.

As shown in the results, the white-box optimizer (WB-PURS) found the optimal configuration in approximately 100 evaluations. In contrast, standard black-box random search required nearly 1,000,000 evaluations, and the state-of-the-art ParamILS required roughly 10,000.

Benchmark 2: Design Adaptivity

This benchmark tests the ability to learn a dynamic policy where the optimal decision depends on the order in which choices are encountered—a context invisible to static configurators.

Benchmark 2 results demonstrating how white-box approaches can achieve optimal adaptive rewards that static black-box methods cannot.

The white-box approach successfully learned an adaptive policy reaching a reward of 5.0. Because black-box approaches are limited to static configurations, they could never exceed a reward of 1.0, regardless of the number of evaluations performed.

Conclusion and Future Work

While the white-box approach offers significant gains in efficiency and adaptivity, challenges remain regarding state-space explosion. Modeling every variable as an MDP state is impractical; future work must focus on automated feature selection to identify relevant context. Additionally, while current implementation requires manual code instrumentation (using getDecision and feedback hooks), future integration into compilers could automate this process, making white-box optimization a standard part of the software development lifecycle.

Summary updated

Abstract

To date, algorithms for real-world problems are most commonly designed following a manual, adhoc, trial & error approach, making algorithm design a tedious, time-consuming and costly process. Recently, Programming by Optimization (PbO) has been proposed as an alternative design paradigm in which algorithmic choices are left open by design and algorithm configuration methods (e.g. ParamILS) are used to automatically generate the best algorithm for a specific use-case. We argue that, while powerful, contemporary configurators limit themselves by abstracting information that can otherwise be exploited to speed up the optimization process as well as improve the quality of the resulting design. In this work, we propose an alternative white box approach, reformulating the algorithm design problem as a Markov Decision Process, capturing the intrinsic relationships between design decisions and their respective contribution to overall algorithm performance. Subsequently, we discuss and illustrate the benefits of this formulation experimentally.
BibTeX
@inproceedings{adriaensen2016towards,
  author = {Steven Adriaensen and Ann Nowé},
  title = {{Towards a White Box Approach to Automated Algorithm Design}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=HJ-IWrfObB},
}
Figure