PaperlayerView exact revision on arXiv

Source-linked AI summary

GLASSES: Relieving The Myopia Of Bayesian Optimisation

Javier González, Michael Osborne, Neil D. Lawrence

arXiv:1510.06299v1stat.ML

TL;DR

Most global-optimization methods are myopic, and existing multi-step approaches consider only a handful of future evaluations. GLASSES approximates the costly look-ahead loss to plan dozens of evaluations ahead; in the reported comparisons, a non-myopic loss is best in 6 of 11 cases, though no method is universally best.

  • Problem

    Most global-optimization approaches consider only the next function value, while prior non-myopic methods consider only a handful of future evaluations.

    Source: §1 · p. 1

  • Method

    GLASSES approximates the costly multi-step expected loss by predicting future steps and using Expectation Propagation for joint marginalization.

    Source: §5 · p. 8

  • Results

    A non-myopic loss is best in 6 of 11 cases, the full GLASSES approach is best in 3, and no method is universally best.

    Source: §4.2 · p. 8

  • Takeaways & Limitations

    When GLASSES is not the best global method, it typically performs closely to the best alternative, making it a good default when objective evaluations are expensive.

    Source: §4.2 · p. 8

    Exact multi-step loss evaluation is computationally burdensome, and analytical expressions are available only for the myopic case.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

We present GLASSES: Global optimisation with Look-Ahead through Stochastic Simulation and Expected-loss Search. The majority of global optimisation approaches in use are myopic, in only considering the impact of the next function value; the non-myopic approaches that do exist are able to consider only a handful of future evaluations. Our novel algorithm, GLASSES, permits the consideration of dozens of evaluations into the future. This is done by approximating the ideal look-ahead loss function, which is expensive to evaluate, by a cheaper alternative in which the future steps of the algorithm are simulated beforehand. An Expectation Propagation algorithm is used to compute the expected value of the loss.We show that the far-horizon planning thus enabled leads to substantive performance gains in empirical tests.

1 Introduction

Most global-optimization methods consider only one step ahead, while multi-step lookahead is computationally difficult and prior approaches considered only a few future evaluations. GLASSES exploits parallelism to compute a non-myopic loss for Bayesian optimization.

1 Introduction

  • Most global-optimization techniques are myopic, considering no more than a single step into the future.The paper frames multi-step lookahead as accounting for the significance of evaluations further ahead.Source: §1 · p. 1
  • A two-evaluation myopic strategy can leave half of [0, 1] unexamined, whereas two-step lookahead can distribute evaluations more evenly.The paper argues that the broader coverage provides better information about the objective and its optimum.Source: §1 · p. 1
  • Prior multi-step methods reached at most two future evaluations or six, while GLASSES exploits parallelism to compute a non-myopic loss.Osborne et al. [2009] considered no more than two steps; Marchant et al. [2014] considered no more than six.Source: §1 · pp. 1–2
  • The paper links multi-step lookahead to batch Bayesian optimization, where locations are selected for parallel evaluation.For greedy batch selection, good batches depend on predicting future algorithm steps.Source: §1 · pp. 1–2
  • The n-step lookahead model couples future function values, but its nested maximizations and integrations make inference prohibitively expensive.Figure 1 marks the known data D0 and current decision x∗.Source: Figure 1 · p. 2

2 Background and challenge

The section moves from Bayesian optimization's one-step setting to the expected loss for n future evaluations, whose exact evaluation is computationally burdensome. It then introduces GLASSES as an efficient approximation intended to consider dozens of steps ahead.

2.1 Bayesian optimisation with one step look-ahead

  • Bayesian optimization uses a probabilistic surrogate, typically a Gaussian Process, to guide a limited sequence of noisy black-box evaluations toward the minimum.The setup assumes observations yi = f(xi) + ϵi with Gaussian noise.Source: §2.1 · p. 2
  • With one evaluation remaining, the method defines loss from the best value found so far and selects the next location by minimizing its expected loss.The one-step loss has a closed form, and its minimum can be obtained with gradient descent.Source: §2.1 · pp. 2–3

2.2 Looking many steps ahead

  • Λn(x∗|I0) denotes the expected loss of selecting x∗ while considering n future evaluations.The future evaluations augment the data and update the model parameters as the available information changes.Source: §2.2 · p. 3
  • Evaluating the exact n-step loss requires successive sampling and optimization, and analytical expressions are available only for the myopic case.The paper identifies the computation required for many-step horizons as the reason further horizons remained unexplored.Source: §2.2 · p. 3

2.3 Contributions of this work

  • GLASSES is proposed to efficiently account for dozens of future steps by predicting future steps of the myopic loss and integrating out a long-sight loss.The contribution list also describes splitting recursive optimization and marginalization into two steps, with Expectation Propagation for joint marginalization.Source: §2.3 · p. 3

3 The GLASSES algorithm

GLASSES approximates expensive multi-step lookahead by modeling future evaluations jointly and using a fixed set of predicted locations. Its expected-loss criterion values the best outcome across the remaining horizon, while local penalization supplies diverse future locations.

3 The GLASSES algorithm

  • Fixing future locations makes the joint lookahead approximation cheaper, though it does not use epistemic uncertainty about those future steps.Figure 2 depicts the approximation's sparser network, with the current decision variable connected to all future steps.Source: §3 · pp. 3, 5, Figure 2 · p. 4

3.1 Oracle multiple steps look-ahead expected loss

  • The oracle loss is the expected best function value over the next n evaluations, conditional on evaluating x* first; Expectation Propagation computes this loss.The oracle assumes perfect information about future locations, an unrealistic assumption used to set up the algorithm.Source: §3.1 · p. 5

3.2 Local Penalisation to Predicting the Steps Ahead

  • Local penalization predicts future locations by iteratively discouraging nearby selections while favoring regions of low loss, balancing diversity with location quality.The penalizers define probabilistic exclusion zones around selected points, using the probability that a candidate minimum lies outside the neighborhood.Source: §3.2 · pp. 6–7

3.3 Algorithm and computational costs

  • The main computational cost is predicting future steps with a sequence of L-BFGS optimizers at O(Pq^2) complexity; EP updates Gaussian factors quadratically in dimensionality.P is the maximum number of L-BFGS updates.Source: §3.3 · p. 7

4 Experiments

Experiments show how longer lookahead changes the loss and compare GLASSES with fixed-horizon losses and other acquisition functions across test functions. Non-myopic losses often perform well, but no method is universally best.

4.1 Interpreting the non-myopic loss

  • As lookahead increases, the expected loss decreases and flattens, making the acquisition function more explorative.The experiment plots myopic loss against variants using 2, 3, 5, 10, and 20 steps ahead.Source: §4.1 · p. 7

4.2 Testing the effect of considering multiple steps ahead

  • Across varied functions, five runs compare GLASSES and 2-, 3-, 5-, and 10-step losses with EL, MPI, and GP-LCB, using 10 evaluations per dimension.Each run starts from five randomly initialized data points; Table 1 gives function details.Source: §4.2 · p. 7, Table 1 · p. 7
  • Non-myopic loss is best in 6 of 11 cases, full GLASSES in 3; on McCormick and Powers, more lookahead consistently improves results.When GLASSES is not best, it typically performs close to the best alternative.Source: Table 2 · p. 8, §4.2 · p. 8
  • Performance is measured by normalized gap across methods, with the initial point set to the best of the model's original initialization points.The gap uses the first and best evaluated points relative to the global minimum.Source: §4.2 · p. 8

5 Conclusions

GLASSES approximates a far-horizon Bayesian-optimisation loss by predicting future steps and using Expectation Propagation to compute expected loss. The authors report practical gains, while noting computational challenges and areas for future work.

5 Conclusions

  • GLASSES jointly models future evaluations, uses fixed predictions to reduce the cost of approximating the loss, and applies Expectation Propagation to compute it.The fixed-prediction approach does not use epistemic uncertainty about future steps.Source: §5 · p. 8
  • The authors report that non-myopic loss helps solve global-optimisation problems, but no method is universally best and GLASSES stays close to myopic loss when it is not superior.They describe GLASSES as an interesting default choice in most scenarios.Source: §5 · p. 8
  • If optimization of predicted future steps fails, optimizing the resulting loss may become challenging; efficient loss optimization, non-stationary kernels, and high-dimensional extensions remain future challenges.The authors also identify efficient sampling of many future steps as future work.Source: §5 · pp. 8–9

S1 Oracle Multiple Steps look-ahead Expected Loss

The oracle look-ahead loss tracks the best visited value over future evaluations. Its formulation treats future locations and function values through conditional distributions.

S1 Oracle Multiple Steps look-ahead Expected Loss

S2 Formulation of the Oracle Multiple Steps loook-ahead Expected Loss to be computed using Expectation Propagation

The appendix formulates the oracle multi-step expected loss for computation with Expectation Propagation. It partitions the integral by which future value is minimal, represents the regions with indicators, and combines two terms into Eq. (5).

S2 Formulation of the Oracle Multiple Steps loook-ahead Expected Loss to be computed using Expectation Propagation

S2.1 Synthetic functions

  • The appendix introduces objective-function formulations used in experiments when those formulations are unavailable in the cited references.Source: S2.1 Synthetic functions · p. 12
  • Table 3 lists the functions used in the experimental section.Source: Table 3 · p. 12

Related papers

Loading 1510.06299v1…