Continuous multi-task Bayesian Optimisation with correlation

Michael Pearce, Jürgen BrankeEur. J. Oper. Res 2018 · DOI

TL;DR

This paper introduces CLEVI and REVI, novel Bayesian optimization algorithms designed to efficiently find optimal parameters across multiple correlated tasks simultaneously. These methods outperform existing approaches by intelligently leveraging task correlations to guide the sampling process, leading to faster convergence and better overall performance, especially in complex scenarios.

What Problem Does This Paper Address?

Many real-world problems involve optimizing a system with multiple related tasks, where each task has its own set of parameters that need tuning. For example, tuning the hyperparameters of a machine learning model for different datasets, or finding the optimal drug dosage for different patient profiles. The challenge is that evaluating each parameter setting on each task can be expensive and time-consuming. Traditional single-task optimization methods don't scale well to this multi-task setting, and existing multi-task approaches often fail to fully exploit the correlations between tasks. This paper addresses the problem of efficiently exploring the parameter space across multiple correlated tasks to find the optimal parameter setting for each task, given a limited budget of evaluations.

Methods

The core of this work lies in developing new myopic sampling policies for Bayesian Optimization (BO). BO works by building a probabilistic model (specifically, a Gaussian Process) of the objective function and using an acquisition function to decide where to sample next to maximize expected improvement.

The paper proposes two main novel acquisition functions:

  • CLEVI (Convolutional Local Expected Value of Improvement): This method approximates the expected improvement across all tasks by considering the "regional influence" of a sample. It leverages the task distribution and assumes a fixed target level for improvement.
  • REVI (Regional Expected Value of Improvement): REVI builds upon CLEVI by more accurately accounting for the "regional influence" and the information gain for other tasks due to task correlations. It uses a Monte Carlo approach to approximate the expected improvement over the task distribution.

Both methods use Gaussian Processes to model the latent function relating task features and parameters to performance, and they exploit the covariance between tasks. They also consider two ways of defining the "best" solution: the one with the highest predicted performance (risk-neutral) and the one with the highest sampled performance (risk-averse).

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic benchmark functions for evaluation:

  • Rosenbrock Test Function: Scaled to a specific domain and used with different noise levels and task distributions (uniform and triangular).
  • High Dimensional Test Functions: Generated from Gaussian Process priors with varying dimensions (1 to 5) to test the algorithms' scalability.
  • Discrete Task Benchmarks: Used to compare against the SCoT algorithm.

Key Insights and Ideas

  • Exploiting Task Correlation is Crucial: The paper strongly demonstrates that effectively leveraging the correlations between tasks significantly improves optimization efficiency compared to methods that treat tasks independently or ignore correlations.
  • REVI's Superiority in Complex Scenarios: REVI, by more accurately modeling task correlations and using Monte Carlo integration, consistently outperforms CLEVI and other baseline methods, especially when task distributions are non-uniform or when dealing with higher dimensions.
  • Risk-Averse vs. Risk-Neutral Decision Making: The paper highlights the importance of considering the decision-maker's risk preference. A risk-averse approach, which prioritizes sampled performance, can lead to better outcomes in certain settings, particularly with limited tasks.
  • CLEVI as a Special Case: The Profile Expected Improvement (PEI) algorithm, a state-of-the-art method, is shown to be a simplified version of CLEVI under specific assumptions (uniform task distribution, no convolution).
  • Dimensionality Challenges: While REVI and CLEVI are more robust to increasing dimensionality than PEI, they still face challenges in very high-dimensional spaces due to data sparsity and computational costs.

Key Results

  • Performance Gains: In experiments, REVI consistently achieved the best results, converging to the true optimal mapping faster than CLEVI and PEI across various scenarios. CLEVI and PEI often performed similarly, but REVI showed a significant advantage, especially with non-uniform task distributions.
  • Robustness to Noise and Distribution: REVI's performance was less affected by noise and non-uniform task distributions compared to other methods.
  • High-Dimensional Performance: REVI and CLEVI showed better scalability in higher dimensions compared to PEI.
  • Risk-Averse Advantage: For risk-averse decision-makers, optimizing the posterior mean before selecting the final sample yielded substantial benefits.

Limitations and Future Work

  • Model Mismatch: The paper acknowledges that real-world applications often involve model mismatch (where the assumed Gaussian Process model doesn't perfectly represent the true function). This can affect the performance of Bayesian Optimization algorithms, and REVI, which heavily exploits covariance, might be particularly sensitive to inaccurately estimated covariance structures.
  • Computational Complexity: While REVI outperforms CLEVI, it is computationally more expensive, especially in high dimensions. The paper suggests that further optimization of Monte Carlo integration and sparsity assumptions could mitigate this.
  • Batch Parallel Sampling: The current work focuses on sequential sampling. Extending the algorithms to batch parallel sampling would be a natural next step for practical applications.
  • Other Notions of Risk Aversion: The paper primarily considers a specific type of risk aversion. Exploring other notions, like lower confidence bounds, could be beneficial.
  • Real-World Applications: The authors emphasize the need to apply these algorithms to various real-world problems to reveal specific flaws or benefits and to understand their practical utility.

Summary updated

BibTeX
@article{pearce2018continuous,
  author = {Michael Pearce and Jürgen Branke},
  title = {{Continuous multi-task Bayesian Optimisation with correlation}},
  journal = {Eur. J. Oper. Res.},
  year = {2018},
  doi = {10.1016/j.ejor.2018.03.017},
}
Figure