PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Global Optimization via Local Bayesian Optimization

David Eriksson, Michael Pearce, Jacob R Gardner, Ryan Turner, Matthias Poloczek

arXiv:1910.01739v4cs.LGstat.ML

TL;DR

High-dimensional Bayesian optimization with large evaluation budgets remains difficult because global models struggle with heterogeneous objectives and existing approaches are often not competitive. TuRBO uses multiple local Gaussian-process models in trust regions, with a bandit strategy allocating samples globally. Across varied benchmarks, the authors report that TuRBO consistently finds excellent solutions and outperforms other methods on most problems.

  • Problem

    Bayesian optimization often scales poorly to high dimensions and large sample budgets, while global surrogate models struggle with heterogeneous objectives.

  • Method

    TuRBO maintains multiple independent local Gaussian-process models in trust regions and uses an implicit multi-armed bandit strategy to allocate samples among them.

  • Results

    TuRBO consistently finds excellent solutions and outperforms other methods on most problems across benchmarks spanning reinforcement learning, robotics, and natural sciences.

  • Takeaways & Limitations

    The evaluation supports local probabilistic modeling with global bandit allocation as an approach to high-dimensional global optimization.

  • Takeaways & Limitations

    The authors identify learning local low-dimensional structure as future work to improve the accuracy of TuRBO’s local Gaussian-process model.

Abstract

from arXiv · show

Bayesian optimization has recently emerged as a popular method for the sample-efficient optimization of expensive black-box functions. However, the application to high-dimensional problems with several thousand observations remains challenging, and on difficult problems Bayesian optimization is often not competitive with other paradigms. In this paper we take the view that this is due to the implicit homogeneity of the global probabilistic models and an overemphasized exploration that results from global acquisition. This motivates the design of a local probabilistic approach for global optimization of large-scale high-dimensional problems. We propose the $\texttt{TuRBO}$ algorithm that fits a collection of local models and performs a principled global allocation of samples across these models via an implicit bandit approach. A comprehensive evaluation demonstrates that $\texttt{TuRBO}$ outperforms state-of-the-art methods from machine learning and operations research on problems spanning reinforcement learning, robotics, and the natural sciences.

1 Introduction

High-dimensional black-box optimization is important but difficult to scale: global surrogates struggle with heterogeneous objectives, while existing methods can be computationally costly or underperform stochastic optimization. TuRBO addresses these challenges with local models and global sample allocation, and is evaluated broadly across benchmark domains.

  • High-dimensional black-box optimization arises in tuning, reinforcement learning, simulation calibration, and chemical engineering or materials discovery.
  • Existing high-dimensional methods often assume low-dimensional or additive structure, while large-scale Bayesian optimization methods can require costly model ensembles or fail to match stochastic optimizers.
  • The search space grows exponentially with dimension, making global optima harder to find and global surrogate modeling more difficult.
  • Global Gaussian processes assume constant characteristic lengthscales and signal variances, which can mismatch heterogeneous objectives such as sparse-reward reinforcement learning.
  • TuRBO uses simultaneous local probabilistic models and an implicit multi-armed bandit strategy to allocate samples across local optimization runs.
  • TuRBO is evaluated against Bayesian, evolutionary, simulation-optimization, and stochastic-optimization methods across benchmarks spanning reinforcement learning, robotics, and natural sciences.

2 The trust region Bayesian optimization algorithm

TuRBO performs global optimization by maintaining multiple local trust-region Bayesian optimization runs rather than relying on one global surrogate. It adapts each region locally and uses Thompson sampling to allocate candidates across regions.

  • Problem setup: The optimization problem concerns a potentially noisy black-box function f over the bounded domain Ω = [0, 1]^d.
  • Local modeling: TuRBO abandons global surrogate modeling and maintains several independent local models, each supporting a separate local optimization run.
  • Trust regions: Each trust region is a hyperrectangle centered at the best solution found so far, with side lengths rescaled by GP lengthscales while preserving total volume L^d.
  • Trust-region adaptation: A trust region doubles after τsucc consecutive improvements and halves after τfail consecutive failures, while regions below Lmin are discarded and restarted.
  • Global allocation: TuRBO maintains m simultaneous trust regions with independent local GPs and treats them as levers in a multi-armed bandit.
  • Candidate selection: Thompson sampling draws posterior-function realizations within each trust region to select batches of candidates across their union.

3 Numerical experiments

TuRBO is evaluated across high-dimensional, multimodal problems in reinforcement learning, robotics, natural sciences, and synthetic optimization. Across these experiments, local trust-region models and multiple parallel runs generally outperform competing Bayesian optimization and optimization baselines.

  • Robot pushing: TuRBO-1 and TuRBO-20 outperform alternative methods on the 14D robot pushing problem after sufficient evaluations.TuRBO-20 starts more slowly because of its 1K-point initialization but eventually surpasses TuRBO-1; CMA-ES and BOBYQA are the strongest non-TuRBO baselines.
  • Rover trajectory planning: TuRBO-1 and TuRBO-20 outperform all other algorithms on 60D rover trajectory planning after a few thousand evaluations.TuRBO-1 reaches a mean and median reward of about 2 after 1K evaluations, compared with EBO’s reported mean of 1.5 after 35K evaluations.
  • Natural sciences and reinforcement learning: TuRBO variants improve over competing methods on cosmological calibration and learn lunar-lander controllers better than the original OpenAI controller.TuRBO-5 improves over BOBYQA and TuRBO-1 for cosmological constants; TuRBO-5 and TuRBO-1 are among methods exceeding the original controller.
  • 200-dimensional Ackley: TuRBO-1 achieves the best solutions on the 200D Ackley function after initially slower progress by HeSBO-TS-5 and BOBYQA.The authors attribute the limited progress of global-GP Bayesian optimization methods to over-emphasized exploration.
  • Local versus global models: Local GPs achieve average log loss 1.174 versus 1.284 for the global GP across 50 trials, with the improvement significant at p < 10^-4.The local approach also reduces GP computational overhead and captures heterogeneous noise across regions.

4 Conclusions

TuRBO addresses high-dimensional global optimization with local probabilistic models and global bandit-based allocation. The evaluation reports strong performance across complex real-world tasks, while future work targets local low-dimensional structure.

  • 4 Conclusions: TuRBO replaces one global surrogate with multiple local probabilistic models and allocates samples across trust regions using a global bandit strategy.The local models support heterogeneous objective modeling and local search trajectories.
  • 4 Conclusions: TuRBO outperforms state-of-the-art Bayesian optimization and operations research methods across varied real-world complex tasks.The evaluation spans the paper’s broad benchmark suite.
  • 4 Conclusions: Future work will extend TuRBO to learn local low-dimensional structure to improve local Gaussian process accuracy.The authors highlight derivative-informed engineering and machine-learning settings as particularly relevant.

Supplementary material

The supplementary material documents additional benchmarks, algorithm details, scalable GP regression, hyperparameters, trust-region updates, Thompson sampling, test problems, and runtimes.

  • Supplementary material: The supplement adds synthetic benchmarks and detailed descriptions of the algorithms, scalable GP regression, hyperparameters, trust-region updates, and Thompson sampling.It also describes the test problems and provides benchmark runtimes.

A Synthetic experiments

The synthetic experiments evaluate TuRBO and competing local, evolutionary, and Bayesian optimization methods on four benchmark functions. TuRBO performs strongly overall, with performance varying by function and initialization.

  • A Synthetic experiments: The study evaluates Ackley, Levy, Rastrigin, and 6D Hartmann using 50 batches of size q = 10, totaling n = 500 evaluations.Most methods use 20 Latin-hypercube initial points; TuRBO-5 uses 10 per local region.
  • A Synthetic experiments: TuRBO-1 and TuRBO-5 perform well across all synthetic problems, outperforming other methods on Ackley and finding solutions near the global optimum.TuRBO-5 performs best on Levy and Rastrigin, while Hartmann is easier for most methods.
  • A Synthetic experiments: TuRBO-1 is less consistent on Levy, whereas TuRBO-5 performs best on Rastrigin and BOBYQA and BFGS are comparable to TuRBO-1.The Levy results indicate that initialization affects TuRBO-1’s performance.
  • A Synthetic experiments: HeSBO-TS performs well on Levy and Rastrigin, while CMA-ES eventually finds good solutions on several functions but is slower than TuRBO.CMA-ES appears stuck with suboptimal solutions on Levy.
  • A Synthetic experiments: The comparison includes local optimizers, evolutionary algorithms, Bayesian optimization methods, and random search.The baselines include NM, BOBYQA, BFGS, CMA-ES, EBO, BOCK, HeSBO-TS, BOHAMIANN, GP-TS, and RS.

C Gaussian process regression

The experiments use scalable GP regression and a standardized Matérn-5/2 ARD modeling setup. These choices address computational scaling while keeping the GP configuration consistent across experiments.

  • C Gaussian process regression: Scalable GP regression uses conjugate gradients for linear systems and Lanczos approximations for the log-determinant.Classical GP regression becomes infeasible beyond a few thousand evaluations because of cubic scaling.
  • C Gaussian process regression: All experiments use a Matérn-5/2 kernel with ARD, a constant mean, log-marginal-likelihood fitting, rescaled domains, and standardized function values.TuRBO’s GP hyperparameters are bounded, including lengthscales λi ∈ [0.005, 2.0] and signal variance s2 ∈ [0.05, 20].

D TuRBO details

TuRBO details specify trust-region initialization, adaptation, candidate generation, and Thompson-sampling-based selection. The procedure supports multiple trust regions and parallel suggestions through posterior sampling.

  • Trust-region management: TuRBO-1 uses fixed trust-region hyperparameters, including τsucc = 3, τfail = ⌈d/q⌉, Lmin = 2^-7, Lmax = 1.6, and Linit = 0.8.The domain is assumed to be scaled to the unit hypercube [0, 1]^d.
  • Trust-region management: With multiple trust regions, each region has separate success and failure counters, updated according to whether selected points improve that region’s best solution.The number of evaluations allocated to each region may differ across batches.
  • Candidate generation: Each trust region starts at Linit and terminates when L < Lmin, while Thompson samples use candidate sets of size min{100d, 5000}.Candidate sets are regenerated per batch using scrambled Sobol points within the trust-region and domain intersection, with coordinate perturbations controlled by min{1, 20/d}.
  • Thompson sampling: Thompson sampling draws functions from a Gaussian-process posterior and selects each suggestion by optimizing its sampled function.Sampling stochasticity provides the exploration-exploitation trade-off, and repeated suggestions are drawn independently for q > 1.
  • Thompson sampling: Independent Thompson sampling handles parallel batches through Gaussian-process marginalization coherence and also supports asynchronous sampling.This is equivalent to conditioning on imputed values for unobserved suggestions.
  • Thompson sampling: Because full posterior functions cannot be sampled in practice, TuRBO samples Gaussian-process marginals on a finite candidate set before applying standard Thompson sampling.This discretization places the procedure in the setting of traditional multi-arm bandits.

F.1 Robot pushing

The robot pushing task tunes a 14-parameter controller for two robot hands to move two objects toward specified target locations. Its reward measures progress from initial positions toward the goals.

  • Task definition: The task optimizes a controller for two robot hands pushing two objects to given target locations.The controller has d = 14 parameters.
  • Task definition: The 14 controller parameters specify hand locations and rotations, pushing speed, movement direction, and pushing time.These parameters determine the robot’s pushing behavior.
  • Reward: The reward compares each object’s initial-to-goal distance with its final-to-goal distance, rewarding movement toward the targets.The supplied reward expression sums this distance reduction over the two objects.

F.2 Rover trajectory planning

The rover trajectory-planning task optimizes a rough-terrain trajectory represented by a B-spline through 30 points in a 2D plane. Its reward combines collision penalties with start and endpoint penalties.

  • Task definition: The objective is to optimize a rover trajectory over rough terrain using a B-spline fitted to 30 points in a 2D plane.The trajectory is determined by the locations of those points.
  • Reward: The reward penalizes deviations of the trajectory’s start and endpoint from desired positions using an L1-distance term.The desired positions are denoted xs and xg.
  • Reward: Collisions with objects incur a penalty of −20 in the cost function.The reward expression also includes the start and endpoint penalty terms.

F.3 Cosmological constant learning

The cosmological-constant experiment estimates a simulation-based astrophysics model from luminous red galaxy observations. The supplied passages also describe a lunar-lander controller task involving fuel, landing distance, and crash prevention.

  • Cosmological constant learning: The cosmological-constant objective is a likelihood estimate for a simulation-based astrophysics model of Sloan Digital Sky Survey luminous red galaxy data.The model includes physical constants such as Hubble’s constant and matter densities.
  • Cosmological constant learning: The cosmological experiment tunes nine parameters used in previous papers plus three additional parameters selected from simulator options.The resulting parameterization contains 12 tuned parameters.
  • Lunar lander: The lunar-lander task learns a controller that minimizes fuel consumption and landing-target distance while preventing crashes.The controller receives an 8-dimensional state containing position, angle, and their time derivatives, then selects among four booster actions.

G Runtimes

TuRBO combines superior optimization performance with low algorithmic overhead, remaining fast as evaluation counts increase. It runs in minutes across all test problems and is over 2000× faster than the slowest BO method.

  • More than 2000× faster than the slowest BO method, TuRBO runs in minutes on all test problems.The comparison excludes objective-evaluation time and measures one optimization run.
  • Global-GP Bayesian optimization methods become computationally expensive as the number of evaluations increases.Scalable GPs were used on an NVIDIA RTX 2080 TI for these experiments.
  • The reported runtimes are rounded to minutes, hours, or days for each test problem.
Loading 1910.01739v4…