Bayesian Multi-Scale Optimistic Optimization

Abstract

Bayesian optimization is a powerful global optimization technique for expensive black-box functions. One of its shortcomings is that it requires auxiliary optimization of an acquisition function at each iteration. This auxiliary optimization can be costly and very hard to carry out in practice. Moreover, it creates serious theoretical concerns, as most of the convergence results assume that the exact optimum of the acquisition function can be found. In this paper, we introduce a new technique for efficient global optimization that combines Gaussian process confidence bounds and treed simultaneous optimistic optimization to eliminate the need for auxiliary optimization of acquisition functions. The experiments with global optimization benchmarks and a novel application to automatic information extraction demonstrate that the resulting technique is more efficient than the two approaches from which it draws inspiration. Unlike most theoretical analyses of Bayesian optimization with Gaussian processes, our finite-time convergence rate proofs do not require exact optimization of an acquisition function. That is, our approach eliminates the unsatisfactory assumption that a difficult, potentially NP-hard, problem has to be solved in order to obtain vanishing regret rates.

15 pages

References in corpus (6)

• Practical Bayesian Optimization of Machine Learning Algorithms
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Bandit Algorithms for Tree Search
• Stochastic simultaneous optimistic optimization
• Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations
• Joint Optimization and Variable Selection of High-dimensional Gaussian Processes

Cited by in corpus (18)

• A Framework to Integrate Mode Choice in the Design of Mobility-on-Demand Systems
• Bayesian Optimization with Exponential Convergence
• Constrained Bayesian Optimization for Automatic Chemical Design
• Sample-Efficient Neural Architecture Search by Learning Action Space
• Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search
• B-Splines for Sparse Grids: Algorithms and Application to Higher-Dimensional Optimization
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• Kernel Trajectory Maps for Multi-Modal Probabilistic Motion Prediction
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining
• Facilitating Database Tuning with Hyper-Parameter Optimization: A Comprehensive Experimental Evaluation
• A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption
• Multiscale Gaussian Process Level Set Estimation
• Bayesian Optimization with Approximate Set Kernels
• A Simple Heuristic for Bayesian Optimization with A Low Budget
• Speed-Constrained Tuning for Statistical Machine Translation Using Bayesian Optimization
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret
• Bayesian optimization for modular black-box systems with switching costs