Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation

Abstract

We present a new algorithm, truncated variance reduction (TruVaR), that treats Bayesian optimization (BO) and level-set estimation (LSE) with Gaussian processes in a unified fashion. The algorithm greedily shrinks a sum of truncated variances within a set of potential maximizers (BO) or unclassified points (LSE), which is updated based on confidence bounds. TruVaR is effective in several important settings that are typically non-trivial to incorporate into myopic algorithms, including pointwise costs and heteroscedastic noise. We provide a general theoretical guarantee for TruVaR covering these aspects, and use it to recover and strengthen existing results on BO and LSE. Moreover, we provide a new result for a setting where one can select from a number of noise levels having associated costs. We demonstrate the effectiveness of the algorithm on both synthetic and real-world data sets.

Accepted to NIPS 2016

Cited by in corpus (17)

• Distributionally Robust Bayesian Optimization
• On the Design of Black-box Adversarial Examples by Leveraging Gradient-free Optimization and Operator Splitting Method
• Evaluating Gaussian Process Metamodels and Sequential Designs for Noisy Level Set Estimation
• Corruption-Tolerant Gaussian Process Bandit Optimization
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• Optimal approximation for unconstrained non-submodular minimization
• Value-at-Risk Optimization with Gaussian Processes
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits
• Scalable Acceleration for Classification-Based Derivative-Free Optimization
• Multiscale Gaussian Process Level Set Estimation
• Efficient Batch Black-box Optimization with Deterministic Regret Bounds
• High Dimensional Level Set Estimation with Bayesian Neural Network
• Mixed Strategies for Robust Optimization of Unknown Objectives
• Nearly Optimal Algorithms for Level Set Estimation
• No-Regret Learning in Unknown Games with Correlated Payoffs
• Contraction methods for continuous optimization