HyperBand - Trajectory possibly wrong.

[CreaperLost]

Description

I run hyperband and got the history and trajectory results.
I specify as budget the number of estimators for XGB (simplified example)

In some cases, the final value in trajectory is not the minimum value of the history. (Trajectory selects the best from the final bracket (highest budget)) However, the hyperband algorithm should select the best from all brackets. So the history can contain a configuration with better performance in a early bracket ( n_est =50 for example ) vs a configuration with 500 estimators in the third bracket.

I think this should be fixed.

Version 2.0.0

Sorry, I don't know how to label this issue etc.

[helegraf]

Hi, thanks for opening an issue on this. Could you give some more details on your simplified example, i.e. a runhistory + trajectory that exhibits the behavior, + how you configured SMAC?

[CreaperLost]

The configuration of SMAC is done simply by adding min-budget 1, max-budget 3 (in scenario object). I used the Hyperband object to instantiate the run.

I simply use the final history and trajectory. I passed the cost of each trial in two lists. One for history. One for Trajectory. Then compared the minimum values.

I tested across 20 datasets and this is happening in 2-3 of them. I guess. My guess is that the hyper-band trajectory is calculated on the max-budget only. However, lower budgets are run on the same data, but just with less n_estimators. N_estimators may indeed improve performance of a configuration (given the other hyper-parameters constant). However, for models like XGBoost this is not always the case.

I think replicating a simple function call to XGBoost with varying n_estimaros can show the difference. Please note that I work on CASH problem, so I name budget =1,2,3 but then on the configuration set budget =1 --> n_estimators = 100 for RF, and n_estimators = 50 for XGBoost and the continue. Essentially a budget == 1 is converted differently for each classifier. (SVMs subsample the training set etc.)

I think a simple example can replicate that issue on your end. Try HPOBench configuration for XGBoost with the Hyperband object. Hope that helps.

I solve my problem for now by using the History Object to essentially give an unbiased performance of HB based methods. I expect this behaviour to be the same on SMAC-HB possibly?

[helegraf]

Thanks! A few notes regarding the general usage of SMAC's HyperBand implementation:

• The incumbent selection is not aware of the different brackets going on, so this is not where this behavior comes from.
• There are different incumbent selection strategies that you can choose (see documentation of the successive halving superclass). The default is highest_observed_budget. It only considers the highest evaluated budget for each configuration when selecting the incumbent, including for the current incumbent.
• The cost values in the trajectory are not updated when a new cost for a config becomes known after intensifying it. In the trajectory, each config is inserted with the cost it had at the moment of becoming incumbent. So for example, if a config A has cost 5 on budget 1 and is incumbent, then gets evaluated on budget 2 with cost 10, but another config B has been evaluated with cost 7 on budget 1, then B will be incumbent according to highest_observed_budget. This will be reflected in the trajectory as (A, 5), (B, 7) (simplified). So this way, the final value is not the minimum of the history. If this selection strategy is not what you want, you need to choose the any_budget or highest_budget selection strategy.

If this doesn't help, it would be great if you could include a code snippet for the instantiation (minimal example with transcript of runhistory and trajectory).