Going Beyond Global Optima with
Bayesian Algorithm Execution
Willie Neiswanger

Going Beyond Global Optima with
Bayesian Algorithm Execution
Willie Neiswanger

WillieKe Alex Wang

Stefano Ermon

Going Beyond Global Optima with
Bayesian Algorithm Execution
Willie Neiswanger
Extending Bayesian optimizationfrom estimating global optima toestimating other function properties
deﬁned by algorithms

BACKGROUND
Background on Black-box Global Optimization
Suppose we have a noisy “black-box” function f .

Can query f :xBlack-box
function f .

Assume:• Observations are noisy: y ~ f(x) + ε• Each function query is costly-

E.g. in money, time, labor, etc.

• Goal: estimate the location of global optima of f
• Budget of T queriesyBACKGROUND
Black-box Global Optimization — many applications
Hyperparameter Opt & Neural Architecture Search

Systems Auto-tuning

Optimizing Laboratory Equipment & Machines

Materials Discovery & Protocols[1] Korovina, Ksenia, Sailun Xu, Kirthevasan Kandasamy, Willie Neiswanger, Barnabas Poczos, Jeff Schneider, and Eric Xing. "Chembo: Bayesian optimization of small organic molecules with synthesizable recommendations." AISTATS, 2020..
[2] Duris, Joseph, Dylan Kennedy, Adi Hanuka, Jane Shtalenkova, Auralee Edelen, P. Baxevanis, Adam Egger et al. "Bayesian optimization of a free-electron laser." Physical review letters 124, no. 12 (2020): 124801.
[3] Tran, Kevin, Willie Neiswanger, Junwoong Yoon, Qingyang Zhang, Eric Xing, and Zachary W. Ulissi. "Methods for comparing uncertainty quantiﬁcations for material property predictions." Machine Learning: Science and Technology 1, no. 2 (2020): 025006.
[4] Attia et al., “Closed-loop optimization of fast-charging protocols for batteries with machine learning”, Nature, 2020
[5] Char, Ian, Youngseog Chung, Willie Neiswanger, Kirthevasan Kandasamy, Andrew O. Nelson, Mark Boyer, Egemen Kolemen, and Jeff Schneider. "Ofﬂine contextual Bayesian optimization." Advances in Neural Information Processing Systems 32 (2019).
[6] Facebook blog, “Efﬁcient tuning of online systems using Bayesian optimization”, Ben Letham, Brian Karrer, Guilherme Ottoni, Eytan Bakshy, September 27, 2018
[7] Kandasamy, K., Neiswanger, W., Schneider, J., Póczos, B., & Xing, E. P. “Neural architecture search with Bayesian optimisation and optimal transport”. NeurIPS 2018.
[8] Van Aken, Dana, et al. "Automatic database management system tuning through large-scale machine learning." Proceedings of the 2017 ACM International Conference on Management of Data. 2017.

BACKGROUND
A popular method is Bayesian optimization (BO)●

Leverages a probabilistic model of f to sequentially choose queries.

●

The model can:○ incorporate prior beliefs about f (e.g. smoothness)○ tell us where we are certain vs uncertain about f●⇒ Sample efﬁcient optimization.

Probabilistic model of f

Use model to choose queries

BEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:BEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)BEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)
3●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)2
1

Local optima

Top-k optima

Applications- ML model training- HPO / NAS- Systems tuningBEYOND GLOBAL OPTIMA
Estimating other properties●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)Objective 2

In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:Objective 1
Applications- HPO / NAS- Systems tuning- Laboratory equipment / machinesBEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)Applications- Catalyst design- Active learning / weak supervision- Environmental monitoring

BEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)(molecules)

Applications- Drug discovery- Fraud detection- Targeted opinion pollingBEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)(compounds)

Applications- High throughput materials
design/discovery

BEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)(Frazier, 2012)

Applications●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)- Target localization (airborne radar)- Edge detection (computer vision)- Biology / microbiology (phase shifts)

BEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)(Emukit, 2021)

Applications- Probabilistic modeling (marginal
distributions, normalization constants)- Estimating center of mass (andcentroids)

BEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)Applications- Transportation networks- Shipping networks- Social networks

BEYOND GLOBAL OPTIMA
Estimating other properties
In a variety of real-world tasks, there are many other properties of
black-box functions that we also want to estimate:●

Optimization variations (global/local/top-k optima)●

Multi-objective optimization (Pareto frontiers)●

Level set estimation (sublevel sets, superlevel sets)●

Search (subset w/ value matching some criteria)●

Phase identiﬁcation (boundaries / partitions)●

Root ﬁnding / noisy bisection (roots)●

Quadrature (integrals, expectations, averages)●

Graph-structured estimation (shortest paths)●

Sensor placement (function value at set of locations)(Krause et al., 2008)

Applications- Water distribution systems- Outbreak detection in networks- Weather monitoring

BEYOND GLOBAL OPTIMA
Our goal
To develop methods to estimate a broad set of function properties within alimited budget, using probabilistic models.
⇒ Can view this as a generalization of Bayesian optimization to otherfunction properties... beyond global optima.

First question:
How do we formalize “other function properties” ?

ALGORITHMS w/o BUDGET CONSTRAINTS
Note that, given a function property of interest...
Often exists effective algorithms for computing (or numericallyapproximating) the property, if you ignore budget constraintALGORITHMS w/o BUDGET CONSTRAINTS
Note that, given a function property of interest...
Often exists effective algorithms for computing (or numericallyapproximating) the property, if you ignore budget constraint
Property: local optima (close to some initial point) of f

ALGORITHMS w/o BUDGET CONSTRAINTS
Note that, given a function property of interest...
Often exists effective algorithms for computing (or numericallyapproximating) the property, if you ignore budget constraint
Property: local optima (close to some initial point) of f
Algorithm: local optimization algorithme.g. gradient descent, Nelder-Mead method,evolutionary algorithm, etc.

Evolution Strategy

ALGORITHMS w/o BUDGET CONSTRAINTS
Note that, given a function property of interest...
Often exists effective algorithms for computing (or numericallyapproximating) the property, if you ignore budget constraint
Property: local optima (close to some initial point) of f
Algorithm: local optimization algorithme.g. gradient descent, Nelder-Mead method,evolutionary algorithm, etc.

⇒ initialize at some location, then run local minimizer. Return ﬁnal query as output.

init

end

ALGORITHMS w/o BUDGET CONSTRAINTS
Note that, given a function property of interest...
Often exists effective algorithms for computing (or numericallyapproximating) the property, if you ignore budget constraint
Property: superlevel set of f (e.g. over a discrete space of items).

ALGORITHMS w/o BUDGET CONSTRAINTS
Note that, given a function property of interest...
Often exists effective algorithms for computing (or numericallyapproximating) the property, if you ignore budget constraint
Property: superlevel set of f (e.g. over a discrete space of items).
Algorithm: scan and threshold.
⇒ Scan through each item

Superlevel
Set, query its value, return subset of items above threshold.

ALGORITHMS w/o BUDGET CONSTRAINTS
Note that, given a function property of interest...
Often exists effective algorithms for computing (or numericallyapproximating) the property, if you ignore budget constraint
Property: integral or expectation of f.

ALGORITHMS w/o BUDGET CONSTRAINTS
Note that, given a function property of interest...
Often exists effective algorithms for computing (or numericallyapproximating) the property, if you ignore budget constraint
Property: integral or expectation of f.
Algorithm: numerical integration (e.g. rectangle/trapezoidal approximation).
⇒ Run numerical integration (e.g. rectangle/trapezoidal approximation). Return approximate integral
over region.

DEFINITIONS
Deﬁnition: computable function property
The output of a given algorithm A, if it were run on our black-box function f.
⇒ E.g. previous properties are all computable function properties:
local optima, integrals, level sets, Pareto frontiers, partitions — and many others,deﬁned by an algorithm!

DEFINITIONS
Deﬁnition: computable function property
The output of a given algorithm A, if it were run on our black-box function f.
⇒ E.g. previous properties are all computable function properties:
local optima, integrals, level sets, Pareto frontiers, partitions — and many others,deﬁned by an algorithm!

Deﬁnition: Bayesian algorithm execution (BAX)The task of estimating a computable function property (output of analgorithm A), using a budget of only T queries to f.
(Even if algorithm A requires far more than T queries.)

DEFINITIONS
Deﬁnition: computable function property
The output of a given algorithm A, if it were run on our black-box function f.
⇒ E.g. previous properties are all computable function properties:
local optima, integrals, level sets, Pareto frontiers, partitions — and many others,deﬁned by an algorithm!

Deﬁnition: Bayesian algorithm execution (BAX)The task of estimating a computable function property (output of analgorithm A), using a budget of only T queries to f.
(Even if algorithm A requires far more than T queries.)

Note: two main reasons to frame function property in terms of an algorithm:(1) gives a ﬂexible way to deﬁne function properties.
(2) we will use algorithm in our procedure to estimate these properties.

BAYESIAN ALGORITHM EXECUTION

Methods for BAXBAYESIAN ALGORITHM EXECUTION
Information-based method for BAX
InfoBAX — an algorithm for BAX, based on info-theoretic methods for BO.

BAYESIAN ALGORITHM EXECUTION
Information-based method for BAX
InfoBAX — an algorithm for BAX, based on info-theoretic methods for BO.

Some relevant backgroundSome BOED History

There exist a few popular info-based methods for BO:-

E.g. entropy search (ES), predictive ES, max-value ES.
Rooted in Bayesian optimal experimental design (BOED).

BOED: have model with an (unknown) parameter of interest.
-

Choose experiments that most reduce uncertainty about parameter.
Uncertainty: entropy of posterior distribution over parameter.
Lower entropy

Higher entropy

Reducing theodolite
measurements forsurveying.

BAYESIAN ALGORITHM EXECUTION
Information-based method for BAX
InfoBAX — an algorithm for BAX, based on info-theoretic methods for BO.

Some relevant backgroundSome BOED History

There exist a few popular info-based methods for BO:-

E.g. entropy search (ES), predictive ES, max-value ES.
Rooted in Bayesian optimal experimental design (BOED).

BOED: have model with an (unknown) parameter of interest.
-

Choose experiments that most reduce uncertainty about parameter.
Uncertainty: entropy of posterior distribution over parameter.

To describe InfoBAX:(1)(2)

Describe info-based BO.
Extend it to info-based BAX.

Reducing theodolite
measurements forsurveying.

INFO-BASED BO
Information-based Bayesian Optimization

INFO-BASED BO
Information-based Bayesian Optimization

Initial dataset of (x, y) pairs (function
observations) — can be empty set.

INFO-BASED BO
Information-based Bayesian Optimization

Over a sequence of T iterations:INFO-BASED BO
Information-based Bayesian Optimization

Optimize an acquisition function.
- aims to capture value of querying f at an x.
- deﬁned using our probabilistic model.
⇒ Chooses next x to query.

INFO-BASED BO
Information-based Bayesian Optimization

Query f on chosen x, observe yINFO-BASED BO
Information-based Bayesian Optimization

Update dataset with new (x, y) pair

INFO-BASED BO
Information-based Bayesian Optimization
Visualizing this ...

BACKGROUND(unknown)

black-box
function fdatasetDt = {(x, y)}Unknown black-box f , and dataset of (x, y) pairs.

BACKGROUND

Samples fromposterior
distribution
over functions

Can use probabilistic model to infer f , given dataset.

BACKGROUNDαt(x)Deﬁne acquisition function using probabilistic model.

BACKGROUNDαt(x)Optimize acquisition function ⇒ yields next point to query.

BACKGROUND

New
observation(x, y)

Query black-box f at x, observe y, and update dataset.

INFO-BASED BO
Information-based Bayesian Optimization… Key step is line 2: deﬁning and optimizing acquisition function.

INFO-BASED BO
Acquisition function — info-based BO

Samples fromposterior
distribution
over functions

Probabilistic model of f , given dataset.

INFO-BASED BO
Acquisition function — info-based BO

Samples fromposterior
distribution
over functions

Consider the
global optima ofeach sample...

Probabilistic model of f , given dataset.

INFO-BASED BO
Acquisition function — info-based BO

Samples fromposterior
distribution
over functions

Consider the
global optima ofeach sample...

Probabilistic model of f , given dataset.

INFO-BASED BO
Acquisition function — info-based BO

There is a posterior distribution
over global optima induced byprobabilistic model:

Samples fromposterior
distribution
over functions

Consider the
global optima ofeach sample...

Probabilistic model of f , given dataset.

INFO-BASED BO
Acquisition function — info-based BO
This leads us to the acquisition function:e.g. used in entropy search (ES), predictive entropy search (PES)INFO-BASED BO
Acquisition function — info-based BO
This leads us to the acquisition function:e.g. used in entropy search (ES), predictive entropy search (PES)

entropy of posterior distribution overglobal optima x*
minus

expected entropy of posterior
distribution over global optima x* ,… if we were to make a query at x

INFO-BASED BO
Acquisition function — info-based BO
This leads us to the acquisition function:e.g. used in entropy search (ES), predictive entropy search (PES)

entropy of posterior distribution overglobal optima x*

expected entropy of posterior
distribution over global optima x* ,… if we were to make a query at x

minus

“Expected information gain” (EIG) — expected decrease in entropy if we were to query f
at x.

There exists a clever way to compute/optimize this (from work on PES)…

INFO-BASED BO
Acquisition function — info-based BO
How to compute and optimize it? Two stages:

INFO-BASED BO
Acquisition function — info-based BO
How to compute and optimize it? Two stages:
1) Before acquisition optimization:2) Acquisition optimization:-

Generate posterior samples ofglobal optima.

-

For any x, approximate EIG
αt(x) using these samples.

-(⇒ run optimization algorithm on
function samples to get optima).

-

Allows us to optimize acquisition
function.

Beneﬁts: generate samples only once. Then cheaper during iterative acquisition opt.

BAYESIAN ALGORITHM EXECUTION(previous was existing work, following is new)What acquisition function do we use for InfoBAX?

Recall goal of BAX:
- Estimate a computable function property using a limited budget of
queries.
- (equivalently: Estimate output of algorithm A.)

BAYESIAN ALGORITHM EXECUTION(previous was existing work, following is new)What acquisition function do we use for InfoBAX?

Recall goal of BAX:
- Estimate a computable function property using a limited budget of
queries.
- (equivalently: Estimate output of algorithm A.)

Similar to info-based BO, take a BOED strategy:-

Denote the output of algorithm A (computable function property):-

We care about posterior over output:-

And its entropy:
Want to make queries to best
reduce this uncertainty overalgorithm output.

BAYESIAN ALGORITHM EXECUTIONInfoBAX acquisition function

Can also deﬁne an expected information gain (EIG) acquisition function:

BAYESIAN ALGORITHM EXECUTIONInfoBAX acquisition function

Can also deﬁne an expected information gain (EIG) acquisition function:

entropy of posterior distribution overalgorithm output

expected entropy of posterior
distribution over algorithm output,… if we were to make a query at x

minus

“Expected decrease in entropy on the algorithm output, if we were to query f at x.”

BAYESIAN ALGORITHM EXECUTIONInfoBAX acquisition function

Can also deﬁne an expected information gain (EIG) acquisition function:

entropy of posterior distribution overalgorithm output

expected entropy of posterior
distribution over algorithm output,… if we were to make a query at x

minus

“Expected decrease in entropy on the algorithm output, if we were to query f at x.”… how can we compute (and optimize) this?

BAYESIAN ALGORITHM EXECUTION
Deﬁnition:
Deﬁne the execution path of algorithm A as the sequence of queries( (x, y) pairs) that A would make on the black-box function f.
Local Optima

Superlevel Set

BAYESIAN ALGORITHM EXECUTION
Deﬁnition:
Deﬁne the execution path of algorithm A as the sequence of queries( (x, y) pairs) that A would make on the black-box function f.
Local Optima

Superlevel Set

Execution path = pink dots

BAYESIAN ALGORITHM EXECUTION
Deﬁnition:
Deﬁne the execution path of algorithm A as the sequence of queries( (x, y) pairs) that A would make on the black-box function f.
Local Optima

Superlevel Set

Execution path = pink dots

Note: we don’t know true execution path.
-(Since we are not running A on f ⇒ this require too many queries)-

But given a model for f, we have a posterior distribution over execution paths

INFO-BASED BO
InfoBAX acquisition function

Probabilistic model of f , given dataset.

INFO-BASED BO
InfoBAX acquisition function

Consider one function sample

INFO-BASED BO
InfoBAX acquisition function

Consider one function sample
Can run algorithm A
on function sample...

INFO-BASED BO
InfoBAX acquisition function

Consider one function sample
Execution path ofalgorithm A on sample.

INFO-BASED BO
InfoBAX acquisition function

Consider one function sample
Execution path ofalgorithm A on sample.

Can do this on
many samples.

INFO-BASED BO
InfoBAX acquisition function

Consider one function sample
Execution path ofalgorithm A on sample.

Can do this on
many samples.

There is a posterior distribution
over execution paths induced byprobabilistic model.

BAYESIAN ALGORITHM EXECUTIONInfoBAX acquisition function
How to compute and optimize it? Two stages:

Similar to info-based BO!

BAYESIAN ALGORITHM EXECUTIONInfoBAX acquisition function
How to compute and optimize it? Two stages:
1) Before acquisition optimization:-

Run algorithm A on posterior
function samples to get
posterior samples ofexecution path.

Similar to info-based BO!

2) Acquisition optimization:-

For any x, approximate EIG
αt(x) using these samples-

Allows us to optimize acquisition
function⇒ Similar structure as info-based BO, but replace global opt algorithm with A.
-

Same beneﬁts: generate samples only once. Then cheaper during iterative acquisition opt.

⇒ Look in paper for math on computing EIG αt(x) with samples.

INFO-BASED BO
Information-based Bayesian Optimization(1) Run algorithm on posterior function samples.
(2) Optimize αt(x) using resulting execution paths.

INFO-BASED BO
InfoBAX — one-slide summary of the full story

INFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestfINFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestflevel set

INFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestfinﬂectionpoint

INFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestf0

integralINFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interest

f

local
minimaINFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestfSuppose property is computable ⇒there exists an algorithm A (of any budget)
start

local
minimaend

INFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestfSuppose property is computable ⇒there exists an algorithm A (of any budget)
start

local
minimaend⇒ Goal: estimate the property (i.e. output of A) with minimal function queries

INFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestfSuppose property is computable ⇒there exists an algorithm A (of any budget)
start

local
minimaend⇒ Goal: estimate the property (i.e. output of A) with minimal function queries
Run InfoBAX, a sequential algorithm(similar in structure to BO)

INFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestfSuppose property is computable ⇒there exists an algorithm A (of any budget)
start

local
minimaend⇒ Goal: estimate the property (i.e. output of A) with minimal function queries
Run InfoBAX, a sequential algorithm(at each iteration) To optimize InfoBAX(similar in structure to BO)

acquisition function: two stages
1

INFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestfSuppose property is computable ⇒there exists an algorithm A (of any budget)
start

local
minimaend⇒ Goal: estimate the property (i.e. output of A) with minimal function queries
Run InfoBAX, a sequential algorithm(at each iteration) To optimize InfoBAX(similar in structure to BO)

acquisition function: two stages
2

INFO-BASED BO
InfoBAX — one-slide summary of the full story
Suppose we have a black-box function fand a property of interestfSuppose property is computable ⇒there exists an algorithm A (of any budget)
start

local
minimaend⇒ Goal: estimate the property (i.e. output of A) with minimal function queries
Run InfoBAX, a sequential algorithm(at each iteration) To optimize InfoBAX(similar in structure to BO)

acquisition function: two stages
2⇒ Output: posterior estimate of property (i.e. output of A)

BAYESIAN ALGORITHM EXECUTION

BAX: Demos and Applications

APPLICATIONS of BAX
Applications
We demo BAX to estimate a few different properties of black-box functions(trying to show the breadth of what we can estimate)Three applications:-

Estimating shortest paths in graphs
Bayesian local optimization
Estimating top-k optima

Black-box function overedges in a network
Optimization variants

APPLICATIONS of BAX
Application: estimating shortest paths in graphs
Graph traversal/search algorithms can deﬁne properties of a black-box
function f deﬁned on edge weights in a graph.

Example: real-world transportation network(e.g. road, railway, shipping, air)-Suppose we want to ﬁnd shortest path from location A
to location B.

-

Shortest path depends on edge weights.
--

It can be expensive to query edge weights--

e.g. trafﬁc, road conditions, weather, etc.
e.g. measure trafﬁc/road/weather conditions via satellite.
e.g. determine/access shipping costs.

Goal: adaptively query edge weights to estimate
shortest path.

California road network.

APPLICATIONS of BAX — estimating shortest paths in graphs

Grid-shaped
graph:-

400 nodes
2964 edges

APPLICATIONS of BAX — estimating shortest paths in graphs

Edge weights
are given byfunction f(green).

APPLICATIONS of BAX — estimating shortest paths in graphs

Want to know
shortest path
between startand goal.

APPLICATIONS of BAX — estimating shortest paths in graphs

Want to know
shortest path
between startand goal.

APPLICATIONS of BAX — estimating shortest paths in graphs

Want to know
shortest path
between startand goal.

Can view this shortest path
as a function property!

APPLICATIONS of BAX — estimating shortest paths in graphs

Suppose thataccessing(querying)edge weights
is expensive.
→ e.g. intransportation
network
examplesAPPLICATIONS of BAX — estimating shortest paths in graphs

Suppose thataccessing(querying)edge weights
is expensive.
→ e.g. intransportation
network
examples

How to estimate
shortest path?
One strategy:
use Dijkstra’salgorithm

APPLICATIONS of BAX — estimating shortest paths in graphs

One strategy:
use Dijkstra’salgorithm
Exactly
computes theshortest path

Blue line = shortest path
(output of Dijkstra’s)

APPLICATIONS of BAX — estimating shortest paths in graphs

One strategy:
use Dijkstra’salgorithm
Exactly
computes theshortest path
However…
requires over
430 queries!
Can try adifferent
strategy...
Blue line = shortest path
(output of Dijkstra’s)

APPLICATIONS of BAX — estimating shortest paths in graphs

Suppose we
take small set ofedge weight
queries(e.g. 30 unif-random)

Could try toinfer shortest
path fromthese

APPLICATIONS of BAX — estimating shortest paths in graphs

Suppose we
take small set ofedge weight
queries(e.g. 30 unif-random)

Could try toinfer shortest
path fromthese
We’ll do the following:(1) Use a model to infer f(e.g. GP), given queries.
(2) Run Dijkstra’s onposterior function
samples.

APPLICATIONS of BAX — estimating shortest paths in graphs

Posteriorsamples ofshortest path
(output of Dijkstra’s)

via GP modelAPPLICATIONS of BAX — estimating shortest paths in graphs

Posteriorsamples ofshortest path
(output of Dijkstra’s)

via GP model

Estimate after
100 queries?

APPLICATIONS of BAX — estimating shortest paths in graphs

Posteriorsamples ofshortest path
(output of Dijkstra’s)

via GP model

Estimate after
100 queries?

Many uninformative queries.

APPLICATIONS of BAX — estimating shortest paths in graphs

Posteriorsamples ofshortest path
(output of Dijkstra’s)

via GP model

Goal:
Choose queries to best

Estimate
afterpath (ieinfer shortest
100
queries?
outputof Dijkstra’s).

⇒ InfoBAX w/ Dijkstra’s.

APPLICATIONS of BAX — estimating shortest paths in graphs

InfoBAX inaction →APPLICATIONS of BAX — estimating shortest paths in graphs

InfoBAX inaction →APPLICATIONS of BAX — estimating shortest paths in graphs

InfoBAX inaction →After 100
queries.

APPLICATIONS of BAX — estimating shortest paths in graphs
Comparison after 100 queries:

Random Search

Dijkstra’s

InfoBAXAPPLICATIONS of BAX
Application: Bayesian local optimization

APPLICATIONS of BAX
Application: Bayesian local optimization
BO (typically) aims to estimate global optima.
However, many local optimization algorithms only aim to ﬁnd a local optima(nearby some initial point)-e.g. gradient descent, evolutionary algorithms, nelder-mead/simplex, etc.

Local opt can be very effective for certain settings (e.g. high dimensions),
but can require large numbers of queries.
-

Sometimes many redundant queries.
Not effective if each query is very expensive.

We can use the local opt algorithms in a BAX procedure.
-⇒ Yields local variants of BO parameterized by a local opt algorithm.

Overall intuition — view optimization as:-

Trying to estimate the output of a local opt algo, given limited budget of queries.

APPLICATIONS of BAX — Bayesian local optimization
After 208
queries

Two dimensional function,w/ three local optima

APPLICATIONS of BAX — Bayesian local optimization
After 208
queries

After 18
queries

Two dimensional function,w/ three local optima

APPLICATIONS of BAX — Bayesian local optimization

InfoBAX matches performance of Evolution Strategy, using <10% of the queries.

Future steps: try this out with a variety of local optimizers.

APPLICATIONS of BAX — top-k estimation
Application: top-k estimation
Suppose we have a large set of items.
-

E.g. set of 500 catalyst materials / bulks.

Each item has a value under an expensive black-box function f.
-

E.g. each catalyst bulk has an activity level, which is expensive to measure (simulate).

Suppose we want to determine the top-k items in the set.
-

E.g. the top-10 catalysts, with highest activity ⇒ for experimental evaluation.
(These top-k might then be ﬁltered further based on additional tests)⇒ distinct from both global optimization (k=1) and level set estimation.

Visualizing this…

APPLICATIONS of BAX — top-k estimation

250 items

APPLICATIONS of BAX — top-k estimation

250 items

Black-box
function f(green).

APPLICATIONS of BAX — top-k estimation

250 items

Black-box
function f(green).

Stars denote
top-10 items

APPLICATIONS of BAX — top-k estimation

Algorithm: scanthrough each
item and query;
return top-k

APPLICATIONS of BAX — top-k estimation
Scan and Query Algorithm (full)
Algorithm yields
perfect estimate

APPLICATIONS of BAX — top-k estimation
Scan and Query Algorithm (full)
Algorithm yields
perfect estimate

However: uses 250
queriesAPPLICATIONS of BAX — top-k estimation

New strategy:
Make a few
queries and infertop-10 items

APPLICATIONS of BAX — top-k estimation

New strategy:
Make a few
queries and infertop-10 items

10 queries(black dots)

APPLICATIONS of BAX — top-k estimation

New strategy:
Make a few
queries and infertop-10 items

Posteriorsamples of
top-10 items(blue squares)

Estimate is prettybad

10 queries(black dots)

APPLICATIONS of BAX — top-k estimation

New strategy:
Make a few
queries and infertop-10 items

How about 100
uniform random
queries?

Posteriorsamples of
top-10 items(blue squares)

10 queries(black dots)

APPLICATIONS of BAX — top-k estimation

New strategy:
Make a few
queries and infertop-10 items

Posteriorsamples of
top-10 items(blue squares)

Estimate is still not
great

100 queries(black dots)

APPLICATIONS of BAX — top-k estimation

New strategy:
Make a few
queries and infertop-10 items

Posteriorsamples of
top-10 items(blue squares)

Estimate is still not
great
Try InfoBAX with“scan and query”
algorithm

100 queries(black dots)

APPLICATIONS of BAX — top-k estimation
InfoBAX
Good estimate
in <100 queries

InfoBAX explores
the space but
samples densely
around high-value
items.

UNCERTAINTY MODELS
Final topic: software tools for uncertainty models
The BAX/BO procedures discussed all use predictive uncertainty models.
“A model of the conditional distribution over output y given an input x”

UNCERTAINTY MODELS
Final topic: software tools for uncertainty models
The BAX/BO procedures discussed all use predictive uncertainty models.
“A model of the conditional distribution over output y given an input x”⇒ in BAX we focus on GP models, but we may wish to run similar procedures
on a variety of probabilistic models (and to know if our models are good)UNCERTAINTY MODELS
Final topic: software tools for uncertainty models
The BAX/BO procedures discussed all use predictive uncertainty models.
“A model of the conditional distribution over output y given an input x”⇒ in BAX we focus on GP models, but we may wish to run similar procedures
on a variety of probabilistic models (and to know if our models are good)

Types of uncertainty models:“Classic” Bayesian models: GPs, various (non)lin/hier/add
or other Bayesian models
Neural models: probabilistic neural networks, BNN,
neural processes, deep generative models
Also: ensembles, quantile regression, conformal
prediction, etc.

ASSESSING UNCERTAINTY
How can we assess quality of predictive uncertainty?

ASSESSING UNCERTAINTY
How can we assess quality of predictive uncertainty?
We can visualize point-predictions and predictive uncertainties on a given test set.

For each test point, plot predictions vs. ground truth values:

Predictive
uncertainty model

Predictions

Predictions

Point prediction
model

Ground truth

Uncertainty for point
prediction: interval,
parametric distribution,
samples, etc.

Ground truth

ASSESSING UNCERTAINTY
How can we empirically assess predictive uncertainty?
Three important criteria are...

ASSESSING UNCERTAINTY
How can we empirically assess predictive uncertainty?
Three important criteria are...

Predictions“How good is mean prediction?
(agnostic to uncertainty)”

Predictions

Accuracy:

Ground truth

Ground truth

Ground truth

Ground truth

Ground truth

Ground truth

Predictions“Is predictive uncertainty
distribution empirically correct?
(ignoring prediction accuracy)”

Observed fraction in interval

Calibration:

Predictions

Sharpness:“On average, how conﬁdent are thepredictions? (ignoring both of theabove)”

Ground truth

Expected fraction in interval

ASSESSING UNCERTAINTY
How can we empirically assess predictive uncertainty?
Three important criteria are...

Predictions“How good is mean prediction?
(agnostic to uncertainty)”

Predictions

Accuracy:

Ground truth

Ground truth

Ground truth

Ground truth

Ground truth

Ground truth

Predictions“Is predictive uncertainty
distribution under/over conﬁdent?
(ignoring prediction accuracy)”

Observed fraction in interval

Calibration:

Predictions

Sharpness:“On average, how conﬁdent are thepredictions? (ignoring both of theabove)”

Ground truth

Expected fraction in interval

ASSESSING UNCERTAINTY
How can we empirically assess predictive uncertainty?
Three important criteria are...

Predictions“How good is mean prediction?
(agnostic to uncertainty)”

Predictions

Accuracy:

Ground truth

Ground truth

Ground truth

Ground truth

Ground truth

Ground truth

Predictions“Is predictive uncertainty
distribution under/over conﬁdent?
(ignoring prediction accuracy)”

Observed fraction in interval

Calibration:

Predictions

Sharpness:“On average, how conﬁdent are thepredictions? (ignoring both of theabove)”

Ground truth

Expected fraction in interval

ASSESSING UNCERTAINTYMetrics for calibration
Suppose for each test point, our predictive uncertainty model returns a (1-𝛼)-interval (e.g. 95% interval)of the predictive distribution.
Well-calibrated ⇒ “the (1-𝛼)-interval covers the true value (1-𝛼)-proportion of the time, for all 𝛼”

ASSESSING UNCERTAINTYMetrics for calibration
Suppose for each test point, our predictive uncertainty model returns a (1-𝛼)-interval (e.g. 95% interval)of the predictive distribution.

Predictions

Well-calibrated ⇒ “the (1-𝛼)-interval covers the true value (1-𝛼)-proportion of the time, for all 𝛼”Ground truth

Ground truth

𝛼 = 0.05 (95% intervals)

ASSESSING UNCERTAINTYMetrics for calibration
Suppose for each test point, our predictive uncertainty model returns a (1-𝛼)-interval (e.g. 95% interval)of the predictive distribution.
Well-calibrated ⇒ “the (1-𝛼)-interval covers the true value (1-𝛼)-proportion of the time, for all 𝛼”

Predictions

Observed fraction in interval

Miscalibration Area

Ground truth

Ground truth

0

Expected fraction in interval 1

Can scan from 𝛼=0 to 𝛼=1, and compute:(1) expected fraction of true values contained in interval(2) observed fraction of true values contained in interval

UNCERTAINTY TOOLBOX
Uncertainty Toolbox• To help assess uncertainty quantiﬁcation methods, we released Uncertainty Toolbox.
• “A python toolbox for predictive uncertainty quantiﬁcation, calibration, metrics, andvisualization” → github.com/uncertainty-toolbox/uncertainty-toolbox

Collaborators
Kevin
Tran

Young
Chung

Glossary
Metrics / Viz

Ian
Char

Recalibration
Relevant Papers

Han
Guo

CONCLUSION

CONCLUSION

In summary…
We extend Bayesian optimization from targeting global optima to targetingother function properties deﬁned by algorithms.
⇒ Introduce the task of BAX,
and the information-based procedure InfoBAX
Paper link: arxiv.org/abs/2104.09460
Uncertainty Toolbox: github.com/uncertainty-toolbox/uncertainty-toolbox
Thanks for listening!