Optimizer using the Hyperband (HB) algorithm.
HB runs the Successive Halving Algorithm (SHA) with different numbers of stating configurations.
The algorithm is initialized with the same parameters as Successive Halving but without n
.
Each run of Successive Halving is called a bracket and starts with a different budget r_0
.
A smaller starting budget means that more configurations can be tried out.
The most explorative bracket allocated the minimum budget r_min
.
The next bracket increases the starting budget by a factor of eta
.
In each bracket, the starting budget increases further until the last bracket s = 0
essentially performs a random search with the full budget r_max
.
The number of brackets s_max + 1
is calculated with s_max = log(r_min / r_max)(eta)
.
Under the condition that r_0
increases by eta
with each bracket, r_min
sometimes has to be adjusted slightly in order not to use more than r_max
resources in the last bracket.
The number of configurations in the base stages is calculated so that each bracket uses approximately the same amount of budget.
The following table shows a full run of HB with eta = 2
, r_min = 1
and r_max = 8
.
s | 3 | 2 | 1 | 0 | ||||||||
i | n_i | r_i | n_i | r_i | n_i | r_i | n_i | r_i | ||||
0 | 8 | 1 | 6 | 2 | 4 | 4 | 8 | 4 | ||||
1 | 4 | 2 | 3 | 4 | 2 | 8 | ||||||
2 | 2 | 4 | 1 | 8 | ||||||||
3 | 1 | 8 |
s
is the bracket number, i
is the stage number, n_i
is the number of configurations and r_i
is the budget allocated to a single configuration.
The budget hyperparameter must be tagged with "budget"
in the search space.
The minimum budget (r_min
) which is allocated in the base stage of the most explorative bracket, is set by the lower bound of the budget parameter.
The upper bound defines the maximum budget (r_max
) which is allocated to the candidates in the last stages.
Source
Li L, Jamieson K, DeSalvo G, Rostamizadeh A, Talwalkar A (2018). “Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization.” Journal of Machine Learning Research, 18(185), 1-52. https://jmlr.org/papers/v18/16-558.html.
Resources
The gallery features a collection of case studies and demos about optimization.
Tune the hyperparameters of XGBoost with Hyperband.
Use data subsampling and Hyperband to optimize a support vector machine.
Dictionary
This Optimizer can be instantiated via the dictionary
mlr_optimizers or with the associated sugar function opt()
:
$get("hyperband")
mlr_optimizersopt("hyperband")
Parameters
eta
numeric(1)
With every stage, the budget is increased by a factor ofeta
and only the best1 / eta
points are promoted to the next stage. Non-integer values are supported, buteta
is not allowed to be less or equal to 1.sampler
paradox::Sampler
Object defining how the samples of the parameter space should be drawn in the base stage of each bracket. The default is uniform sampling.repetitions
integer(1)
If1
(default), optimization is stopped once all brackets are evaluated. Otherwise, optimization is stopped afterrepetitions
runs of HB. The bbotk::Terminator might stop the optimization before all repetitions are executed.
Archive
The bbotk::Archive holds the following additional columns that are specific to HB:
bracket
(integer(1)
)
The bracket index. Counts down to 0.stage
(integer(1))
The stages of each bracket. Starts counting at 0.repetition
(integer(1))
Repetition index. Start counting at 1.
Custom Sampler
Hyperband supports custom paradox::Sampler object for initial configurations in each bracket. A custom sampler may look like this (the full example is given in the examples section):
# - beta distribution with alpha = 2 and beta = 5
# - categorical distribution with custom probabilities
= SamplerJointIndep$new(list(
sampler $new(params[[2]], function(n) rbeta(n, 2, 5)),
Sampler1DRfun$new(params[[3]], prob = c(0.2, 0.3, 0.5))
Sampler1DCateg ))
Progress Bars
$optimize()
supports progress bars via the package progressr
combined with a Terminator. Simply wrap the function in
progressr::with_progress()
to enable them. We recommend to use package
progress as backend; enable with progressr::handlers("progress")
.
Logging
Hyperband uses a logger (as implemented in lgr) from package
bbotk.
Use lgr::get_logger("bbotk")
to access and control the logger.
Super class
bbotk::Optimizer
-> OptimizerHyperband
Examples
library(bbotk)
library(data.table)
# set search space
search_space = domain = ps(
x1 = p_dbl(-5, 10),
x2 = p_dbl(0, 15),
fidelity = p_dbl(1e-2, 1, tags = "budget")
)
# Branin function with fidelity, see `bbotk::branin()`
fun = function(xs) branin_wu(xs[["x1"]], xs[["x2"]], xs[["fidelity"]])
# create objective
objective = ObjectiveRFun$new(
fun = fun,
domain = domain,
codomain = ps(y = p_dbl(tags = "minimize"))
)
# initialize instance and optimizer
instance = OptimInstanceSingleCrit$new(
objective = objective,
search_space = search_space,
terminator = trm("evals", n_evals = 50)
)
optimizer = opt("hyperband")
# optimize branin function
optimizer$optimize(instance)
#> x1 x2 fidelity x_domain y
#> 1: 2.777658 0.7909306 0.015625 <list[3]> 2.07847
# best scoring evaluation
instance$result
#> x1 x2 fidelity x_domain y
#> 1: 2.777658 0.7909306 0.015625 <list[3]> 2.07847
# all evaluations
as.data.table(instance$archive)
#> x1 x2 fidelity stage bracket repetition y
#> 1: 8.9966344 3.28530228 0.015625 0 6 1 84.352288
#> 2: 5.4096530 3.24660473 0.015625 0 6 1 40.733060
#> 3: 9.9774524 8.72528262 0.015625 0 6 1 243.444599
#> 4: -3.2637916 2.14383889 0.015625 0 6 1 88.419642
#> 5: 8.9513659 9.27182482 0.015625 0 6 1 228.098002
#> 6: -1.0360717 6.09273140 0.015625 0 6 1 17.418938
#> 7: 8.1255737 13.29660712 0.015625 0 6 1 338.620030
#> 8: 1.2302378 5.45880047 0.015625 0 6 1 15.084820
#> 9: 8.4405126 1.54708580 0.015625 0 6 1 50.790827
#> 10: -0.7912597 8.07999267 0.015625 0 6 1 17.392068
#> 11: 4.1444960 1.29261164 0.015625 0 6 1 6.686793
#> 12: 4.8588744 3.26297133 0.015625 0 6 1 29.636276
#> 13: 4.2644155 5.42833951 0.015625 0 6 1 37.833834
#> 14: 4.1175928 11.10287523 0.015625 0 6 1 128.606115
#> 15: 4.1406721 8.23899625 0.015625 0 6 1 73.726364
#> 16: 8.0078946 12.50813391 0.015625 0 6 1 307.174716
#> 17: 2.8133509 10.36772102 0.015625 0 6 1 74.904033
#> 18: 8.6051410 14.91087471 0.015625 0 6 1 416.739876
#> 19: 3.3530531 9.02724029 0.015625 0 6 1 64.901738
#> 20: -2.0295041 4.81407926 0.015625 0 6 1 26.383681
#> 21: 6.9788027 4.13654139 0.015625 0 6 1 77.374107
#> 22: 8.6446973 12.33333410 0.015625 0 6 1 319.802445
#> 23: -1.1195168 8.15761115 0.015625 0 6 1 14.301425
#> 24: 9.5849894 6.84482551 0.015625 0 6 1 176.747014
#> 25: -2.3810496 4.15587536 0.015625 0 6 1 36.776498
#> 26: 7.2880488 7.70895126 0.015625 0 6 1 151.456498
#> 27: 9.2981322 4.98740973 0.015625 0 6 1 124.298405
#> 28: 2.9460667 6.70477836 0.015625 0 6 1 26.864173
#> 29: -1.5084512 6.00472771 0.015625 0 6 1 16.679460
#> 30: -2.7889138 7.81416084 0.015625 0 6 1 9.189580
#> 31: 0.7114213 5.19229797 0.015625 0 6 1 17.368453
#> 32: 3.3998732 8.05236808 0.015625 0 6 1 51.240409
#> 33: 9.9923130 3.64388078 0.015625 0 6 1 111.674214
#> 34: -1.3609815 11.44435250 0.015625 0 6 1 22.376892
#> 35: -2.3645393 2.61957040 0.015625 0 6 1 56.672137
#> 36: 1.4415385 4.37539220 0.015625 0 6 1 11.604663
#> 37: 5.4749404 11.29736865 0.015625 0 6 1 187.964345
#> 38: 3.1039942 6.28016795 0.015625 0 6 1 24.651311
#> 39: -4.6879387 14.97035810 0.015625 0 6 1 10.460058
#> 40: -4.0227358 14.10803531 0.015625 0 6 1 5.349953
#> 41: 2.5899102 1.57518942 0.015625 0 6 1 2.081582
#> 42: 8.7345841 14.30034771 0.015625 0 6 1 396.859894
#> 43: -1.9404565 8.10107816 0.015625 0 6 1 7.747441
#> 44: 0.1502973 12.26667190 0.015625 0 6 1 61.811269
#> 45: -1.4025273 0.05347484 0.015625 0 6 1 79.492518
#> 46: -4.4385082 2.67698745 0.015625 0 6 1 128.245555
#> 47: -3.2236555 2.07024420 0.015625 0 6 1 88.412433
#> 48: 9.0017403 5.65727788 0.015625 0 6 1 133.322402
#> 49: 2.7776582 0.79093059 0.015625 0 6 1 2.078470
#> 50: 1.7764740 8.10432743 0.015625 0 6 1 31.412702
#> 51: 6.1945328 0.92230116 0.015625 0 6 1 32.534305
#> 52: -3.8796233 11.90351945 0.015625 0 6 1 3.434985
#> 53: 1.5928774 8.83764383 0.015625 0 6 1 37.822622
#> 54: -4.5978324 12.84566176 0.015625 0 6 1 10.161325
#> 55: 1.6317890 7.51113822 0.015625 0 6 1 25.626118
#> 56: 3.5939455 1.95729818 0.015625 0 6 1 3.002308
#> 57: 7.7623196 6.75405836 0.015625 0 6 1 137.566448
#> 58: 7.2250588 3.83147603 0.015625 0 6 1 75.331638
#> 59: 3.2691800 14.88095436 0.015625 0 6 1 189.687131
#> 60: 2.9898348 8.76312689 0.015625 0 6 1 53.023570
#> 61: -0.2240898 0.32407101 0.015625 0 6 1 55.772669
#> 62: -3.7718006 8.91980711 0.015625 0 6 1 14.637183
#> 63: 7.1063939 2.88910852 0.015625 0 6 1 60.704647
#> 64: 2.6406147 11.70565809 0.015625 0 6 1 95.550192
#> x1 x2 fidelity stage bracket repetition y
#> timestamp batch_nr x_domain_x1 x_domain_x2 x_domain_fidelity
#> 1: 2023-03-02 12:45:52 1 8.9966344 3.28530228 0.015625
#> 2: 2023-03-02 12:45:52 1 5.4096530 3.24660473 0.015625
#> 3: 2023-03-02 12:45:52 1 9.9774524 8.72528262 0.015625
#> 4: 2023-03-02 12:45:52 1 -3.2637916 2.14383889 0.015625
#> 5: 2023-03-02 12:45:52 1 8.9513659 9.27182482 0.015625
#> 6: 2023-03-02 12:45:52 1 -1.0360717 6.09273140 0.015625
#> 7: 2023-03-02 12:45:52 1 8.1255737 13.29660712 0.015625
#> 8: 2023-03-02 12:45:52 1 1.2302378 5.45880047 0.015625
#> 9: 2023-03-02 12:45:52 1 8.4405126 1.54708580 0.015625
#> 10: 2023-03-02 12:45:52 1 -0.7912597 8.07999267 0.015625
#> 11: 2023-03-02 12:45:52 1 4.1444960 1.29261164 0.015625
#> 12: 2023-03-02 12:45:52 1 4.8588744 3.26297133 0.015625
#> 13: 2023-03-02 12:45:52 1 4.2644155 5.42833951 0.015625
#> 14: 2023-03-02 12:45:52 1 4.1175928 11.10287523 0.015625
#> 15: 2023-03-02 12:45:52 1 4.1406721 8.23899625 0.015625
#> 16: 2023-03-02 12:45:52 1 8.0078946 12.50813391 0.015625
#> 17: 2023-03-02 12:45:52 1 2.8133509 10.36772102 0.015625
#> 18: 2023-03-02 12:45:52 1 8.6051410 14.91087471 0.015625
#> 19: 2023-03-02 12:45:52 1 3.3530531 9.02724029 0.015625
#> 20: 2023-03-02 12:45:52 1 -2.0295041 4.81407926 0.015625
#> 21: 2023-03-02 12:45:52 1 6.9788027 4.13654139 0.015625
#> 22: 2023-03-02 12:45:52 1 8.6446973 12.33333410 0.015625
#> 23: 2023-03-02 12:45:52 1 -1.1195168 8.15761115 0.015625
#> 24: 2023-03-02 12:45:52 1 9.5849894 6.84482551 0.015625
#> 25: 2023-03-02 12:45:52 1 -2.3810496 4.15587536 0.015625
#> 26: 2023-03-02 12:45:52 1 7.2880488 7.70895126 0.015625
#> 27: 2023-03-02 12:45:52 1 9.2981322 4.98740973 0.015625
#> 28: 2023-03-02 12:45:52 1 2.9460667 6.70477836 0.015625
#> 29: 2023-03-02 12:45:52 1 -1.5084512 6.00472771 0.015625
#> 30: 2023-03-02 12:45:52 1 -2.7889138 7.81416084 0.015625
#> 31: 2023-03-02 12:45:52 1 0.7114213 5.19229797 0.015625
#> 32: 2023-03-02 12:45:52 1 3.3998732 8.05236808 0.015625
#> 33: 2023-03-02 12:45:52 1 9.9923130 3.64388078 0.015625
#> 34: 2023-03-02 12:45:52 1 -1.3609815 11.44435250 0.015625
#> 35: 2023-03-02 12:45:52 1 -2.3645393 2.61957040 0.015625
#> 36: 2023-03-02 12:45:52 1 1.4415385 4.37539220 0.015625
#> 37: 2023-03-02 12:45:52 1 5.4749404 11.29736865 0.015625
#> 38: 2023-03-02 12:45:52 1 3.1039942 6.28016795 0.015625
#> 39: 2023-03-02 12:45:52 1 -4.6879387 14.97035810 0.015625
#> 40: 2023-03-02 12:45:52 1 -4.0227358 14.10803531 0.015625
#> 41: 2023-03-02 12:45:52 1 2.5899102 1.57518942 0.015625
#> 42: 2023-03-02 12:45:52 1 8.7345841 14.30034771 0.015625
#> 43: 2023-03-02 12:45:52 1 -1.9404565 8.10107816 0.015625
#> 44: 2023-03-02 12:45:52 1 0.1502973 12.26667190 0.015625
#> 45: 2023-03-02 12:45:52 1 -1.4025273 0.05347484 0.015625
#> 46: 2023-03-02 12:45:52 1 -4.4385082 2.67698745 0.015625
#> 47: 2023-03-02 12:45:52 1 -3.2236555 2.07024420 0.015625
#> 48: 2023-03-02 12:45:52 1 9.0017403 5.65727788 0.015625
#> 49: 2023-03-02 12:45:52 1 2.7776582 0.79093059 0.015625
#> 50: 2023-03-02 12:45:52 1 1.7764740 8.10432743 0.015625
#> 51: 2023-03-02 12:45:52 1 6.1945328 0.92230116 0.015625
#> 52: 2023-03-02 12:45:52 1 -3.8796233 11.90351945 0.015625
#> 53: 2023-03-02 12:45:52 1 1.5928774 8.83764383 0.015625
#> 54: 2023-03-02 12:45:52 1 -4.5978324 12.84566176 0.015625
#> 55: 2023-03-02 12:45:52 1 1.6317890 7.51113822 0.015625
#> 56: 2023-03-02 12:45:52 1 3.5939455 1.95729818 0.015625
#> 57: 2023-03-02 12:45:52 1 7.7623196 6.75405836 0.015625
#> 58: 2023-03-02 12:45:52 1 7.2250588 3.83147603 0.015625
#> 59: 2023-03-02 12:45:52 1 3.2691800 14.88095436 0.015625
#> 60: 2023-03-02 12:45:52 1 2.9898348 8.76312689 0.015625
#> 61: 2023-03-02 12:45:52 1 -0.2240898 0.32407101 0.015625
#> 62: 2023-03-02 12:45:52 1 -3.7718006 8.91980711 0.015625
#> 63: 2023-03-02 12:45:52 1 7.1063939 2.88910852 0.015625
#> 64: 2023-03-02 12:45:52 1 2.6406147 11.70565809 0.015625
#> timestamp batch_nr x_domain_x1 x_domain_x2 x_domain_fidelity