Bayesian Optimization with Categorical andContinuous Variables
Dr Vu Nguyen
Machine Learning Scientist@nguyentienvu
Vu Nguyen

vu-nguyen.org
1Outline
Bayesian optimisation and Illustration
Mixed categorical-continuous optimisation
Mixed optimization in high dimensional space
Mixed optimization in population-based AutoRL

2

Hyperparameters Optimization
ML algorithm’s performances depend on hyperparameters.
Finding the best hyperparameters for the highest performance3

Traditional Hyperparameters Tuning
Grid Search:
Create a list of values for each parameter.
Consider all possible combinations of these values.
Exhaustively evaluate the model and choose thebest parameter.

Random Search:
Randomly select a parameter to evaluate.
Select the best parameter.

4

Grid vs Random vs Bayesian Optimization

Grid Search

Random Search

Bayesian Optimization

best hyperparameter5

Grid vs Random vs Bayesian Optimization

Missedoptimum location

Grid SearchMissedoptimum location

Random SearchFound
optimum location

Bayesian Optimization

6

Blackbox optimisation competition at NeurIPS20
The top 20 teams uses Bayes Opt.

https://bbochallenge.com/leaderboard

7Black-box Optimization
The relationship from
Input

tois through the black-box.
OutputBlack-box𝑓(𝑥)looking for this maximizer

Outputunknown

Input
8Properties of Black-box Function

input

outputFunction form is not known
No derivative form
Expensive to evaluate (in time and cost)
Nothing is known about the function, except a few evaluations
9

Bayesian Optimization Overview
RefineMake a series of evaluations
Find the optimum using few evaluations

outputBayes Opt
input

Acquisition function

exploitfunction belief

exploreuncertainty

Surrogate function10

Illustration of Bayes Opt (3 points)
Given 3 initial observations
the unknown
maximizer

Accuracy=6

black-box function(unknown)=0.78
Learning rate11

Illustration of Bayes Opt (3 points)
Given 3 initial observations

where to evaluate next?
?

?

?

?

Accuracy?

Learning rate12

Illustration of Bayes Opt (4 points)
RefineoutputBlack-box𝑓(𝑥)Bayes Opt

Accuracy

input

Suggested Experiment
Learning rate13

Illustration of Bayes Opt (5 points)

Accuracy

Suggested Experiment

Learning rate14

Illustration of Bayes Opt (6 points)

AccuracySuggested Experiment

Learning rate15

Illustration of Bayes Opt (7 points)

Accuracy

Suggested Experiment

Learning rate16

Illustration of Bayes Opt (8 points)
Hits the optimum

less samples
poor locations
Accuracy

more samples
promising locations

Bayes Opt finds the global optimum,
using fewest evaluations.
Learning rate17

Outline
Bayesian optimisation and Illustration
Mixed categorical-continuous optimisation
Mixed optimization in high dimensional space
Mixed optimization in population-based AutoRL

18

Bayes Opt Mixed Categorical – Continuous Input
Tuning hyperparameters for deep neural network
continuous variables

learning rate

weight decay

categorical variables

optimiser typeactivation type19

Bayes Opt Mixed Categorical – Continuous Input
One-hot encoding:
Red: [1,0,0]Green: [0,1,0]

Blue: [0,0,1]

Drawbacks:
Make the search space large.
if
4 categories, each has
choices=>Non-continuous and non-differentiable spaceextra dimensions.

Challenging in optimizing mixed-type: categorical - continuous

20Bayes Opt Mixed Categorical – Continuous Input
continuous

learning rate

weight decay

Bayes Opt

categoricaloptimiser typeactivation typeMulti-armed Bandit

21

Two settings in mixed variables optimization
1. Continuous variable is specific to categorical variable

2. Continuous is sharing across categorical variables

22

Two settings in mixed variables optimization
1. Continuous variable is specific to categorical variable
Category 1

RBF

Kernel parameter is specificto the kernel type.

lengthscale

Category 2

Category 3

Polynomial

Linearcategoricaldegreenone

continuous

dimensions for the continuous: 1 or 2 ?

ACML 2020 Tutorial - Recent Advances in
Bayesian Optimization

23

Two settings in mixed variables optimization
1. Continuous variable is specific to categorical variable
RBF

Polynomial

Linear

2. Continuous is sharing across categorical variables
Learning rate in DL is sharing across activation types
categorical
Cat 1Cat 2

Cat 3

continuousACML 2020 Tutorial - Recent Advances in
Bayesian Optimization

continuous
24

Two settings in mixed variables optimization
1.

Continuous variable is specific to categorical variable
RBF

Polynomial

Linear• Independent/local functions

2.

Continuous is sharing across categorical variables

Cat 1 Cat 2

continuousCat 3• Global function

ACML 2020 Tutorial - Recent Advances in
Bayesian Optimization

25

Algorithm overview
Optimize
categorical

MAB

Optimize continuousgiven

Bayes OptObserve the feedback

26

OptimizeMABby multi-armed bandits
Bandit arms to be pulled

BO

Cat A

Observe

Rewardprob

RMSProp

Adam

SGD

|

Cat B

Cat C

Multiple categories

27

Setting (1): continuous is categorical-specific
MAB

BO

Select |by BO|

h=RBF

Polynomial

LinearIgnoreIgnoreObserve

S. Gopakumar, S. Gupta, S. Rana, V. Nguyen, & S. Venkatesh. Algorithmic assurance: An active approach to algorithmic testing using BO. NeurIPS’18

28

Setting (2): continuous shared across categories
MABBO|

Using Bayes Opt to find in a global
space across all categories .
Joint kernel for bothandAdditive
MultiplicativeObservecan be estimated from the data.
B. Ru, A. Alvi, V. Nguyen, M. Osborne, & S. Roberts. Bayesian optimisation over multiple continuous and categorical inputs. ICML’2029

Visualization of the Algorithm
CategoricalContinuous

RBF

Polynomial

LinearMAB

Bayes Opt

Concentrate on Polynomialwith higher (expected) value.

30

Outline
Bayesian optimisation and Illustration
Mixed categorical-continuous optimization
Mixed optimization in high dimensional space
Mixed optimization in population-based AutoRL

31

Mixed optimization with 200 dimensions ?
High dimension causes problem for optimization.
Statistical challenge: the search space grows exponentially
Computational challenge: global optimizers fail to return an optimum
within limited time and resource

32Local Trust Optimization
Build multiple trust regions
Perform local optimization in eachtrust region
The local region is narrower for thelocal optimizer to be successful

Eriksson et al. "Scalable global optimization via local Bayesian optimization." NeurIPS’19

Trust regions

33

Local Trust Optimization
Iteratively
expand the trust region for exploration if successes
shrink the trust region for exploitation if failuresterminate and randomly jump to another region if local search is exhausted
exploration

Given limited observations, the GP estimation is more accurate within a local region
34

CASMOPOLITAN
Extending local trust idea for mixed categorical-continuous variables
Separate trust regions: categorical and continuous, defined from the best
seen location

After a local search is exhausted, a new trust region is selected using the UCB
exploit promising region

explore region with high uncertainty
X. Wan, V. Nguyen, H. Ha, B. Ru, C. Lu, and M. Osborne. "Think Global and Act Local: Bayes Opt over High-Dimensional Categorical and Mixed Search Spaces." ICML’2135

Illustration of Updating Trust Region CenterAt unseen nodes:(i) Predict the expected function
value and uncertainty(ii) Calculate acq func value

Exploit/explore to select thehighest value node to querythe black-box

Update trust region centerRebuild the local trust region36Illustration of the algorithm in the mixed space
Iteratively expand, shrink and restart the local search

Natural extension to handle parallelism

https://github.com/xingchenwan/Casmopolitan

37Outline
Bayesian optimisation and Illustration
Mixed categorical-continuous optimisation
Mixed optimization in high dimensional space
Mixed optimization in population-based AutoRL

38

Population Based Training (PBT)

Agent 1 (CPU 1)(Neural network 1)

Agent 2 (CPU 2)(Neural network 2)

Agent 3 (CPU 3)(Neural network 3)

Parallel agents
39Population Based Training (PBT)
trained for a
few iterations

each agent receives a (different)
hyperparameter to train

poor-performing agentswill be terminatedParallel agentshigh-performing agentswill continue

Deep learning training process40

Population Based Training
Terminates poor-performing agents and restarts by:• Copies a network weight from the best-performing agent.
• Generate a new hyperparameter by randomly perturb from the best agent.
At the end of this single training process, we obtain the “well-trained” model.

41

Two Key Advantages of PBTLearning a schedule of hyperparameters, such as selecting large
learning rate at the beginning and smaller at the later stage.
Existing HPO: a single set of hyperparameters are fixed during training.
PBT: perfectly adapts the hyperparameters.

Time efficiency:
Existing HPO: repeatedly evaluate the black-box with different hypers.
PBT: uses a single training run.

42

Population Based Bandit (PB2)PB2 is an extension of Population Based Training (PBT).
The hyperparameters update is controlled by time-varying
Gaussian process bandit optimization.
initial reward(constant)

final reward𝒕 : hyperparameter at iteration

reward improvement
between 2 timesteps

reward improvement
between 2 timesteps

Maximizing final reward = Minimizing cumulative regret
J. Parker-Holder, V. Nguyen, and S. Roberts. "Provably efficient online hyperparameter optimization with population-based bandits." NeurIPS’20

43

Population Based Bandit (PB2)PB2 is deployed in Ray Tune library (18k users).
Import PB2 from Ray and try in a few line of codes.

J. Parker-Holder, V. Nguyen, and S. Roberts. "Provably efficient online hyperparameter optimization with population-based bandits." NeurIPS’20

44

PB2-Mix
PB2 is only applicable for continuous variables.
PB2-Mix extends PB2 to handle mixed categ-cont variables
MABTime-varying& Parallel

BO|𝐴 𝐴 𝐴Observe

MABTime-varying& ParallelBO|Time-varying & Parallel
𝐴𝐴𝐴

Observe
Existing works

PB2-Mix

J. Parker-Holder, V. Nguyen, S. Desai, and S. Roberts. "Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL." NeurIPS’21

45

Time-varying Parallel Extension of MAB and BO
Time-varying& Parallel
MAB𝐴𝐴

Time-varying& Parallel
BO|𝐴Observe

Propose Time-varying and Parallel MAB to select categorical variables
Time-varying parallel BO has been available in PB2J. Parker-Holder, V. Nguyen, S. Desai, and S. Roberts. "Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL." NeurIPS’21

46

TV.EXP3.M
Time-varying and Parallel TV.EXP3.M to select categorical variable
EXP3 is a popular algorithm in multi-armed bandits
EXP3.M is the Parallel extension for EXP3
Time-varying extension for EXP3.M

Iteratively

Select a batch of arms
(categorical variables)

Sublinear rate on the cumulative regret

reward is time-varying
Uchiya, T., Nakamura, A. and Kudo, M., Algorithms for adversarial bandit problems with multiple plays. In International Conference on Algorithmic Learning Theory. 2010
J. Parker-Holder, V. Nguyen, S. Desai, and S. Roberts. "Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL." NeurIPS’2147

Data Augmentation and Hyper-optimization for AutoRL
Augmentation types are categorical variables
Hyperparameters are continuousRegularization, PPO clip, learning rate and entropy exploration.

J. Parker-Holder, V. Nguyen, S. Desai, and S. Roberts. "Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL." NeurIPS’21

48

Takeaway: mixed categorical-continuous Bayes opt
continuous categorical
MABBO|MAB/BO for mixed optimization
𝐴𝐴

𝐴

Local trust region for handling mixedoptimization in high dimension

Parallel time-varying bandit/BO for
population-based AutoRL
49

References
S. Gopakumar, S. Gupta, S. Rana, V. Nguyen, & S. Venkatesh. Algorithmic assurance: An active approach to algorithmic
testing using BO. NeurIPS’18
B. Ru, A. Alvi, A., V. Nguyen, M. Osborne, & S. Roberts. Bayesian optimisation over multiple continuous and categoricalinputs. ICML’20
Eriksson et al. "Scalable global optimization via local Bayesian optimization." NeurIPS’19
X. Wan, V. Nguyen, H. Ha, B. Ru, C. Lu, and M. Osborne. "Think Global and Act Local: Bayes Opt over High-Dimensional
Categorical and Mixed Search Spaces." ICML’21
Bogunovic, I., Scarlett, J., & Cevher, V. Time-varying Gaussian process bandit optimization. AISTATS 2016
Jaderberg, M., Dalibard, V., Osindero, S., Czarnecki, W.M., Donahue, J., Razavi, A., Vinyals, O., Green, T., Dunning, I.,
Simonyan, K. and Fernando, C. Population based training of neural networks. arXiv preprint arXiv:1711.09846.
J. Parker-Holder, V. Nguyen, and S. Roberts. "Provably efficient online hyperparameter optimization with population-basedbandits." NeurIPS’20
Uchiya, T., Nakamura, A. and Kudo, M., Algorithms for adversarial bandit problems with multiple plays. In International
Conference on Algorithmic Learning Theory 2010
J. Parker-Holder, V. Nguyen, S. Desai, and S. Roberts. "Tuning Mixed Input Hyperparameters on the Fly for Efficient
Population Based AutoRL." NeurIPS’21
Cocabo: https://github.com/rubinxin/CoCaBO_code
Casmopolitan: https://github.com/xingchenwan/Casmopolitan
PB2: https://github.com/jparkerholder/PB2
PB2-Mix: https://github.com/jparkerholder/procgen_autorl
50

Question and Answer
vu@ieee.org@nguyentienvu

vu-nguyen.org
github.com/ntienvu

51