Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees
- URL: http://arxiv.org/abs/2006.15779v1
- Date: Mon, 29 Jun 2020 02:17:18 GMT
- Title: Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees
- Authors: Shali Jiang, Daniel R. Jiang, Maximilian Balandat, Brian Karrer, Jacob
R. Gardner, Roman Garnett
- Abstract summary: We provide the first efficient implementation of general multi-stepahead look Bayesian optimization.
Instead of solving these problems in a nested way, we equivalently optimize all decision variables in the full tree jointly.
We demonstrate that multistep expected improvement is tractable and exhibits performance superior to existing methods on a wide range of benchmarks.
- Score: 28.46586066038317
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bayesian optimization is a sequential decision making framework for
optimizing expensive-to-evaluate black-box functions. Computing a full
lookahead policy amounts to solving a highly intractable stochastic dynamic
program. Myopic approaches, such as expected improvement, are often adopted in
practice, but they ignore the long-term impact of the immediate decision.
Existing nonmyopic approaches are mostly heuristic and/or computationally
expensive. In this paper, we provide the first efficient implementation of
general multi-step lookahead Bayesian optimization, formulated as a sequence of
nested optimization problems within a multi-step scenario tree. Instead of
solving these problems in a nested way, we equivalently optimize all decision
variables in the full tree jointly, in a ``one-shot'' fashion. Combining this
with an efficient method for implementing multi-step Gaussian process
``fantasization,'' we demonstrate that multi-step expected improvement is
computationally tractable and exhibits performance superior to existing methods
on a wide range of benchmarks.
Related papers
- Bayesian Optimization for Non-Convex Two-Stage Stochastic Optimization Problems [2.9016548477524156]
We formulate a knowledgeient-based acquisition function to jointly optimize the first and second-stage variables.
We show that differences in the dimension and length scales between the variable types can lead to inefficiencies of the twostep algorithm.
arXiv Detail & Related papers (2024-08-30T16:26:31Z) - Voronoi Candidates for Bayesian Optimization [2.7309692684728617]
Many practical BO methods, particularly in high dimension, eschew a formal, continuous optimization of the acquisition function.
We propose to use candidates which lie on the boundary of the Voronoi tessellation of the current design points, so they are equidistant to two or more of them.
We discuss strategies for efficient implementation by directly sampling the Voronoi boundary without explicitly generating the tessellation.
arXiv Detail & Related papers (2024-02-07T14:47:13Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form.
This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method.
A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
arXiv Detail & Related papers (2023-12-28T23:15:18Z) - Random Postprocessing for Combinatorial Bayesian Optimization [0.552480439325792]
We numerically study the effect of a postprocessing method on Bayesian optimization.
We find the postprocessing method significantly reduces the number of sequential steps to find the global optimum.
arXiv Detail & Related papers (2023-09-06T08:59:34Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms.
Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability.
We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
arXiv Detail & Related papers (2023-07-17T20:11:56Z) - Optimistic Optimization of Gaussian Process Samples [30.226274682578172]
A competing, computationally more efficient, global optimization framework is optimistic optimization, which exploits prior knowledge about the geometry of the search space in form of a dissimilarity function.
We argue that there is a new research domain between geometric and probabilistic search, i.e. methods that run drastically faster than traditional Bayesian optimization, while retaining some of the crucial functionality of Bayesian optimization.
arXiv Detail & Related papers (2022-09-02T09:06:24Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients.
We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function.
We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
arXiv Detail & Related papers (2020-12-04T00:26:56Z) - Stochastic Optimization Forests [60.523606291705214]
We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm.
We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
arXiv Detail & Related papers (2020-08-17T16:56:06Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
We present techniques that produce optimal decision trees over a variety of objectives.
We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
arXiv Detail & Related papers (2020-06-15T19:00:11Z) - Global Optimization of Gaussian processes [52.77024349608834]
We propose a reduced-space formulation with trained Gaussian processes trained on few data points.
The approach also leads to significantly smaller and computationally cheaper sub solver for lower bounding.
In total, we reduce time convergence by orders of orders of the proposed method.
arXiv Detail & Related papers (2020-05-21T20:59:11Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.