PAL (Pareto Active Learning) Algorithm for Multi-objective Optimization

What is it?

PAL is an algorithm designed to quickly predict the Pareto-optimal solutions in a multi-objective design space. This is a particularly useful when measuring the target objectives given a design point is expensive, and therefore only a few samples of the design space should be drawn for measurement.

All our work on learning for optimization and autotuning.

Overview

The challenge of multi-objective design spaces is that rather than having a single optimal solution, several solutions may simultaneously optimize the target objective functions.

A concrete example in the domain of hardware design, are the design spaces generated by the Spiral DFT and sorting network hardware generators, when exploring the different settings provided by the tool. The user needs to choose between different candidate designs that perform the same task but that trade differently throughput and area. This challenge is aggravated by the fact that evaluating each design is extremely expensive, since complex synthesis processes must be executed. Thus, it is impractical and sometimes infeasible to evaluate every possible design in order to find the Pareto-optimal solutions that maximize throughput and minimize area at the same time.

Having drawn a few samples of the design space, PAL builds models using Gaussian processes to predict the objective functions for the rest of the space. Given these predictions and their corresponding uncertainties, PAL speculatively classifies designs as Pareto-optimal or not Pareto-optimal. Training samples are smartly selected until all points can be classified with the desired accuracy. This accuracy can be specified with the parameter epsilon. More details can be found in [1,2]. An illustrative example of an iteration of the PAL is shown below.

The implementation of PAL that is provided here is written in Matlab, and uses the GPML libraries written by Carl Edward Rasmussen and Chris Williams [3]. PAL can be used for any number of objective functions, however this implementation is limited to two objective functions.

Benchmarks

In the plots below we show that different accuracy/training-cost tradeoffs can be obtained by varying the value of the parameter epsilon. Accuracy in predicting the Pareto front of a design space is measured using the logarithmic hypervolume error. The plots only show the errors obtained with the objective function 1.

The plots also show the effect of choosing epsilon on the termination of PAL. A larger epsilon causes PAL to stop earlier. Design spaces used are based on data sets obtained in [4], [5] and [6].

We compare the efficiency of PAL with that of the evolutionary algorithm ParEGO [7]. These results show that PAL in almost all cases significantly improves over ParEGO.

A detail explanation of these experiments can be found in [1].

Download

Our implementation of PAL can be downloaded here. This archive also contains the datasets used for our experiments presented in [1]. Detail instructions on how to use this program are included in the README file.

References

All our work on learning for optimization and autotuning.
  1. Marcela Zuluaga, Andreas Krause, Guillaume Sergent and Markus Püschel
    Active Learning for Multi-Objective Optimization
    to appear in Proc. International Conference on Machine Learning (ICML), 2013
  2. Marcela Zuluaga, Andreas Krause, Peter A. Milder and Markus Püschel
    "Smart" Design Space Sampling to Predict Pareto-Optimal Solutions
    Proc. Languages, Compilers, Tools and Theory for Embedded Systems (LCTES), pp. 119-128 , 2012
  3. Marcela Zuluaga, Peter A. Milder, and Markus Püschel
    Computer Generation of Streaming Sorting Networks
    Proc. Design Automation Conference (DAC), 2012
  4. Carl Edward Rasmussen and Christopher K. I. Williams
    Gaussian Processes for Machine Learning
    The MIT Press, 2006
  5. Oscar Almer, Nigel Topham, and Björn Franke
    Learning-Based Approach to the Automated Design of MPSoC Networks
    Proc. Architecture of Computing Systems (ARCS), 2011
  6. N. Siegmund, S. S. Kolesnikov, C. Kastner, S. Apel, D. Batoryx, M. Rosenmuller, and G. Saake
    Predicting Performance via Automated Feature-Interaction Detection
    Proc. Int'l Conference on Software Engineering (ICSE), 2012
  7. J. Knowles
    ParEGO: a Hybrid Algorithm with Online Landscape Approximation for Expensive Multiobjective Optimization Problems
    IEEE Trans. on Evolutionary Computation, 2006

More information

Contact: Marcela Zuluaga <firstname.lastname@inf.ethz.ch>