Towards GP-based optimization with finite time horizon

David Ginsbourger, Rodolphe Le Riche2009

TL;DR

This paper introduces a new framework for optimizing functions with a fixed number of evaluations, showing that the standard "Expected Improvement" (EI) strategy is suboptimal. They propose a "multipoints EI" approach that considers the entire optimization horizon, leading to better strategies, especially when the total number of evaluations is limited.

What Problem Does This Paper Address?

In computer experiments and expensive black-box optimization, we often want to find the best input parameters for a function that is costly to evaluate. A common approach is to use Gaussian Processes (GPs) to build a surrogate model of the function and then use an "acquisition function" to decide where to sample next. The "Expected Improvement" (EI) is a popular acquisition function that balances exploring uncertain regions and exploiting promising ones. However, the standard EI strategy (like in the EGO algorithm) treats each iteration independently, essentially assuming the current iteration is the last one. This paper addresses the problem of optimizing when there's a known, finite budget of evaluations (a "finite time horizon"), arguing that this myopic approach is suboptimal and proposing a more holistic strategy.

Methods

The core of the paper is the formalization of "deterministic strategies with finite horizon." Instead of just maximizing the 1-point EI at each step, they define a strategy as a sequence of functions that decide the next point to evaluate, taking into account the entire remaining budget. They then define a new criterion, the "Expected Improvement of a strategy," which measures the overall performance of a strategy over the entire horizon.

To solve the problem of finding the optimal strategy, they derive a recursive solution. The optimal strategy for the last iteration is simply maximizing the EI. For earlier iterations, the optimal strategy involves maximizing an EI that accounts for the future optimal choices. This leads to a backward induction approach. They also introduce a way to decompose the expected improvement of a strategy into the immediate 1-point EI and a "future expected improvement" term, which can be estimated using Monte-Carlo simulations with conditional sampling from the GP.

Datasets

The paper uses a 1-dimensional test case with a specific objective function: $y_1(x) = \sin(10x+1)/(1+x) + 2\cos(5x)x^4$ for $x \in [0,1]$. This function is used to illustrate the proposed methods and compare the standard EI algorithm with their new strategy. No standard benchmark datasets are used; instead, a custom, illustrative example is employed.

Key Insights and Ideas

  • Myopic EI is Suboptimal: The most significant insight is that greedily maximizing the 1-point EI at each step is not optimal when there's a fixed, finite number of evaluations. This is because it ignores the value of information gained for future steps.
  • Finite Horizon Matters: Recognizing and formalizing the "finite time horizon" is crucial. It shifts the problem from a series of independent decisions to a single, integrated optimization problem.
  • Recursive Optimal Strategy: The paper provides a clear recursive structure for finding the optimal strategy, working backward from the last iteration. This is a powerful theoretical result.
  • Decomposition of Improvement: The idea of decomposing the total expected improvement into an immediate gain and a future gain is insightful. It helps understand why a particular point might be good beyond its immediate EI value.
  • Monte-Carlo for Future EI: Using Monte-Carlo simulations with conditional GP sampling is a practical approach to estimate the future expected improvement, making the proposed strategy computationally feasible.

Key Results

The paper demonstrates through a 1D example that their proposed strategy can yield higher improvement values compared to the standard EI algorithm. Specifically, they show that for a finite horizon, choosing a point that might not have the absolute highest 1-point EI can lead to better overall results because it strategically positions the optimizer for subsequent steps. The example highlights how the standard EI might get "stuck" exploring a local optimum early on, while the new strategy can achieve a better balance.

Limitations and Future Work

  • Computational Complexity: The proposed method, especially the Monte-Carlo estimation of future EI, can be computationally intensive, particularly for higher dimensions or longer horizons. The authors suggest that dimension reduction techniques and heuristics might be needed for horizons $r \ge 3$.
  • Theoretical Extension: While the paper focuses on deterministic strategies, extending this to stochastic strategies could be a future direction.
  • Practical Examples: The paper uses a single, simple 1D example. Applying and validating the method on more complex, large-scale practical problems is a natural next step.
  • Connection to Control Theory: The authors mention exploring deeper connections with control theory, which could offer new perspectives and tools for sequential optimization.

Summary updated

Abstract

Abstract During the last decade, Kriging-based sequential algorithms like EGO [2] and its variants have become reference optimization methods in computer experiments. Such algorithms rely on the iterative maximization of a sampling criterion, the expected improvement (EI), which takes advantage of Kriging conditional distributions to make an explicit trade-off between promizing and uncertain search space points. We have recently worked on a multipoints EI criterion meant to simultaneously choose several points, which is useful for instance in synchronous parallel computation. The research results that we wish to present in this paper concern sequential procedures with a fixed number of iterations. We show that maximizing the 1-point criterion at each iteration (EI algorithm) is suboptimal. In essence, the latter amounts to considering the current iteration as the last one. This work formulates the problem of optimal strategy for finite horizon sequential optimization, provides the solution to this problem in terms of multipoints EI, and illustrates the suboptimality of the usual EI algorithm on the basis of a first counter-example. 1
BibTeX
@misc{ginsbourger2009towards,
  author = {David Ginsbourger and Rodolphe Le Riche},
  title = {{Towards GP-based optimization with finite time horizon}},
  year = {2009},
}
Figure